Metodo dei moltiplicatori di Lagrange

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

Figura 2: Rappresentazione mediante curve di livello del problema della figura 1. La linea rossa evidenzia il vincolo g(x,y) = c. 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.

Nei problemi di ottimizzazione, quello dei moltiplicatori di Lagrange (così chiamati da Joseph Louis Lagrange) è un metodo per trovare i massimi e i minimi di una funzione di più variabili soggetta a uno o più vincoli: è lo strumento di base nell'ottimizzazione non lineare vincolata.

I moltiplicatori di Lagrange calcolano i punti stazionari della funzione vincolata; dal teorema di Fermat sui punti stazionari, i massimi e i minimi si trovano in questi punti, o sul bordo, o nei punti in cui la funzione non è differenziabile.

Questo metodo riduce la ricerca dei punti stazionari, di una funzione vincolata in n variabili con k vincoli, a trovare i punti stazionari di una funzione non vincolata in n+k variabili: esso introduce una nuova variabile scalare incognita, il moltiplicatore di Lagrange appunto, per ogni vincolo e definisce una nuova funzione (la Lagrangiana) in termini della funzione originaria, dei vincoli e dei moltiplicatori di Lagrange.

Per esempio (vedi Figura 1 a destra), si consideri il problema di ottimizzazione:

massimizzare $f(x, y) \,$

sotto il vincolo $g(x, y) = c. \,$

Introduciamo una nuova variabile (λ) chiamata moltiplicatore di Lagrange, e studiamo la funzione di Lagrange definita da:

$\Lambda(x,y,\lambda) = f(x,y) + \lambda \Big(g(x,y)-c\Big).$

Se (x,y) è un massimo per il problema vincolato originario, allora esiste un λ tale che (x,y,λ) è un punto stazionario per la Lagrangiana (i punti stazionari sono quei punti dove le derivate parziali di Λ sono pari a zero). Comunque, non tutti i punti stazionari portano ad una soluzione del problema originario. Quindi, il metodo dei moltiplicatori di Lagrange fornisce una condizione necessaria per l'ottimizzazione nei problemi vincolati.

Introduzione

Consideriamo il caso bidimensionale. Supponiamo di avere una funzione, f(x,y), da massimizzare soggetta al vincolo:

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

ove c è una costante. Possiamo 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.

Supponiamo di camminare lungo la curva di livello con g = c. In generale le curve di livello della f e della g possono essere distinte, quindi la curva di livello per g = c potrebbe passare attraverso 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 potrebbe variare. Solo quando la curva di livello per g = c tocca le curve di livello della f in modo tangente, il valore della f non aumenta né diminuisce - cioè, le curve di livello toccano ma non attraversano.

Questo succede esattamente quando la componente tangente della derivata totale si annulla: $df_\parallel = 0$, cioè nei punti stazionari vincolati della f (che includono i massimi e minimi locali, assumendo che f sia differenziabile). In equazioni, questo succede quando il gradiente della f è perpendicolare al vincolo (o ai vincoli), ovvero quando grad f è una combinazione lineare dei grad g_i.

Un esempio familiare può essere ottenuto dalle mappe meteorologiche, con le loro curve di livello per temperatura e pressione: i massimi e minimi vincolati capiteranno dove le mappe sovrapposte mostrano linee tangenti (isoplete).

Geometricamente traduciamo la condizione di tangenza dicendo che i gradienti della f e della g sono vettori paralleli dove c'è un massimo, visto che i gradienti sono sempre perpendicolari alle curve di livello. Introducendo uno scalare incognito, λ, dobbiamo risolvere

$\nabla \left[f \left(x, y \right) + \lambda \left(g \left(x, y \right) - c \right) \right] = 0$

per λ ≠ 0.

Una volta che i valori per λ sono stati determinati, torniamo al numero originario di variabili e possiamo quindi continuare a trovare i punti stazionari della nuova funzione non vincolata

$F \left( x , y \right) = f \left( x , y \right) + \lambda \left( g \left( x , y \right) - c \right)$

nel modo tradizionale. Cioè, F(x,y) = f(x,y) per ogni punto (x,y) che soddisfa il vincolo perché g(x,y) − c è uguale a zero sul vincolo, ma i punti stazionari della F(x,y) sono tutti su g(x,y) = c. (Come può essere visto ponendo il gradiente uguale a zero.)

Attenzione: differenze tra massimi e minimi e punti stazionari

Bisogna essere consapevoli del fatto che le soluzioni sono punti stazionari della Lagrangiana Λ, e questi possono essere anche punti di sella: questi non sono né massimi né minimi di Λ o F. Λ è illimitata: dato un punto (x,y) che non giace sul vincolo, facendo il limite per $\lambda \to \pm \infty$ si rende Λ arbitrariamente grande o piccola.

Il metodo dei moltiplicatori di Lagrange

