Metodo dei moltiplicatori di Lagrange

(Reindirizzamento da Moltiplicatori di Lagrange)

In analisi matematica e programmazione matematica, il metodo dei moltiplicatori di Lagrange permette di ridurre i punti stazionari di una funzione in variabili e vincoli di frontiera , detta obiettivo, a quelli di una terza funzione in variabili non vincolata, detta lagrangiana:

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.

,

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   soggetta al vincolo:

 

ove   è una costante. Si possono visualizzare le curve di livello[2] della   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   (senza attraversamento), 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   che includono i massimi e minimi locali, assumendo che   sia differenziabile. Nelle equazioni questo succede quando il gradiente della   è 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  ; 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, minimi e punti di sellaModifica

Le soluzioni sono punti stazionari della lagrangiana   e possono essere anche punti di sella, ovvero né massimi né minimi di   o  .   è illimitata: dato un punto   che non giace sul vincolo, facendo il limite per   si rende   arbitrariamente grande o piccola.

Spiegazione analiticaModifica

Sia l'obiettivo   una funzione definita su  , e siano i vincoli dati da   (ottenuti da un'equazione del tipo   con  ). Si definisca la lagrangiana,  , come:

 

Sia il criterio di ottimizzazione sia i vincoli   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:

 

  è 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,   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  : 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   diventa  ). Sostituendo nella   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   da   a  , si impongono le equazioni:

 

Procedendo con la derivazione si ottiene, oltre all'equazione del vincolo originario:

 

Questo dimostra che tutti i   sono uguali perché dipendono soltanto da un parametro comune. Introducendola nell'equazione vincolare, ovvero imponendo

 

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