1
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\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
    Commented May 14, 2019 at 20:46
  • $\begingroup$ Obvious typo fixed, thanks for pointing it out. $\endgroup$
    – JohnA
    Commented May 14, 2019 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
    Commented May 14, 2019 at 20:51

1 Answer 1

Reset to default
4
$\begingroup$

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .