In analisi matematica e programmazione matematica, il metodo dei moltiplicatori di Lagrange permette di ottenere i punti stazionari di una funzione in variabili e vincoli di frontiera , detta obiettivo, tramite una terza funzione in 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..
Introduzione Si consideri il caso bidimensionale. Si vuole massimizzare una soggetta al vincolo:
ove è una costante. Si possono visualizzare le curve di livelloCourant, Richard, Herbert Robbins, and Ian Stewart. What Is Mathematics?: An Elementary Approach to Ideas and Methods. New York: Oxford University Press, 1996. p. 344. 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. Nelle equazioni questo succede quando il gradiente della è perpendicolare al vincolo (o ai vincoli) ovvero quando è una combinazione lineare dei .
Introducendo lo scalare incognito , si deve dunque risolvere il sistema di equazioni:
Differenze tra massimi, minimi e punti di sella Le soluzioni sono punti stazionari della lagrangiana e possono essere anche punti di sella, ossia né massimi né minimi di o .
La funzione è illimitata: dato un punto che non giace sul vincolo, facendo il limite per si rende arbitrariamente grande o piccola.
Spiegazione analitica 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:
Il valore di è interpretabile come 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.
Esempi Esempio 1
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 è 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: entropia 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, ossia imponendo
si ottiene:
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àAlfred Marshall. 1920. Principles of Economics. An introductory Volume. 8th edition. London: Macmillan. soggetta a un vincolo di bilancio. Il moltiplicatore di Lagrange ha un'interpretazione economica come prezzo ombra (shadow price) associato al vincolo, in questo caso l'utilità marginaleStigler, George Joseph; “The Development of Utility Theory”, I and II, Journal of Political Economy (1950), issues 3 and 4.Stigler, George Joseph; “The Adoption of Marginal Utility Theory” History of Political Economy (1972). del capitale.• 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..
Vincoli monolateri 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.
Note
Altri progetti
Collegamenti esterni Conceptual introduction (plus a brief discussion of Lagrange multipliers in the calculus of variations as used in physics)
Slides accompanying Bertsekas's nonlinear optimization text, with details on Lagrange multipliers (lectures 11 and 12) http://eom.springer.de/L/l057190.htm
Categoria:Calcolo a più variabili Categoria:Ottimizzazione