Didier Henrion
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.
- 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.Google Scholar
- Ben-Saad, S. 1989. An algorithm for a class of nonlinear nonconvex optimization problems. Ph.D. dissertation. University of California, Los Angeles, CA.Google Scholar
- 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.Google Scholar
- Corless, R. M., Gianni, P. M., and Trager, B. M. 1997. A reordered schur factorization method for zero-dimensional polynomial systems with multiple roots. In Proceedings of the ACM International Symposium on Symbolic and Algebraic Computation (Maui, HI). 133--140. Google Scholar
- Dixon, L. C. W. and Szegö, G. P. 1975. Towards global optimization. North-Holland, Amsterdam, The Netherlands.Google Scholar
- 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/TestProblemsGoogle Scholar
- Goemans, M. X. and Williamson, D. P. 1995. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42, 6, 1115--1145. Google Scholar
- Henrion, D., Tarbouriech, S., and Arzelier, D. 2001. LMI approximations for the radius of the intersection of ellipsoids. J. Opt. Theory Appl. 108, 1, pp. 1--28. Google Scholar
- Lasserre, J. B. 2001. Global optimization with polynomials and the problem of moments. SIAM J. Opt. 11, 3, 796--817. Google Scholar
- Lasserre, J. B. 2002a. An explicit equivalent positive semidefinite program for 0--1 nonlinear programs. SIAM J. Opt. 12, 3, 756--769. Google Scholar
- Lasserre, J. B. 2002b. Polynomials nonnegative on a grid and discrete optimization. Trans. Amer. Math. Soc. 354, 2, 631--649.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- Parrilo, P. A. 2003. Semidefinite programming relaxations for semialgebraic problems. Math. Program. Ser. B 96, 2, 293--320.Google Scholar
- Putinar, M.1993. Positive polynomials on compact semi-algebraic sets. Indiana Univ. Math. J. 42, 3, 969--984.Google Scholar
- Sherali, H. D. and Adams, W. P. 1990. A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM J. Discr. Math. 3, 3, 411--430. Google Scholar
- Sherali, H. D. and Adams, W. P. 1999. A reformulation-linearization technique for solving discrete and continuous nonconvex problems. Kluwer, Dordrecht, The Netherlands.Google Scholar
- Shor, N. Z. 1987. Quadratic optimization problems. Tekhn. Kibernet. 1, 128--139.Google Scholar
- Shor, N. Z. 1998. Nondifferentiable optimization and polynomial problems. Kluwer, Dordrecht, The Netherlands.Google Scholar
- Soland, R. M. 1971. An algorithm for separable nonconvex programming problems---II: Nonconvex constraints. Manag. Sci. 17, 759--773.Google Scholar
- 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.Google Scholar
- The MathWorks Inc. 2001. Matlab version 6.1. The Mathworks Inc., Natick, MA. See www.mathworks.com.Google Scholar
- Vandenberghe, L. and Boyd, S. 2001. Semidefinite programming. SIAM Rev. 38, 1 (March), 49--95. Google Scholar
- Waterloo Maple Software Inc. 2001. Maple V release 5. Waterloo, Ont., Canada. See www. maplesoft.com.Google Scholar
Index Terms
- GloptiPoly: Global optimization over polynomials with Matlab and SeDuMi
Recommendations
Cones of Matrices and Successive Convex Relaxations of Nonconvex Sets
Let F be a compact subset of the n-dimensional Euclidean space Rn represented by (finitely or infinitely many) quadratic inequalities. We propose two methods, one based on successive semidefinite programming (SDP) relaxations and the other on successive ...
Second-Order Cone Relaxations for Binary Quadratic Polynomial Programs
Several types of relaxations for binary quadratic polynomial programs can be obtained using linear, second-order cone, or semidefinite techniques. In this paper, we propose a general framework to construct conic relaxations for binary quadratic ...
An Exact Duality Theory for Semidefinite Programming Based on Sums of Squares
Farkas' lemma is a fundamental result from linear programming providing linear certificates for infeasibility of systems of linear inequalities. In semidefinite programming, such linear certificates only exist for strongly infeasible linear matrix ...
Comments