Por favor, explique la intuición detrás de la doble problema de optimización.

Question

He estudiado convexo optimización de bastante cuidado, pero no siento que todavía tengo "grokked" el problema doble. Aquí hay algunas preguntas que me gustaría entender más profundamente/claramente/simplemente:

1) ¿Cómo podría alguien pensar en el doble problema? Lo que el proceso de pensamiento que podría llevar a alguien a considerar el doble problema y reconocer que es valioso o interesante?

2) En el caso de un problema de optimización convexa, hay ninguna razón obvia para esperar que la fuerte dualidad (en general)?

3) a veces ocurre que el dual del problema dual es el primal problema. Sin embargo, esto parece como una completa sorpresa para mí. ¿Hay alguna razón intuitiva para esperar que esto suceda?

4) ¿el uso de la palabra "dual" o "dualidad" en la optimización tiene nada que ver con el doble de espacio en álgebra lineal? O son sólo diferentes conceptos que van por el mismo nombre. ¿Qué acerca de la utilización de la palabra "dual", en geometría proyectiva-hay una conexión ahí?

5) Se puede definir el problema doble y demostrar teoremas acerca de la fuerte dualidad, sin mencionar jamás la conjugada de Fenchel. Por ejemplo, Boyd y Vandenberghe probar una fuerte dualidad teorema sin mencionar la conjugada de Fenchel en su prueba. Y, sin embargo, a menudo la gente habla como si la conjugada de Fenchel es de alguna manera la "esencia" de la dualidad, y hacer que suene como si toda la teoría de la dualidad se basa en la conjugada de Fenchel. ¿Por qué es la conjugada de Fenchel considera que tiene tal importancia fundamental?

Nota: ahora voy a describir mi nivel actual de comprensión de la intuición detrás de la doble problema. Por favor, dígame si usted cree que me puede estar faltando cualquiera de conocimientos básicos.

He leído las excelentes notas acerca de la optimización convexa por Guilherme Freitas, y en particular la sección sobre "la pena de la intuición". Cuando estamos tratando de resolver \begin{align*} \text{minimize} &\quad f(x) \\ \text{such that} & \quad h(x) \leq 0 \end{align*} uno podría tratar de eliminar las restricciones mediante la introducción de una pena cuando las restricciones son violados. Esto nos da el nuevo problema sin restricciones \begin{equation} \text{minimize} \quad f(x) + \langle \lambda ,h(x) \rangle \end{equation} donde $\lambda \geq 0$. No es difícil ver que para un determinado $\lambda \geq 0$, el valor óptimo de este problema sin restricciones es menor o igual que el valor óptimo para la limitación de problema. Esto nos da un nuevo problema: encontrar$\lambda$, de modo que el valor óptimo para el problema sin restricciones es tan grande como sea posible. Esta es una manera de imaginar cómo alguien podría haber pensado en el problema dual. Es esta la mejor intuición de donde el doble problema viene de?

Otro punto de vista: las condiciones KKT, a partir de lo que Freitas llama a la "intuición geométrica". Entonces, si supiéramos el valor de los multiplicadores $\lambda$, sería (a menudo) mucho más fácil encontrar a $x$. Así, un nuevo problema es encontrar a $\lambda$. Y si podemos de alguna manera reconocer que $\lambda$ es un maximizer para el problema dual, entonces esto sugiere que podríamos tratar de resolver el problema doble.

Por favor, explicar o dar referencias a cualquier intuición que crees que podría encontrar interesante, aunque no directamente relacionado con lo que te pedí.

Answer 1

Aquí es lo que realmente está pasando con el doble problema. (Este es mi intento de responder a mi propia pregunta, más de un año después de que originalmente preguntando).

(Una presentación muy interesante de este material es dado en Ekeland y Temam. Estas ideas también están en Rockafellar.)

Deje $V$ ser finito dimensionales normativa espacio vectorial sobre $\mathbb R$. (Trabajando en un producto interior espacio o simplemente en $\mathbb R^N$ riesgos de ocultar el papel fundamental que el espacio dual juega en la dualidad de optimización convexa.)

