Metodo dei moltiplicatori di Lagrange

Da Wikipedia, l'enciclopedia libera.
Se riscontri problemi nella visualizzazione dei caratteri, clicca qui.
Figura 1: Ricerca dei massimi di f(x,y) dato il vincolo (rappresentato in rosso) g(x,y)=0.
Figura 2: Rappresentazione mediante curve di livello del problema della figura 1. La linea rossa evidenzia il vincolo g(x,y)=0. 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.

Nella programmazione matematica, quello dei moltiplicatori di Lagrange è un metodo che riduce i punti stazionari di una funzione detta obiettivo in I variabili e J vincoli di frontiera \vec g(\vec x)= \vec 0, a quelli di una terza funzione in I+K variabili non vincolata detta lagrangiana:

 \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 cioè tante nuove variabili scalari λ quanti sono i vincoli che vengono dette appunto moltiplicatori.

Se \vec x^* è stazionario (per esempio un massimo) per il problema vincolato originario, allora esiste un \vec \lambda^* tale che (\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 cioè ad 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[modifica | modifica sorgente]

Consideriamo il caso bidimensionale. Supponiamo di avere un obiettivo, f(x,y) da massimizzare soggetto al vincolo:

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

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

Supponiamo di camminare lungo la curva di livello con  g = 0 . In generale le curve di livello della  f e della  g possono essere distinte, quindi la curva di livello per  g = 0 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 = 0 il valore della f potrebbe variare. Solo quando la curva di livello per  g = 0 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: d f_\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 \nabla f è una combinazione lineare dei \nabla 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 il sistema di equazioni:

 \frac {\partial}{\partial x }\left[f \left(x, y \right) + \lambda g \left(x, y \right) \right] = 0
 \frac {\partial}{\partial y}\left[f \left(x, y \right) + \lambda g \left(x, y \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 lagrangiana

 \Lambda \left( x , y \right) = f \left( x , y \right) + \lambda  g \left( x , y \right)

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

Attenzione: differenze tra massimi e minimi e punti stazionari[modifica | modifica sorgente]

Bisogna essere consapevoli del fatto che le soluzioni sono punti stazionari della lagrangiana \Lambda, e questi possono essere anche punti di sella: questi non sono 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[modifica | modifica sorgente]

Sia l'obiettivo f una funzione definita su Rn, e siano i vincoli dati da gj(x) = 0 (ottenuti da un'equazione del tipo hj(x) = cj con gj(x) = hj(x) - cj). Ora si definisca la lagrangiana, Λ, come

\Lambda(\mathbf x, \boldsymbol \lambda) = f + \sum_j \lambda_j g_j.

Si osservi che sia il criterio di ottimizzazione sia i vincoli gj 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 \vec g = \vec 0.

Perciò è assolutamente inutile eseguire queste derivate all'atto pratico (se non al limite al fine di verifica dell'esattezza della lagrangiana). 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_j}} = \lambda_j.

Dunque, λj è 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[modifica | modifica sorgente]

Esempio semplicissimo[modifica | modifica sorgente]

Figura 3. Illustrazione del problema di ottimizzazione vincolata.

Supponiamo di voler massimizzare x+y sotto il 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, se poniamo 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 otteniamo 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}

La derivata rispetto al moltiplicatore è come sempre il vincolo originario: risulta come già detto inutile e anzi ritardante per la soluzione il suo calcolo.

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

N.B. 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 semplice[modifica | modifica sorgente]

Supponiamo di voler trovare i valori di massimo per la funzione complessa:

 x^2 y \,

con l'unica condizione che giaccia sull'iperbole equilatera con fuochi sulle ascisse distanti 2√6, per cui la funzione di vincolo è rappresentata da:

 x^2 - y^2 - 3=0\,

Useremo perciò un solo moltiplicatore λ. Annullando il gradiente della lagrangiana risultano oltre all'equazione vincolare:

\begin{align}
2 x y + 2 \lambda x &&= 0, \qquad \text{(i)} \\
x^2 - 2 \lambda y   &&= 0, \qquad \text{(ii)} \\
\end{align}

La (i) implica λ = −y oppure x=0. Se x=0 allora per la vincolare dobbiamo avere il numero immaginario y = \pm \sqrt{3} i e dalla (ii) otteniamo che λ=0. Se invece λ = −y, sostituendo nella (ii) abbiamo che,

x^2 + 2y^2 = 0. \,

Quindi x² = - 2y². Sostituendo nella vincolare e risolvendo rispetto a y si ottiene per y il valore seguente:

y = \pm i. \,

Chiaramente ci sono sei punti critici:

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

Valutando l'obiettivo in questi punti, troviamo

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

Perciò, l'obiettivo raggiunge il suo massimo nei punti

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

e il suo minimo nei punti

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

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

Esempio: entropia[modifica | modifica sorgente]

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.

Chiaramente il nostro 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, imponiamo perciò le equazioni:

\frac{\partial}{\partial p_n}(-\sum_{n=1}^N p_n\log_2 p_n + \lambda \sum_{n=1}^N p_n - \lambda)=0

Procedendo con la derivazione otteniamo oltre all'equazione del vincolo originario:

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

Questo dimostra che tutti i pn sono uguali (perché dipendono soltanto da un parametro comune). Introducendola nell'equazione vincolare (quella che mancava per il set delle derivate) otteniamo infine:

p_n = \frac{1}{N}.

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

Economia[modifica | modifica sorgente]

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 costo. Il moltiplicatore di Lagrange ha una interpretazione economica come shadow price[4] associato al vincolo, in questo caso l'utilità marginale[5][6] del capitale.[7].

Vincoli monolateri[modifica | modifica sorgente]

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)\le 0
  • In caso di minimizzazione porre il vincolo nella forma normale g_j(\mathbf x)\ge 0
  • Il sistema da risolvere si trasforma in

\nabla_{\mathbf x} \Lambda=0 \quad
\nabla_{\mathbf \lambda} \Lambda=0 \quad
\lambda_j \ge 0_j
  • Procedere con il calcolo del carattere della matrice hessiana orlata.

Note[modifica | modifica sorgente]

  1. ^ (EN) I.B. Vapnyarskii, Lagrange multipliers in Encyclopaedia of Mathematics, Springer e European Mathematical Society, 2002. .
  2. ^ 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.
  3. ^ Alfred Marshall. 1920. Principles of Economics. An introductory Volume. 8th edition. London: Macmillan.
  4. ^ Shadow Price: Definition and Much More from Answers.com
  5. ^ Stigler, George Joseph; “The Development of Utility Theory”, I and II, Journal of Political Economy (1950), issues 3 and 4.
  6. ^ Stigler, George Joseph; “The Adoption of Marginal Utility Theory” History of Political Economy (1972).
  7. ^ 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.

Collegamenti esterni[modifica | modifica sorgente]

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