Symbolic computation of multidimensional Fenchel conjugates

ABSTRACT

Convex optimization is a branch of mathematics dealing with non-linear optimization problems with additional geometric structure. This area has been the focus of considerable recent research due to the fact that convex optimization problems are scalable and can be efficiently solved by interior-point methods. Over the last ten years or so, convex optimization has found new applications in many areas including control theory, signal processing, communications and networks, circuit design, data analysis and finance.Of key importance in convex optimization is the notion of duality, and in particular that of Fenchel duality. This work explores algorithms for calculating symbolic Fenchel conjugates of a class of real-valued functions defined on Rⁿ, extending earlier work to the non-separable multi-dimensional case. It also explores the potential application of the developed algorithms to automatic inequality proving.

REFERENCES

• 1: L. Ahlfors. Complex Analysis. McGraw-Hill, New York, 1966.
• 2: A. Auslender and M. Teboulle. Asymptotic Cones and Functions in Optimization and Variational Inequalities. Springer-Verlag, 2003.
• 3: H.H. Bauschke and M. v. Mohrenschildt. Fenchelconjugates and subdifferentiation in Maple. Technical Report CORR 97-23, Department of Combinatorics and Optimization, University of Waterloo, 1997.
• 4: H.H. Bauschke and M. v. Mohrenschildt. Symbolic computation of Fenchel conjugates. ACM SIGSAM Bulletin, 2006. To appear.
• 5: J.M. Borwein and C.H. Hamilton. Symbolic Fenchel conjugation. Special Issue of Mathematical Programming Series B, 2006. Submitted.
• 6: J.M. Borwein and A.S. Lewis. Convex Analysis and Nonlinear Optimization. CMS Books in Mathematics. Springer-Verlag, New York, 2000.
• 7: J.M. Borwein, P. Maréchal, and D. Naugler. A convex dual approach to the computation of NMR complex spectra. Mathematical Methods of Operations Research, 51(1):90--102, 2000.
• 8: Stephen Boyd , Lieven Vandenberghe, Convex Optimization, Cambridge University Press, New York, NY, 2004
• 9: Lucilla Corrias, Fast Legendre--Fenchel Transform and Applications to Hamilton--Jacobi Equations and Conservation Laws, SIAM Journal on Numerical Analysis, v.33 n.4, p.1534-1558, Aug. 1996 [doi>10.1137/S0036142993260208]
• 10: Stefan Gerhold , Manuel Kauers, A procedure for proving special function inequalities involving a discrete parameter, Proceedings of the 2005 international symposium on Symbolic and algebraic computation, p.156-162, July 24-27, 2005, Beijing, China [doi>10.1145/1073884.1073907]
• 11: C.H. Hamilton. Symbolic convex analysis. Master's thesis, Department of Mathematics and Statistics, Simon Fraser University, April 2005.
• 12: J.C. Hoch, A.S. Stern, D.L. Donoho, and I.M Johnstone. Maximum entropy reconstruction of complex (phase-sensitive) spectra. Journal of Magnetic Resonance, 86:236--246, 1990.
• 13: Y. Lucet, A fast computational algorithm for the Legendre-Fenchel transform, Computational Optimization and Applications, v.6 n.1, p.27-57, July 1996
• 14: Y. Lucet. Faster than the fast Legendre transform, the linear-time Legendre transform. Numerical Algorithms, 16:171--185, 1997.
• 15: David G. Luenberger, Optimization by Vector Space Methods, John Wiley & Sons, Inc., New York, NY, 1997
• 16: R.T. Rockafeller. Convex Analysis. Princeton University Press, Princeton, NJ, 1970.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Convex programming

General Terms:
Algorithms, Theory

Keywords:
Fenchel conjugate, Legendre-Fenchel transform, computer proofs, inequalities, subdifferential, subgradient