Organizar estos conceptos, las condiciones de KKT y problema dual

Question

Esta es una pregunta larga en el que explico mi comprensión actual de ciertas ideas. Si alguien está interesado en leer esto y quisiera proporcionar cualquier comentario/opinión que pueda ayudarme a entender estas ideas con mayor claridad, o que crees que podría encontrar interesante, se lo agradecería!

En el cálculo multivariable, para minimizar una función de $f:\mathbb R^N \to \mathbb R$ escribimos la condición de optimalidad $\nabla f(x) = 0$ y resolver para $x$. Cálculo Multivariable clases suelen llevar esto más lejos y dar un método para minimizar $f$ sujeto a una restricción de igualdad $h(x) = 0$. Se forma el Lagrangiano $L(x,z) = f(x) + \langle h(x), z \rangle$, anote la condición de optimalidad

$$\begin{align} h(x) &= 0 \\ \frac{\partial L(x,z)}{\partial x} &= 0 \end{align}$$ y resolver para $x$ (e $z$).

Cálculo clases normalmente paran ahí, sino que puede ir más lejos todavía y muestran cómo manejar restricciones de desigualdad-en ese caso vamos a tener un nonnegativity restricción y complementarias "desidia" en la optimalidad de las condiciones (condiciones KKT).

Bajo ciertos supuestos ("restricción de calificaciones"), estas condiciones de optimalidad son necesarias (pero no suficientes) para $x$ a ser un local minimizer.

Estas condiciones de optimalidad se pueden derivar alineando sobre un minimizer, o tomando algunas fotos y hacer algunos argumentos geométricos. (Nocedal y Wright presenta este material.)

Hasta ahora, no hemos mencionado convexidad en absoluto, ni hemos mencionado el problema doble. Entonces, ¿cómo esas ideas encajan en la imagen?

Una clase de cálculo podría mencionar que si nuestro problema de optimización es convexa, entonces las condiciones necesarias, de hecho, son suficientes para $x$ mundial minimizer.

Pero hay mucho más que decir sobre el caso convexo. Cuando se trabaja con funciones convexas, es antinatural para exigir a ser diferenciable. Debemos permitir la no-diferenciable de las funciones convexas y uso subgradients en lugar de gradientes. De hecho, una versión de las condiciones KKT para problemas de optimización convexa puede ser dado, que no asume la diferenciabilidad.

Y ¿cómo podemos demostrar que para un problema de optimización convexa, si un "restricción de calificación" está satisfecho, entonces el subgradiente versión de las condiciones KKT es necesario y suficiente para $x$ a ser un minimizer?

Hay distintas maneras de demostrar esto. (PREGUNTA: ¿alguien Puede resumir los diversos enfoques que podrían adoptarse para demostrar esto?) De una manera, tal vez la mejor manera, es demostrar que: 1) si Slater se satisface la condición, luego fuerte dualidad tiene y hay un doble óptimo de la variable; 2) si la fuerte dualidad se mantiene, entonces las condiciones KKT son satisfechos por $x,z$ si y sólo si $x$ es primal óptima y $z$ es dual óptima. (Este es el enfoque adoptado en Boyd y Vandenberghe.) Por primera vez en este desarrollo, ahora hemos mencionado el problema doble. Creo que otros enfoques para demostrar un teorema de KKT en optimización convexa no utilizar el doble problema en absoluto.

Y de dónde sacaste esta doble problema? ¿Cómo podemos motivar a que? ¿Cuál es la mejor manera de pensar acerca de esto?

Una de las ideas clave de análisis convexo es que un conjunto convexo cerrado $C$ es la intersección de todos los cerrados de la mitad de los espacios que contengan $C$. Creo que esto podría ser llamada la fuente de toda dualidad, resultados de análisis convexo. Cuando esta idea se aplica a un cono convexo $K$, se descubre la doble cono $K^*$ y el hecho de que $K^{**} = K$. Cuando esta idea se aplica el epígrafe de un cerrado convexo función de $f$, descubrimos el lado convexo conjugado $f^*$ y el hecho de que $f^{**} = f$. Es tentador aplicar esta idea (de alguna manera) a un problema de optimización convexa. ¿Cómo podemos asociar un conjunto convexo cerrado $C$ a un problema de optimización convexa? Si el problema es

