# 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  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.

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

• 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. – Dima Pasechnik May 14 at 20:46
• Obvious typo fixed, thanks for pointing it out. – JohnA May 14 at 20:48
• 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. – Dima Pasechnik May 14 at 20:51

## 1 Answer

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).