Método de los multiplicadores de Lagrange

El Método de los multiplicadores de Lagrange es un método para resolver problemas de programación no lineal, es decir, problemas en los que tanto la función objetivo y las funciones de restricciones son no lineales, es decir, problemas de la forma

maximizar f (x)
Sujeto a gi (x) = 0
Con gi: Rn → R f: Rn → R y x ∈ Rn
i entero positivo, con 1 ≤ i≤ m

Suponemos que tanto f, como las gi son funciones al menos, dos veces diferenciables

La idea es estudiar las curvas de nivel de la funcion f, es decir, aquellos valores vectoriales x en los que

N (f, k) = { x∈ Rn : f(x) = k}

Como quiera que f, está restringida a gi(x) = 0, el conjunto factible será la intersección de este conjunto con el conjunto de nivel 0 de cada una de las gi, es decir cada conjunto
N (gi, 0) = { x∈ Rn : gi (x) = 0}

Y así

RF = Región factible = N (f, k) ∩ N (gi, 0) , con i = 1, 2, ..., m

Lo primero de todo es notar que por ser f continua y RF compacto (intersección de compactos), f alcanza su máximo en RF (y su mínimo).
Supongamos que f tiene un máximo en el punto x0 y supongamos por ahora que ∇ f(x0)≠ 0 .
si nos desplazamos por los conjuntos de nivel de la f en la direcciónde mayor crecimiento de la función, esto es en la dirección de ∇ f, para el punto x0 f alcanza el máximo, supongamos el valor k0, por tanto tendremos el conjunto de nivel N (f, k0).
Por otro lado, por estar x0 en la región factible, este conjunto de nivel intersecta con a cada N (gi, 0) en el punto x0.
Se puede demostrar que en x0, los conjuntos de nivel N (f, k0) y N (gi, 0) se cortan de manera tangente, es decir ∇ f y ∇ gi son paralelos ∀ i , por tanto se tiene que

∇f (x0) = λi ∇gi (x0)

Por tanto el máximo de f restringida a gi = 0 es el máximo de la función

L(x, λ) = f(x) - λi gi(x)

A los números λi se les llaman multiplicadores de Lagrange

Recordando la condición del gradiente, una condición necesaria para que x0 sea un punto crítico de L es que se cumpla que



Obsérvese que ∇L es una función vectorial con n+m coordenadas, es decir ∇L = (Lx1, ... , Lxn, Lλ1, ..., Lλm),

Así nuestro problema de programación no lineal se ha reducido a resolver un sistema no lineal de n+m ecuaciones para las incógnitas xj, λi, donde . 1 ≤ i≤ m, 1 ≤ j≤ n . Lo cual es un problema, en principio, nada trivial de resolver, cuyas ecuaciones son.



Obsérvese también que los puntos donde se verifica el sistema de ecuaciones pueden corresponder a máximos, mínimos o puntos de silla, de modo que la solución, en principio, tampoco está garantizada por este método, tales soluciones van a requerir un análisis un poco mayor, entre ellos el cálculo del Hessiano o bien se puede recurrir a un análisis de la vecindad del punto en cuestión para analizar la solución.

Hay varios métodos para el cálculo de máximo de L uno de ellos es aplicar el método del gradiente a la función L Esto es, calcularemos numéricamente ∇L e iremos avanzando en la dirección en la que tiende a hacerse cero, encontrado este punto, el método del Hessiano o otro tipo de análisis nos dirá siel punto crítico es un máximo, un mínimo o un punto de silla.