Understanding why it works
Have you ever wondered why we use the Lagrange multiplier to solve constrained optimization problems?
Is it just a clever technique?
Dado que es muy fácil de usar, lo aprendemos como una aritmética básica practicándola hasta que podamos hacerlo de memoria.
Pero ¿alguna vez te has preguntado por qué funciona? ¿Siempre funciona? Si no, ¿por qué no?
Si quieres conocer las respuestas a estas preguntas, estás en el lugar correcto.
Lo desmitificaré por ti.
Un ejemplo de problema de optimización restringida
En caso de que no esté familiarizado con lo que son las optimizaciones restringidas, he escrito un artículo que lo explica. De lo contrario, siga leyendo.
Supongamos que tenemos una montaña que se parece a la siguiente:
The height of a location (x, y) is given as follows (in kilometers):
Further suppose, the mountain has an eruption:
From the top, it looks like below:
The eruption area is given as follows:
Esto significa que el borde de la erupción está dada de la siguiente manera:
Así, el borde se parece a esto.
Supongamos que queremos saber la posición más alta de la erupción en esta montaña.
Esto significa que la posición más alta debe estar en la línea de borde de la erupción, que podemos expresar de la siguiente manera:
Cualquier ubicación (x, y) que satisface g(x, y)=0 está en el borde de la erupción.
Por lo tanto, el problema de optimización restringido es encontrar el máximo f(x, y) que satisfaga g(x, y) = 0.
Intuición sobre cómo resolver el problema de optimización restringido
Intuitivamente, sabemos que la altura máxima de la erupción está alrededor de donde la flecha azul indica.
Estamos buscando la más alta línea de contorno que toque el borde de la erupción.
Definamos la ecuación de la línea de contorno:
f(x, y) = H
H es un valor constante que indica la altura del contorno.
Para un valor dado de H, hay un conjunto de (x, y) valores que satisface f(x, y) = H.
El gradiente de f(x, y) indica la dirección en la que aumenta la altura, que es perpendicular a la línea de contorno.
The gradient is a vector of partial derivatives.
Similarly, the gradient of g(x, y) is perpendicular to the edge of the eruption area.
El más alto de la línea de contorno que toque el borde de la erupción debe tener el gradiente de f(x, y) en paralelo a la pendiente de g(x, y).
Si el gradiente de la línea de contorno no está en paralelo con el gradiente de la erupción del borde, habrá alguna erupción área que se encuentra más alto que la línea de contorno.
Así, tenemos que encontrar un punto de (x, y) donde el gradiente de f(x, y) está en paralelo a la pendiente de g(x, y).
El multiplicador de Lagrange y el Lagrangiano
Pongamos nuestro objetivo en una fórmula matemática.
El gradiente de f(x, y) y el gradiente de g(x, y) deben estar en paralelo, pero pueden tener diferentes tamaños y direcciones.
grad f(x, y) = λ grad g(x, y)
Este λ se llama multiplicador de Lagrange por el nombre del matemático que introdujo la mecánica de Lagrange en 1788.
En esta etapa, no sabemos el valor de λ que podría ser cualquier cosa, como 2.5, -1, o, de lo contrario. Solo significa el hecho de que los dos gradientes deben estar en paralelo.
Podemos reorganizar la ecuación de la siguiente manera:
grad { f(x, y) - λ g(x, y) } = 0
El cero significa aquí el vector de ceros: (0,0).
Y llamamos al interior de los corchetes rizados como el Lagrangiano L.
L = f(x, y) - λ g(x, y)
por Lo tanto, estamos diciendo que la siguiente es la necesaria condición.
grad L = 0
El gradiente del Lagrangiano nos da dos ecuaciones.
Pero tenemos tres incógnitas xy y λ. ¿Cómo podemos resolver estas ecuaciones?
En realidad, tenemos una ecuación más que es el g(x, y) = 0.
Por lo tanto, podemos resolver las tres ecuaciones para encontrar la ubicación más alta (x, y) que satisfaga la restricción.
El problema ahora se convierte en un ejercicio aritmético.
La respuesta es f(x, y) = 2 where x = 1 and y = 1.
Usted puede comprobar los valores con las ecuaciones.
También, λ = -4/5 lo que significa que estos degradados están en direcciones opuestas como se esperaba.
En general, el multiplicador de Lagrange es útil para resolver problemas de optimización de restricciones.
Encontramos el punto (x, y)donde el gradiente de la función que estamos optimizando y el gradiente de la función de restricción están en paralelo utilizando el multiplicador λ.
En resumen, hemos seguido los siguientes pasos:
- Identificar la función a optimizar (maximizar o minimizar):
f(x, y) - Identificar la función de la restricción:
g(x, y) = 0 - Definir el Lagrangiano
L = f(x, y) - λ g(x, y) - Resolver
grad L = 0satisfacer la restricción
Es tan mecánico como el de arriba y ahora sé por qué funciona.
Pero hay algunas cosas más que mencionar.
Cuando no funciona
Hice algunas suposiciones mientras explicaba el multiplicador de Lagrange.
En primer lugar, asumí que todas las funciones tienen gradientes (las primeras derivadas), lo que significa que las funciones f(x, y)y g(x, y) son continuas y suaves.
En segundo lugar, también asumo que f(x, y) tiene las segundas derivadas para que podamos comprobar si la solución (x, y) es realmente la máxima o no.
Estas dos suposiciones son ciertas en este ejemplo, pero en problemas reales debe comprobarlo para poder usar el multiplicador de Lagrange para resolver su problema de optimización de restricciones.
En tercer lugar, simplifiqué la pregunta para que solo necesitáramos tratar con un máximo.
En otras palabras, la forma de la montaña se define de tal manera que solo hay una solución al problema de optimización restringida.
En problemas de la vida real, la montaña podría tener formas más complicadas con múltiples picos y valles.
En ese caso, tendríamos que lidiar con el problema de optimización global (es decir, múltiples locales maxima).
En su lugar, el ejemplo de este artículo solo trata de un máximo local, que también es el máximo global.
Espero que su comprensión del multiplicador de Lagrange sea óptima ahora.