# Documentation

`gposolver-`, located in the directory

*VERSION*.pdf`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

*i.e.*, [4]. The polynomial optimization problem (POP) can be stated as follows:

*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↑.

*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.

*i.e.*, there is no need for additional standalone executable.

# Workflow

*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.

*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:

`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.

# PMI class parametrization

*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 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.

# References

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

[2] MOSEK: large scale optimization software.

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

[4]
. *Using
Algebraic Geometry*. Springer, 2005. URL
http://books.google.com/books?id=1blxizOS9N0C.

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

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

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