Articulo de referencia

multiplicador de Lagrange

En optimización matemática , el método de los multiplicadores de Lagrange es una estrategia para encontrar los máximos y mínimos locales de una función sujeta a restricciones de...

En optimización matemática , el método de los multiplicadores de Lagrange es una estrategia para encontrar los máximos y mínimos locales de una función sujeta a restricciones de ecuaciones (es decir, sujeta a la condición de que una o más ecuaciones deben ser satisfechas exactamente por los valores elegidos de las variables ). [ 1 ] Recibe su nombre del matemático Joseph-Louis Lagrange .

Resumen y justificación

La idea básica es convertir un problema con restricciones en una forma tal que aún se pueda aplicar la prueba de la derivada de un problema sin restricciones. La relación entre el gradiente de la función y los gradientes de las restricciones conduce de manera bastante natural a una reformulación del problema original, conocida como la función lagrangiana o lagrangiana. [ 2 ] En el caso general, la lagrangiana se define como

L(incógnita,λ)F(incógnita)+λ,gramo(incógnita){\displaystyle {\mathcal {L}}(x,\lambda )\equiv f(x)+\langle \lambda ,g(x)\rangle }

para funcionesF,gramo{\displaystyle f,g}; la notación,{\displaystyle \langle \cdot ,\cdot \rangle }denota un producto interno . El valorλ{\displaystyle \lambda }se denomina multiplicador de Lagrange .

En casos sencillos, donde el producto interno se define como el producto escalar , el lagrangiano es

L(incógnita,λ)F(incógnita)+λgramo(incógnita){\displaystyle {\mathcal {L}}(x,\lambda )\equiv f(x)+\lambda \cdot g(x)}

El método se puede resumir de la siguiente manera: para encontrar el máximo o el mínimo de una funciónF{\displaystyle f}sujeto a la restricción de igualdadgramo(incógnita)=0{\displaystyle g(x)=0}, encontrar los puntos estacionarios deL{\displaystyle {\mathcal {L}}}considerado como una función deincógnita{\displaystyle x}y el multiplicador de Lagrangeλ {\displaystyle \lambda ~}Esto significa que todas las derivadas parciales deben ser cero, incluida la derivada parcial con respecto aλ {\displaystyle \lambda ~}. [ 3 ]

Lincógnita=0{\displaystyle {\frac {\partial {\mathcal {L}}}{\partial x}}=0} y  L λ=0 ;{\displaystyle {\frac {\ \partial {\mathcal {L}}\ }{\partial \lambda }}=0\ ;}

o equivalentemente

F(incógnita)incógnita+λgramo(incógnita)incógnita=0{\displaystyle {\frac {\partial f(x)}{\partial x}}+\lambda \cdot {\frac {\partial g(x)}{\partial x}}=0} y gramo(incógnita)=0 .{\displaystyle g(x)=0~.}

La solución correspondiente a la optimización restringida original es siempre un punto de silla de la función lagrangiana, [ 4 ] [ 5 ] que puede identificarse entre los puntos estacionarios a partir de la definición de la matriz hessiana bordeada . [ 6 ]

La gran ventaja de este método es que permite resolver la optimización sin parametrización explícita en términos de las restricciones. Como resultado, el método de los multiplicadores de Lagrange se utiliza ampliamente para resolver problemas de optimización con restricciones complejos. Además, el método de los multiplicadores de Lagrange se generaliza mediante las condiciones de Karush-Kuhn-Tucker , que también pueden tener en cuenta restricciones de desigualdad de la formah(incógnita)do{\displaystyle h(\mathbf {x} )\leq c}para una constante dadado{\displaystyle c}.

Declaración

El siguiente se conoce como el teorema de los multiplicadores de Lagrange. [ 7 ]

DejarF:RnorteR{\displaystyle f\colon \mathbb {R} ^{n}\to \mathbb {R} }Sea la función objetivo y dejemos quegramo:RnorteRdo{\displaystyle g\colon \mathbb {R} ^{n}\to \mathbb {R} ^{c}}ser la función de restricciones, ambas pertenecientes ado1{\displaystyle C^{1}}(es decir, que tengan derivadas primeras continuas). Considere el siguiente problema de optimización con restricciones:

maximizar F(incógnita)sujeto a: gramo(incógnita)=0{\displaystyle {\begin{aligned}&{\text{maximizar }}f(x)\\&{\text{sujeto a: }}g(x)=0\end{aligned}}}