Sia f una funzione definita su Rⁿ, e siano i vincoli dati da g_k(x) = 0 (ottenuti da un' equazione del tipo h_k(x) = c con g_k(x) = h_k(x) - c). Ora si definisca la Lagrangiana, Λ, come

$\Lambda(\mathbf x, \boldsymbol \lambda) = f + \sum_k \lambda_k g_k.$

Si osservi che sia il criterio di ottimizzazione sia i vincoli g_k sono compresi in modo compatto come punti stazionari della Lagrangiana:

$\nabla_{\mathbf x} \Lambda = 0 \Leftrightarrow \nabla_{\mathbf x} f = - \sum_k \lambda_k \nabla_{\mathbf x} g_k,$

e

$\nabla_{\mathbf \lambda} \Lambda = 0 \Rightarrow g_k = 0.$

Spesso i moltiplicatori di Lagrange hanno un'interpretazione come una certa quantità interessante. Per vedere perché ciò può capitare, si osservi che:

$\frac{\partial \Lambda}{\partial {g_k}} = \lambda_k.$

Dunque, λ_k è la velocità con cui cambia la quantità da ottimizzare come funzione della variabile vincolata. Come esempi, 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, F = −∇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.

Esempio

Esempio semplicissimo

Figura 3. Illustrazione del problema di ottimizzazione vincolata.

Supponi di voler massimizzare f(x,y) = x + y sotto il vincolo x² + y² = 1. Il vincolo è il cerchio unitario, e le curve di livello della f sono rette diagonali (con pendenza -1), così si può vedere 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)$)

Formalmente, poniamo g(x,y) = x² + y² − 1, e

Λ(x,y,λ) = f(x,y) + λg(x,y) = x + y + λ(x² + y² − 1)

Poniamo la derivata dΛ = 0, ottenendo il sistema di equazioni:

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

Come sempre, la derivata rispetto a λ è il vincolo originario.

Combinando le prime due equazioni si ottiene x = y ($x \neq 0$ altrimenti (i) implica 1 = 0). Sostituendo nella (iii) si ottiene 2x² = 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 la funzione studiata f su questi si ottiene

$f(\sqrt{2}/2,\sqrt{2}/2)=\sqrt{2}\mbox{ e } f(-\sqrt{2}/2, -\sqrt{2}/2)=-\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)$.

N.B. Essendo f 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 semplice

Supponiamo di voler trovare i valori di massimo per la funzione

$f(x, y) = x^2 y \,$

con la condizione che (x,y) giace sul cerchio centrato nell'origine di raggio √3, cioè,

$x^2 + y^2 = 3. \,$

Visto che c'è una sola condizione, useremo un solo moltiplicatore, diciamo λ.

Usiamo il vincolo per definire una funzione g(x, y):

$g (x, y) = x^2 +y^2 -3. \,$

La funzione g è identicamente nulla sul cerchio di raggio √3. Dunque ogni multiplo di g(x, y) può essere aggiunto alla f(x, y) senza cambiarne il valore sul vincolo. Sia

$\Lambda(x, y, \lambda) = f(x,y) + \lambda g(x, y) = x^2y + \lambda (x^2 + y^2 - 3). \,$

I valori critici di Λ capitano quando il suo gradiente è zero. Le derivate parziali sono

$\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'equazione (iii) è semplicemente il vincolo originario. L'equazione (i) implica λ = −y o x = 0. Se x = 0 allora dobbiamo avere $y = \pm \sqrt{3}$ per la (iii) e dalla (ii) otteniamo che λ=0. Se invece λ = −y, sostituendo nell'equazione (ii) abbiamo che,

$x^2 - 2y^2 = 0. \,$

Quindi x² = 2y². Sostituendo nell'equazione (iii) e risolvendo rispetto a y si ottiene per y il valore seguente:

$y = \pm 1. \,$

Chiaramente ci sono sei punti critici:

$(\sqrt{2},1); \quad (-\sqrt{2},1); \quad (\sqrt{2},-1); \quad (-\sqrt{2},-1); \quad (0,\sqrt{3}); \quad (0,-\sqrt{3}).$

Valutando la funzione studiata in questi punti, troviamo

$f(\pm\sqrt{2},1) = 2; \quad f(\pm\sqrt{2},-1) = -2; \quad f(0,\pm \sqrt{3})=0.$

Perciò, la funzione studiata raggiunge il suo massimo nei punti

$(\sqrt{2},1) \quad\text{e}\quad (-\sqrt{2},1),$

e il suo minimo minimo nei punti

$(\sqrt{2},-1) \quad\text{e}\quad (-\sqrt{2},-1),$

I punti $(0,\pm\sqrt{3})$ sono punti di sella.

Esempio: entropia

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

$f(p_1,p_2,\ldots,p_n) = -\sum_{k=1}^n p_k\log_2 p_k.$

Chiaramente, la somma di queste probabilità fa 1, quindi il nostro vincolo è g(p) = 1 con

