Multiplicadors de Lagrange

En problemes d'optimització matemàtica, el mètode dels multiplicadors de Lagrange, anomenat així per Joseph Louis Lagrange, és un mètode per trobar l'extrem d'una funció de diverses variables subjecte a una o més restriccions; és l'eina bàsica en l'optimització no lineal amb restriccions.

Fig. 1. En verd, el lloc geomètric (corba de nivell o isolínia) dels punts que satisfan la restricció g(x,y) = c. En blau els contorns de f. Les fletxes representen el gradient, que té una direcció perpendicular a la tangent de la isolínia.

Simplificant, aquesta tècnica permet determinar a quin lloc d'un conjunt particular de punts (com una esfera, un cercle o un pla) es troba l'extrem d'una funció donada. La tècnica aplica una generalització i formalització del fet que el conjunt de tots els punts a alçada h sobre la superfície de la terra és un conjunt tangent al cim d'una muntanya d'alçada h.

Més formalment, els multiplicadors de Lagrange calculen els punts estacionaris de la funció restringida. En virtut del teorema de Fermat, els extrems es troben en aquests punts, o bé en els límits, o bé en punts on la funció no és diferenciable.

Redueix el trobar els punts estacionaris d'una funció restringida d'n variables amb k restriccions a trobar els punts estacionaris d'una funció no restringida d'n+k variables. El mètode introdueix una variable escalar desconeguda nova (anomenada multiplicador de Lagrange) per a cada restricció, i defineix una funció nova (anomenada Lagrangià) en termes de la funció original, les restriccions, i els multiplicadors Lagrange.

Introducció

Considereu un cas bidimensional. Suposeu una funció $f(x,y)$ que cal maximitzar subjecte a la restricció

$g\left(x,y\right)=c,$

on c és una constant. Es poden visualitzar les isolínies de $f$ donades per

$f\left(x,y\right)=d_{n}$

per a diversos valors de $d_{n}$, i la isolínia de $g$ donada per $g(x,y)=c$.

Considereu el recorregut al llarg de la isolínia $g=c$. En general les corbes de nivell de $f$ i $g$ poden ser diferents, la trajectòria de la isolínia $g=c$ pot intersectar o encreuar-se amb les isolínies $f$. Això equival a dir que al llarg del recorregut de $g=c$ el valor de $f$ pot variar. Només quan la isolínia $g=c$ toca tangencialment la isolínia $f$, ni augmenta ni disminueix el valor de $f$, és a dir, que es toquen però no es creuen.

Això succeeix exactament quan la component tangencial de la derivada total s'anul·la: $df_{\parallel }=0$, cosa que es dona als punts estacionaris restringits de $f$ (que inclou els extrems locals restringits, assumint que $f$ és diferenciable). Computacionalment, això passa quan el pendent de $f$ és normal a la restricció: quan $\nabla f=\lambda \nabla g$ per alguns escalars $\lambda$.

Un exemple familiar es pot obtenir dels mapes meteorològics, amb les seves isolínies per a temperatura (isotermes) i pressió (isòbares): els extrems restringits són els punts on, superposant els mapes, les línies es toquen (isopletes).

La condició de tangència s'expressa geomètricament dient que els gradients de $f$ i de $g$ són vectors paral·lels en els màxims, ja que els pendents són sempre normals a les isolínies. Per tant, la solució del problema són punts $(x,y)$ on $\nabla _{x,y}f=\lambda \nabla _{x,y}g$ i, a més, $g(x,y)=c$. Per tal d'incorporar aquestes dues condicions a una equació, s'introdueix un escalar desconegut, $\lambda$, i es resol

$\nabla _{x,y,\lambda }F\left(x,y,\lambda \right)=0$

amb

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

i

$\nabla _{x,y,\lambda }=\left({\frac {\partial }{\partial x}},{\frac {\partial }{\partial y}},{\frac {\partial }{\partial \lambda }}\right).$

Justificació

Com s'ha dit més amunt, es volen trobar punts estacionaris de $f$ d'entre els punts del conjunt $g(x,y)=c$. Això succeeix només quan el pendent de $f$ no té component tangencial a les isolínies $g$. Aquesta condició es pot escriure com $\nabla _{x,y}f(x,y)=\lambda \nabla _{x,y}g(x,y)$ per a algun valor de $\lambda$. Els punts estacionaris $(x,y,\lambda )$ de $F$ també satisfan $g(x,y)=c$ com es pot comprovar considerant la derivada respecte de $\lambda$.

Advertència: diferència entre extrems i punts estacionaris

