Multiplicadores de Lagrange y condiciones KKT: ¿qué ganamos?

Question

Estoy trabajando en un problema de optimización que reformula el problema en términos de condiciones KKT. ¿Puede alguien explicar lo siguiente en términos sencillos?

• ¿Qué ganamos reescribiendo un problema de optimización en términos de condiciones KKT? Parece que sólo estamos escribiendo nuestro problema de optimización restringido original como un problema de optimización restringido diferente que no es más fácil de resolver.

• De hecho, para los problemas de optimización restringidos sin restricciones de desigualdad, ¿qué ganamos exactamente al utilizar el método de los multiplicadores de Lagrange? Lo único que obtenemos es un sistema de ecuaciones no lineal que, en general, no es fácil de resolver.

Si necesitamos métodos numéricos para resolver el problema reformulado, ¿por qué no utilizar métodos numéricos desde el principio?

Answer 1

1. Como cualquier profesional sabe, el "dolor" de la resolución de un problema de optimización con restricciones consiste en averiguar qué restricciones son vinculantes y qué restricciones son flojas. Si supiéramos de antemano qué restricciones son las que realmente importan, podríamos utilizar los métodos lagrangianos. KKT nos da una manera sistemática de comprobar qué restricciones están activas (bind) y cuáles no.
2. Utilizando los métodos lagrangianos podemos obtener información valiosa sobre el problema. Los economistas se refieren a los multiplicadores de Lagrange como "precios en la sombra", porque si se tiene una restricción, por ejemplo $g(x)= c$ y el multiplicador asociado es $\lambda$ entonces usted sabe el cómo el óptimo valor de su función objetivo $f$ cambiaría si pudiera cambiar $c$ : $$\dfrac{\partial}{\partial c}\left( \max\limits_{x \text{ st } g(x)=c} f(x) \right)=\lambda.$$
3. Incluso algunos métodos numéricos que propones utilizar emplean variaciones de las ideas KKT y Lagrangianas. Otra forma natural de pensar en los multiplicadores de un problema KKT es considerarlos como sanciones por infringir las restricciones . Digamos que tenemos una restricción $g(x)\le c$ en un problema de maximización entonces el Lagrangiano es $f(x)-\lambda\cdot (g(x)-c)$ y como $\lambda\ge 0$ entonces si una rutina numérica eligiera $x$ tal que violó la restricción que reducir el valor del lagrangiano, mayor será el $\lambda$ mayor será la reducción/penalización.
4. Por último, algunos problemas se resuelven más fácilmente si se observa su doble (la dualidad es más conocida para la programación lineal, pero también podemos utilizarla en la programación no lineal) en lugar del problema original. Sin hacer referencia/utilizar los multiplicadores de Lagrange no podemos ni siquiera formular cuál es el problema dual.

Answer 2

Utilizando los multiplicadores de Lagrange o las condiciones KKT, se transforma un problema de optimización ("minimizar alguna cantidad") en un sistema de ecuaciones e inecuaciones -- ya no es un problema de optimización.

El nuevo problema puede ser más fácil de resolver. También es más fácil comprobar si un punto es una solución. Pero también hay algunos inconvenientes: por ejemplo sólo da una condición necesaria.

Esta es la misma diferencia que existe entre "encontrar $\min_x f(x)$ " y "resolver $f'(x)=0$ ", donde $f:\mathbb{R} \longrightarrow \mathbb{R}$ .

Answer 3

Empezando por su segunda pregunta: ¿Qué ganamos cuando el problema sólo tiene restricciones de igualdad - y si en todo caso es un problema que se resolverá por métodos numéricos, para qué molestarse?
Hay muchos casos en los que el problema que se estudia se plantea en términos abstractos: no hay números a la vista, sólo símbolos para las variables, y aún más símbolos para los coeficientes/parámetros. En este caso, la solución cuantitativa exacta no es algo que nos interese; lo que sí nos interesa es caracterizar la solución, es decir, determinar sus características cualitativas (como la existencia, la unicidad, la robustez a las perturbaciones, etc.). Pero aunque busquemos la solución cuantitativa concreta, la optimización numérica no caracteriza la solución, sólo te la da (¿y por qué estamos tan seguros de que el algoritmo no se ha equivocado? -especialmente con funciones objetivo de mal comportamiento). Y saber sólo esto, deja mucha incertidumbre. La optimización numérica te dará las coordenadas y la altura del pico de la montaña -¿no crees que es importante saber cómo de nevadas y resbaladizas están las rocas que rodean el pico? $$ $$ En cuanto a tu primera pregunta, en la elaboración analítica del problema suele ser una pesadilla algebraica no formular en términos de Lagrange, KKT o, mejor aún, de Fritz John. Considere $\max_{x,y} f(x,y) \; \text{s.t.}\; g(x)=h(y) $ . sin utilizar el enfoque del multiplicador se debería encontrar por ejemplo $x=g^{-1}(h(y)$ y luego enfrentar $max_{y}f\left[(g^{-1}(h(y)),y\right]$ - y yo no lo hizo dicen que $x$ y $y$ son unidimensionales. La experiencia que tengo me dice que esto es no un problema igualmente fácil de trabajar.

Answer 4

Creo que la clave está en transformar el problema de optimización en una ecuación que no necesita de un software para ser resuelta, sino que puede ser resuelta por las derivadas directamente.