$g(p_1,p_2,\ldots,p_n)=\sum_{k=1}^n p_k.$

Possiamo usare i moltiplicatori di Lagrange per trovare il punto di massima entropia (dipendente dalle probabilità). Per tutti i k da 1 a n, richiediamo che

$\frac{\partial}{\partial p_k}(f+\lambda (g-1))=0,$

da cui si ottiene

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

Procedendo con la derivazione di queste n equazioni, otteniamo

$-\left(\frac{1}{\ln 2}+\log_2 p_k \right) + \lambda = 0.$

Questo dimostra che tutti i p_i sono uguali (perché dipendono da λ soltanto). Utilizzando il vincolo ∑_k p_k = 1, troviamo

$p_k = \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 budget. Il moltiplicatore di Lagrange ha una interpretazione economica come shadow price associato al vincolo, in questo caso l'utilità marginale del capitale. .

Applicazione del metodo per funzioni con 2 variabili ed un vincolo di eguaglianza

1) Scrivere la funzione lagrangiana $\mathcal{L}$.

Lo studio del lagrangiano non fornisce informazioni sul vincolo g(x,y). È invece fondamentale per studiare la funzione definita su un insieme aperto: i punti critici della funzione lagrangiana sono anche punti critici per la funzione iniziale f(x,y) che si intende studiare. In altre parole, se un punto (x₀,y₀) è di massimo/minimo/sella per la funzione lagrangiana, esso è un punto di massimo/minimo/sella anche per la funzione f(x,y).

2) Calcolare il gradiente della funzione $\mathcal{L}$ (non f(x,y)).

3) Definire un sistema formato dalle equazioni del gradiente poste uguali a 0 e $\lambda \ne \; 0$

$\begin{cases} \frac{\delta \mathcal{L}}{\delta x} =0\\ \frac{\delta \mathcal{L}}{\delta y} =0\\ \frac{\delta \mathcal{L}}{\delta \lambda} =0\\ \lambda \ne \; 0 \end{cases}$

La soluzione del sistema fornisce le coordinate dei punti critici. Un punto critico è un punto nel quale si annullano le derivate prime e può essere un massimo, un minimo o un punto di sella.

4) Si calcolano le derivate seconde e dunque il carattere della matrice hessiana orlata dal vincolo H(f) calcolata per le variabili x e y orlata delle derivate prime del vincolo per ognuno dei punti critici..

$H_f(x_0,y_0) = \begin{bmatrix} 0 & \frac{\partial g}{\partial x} & \frac{\partial g}{\partial y}\\ \frac{\partial g}{\partial x} & \frac{\partial^2 \mathcal{L}}{\partial xx} & \frac{\partial^2 \mathcal{L}}{\partial xy}\\ \frac{\partial g}{\partial y} & \frac{\partial^2 \mathcal{L}}{\partial yx} & \frac{\partial^2 \mathcal{L}}{\partial yy}\\ \end{bmatrix}$

Se la matrice orlata calcolata nel punto è:

• Definita Positiva → il punto è un minimo
• Definita Negativa → il punto è un massimo
• Semidefinita Positiva → il punto potrebbe essere un minimo
• Semidefinita Negativa → il punto potrebbe essere un massimo
• Indefinita → il punto è un punto di sella

per determinare il carattere della matrice orlata si calcola il segno dei determinanti degli ultimi m - n minori principali della diagonale di nord ovest. dove m è il numero di variabili della funzione di partenza e n il numero dei vincoli ai quali è soggetta lo studio.

• Qualora tutti i determinanti abbiano segno positivo la matrice è definita positiva.
• Qualora i determinati abbiano segno uguale a ( − 1)^k dove k è il rango del minore principale in considerazione allora è definita negativa.
• Qualora, ponendoci nei casi precendeti almeno un determinante risulta pari a zero allora la matrice è rispettivamente semidefinita positiva o negativa
• Negli altri casi è indefinita

In presenza di disequazioni

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

• In caso di massimizzazione porre il vincolo nella forma normale $g\left(x,y,z,...\right)\le 0$
• In caso di minimizzazione porre il vincolo nella forma normale $g\left(x,y,z,...\right)\ge 0$
• Il sistema da risolvere si trasforma in

$\frac{\partial \mathcal{L}}{\partial x} =0 \quad \frac{\partial \mathcal{L}}{\partial y} =0 \quad \frac{\partial \mathcal{L}}{\partial \lambda} =0 \quad \lambda \ge 0$

• Procedere con il calcolo del carattere della matrice hessiana orlata.

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
• Applet
• Tutorial and applet
• Video Lecture of Lagrange Multipliers
• MIT Video Lecture on Lagrange Multipliers
• Slides accompanying Bertsekas's nonlinear optimization text, with details on Lagrange multipliers (lectures 11 and 12)
• http://eom.springer.de/L/l057190.htm

Portale Fisica

Portale Matematica