Cal tenir present que les solucions són els punts estacionaris del Lagrangià $F$, que inclou els punts de sella: no són necessàriament extrems de $F$. $F$ no té límits: donat un punt $(x,y)$ que no és sobre la restricció, fent $\lambda \to \pm \infty$ fa $F$ arbitràriament gran o petit. Tanmateix, com s'explica més endavant, sota hipòtesis més fortes el principi fort del Lagrangià diu que els màxims de $f$ maximitzen el Lagrangià globalment.

Formulació general: El principi feble del Lagrangià

Sigui la funció objectiu $f(\mathbf {x} )$ i les restriccions $g_{k}(\mathbf {x} )=0$, passant les constants a l'esquerra de la igualtat, com a $h_{k}(\mathbf {x} )-c_{k}=g_{k}(\mathbf {x} )$. El domini de f hauria de ser un conjunt obert que contingui tots els punts que satisfan les restriccions. A més, $f$ i les restriccions $g_{k}$ han de tenir les primeres derivades parcials contínues i els gradients de les $g_{k}$ han de ser no nul·les en el domini. Aleshores es defineix el Lagrangià, $\Lambda$, com

$\Lambda (\mathbf {x} ,{\boldsymbol {\lambda }})=f+\sum _{k}\lambda _{k}g_{k}.$

$k$ és un índex per a variables i funcions associades a una restricció particular, $k$.

$\mathbf {\lambda }$ sense subíndex indica el vector d'elements $\mathbf {\lambda } _{k}$, que es consideren variables independents.

Observeu que tant els criteris d'optimització com les restriccions $g_{k}(x)$ es codifiquen compactament com punts estacionaris del Lagrangià:

$\nabla _{\mathbf {x} }\Lambda =\mathbf {0}$ si i només si $\nabla _{\mathbf {x} }f=-\sum _{k}\lambda _{k}\nabla _{\mathbf {x} }g_{k},$

$\nabla _{\mathbf {x} }$ és el pendent respecte de cada element del vector $\mathbf {x}$, en comptes de totes les variables.

i

$\nabla _{\mathbf {\lambda } }\Lambda =\mathbf {0}$ implica $g_{k}=0.$

Els punts estacionaris del Lagrangià

$\nabla \Lambda =\mathbf {0}$,

donen conjuntament tantes equacions úniques com el nombre de $\mathbf {x}$ més el nombre de $\mathbf {\lambda }$. Això fa sovint possible resoldre tots els $x$ i $\lambda _{k}$, sense invertir $g_{k}$. Per aquesta raó, el mètode dels multiplicador de Lagrange pot ser útil en situacions on és més fàcil trobar les derivades de les restriccions que invertir-les.

Sovint els multiplicadors de Lagrange es poden interpretar com alguna quantitat principal d'interès. Per entendre de quina manera això és possible, observeu que:

${\frac {\partial \Lambda }{\partial {g_{k}}}}=\lambda _{k}.$

Així, λ_k és la taxa de variació de la quantitat que es vol optimitzar respecte de la variable de restricció. Per exemple, en Mecànica Lagrangiana les equacions del moviment es dedueixen trobant punts estacionaris de l'acció, la integral temporal de la diferència entre energia cinètica i energia potencial. Així, la força sobre una partícula deguda a un potencial escalar, F = −∇V, pot ser interpretada com un multiplicador de Lagrange que determina el canvi en acció (transformació d'energia potencial en energia cinètica) deguda a una variació en la trajectòria restringida de la partícula. En economia, el benefici òptim d'una part es calcula subjecte a un espai restringit d'accions, on un multiplicador de Lagrange és el valor d'alliberar una restricció donada (p. ex. a través del suborn o altres mitjans).

El mètode de les Condicions de Karush-Kuhn-Tucker és la generalització del mètode dels multiplicadors de Lagrange.

Exemples

Exemple molt senzill

Fig. 2. Il·lustració del problema d'optimització restringida.

Es desitja maximitzar $f(x,y)=x+y$ subjecte a la restricció $x^{2}+y^{2}=1$. La restricció és el cercle de radi unitat, i les isolínies de f són línies diagonals (de pendent -1), així un pot veure gràficament que el màxim es dona a $({\sqrt {2}}/2,{\sqrt {2}}/2)$ (i el mínim es dona a $(-{\sqrt {2}}/2,-{\sqrt {2}}/2)$)

Formalment, sigui $g(x,y)=x^{2}+y^{2}-1$, i

