Multiplicadores de Lagrange

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

En los problemas de optimización, el método de los multiplicadores de Lagrange, llamados así en honor a Joseph Louis Lagrange, es un procedimiento para encontrar los máximos y mínimos de funciones de múltiples variables sujetas a restricciones. Este método reduce el problema restringido con n variables a uno sin restricciones de n + k variables, donde k es igual al número de restricciones, y cuyas ecuaciones pueden ser resueltas más fácilmente. Estas nuevas variables escalares desconocidas, una para cada restricción, son llamadas multiplicadores de Lagrange. El método dice que los puntos donde la función tiene un extremo condicionado con k restricciones, están entre los puntos estacionarios de una nueva función sin restricciones construida como una combinación lineal de la función y las funciones implicadas en las restricciones, cuyos coeficientes son los multiplicadores.

La demostración usa derivadas parciales y la regla de la cadena para funciones de varias variables. Se trata de extraer una función implícita de las restricciones, y encontrar las condiciones para que las derivadas parciales con respecto a las variables independientes de la función sean iguales a cero.

Introducción[editar]

Consideremos un caso bidimenional. Supongamos que tenemos la función, f (x, y), y queremos maximizarla, estando sujeta a la condición:

g(x,y) = c,

donde c es una constante. Podemos visualizar las curvas de nivel de f dadas por

f(x,y)=d_n

para varios valores de dn, y el contorno de g dado por g(x, y) = c. Supongamos que hablamos de la curva de nivel donde g = c. Entonces, en general, las curvas de nivel de f y g serán distintas, y la curva g = c por lo general intersecará y cruzará muchos contornos de f. En general, moviéndose a través de la línea g=c podemos incrementar o disminuir el valor de f. Sólo cuando g=c (el contorno que estamos siguiendo) toca tangencialmente (no corta) una curva de nivel de f, no se incrementa o disminuye el valor de f. Esto ocurre en el extremo local restringido y en los puntos de inflexión restringidos de f.

Un ejemplo familiar puede ser obtenido de los mapas climatológicos, con sus curvas de nivel de presión y temperatura (isóbaras e isotermas respectivamente): el extremo restringido ocurrirá donde los mapas superpuestos muestren curvas que se tocan.

Geométricamente traducimos la condición de tangencia diciendo que los gradientes de f y g son vectores paralelos en el máximo. Introduciendo un nuevo escalar, λ, resolvemos

\nabla[f(x, y) - λ (g(x, y) − c)] = 0

para λ ≠ 0.

Una vez determinados los valores de λ, volvemos al número original de variables y así continuamos encontrando el extremo de la nueva ecuación no restringida.

F(x,y)=f(x,y)-\lambda (g(x,y)-c)

de forma tradicional. Eso es, F(x,y) = f(x,y) para todo (x, y) satisfaciendo la condición porque g(x,y)-c es igual a cero en la restricción, pero los ceros de \nablaF(x, y) están todos en g(x,y)=c.

El método de los multiplicadores de Lagrange[editar]

Sea f (x) una función definida en un conjunto abierto n-dimensional {xRn}. Se definen s restricciones gk (x) = 0, k=1,..., s, y se observa (si las restricciones son satisfechas) que:

h(\mathbf x, \mathbf \lambda) = f - \sum_{k=1}^s \lambda_k g_k

Se procede a buscar un extremo para h

\frac{\partial h}{\partial x_i} = 0,

lo que es equivalente a

\frac{\partial f}{\partial x_i} = \sum_k^s \lambda_k \frac{\partial g_k}{\partial x_i}.
Demostración
Comenzemos con el caso de una restricción.

Sea una superficie M contenida en Rn definida por g(x)=0 y sea f(x) la función a obtener su punto crítico. Si p  \in M un punto crítico entonces se ha de cumplir:


\nabla f\cdot v=0

para todo v vector tangente a M en p (es decir, sea cual sea la dirección en la que nos desplacemos en M, el incremento de f a primer orden es nulo) La anterior condición significa que \nabla f es perpendicular al tangente a M en p y dado que dim M=n-1 existe un único vector perpendicular linealmente independiente que viene dado por  \nabla g , de modo que se tiene:


\nabla f=\lambda \nabla g

para algún número  \lambda

En el caso de que M esté definida por varias restricciones g_1,...,g_k el conjunto de vectores perpendiculares al tangente a M en p viene generado por  \nabla g_1, \nabla g_2,...\nabla g_k de modo que al ser  \nabla f perpendicular al vector tangente a M en p este ha de ser de la forma:


\nabla f=\lambda_1\nabla g_1+\lambda_2\nabla g_2+...+\lambda_k\nabla g_k