Dejarincógnita{\displaystyle x_{\star }}sea ​​una solución óptima al problema de optimización anterior tal que, para la matriz de derivadas parciales[Dgramo(incógnita)]j,k= gramoj incógnitak{\displaystyle \left[\operatorname {D} g(x_{\star })\right]_{j,k}={\frac {\ \partial g_{j}\ }{\partial x_{k}}}},rango(Dgramo(incógnita))=donorte{\displaystyle \operatorname {rank} (\operatorname {D} g(x_{\star }))=c\leq n}: Entonces existe un único multiplicador de LagrangeλRdo{\displaystyle \lambda _{\star }\in \mathbb {R} ^{c}}de tal manera queDF(incógnita)=λTDgramo(incógnita) .{\displaystyle \operatorname {D} f(x_{\star })=\lambda _{\star }^{\mathsf {T}}\operatorname {D} g(x_{\star })~.}(En esta ecuación,λ{\displaystyle \lambda _ {\star }}es un vector columna, por lo tanto su transpuestaλT{\displaystyle \lambda _{\star }^{\mathsf {T}}}es un vector fila. Alternativamente, podemos redefinir el multiplicador de Lagrange directamente como un vector fila y así evitar la transposición.

El teorema de los multiplicadores de Lagrange establece que en cualquier máximo (o mínimo) local de la función evaluada bajo las restricciones de igualdad, si se cumple la condición de cualificación de las restricciones (explicada más adelante), entonces el gradiente de la función (en ese punto) puede expresarse como una combinación lineal de los gradientes de las restricciones (en ese punto), donde los multiplicadores de Lagrange actúan como coeficientes . [ 8 ] Esto equivale a decir que cualquier dirección perpendicular a todos los gradientes de las restricciones también es perpendicular al gradiente de la función. O, dicho de otro modo, decir que la derivada direccional de la función es 0 en todas las direcciones factibles.

Restricción única

Figura 1: La curva roja muestra la restricción g ( x , y ) = c . Las curvas azules son contornos de f ( x , y ) . El punto donde la restricción roja toca tangencialmente un contorno azul es el máximo de f ( x , y ) a lo largo de la restricción, ya que d 1 > d 2 .

Para el caso de una sola restricción y solo dos variables de elección (como se ejemplifica en la Figura 1), considere el problema de optimización.maximizarincógnita,yF(incógnita,y)sujeto agramo(incógnita,y)=0.{\displaystyle {\begin{aligned}{\underset {x,y}{\text{maximizar}}}\quad &f(x,y)\\{\text{sujeto a}}\quad &g(x,y)=0.\end{aligned}}} (A veces, una constante aditiva se muestra por separado en lugar de estar incluida engramo{\displaystyle g}, en cuyo caso la restricción está escritagramo(incógnita,y)=do,{\displaystyle g(x,y)=c,}como en la Figura 1.) Suponemos que ambosF{\displaystyle f}ygramo{\displaystyle g}tienen derivadas parciales primeras continuas . Introducimos una nueva variable (λ{\displaystyle \lambda }) llamado multiplicador de Lagrange (o multiplicador indeterminado de Lagrange ) y estudia la función de Lagrange (o lagrangiana o expresión lagrangiana ) definida por L(incógnita,y,λ)=F(incógnita,y)+λgramo(incógnita,y),{\displaystyle {\mathcal {L}}(x,y,\lambda )=f(x,y)+\lambda \cdot g(x,y),} donde elλ{\displaystyle \lambda }El término puede sumarse o restarse. SiF(incógnita0,y0){\displaystyle f(x_{0},y_{0})}es un máximo deF(incógnita,y){\displaystyle f(x,y)}para el problema restringido original ygramo(incógnita0,y0)0,{\displaystyle \nabla g(x_{0},y_{0})\neq 0,}entonces existeλ0{\displaystyle \lambda _{0}}de tal manera que (incógnita0,y0,λ0{\displaystyle x_{0},y_{0},\lambda _{0}}) es un punto estacionario para la función de Lagrange (los puntos estacionarios son aquellos puntos donde las primeras derivadas parciales deL{\displaystyle {\mathcal {L}}}son cero). La suposicióngramo0{\displaystyle \nabla g\neq 0}Se denomina cualificación de restricciones. Sin embargo, no todos los puntos estacionarios proporcionan una solución del problema original, ya que el método de los multiplicadores de Lagrange solo proporciona una condición necesaria para la optimalidad en problemas con restricciones. [ 9 ] [ 10 ] [ 11 ] [ 12 ] [ 13 ] También existen condiciones suficientes para un mínimo o un máximo , pero si una solución candidata particular satisface las condiciones suficientes, solo se garantiza que esa solución es la mejor localmente , es decir, es mejor que cualquier punto cercano permisible. El óptimo global se puede encontrar comparando los valores de la función objetivo original en los puntos que satisfacen las condiciones necesarias y localmente suficientes.

El método de los multiplicadores de Lagrange se basa en la intuición de que, en un máximo, f ( x , y ) no puede ser creciente en la dirección de ningún punto vecino que también tenga g = 0. Si lo fuera, podríamos movernos a lo largo de g = 0 para ascender, lo que significa que el punto de partida no era realmente el máximo. Visto así, es un análogo exacto a comprobar si la derivada de una función sin restricciones es 0 ; es decir, estamos verificando que la derivada direccional sea 0 en cualquier dirección relevante (viable).

Podemos visualizar los contornos de f dados por f ( x , y ) = d para varios valores de d , y el contorno de g dado por g ( x , y ) = c .

Supongamos que caminamos a lo largo de la línea de contorno con g = c . Nos interesa encontrar puntos donde f casi no cambia mientras caminamos, ya que estos puntos podrían ser máximos.

Esto podría suceder de dos maneras:

  1. Podríamos tocar una línea de contorno de f , ya que, por definición, f no cambia al recorrer sus líneas de contorno. Esto significaría que las tangentes a las líneas de contorno de f y g son paralelas en este punto.
  2. Hemos llegado a una parte "nivelada" de f , lo que significa que f no cambia en ninguna dirección.

Para comprobar la primera posibilidad (tocamos una línea de contorno de f ), observe que, dado que el gradiente de una función es perpendicular a las líneas de contorno, las tangentes a las líneas de contorno de f y g son paralelas si y solo si los gradientes de f y g son paralelos. Por lo tanto, queremos puntos ( x , y ) donde g ( x , y ) = c y incógnita,yF=λincógnita,ygramo,{\displaystyle \nabla _{x,y}f=\lambda \,\nabla _{x,y}g,} para algunosλ{\displaystyle \lambda }dónde incógnita,yF=(Fincógnita,Fy),incógnita,ygramo=(gramoincógnita,gramoy){\displaystyle \nabla _{x,y}f=\left({\frac {\partial f}{\partial x}},{\frac {\partial f}{\partial y}}\right),\qquad \nabla _{x,y}g=\left({\frac {\partial g}{\partial x}},{\frac {\partial g}{\partial y}}\right)} son los gradientes respectivos. La constanteλ{\displaystyle \lambda }es necesario porque, aunque los dos vectores gradiente son paralelos, las magnitudes de los vectores gradiente generalmente no son iguales. Esta constante se llama multiplicador de Lagrange. (En algunas convencionesλ{\displaystyle \lambda }va precedido de un signo menos).

Nótese que este método también resuelve la segunda posibilidad, que f sea nivel: si f es nivel, entonces su gradiente es cero, y estableciendoλ=0{\displaystyle \lambda =0}es una solución independientemente deincógnita,ygramo{\displaystyle \nabla _{x,y}g}.

Para incorporar estas condiciones en una sola ecuación, introducimos una función auxiliar. L(incógnita,y,λ)F(incógnita,y)+λgramo(incógnita,y),{\displaystyle {\mathcal {L}}(x,y,\lambda )\equiv f(x,y)+\lambda \cdot g(x,y)\,,} y resolver incógnita,y,λL(incógnita,y,λ)=0 .{\displaystyle \nabla _{x,y,\lambda }{\mathcal {L}}(x,y,\lambda )=0~.}Cabe destacar que esto equivale a resolver tres ecuaciones con tres incógnitas. Este es el método de los multiplicadores de Lagrange.

Tenga en cuenta que λL(incógnita,y,λ)=0 {\displaystyle \ \nabla _{\lambda }{\mathcal {L}}(x,y,\lambda )=0\ }implica gramo(incógnita,y)=0 ,{\displaystyle \ g(x,y)=0\ ,}como la derivada parcial deL{\displaystyle {\mathcal {L}}}con respecto aλ{\displaystyle \lambda }es gramo(incógnita,y) .{\displaystyle \ g(x,y)~.}

En resumen incógnita,y,λL(incógnita,y,λ)=0{incógnita,yF(incógnita,y)=λincógnita,ygramo(incógnita,y)gramo(incógnita,y)=0{\displaystyle \nabla _{x,y,\lambda }{\mathcal {L}}(x,y,\lambda )=0\iff {\begin{cases}\nabla _{x,y}f(x,y)=-\lambda \,\nabla _{x,y}g(x,y)\\g(x,y)=0\end{cases}}}El método se generaliza fácilmente a funciones ennorte{\displaystyle n}variables incógnita1,,incógnitanorte,λL(incógnita1,,incógnitanorte,λ)=0{\displaystyle \nabla _{x_{1},\dots ,x_{n},\lambda }{\mathcal {L}}(x_{1},\dots ,x_{n},\lambda )=0} lo que equivale a resolver n + 1 ecuaciones con n + 1 incógnitas.

Los extremos restringidos de f son puntos críticos del lagrangiano.L{\displaystyle {\mathcal {L}}}, pero no son necesariamente extremos locales deL{\displaystyle {\mathcal {L}}}(véase el  ejemplo 2 a continuación).

Se puede reformular el lagrangiano como un hamiltoniano , en cuyo caso las soluciones son mínimos locales del hamiltoniano. Esto se hace en la teoría de control óptimo , en la forma del principio del máximo de Pontryagin .

El hecho de que las soluciones del método de los multiplicadores de Lagrange no sean necesariamente extremos del lagrangiano también plantea dificultades para la optimización numérica. Esto se puede solucionar minimizando la magnitud del gradiente del lagrangiano, ya que estos mínimos coinciden con los ceros de dicha magnitud, como se ilustra en el Ejemplo 5: Optimización numérica .

Múltiples restricciones

Figura 2: Un paraboloide restringido a lo largo de dos líneas que se intersecan.
Figura 3: Mapa de contorno de la Figura 2.

El método de los multiplicadores de Lagrange se puede extender para resolver problemas con múltiples restricciones utilizando un argumento similar. Consideremos un paraboloide sujeto a dos restricciones de línea que se intersecan en un único punto. Como única solución factible, este punto es obviamente un extremo restringido. Sin embargo, el conjunto de nivel deF{\displaystyle f}Es evidente que no es paralela a ninguna de las restricciones en el punto de intersección (véase la Figura 3); en cambio, es una combinación lineal de los gradientes de las dos restricciones. En el caso de múltiples restricciones, eso es lo que buscaremos en general: el método de Lagrange busca puntos en los que el gradiente deF{\displaystyle f}es necesariamente un múltiplo del gradiente de cualquier restricción individual, pero en el que es una combinación lineal de los gradientes de todas las restricciones.

Concretamente, supongamos que tenemosMETRO{\displaystyle M}restricciones y están caminando a lo largo del conjunto de puntos que satisfacengramoi(incógnita)=0,i=1,,METRO.{\displaystyle g_{i}(\mathbf {x} )=0,i=1,\dots ,M\,.}Cada puntoincógnita{\displaystyle \mathbf {x} }en el contorno de una función de restricción dadagramoi{\displaystyle g_{i}}tiene un espacio de direcciones permitidas: el espacio de vectores perpendiculares agramoi(incógnita).{\displaystyle \nabla g_{i}(\mathbf {x} )\,.}El conjunto de direcciones permitidas por todas las restricciones es, por lo tanto, el espacio de direcciones perpendiculares a los gradientes de todas las restricciones. Denotemos este espacio de movimientos permitidos por A {\displaystyle \ A\ }y denotemos el rango de los gradientes de las restricciones porS.{\displaystyle S\,.}EntoncesA=S,{\displaystyle A=S^{\perp }\,,}el espacio de vectores perpendiculares a cada elemento deS.{\displaystyle S\,.}

Todavía estamos interesados ​​en encontrar puntos dondeF{\displaystyle f}no cambia mientras caminamos, ya que estos puntos podrían ser extremos (restringidos). Por lo tanto buscamosincógnita{\displaystyle \mathbf {x} }de tal manera que cualquier dirección de movimiento permitida se aleje deincógnita{\displaystyle \mathbf {x} }es perpendicular aF(incógnita){\displaystyle \nabla f(\mathbf {x} )}(de lo contrario podríamos aumentarF{\displaystyle f}al moverse en esa dirección permitida). En otras palabras,F(incógnita)A=S.{\displaystyle \nabla f(\mathbf {x} )\in A^{\perp }=S\,.}Por lo tanto, existen escalares.λ1,λ2, ,λMETRO{\displaystyle \lambda _{1},\lambda _{2},\ \dots ,\lambda _{M}}de tal manera que F(incógnita)=k=1METROλkgramok(incógnita)F(incógnita)k=1METROλkgramok(incógnita)=0 .{\displaystyle \nabla f(\mathbf {x} )=\sum _{k=1}^{M}\lambda _{k}\,\nabla g_{k}(\mathbf {x} )\quad \iff \quad \nabla f(\mathbf {x} )-\sum _{k=1}^{M}{\lambda _{k}\nabla g_{k}(\mathbf {x} )}=0~.}

Estos escalares son los multiplicadores de Lagrange. Ahora tenemosMETRO{\displaystyle M}de ellos, uno para cada restricción.

Como antes, introducimos una función auxiliar. L(incógnita1,,incógnitanorte,λ1,,λMETRO)=F(incógnita1,,incógnitanorte)k=1METROλkgramok(incógnita1,,incógnitanorte) {\displaystyle {\mathcal {L}}\left(x_{1},\ldots ,x_{n},\lambda _{1},\ldots ,\lambda _{M}\right)=f\left(x_{1},\ldots ,x_{n}\right)-\sum \limits _{k=1}^{M}{\lambda _{k}g_{k}\left(x_{1},\ldots ,x_{n}\right)}\ } y resolver incógnita1,,incógnitanorte,λ1,,λMETROL(incógnita1,,incógnitanorte,λ1,,λMETRO)=0{F(incógnita)k=1METROλkgramok(incógnita)=0gramo1(incógnita)==gramoMETRO(incógnita)=0{\displaystyle \nabla _{x_{1},\ldots ,x_{n},\lambda _{1},\ldots ,\lambda _{M}}{\mathcal {L}}(x_{1},\ldots ,x_{n},\lambda _{1},\ldots ,\lambda _{M})=0\iff {\begin{cases}\nabla f(\mathbf {x} )-\sum _{k=1}^{M}{\lambda _{k}\,\nabla g_{k}(\mathbf {x} )}=0\\g_{1}(\mathbf {x} )=\cdots =g_{M}(\mathbf {x} )=0\end{cases}}} lo que equivale a resolvernorte+METRO{\displaystyle n+M}ecuaciones en norte+METRO {\displaystyle \ n+M\ }desconocidos.

La condición para la calificación de restricciones cuando existen múltiples restricciones es que los gradientes de las restricciones en el punto relevante sean linealmente independientes.

Formulación moderna mediante variedades diferenciables

El problema de encontrar los máximos y mínimos locales sujetos a restricciones puede generalizarse a encontrar máximos y mínimos locales en una variedad diferenciable. METRO .{\displaystyle \ M~.}[ 14 ] En lo que sigue, no es necesario queMETRO{\displaystyle M}puede ser un espacio euclidiano, o incluso una variedad riemanniana . Todas las apariencias del gradiente  {\displaystyle \ \nabla \ }(que depende de la elección de la métrica riemanniana) puede reemplazarse por la derivada exterior. d{\displaystyle \ \operatorname {d} }.

Restricción única

Dejar METRO {\displaystyle \ M\ }ser una variedad suave de dimensión metro .{\displaystyle \ m~.}Supongamos que deseamos encontrar los puntos estacionarios. incógnita {\displaystyle \ x\ }de una función suave F:METROR {\displaystyle \ f:M\to \mathbb {R} \ }cuando se restringe a la subvariedad norte {\displaystyle \ N\ }definido por gramo(incógnita)=0 ,{\displaystyle \ g(x)=0\ ,}dónde gramo:METROR {\displaystyle \ g:M\to \mathbb {R} \ }es una función suave para la cual 0 es un valor regular .

Dejar dF {\displaystyle \ \operatorname {d} f\ }y dgramo {\displaystyle \ \operatorname {d} g\ }ser los derivados exteriores de F {\displaystyle \ f\ }y gramo {\displaystyle \ g\ }Estacionariedad para la restricción F|norte {\displaystyle \ f|_{N}\ }en incógnitanorte {\displaystyle \ x\in N\ }medio d(F|norte)incógnita=0 .{\displaystyle \ \operatorname {d} (f|_{N})_{x}=0~.}De forma equivalente, el núcleo ker(dFincógnita) {\displaystyle \ \ker(\operatorname {d} f_{x})\ }contiene Tincógnitanorte=ker(dgramoincógnita) .{\displaystyle \ T_{x}N=\ker(\operatorname {d} g_{x})~.}En otras palabras, dFincógnita {\displaystyle \ \operatorname {d} f_{x}\ }y dgramoincógnita {\displaystyle \ \operatorname {d} g_{x}\ }son 1-formas proporcionales. Para ello es necesario y suficiente que el siguiente sistema de 12metro(metro1) {\displaystyle \ {\tfrac {1}{2}}m(m-1)\ }Las ecuaciones se cumplen: dFincógnitadgramoincógnita=0Λ2(TincógnitaMETRO){\displaystyle \operatorname {d} f_{x}\wedge \operatorname {d} g_{x}=0\in \Lambda ^{2}(T_{x}^{\ast }M)} dónde  {\displaystyle \ \wedge \ }denota el producto exterior . Los puntos estacionarios incógnita {\displaystyle \ x\ }son las soluciones del sistema de ecuaciones anterior más la restricción gramo(incógnita)=0 .{\displaystyle \ g(x)=0~.}Tenga en cuenta que el 12metro(metro1) {\displaystyle \ {\tfrac {1}{2}}m(m-1)\ }Las ecuaciones no son independientes, ya que el lado izquierdo de la ecuación pertenece a la subvariedad de Λ2(TincógnitaMETRO) {\displaystyle \ \Lambda ^{2}(T_{x}^{\ast }M)\ }compuesto de elementos descomponibles .

En esta formulación, no es necesario hallar explícitamente el multiplicador de Lagrange, un número λ {\displaystyle \ \lambda \ }de tal manera que dFincógnita=λdgramoincógnita .{\displaystyle \ \operatorname {d} f_{x}=\lambda \cdot \operatorname {d} g_{x}~.}

Múltiples restricciones

Dejar METRO {\displaystyle \ M\ }y F {\displaystyle \ f\ }ser como en la sección anterior con respecto al caso de una sola restricción. En lugar de la funcióngramo{\displaystyle g}Descrita allí, ahora consideremos una función suave. GRAMO:METRORpag(pag>1) ,{\displaystyle \ G:M\to \mathbb {R} ^{p}(p>1)\ ,}con funciones de componentes gramoi:METROR ,{\displaystyle \ g_{i}:M\to \mathbb {R} \ ,}para qué0Rpag{\displaystyle 0\in \mathbb {R} ^{p}}es un valor regular .norte{\displaystyle N}sea ​​la subvariedad de METRO {\displaystyle \ M\ }definido por GRAMO(incógnita)=0 .{\displaystyle \ G(x)=0~.}

 incógnita {\displaystyle \ x\ }es un punto estacionario deF|norte{\displaystyle f|_{N}}si y solo si ker(dFincógnita) {\displaystyle \ \ker(\operatorname {d} f_{x})\ }contiene ker(dGRAMOincógnita) .{\displaystyle \ \ker(\operatorname {d} G_{x})~.}Para mayor comodidad, deje que Lincógnita=dFincógnita {\displaystyle \ L_{x}=\operatorname {d} f_{x}\ }y Kincógnita=dGRAMOincógnita ,{\displaystyle \ K_{x}=\operatorname {d} G_{x}\ ,}dónde dGRAMO{\displaystyle \ \operatorname {d} G}denota el mapa tangente o jacobiano TMETROTRpag {\displaystyle \ TM\to T\mathbb {R} ^{p}~}( TincógnitaRpag{\displaystyle \ T_{x}\mathbb {R} ^{p}}puede identificarse canónicamente con Rpag{\displaystyle \ \mathbb {R} ^{p}}). El subespacioker(Kincógnita){\displaystyle \ker(K_{x})}tiene una dimensión menor que la deker(Lincógnita){\displaystyle \ker(L_{x})}, es decir oscuro(ker(Lincógnita))=norte1 {\displaystyle \ \dim(\ker(L_{x}))=n-1\ }y oscuro(ker(Kincógnita))=nortepag .{\displaystyle \ \dim(\ker(K_{x}))=n-p~.}ker(Kincógnita){\displaystyle \ker(K_{x})}pertenece a ker(Lincógnita) {\displaystyle \ \ker(L_{x})\ }si y solo siLincógnitaTincógnitaMETRO{\displaystyle L_{x}\in T_{x}^{\ast }M}pertenece a la imagen de Kincógnita:RpagTincógnitaMETRO .{\displaystyle \ K_{x}^{\ast }:\mathbb {R} ^{p\ast }\to T_{x}^{\ast }M~.}Desde el punto de vista computacional, la condición es queLincógnita{\displaystyle L_{x}}pertenece al espacio fila de la matriz de Kincógnita ,{\displaystyle \ K_{x}\ ,}o equivalentemente el espacio columna de la matriz deKincógnita{\displaystyle K_{x}^{\ast }}(la transpuesta). Si ωincógnitaΛpag(TincógnitaMETRO) {\displaystyle \ \omega _{x}\in \Lambda ^{p}(T_{x}^{\ast }M)\ }denota el producto exterior de las columnas de la matriz de Kincógnita ,{\displaystyle \ K_{x}^{\ast }\ ,}la condición estacionaria para F|norte {\displaystyle \ f|_{N}\ }en incógnita {\displaystyle \ x\ }se convierte Lincógnitaωincógnita=0Λpag+1(TincógnitaMETRO){\displaystyle L_{x}\wedge \omega _{x}=0\in \Lambda ^{p+1}\left(T_{x}^{\ast }M\right)} Una vez más, en esta formulación no es necesario encontrar explícitamente los multiplicadores de Lagrange, los números λ1,,λpag {\displaystyle \ \lambda _{1},\ldots ,\lambda _{p}\ }de tal manera que  dFincógnita=i=1pagλid(gramoi)incógnita .{\displaystyle \ \operatorname {d} f_{x}=\sum _{i=1}^{p}\lambda _{i}\operatorname {d} (g_{i})_{x}~.}

Interpretación de los multiplicadores de Lagrange

En esta sección, modificamos las ecuaciones de restricción de la formagramoi(incógnita)=0{\displaystyle g_{i}({\bf {x}})=0}al formulario gramoi(incógnita)=doi ,{\displaystyle \ g_{i}({\bf {x}})=c_{i}\ ,}donde el doi {\displaystyle \ c_{i}\ }son m constantes reales que se consideran argumentos adicionales de la expresión lagrangianaL{\displaystyle {\mathcal {L}}}.

A menudo, los multiplicadores de Lagrange tienen una interpretación como alguna cantidad de interés. Por ejemplo, al parametrizar la línea de contorno de la restricción, es decir, si la expresión lagrangiana es L(incógnita1,incógnita2,;λ1,λ2,;do1,do2,)=F(incógnita1,incógnita2,)+λ1(do1gramo1(incógnita1,incógnita2,))+λ2(do2gramo2(incógnita1,incógnita2,))+{\displaystyle {\begin{aligned}&{\mathcal {L}}(x_{1},x_{2},\ldots ;\lambda _{1},\lambda _{2},\ldots ;c_{1},c_{2},\ldots )\\[4pt]={}&f(x_{1},x_{2},\ldots )+\lambda _{1}(c_{1}-g_{1}(x_{1},x_{2},\ldots ))+\lambda _{2}(c_{2}-g_{2}(x_{1},x_{2},\ldots ))+\cdots \end{aligned}}} entonces  Ldok=λk .{\displaystyle \ {\frac {\partial {\mathcal {L}}}{\partial c_{k}}}=\lambda _{k}~.}

Así, λ k es la tasa de cambio de la cantidad que se está optimizando en función del parámetro de restricción. Como ejemplos, en mecánica lagrangiana las ecuaciones de movimiento se derivan encontrando puntos estacionarios de la acción , la integral temporal de la diferencia entre energía cinética y potencial. Así, la fuerza sobre una partícula debida a un potencial escalar, F = −∇ V , puede interpretarse como un multiplicador de Lagrange que determina el cambio en la acción (transferencia de energía potencial a cinética) siguiendo una variación en la trayectoria restringida de la partícula. En teoría de control esto se formula en cambio como ecuaciones de coestado .

Además, por el teorema de la envolvente, el valor óptimo de un multiplicador de Lagrange tiene una interpretación como el efecto marginal de la constante de restricción correspondiente sobre el valor óptimo alcanzable de la función objetivo original: Si denotamos los valores en el óptimo con una estrella ({\displaystyle \star }), entonces se puede demostrar que  dF( incógnita1(do1,do2,), incógnita2(do1,do2,),  ) ddok=λk .{\displaystyle {\frac {\ \operatorname {d} f\left(\ x_{1\star }(c_{1},c_{2},\dots ),\ x_{2\star }(c_{1},c_{2},\dots ),\ \dots \ \right)\ }{\operatorname {d} c_{k}}}=\lambda _{\star k}~.}

Por ejemplo, en economía, el beneficio óptimo para un jugador se calcula sujeto a un espacio de acciones restringido, donde un multiplicador de Lagrange es el cambio en el valor óptimo de la función objetivo (beneficio) debido a la relajación de una restricción dada (por ejemplo, a través de un cambio en los ingresos); en tal contexto λk {\displaystyle \ \lambda _{\star k}\ }es el costo marginal de la restricción y se denomina precio sombra . [ 15 ]

Condiciones suficientes

Las condiciones suficientes para un máximo o mínimo local restringido pueden expresarse en términos de una secuencia de menores principales (determinantes de submatrices alineadas superiormente a la izquierda) de la matriz hessiana bordeada de las segundas derivadas de la expresión lagrangiana. [ 6 ] [ 16 ]

Ejemplos

Ejemplo 1

Ilustración del problema de optimización con restricciones 1 

Supongamos que deseamos maximizar F(incógnita,y)=incógnita+y {\displaystyle \ f(x,y)=x+y\ }sujeto a la restricción incógnita2+y2=1 .{\displaystyle \ x^{2}+y^{2}=1~.}El conjunto factible es el círculo unitario, y los conjuntos de nivel de f son líneas diagonales (con pendiente −1), por lo que podemos ver gráficamente que el máximo ocurre en (12,12) ,{\displaystyle \ \left({\tfrac {1}{\sqrt {2}}},{\tfrac {1}{\sqrt {2}}}\right)\ ,}y que el mínimo se produce en (12,12) .{\displaystyle \ \left(-{\tfrac {1}{\sqrt {2}}},-{\tfrac {1}{\sqrt {2}}}\right)~.}

Para el método de los multiplicadores de Lagrange, la restricción es gramo(incógnita,y)=incógnita2+y21=0 ,{\displaystyle g(x,y)=x^{2}+y^{2}-1=0\ ,} de ahí la función lagrangiana, L(incógnita,y,λ)=F(incógnita,y)+λgramo(incógnita,y)=incógnita+y+λ(incógnita2+y21) ,{\displaystyle {\begin{aligned}{\mathcal {L}}(x,y,\lambda )&=f(x,y)+\lambda \cdot g(x,y)\\[4pt]&=x+y+\lambda (x^{2}+y^{2}-1)\ ,\end{aligned}}} es una función que es equivalente a F(incógnita,y) {\displaystyle \ f(x,y)\ }cuando gramo(incógnita,y) {\displaystyle \ g(x,y)\ }está establecido en 0 .

Ahora podemos calcular el gradiente: incógnita,y,λL(incógnita,y,λ)=(Lincógnita,Ly,Lλ)=(1+2λincógnita,1+2λy,incógnita2+y21) ,{\displaystyle {\begin{aligned}\nabla _{x,y,\lambda }{\mathcal {L}}(x,y,\lambda )&=\left({\frac {\partial {\mathcal {L}}}{\partial x}},{\frac {\partial {\mathcal {L}}}{\partial y}},{\frac {\partial {\mathcal {L}}}{\partial \lambda }}\right)\\[4pt]&=\left(1+2\lambda x,1+2\lambda y,x^{2}+y^{2}-1\right)\ \color {gray}{,}\end{aligned}}} y por lo tanto: incógnita,y,λL(incógnita,y,λ)=0{1+2λincógnita=01+2λy=0incógnita2+y21=0{\displaystyle \nabla _{x,y,\lambda }{\mathcal {L}}(x,y,\lambda )=0\quad \Leftrightarrow \quad {\begin{cases}1+2\lambda x=0\\1+2\lambda y=0\\x^{2}+y^{2}-1=0\end{cases}}}

Nótese que la última ecuación es la restricción original.

Las dos primeras ecuaciones dan como resultado: incógnita=y=12λ,λ0 .{\displaystyle x=y=-{\frac {1}{2\lambda }},\qquad \lambda \neq 0~.} Sustituyendo en la última ecuación tenemos: 14λ2+14λ21=0 ,{\displaystyle {\frac {1}{4\lambda ^{2}}}+{\frac {1}{4\lambda ^{2}}}-1=0\ ,} entonces λ=±12  ,{\displaystyle \lambda =\pm {\frac {1}{\sqrt {2\ }}}\ ,} lo que implica que los puntos estacionarios deL{\displaystyle {\mathcal {L}}}son (2 2,2 2,12 ),(2 2,2 2,12 ) .{\displaystyle \left({\tfrac {\sqrt {2\ }}{2}},{\tfrac {\sqrt {2\ }}{2}},-{\tfrac {1}{\sqrt {2\ }}}\right),\qquad \left(-{\tfrac {\sqrt {2\ }}{2}},-{\tfrac {\sqrt {2\ }}{2}},{\tfrac {1}{\sqrt {2\ }}}\right)~.}

Evaluar la función objetivo f en estos puntos produce: F(2 2,2 2)=2  ,F(2 2,2 2)=2  .{\displaystyle f\left({\tfrac {\sqrt {2\ }}{2}},{\tfrac {\sqrt {2\ }}{2}}\right)={\sqrt {2\ }}\ ,\qquad f\left(-{\tfrac {\sqrt {2\ }}{2}},-{\tfrac {\sqrt {2\ }}{2}}\right)=-{\sqrt {2\ }}~.}

Por lo tanto, el máximo restringido es 2  {\displaystyle \ {\sqrt {2\ }}\ }y el mínimo restringido es2{\displaystyle -{\sqrt {2}}}.

Ejemplo 2

Ilustración del problema de optimización con restricciones 2 

Ahora modificamos la función objetivo del Ejemplo 1 para minimizar  F(incógnita,y)=(incógnita+y)2 {\displaystyle \ f(x,y)=(x+y)^{2}\ }en lugar de F(incógnita,y)=incógnita+y ,{\displaystyle \ f(x,y)=x+y\ ,}de nuevo a lo largo del círculo gramo(incógnita,y)=incógnita2+y21=0 .{\displaystyle \ g(x,y)=x^{2}+y^{2}-1=0~.}Ahora los conjuntos de nivel deF{\displaystyle f}siguen siendo líneas de pendiente −1, y los puntos en el círculo tangente a estos conjuntos de nivel son nuevamente (2/2,2/2) {\displaystyle \ ({\sqrt {2}}/2,{\sqrt {2}}/2)\ }y (2/2,2/2) .{\displaystyle \ (-{\sqrt {2}}/2,-{\sqrt {2}}/2)~.}Estos puntos de tangencia son máximos de F .{\displaystyle \ f~.}

Por otro lado, los mínimos ocurren en el conjunto de nivel para F=0 {\displaystyle \ f=0\ }(ya que por su construcción F {\displaystyle \ f\ }no puede tomar valores negativos), en (2/2,2/2) {\displaystyle \ ({\sqrt {2}}/2,-{\sqrt {2}}/2)\ }y (2/2,2/2) ,{\displaystyle \ (-{\sqrt {2}}/2,{\sqrt {2}}/2)\ ,}donde las curvas de nivel de F {\displaystyle \ f\ }no son tangentes a la restricción. La condición que incógnita,y,λ(F(incógnita,y)+λgramo(incógnita,y))=0 {\displaystyle \ \nabla _{x,y,\lambda }\left(f(x,y)+\lambda \cdot g(x,y)\right)=0\ }identifica correctamente los cuatro puntos como extremos; los mínimos se caracterizan por λ=0 {\displaystyle \ \lambda =0\ }y los máximos por λ=2 .{\displaystyle \ \lambda =-2~.}

Ejemplo 3

Ilustración del problema de optimización con restricciones 3 . 

Este ejemplo aborda cálculos más complejos, pero sigue siendo un problema con una sola restricción.

Supongamos que uno quiere encontrar los valores máximos de F(incógnita,y)=incógnita2y{\displaystyle f(x,y)=x^{2}y} con la condición de que el incógnita {\displaystyle \ x\ }- y y {\displaystyle \ y\ }-las coordenadas se encuentran en el círculo alrededor del origen con radio 3  .{\displaystyle \ {\sqrt {3\ }}~.}Es decir, sujeto a la restricción gramo(incógnita,y)=incógnita2+y23=0 .{\displaystyle g(x,y)=x^{2}+y^{2}-3=0~.}

Como solo hay una restricción, hay un solo multiplicador, por ejemplo λ .{\displaystyle \ \lambda ~.}

La restricción gramo(incógnita,y) {\displaystyle \ g(x,y)\ }es idénticamente cero en el círculo de radio 3  .{\displaystyle \ {\sqrt {3\ }}~.}Cualquier múltiplo de gramo(incógnita,y) {\displaystyle \ g(x,y)\ }se puede agregar a gramo(incógnita,y) {\displaystyle \ g(x,y)\ }partida gramo(incógnita,y) {\displaystyle \ g(x,y)\ }sin cambios en la región de interés (en el círculo donde se cumple nuestra restricción original).

Aplicando el método del multiplicador de Lagrange ordinario se obtiene L(incógnita,y,λ)=F(incógnita,y)+λgramo(incógnita,y)=incógnita2y+λ(incógnita2+y23) ,{\displaystyle {\begin{aligned}{\mathcal {L}}(x,y,\lambda )&=f(x,y)+\lambda \cdot g(x,y)\\&=x^{2}y+\lambda (x^{2}+y^{2}-3)\ ,\end{aligned}}} a partir de la cual se puede calcular el gradiente: incógnita,y,λL(incógnita,y,λ)=(Lincógnita,Ly,Lλ)=(2incógnitay+2λincógnita,incógnita2+2λy,incógnita2+y23) .{\displaystyle {\begin{aligned}\nabla _{x,y,\lambda }{\mathcal {L}}(x,y,\lambda )&=\left({\frac {\partial {\mathcal {L}}}{\partial x}},{\frac {\partial {\mathcal {L}}}{\partial y}},{\frac {\partial {\mathcal {L}}}{\partial \lambda }}\right)\\&=\left(2xy+2\lambda x,x^{2}+2\lambda y,x^{2}+y^{2}-3\right)~.\end{aligned}}} Y por lo tanto: incógnita,y,λL(incógnita,y,λ)=0{2incógnitay+2λincógnita=0incógnita2+2λy=0incógnita2+y23=0{incógnita(y+λ)=0(i)incógnita2=2λy(ii)incógnita2+y2=3(iii){\displaystyle \nabla _{x,y,\lambda }{\mathcal {L}}(x,y,\lambda )=0\quad \iff \quad {\begin{cases}2xy+2\lambda x=0\\x^{2}+2\lambda y=0\\x^{2}+y^{2}-3=0\end{cases}}\quad \iff \quad {\begin{cases}x(y+\lambda )=0&{\text{(i)}}\\x^{2}=-2\lambda y&{\text{(ii)}}\\x^{2}+y^{2}=3&{\text{(iii)}}\end{cases}}} (iii) es simplemente la restricción original. (i) implica incógnita=0 {\displaystyle \ x=0\ }o λ=y .{\displaystyle \ \lambda =-y~.}Siincógnita=0{\displaystyle x=0}entonces y=±3  {\displaystyle \ y=\pm {\sqrt {3\ }}\ }por (iii) y, en consecuencia,  λ=0 {\displaystyle \ \lambda =0\ }de (ii). Si λ=y ,{\displaystyle \ \lambda =-y\ ,}Sustituyendo esto en (ii) se obtiene incógnita2=2y2 .{\displaystyle \ x^{2}=2y^{2}~.}Sustituyendo esto en (iii) y resolviendo para y {\displaystyle \ y\ }da y=±1 .{\displaystyle \ y=\pm 1~.}Por lo tanto, hay seis puntos críticos de L :{\displaystyle \ {\mathcal {L}}\ :} (2 ,1,1);(2 ,1,1);(2 ,1,1);(2 ,1,1);(0,3 ,0);(0,3 ,0) .{\displaystyle ({\sqrt {2\ }},1,-1);\quad (-{\sqrt {2\ }},1,-1);\quad ({\sqrt {2\ }},-1,1);\quad (-{\sqrt {2\ }},-1,1);\quad (0,{\sqrt {3\ }},0);\quad (0,-{\sqrt {3\ }},0)~.}

Al evaluar el objetivo en estos puntos, se encuentra que F(±2 ,1)=2;F(±2 ,1)=2;F(0,±3 )=0 .{\displaystyle f(\pm {\sqrt {2\ }},1)=2;\quad f(\pm {\sqrt {2\ }},-1)=-2;\quad f(0,\pm {\sqrt {3\ }})=0~.}

Por lo tanto, la función objetivo alcanza el máximo global (sujeto a las restricciones) en (±2 ,1 ){\displaystyle \ (\pm {\sqrt {2\ }},1\ )}y el mínimo global en (±2 ,1) .{\displaystyle \ (\pm {\sqrt {2\ }},-1)~.}El punto (0,3 ) {\displaystyle \ (0,{\sqrt {3\ }})\ }es un mínimo local de F {\displaystyle \ f\ }y (0,3 ) {\displaystyle \ (0,-{\sqrt {3\ }})\ }es un máximo local de F ,{\displaystyle \ f\ ,}como se puede determinar considerando la matriz hessiana de L(incógnita,y,0) .{\displaystyle \ {\mathcal {L}}(x,y,0)~.}

Tenga en cuenta que mientras (2 ,1,1) {\displaystyle \ ({\sqrt {2\ }},1,-1)\ }es un punto crítico de L ,{\displaystyle \ {\mathcal {L}}\ ,}no es un extremo local de L .{\displaystyle \ {\mathcal {L}}~.}Tenemos L(2 +ε,1,1+δ)=2+δ(ε2+(22 )ε) .{\displaystyle {\mathcal {L}}\left({\sqrt {2\ }}+\varepsilon ,1,-1+\delta \right)=2+\delta \left(\varepsilon ^{2}+\left(2{\sqrt {2\ }}\right)\varepsilon \right)~.}

Dado cualquier vecindario de (2 ,1,1) ,{\displaystyle \ ({\sqrt {2\ }},1,-1)\ ,}uno puede elegir un pequeño positivo ε {\displaystyle \ \varepsilon \ }y un pequeño δ {\displaystyle \ \delta \ }de cualquiera de los signos para obtener L{\displaystyle \ {\mathcal {L}}}valores tanto mayores como menores que 2 .{\displaystyle \ 2~.}Esto también se puede observar en la matriz hessiana de L {\displaystyle \ {\mathcal {L}}\ }evaluado en este punto (o de hecho en cualquiera de los puntos críticos) que es una matriz indefinida . Cada uno de los puntos críticos de L {\displaystyle \ {\mathcal {L}}\ }es un punto de silla de L .{\displaystyle \ {\mathcal {L}}~.}[ 4 ]

Ejemplo 4 – Entropía

Supongamos que deseamos encontrar la distribución de probabilidad discreta en los puntos {pag1,pag2,,pagnorte} {\displaystyle \ \{p_{1},p_{2},\ldots ,p_{n}\}\ }con máxima entropía de información . Esto es lo mismo que decir que deseamos encontrar la distribución de probabilidad menos estructurada en los puntos. {pag1,pag2,,pagnorte} .{\displaystyle \ \{p_{1},p_{2},\cdots ,p_{n}\}~.}En otras palabras, deseamos maximizar la ecuación de entropía de Shannon : F(pag1,pag2,,pagnorte)=j=1nortepagjregistro2pagj .{\displaystyle f(p_{1},p_{2},\ldots ,p_{n})=-\sum _{j=1}^{n}p_{j}\log _{2}p_{j}~.}

Para que esto sea una distribución de probabilidad, la suma de las probabilidades pagi {\displaystyle \ p_{i}\ }en cada punto incógnitai {\displaystyle \ x_{i}\ }debe ser igual a 1, por lo tanto nuestra restricción es: gramo(pag1,pag2,,pagnorte)=j=1nortepagj=1 .{\displaystyle g(p_{1},p_{2},\ldots ,p_{n})=\sum _{j=1}^{n}p_{j}=1~.}

Utilizamos multiplicadores de Lagrange para encontrar el punto de máxima entropía, pag ,{\displaystyle \ {\vec {p}}^{\,*}\ ,}en todas las distribuciones de probabilidad discretas pag {\displaystyle \ {\vec {p}}\ }en {incógnita1,incógnita2,,incógnitanorte} .{\displaystyle \ \{x_{1},x_{2},\ldots ,x_{n}\}~.}Requerimos que: pag(F+λ(gramo1))|pag=pag=0 ,{\displaystyle \left.{\frac {\partial }{\partial {\vec {p}}}}(f+\lambda (g-1))\right|_{{\vec {p}}={\vec {p}}^{\,*}}=0\ ,} lo que da como resultado un sistema de n ecuaciones, k=1, ,norte ,{\displaystyle \ k=1,\ \ldots ,n\ ,}de tal manera que: pagk{(j=1nortepagjregistro2pagj)+λ(j=1nortepagj1)}|pagk=pagk=0 .{\displaystyle \left.{\frac {\partial }{\partial p_{k}}}\left\{-\left(\sum _{j=1}^{n}p_{j}\log _{2}p_{j}\right)+\lambda \left(\sum _{j=1}^{n}p_{j}-1\right)\right\}\right|_{p_{k}=p_{\star k}}=0~.}

Al realizar la diferenciación de estas n ecuaciones, obtenemos (1ln2+registro2pagk)+λ=0 .{\displaystyle -\left({\frac {1}{\ln 2}}+\log _{2}p_{\star k}\right)+\lambda =0~.}

Esto demuestra que todos pagk {\displaystyle \ p_{\star k}\ }son iguales (porque dependen solo de λ ). Al usar la restricción jpagj=1 ,{\displaystyle \sum _{j}p_{j}=1\ ,} encontramos pagk=1norte .{\displaystyle p_{\star k}={\frac {1}{n}}~.}

Por lo tanto, la distribución uniforme es la distribución con la mayor entropía, entre las distribuciones en n puntos.

Ejemplo 5 – Optimización numérica

Los multiplicadores de Lagrange hacen que los puntos críticos ocurran en puntos de silla (Ejemplo 5 ). 
La magnitud del gradiente se puede utilizar para forzar que los puntos críticos ocurran en mínimos locales (Ejemplo 5 ). 

Los puntos críticos de los lagrangianos ocurren en puntos de silla , en lugar de en máximos (o mínimos) locales. [ 4 ] [ 17 ] Desafortunadamente, muchas técnicas de optimización numérica, como ascenso de colina , descenso de gradiente , algunos de los métodos cuasi-Newton , entre otros, están diseñadas para encontrar máximos (o mínimos) locales y no puntos de silla. Por esta razón, se debe modificar la formulación para asegurar que sea un problema de minimización (por ejemplo, extremizando el cuadrado del gradiente del lagrangiano como se muestra a continuación), o bien utilizar una técnica de optimización que encuentre puntos estacionarios (como el método de Newton sin una búsqueda lineal de extremos ) y no necesariamente extremos.

Como ejemplo sencillo, consideremos el problema de encontrar el valor de x que minimiza F(incógnita)=incógnita2 ,{\displaystyle \ f(x)=x^{2}\ ,}restringido de tal manera que incógnita2=1 .{\displaystyle \ x^{2}=1~.}(Este problema es algo atípico porque solo hay dos valores que satisfacen esta restricción, pero resulta útil a efectos ilustrativos porque la función correspondiente sin restricciones puede visualizarse en tres dimensiones).

Utilizando multiplicadores de Lagrange, este problema se puede convertir en un problema de optimización sin restricciones: L(incógnita,λ)=incógnita2+λ(incógnita21) .{\displaystyle {\mathcal {L}}(x,\lambda )=x^{2}+\lambda (x^{2}-1)~.}

Los dos puntos críticos se producen en los puntos de silla donde x = 1 y x = −1 .

Para resolver este problema mediante una técnica de optimización numérica, primero debemos transformarlo de manera que los puntos críticos coincidan con mínimos locales. Esto se logra calculando la magnitud del gradiente del problema de optimización sin restricciones.

Primero, calculamos la derivada parcial del problema sin restricciones con respecto a cada variable: Lincógnita=2incógnita+2incógnitaλLλ=incógnita21 .{\displaystyle {\begin{aligned}&{\frac {\partial {\mathcal {L}}}{\partial x}}=2x+2x\lambda \\[5pt]&{\frac {\partial {\mathcal {L}}}{\partial \lambda }}=x^{2}-1~.\end{aligned}}}

Si la función objetivo no es fácilmente diferenciable, el diferencial con respecto a cada variable se puede aproximar como  L incógnitaL(incógnita+ε,λ)L(incógnita,λ)ε, L λL(incógnita,λ+ε)L(incógnita,λ)ε,{\displaystyle {\begin{aligned}{\frac {\ \partial {\mathcal {L}}\ }{\partial x}}\approx {\frac {{\mathcal {L}}(x+\varepsilon ,\lambda )-{\mathcal {L}}(x,\lambda )}{\varepsilon }},\\[5pt]{\frac {\ \partial {\mathcal {L}}\ }{\partial \lambda }}\approx {\frac {{\mathcal {L}}(x,\lambda +\varepsilon )-{\mathcal {L}}(x,\lambda )}{\varepsilon }},\end{aligned}}} dóndeε{\displaystyle \varepsilon }es un valor pequeño.

A continuación, calculamos la magnitud del gradiente, que es la raíz cuadrada de la suma de los cuadrados de las derivadas parciales: h(incógnita,λ)=(2incógnita+2incógnitaλ)2+(incógnita21)2 ( L(incógnita+ε,λ)L(incógnita,λ) ε)2+( L(incógnita,λ+ε)L(incógnita,λ) ε)2  .{\displaystyle {\begin{aligned}h(x,\lambda )&={\sqrt {(2x+2x\lambda )^{2}+(x^{2}-1)^{2}\ }}\\[4pt]&\approx {\sqrt {\left({\frac {\ {\mathcal {L}}(x+\varepsilon ,\lambda )-{\mathcal {L}}(x,\lambda )\ }{\varepsilon }}\right)^{2}+\left({\frac {\ {\mathcal {L}}(x,\lambda +\varepsilon )-{\mathcal {L}}(x,\lambda )\ }{\varepsilon }}\right)^{2}\ }}~.\end{aligned}}}

(Dado que la magnitud siempre es no negativa, optimizar sobre la magnitud al cuadrado equivale a optimizar sobre la magnitud. Por lo tanto, la raíz cuadrada puede omitirse de estas ecuaciones sin que ello afecte a los resultados de la optimización).

Los puntos críticos de h ocurren en x = 1 y x = −1 , al igual que enL .{\displaystyle {\mathcal {L}}~.}A diferencia de los puntos críticos enL,{\displaystyle {\mathcal {L}}\,,}Sin embargo, los puntos críticos en h se producen en mínimos locales, por lo que se pueden utilizar técnicas de optimización numérica para encontrarlos.

Aplicaciones

Mecánica lagrangiana

En mecánica lagrangiana , las ecuaciones de Euler-Lagrange pueden ampliarse con multiplicadores de Lagrange como método para imponer restricciones físicas a los sistemas. [ 18 ] Este método no es necesario en general, ya que un método alternativo consiste en elegir un conjunto de coordenadas generalizadas linealmente independientes de tal manera que las restricciones se impongan implícitamente.

Cuando se utilizan multiplicadores de Lagrange, las ecuaciones de restricción deben resolverse simultáneamente con las ecuaciones de Euler-Lagrange. Por lo tanto, las ecuaciones se convierten en un sistema de ecuaciones diferenciales algebraicas (en contraposición a un sistema de ecuaciones diferenciales ordinarias ). [ 19 ]

El método de los multiplicadores de Lagrange es útil cuando resulta difícil expresar el lagrangiano en términos de un conjunto de coordenadas generalizadas linealmente independientes. Por ejemplo, para su uso en algoritmos de modelado de sistemas dinámicos programáticos o para el modelado de sistemas con cadenas cinemáticas cerradas. [ 20 ] También son útiles para imponer restricciones no holonómicas. [ 18 ] [ 20 ]

Dado un conjunto de ecuaciones de restricción holonómicasFj(q,t)=0{\displaystyle f_{j}(\mathbf {q} ,t)=0}, las ecuaciones de Euler-Lagrange con multiplicadores de Lagrange se pueden escribir como [ 18 ] [ 19 ]

ddtLq˙iLqi+j=1doλjFjqiτi,restricción=τi{\displaystyle {\frac {\mathrm {d} }{\mathrm {d} t}}{\frac {\partial L}{\partial {\dot {q}}_{i}}}-{\frac {\partial L}{\partial q_{i}}}+\underbrace {\sum _{j=1}^{C}\lambda _{j}{\frac {\partial f_{j}}{\partial q_{i}}}} _{-\tau _{i,{\text{constraint}}}}=\tau _{i}}

El significado deτi,restricción{\displaystyle \tau _{i,{\text{constraint}}}}puede interpretarse trasladándolo al otro lado de la ecuación y absorbiéndolo en el término de fuerza generalizada.τi{\displaystyle \tau _{i}}. En esta interpretación, el sistema tienedo{\displaystyle C}número de grados de libertad adicionales, y no hay restricciones impuestas adicionales, pero las fuerzas de restricciónτi,restricción{\displaystyle \tau _{i,{\text{constraint}}}}Simplemente tienen los valores correctos para que se cumplan las restricciones. [ 18 ] [ 19 ]

Teoría de control

En la teoría de control óptimo , los multiplicadores de Lagrange se interpretan como variables coestado , y los multiplicadores de Lagrange se reformulan como la minimización del hamiltoniano , en el principio del máximo de Pontryagin .

Programación no lineal

El método de los multiplicadores de Lagrange tiene varias generalizaciones. En programación no lineal existen varias reglas de multiplicación, por ejemplo, la regla de multiplicación de Carathéodory-John y la regla de multiplicación convexa, para restricciones de desigualdad. [ 21 ]

Ciencias económicas

En muchos modelos de economía matemática , como los modelos de equilibrio general , el comportamiento del consumidor se implementa como maximización de la utilidad y el comportamiento de la empresa como maximización de beneficios , estando ambas entidades sujetas a restricciones como las presupuestarias y las de producción . La forma habitual de determinar una solución óptima se logra maximizando alguna función, donde las restricciones se imponen mediante multiplicadores de Lagrange. [ 22 ] [ 23 ] [ 24 ] [ 25 ]

Sistemas de energía

Los métodos basados ​​en multiplicadores de Lagrange tienen aplicaciones en sistemas de energía , por ejemplo, en la ubicación de recursos energéticos distribuidos (RED) y la reducción de carga. [ 26 ]

Aprendizaje por refuerzo seguro

El método de los multiplicadores de Lagrange se aplica a procesos de decisión de Markov con restricciones . [ 27 ] Produce de forma natural algoritmos primales-duales basados ​​en gradientes en el aprendizaje por refuerzo seguro. [ 28 ]

En los problemas de ecuaciones diferenciales parciales con restricciones, es decir, en el estudio de las propiedades de las soluciones normalizadas, los multiplicadores de Lagrange desempeñan un papel importante.

Véase también

Referencias

  1. Hoffmann, Laurence D.; Bradley, Gerald L. (2004). Cálculo para negocios, economía y ciencias sociales y de la vida (8.ª  ed.). McGraw Hill Higher Education. págs. 575–588 . ISBN  0-07-242432-X.
  2. Beavis, Brian; Dobbs, Ian M. (1990). «Optimización estática» . Optimización y teoría de la estabilidad para el análisis económico . Nueva York: Cambridge University Press. pág. 40. ISBN  0-521-33605-8.
  3. Protter, Murray H.; Morrey , Charles B. Jr. (1985). Cálculo intermedio (2.ª ed.). Nueva York, NY: Springer. pág. 267. ISBN   0-387-96058-9.
  4. 1 2 3 Walsh, GR (1975). «Propiedad del punto de silla de la función lagrangiana» . Métodos de optimización . Nueva York, NY: John Wiley & Sons. págs. 39–44 . ISBN  0-471-91922-5.
  5. Kalman, Dan (2009). "Nivelando con Lagrange: una visión alternativa de la optimización con restricciones". Mathematics Magazine . 82 (3): 186– 196. doi : 10.1080/0025570X.2009.11953617 . JSTOR 27765899. S2CID 121070192 .  
  6. 1 2 Silberberg, Eugene; Suen, Wing (2001). La estructura de la economía: un análisis matemático (Tercera ed.). Boston: Irwin McGraw-Hill. págs. 134–141 . ISBN   0-07-234352-4.
  7. de la Fuente , Ángel (2000). Métodos y modelos matemáticos para economistas . Cambridge: Cambridge University Press. p. 285. doi : 10.1017 /CBO9780511810756 . ISBN  978-0-521-58512-5.
  8. Luenberger, David G. (1969). Optimización mediante métodos de espacio vectorial . Nueva York: John Wiley & Sons. págs. 188–189 . 
  9. Bertsekas, Dimitri P. (1999). Programación no lineal (Segunda edición). Cambridge, MA: Athena Scientific. ISBN  1-886529-00-0.
  10. Vapnyarskii, IB (2001) [1994], "Multiplicadores de Lagrange" , Enciclopedia de Matemáticas , EMS Press.
  11. Lasdon, Leon S. (2002) [1970]. Teoría de la optimización para sistemas grandes ( edición reimpresa). Mineola, Nueva York, NY: Dover. ISBN   0-486-41999-1. MR 1888251 . 
  12. ^ Hiriart-Urruty, Jean-Baptiste; Lemaréchal, Claude (1993). "Capítulo XII: Dualidad abstracta para profesionales". Algoritmos de análisis y minimización convexos . Grundlehren der Mathematischen Wissenschaften [Principios fundamentales de las ciencias matemáticas]. vol. 306. Berlín, DE: Springer-Verlag. Págs. 136-193 (y comentarios bibliográficos págs. 334-335). ISBN    3-540-56852-2. MR 1295240 . Volumen II: Teoría avanzada y métodos de haces.  
  13. ^ Lemaréchal, Claude (15 a 19 de mayo de 2000). "Relajación lagrangiana". En Jünger, Michael; Naddef, Denis (eds.). Optimización combinatoria computacional: artículos de la escuela de primavera celebrada en Schloß Dagstuhl . Escuela de primavera celebrada en Schloß Dagstuhl del 15 al 19 de mayo de 2000 . Apuntes de conferencias sobre informática. vol. 2241. Berlín, DE: Springer-Verlag (publicado en 2001). págs. 112-156 . doi : 10.1007/3-540-45586-8_4 . ISBN   3-540-42877-1. MR 1900016 . S2CID 9048698 .  
  14. Lafontaine, Jacques (2015). Introducción a las variedades diferenciales . Springer. pág. 70. ISBN  978-3-319-20735-3.
  15. Dixit, Avinash K. (1990). «Precios sombra» . Optimización en teoría económica (2.ª ed.). Nueva York: Oxford University Press. págs. 40–54 . ISBN   0-19-877210-6.
  16. Chiang, Alpha C. (1984). Métodos fundamentales de economía matemática (Tercera ed.). McGraw-Hill. pág . 386. ISBN   0-07-010813-7.
  17. Heath, Michael T. (2005). Scientific Computing: An introductory survey . McGraw-Hill. p. 203. ISBN  978-0-07-124489-3.
  18. 1 2 3 4 Goldstein, Herbert ; Poole, Charles P. Jr .; Safko, John L. (2002). Mecánica clásica (3.ª ed.). San Francisco, CA: Addison Wesley. págs. 45–51 . ISBN   0-201-65702-3.
  19. 1 2 3 Brenan, KE; Campbell, SL; Petzold, LR (1995). Solución numérica de problemas de valor inicial en ecuaciones diferenciales-algebraicas . Sociedad de Matemáticas Industriales y Aplicadas. págs. 4– 5. doi : 10.1137/1.9781611971224 . 
  20. 12Roy, Featherstone (2008). Rigid Body Dynamics Algorithms. Springer New York. pp. 42–45, 141–143. doi:10.1007/978-1-4899-7560-7.
  21. Pourciau, Bruce H. (1980). "Modern multiplier rules". American Mathematical Monthly. 87 (6): 433–452. doi:10.2307/2320250. JSTOR 2320250.
  22. Kamien, M. I.; Schwartz, N. L. (1991). Dynamic Optimization: The Calculus of Variations and Optimal Control in Economics and Management (Second ed.). New York: Elsevier. ISBN 0-444-01609-0.
  23. Glötzl, Erhard; Glötzl, Florentin; Richters, Oliver (2019). "From constrained optimization to constrained dynamics: extending analogies between economics and mechanics". Journal of Economic Interaction and Coordination. 14 (3): 623–642. doi:10.1007/s11403-019-00252-7. hdl:10419/171974.
  24. Baxley, John V.; Moorhouse, John C. (1984). "Lagrange Multiplier Problems in Economics". The American Mathematical Monthly. 91 (7): 404–412. doi:10.1080/00029890.1984.11971446..
  25. Janová, Jitka (2011). "Applications of a constrained mechanics methodology in economics". European Journal of Physics. 32 (6): 1443–1463. arXiv:1106.3455. Bibcode:2011EJPh...32.1443J. doi:10.1088/0143-0807/32/6/001.
  26. Gautam, Mukesh; Bhusal, Narayan; Benidris, Mohammed (2020). A sensitivity-based approach to adaptive under-frequency load shedding. 2020 IEEE Texas Power and Energy Conference (TPEC). Institute of Electronic and Electrical Engineers. pp. 1–5. doi:10.1109/TPEC48276.2020.9042569.
  27. Altman, Eitan (2021). Constrained Markov Decision Processes. Routledge.
  28. Ding, Dongsheng; Zhang, Kaiqing; Jovanovic, Mihailo; Basar, Tamer (2020). Natural policy gradient primal-dual method for constrained Markov decision processes. Advances in Neural Information Processing Systems.

Further reading

  • Beavis, Brian; Dobbs, Ian M. (1990). «Optimización estática» . Optimización y teoría de la estabilidad para el análisis económico . Nueva York, NY: Cambridge University Press. págs. 32–72 . ISBN  0-521-33605-8.
  • Bertsekas, Dimitri P. (1982). Optimización con restricciones y métodos de multiplicadores de Lagrange . Nueva York, NY: Academic Press. ISBN 0-12-093480-9.
  • Beveridge, Gordon SG; Schechter, Robert S. (1970). «Multiplicadores de Lagrange» . Optimización: Teoría y práctica . Nueva York, NY: McGraw-Hill. págs. 244–259 . ISBN  0-07-005128-3.
  • Binger, Brian R.; Hoffman, Elizabeth (1998). «Optimización con restricciones». Microeconomía con cálculo (2.ª  ed.). Reading: Addison-Wesley. pp. 56–91 . ISBN  0-321-01225-9.
  • Carter, Michael (2001). «Restricciones de igualdad» . Fundamentos de economía matemática . Cambridge, MA: MIT Press. pp. 516–549 . ISBN  0-262-53192-5.
  • Hestenes, Magnus R. (1966). "Mínimos de funciones sujetas a restricciones de igualdad". Cálculo de variaciones y teoría del control óptimo . Nueva York, NY: Wiley. pp. 29–34 . 
  • Wylie, C. Ray; Barrett, Louis C. (1995). «Los extremos de las integrales bajo restricciones». Matemáticas avanzadas para ingeniería (Sexta  ed.). Nueva York, NY: McGraw-Hill. págs. 1096–1103 . ISBN  0-07-072206-4.

Exposición

  • Steuard. "Introducción conceptual" . slimy.com .— además de una breve discusión sobre los multiplicadores de Lagrange en el cálculo de variaciones tal como se utiliza en física.
  • Carpenter, Kenneth H. "Multiplicadores de Lagrange para formas cuadráticas con restricciones lineales" (PDF) . Universidad Estatal de Kansas .

Texto adicional y applets interactivos

  • Resnik. "Explicación sencilla con un ejemplo de gobiernos que utilizan los impuestos como multiplicadores de Lagrange" . umiacs.umd.edu . Universidad de Maryland . Archivado del original el 4 de septiembre de 2015. Consultado el 28 de febrero de 2007 .
  • Klein, Dan. "Multiplicadores de Lagrange sin cicatrices permanentes ] Explicación con énfasis en la intuición" (PDF) . nlp.cs.berkeley.edu . Universidad de California, Berkeley .
  • Sathyanarayana, Shashi. "Representación geométrica del método de los multiplicadores de Lagrange" . wolfram.com ( Demostración en Mathematica ). Wolfram Research . Requiere Internet Explorer / Firefox / Safari.— Proporciona una perspectiva convincente en 2  dimensiones de que, en un punto de minimización, la dirección de descenso más pronunciado debe ser perpendicular a la tangente de la curva de restricción en ese punto.
  • "Multiplicadores de Lagrange: dos variables" . MIT Open Courseware (ocw.mit.edu) (Applet). Instituto Tecnológico de Massachusetts .
  • Multiplicadores de Lagrange . MIT Open Courseware (ocw.mit.edu) (videoclase). Matemáticas 18-02: Cálculo multivariable. Instituto Tecnológico de Massachusetts . Otoño de 2007.
  • Bertsekas. "Detalles sobre los multiplicadores de Lagrange" (PDF) . athenasc.com (diapositivas / clase). Programación no lineal.— Diapositivas del curso que acompañan al texto sobre optimización no lineal
  • Wyatt, John (7 de abril de 2004) [19 de noviembre de 2002]. "Multiplicadores de Legrange, optimización con restricciones y el principio de máxima entropía" (PDF) . www-mtl.mit.edu . Elec E & CS / Mech E 6.050 – Información, entropía y computación.— Idea geométrica detrás de los multiplicadores de Lagrange
  • "Uso de multiplicadores de Lagrange en optimización" . matlab.cheme.cmu.edu (ejemplo en MATLAB). Pittsburgh, PA: Universidad Carnegie Mellon. 24 de diciembre de 2011.