GloptiPoly: Global optimization over polynomials with Matlab and SeDuMi

ABSTRACT

GloptiPoly is a Matlab/SeDuMi add-on to build and solve convex linear matrix inequality relaxations of the (generally nonconvex) global optimization problem of minimizing a multivariable polynomial function subject to polynomial inequality, equality, or integer constraints. It generates a series of lower bounds monotonically converging to the global optimum without any problem splitting. Global optimality is detected and isolated optimal solutions are extracted automatically. Numerical experiments show that for most of the small-scale problems described in the literature, the global optimum is reached at low computational cost.

REFERENCES

• 1: Anjos, M. 2001. New convex relaxations for the maximum cut and VLSI layout problems. Ph.D. dissertation. Waterloo University, Waterloo, Ont., Canada. See orion.math.uwaterloo.ca/∼hwolkowi.
• 2: Ben-Saad, S. 1989. An algorithm for a class of nonlinear nonconvex optimization problems. Ph.D. dissertation. University of California, Los Angeles, CA.
• 3: Bondyfalat, D., Mourrain, B., and Pan, V. Y. 2000. Computation of a specified root of a polynomial system of equations using eigenvectors. Linear Algebra and its Applications, 319, 1--3, 193--209.
• 4: Robert M. Corless , Patrizia M. Gianni , Barry M. Trager, A reordered Schur factorization method for zero-dimensional polynomial systems with multiple roots, Proceedings of the 1997 international symposium on Symbolic and algebraic computation, p.133-140, July 21-23, 1997, Kihei, Maui, Hawaii, United States [doi>10.1145/258726.258767]
• 5: Dixon, L. C. W. and Szegö, G. P. 1975. Towards global optimization. North-Holland, Amsterdam, The Netherlands.
• 6: Floudas, C. A., Pardalos, P. M., Adjiman, C. S., Esposito, W. R., Gümüs, Z. H., Harding, S. T., Klepeis, J. L., Meyer, C. A., and Schweiger, C. A. 1999. Handbook of Test Problems in Local and Global Optimization. Kluwer, Dordrecht, The Netherlands. See titan.princeton.edu/TestProblems
• 7: Michel X. Goemans , David P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, Journal of the ACM (JACM), v.42 n.6, p.1115-1145, Nov. 1995 [doi>10.1145/227683.227684]
• 8: D. Henrion , S. Tarbouriech , D. Arzelier, LMI approximation for the Radius of the intersection of ellipsoids: survey, Journal of Optimization Theory and Applications, v.108 n.1, p.1-28, Jan. 2001 [doi>10.1023/A:1026454804250]
• 9: Jean B. Lasserre, Global Optimization with Polynomials and the Problem of Moments, SIAM Journal on Optimization, v.11 n.3, p.796-817, 2000 [doi>10.1137/S1052623400366802]
• 10: Jean B. Lasserre, An Explicit Equivalent Positive Semidefinite Program for Nonlinear 0-1 Programs, SIAM Journal on Optimization, v.12 n.3, p.756-769, 2002 [doi>10.1137/S1052623400380079]
• 11: Lasserre, J. B. 2002b. Polynomials nonnegative on a grid and discrete optimization. Trans. Amer. Math. Soc. 354, 2, 631--649.
• 12: Nesterov, Y. 2000. Squared functional systems and optimization problems. In High Performance Optimization, H. Frenk, K. Roos, and T. Terlaky (Eds.). Kluwer, Dordrecht, The Netherlands, Chap. 17, 405--440.
• 13: Parrilo, P. A. 2000. Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization. Ph.D. dissertation. California Institute of Technology, Pasadena, CA. See www.control.ethz.ch/∼parrilo.
• 14: Parrilo, P. A. 2003. Semidefinite programming relaxations for semialgebraic problems. Math. Program. Ser. B 96, 2, 293--320.
• 15: Putinar, M.1993. Positive polynomials on compact semi-algebraic sets. Indiana Univ. Math. J. 42, 3, 969--984.
• 16: Hanif D. Sherali , Warren P. Adams, A hierarchy of relaxation between the continuous and convex hull representations, SIAM Journal on Discrete Mathematics, v.3 n.3, p.411-430, Aug. 1990 [doi>10.1137/0403036]
• 17: Sherali, H. D. and Adams, W. P. 1999. A reformulation-linearization technique for solving discrete and continuous nonconvex problems. Kluwer, Dordrecht, The Netherlands.
• 18: Shor, N. Z. 1987. Quadratic optimization problems. Tekhn. Kibernet. 1, 128--139.
• 19: Shor, N. Z. 1998. Nondifferentiable optimization and polynomial problems. Kluwer, Dordrecht, The Netherlands.
• 20: Soland, R. M. 1971. An algorithm for separable nonconvex programming problems---II: Nonconvex constraints. Manag. Sci. 17, 759--773.
• 21: Sturm, J. F. 1999. Using SeDuMi 1.02, a Matlab Toolbox for Optimization over Symmetric Cones. Opt. Meth. Softw. 11--12, 625--653. Version 1.05 available at fewcal.kub.nl/sturm.
• 22: The MathWorks Inc. 2001. Matlab version 6.1. The Mathworks Inc., Natick, MA. See www.mathworks.com.
• 23: Lieven Vandenberghe , Stephen Boyd, Semidefinite programming, SIAM Review, v.38 n.1, p.49-95, Mar. 1996 [doi>10.1137/1038003]
• 24: Waterloo Maple Software Inc. 2001. Maple V release 5. Waterloo, Ont., Canada. See www. maplesoft.com.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Constrained optimization

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Integer programming; Global optimization

  J. Computer Applications
  J.2 PHYSICAL SCIENCES AND ENGINEERING
      Subjects: Mathematics and statistics

General Terms:
Algorithms, Documentation, Experimentation

Keywords:
Matlab, Polynomial programming, SeDuMi, linear matrix inequality, semidefinite programming