para unos ciertos números \lambda_1,...,\lambda_k


Los multiplicadores desconocidos λk se determinan a partir de las ecuaciones con las restricciones y conjuntamente se obtiene un extremo para h que al mismo tiempo satisface las restricciones (i.e. gk=0), lo que implica que f ha sido optimizada

El método de multiplicadores de Lagrange es generalizado por las condiciones de Karush-Kuhn-Tucker.

Ejemplos[editar]

Ejemplo #1[editar]

Supongamos que queremos encontrar la distribución probabilística discreta con máxima entropía. Entonces

f(p_1,p_2,\ldots,p_n) = -\sum_{k=1}^n p_k\log_2 p_k.
g(p_1,p_2,\ldots,p_n)=\sum_{k=1}^n p_k=1.

Podemos usar los multiplicadores de Lagrange para encontrar el punto de máxima entropía (dependiendo de las probabilidades). Para todo k desde 1 hasta n, necesitamos

\frac{\partial}{\partial p_k}(f+\lambda (g-1))=0,

lo que nos da

\frac{\partial}{\partial p_k}\left(-\sum_{k=1}^n p_k \log_2 p_k + \lambda\sum_{k=1}^n p_k - \lambda\right) = 0.

Derivando estas n ecuaciones, obtenemos

-\left(\frac{1}{\ln 2}+\log_2 p_k \right) + \lambda = 0.

Esto muestra que todo pi es igual (debido a que depende solamente de λ). Usando la restricción ∑k pk = 1, encontramos

p_k = \frac{1}{n}.

Esta (la distribución uniforme discreta) es la distribución con la mayor entropía.

Ejemplo #2[editar]

Determinar los puntos en la esfera x^{2}+y^{2}+z^{2}=4 que están más cercanos al punto (3,1,-1)

la distancia al punto (3,1,-1):

d=\sqrt{(x-3)^{2}+(y-1)^{2}+(z+1)^{2}}

para hacer más sencilla la operación se maximiza o minimiza el cuadrado de la distancia:

d^{2}= f(x,y,z) ={(x-3)^{2}+(y-1)^{2}+(z+1)^{2}}


la restricción: g(x,y,z)=x^{2}+y^{2}+z^{2}=4

De acuerdo con el método de los multiplicadores de Lagrange, se resuelven las ecuaciones "  \bigtriangledown f = \lambda\bigtriangledown g " y "g=4" y el resultado es:

                          (1)  2(x-3) = 2x\lambda
                          (2)  2(y-1) = 2y\lambda
                          (3)  2(z+1) = 2z\lambda
                          (4)  x^{2}+y^{2}+z^{2}=4

la manera más sencilla de resolver estas ecuaciones es dejar x, y, z en función de  \lambda y luego sustituimos en la ecuación (4).

de la ecuación (1) obtenemos  x=\frac{3}{1-\lambda} se observa que \lambda ≠ 1 por que si \lambda = 1 no se puede realizar la operación.

lo mismo sucede con la ecuación (2) y (3)

 y=\frac{1}{1-\lambda}

 z=-\frac{1}{1-\lambda}

sustituyendo en la ecuación (4)

 \left(\frac{3}{1-\lambda}\right)^{2}+\left(\frac{1}{1-\lambda}\right)^{2}+\left(-\frac{1}{1-\lambda}\right)^{2}=4

se obtiene que \lambda = 1_{-}^{+}\frac{\sqrt{11}}{2}

y entonces los puntos (x, y, z) son :

(\frac{6}{\sqrt{11}},\frac{2}{\sqrt{11}},-\frac{2}{\sqrt{11}}) y (-\frac{6}{\sqrt{11}},-\frac{2}{\sqrt{11}},\frac{2}{\sqrt{11}})

se puede observar que el punto más cercano entonces es (\frac{6}{\sqrt{11}},\frac{2}{\sqrt{11}},-\frac{2}{\sqrt{11}})

Ejemplo #3 (restricciones múltiples)[editar]

 f(x,y,z)= yz+xy

Restricciones:
 xy=1

 y^2+z^2=1

Aplicar el método:  \overrightarrow {\nabla } f = \lambda \overrightarrow {\nabla } g + \mu \overrightarrow {\nabla } h

  \overrightarrow {\nabla } f=(y,z+x,y)

  \overrightarrow {\nabla } g=(y,x,0)

  \overrightarrow {\nabla } h=(0,2y,2z)

Entonces:

y=\lambda y

z+x=x\lambda+2\mu y

y=2\mu z

xy=1

y^2+x^2=1

x\neq 0

y\neq 0

\lambda = 1