La idea básica detrás de la dualidad en el análisis convexo es pensar en un conjunto convexo en términos de su apoyo hyperplanes. (Cerrado conjunto convexo $\Omega$ puede ser "recuperado" de su apoyo hyperplanes tomando la intersección de todos los cerrados de la mitad de los espacios que contengan $\Omega$. El conjunto de todos los hyperplanes a $\Omega$ es una especie de "doble representación" de $\Omega$.)

Para una función convexa $f$ (cuyo epígrafe es un conjunto convexo), esta estrategia conduce nos hace pensar sobre $f$ en términos de afín a las funciones de $\langle m^*, x \rangle - \alpha$ que son majorized por $f$. (Aquí se $m^* \in V^*$ y estamos utilizando la notación $\langle m^*, x \rangle = m^*(x)$.)

Para una pendiente dada $m^* \in V^*$, sólo necesitamos considerar el "mejor" elección de $\alpha$ - de la otra afín minorants con pendiente $m^*$ puede ser ignorada. \begin{align*} & f(x) \geq \langle m^*,x \rangle - \alpha \quad \forall x \in V \\ \iff & \alpha \geq \langle m^*, x \rangle - f(x) \quad \forall x \in V \\ \iff & \alpha \geq \sup_{x \in V} \quad \langle m^*, x \rangle - f(x) \end{align*} así que la mejor opción de $\alpha$ es \begin{equation} f^*(m^*) = \sup_{x \in V} \quad \langle m^*, x \rangle - f(x). \end{equation} Si este supremum es finito, entonces $\langle m^*,x \rangle - f^*(m^*)$ es la mejor afín minorant de $f$ con pendiente $m^*$. Si $f^*(m^*) = \infty$, entonces no hay afín minorant de $f$ con pendiente $m^*$.

La función de $f^*$ es llamado el "conjugado" de $f$. La definición y hechos básicos acerca de la $f^*$ son todos muy intuitiva. Por ejemplo, si $f$ es un buen cerrado convexo de la función, a continuación, $f$ puede ser recuperado de $f^*$, debido a que cualquier conjunto convexo cerrado (en este caso el epígrafe de $f$) es la intersección de todos los cerrados de la mitad de los espacios que los contienen. (Yo aún creo que el hecho de que la "inversión de la fórmula" $f = f^{**}$ es tan simple, es una sorprendente y matemáticamente hermoso hecho, pero no es difícil derivar o probar con esta intuición.)

Debido a $f^*$ está definido en el espacio dual, podemos ver ya el papel fundamental desempeñado por el doble de espacio en la dualidad de optimización convexa.

Dado un problema de optimización, no podemos obtener un doble problema hasta que especifique cómo se va a perturbar el problema de optimización. Esta es la razón por la equivalente formulaciones de un problema de optimización puede causar diferentes problemas duales. Por la reformulación que de hecho hemos especificado una manera diferente a perturbar.

Como es típico en las matemáticas, las ideas quedan claras cuando trabajamos en un nivel de generalidad. Supongamos que nuestro problema de optimización es \begin{equation*} \operatorname*{minimize}_{x} \quad \phi(x,0). \end{ecuación*} Aquí $\phi:X \times Y \to \bar{\mathbb R}$ es convexa. Estándar convexo problemas de optimización puede ser escrita en esta forma con una elección adecuada de $\phi$. El perturbado problemas \begin{equation*} \operatorname*{minimize}_{x} \quad \phi(x,y) \end{ecuación*} para valores distintos de cero de a $y \in Y$.

Deje $h(y) = \inf_x \phi(x,y)$. Nuestro problema de optimización es simplemente para evaluar $h(0)$.

A partir de nuestro conocimiento de conjugar las funciones, sabemos que \begin{equation*} h(0) \geq h^{**}(0) \end{ecuación*} y que normalmente tenemos la igualdad. Por ejemplo, si $h$ es subdifferentiable en $0$ (lo cual es típico para una función convexa), a continuación,$h(0) = h^{**}(0)$.

El doble problema es simplemente para evaluar $h^{**}(0)$.

En otras palabras, el doble problema es: \begin{equation*} \operatorname*{maximize}_{y^* \in Y^*} \quad - h^*(y^*). \end{ecuación*} Vemos de nuevo el papel fundamental que el espacio dual juega aquí.

