Metodo dei moltiplicatori di Lagrange

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

Rappresentazione mediante curve di livello del problema. Le linee blu rappresentano curve di livello di $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 ottenere i punti stazionari di una funzione $f(\mathbf {x} )$ in $I$ variabili e $J$ vincoli di frontiera $\mathbf {g} (\mathbf {x} )=\mathbf {0}$, detta obiettivo, tramite una terza funzione in $I+J$ variabili non vincolata, detta lagrangiana:

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

introducendo tante nuove variabili scalari $\lambda$], dette moltiplicatori, quanti sono i vincoli .

Se $\mathbf {x} ^{*}$ è stazionario, per esempio un massimo, per il problema vincolato originario, allora esiste un $\mathbf {\lambda } ^{*}$ tale che $(\mathbf {x} ^{*},\mathbf {\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.

Introduzione

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

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

ove $c$ è una costante. Si possono visualizzare le curve di livello della $f$ date da

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

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

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

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

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

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

${\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 $\Lambda$ e possono essere anche punti di sella, ovvero né massimi né minimi di $\Lambda$ o $F$.

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

Spiegazione analitica

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

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

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

$\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

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

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

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

$\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, $\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

Figura 3. Illustrazione del problema di ottimizzazione vincolata.

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

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

$\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:

${\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:

$1+2\lambda x=1+2\lambda y,$

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

$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 è ${\sqrt {2}}$, raggiunto nel punto $({\sqrt {2}}/2,{\sqrt {2}}/2)$, e il minimo è $-{\sqrt {2}}$, raggiunto nel punto $(-{\sqrt {2}}/2,-{\sqrt {2}}/2)$.

Secondo il teorema di Weierstrass: essendo $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 è:

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

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

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

Per tutti gli $n$ da $1$ a $N$, si impongono le equazioni:

${\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:

$-\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 $p_{n}$ sono uguali perché dipendono soltanto da un parametro comune. Introducendola nell'equazione vincolare, ovvero imponendo

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

si ottiene:

$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à 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 del capitale..

Vincoli monolateri

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

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

$\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.

Altri progetti

Altri progetti

• Wikimedia Commons

• 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 , 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