Programa cuadrático con restricciones de igualdad

Question

Considere el programa cuadrático (QP)

$$\begin{array}{ll} \text{minimizar} & \frac{1}{2} x^\top P x + q^\top x\\ \text{sujeto a} & A x = b\\ & x \in \mathbb{R}^n {\geq 0}\end{array}$$

donde $P \succ 0$. Sea $x^*$ el minimizador.

Sin la restricción de no negatividad $x \geq 0$, el optimizador $y^*$ es la solución del sistema KKT

$$\left[ \begin{matrix} P & A^\top \\ A & 0\end{matrix} \right] \left( \begin{matrix} x \\ \nu\end{matrix}\right) = \left( \begin{matrix} -q \\ b \end{matrix}\right)$$

Supongamos que la inversa de $\left[ \begin{matrix} P & A^\top \\ A & 0\end{matrix} \right]$ existe y se conoce analíticamente, por lo que $y^*$ también se conoce analíticamente.

Ahora, con la restricción de no negatividad $x \geq 0$, ¿tiene $x^*$ una expresión analítica conocida (como función de $y^*$)?

Answer 1

No especialmente. Incluso en dos dimensiones, la naturaleza del problema se presenta adecuadamente. O bien $y^* \geq 0$ entonces $y^*$ es la solución restringida o no lo es. Si lo es, genial. Si no, en la nueva frontera impuesta por la restricción, la solución se puede encontrar resolviendo un problema de reducción de dimensionalidad en cada faceta. En dos dimensiones, esto significa optimizar la forma cuadrática en el eje $x$ positivo y luego nuevamente en el eje $y$ positivo. Puede descubrir que la solución está realmente en la intersección de varias facetas, es decir, en el origen en dos dimensiones.

Representar el problema combinatorio de encontrar el subconjunto de facetas que se cruzan en la solución no es analítico.