buena aproximación a la solución de este programa cuadráticamente obligado nonconvex

Question

Quiero encontrar un minimizador (local)$x, y$ para el siguiente problema de optimización:

PS

¿Es la programación cuadrática secuencial mi único recurso, o existen técnicas especializadas que podrían ser más eficientes? Aunque el problema es claramente no convexo, las características especiales (la restricción es cuadrática y las variables con desigualdad aparecen solo de forma lineal en las restricciones y no en absoluto en el objetivo) me dan alguna esperanza.

Answer 1

No estoy seguro de lo que tenía en mente secuencial de programación cuadrática, intenta el siguiente?

Reescribir el problema con $b=-\frac{1}{2}a$ $L(y)^T=-[M_1 y, M_2 y, \ldots ] $ y la solución para que fija y da: $$ \min_{x,y}\ \frac{1}{2} \|x-b\|^2 \qquad \mathrm{s.t.} \qquad \begin{array}{r} L(y)x = c \\ y \geq 0\end{array}. $$

$$ x^* = b + L(y)^T(L(y)de L(y)^T)^{-1}(c-L(y)b) $$

Entonces, el problema para el y solo es:

$$ \min_{y}\ \frac{1}{2} \|c-L(y)b\|_{H^{-1}}^2 \qquad \mathrm{s.t.} \qquad \begin{array}{r} H = L(y)L(y)^T \\ y \geq 0\end{array}. $$

Donde $\|z\|_{H^{-1}}^2=z^TH^{-1}z$. Por lo que inicialmente tome $H_{0}=I$, e iterar:

$$ y_{k+1} = \mbox{arg }\min_{y\ge 0 }\ \frac{1}{2} \|c-L(y)b\|_{H_{k}^{-1}}^2 $$

$$ H_{k+1} = L(y_{k+1})L(y_{k+1})^T $$

Si $c=L(y_1)b$,$x^*=b$.