# GpoSolver

A MATLAB/C++ Toolbox for Global Polynomial Optimization

# Documentation

The authoritative documentation is the PDF document gposolver-VERSION.pdf, located in the directory doc in the distribution archive of the respective GpoSolver version. The documentation for the latest version of GpoSolver can be downloaded from here:

# Problems solvable by GpoSolver

Let , , be multivariate polynomials in , i.e.,  [4]. The polynomial optimization problem (POP) can be stated as follows:
Problem 1 (Polynomial optimization problem)
Since polynomial equalities can be expressed using pairs of opposite inequalities, i.e., POP encompasses all polynomial optimization problems. In general, POP is an NP-hard problem. In [6], Lasserre suggested to convexify POP using a hierarchy of semidefinite (SDP) relaxations , Since the SDP problems take the form of linear matrix inequalities (LMI), the hierarchy is sometimes called Lasserre’s LMI hierarchy and is called a LMI relaxation of order . The most agreeable property of Lasserre’s hierarchy is the fact that the minima of form a monotonically non-decreasing sequence of the lower bounds on the global minimum of Problem 1↑. Moreover, in most cases a relaxation , exists such that its minimum is equal to the global minimum of Problem 1↑.
Another optimization problem, closely related to POP, is the polynomial matrix inequalities (PMI) optimization problem:
Problem 2 (Polynomial matrix inequalities optimization problem)
Here, stands for the set of symmetric matrices with polynomial entries and the condition means that the polynomial matrix is positive semidefinite. Note that if , , Problem 2↑ becomes equivalent to Problem 1↑, i.e., POP is a subset of PMI. Also note that if the polynomial degree of and the maximal polynomial degree of all the entries of , , is one, PMI becomes LMI. Even though PMI is a strict superset of POP, it was shown in [5] that PMI is amendable to solution using an LMI hierarchy analogous to the LMI hierarchy for POP. GpoSolver implements solutions for PMI, POP, and LMI problems. We refer to these problems by the name of the largest problem set as PMI problems.
GpoSolver is a Matlab toolbox/C++ library for solving POP and PMI problems using the Lasserre’s LMI hierarchy approach. It aims at situations where one wishes to repeatedly solve instances of a specific PMI problem with coefficients arising from concrete physical measurements. It combines several advantages. It is able to solve and to recover multiple global minima of both POP and PMI, it does not need the Matlab environment in the problem solving phase, it interfaces several SDP solvers, and it is used as a C++ template library, i.e., there is no need for additional standalone executable.

# Workflow

The purpose of GpoSolver is to provide a convenient way to repeatedly solve PMI problems with a common underlying structure. In the next, we will borrow from the nomenclature of the object oriented programming languages and call this underlying structure a PMI class. A PMI class is a PMI problem with unknowns of three kinds: problem parameters, residual parameters, and problem variables. A PMI instance is then a PMI class where numerical values have been substituted for the problem and residual parameters. Specifically, PMI classes addressed by GpoSolver are such that two different PMI instances of the same class are identical up the coefficients of and , respectively.
Conceptually, using GpoSolver is divided into two phases. The first phase is the problem modeling phase and it is implemented as a Matlab toolbox. The second phase is the problem solving phase and it is implemented as a C++ template library. The following figure depicts the GpoSolver’s workflow as well as the relationship between the two phases:
First, a PMI class is defined as a Matlab data structure. Next, based on this data structure, a C++ class describing an LMI relaxation of a given order is generated using gpogenerator function of the toolbox. In the problem solving phase, the generated C++ class, together with the GpoSolver C++ template library, is included into the user’s code. Finally, by simply changing the values of the problem and residual parameters, different instances of the original PMI class can be solved. This two-phase approach has the advantage of convenient problem modeling in Matlab, while the final executable can be deployed into a Matlab-free environment where different instances of the original PMI class can be repeatedly solved.
The Matlab toolbox will run on every Matlab supported platform provided that Symbolic Math Toolbox with MuPAD engine is available. The C++ template library is also platform agnostic, however, there are several prerequisites as well. It is based on C++ linear algebra library Eigen [1] and it needs to be linked against at least one of these SDP solvers: CSDP [3], SDPA [7], or MOSEK [2]. Both parts of GpoSolver were tested on Ubuntu Linux 64-bit and Windows 7 64-bit. GpoSolver is distributed as an archive file containing the Matlab toolbox, the C++ template library, and the third party DLL libraries facilitating the usage of GpoSolver under Windows 64-bit.

# PMI class parametrization

Mathematically, PMI classes lead to problems that are equivalent to Problem 2↑. However, not every aspect of Problem 2↑ can be parametrized in GpoSolver at the moment, e.g., the number of constraints must be fixed. The precise formulation of PMI classes solvable by GpoSolver is stated by the following problem:
Problem 3 (GpoSolver PMI class parametrization)
This parametrization allows for two sets of parameters , , and for a summation-based cost function. We call the parameters problem parameters and they can appear in the cost function as well as in the constraints. The values of these parameters are to be specified during the problem solving phase, however, the number of problem parameters needs to be specified in the modeling phase. The second set of parameters , we call residual parameters. Again, the number of parameters must be specified in the modeling phase. The values of the residual parameters as well as the number of the parameter blocks are instance specific. The instance-specific parameter together with the summation-based cost function allow for PMI classes based on minimization of residual based cost functions. In the modeling phase, only the form of must be specified. If the problem contains no residual parameters, then by default. To sum it up, the values of , , , and need to be specified in the modeling phase. The parameter values as well as the number of residual blocks are instance dependent and are to be specified in the solving phase.
Another constraint on a PMI class is the requirement that both and must be polynomials in the problem variables as well as in the parameters This means that the parameters can appear as monomials only. If the problem at hand calls for more complicated functions such as , , , etc., the user must substitute these using new variables in the modeling phase manually. In the solving phase, one must also take care of correctly “pre-computing” the values of these new variables. The reason behind this constraint is the fact that polynomial functions are easy to translate into C++ code and are defined for all real values.

# References

[1] Eigen: C++ template library for linear algebra.

[2] MOSEK: large scale optimization software.

[3] Brian Borchers. CSDP, A library for semidefinite programming. Optimization methods and Software, 11(1-4):613—623, 1999.

[4] D.A. Cox, J.B. Little, D. O'Shea. Using Algebraic Geometry. Springer, 2005. URL http://books.google.com/books?id=1blxizOS9N0C.

[5] Didier Henrion, Jean-Bernard Lasserre. Convergent relaxations of polynomial matrix inequalities and static output feedback. Automatic Control, IEEE Transactions on, 51(2):192—202, 2006.

[6] Jean-Bernard Lasserre. Global Optimization with Polynomials and the Problem of Moments. SIAM Journal on Optimization, 11:796—817, 2001.

[7] Katsuki Fujisawa Makoto Yamashita. A high-performance software package for semidefinite programs: SDPA 7. 2010.