I do not understand how SOS (Sum-Of-Squares) relaxation for polynomial optimization works in some cases.

For instance, consider the polynomial optimization problem:

\begin{equation} \begin{array}{c} minimize \hspace{1cm} p(\mathbf{x}) \\ s.t. \hspace{1cm} \mathbf{x} \in K, \\ \end{array} \end{equation} where $K$ is a semi-algebraic set, and $\mathbf{x} \in \mathbb{R}^n.$

This problem is equivalent to \begin{equation} \begin{array}{c} maximize \hspace{1cm} \rho \\ s.t. \hspace{0.5cm} p(\mathbf{x}) -\rho \geq 0 \\ \hspace{1cm} \mathbf{x} \in K. \\ \end{array} \end{equation}

By using SOS relaxation, the optimization problem can be written as

\begin{equation} \begin{array}{c} maximize \hspace{1cm} \rho \\ s.t. \hspace{0.5cm} p(\mathbf{x}) -\rho \in \Sigma \\ \hspace{1cm} \mathbf{x} \in K, \\ \end{array} \end{equation} where $\Sigma$ is the set of SOS polynomials.

My question is: if $p(\mathbf{x}) -\rho $ cannot be written as an SOS polynomial, does the relaxation still work to solve such a problem? If does, how a specific algorithm (Interior point method, for example) works in that case?

Thanks in advance!


First of all if $K$ is described by polynomial inequalities I think you better also include them in the preorder. If can not written as SOS then you will get conservative result. There might be mysterious behaviour of SDP solver that can get to the actual maximum value even it does not have SOS certificate. I remember read it somewhere. But the authors (giants in optimization actually) just say they think it is very mysterious...


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.