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.