Es esclarecedor para expresar la doble problema en términos de $\phi$. Es fácil mostrar que el problema es doble \begin{equation*} \operatorname*{maximize}_{y^* \in Y^*} \quad - \phi^*(0,y^*). \end{ecuación*}

Así que el problema primal es \begin{equation*} \operatorname*{minimize}_{x \in X} \quad \phi(x,0) \end{ecuación*} y el problema dual (ligeramente reexpresado) es \begin{equation*} \operatorname*{minimize}_{y^* \in Y^*} \quad \phi^*(0,y^*). \end{ecuación*} La similitud entre estos dos problemas es matemáticamente hermosa, y podemos ver que si nos perturban el doble problema de la manera obvia, entonces el dual del problema dual será el problema primal (asumiendo $\phi = \phi^{**}$). El natural de isomorfismo entre el $V$ $V^{**}$ es de fundamental importancia aquí.

Los hechos clave sobre el doble problema-fuerte dualidad, las condiciones de optimalidad, y la sensibilidad a la interpretación de la óptima dual de las variables-todos se convierten en intuitivamente evidente, e incluso "obvio" desde este punto de vista.

Un problema de optimización en el formulario \begin{align*} \operatorname*{minimize}_x & \quad f(x) \\ \text{subject to} & \quad g(x) \leq 0, \end{align*} puede ser perturbado de la siguiente manera: \begin{align*} \operatorname*{minimize}_x & \quad f(x) \\ \text{subject to} & \quad g(x) + y \leq 0. \end{align*}

Este perturbado problema tiene la forma arriba indicada con \begin{equation*} \phi(x,y) = \begin{cases} f(x) \quad \text{if } g(x) + y \leq 0 \\ \infty \quad \text{otherwise}. \end{casos} \end{ecuación*} Para encontrar el doble problema, necesitamos evaluar $-\phi^*(0,y^*)$, que es relativamente sencillo cálculo. \begin{align*} -\phi^*(0,y^*) &= -\sup_{g(x) + y \leq 0} \quad \langle y^*,y \rangle - f(x) \\ &= -\sup_{\substack{ x \\ q \geq 0 }} \quad \langle y^*, -g(x) - q \rangle - f(x) \\ &= \inf_{\substack{ x \\ q \geq 0 }} \quad f(x) + \langle y^*, g(x) \rangle + \langle y^*, q \rangle. \end{align*} Podemos minimizar el primero con respecto a $q$, y nos pondremos $-\infty$ si $\langle y^*, q \rangle \geq 0$ todos los $q \geq 0$. En otras palabras, nos pondremos $-\infty$ si $y^* \geq 0$.

La función dual se \begin{equation*} -\phi^*(0,y^*) = \begin{cases} \inf_x \quad f(x) + \langle y^*, g(x) \rangle \quad \text{if } y^* \geq 0 \\ -\infty \quad \text{otherwise}. \end{casos} \end{ecuación*}

Este es el resultado esperado.

Answer 2

Voy a tomar una grieta en un par de estas preguntas (algunas de ellas son difíciles y requieren más de pensamiento).

1) he Aquí una bonita interpretación económica de la dualidad (siendo un poco "rápido y suelto" con los detalles). Vamos a decir $x$ representa el diseño de un widget, y $f(x)$ es el costo que se incurren en la producción. $x$ debe satisfacer "las restricciones de diseño" dado por $h(x)\leq 0$ (supongamos por simplicidad que sólo tenemos 1 función de limitación). Por curiosidad, decide probar la agricultura de la producción: otra empresa se compromete a producir su cosita $x$ y "cargo"$f(x)$. Su objetivo final es maximizar las ganancias, pero no pueden cobrar más de lo que podría pasar haciendo lo mismo. Por lo tanto, dado un fijo $\lambda$, que necesitan para encontrar el diseño de $x$ que minimiza $f(x)+\lambda h(x)$. Si no, usted será capaz de encontrar un diseño posible $y$ que tiene un menor costo,$f(y)<f(x)$, y por lo tanto usted hacer que el widget de ti mismo. Ahora que esta empresa puede hacer, al menos, tan bueno como usted, van a establecer acerca de la maximización de sus beneficios mediante la variación de $\lambda$ (quizás $\lambda$ corresponde a un proceso diferente o algo).

