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ó que cal maximitzar subjecte a la restricció

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

per a diversos valors de , i la isolínia de donada per .

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

Això succeeix exactament quan la component tangencial de la derivada total s'anul·la: , cosa que es dóna als punts estacionaris restringits de (que inclou els extrems locals restringits, assumint que és diferenciable). Computacionalment, això passa quan el pendent de és normal a la restricció: quan per alguns escalars .

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 i de 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 on i, a més, . Per tal d'incorporar aquestes dues condicions a una equació, s'introdueix un escalar desconegut, , i es resol

amb

i

Justificació[modifica | modifica el codi]

Com s'ha dit més amunt, es volen trobar punts estacionaris de d'entre els punts del conjunt . Això succeeix només quan el pendent de no té component tangencial a les isolínies . Aquesta condició es pot escriure com per a algun valor de . Els punts estacionaris de també satisfan com es pot comprovar considerant la derivada respecte de .

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à , que inclou els punts de sella: no són necessàriament extrems de . no té límits: donat un punt que no és sobre la restricció, fent fa 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 maximitzen el Lagrangià globalment.

Formulació general: El principi feble del Lagrangià[modifica | modifica el codi]

Sigui la funció objectiu i les restriccions , passant les constants a l'esquerra de la igualtat, com a . El domini de f hauria de ser un conjunt obert que contingui tots els punts que satisfan les restriccions. A més, i les restriccions han de tenir les primeres derivades parcials contínues i els gradients de les han de ser no nul·les en el domini.[1] Aleshores es defineix el Lagrangià, , com

és un índex per a variables i funcions associades a una restricció particular, .
sense subíndex indica el vector d'elements , que es consideren variables independents.

Observeu que tant els criteris d'optimització com les restriccions es codifiquen compactament com punts estacionaris del Lagrangià:

si i només si
és el pendent respecte de cada element del vector , en comptes de totes les variables.

i

implica

Els punts estacionaris del Lagrangià

,

donen conjuntament tantes equacions úniques com el nombre de més el nombre de . Això fa sovint possible resoldre tots els i , sense invertir .[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:

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 subjecte a la restricció . 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 (i el mínim es dóna a )

Formalment, sigui , i

Sigui la derivada , que produeix el sistema d'equacions:

Com sempre, l'equació és la restricció original.

Combinant les dues primeres equacions s'obté (explícitament, (si no, l'equació (i) donaria 1 = 0), així es pot resoldre per , que dóna , que es pot substituir a (ii)).

Substituint a (iii) dóna , així i els punts estacionaris són i . Avaluant-hi la funció objectiu f dóna

Així, el màxim és , que s'assoleix a , i el mínim és , que s'assoleix a .

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

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

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):

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

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


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

Llavors x2 = 2y2. Substituint a l'equació (iii) i resolent per y dóna el valor de y:

Hi ha clarament sis punts crítics:

Avaluant l'objectiu en aquests punts, tenim

Per tant, la funció objectiu assoleix un màxim global (respecte de les restriccions) a i un mínim global a El punt és un mínim local i é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

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

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

que resulta

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


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

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 subjecte a

tenint el domini amb interior no buit, la funció Lagrangiana es defineix com

Els vectors i són anomenats les variables duals o vectors del multiplicador Lagrange associat al problema. La funció dual de Lagrange es defineix com

La funció dual és còncava, àdhuc quan el problema inicial és no convex. La funció dual produeix fites inferiors de l'òptim del problema inicial; per a qualsevol i qualsevol tenim . 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 .

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