Ejercicio del libro de texto: verificar las condiciones KKT para un programa cuadrático

Question

Estoy luchando con el Ejercicio 7.3 en Optimization Methods in Finance de Cornuejols & Tutuncu (1ra edición, 2006) [PDF]:

$$\begin{array}{ll} \text{minimizar} & f(x) := x_1x_2 + x_1^2 + \frac{3}{2}x_2^2 + 2x_3^2 + 2x_1 + x_2 + 3x_3\\ \text{sujeto a} & g_1(x) := x_1 + x_2 + x_3 = 1\\ & g_2(x) := x_1 - x_2 = 0\\ & h_i(x) := x_i \geq 0 \text{ para } 1 \leq i \leq 3\end{array}$$

El ejercicio pide demostrar que $$ x^\star = (.5, .5, 0)$$ es una solución óptima mediante la verificación de las condiciones KKT.

Sea $y_1, y_2$ y $s_1, s_2, s_3$ los multiplicadores correspondientes a $g_i$ y $h_i$. Tenemos que $s_1 = s_2 = 0$ porque $s_ix_i = 0$. Por lo tanto, la primera condición (necesaria) a verificar es que existan $s_3 \geq 0, y_1, y_2$ tal que

$$\nabla f = y_1\nabla g_1 + y_2\nabla g_2 + s_3\nabla h_3,$$

donde todos los gradientes se evalúan en $x^\ast$.

Esto lleva al sistema lineal (a menos que haya cometido un error...):

$$ \left(\begin{matrix} 2x_1 + x_2 + 2\\ x_1 + 3x_2+1\\ 4x_3 + 3\\ \end{matrix}\right) = \left(\begin{matrix} 7/2\\ 3\\ 3\\ \end{matrix}\right) = \left( \begin{matrix} 1 & 1 & 0 \\ 1 & -1 & 0 \\ 1 & 0 & 1 \end{matrix}\right) \left( \begin{matrix} y_1\\ y_2\\ s_3 \end{matrix}\right), $$

pero esto tiene una solución $s_3 < 0$. Por favor ayúdame a ver dónde me equivoqué.

Answer 1

Dado que no puedes resolver las condiciones KKT para $x^*=(0.5, 0.5, 0)$, esa solución no es óptima. Hay un error en la asignación.

Dado que $Q$ es definida positiva, hay solo una solución óptima. Con software de optimización (código Python agregado abajo) encontré la solución aproximada como $\hat{x}\approx(0.47826, 0.47826, 0.04348)$. Observa que $\hat{x}$ es una solución factible porque satisface las restricciones. Con esta solución aproximada puedes fácilmente demostrar que la solución $x^*$ dada en el libro es subóptima, ya que su valor objetivo es 2.375, mientras que $\hat{x}$ tiene un valor objetivo de 2.3695..., que es mejor.

import numpy
import cvxopt
Q = 2*matrix([ [1, .5, 0.0], [.5, 1.5, 0.0], [0.0, 0.0, 2.0] ])
p = matrix([2.0, 1.0, 3.0])
G = matrix([[-1.0,0.0,0.0],[0.0,-1.0,0.0],[0.0,0.0,-1.0]])
h = matrix([0.0,0.0,0.0])
A = matrix([[1.0, 1.0], [1.0, -1.0], [1.0, 0.0]])
b = matrix([1.0, 0.0])
sol=solvers.qp(Q, p, G, h, A, b)