Multiplicadors de Lagrange

De Viquipèdia
Dreceres ràpides: navegació, cerca
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.

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.

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ó[modifica | modifica el codi]

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 dóna 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ó[modifica | modifica el codi]

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[modifica | modifica el codi]

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à[modifica | modifica el codi]

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.[1] 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.[1] 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[modifica | modifica el codi]

Exemple molt senzill[modifica | modifica el codi]

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 dóna a (\sqrt{2}/2,\sqrt{2}/2) (i el mínim es dóna 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{align}
\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{align}

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 dóna \lambda=-1/(2x), que es pot substituir a (ii)).

Substituint a (iii) dóna 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 dóna

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[modifica | modifica el codi]

Fitxer:Lagrange simple.jpg
Fig. 3. Imatge del problema d'optimització restringida.

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(xy) a f(xy) deixant inalterada f(xy) 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^2y +  \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{align}
\frac{\partial \Lambda}{\partial x}       &= 2 x y + 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{align}


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 x2 = 2y2. Substituint a l'equació (iii) i resolent per y dóna 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[modifica | modifica el codi]

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 (\sum_{k=1}^n p_k - 1) \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 pi són iguals (perquè només depenen de λ). Utilitzant la restricció ∑k pk = 1, s'arriba a

p_k = \frac{1}{n}.

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

Economia[modifica | modifica el codi]

L'optimització restringida juga 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[modifica | modifica el codi]

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é[modifica | modifica el codi]

Referències[modifica | modifica el codi]

  1. 1,0 1,1 Weisstein, Eric W., "Lagrange Multiplier" a MathWorld (en anglès).

Enllaços externs[modifica | modifica el codi]

Consulteu el següent enllaç per referències a l'obra original de Lagrange i per a una relació de la terminologia dels Multiplicadors Lagrange.

Exposició

Text suplementari i applets interactius