Lagrange Multiplier Demystified

Have you ever wondered why we use the Lagrange multiplier to solve constrained optimization problems?

Is it just a clever technique?

Poiché è molto facile da usare, lo impariamo come un’aritmetica di base praticandola fino a quando non possiamo farlo a memoria.

Ma vi siete mai chiesti perché funziona? Funziona sempre? Se no, perché no?

Se vuoi conoscere le risposte a queste domande, sei nel posto giusto.

Lo demistificherò per te.

Un esempio di problema di ottimizzazione vincolata

Nel caso in cui non si abbia familiarità con le ottimizzazioni vincolate, ho scritto un articolo che lo spiega. In caso contrario, si prega di leggere.

Supponiamo di avere una montagna che assomiglia al di sotto:

The height of a location (x, y) is given as follows (in kilometers):

Further suppose, the mountain has an eruption:

From the top, it looks like below:

The eruption area is given as follows:

Questo significa che il bordo dell’eruzione è determinato come segue:

Così, l’orlo simile a questo.

Supponiamo di voler conoscere la posizione più alta dell’eruzione su questa montagna.

Questo significa che la posizione più alta deve essere sul bordo linea dell’eruzione che si può esprimere come segue:

posizione (x, y) che soddisfa g(x, y)=0 è sul bordo dell’eruzione.

Pertanto, il problema di ottimizzazione vincolata consiste nel trovare il massimof(x, y) soddisfacenteg(x, y) = 0.

Intuizione su come risolvere il problema di ottimizzazione vincolata

Intuitivamente, sappiamo che l’altezza massima dell’eruzione è intorno a dove indica la freccia blu.

Siamo alla ricerca di alta linea di contorno che tocca il bordo della eruzione.

Definiamo l’equazione della linea di contorno:

f(x, y) = H

H è un valore costante che indica l’altezza del contorno.

Per un dato valore di H, esiste un insieme di (x, y) valori che soddisfano f(x, y) = H.

Il gradiente dif(x, y) indica la direzione in cui l’altezza aumenta che è perpendicolare alla linea di contorno.

The gradient is a vector of partial derivatives.

Similarly, the gradient of g(x, y) is perpendicular to the edge of the eruption area.

La più alta linea di contorno che tocca il bordo della eruzione deve avere il gradiente di f(x, y) in parallelo alla pendenza g(x, y).

Se la pendenza della linea di contorno non è in parallelo con il gradiente dell’eruzione bordo, ci sarà qualche eruzione area che si trova più in alto rispetto alla linea di contorno.

Così, abbiamo bisogno di trovare il punto (x, y) dove la pendenza del f(x, y) è in parallelo alla pendenza g(x, y).

Il moltiplicatore di Lagrange e la lagrangiana

Mettiamo il nostro obiettivo in una formula matematica.

Il gradiente di f(x, y) e il gradiente di g(x, y) dovrebbero essere in parallelo ma potrebbero avere dimensioni e direzione diverse.

grad f(x, y) = λ grad g(x, y)

Questoλ è chiamato moltiplicatore di Lagrange dal nome del matematico che introdusse la meccanica lagrangiana nel 1788.

In questa fase, non sappiamo il valore di λ che potrebbe essere qualcosa come 2.5, -1, o altro. Significa solo il fatto che i due gradienti devono essere paralleli.

Possiamo riorganizzare l’equazione come segue:

grad { f(x, y) - λ g(x, y) } = 0

Lo zero qui indica il vettore con zeri:(0,0).

E chiamiamo l’interno delle parentesi graffe come la lagrangianaL.

L = f(x, y) - λ g(x, y)

Quindi, stiamo dicendo che la seguente è la condizione richiesta.

grad L = 0

Il gradiente della Lagrangiana ci dà due equazioni.

Ma ci sono tre incognite xy e λ. Come possiamo risolvere queste equazioni?

In realtà, abbiamo un’altra equazione che èg(x, y) = 0.

Quindi, possiamo risolvere le tre equazioni per trovare la posizione più alta(x, y) che soddisfa il vincolo.

Il problema ora diventa un esercizio aritmetico.

La risposta è f(x, y) = 2 where x = 1 and y = 1.

È possibile verificare i valori con le equazioni.

Inoltre, λ = -4/5 il che significa che questi gradienti sono nelle direzioni opposte come previsto.

Tutto sommato, il moltiplicatore di Lagrange è utile per risolvere i problemi di ottimizzazione dei vincoli.

Troviamo il punto(x, y) dove il gradiente della funzione che stiamo ottimizzando e il gradiente della funzione di vincolo è in parallelo utilizzando il moltiplicatoreλ.

In sintesi, abbiamo seguito i passaggi seguenti:

• Identificare la funzione da ottimizzare (massimizzare o minimizzare): f(x, y)
• Identificare la funzione per il vincolo: g(x, y) = 0
• Definisci la lagrangianaL = f(x, y) - λ g(x, y)
• Risolvigrad L = 0 soddisfacendo il vincolo

È meccanico come sopra e ora sai perché funziona.

Ma ci sono alcune altre cose da menzionare.

Quando non funziona

Ho fatto alcune ipotesi mentre spiegavo il moltiplicatore di Lagrange.

Prima di tutto, ho assunto che tutte le funzioni abbiano gradienti (le prime derivate), il che significa che le funzionif(x, y) eg(x, y) sono continue e lisce.

In secondo luogo, presumo anche chef(x, y) abbia le seconde derivate in modo da poter verificare se la soluzione(x, y) è effettivamente il massimo o meno.

Queste due ipotesi sono vere in questo esempio, ma nei problemi reali è necessario verificare che sia possibile utilizzare il moltiplicatore di Lagrange per risolvere il problema di ottimizzazione dei vincoli.

In terzo luogo, ho semplificato la domanda in modo che abbiamo solo bisogno di affrontare un massimo.

In altre parole, la forma della montagna è definita in modo tale che esiste una sola soluzione al problema di ottimizzazione vincolata.

Nei problemi reali, la montagna potrebbe avere forme più complicate con più picchi e valli.

In questo caso, abbiamo bisogno di affrontare il problema di ottimizzazione globale (cioè, più locale maxima).

Invece, l’esempio in questo articolo riguarda solo un massimo locale che è anche il massimo globale.

Spero che la tua comprensione del moltiplicatore di Lagrange sia ottimale ora.