$\Lambda (x,y,\lambda )=f(x,y)+\lambda g(x,y)=x+y+\lambda (x^{2}+y^{2}-1)$

Sigui la derivada $d\Lambda =0$, que produeix el sistema d'equacions:

${\begin{aligned}{\frac {\partial \Lambda }{\partial x}}&=1+2\lambda x&&=0,\qquad {\text{(i)}}\\{\frac {\partial \Lambda }{\partial y}}&=1+2\lambda y&&=0,\qquad {\text{(ii)}}\\{\frac {\partial \Lambda }{\partial \lambda }}&=x^{2}+y^{2}-1&&=0,\qquad {\text{(iii)}}\end{aligned}}$

Com sempre, l'equació $\partial \lambda$ és la restricció original.

Combinant les dues primeres equacions s'obté $x=y$ (explícitament, $x\neq 0$ (si no, l'equació (i) donaria 1 = 0), així es pot resoldre per $\lambda$, que dona $\lambda =-1/(2x)$, que es pot substituir a (ii)).

Substituint a (iii) dona $2x^{2}=1$, així $x=\pm {\sqrt {2}}/2$ i els punts estacionaris són $({\sqrt {2}}/2,{\sqrt {2}}/2)$ i $(-{\sqrt {2}}/2,-{\sqrt {2}}/2)$. Avaluant-hi la funció objectiu f dona

$f({\sqrt {2}}/2,{\sqrt {2}}/2)={\sqrt {2}}{\mbox{ and }}f(-{\sqrt {2}}/2,-{\sqrt {2}}/2)=-{\sqrt {2}},$

Així, el màxim és ${\sqrt {2}}$, que s'assoleix a $({\sqrt {2}}/2,{\sqrt {2}}/2)$, i el mínim és $-{\sqrt {2}}$, que s'assoleix a $(-{\sqrt {2}}/2,-{\sqrt {2}}/2)$.

Exemple senzill

Es vol trobar els valors màxims de

$f(x,y)=x^{2}y\,$

amb la condició que les coordenades x i y romanguin dins el cercle de radi √3 centrat a l'origen, és a dir

$x^{2}+y^{2}=3.\,$

Com que només hi ha una condició, s'utilitza només un multiplicador, λ.

A partir de la restricció, es defineix la funció g(x, y):

$g(x,y)=x^{2}+y^{2}-3.\,$

La funció g és idènticament zero sobre el cercle de radi 3. Així, es pot sumar qualsevol múltiple de g(x, y) a f(x, y) deixant inalterada f(x, y) a la regió d'interès (damunt el cercle on se satisfà la restricció original). Siguin

$\Lambda (x,y,\lambda )=f(x,y)+\lambda g(x,y)=x^{2}y+\lambda (x^{2}+y^{2}-3).\,$

Els valors crítics de $\Lambda$ tenen lloc on el seu gradient és zero. Les derivades parcials són

${\begin{aligned}{\frac {\partial \Lambda }{\partial x}}&=2xy+2\lambda x&&=0,\qquad {\text{(i)}}\\{\frac {\partial \Lambda }{\partial y}}&=x^{2}+2\lambda y&&=0,\qquad {\text{(ii)}}\\{\frac {\partial \Lambda }{\partial \lambda }}&=x^{2}+y^{2}-3&&=0.\qquad {\text{(iii)}}\end{aligned}}$

L'equació (iii) és la restricció original. L'equació (i) implica $x=0$ o λ = −y. En el primer cas, si $x=0$ aleshores es compleix $y=\pm {\sqrt {3}}$ mitjançant (iii) i llavors mitjançant (ii) λ=0. En el segon cas, si λ = −y i substituint a l'equació (ii) tenim que,

$x^{2}-2y^{2}=0.\,$

Llavors x² = 2y². Substituint a l'equació (iii) i resolent per y dona el valor de y:

$y=\pm 1.\,$

Hi ha clarament sis punts crítics:

$({\sqrt {2}},1);\quad (-{\sqrt {2}},1);\quad ({\sqrt {2}},-1);\quad (-{\sqrt {2}},-1);\quad (0,{\sqrt {3}});\quad (0,-{\sqrt {3}}).$

Avaluant l'objectiu en aquests punts, tenim

$f(\pm {\sqrt {2}},1)=2;\quad f(\pm {\sqrt {2}},-1)=-2;\quad f(0,\pm {\sqrt {3}})=0.$

Per tant, la funció objectiu assoleix un màxim global (respecte de les restriccions) a $(\pm {\sqrt {2}},1)$ i un mínim global a $(\pm {\sqrt {2}},-1).$ El punt $(0,{\sqrt {3}})$ és un mínim local i $(0,-{\sqrt {3}})$ és un màxim local.

