No entiendo cómo funciona la relajación SOS (Suma de Cuadrados) para la optimización polinómica en algunos casos.
Por ejemplo, consideremos el problema de optimización polinómica:
\begin{equation} \begin{array}{c} minimize \hspace{1cm} p(\mathbf{x}) \\ s.t. \hspace{1cm} \mathbf{x} \in K, \\ \end{array} \end{equation} donde $K$ es un conjunto semialgebraico, y $\mathbf{x} \in \mathbb{R}^n.$
Este problema equivale a \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}
Utilizando la relajación SOS, el problema de optimización puede escribirse como
\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} donde $\Sigma$ es el conjunto de polinomios SOS.
Mi pregunta es: si $p(\mathbf{x}) -\rho $ no puede escribirse como un polinomio SOS, ¿sigue funcionando la relajación para resolver dicho problema? Si es así, ¿cómo funciona un algoritmo específico (el método del punto interior, por ejemplo) en ese caso?
Gracias de antemano.