$$\begin{align} \text{minimize}_x & \quad f(x) \\ \text{subject to} & \quad Ax = b \\ &\quad h(x) \leq 0, \end{align}$$ y $\mathcal D$ es el dominio del problema, podemos formar algo así como un "epígrafe" para este problema de optimización de la siguiente manera: $$\begin{equation} C = \{ (u,v,t) \mid \exists x \in \mathcal D \text{s.t.} u = Ax - b, h(x) \leq v, f(x) \leq t \}. \end{equation}$$

Pensando en el problema de optimización en términos de la mitad de los espacios que contengan $C$ (o en términos de hyperplanes apoyo a $C$), se obtiene una interpretación geométrica del problema doble y una buena manera de probar una fuerte dualidad teorema. (Este es el enfoque adoptado en Boyd y Vandenberghe.)

PREGUNTAS: ¿he explicado nada aquí de forma incorrecta? Existe una mejor manera de organizar o entender estas ideas, o una mejor manera de ponerlos en perspectiva? ¿Te gusta esta forma de pensar acerca de estas ideas? ¿Tiene algún comentario, incluso si no están directamente relacionados, que creo que podría encontrar interesante o que me puede ayudar a obtener una comprensión más profunda de estas ideas?

Gracias!

Answer 1

Yo creo que usted debe buscar el Fritz John condiciones. Mi opinión es que ellos son superiores a las condiciones KKT, en la que se incorporan el desagradable problema de la "restricción de calificación" en el Lagrangean por el uso de un multiplicador adicional -y que son capaces de descubrir soluciones a un problema de optimización que en virtud de KKT puede pasar desapercibido. El Fritz John condiciones se han establecido en
"F. JUAN. Extremo problemas con las desigualdades como las condiciones. En "Estudios y Ensayos, Courant Aniversario de Volumen" (K. O. Friedrichs, O. E. Neugebauer y J. J. Stoker, eds.), p 187-204. Wiley (Interscience), Nueva York, 1948"

y se han generalizado en la

"Mangasarian, O. L., & Fromovitz, S. (1967). El Fritz John necesarias de optimalidad de las condiciones en la presencia de la igualdad y la desigualdad restricciones. Revista de Análisis Matemático y Aplicaciones, 17(1), 37-47.

En una versión simplificada de la configuración, suponga que queremos $$\begin{align} \max_x &f(x)\\ s.t. & g(x) \ge 0\\ & h(x) = 0 \end{align}$$

A continuación, el Lagrangean en el caso de Fritzh Juan condiciones se formó como

$$L_{FJ} = \xi f(x) + \lambda g(x)+\mu h(x)$$ $$\lambda, \mu \ge 0,\qquad \xi \in\{0,1\},\qquad \{\xi , \lambda, \mu\}\neq \mathbf 0$$

El nuevo elemento es el multiplicador $\xi$ en la función objetivo, que toma sólo los valores cero o unidad (después de normalización). Si la solución requiere que el $\xi =1$, obtenemos las condiciones KKT con la restricción de calificación satisfecho. Si la solución requiere que el $\xi =0$, que refleja, entre otros casos especiales, en el caso de que la restricción de calificación no lleva a cabo.

Un ejemplo es el caso en que el conjunto factible para $x$ se ha reducido a un solo punto, debido a las limitaciones. A continuación, vamos a encontrar que la única solución dicta que $\xi=0$, que cuenta con una intuitiva explicación: si $x$ puede tomar uno y sólo un valor debido a las restricciones, la función objetivo "no juega ningún papel" en la determinación del$x$, por lo que se obtiene un cero multiplicador.
Esto no es tan especial que un caso como pueda parecer: en nuestro problema pueden existir parámetros que pueden variar en un rango. Y por alguna combinación(s) de sus valores en el conjunto factible puede convertirse en un punto único. Si ha aplicado condiciones KKT en un escenario, y se utiliza sólo cálculos algebraicos, usted podría terminar encima de la caracterización de casos como el de "no hay solución", mientras que una solución no existe. Lo he visto suceder - por eso creo que el FJ condiciones son superiores.