Metodo dei moltiplicatori di Lagrange

Ricerca dei massimi di ${\displaystyle f(x,y)}$ dato il vincolo (rappresentato in rosso) ${\displaystyle g(x,y)=c}$.

Rappresentazione mediante curve di livello del problema. Le linee blu rappresentano curve di livello di ${\displaystyle f(x,y)}$. La soluzione al problema è data dai punti di tangenza tra la linea rossa e le linee blu.

In analisi matematica e programmazione matematica, il metodo dei moltiplicatori di Lagrange permette di ridurre i punti stazionari di una funzione ${\displaystyle f({\vec {x}})}$ in ${\displaystyle I}$ variabili e ${\displaystyle J}$ vincoli di frontiera ${\displaystyle {\vec {g}}({\vec {x}})={\vec {0}}}$, detta obiettivo, a quelli di una terza funzione in ${\displaystyle I+J}$ variabili non vincolata, detta lagrangiana:

${\displaystyle \Lambda ({\vec {x}},{\vec {\lambda }})=f({\vec {x}})+{\vec {\lambda }}\cdot \,{\vec {g}}({\vec {x}})=f({\vec {x}})+\sum _{j=1}^{J}\lambda _{j}g_{j}({\vec {x}})}$,

introducendo tante nuove variabili scalari λ, dette moltiplicatori, quanti sono i vincoli .

Se ${\displaystyle {\vec {x}}^{*}}$ è stazionario, per esempio un massimo, per il problema vincolato originario, allora esiste un ${\displaystyle {\vec {\lambda }}^{*}}$ tale che ${\displaystyle ({\vec {x}}^{*},{\vec {\lambda }}^{*})}$ è stazionario anche se non necessariamente dello stesso tipo, cioè nell'esempio un massimo, per la lagrangiana. Non tutti i punti stazionari portano a una soluzione del problema originario. Quindi il metodo dei moltiplicatori di Lagrange fornisce una condizione necessaria, ma non sufficiente per l'ottimizzazione nei problemi vincolati.^[1]

Introduzione

Si consideri il caso bidimensionale. Si vuole massimizzare una ${\displaystyle f(x,y)}$ soggetta al vincolo:

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

ove ${\displaystyle c}$ è una costante. Si possono visualizzare le curve di livello^[2] della ${\displaystyle f}$ date da

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

per vari valori di ${\displaystyle d_{n}}$, e le curve di livello della ${\displaystyle g}$ date da ${\displaystyle g(x,y)=c}$.

Si supponga di camminare lungo la curva di livello con ${\displaystyle g=c}$. In generale le curve di livello della ${\displaystyle f}$ e della ${\displaystyle g}$ sono distinte, quindi la curva di livello per ${\displaystyle g=c}$ può intersecare le curve di livello della ${\displaystyle f}$. Questo equivale a dire che mentre ci si muove lungo la curva di livello per ${\displaystyle g=c}$ il valore della ${\displaystyle f}$ può variare. Solo quando la curva di livello per ${\displaystyle g=c}$ è tangente a una delle curve di livello della ${\displaystyle f}$ (senza attraversamento), il valore di ${\displaystyle f}$ non aumenta né diminuisce. Nelle equazioni questo succede quando il gradiente della ${\displaystyle f}$ è perpendicolare al vincolo (o ai vincoli) ovvero quando ${\displaystyle \nabla f}$ è una combinazione lineare dei ${\displaystyle \nabla g_{i}}$.

Introducendo lo scalare incognito ${\displaystyle \lambda }$, si deve dunque risolvere il sistema di equazioni:

${\displaystyle {\frac {\partial }{\partial x}}\left[f\left(x,y\right)+\lambda \left(g\left(x,y\right)-c\right)\right]=0}$

${\displaystyle {\frac {\partial }{\partial y}}\left[f\left(x,y\right)+\lambda \left(g\left(x,y\right)-c\right)\right]=0}$

${\displaystyle {\frac {\partial }{\partial \lambda }}\left[f\left(x,y\right)+\lambda \left(g\left(x,y\right)-c\right)\right]=g\left(x,y\right)-c=0}$

Differenze tra massimi, minimi e punti di sella

Le soluzioni sono punti stazionari della lagrangiana ${\displaystyle \Lambda }$ e possono essere anche punti di sella, ovvero né massimi né minimi di ${\displaystyle \Lambda }$ o ${\displaystyle F}$.