Esta interpretación es similar a la de Boyd y Vandenberghe, 5.4.4. También me parece 'teoría de juegos' interpretaciones útiles - el problema primal es su estrategia, mientras que el dual corresponde a una estrategia del oponente.

2) no tengo una respuesta intuitiva para esta otra que decir que la fuerte dualidad es equivalente a la existencia de un punto de silla de la Lagrangiana.

3) Para los problemas convexos esto tiene sentido porque la aplicación de la convexo conjugado (Fenchel transformar) dos veces devuelve el 'convexification' de la original de la función objetivo, que es la misma que la función original en la mayoría de los 'bonito' situaciones.

4) Sí, pero definitivamente hay que tener cuidado. El dual de un espacio vectorial se define formalmente como el espacio de todos lineal continua y funcionales en el espacio, y este concepto de vida 100% independientemente de la teoría de la optimización. Sin embargo, usted está en lo correcto notar que el dual de un espacio vectorial hace surgir en la declaración del dual de un problema de optimización. Me explico: definir $X=\mathbb{R}^n$ $Y=\mathbb{R}^m$ y considerar el problema:

$$ \text{minimizar}\quad f(x)\\ \text{tales que} \quad h(x)\leq 0\\ x\in X,\;f:X\rightarrow \mathbb{R},\\ h:X\rightarrow Y. $$ A continuación, este problema tiene las siguientes doble:

$$ \max_\lambda\quad \inf_{x\in X} \{f(x)+\langle \lambda,h(x)\rangle\}\\ \text{tales que}\quad \lambda_i\geq 0,~~\forall i: 0\leq i\leq m $$ Now, "formally", $\lambda$ is an element of the dual space of $S$, since we're considering an inner product of the form $\langle\lambda, y\rangle$ where $s\in S$, and hence can think of this as a continuous linear functional on $S$. But here $S$ is finite dimensional, so (by the Riesz representation theorem) $Y^*$ is actually isomorphic to $S$, so the distinction isn't really necessary and you haven't gained anything by thinking of $\lambda$ as being an element of the dual space. It's possible that in infinite dimensional problems where $Y^*$ is not isomorphic to $$ Y se puede conseguir algo de esto, pero no puedo pensar en un buen ejemplo.

A mi conocimiento, no existe ninguna conexión entre la dualidad en la geometría proyectiva y la dualidad en la optimización. La dualidad en la geometría proyectiva es más una declaración acerca de la bijection entre puntos y rayas que define el espacio proyectivo. La "dualidad" en matemáticas, en realidad, significa que tiene 2 maneras de pensar acerca de un problema - es tan trillado como las palabras como "fundamental" y "canónica". Otro ejemplo clásico de la dualidad proviene de la dinámica de fluidos y de la PDE - "Euler" coordenadas vs 'de Lagrange' coordenadas.

5) Para problemas convexos, yo estaría de acuerdo en que la convexo conjugado es clave, aunque en general no estoy seguro de que ayuda mucho con el 'general' de la idea de la dualidad, ya que (a) no todos los problemas interesantes son convexas y (b) la convexo conjugado es legendariamente duro para ganar la intuición. Históricamente este "fundamental importancia" de la convexo conjugado podría atribuirse a la física, de donde resulta que un montón de interesantes de la física de los sistemas tienen un convexo 'de Lagrange", que describe su energía total. Las ecuaciones de movimiento pueden entonces ser expresada esencialmente como un convexo problema de minimización con respecto a este Lagrangiano. El convexo conjugada de la función, entonces resulta, es lo que se llama el 'Hamilton', que lleva a una totalmente diferente (uno podría decir 'dual') la formulación de las ecuaciones de la física. Así pues, tenemos de nuevo dos maneras de abordar el mismo problema!

Espero que esto fue algo de utilidad para usted.

Answer 3

Considere el problema $$ \begin{aligned} \mbox{min} & f(x) \\ \mbox{subject to} & x\le a\\ \end{aligned} $$ se ilustra a continuación y donde $f$ es convexo:

Las características esenciales que hay en este problema a pesar de ser el más básico, el problema de la desigualdad. Ahora, considere el óptimo dada como una función de la $a$. Por lo $f_+(a)=\inf_{x\le a}f(a)$. Su gráfica se parece a esto:

