Metodo dei moltiplicatori di Lagrange

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.

In analisi matematica e programmazione matematica, il metodo dei moltiplicatori di Lagrange 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 tante nuove variabili scalari λ, dette moltiplicatori, quanti sono i vincoli .

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

IntroduzioneModifica

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

 

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

 

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

Si supponga di camminare lungo la curva di livello con  . In generale le curve di livello della   e della   sono distinte, quindi la curva di livello per   può intersecare le curve di livello della  . Questo equivale a dire che mentre ci si muove lungo la curva di livello per   il valore della   può variare. Solo quando la curva di livello per   è tangente a una delle curve di livello della   in modo tangente, il valore di   non aumenta né diminuisce.

Questo succede esattamente nei punti in cui 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. Nelle equazioni questo succede quando il gradiente della f è perpendicolare al vincolo, o ai vincoli, ovvero quando   è una combinazione lineare dei  .

Un esempio familiare è quello delle curve di livello per temperatura e pressione delle mappe meteorologiche: i massimi e minimi vincolati capitano dove le mappe sovrapposte mostrano linee tangenti (isoplete).

Geometricamente la condizione di tangenza si traduce 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 lo scalare incognito λ, si deve risolvere il sistema di equazioni:

 
 

per λ ≠ 0; avendo assunto, senza perdita di generalità,  .

Una volta che i valori per λ siano stati determinati, si torna al numero originario di variabili e si possono trovare i punti stazionari della lagrangiana

 

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

Differenze tra massimi e minimi e punti stazionariModifica

Le soluzioni sono punti stazionari della lagrangiana   e possono essere anche punti di sella, ovvero 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 analiticaModifica

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). Si definisca la lagrangiana, Λ, come

 

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

 

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

 

λ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, 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.

EsempiModifica

Esempio 1Modifica

 
Figura 3. Illustrazione del problema di ottimizzazione vincolata.

Si voglia massimizzare   col 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, ponendo  , e

 

Annullando il gradiente si ottiene il sistema di equazioni:

 

La derivata rispetto al moltiplicatore è come sempre il vincolo originario.

Combinando le prime due equazioni si ottiene:

 

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

 

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

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

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

 

Il vincolo è che le configurazioni   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, si impongono le equazioni:

 

Procedendo con la derivazione si ottiene, 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[non chiaro] si ottiene:

 

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

EconomiaModifica

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

Vincoli monolateriModifica

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
 
  • Si procede con il calcolo del carattere della matrice hessiana orlata.

NoteModifica

  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.

Altri progettiModifica

Collegamenti esterniModifica

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