${\displaystyle \Lambda }$ è illimitata: dato un punto ${\displaystyle (x,y)}$ che non giace sul vincolo, facendo il limite per ${\displaystyle \lambda \to \pm \infty }$ si rende ${\displaystyle \Lambda }$ arbitrariamente grande o piccola.

Spiegazione analitica

Sia l'obiettivo ${\displaystyle f}$ una funzione definita su ${\displaystyle \mathbb {R} ^{n}}$, e siano i vincoli dati da ${\displaystyle g_{j}(x)=0}$ (ottenuti da un'equazione del tipo ${\displaystyle h_{j}(x)=c_{j}}$ con ${\displaystyle g_{j}(x)=h_{j}(x)-c_{j}}$). Si definisca la lagrangiana, ${\displaystyle \Lambda }$, come:

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

Sia il criterio di ottimizzazione sia i vincoli ${\displaystyle g_{j}}$ sono compresi in modo compatto come punti stazionari della lagrangiana:

${\displaystyle \nabla _{\mathbf {x} }\Lambda =0\Leftrightarrow \nabla _{\mathbf {x} }f=-\sum _{j}\lambda _{j}\nabla _{\mathbf {x} }g_{j},}$

nei gradienti delle funzioni originarie, e

${\displaystyle \nabla _{\mathbf {\lambda } }\Lambda =0\Rightarrow {\vec {g}}={\vec {0}}.}$

Spesso i moltiplicatori di Lagrange sono interpretabili come una certa quantità interessante. Si osservi ad esempio che:

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

${\displaystyle \lambda _{j}}$ è la velocità con cui cambia la quantità da ottimizzare come funzione della variabile vincolata. Per esempio, nella meccanica lagrangiana le equazioni del moto sono ottenute trovando i punti stazionari dell'azione, l'integrale nel tempo della differenza tra energia cinetica e potenziale. Dunque la forza su una particella dovuta a un potenziale scalare, ${\displaystyle \mathbf {F} =-\nabla V}$ può essere interpretata come un moltiplicatore di Lagrange che determina il cambiamento dell'azione (trasferimento di energia potenziale in energia cinetica) conseguente a una variazione della traiettoria vincolata della particella. In economia, il profitto ottimale per un giocatore è calcolato in base a uno spazio di azione vincolato, dove un moltiplicatore di Lagrange indica il rilassamento di un dato vincolo, ad esempio attraverso la corruzione o altri mezzi.

Il metodo dei moltiplicatori di Lagrange è generalizzato dalle condizioni di Karush-Kuhn-Tucker.

Esempi

Esempio 1

Si voglia massimizzare ${\displaystyle f(x,y)=x+y}$ col vincolo ${\displaystyle x^{2}+y^{2}-1=0}$. Il vincolo è la circonferenza unitaria, e le curve di livello dell'obiettivo sono rette con pendenza ${\displaystyle -1}$: si vede subito graficamente che il massimo viene raggiunto in ${\displaystyle ({\sqrt {2}}/2,{\sqrt {2}}/2)}$ e il minimo viene raggiunto in ${\displaystyle (-{\sqrt {2}}/2,-{\sqrt {2}}/2)}$.

Analiticamente, ponendo ${\displaystyle g(x,y)=x^{2}+y^{2}-1}$, e

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

Annullando il gradiente si ottiene il sistema di equazioni:

${\displaystyle {\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}}}$

La derivata rispetto al moltiplicatore è come sempre il vincolo originario.

Combinando le prime due equazioni si ottiene:

${\displaystyle 1+2\lambda x=1+2\lambda y,}$

cioè ${\displaystyle x=y}$ (${\displaystyle x\neq 0}$ altrimenti la ${\displaystyle (i)}$ diventa ${\displaystyle 1=0}$). Sostituendo nella ${\displaystyle (iii)}$ si ottiene ${\displaystyle 2x^{2}=1}$, cosicché ${\displaystyle x=\pm {\sqrt {2}}/2}$ e i punti stazionari sono ${\displaystyle ({\sqrt {2}}/2,{\sqrt {2}}/2)}$ e ${\displaystyle (-{\sqrt {2}}/2,-{\sqrt {2}}/2)}$. Valutando l'obiettivo ${\displaystyle x+y}$ su questi si ottiene:

