Convex optimization for solving globally nonconvex polynomial optimization problems

Didier Henrion

Department of Control Engineering, FEL CVUT, Prague, Czech Republic (part-time)
and
LAAS-CNRS, Toulouse, France

We survey how recent results from real algebraic geometry (representation theorems for positive polynomials by Putinar or Polya) and the theory of moments (flat extensions of moment matrices by Curto and Fialkow) can be used to address optimization problems with multivariate polynomial objective function and constraints. Even though these optimization problems are typically nonconvex and NP-hard, they can often be solved in floating point arithmetic at reasonable numerical accuracy and computational cost. The main ingredient is convex semidefinite programming, a generalization of linear programming in the cone of symmetric matrices with non-negative eigenvalues. Following this approach, nonconvex polynomial optimization problems can be solved using convex optimization, without resorting to branch-and-bound or similar expensive combinatorial techniques. We mention several applications of this approach in control theory, combinatorial optimization and computer vision. If time permits we would like to mention numerical issues regarding compactness assumptions, problem conditioning, sparsity, structure, use of scaling and orthogonal polynomial bases in this context.