Source-linked AI summary
GloptiPoly 3: moments, optimization and semidefinite programming
Didier Henrion, Jean Bernard Lasserre, Johan Lofberg
TL;DR
GloptiPoly 3 addresses polynomial-data moment problems and the difficulty of representing such problems computationally. It builds semidefinite-programming hierarchies whose optimal values converge to the global optimum, while constrained cases may not ensure global optimality.
Problem
Polynomial-data moment problems can be difficult to represent computationally in an efficient way.
Method
GloptiPoly 3 parses generalized problems of moments, including several measures with semialgebraic structure, and builds semidefinite-programming hierarchies.
Results
The resulting hierarchy has optimal values that converge to the global optimum, with numerical extraction of two globally optimal solutions demonstrated.
Takeaways & Limitations
GloptiPoly 3 provides freeware Matlab support for numerically handling polynomial-data moment problems through semidefinite programming.
Takeaways & Limitations
Global optimality cannot be ensured for the constrained polynomial optimization problem.
Abstract
from arXiv · showhide
We describe a major update of our Matlab freeware GloptiPoly for parsing generalized problems of moments and solving them numerically with semidefinite programming.
1 What is GloptiPoly ?
GloptiPoly 3 targets generalized problems of moments with polynomial data, which arise across mathematics and applications. It builds semidefinite-programming relaxations whose optimal values converge to the global optimum.
- Generalized problems of moments extend the classical problem of moments and have applications in optimization, probability, finance, control, and signal processing.
- GloptiPoly 3 handles generalized problems of moments with polynomial data.
- The software builds a hierarchy of semidefinite-programming or linear-matrix-inequality relaxations for generalized problems of moments.
- The associated monotone sequence of optimal values converges to the global optimum.
2 Installation
GloptiPoly 3 is distributed as Matlab source under the GPL and requires installation on the Matlab working path. It uses SeDuMi by default, while other semidefinite solvers can be connected through YALMIP.
- GloptiPoly 3 is freeware distributed under the General Public Licence.
- The package contains Matlab files and subdirectories that should be placed in a gloptipoly3 directory on the Matlab working path.
- SeDuMi is the default semidefinite-programming solver for GloptiPoly 3.
- Other semidefinite solvers can be used when installed and interfaced through YALMIP.
3 Getting started
The getting-started example models the six-hump camel function as a moment problem and solves it with a semidefinite solver. GloptiPoly extracts two globally optimal solutions and reports successful numerical solution status.
- The six-hump camel function has six local minima, including two global minima.
- The example models the polynomial optimization problem as a moment problem and generates a moment semidefinite-programming problem.
- 2 globally optimal solutions are extracted in the example.
- The status flag equal to 1 indicates successful solution of the moment problem.
- GloptiPoly extracts two globally optimal solutions reaching the objective function.
4 From version 2 to version 3
GloptiPoly 3 broadens solver compatibility and replaces required symbolic processing with native polynomial objects. It also supports richer generalized moment problems involving multiple measures, semialgebraic supports, and linear moment constraints.
- Native polynomial objects and object-oriented programming provide classes for polynomials, measures, and moments.
- The Matlab Symbolic Toolbox is no longer required to process polynomial data.
- GloptiPoly 3 processes generalized moment problems with several measures, semialgebraic support constraints, and linear moment constraints.
- Explicit moment substitutions reduce the number of variables.
- GloptiPoly 3 supports numerical solution with any semidefinite solver interfaced through YALMIP.
5 Solving generalized problems of moments
GloptiPoly 3 represents generalized problems of moments through object-oriented Matlab classes for polynomials, measures, moments, and constraints. It supports multiple measures, semialgebraic support restrictions, and linear moment relations.
- Objects and measures: GloptiPoly 3 uses Matlab classes and overloaded operators to represent multivariate polynomials, variables, measures, moments, and constraints.Variables, monomials, and polynomials use class mpol; moment constraints use momcon objects, while support constraints use supcon objects.
- Objects and measures: Variables can be associated with real-valued measures, including measures on different numbers of variables.The examples create dµ1(x) on R and dµ2(y) on R2, and measures are identified by positive-integer labels.
- Moments: Moments are represented as polynomial integrals with respect to a selected measure, whose label identifies the measure involved.The notation I[p]d[k] denotes the integral of polynomial p against measure dµk.
- Modeling restrictions: Moment expressions cannot be defined over several measures or be nonlinear in moments, and support constraints cannot be imposed on several measures.These restrictions define the modeling boundaries for moment and support constraints.
- Support constraints: A measure’s support can be restricted to a semialgebraic set, including finite points or geometric regions such as the unit disk.A polynomial equality can force dµ1(x) to be a combination of Dirac measures at 1, −1, and −2, while an inequality restricts dµ2(y) to the unit disk.
- Moment constraints: GloptiPoly 3 can handle several measures whose moments are linearly related.Moment constraints are modeled through linear relations among moments, while objectives are treated as particular moment constraints.
5.6 Floating point numbers (double)
GloptiPoly 3 represents generalized moment problems through measures and moments, then solves their semidefinite relaxations numerically. It supports polynomial and constrained optimization, with solutions that can certify or approximate global optima depending on the relaxation and problem status.
- Moment formulation: GloptiPoly 3 models generalized problems of moments using measures supported on basic semialgebraic sets and optimizes over their moments.The moment formulation uses polynomial data, multi-indexed moments, and support constraints defined by polynomial inequalities.
- Numerical solution: The software provides user-friendly problem input and solves moment formulations with existing semidefinite-programming software.Moment problems are defined and then solved numerically using commands such as msol and msdp.
- Constrained minimization: For the constrained quadratic example, status=0 prevents detection of global optimality, while obj=-6.0000 remains a lower bound on the global minimum.The corresponding moment SDP is solved, but the reported status does not certify that the lower bound is globally attained.
- Constrained minimization: The relaxation hierarchy generates monotonically increasing lower bounds that converge asymptotically to the global optimum under mild technical assumptions.The default relaxation has order equal to half the highest monomial degree, while higher-order relaxations can be requested.
- Several measures: GloptiPoly 3 handles several measures with linearly related moments, including occupation and performance measures in polynomial optimal control.For the double integrator, the lower bound on minimum time is narrowed by enlarging the class of test functions.
5.9 Using YALMIP
GloptiPoly 3 uses SeDuMi by default for numerical SDP moment problems but can route them through any solver interfaced by YALMIP. YALMIP solver and parameter settings are passed through mset.
- SeDuMi is GloptiPoly 3’s default solver for numerical SDP moment problems.
- Any solver interfaced through YALMIP can be selected by setting a configuration flag with mset.
- YALMIP parameters handled by sdpsettings can be forwarded to GloptiPoly 3 with mset.
- The example configures YALMIP to use SDPT3 instead of SeDuMi for GloptiPoly moment problems.
5.10 SeDuMi parameters settings
GloptiPoly 3 allows users to alter SeDuMi’s default parameter settings by supplying a parameter structure in SeDuMi’s format.
- SeDuMi’s default parameter settings can be altered in GloptiPoly 3.
- The parameter structure pars must use a format consistent with SeDuMi’s parameters.
5.11 Exporting moment SDP problems
GloptiPoly 3 can export moment SDP problems to SeDuMi or YALMIP input formats, after which the problems can be solved with the corresponding solver interfaces.
- A moment problem of class msdp can be converted into SeDuMi’s input format and solved with SeDuMi.
- The SeDuMi input data format is documented in reference.
- A moment SDP problem can likewise be converted into YALMIP’s input format.
- In the YALMIP representation, F contains LMI constraints, h is the objective function, and y is the vector of moments.
- The exported YALMIP SDP problem can be solved with any semidefinite solver interfaced through YALMIP.
5.12 Moment substitutions
GloptiPoly 3 generalizes moment substitutions and can substantially reduce moment SDP size when support or moment equalities isolate monic monomials. In the Max-Cut example, 5005 candidate moments reduce to 465 independent moments in a 130-dimensional matrix.
- 5.12 Moment substitutions: Moment substitutions can significantly reduce the number of variables and constraints in moment SDP problems.
- 5.12 Moment substitutions: Version 3 extends substitutions from mixed-integer 0-1 problems to full generality.
- 5.12 Moment substitutions: GloptiPoly 3 substitutes an isolated monic monomial in a support or moment equality constraint, while preserving other equalities.
- 5.12 Moment substitutions: The example applies these substitutions to the AW 9^2 Max-Cut problem with variables taking values −1 or +1.
- 5.12 Moment substitutions: 465 linearly independent moments remain from 5005 moments of degree up to 6 for 9 variables, forming a reduced moment matrix of dimension 130.