GloptiPoly 2 - Global
Optimization over Polynomials with Matlab and SeDuMi
Description
GloptiPoly is a Matlab/SeDuMi add-on to build and solve
convex linear matrix inequality (LMI) relaxations of the
(generally non-convex) global optimization problem of minimizing a
multivariable polynomial function subject to
polynomial inequality, equality or integer constraints.
The software generates a series of lower bounds monotonically converging
to the global optimum. Global optimality is detected and isolated
optimal solutions are extracted automatically.
Numerical experiments show that for most of the
small- and medium-scale problems described in the literature, the
global optimum is reached at low computational cost.
Applications
Potential applications of GloptiPoly include resolution of polynomial
systems of equations, minimum-distance problems, non-convex quadratic
programming problems, combinatorial optimization, dynamic system
robustness analysis or non-linear system stability analysis.
Particular problem instances and application examples are welcome.
Please forward your data to henrion@laas.fr
User's guide
A comprehensive user's guide is available (
PDF file version 2.3.0).
Several typical problem examples (non-convex quadratic programming,
polynomial programming, Max-Cut) and computational benchmarks (with
continuous and discrete variables) are included.
Warning
The current version of GloptiPoly is aimed at small- and medium-scale
problems only. For example, it cannot handle quadratic optimization
problems with more than 19 variables. This limitation may be removed
in the future.
References
GloptiPoly is based on the theory of moments and positive polynomials
described in:
J. B. Lasserre. Global optimization with polynomials and the problem
of moments. SIAM Journal on Optimization, Vol. 11, No. 3,
pp. 796-817, 2001.
J. B. Lasserre. An explicit equivalent positive semidefinite program
for nonlinear 0-1 programms. SIAM Journal on Optimization, Vol. 12,
No. 3, pp. 756-769, 2002.
Please use the following citation when referring to the software:
D. Henrion, J. B. Lasserre. GloptiPoly: Global optimization over
polynomials with Matlab and SeDuMi. ACM Transactions on Mathematical
Software, Vol. 29, No. 2, pp. 165-194, June 2003.
Research reports
A preliminary version of the above ACM TOMS paper was described in the
following research report, including benchmark examples of continuous and
discrete optimization problems:
D. Henrion, J. B. Lasserre.
GloptiPoly: Global Optimization over Polynomials with Matlab and
SeDuMi. LAAS-CNRS Research Report No. 02057, January 2002.
Proceedings of the IEEE Conference on Decision and Control, Las
Vegas, Nevada, December 10-13, 2002.
Additional benchmark examples of polynomial systems of
equations can be found in the following reseach report:
D. Henrion, J. B. Lasserre.
Solving global Optimization Problems over Polynomials with GloptiPoly
2.1. LAAS-CNRS Research Report No. 02289, July 2002.
Proceedings of the International Workshop on Global Constrained
Optimization and Constraint Satisfaction (Cocos'02), Sophia Antipolis,
France, October 2-4, 2002. Journal version appeared in C. Bliek,
C. Jermann, A. Neumaier (Editors). Global Optimization and Constraint
Satisfaction. Lecture Notes on Computer Science, Volume 2861,
pp. 43-58, Springer Verlag, Berlin, 2003.
The following research report describes various applications
of GloptiPoly in control theory:
D. Henrion, J. B. Lasserre.
Convergent
LMI relaxations for non-convex optimization over polynomials in
control. LAAS-CNRS Research Report No. 02396, September
2002. A revised version entitled "Solving nonconvex optimization
problems - How GloptiPoly is applied to problems in robust and
nonlinear control " appeared in the IEEE Control Systems Magazine,
Vol. 24, No. 3, pp. 72-83, 2004. See also the
corrigendum
reporting several typos in the published version.
The solution extraction algorithm implemented in GloptiPoly is
described in the following report:
D. Henrion, J. B. Lasserre.
Detecting
global optimality and
extracting solutions in GloptiPoly. LAAS-CNRS Research Report No. 03541,
October 2003. Contributed chapter in the book
D. Henrion, A. Garulli (Editors). Positive polynomials in
control. Lecture Notes on Control and Information Sciences, Springer
Verlag, 2005.
Download
GloptiPoly is a freeware subject to the General Public Licence (GPL)
policy.
GloptiPoly requires Matlab
version 5.3 or higher and the freeware SeDuMi
1.1. It consists of a unique source file:
gloptipoly.m
(version 2.3.2 - August 21, 2006)
Additional optional files described in the user's guide are also available:
testpoly.m
- check objective function and feasibility at a point;
defipoly.m
- symbolic definition of polynomial expressions (requires The Symbolic Math
Toolbox 2.1 or higher);
defilin.m
- easy definition of linear expressions Ax+b;
defiquad.m
- easy definition of quadratic expressions x'Ax+2b'x+c;
defimaxcut.m
- easy definition of Max-Cut problems.
Other platforms
In January 2009, Jean-Philippe Chancelier ported GloptiPoly 2 to
NSP, a public-domain
scientific package of the Scilab family, a freeware alternative to Matlab. SeDuMi
is also available for NSP.
New version
A version 3
is now available, including all the features of version 2, and much more.
Version 2 will not be updated anymore.
Last updated on 13 February 2009.