Es básicamente igual que el original $f$, salvo que sólo tenemos el descenso de las partes y ninguno de los ascendientes partes.

Vamos a construir $f_+$ por un poco de la rotonda de la forma, no considerando la misma función, pero su epígrafe, el conjunto de puntos por encima de la gráfica. Aquí está el epígrafe de la original $f$:

Aviso que he dibujado un montón de líneas sólo tocar el epígrafe, es decir,. su subtangents. En general, cualquier convexidad puede ser expresado como la intersección de la mitad de los aviones. Los subtangents indicar un puñado de los límites de la mitad de los aviones. Podemos construir los subtangents considerando las líneas de $y=\lambda x$ y, a continuación, empujando las líneas hacia arriba o hacia abajo de modo que cada uno alto como sea posible sin cruzar $f$. Podemos averiguar cuánto empujando necesitamos por la solución de la optimización: $$ \begin{aligned} \mbox{maximise} & \lambda x-f(x) \end{aligned} $$ y que nosotros llamamos el valor óptimo $f^\ast(\lambda)$. $f^\ast$ es también conocida como la transformación de Legendre o Fenchel dual. Básicamente nos dice que la mitad de los aviones de definir nuestro epígrafe. Curiosamente, la reconstrucción de la función de $f$ $f^\ast$ requiere exactamente la misma expresión. Así que el Fenchel doble también tiene una colección de la mitad de los aviones y le da la espalda a la función original.

Así que ahora queremos construir el epígrafe de $f_+$. Sólo queremos que el descenso de las piezas de $f$. Es fácil construir el epígrafe, tomamos la intersección de sólo la mitad de los aviones de cuyos límites están disminuyendo. Aquí una foto:

Así que aquí es un proceso de construcción de $f_+$: tomamos el Fenchel doble de $f$, nos tiramos a la "mitad" donde $\lambda\le0$, y ahora toma el inverso de Fenchel dual (que es en realidad el Fenchel dual).

Ahora vamos a construir el doble para nuestro original optimización del problema como se describe en numerosos libros de texto. Formamos el Lagrangiano $$L(a,x,\lambda)=f(x)+\lambda (x-a)$$ Tenemos entonces la función $$g(a,\lambda)=\min_x L(a,x,\lambda)$$ Esto es, básicamente, (modulo de un signo) el Fenchel doble de $f$ con un $-\lambda a$ plazo.

El doble problema, como en los libros de texto, es $$ \begin{aligned} \mbox{maximise} & g(a,\lambda)\\ \mbox{such that} & \lambda\ge0\\ \end{aligned} $$ Recordar que $-\lambda a$ plazo, que es casi el inverso Fenchel dual excepto hemos maximizado sobre "la mitad" de la $\lambda$s, aquellos para los que $\lambda\ge0$. Cuando calculamos el óptimo del problema doble llegamos $h(x)=\max_x g(a,x)$. Si el problema es convexo, hemos calculado $f_+$ por otro camino.

Así que esto le da a lo que yo creo que es una clara imagen de lo que el doble problema. La formación de la doble problema es (modulo un desplazamiento vertical) convertir el problema original en la búsqueda de la subtangents. Resolver el doble problema es la conversión que volver a una función de nuevo, pero el uso de sólo el que se inclina hacia abajo las líneas.

Espero que esto también responde a algunas de las otras preguntas.

Por cierto, esto está conectado con duales en álgebra lineal. Nos suele definir un espacio medio el uso de $h(x)\le\mbox{constant}$ donde $h$ es lineal en $x$. Por lo $h$ es un ejemplo de lo que se entiende por un vector dual en álgebra lineal. Cuando trabajamos desde el doble punto de vista que estamos buscando a convexa de los objetos desde el punto de vista de los dos vectores de la definición de la hyperplanes que la tocan.

Mientras estoy aquí, puedo puedo agregar que esto es similar a la transformada de Hilbert en el procesamiento de la señal. La transformada de Hilbert implica tirar "la mitad" de la transformada de Fourier de forma análoga a tirar "la mitad" de la transformación de Legendre. Hay una profunda conexión.

Answer 4

Para #4 y #5, ver "El concepto de la dualidad en el análisis convexo, y la caracterización de la transformación de Legendre" por Artstein-Avidan y Milman.