Exemple: entropia

Es vol trobar la distribució discreta de probabilitat amb màxima entropia d'informació. Llavors

$f(p_{1},p_{2},\ldots ,p_{n})=-\sum _{k=1}^{n}p_{k}\log _{2}p_{k}.$

Naturalment, la suma d'aquestes probabilitats és igual a 1, per tant la restricció és g(p) = 1 amb

$g(p_{1},p_{2},\ldots ,p_{n})=\sum _{k=1}^{n}p_{k}.$

Es poden utilitzar multiplicadors de Lagrange per trobar el punt de màxima entropia (depenent de les probabilitats). Per a qualsevol k des d'1 a n, cal que

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

que resulta

${\frac {\partial }{\partial p_{k}}}\left(-\sum _{k=1}^{n}p_{k}\log _{2}p_{k}+\lambda \left(\sum _{k=1}^{n}p_{k}-1\right)\right)=0.$

Fent la diferenciació d'aquestes n equacions, s'arriba a

$-\left({\frac {1}{\ln 2}}+\log _{2}p_{k}\right)+\lambda =0.$

Això mostra que tots els p_i són iguals (perquè només depenen de λ). Utilitzant la restricció ∑_k p_k = 1, s'arriba a

$p_{k}={\frac {1}{n}}.$

Per això, la distribució uniforme és la distribució amb l'entropia més gran.

Economia

L'optimització restringida té un paper central a l'economia. Per exemple, el problema d'elecció per un consumidor es representa com el problema de maximitzar una funció utilitat subjecte a una restricció pressupostària. El multiplicador de Lagrange té la interpretació econòmica del preu ombra associat a la restricció, en aquest cas la utilitat marginal d'ingressos.

El principi fort del Lagrangià: dualitat de Lagrange

Donat un problema d'optimització convexa en forma canònica

es minimitza $f_{0}(x)$ subjecte a

$f_{i}(x)\leq 0,\ i\in \left\{1,\dots ,m\right\}$

$h_{i}(x)=0,\ i\in \left\{1,\dots ,p\right\}$

tenint el domini ${\mathcal {D}}\subset \mathbb {R} ^{n}$ amb interior no buit, la funció Lagrangiana $L:\mathbb {R} ^{n}\times \mathbb {R} ^{m}\times \mathbb {R} ^{p}\to \mathbb {R}$ es defineix com

$L(x,\lambda ,\nu )=f_{0}(x)+\sum _{i=1}^{m}\lambda _{i}f_{i}(x)+\sum _{i=1}^{p}\nu _{i}h_{i}(x).$

Els vectors $\lambda$ i $\nu$ són anomenats les variables duals o vectors del multiplicador Lagrange associat al problema. La funció dual de Lagrange $g:\mathbb {R} ^{m}\times \mathbb {R} ^{p}\to \mathbb {R}$ es defineix com

$g(\lambda ,\nu )=\inf _{x\in {\mathcal {D}}}L(x,\lambda ,\nu )=\inf _{x\in {\mathcal {D}}}\left(f_{0}(x)+\sum _{i=1}^{m}\lambda _{i}f_{i}(x)+\sum _{i=1}^{p}\nu _{i}h_{i}(x)\right).$

La funció dual $g$ és còncava, àdhuc quan el problema inicial és no convex. La funció dual produeix fites inferiors de l'òptim $p^{*}$ del problema inicial; per a qualsevol $\lambda \geq 0$ i qualsevol $\nu$ tenim $g(\lambda ,\nu )\leq p^{*}$. Si es compleix el requisit d'una restricció com la Condició de Slater i el problema original és convex, llavors tenim dualitat forta, és a dir que $d^{*}=\max g(\lambda ,\nu )=\inf f_{0}=p^{*}(x)$.

Vegeu també

• Interpolació polinòmica de Lagrange
• Condicions de Karush-Kuhn-Tucker: generalització del mètode dels multiplicadors de Lagrange.
• Multiplicadors de Lagrange en espais de Banach: una altra generalització del mètode de multiplicadors de Lagrange.

Enllaços externs

• Conceptual Introduction (més una breu discussió dels multiplicadors de Lagrange en el càlcul de variacions com s'utilitzen en física) (anglès)
• Multiplicadors de Lagrange sense marcat permanent (tutorial de Dan Klein) (anglès)
• Explicació senzilla amb un exemple de governs emprant impostos com a multiplicadors de Lagrange (anglès)