Se riscontri problemi nella visualizzazione dei caratteri, clicca qui

Metodo dei moltiplicatori di Lagrange

Da Wikipedia, l'enciclopedia libera.
Ricerca dei massimi di dato il vincolo (rappresentato in rosso) .
Rappresentazione mediante curve di livello del problema. Le linee blu rappresentano curve di livello di . La soluzione al problema è data dai punti di tangenza tra la linea rossa e le linee blu.

Nell'analisi matematica e nella programmazione matematica, il metodo dei moltiplicatori di Lagrange ci permette di ridurre i punti stazionari di una funzione in I variabili e J vincoli di frontiera , detta obiettivo, a quelli di una terza funzione in I+J variabili non vincolata, detta lagrangiana:

,

introducendo cioè tante nuove variabili scalari λ quanti sono i vincoli che vengono dette appunto moltiplicatori.

Se è stazionario (per esempio un massimo) per il problema vincolato originario, allora esiste un tale che è 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 wikitesto]

Consideriamo il caso bidimensionale. Supponiamo di voler massimizzare una certa f(x,y); questa è però soggetta al vincolo:

ove c è una costante. Possiamo visualizzare le curve di livello[2] della f date da

per vari valori di , e le curve di livello della date da .

Supponiamo di camminare lungo la curva di livello con . In generale le curve di livello della e della possono essere distinte, quindi la curva di livello per potrebbe passare attraverso le curve di livello della . Questo equivale a dire che mentre ci si muove lungo la curva di livello per il valore della potrebbe variare. Solo quando la curva di livello per tocca le curve di livello della in modo tangente, il valore della 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: , 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 è una combinazione lineare dei .

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 e della 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 (assumendo, senza perdere in generalità, ):

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

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

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

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 si rende arbitrariamente grande o piccola.

Spiegazione analitica[modifica | modifica wikitesto]

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

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

nei gradienti delle funzioni originarie, e

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:

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 wikitesto]

Esempio semplicissimo[modifica | modifica wikitesto]

Figura 3. Illustrazione del problema di ottimizzazione vincolata.

Supponiamo di voler massimizzare sotto il vincolo . 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 (e il minimo viene raggiunto in )

Analiticamente, se poniamo , e

Annullando il gradiente otteniamo il sistema di equazioni:

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:

,

cioè ( altrimenti la (i) diventa 1 = 0). Sostituendo nella (iii) si ottiene , cosicché e i punti stazionari sono e . Valutando l'obiettivo x+y su questi si ottiene

dunque il massimo è , raggiunto nel punto , e il minimo è , raggiunto nel punto .

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 wikitesto]

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

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

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

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

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

Chiaramente ci sono sei punti critici:

Valutando l'obiettivo in questi punti, troviamo

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

e il suo minimo nei punti

I punti sono punti di sella.

Esempio: entropia[modifica | modifica wikitesto]

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

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:

Per tutti gli n da 1 a N, imponiamo perciò le equazioni:

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

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:

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

Economia[modifica | modifica wikitesto]

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 prezzo-ombra (shadow price)[4] associato al vincolo, in questo caso l'utilità marginale[5][6] del capitale.[7].

Vincoli monolateri[modifica | modifica wikitesto]

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

  • In caso di massimizzazione porre il vincolo nella forma normale
  • In caso di minimizzazione porre il vincolo nella forma normale
  • Il sistema da risolvere si trasforma in
  • Procedere con il calcolo del carattere della matrice hessiana orlata.

Note[modifica | modifica wikitesto]

  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 wikitesto]

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