Lagranges metode

For å minimere/maksimere \(f(\mathbf{x})\) gitt \(g_j(\mathbf{x}) = b_j\), \(j=1,\ldots,m\), setter vi opp Lagrangefunksjonen \(\mathcal{L}(\mathbf{x},\boldsymbol{\lambda}) = f(\mathbf{x}) - \sum_j\lambda_j(g_j(\mathbf{x})-b_j)\). Førsteordensbetingelsene (FOB) er \(\nabla_x\mathcal{L} = \mathbf{0}\) pluss at bibetingelsene er oppfylt: \(g_j(\mathbf{x}) = b_j\). Dette gir \(n+m\) likninger for \(n+m\) ukjente (\(x_1,\ldots,x_n,\lambda_1,\ldots,\lambda_m\)).

Typisk eksamenoppsett

H2024, Problem 3: minimer \(F(x,y,z) = 3x^2+4y^2-xy+5z^2\) gitt \(x+y+z=6\) og \(x-z=2\). To likhetsbibetingelser, to multiplikatorer \(\lambda_1, \lambda_2\). FOB: \(6x-y=\lambda_1+\lambda_2\), \(8y-x=\lambda_1\), \(10z=\lambda_1-\lambda_2\). Oppgaven gir deg kandidatpunktet \((3,2,1)\) og ber deg (i) verifisere at FOB er oppfylt, (ii) beregne multiplikatorene, og (iii) vise at punktet er et globalt minimum.

Verifisering av optimalitet

Forstordensbetingelsene gir kandidatpunkter, ikke bevis på optimalitet. For å bevise optimalitet brukes konveksitet: hvis \(f\) er konveks (for minimering) eller konkav (for maksimering) og bibetingelsesmengden er konveks, er ethvert kandidatpunkt et globalt optimum. Konveksitetssjekken er typisk en del av selve oppgaven (se seksjonen om konveksitet).

Envelop-teoremet (skyggepris)

Lagrange-multiplikatoren \(\lambda_j\) angir skyggeprisen: \(\partial V^*/\partial b_j = \lambda_j\), der \(V^*\) er optimalverdien som funksjon av \(b_j\). Dette brukes til approksimasjon: hvis \(b_j\) endres fra \(b_j^0\) til \(b_j^0+\varepsilon\), er \(\Delta V^* \approx \lambda_j\varepsilon\). H2024, Problem 3c ber om approksimasjon der \(x-z=2\) erstattes av \(x-z=2+1/100\): svaret er \(\Delta V^* \approx \lambda_2/100\). Merk at H2024(c)(ii) er subtilt: bibetingelsen \(x-z=2+(y/100)\) avhenger av \(y\), og da er envelop-teoremet for parametere ikke direkte anvendbart — du må bruke den direkte differensieringstilnærmingen.

Eksempel (Lagrange med to bibetingelser)

Minimer \(F(x,y,z) = 2x^2 + 3y^2 + z^2\) gitt \(x+y+z=5\) og \(x-y=1\). Sett opp og løs Lagrangebetingelsene.

\(\mathcal{L} = 2x^2+3y^2+z^2 - \lambda_1(x+y+z-5) - \lambda_2(x-y-1)\)

FOB: \(4x = \lambda_1+\lambda_2\), \(6y = \lambda_1-\lambda_2\), \(2z = \lambda_1\)

Bibetingelser: \(x+y+z=5\), \(x-y=1\)

5 likninger, 5 ukjente — løs systematisk

Studieguide: Constrained Optimization: Lagrange Conditions

Studieguide: Constrained Optimization: Lagrange Conditions