A MATLAB/C++ Toolbox for Global Polynomial Optimization

What is GpoSolver?

Global polynomial optimization can be a powerful tool when applied to engineering problems. One of the most successful methods for solving such problems is based on convex linear matrix inequality (LMI) relaxations. Software implementations of this approach can be found for example in Matlab toolboxes GloptiPoly and YALMIP. Matlab language makes it very easy when it comes to modeling polynomial problems. However, when using these toolboxes, Matlab is also required for the problem solving. GpoSolver aims at bridging this gap by providing a Matlab-based problem modeling toolbox supplemented by a problem solving backend in a form of a C++ template library. Once a problem is conveniently modeled and parametrized in Matlab, a C++ class is automatically generated by GpoSolver. This class can be easily included into an existing codebase and used to solve different instances of the problem based on the supplied parameters.
GpoSolver is developed at Center for Machine Perception, the Czech Technical University in Prague, Czech Republic. The primary developers are
  • Jan Heller, homepage, <hellej1 AT>
  • Tomas Pajda, homepage, <pajdla AT>
GpoSolver workflow. The workflow is divided into the problem modeling phase and the problem solving phase. In the next figure, the problem parameters are denoted in blue. The concrete values of these parameters are not determined until the problem solving phase. There, the parameters can be easily updated and different problem instances can be conveniently solved.figure images/workflow.png

Polynomial matrix inequalities optimization problem

Let be multivariate polynomials in , i.e., . GpoSolver is able to solve the following polynomial matrix inequalities optimization (PMI) problems:
Problem 1 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 , becomes a simple polynomial, . Also note that if the polynomial degree of and maximal polynomial degree of all entries of , , is one, the above problem becomes a Semidefinite Programming (SDP) problem.

Platforms & Dependencies

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 dependencies as well. It is based on C++ linear algebra library Eigen and it needs to be linked against one of these SDP solvers: CSDP, SDPA, or MOSEK. Both parts were tested on Ubuntu Linux and Windows 7 64-bit.


GpoSolver is free software: you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.