z+x=x+2\mu y

z=2\mu y

y=4\mu ^2y

y=z

2y^2=1

Por lo tanto, los puntos críticos son:

 (x,y,z) = (\sqrt{2},\frac{1}{\sqrt{2}},\frac{1}{\sqrt{2}})

 (x,y,z) = (-\sqrt{2},\frac{-1}{\sqrt{2}},\frac{-1}{\sqrt{2}})

Bastará entonces evaluar la función en esos puntos para determinar que:

 f(\sqrt{2},\frac{1}{\sqrt{2}},\frac{1}{\sqrt{2}}) = f(-\sqrt{2},\frac{-1}{\sqrt{2}},\frac{-1}{\sqrt{2}}) = \frac{3}{2}

por lo que en ambos puntos  f tiene un máximo si está restringida de esta manera.

Criterio de la segunda derivada para Extremos con Restricción[editar]

El caso bidimensional[editar]

Como en el caso no restringido en el que usamos la matriz Hessiana y el criterio de Sylvester para determinar la naturaleza de los puntos críticos, en presencia de multiplicadores de Lagrange existe un método análogo para descubrir si un punto crítico v0 es máximo, mínimo, o punto silla.

Sea f:U⊂ℝ2→ℝ y g:U⊂ℝ2→ℝ dos curvas suaves de clase C2. Sea v0∈U tal que g(v0)= c y sea S elconjunto de nivel de g con valor c. Asumimos que \nablag(v0)≠0 y existe un número real \lambda tal que \nablaf(v0) = \lambda \nablag(v0). Para la función auxiliar h = f - \lambdag tenemos la matriz hessiana limitada:


H = 
\begin{pmatrix}
0 & \frac{-\partial g}{\partial x} & \frac{-\partial g}{\partial y}\\
\frac{-\partial g}{\partial x} & \frac{\partial^2 h}{\partial x^2} & \frac{\partial^2 h}{\partial y \partial x}\\
\frac{-\partial g}{\partial y} & \frac{\partial^2 h}{\partial x \partial y} & \frac{\partial^2 h}{\partial y^2}\\
\end{pmatrix}
evaluada en v0
  1. Si |H|>0 entonces v0 es un máximo local en f limitada a S
  2. Si |H|<0 entonces v0 es un mínimo local en f limitada a S
  3. Si |H|=0 entonces el criterio no concluye nada

El caso n-dimensional[editar]

Análogamente al caso bidimensional, consideramos el caso n-dimensional, Sea f:U⊂ℝn→ℝ y g:U⊂ℝn→ℝ dos curvas suaves de clase C2. Sea v0∈U tal que g(v0)= c y sea S elconjunto de nivel de g con valor c. Asumimos que \nablag(v0)≠0 y existe un número real \lambda tal que \nablaf(v0) = \lambda \nablag(v0). Para la función auxiliar h = f - \lambdag construimos la matriz hessiana limitada:


H = 
\begin{pmatrix}
0 & \frac{-\partial g}{\partial x_1} & \frac{-\partial g}{\partial x_2} & ... & \frac{-\partial g}{\partial x_n}\\
\frac{-\partial g}{\partial x_1} & \frac{\partial^2 h}{\partial (x_1)^2} & \frac{\partial^2 h}{\partial x_1 \partial x_2} & ... & \frac{-\partial^2 h}{\partial x_1 \partial x_n}\\
\frac{-\partial g}{\partial x_2} & \frac{\partial^2 h}{\partial x_1 \partial x_2} & \frac{\partial^2 h}{\partial (x_2)^2} & ... & \frac{\partial^2 h}{\partial x_2 \partial x_n}\\
... & ... & ... & & ...\\
\frac{-\partial g}{\partial x_n} & \frac{\partial^2 h}{\partial x_1 \partial x_n} & \frac{\partial^2 h}{\partial x_2 \partial x_n} & ... & \frac{\partial^2 h}{\partial (x_n)^2}\\
\end{pmatrix}
evaluada en v0

Examinamos los determinantes de las submatrices en la diagonal de orden mayor o igual a 3:

  1. Si todos ellos son mayores que 0, tenemos un mínimo local en v0
  2. Si el primer subdeterminante de tamaño 3x3 es mayor que cero, el siguiente (el de 4x4) es menor que cero, y de esa manera los subdeterminantes van alternando su signo, tenemos un máximo local en v0
  3. Si todos los subdeterminantes son distintos de cero, pero no siguen ninguno de los dos patrones anteriores, tenemos un punto silla en v0
  4. Si no se da ninguno de los tres casos anteriores, el criterio no concluye nada

Enlaces externos[editar]