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.

  • $\begingroup$ if $g_j$ is an SOS then $g_j(x)\geq 0$ for any $x$, i.e. it can be just removed from the set of constraints. $\endgroup$ – Dima Pasechnik May 14 '19 at 20:46
  • $\begingroup$ Obvious typo fixed, thanks for pointing it out. $\endgroup$ – JohnA May 14 '19 at 20:48
  • 1
    $\begingroup$ well, if $g_j$ is SOS then $g_j(x)\leq 0$ iff $g_j(x)=0$, i.e. each individual square in the SOS decomposition of $g_j$ must be 0. So it's back to Lassere's case, with equality constraints only. $\endgroup$ – Dima Pasechnik May 14 '19 at 20:51

If $g_j$ is SOS, i.e. $g_j=\sum_k h_k^2$, then $g_j(x)\leq 0$ iff $g_j(x)=0$, i.e. $h_1(x)=h_2(x)=\dots =0$. So this is a general case, although with equality constraints only.

A more interesting question would be to allow inhomogenous constraints $g_j(x)\leq b_j$, with $b_j\in\mathbb{R}$. IIRC, this would be solvable with just one step of the Lassere's hierarchy, as the whole point of it is approximating arbitrary nonnegative polynomials by SOS. (I believe the latest Lasserre's book is discussing this in Chapter 11).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.