${\displaystyle f({\sqrt {2}}/2,{\sqrt {2}}/2)=x+y={\sqrt {2}}{\mbox{ e }}f(-{\sqrt {2}}/2,-{\sqrt {2}}/2)=x+y=-{\sqrt {2}},}$

dunque il massimo è ${\displaystyle {\sqrt {2}}}$, raggiunto nel punto ${\displaystyle ({\sqrt {2}}/2,{\sqrt {2}}/2)}$, e il minimo è ${\displaystyle -{\sqrt {2}}}$, raggiunto nel punto ${\displaystyle (-{\sqrt {2}}/2,-{\sqrt {2}}/2)}$.

Secondo il teorema di Weierstrass: essendo ${\displaystyle x+y}$ una funzione continua definita sul vincolo che è un insieme chiuso e limitato, essa ammette sicuramente un minimo e un massimo assoluti. Nessuno dei due punti stazionari trovati può quindi essere un punto di sella.

Esempio 2: entropia

Supponiamo di voler trovare la distribuzione di probabilità discreta con entropia d'informazione massimale. Allora l'obiettivo è:

${\displaystyle -\sum _{n=1}^{N}p_{n}\log _{2}p_{n}.}$

Il vincolo è che le configurazioni ${\displaystyle n}$ siano le uniche alternative possibili, cioè che la loro somma sia unitaria. La funzione di vincolo è allora:

${\displaystyle \sum _{n=1}^{N}p_{n}-1.}$

Per tutti gli ${\displaystyle n}$ da ${\displaystyle 1}$ a ${\displaystyle N}$, si impongono le equazioni:

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

Procedendo con la derivazione si ottiene, oltre all'equazione del vincolo originario:

${\displaystyle -\left({\frac {1}{\ln 2}}+\log _{2}p_{n}\right)+\lambda =0\qquad \Longrightarrow \qquad p_{n}=2^{\lambda }/e.}$

Questo dimostra che tutti i ${\displaystyle p_{n}}$ sono uguali perché dipendono soltanto da un parametro comune. Introducendola nell'equazione vincolare, ovvero imponendo

${\displaystyle \sum _{n=1}^{N}p_{n}=1,}$

si ottiene:

${\displaystyle p_{n}={\frac {1}{N}}.}$

Dunque, la distribuzione uniforme è la distribuzione di massima entropia per variabili aleatorie discrete.

Economia

L'ottimizzazione vincolata gioca un ruolo centrale in economia. Per esempio il problema della scelta per un consumatore è rappresentato come quello che massimizza una funzione di utilità^[3] soggetta a un vincolo di bilancio. Il moltiplicatore di Lagrange ha un'interpretazione economica come prezzo ombra (shadow price) associato al vincolo, in questo caso l'utilità marginale^[4][5] del capitale.^[6].

Vincoli monolateri

Se i vincoli che vengono presentati impongono disequazioni si procede come segue:

• In caso di massimizzazione porre il vincolo nella forma normale ${\displaystyle g_{j}(\mathbf {x} )\leq 0}$
• In caso di minimizzazione porre il vincolo nella forma normale ${\displaystyle g_{j}(\mathbf {x} )\geq 0}$
• Il sistema da risolvere si trasforma in

${\displaystyle \nabla _{\mathbf {x} }\Lambda =0\quad \nabla _{\mathbf {\lambda } }\Lambda =0\quad \lambda _{j}\geq 0_{j}}$

• Si procede con il calcolo del carattere della matrice hessiana orlata.

Note

Altri progetti

• Wikimedia Commons contiene immagini o altri file su metodo dei moltiplicatori di Lagrange

Collegamenti esterni

• Conceptual introduction (plus a brief discussion of Lagrange multipliers in the calculus of variations as used in physics)
• Simple explanation with an example of governments using taxes as Lagrange multipliers, su umiacs.umd.edu.
• Applet, su ocw.mit.edu.
• Video Lecture of Lagrange Multipliers, su midnighttutor.com.
• MIT Video Lecture on Lagrange Multipliers ^{[collegamento interrotto]}, su academicearth.com.
• Slides accompanying Bertsekas's nonlinear optimization text, with details on Lagrange multipliers (lectures 11 and 12)
• http://eom.springer.de/L/l057190.htm

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica