La solución primaria y dual no es la misma

Aug 21 2020

Supongamos que tenemos el siguiente problema de optimización convexa: $$\ \min_x\psi(x) \ \ s.t. \ \phi(x) \leq 0 $$ Podemos escribir el problema primario como: $$\ \min_x\max_{\lambda\geq 0} \psi(x) + \lambda\phi(x) $$ y el problema dual como: $$\ \max_{\lambda\geq 0}\min_x \psi(x) + \lambda\phi(x) $$ Digamos $(\bar x, \bar \lambda)$ es la solución al problema primario y $(x^*, \lambda^*)$solución al problema dual. Asumiendo$\psi$ y $\phi$ no son estrictamente convexas, la solución primaria no necesita ser la misma que la solución dual, es decir $x^* \neq \bar x$ y $\lambda^* \neq \bar\lambda$. Sin embargo, la fuerte dualidad nos dice que,$\mathcal L (\bar x, \bar \lambda) = \mathcal L(x^*, \lambda^*)$. ¿Puede señalarme algún ejemplo interesante para el mismo o dar una intuición? Entiendo que el problema no tiene un punto de silla único y, por lo tanto, este problema. Todavía tengo dudas conceptuales,$(x^*, \lambda^*)$ ¿No satisface las condiciones KKT para el problema de optimización restringida original?

Editar: Estoy confundido porque a menudo la gente habla de métodos para obtener una solución primaria de la solución dual. La página 56 del artículo (Aplicación de la línea del teorema de Minimax) indica que la solución aproximada está en el casco convexo de iteraciones duales. Bueno, mi pregunta es ¿por qué no tomar la última iteración de dual?

Respuestas

1 LinAlg Aug 28 2020 at 23:28

Las condiciones KKT del problema primario y dual son idénticas si se alcanza la solución primaria. El problema principal es:$$\ \min_x\max_{\lambda\geq 0} \psi(x) + \lambda\phi(x) \qquad(P) $$ Sus condiciones KKT son $\phi(x) \leq 0$ (viabilidad primaria), $\lambda\geq 0$ (viabilidad dual) $\psi'(x) + \lambda \phi'(x)=0$ (estacionariedad) y $\lambda \phi(x)=0$ (complementariedad).

El doble problema es: $$\ \max_{\lambda\geq 0}\min_x \psi(x) + \lambda\phi(x) \qquad(D) $$ que es equivalente a: $$\ \max_{\lambda} \min_{y\geq 0, x} \psi(x) + \lambda\phi(x) + \lambda y \qquad(D) $$ La condición de estacionariedad es $\phi(x) + y = 0$ (es decir, $\phi(x)\leq 0$). Las condiciones de viabilidad primarias son$\lambda \geq 0$ (como de lo contrario el valor de $\min_{y\geq 0}$ es $-\infty$) y $\min_x \psi(x) + \lambda \phi(x)>-\infty$. Para lo último, si se alcanza el mínimo (es decir, el problema primario se puede resolver), tiene$\psi'(x) + \lambda \phi'(x)=0$. La condición de complementariedad es$\lambda y = 0$ (lo que implica $\lambda \phi(x)=0$ a través de la condición de estacionariedad).