Metodo dei moltiplicatori di Lagrange

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:

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.

\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 _{j}$ , 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.^[1]

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^[2] 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, ossia né massimi né minimi di $\Lambda$ o $F$ .

La funzione $\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}.

Il valore di $\lambda _{j}$ è interpretabile come 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{cases}{\frac {\partial \Lambda }{\partial x}}=1+2\lambda x=0,&{\text{(i)}}\\{\frac {\partial \Lambda }{\partial y}}=1+2\lambda y=0,&{\text{(ii)}}\\{\frac {\partial \Lambda }{\partial \lambda }}=x^{2}+y^{2}-1=0.&{\text{(iii)}}\end{cases}}

La derivata rispetto al moltiplicatore è 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}}\quad {\text{ e }}\quad 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, ossia 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à^[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 $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

{\begin{cases}\nabla _{\mathbf {x} }\Lambda =\mathbf {0} \\\nabla _{\mathbf {\lambda } }\Lambda =\mathbf {0} \\\lambda _{j}\geq 0.\end{cases}}

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

Note

^ (EN) I.B. Vapnyarskii, Lagrange multipliers, in Encyclopaedia of Mathematics, Springer e European Mathematical Society, 2002..
^ Courant, Richard, Herbert Robbins, and Ian Stewart. What Is Mathematics?: An Elementary Approach to Ideas and Methods. New York: Oxford University Press, 1996. p. 344.
^ Alfred Marshall. 1920. Principles of Economics. An introductory Volume. 8th edition. London: Macmillan.
^ Stigler, George Joseph; “The Development of Utility Theory”, I and II, Journal of Political Economy (1950), issues 3 and 4.
^ Stigler, George Joseph; “The Adoption of Marginal Utility Theory” History of Political Economy (1972).
^ • Paul A. Samuelson and William D. Nordhaus (2004). Economics, 18th ed., [end] Glossary of Terms, "Capital (capital goods, capital equipment."
• Deardorff's Glossary of International Economics, Capital.