Skip to main content
3 of 3
edited body
JohnA
  • 710
  • 4
  • 17

Constrained optimization of sum of squares polynomials

Consider the problem $$ \min p(x) \text{ subject to } g_j(x)\le 0 \quad p,g_j\in\text{SOS}, \qquad (*) $$

i.e. $p,g_j$ ($j=1,\ldots,m$) are sum of squares (SOS) polynomials. Can this problem be solved efficiently?

The paper [1] shows that unconstrained minimization of SOS polynomials can be reduced to a convex program. Surprisingly, the paper goes onto consider general (non-SOS) constrained polynomial optimization to derive the Lasserre hierarchy, but never explicitly discusses the special case $(*)$ above.

[1] Lasserre, Jean B., Global optimization with polynomials and the problem of moments, SIAM J. Optim. 11, No. 3, 796-817 (2001). ZBL1010.90061.

JohnA
  • 710
  • 4
  • 17