Note: This content is accessible to all versions of every browser. However, this browser does not seem to support current Web standards, preventing the display of our site's design details.


Enriching Sum of Squares Hierarchies with AM/GM Polynomials


O. Karaca

Master Thesis, SS16 (10517)

Polynomial optimization is an active field of research with broad range of applications spanning from the control of nonlinear systems to approximate dynamic programming. Problem of finding the global minimum of a polynomial remains an NP-hard problem but it can be solved by a convergent hierarchy of convex relaxations. Towards that, sum of squares is a well-established method which provides theoretical guarantees for the convergence. However, one may need to solve higher levels of the hierarchy to obtain the optimum, and this would result in semidefinite programs that are larger than commercial solvers can handle. Appealingly, a recent development by Chandrasekaran and Shah provides with an alternative convex certificate: "sum of AM/GM polynomials". In this project, we extend sum of squares certificate with AM/GM polynomials, and derive a combined hierarchy of convex relaxations whose optima converge to the optimum of polynomial optimization problems. Further, we describe pre-processing methodologies to reduce the size of the optimization problem. Finally, we introduce a YALMIP toolbox to solve primal and dual AM/GM polynomial hierarchies, and also to solve the combined hierarchy.

In this project, we developed "The REPOP Toolbox: Tackling Polynomial Optimization Using Relative Entropy Relaxations". This toolbox is publicly available at:

Supervisors: Paul Beuchat, Gerogios Darivianakis, Angelos Georghiou, John Lygeros

Further Information

Type of Publication:

(12)Diploma/Master Thesis

File Download:

Request a copy of this publication.
(Uses JavaScript)
% Autogenerated BibTeX entry
@PhdThesis { Xxx:2016:IFA_5489
Permanent link