Interpretación geométrica de la dualidad y condición de Slater

Question

Estoy tratando de estudiar sobre problemas de optimización, dualidad de Lagrange y temas relacionados. Me encontré con una presentación en la red, que afirma mostrar la interpretación geométrica de la dualidad y la condición de Slater para un problema simple con solo una restricción:

$$\begin{equation*} \begin{aligned} & \underset{x}{\text{minimizar}} & & f_0(x) \\ & \text{sujeto a} & & f_1(x) \leq 0. \end{aligned} \end{equation*}$$

Aquí está la siguiente diapositiva:

Ahora, entiendo cómo se representa $p^*$: El problema primal tiene una restricción $f_1(x) \leq 0$ y solo consideramos valores negativos de $u$ por lo tanto. Se elige el punto $(u,t)$ con el valor mínimo de $t$ donde $u \leq 0.

Pero no entiendo en absoluto cómo debería interpretar la función dual $g(\lambda) para empezar. $g(\lambda)$ se representa como una línea (hiperplano). Pero según la definición de $g(\lambda)$ debe ser un valor escalar. El problema dual es $g(\lambda) = \inf_x(f_0(x) + \lambda f_1(x))$ donde $\lambda \geq 0$. Entonces, para un $\lambda \geq 0$ dado, debemos ir y buscar un punto $(u,t)$ en $G$ que minimice $g(\lambda)$. ¿Cómo se conecta esto con un hiperplano para empezar? Estamos en el espacio $(u,t)$, que no tiene ninguna parametrización de $\lambda en él. Necesito desesperadamente algunas aclaraciones aquí.

Answer 1

Una idea clave en el análisis convexo es pensar en un conjunto (como $\mathcal G$) en términos de los semiespacios que lo contienen.

Para un $\lambda$ dado, podrías imaginar todos los hiperplanos de la forma $\lambda u + t = \text{const}$ para los cuales $\mathcal G$ está contenido en el semiespacio superior.

¿Y cuál es la elección "mejor" de la constante en el lado derecho?

La elección "mejor" es $g(\lambda)$, porque ese es el valor de la constante más grande tal que $\mathcal G$ está contenido en el semiespacio superior de $\lambda u + t = \text{const}$.

Así que puedes pensar en $\lambda u + t = g(\lambda)$ como un hiperplano para el cual $\mathcal G$ está contenido en el semiespacio superior. Además, para este valor de $\lambda$, este es el hiperplano "mejor", en el sentido de que la contención es lo más ajustada posible. Si movieras este hiperplano hacia arriba aún más, se violaría la contención.

Answer 2

Ver la conferencia 8 del curso de optimización convexa de Stanford. En el minuto 1.04 (una hora y 4 minutos desde el inicio) Stephen Boyd comienza a explicar la interpretación geométrica.

http://www.youtube.com/watch?v=FJVmflArCXc

También tienes su libro (gratis en su sitio web) con más detalles formales.

Answer 3

Como dijiste $g(\lambda)$ para un $\lambda$ dado es un escalar. Supongamos que $\lambda = 3$ y $g(\lambda) = 5$. Eso define la línea $3u+t=5$. El dual es $5$ (no $3u+t=5$). La intersección de la línea $3u+t=5$ es $5$ que es $g(\lambda)$. Obtienes la función dual al variar los $\lambda$ (deben ser no negativos). Por lo tanto, la función dual define una familia de líneas; encuentra la intersección más grande de todas. Eso es $d^*$ que satisface $d^* \leq p^*$ según la dualidad débil. En caso de que haya más de una restricción ya no tienes líneas de soporte sino hiperplanos de soporte.

En resumen, las líneas no son los duales. Un dual (que es un escalar) ayuda a definir la línea.