Skip to main content

Uke 12 – optimering med likhetsbetingelser og Lagranges metode

Når svaret må ligge på en kurve

I uke 8 lå minimum av en kvadratsum på randen av et rektangel. Der var gradienten ikke null: funksjonen ville gjerne bli mindre, men kravet stoppet den.

  • Uke 11: I uke 11 var kravene lineære ulikheter, og løsningen lå i et hjørne.
  • Denne uken: Nå skal et punkt oppfylle en likning, for eksempel \(x^2+4y^2=1\). Da er bare punktene på selve kurven tillatt.
  • Navnet på kravet: Et slikt krav kalles en likhetsbetingelse eller bibetingelse; vi sier ofte bare krav.

Ukens spørsmål er: Hva erstatter \(\nabla f=0\) når punktet må ligge på en kurve, og hvordan vet vi at kandidaten vi finner, er den beste? Vi bygger svaret i tre steg, ett om gangen:

  1. Hva må gjelde i et beste punkt på kurven? Nivålinjen til målet berører kurven, og gradienten står vinkelrett på den. Det gir Lagranges likninger, som er nye i kurset. Multiplikatoren i dem viser seg å være en pris, som i uke 11 (12.1–12.3).
  2. Hva blir likningene når målet er kvadratisk? Med et sirkelkrav blir de et egenverdiproblem, og med lineære krav et lineært likningssett (12.4).
  3. Hvordan kontrollerer vi et punkt som en løser gir oss? Løseren SLSQP finner et punkt, og vi kontrollerer det med to kontrollfeil og et globalt argument (12.5).

Forelesning viser hovedløpet. Gå i dybden-boksene gir begrunnelser, spesialtilfeller og ulikhetskrav. Regneoppgavene står i 12.6 og kodeoppgavene i 12.7.

Kort løype

Hva må gjelde i et beste punkt?

  1. Nivålinjen berører kurven: en applet som i uke 4, nå med en ellipse.
  2. Lagranges likninger: to normaler som er parallelle.
  3. Multiplikatoren er en pris: samme idé som i uke 11.
  4. Kandidater er ikke løsninger: fire kandidater, men bare to verdier.

Hva blir likningene når målet er kvadratisk?

  1. Kandidattabellen er en egenverditabell: uke 5 og 7.
  2. Lineære krav gir et lineært system: uke 3, 6 og 10.

Hvordan kontrollerer vi et numerisk svar?

  1. Finn et punkt numerisk og kontroller det: SLSQP.

Dette bygger vi videre på

Fra tidligere uker Spørsmålet vi tar med oss
Uke 3: nullrom Hvilke retninger endrer ikke \(Cz\)?
Uke 4: komponent langs en retning Hvilken enhetsretning gir størst komponent?
Uke 5: Rayleigh-kvotienten Hva er størst mulig \(z^TAz\) når \(\lVert z\rVert_2=1\)?
Uke 6: CG og uke 10: Cholesky Hva krever metodene av matrisen?
Uke 7: største strekk og pseudoinvers Hvorfor er \(\sigma_1\) det største strekket?
Uke 8: kompakthet Finnes et maksimum på en kurve?
Uke 11: hva en ekstra enhet er verdt Hva er én enhet mer av en ressurs verdt?

Læringsmål

Etter denne uken skal du kunne

  • finne tangent og normal til en regulær likhetsbetingelse i et punkt,
  • sette opp og løse Lagranges likninger for én likhetsbetingelse,
  • tolke \(-\lambda\) som endringen i optimal verdi per enhet vi flytter kravet,
  • skille kandidater fra løsninger ved å sammenligne verdier eller finne en global grense,
  • forklare hvorfor en kvadratisk form på enhetssirkelen gir et egenverdiproblem,
  • sette opp likningssettet for et kvadratisk mål med lineære krav, og forklare hvorfor matrisen ikke er SPD,
  • kontrollere både betingelsesfeil og stasjonaritetsfeil i et numerisk SLSQP-svar.

Hva skjer når sirkelen blir en ellipse?

I uke 4.1 dro du en enhetsvektor \(q\) rundt enhetssirkelen og leste av komponenten av \(x=(3,2)\) langs \(q\). Du fant at komponenten, \(3q_1+2q_2\), blir størst når \(q\) peker samme vei som \(x\). Det var et optimeringsproblem på enhetssirkelen.

Her bruker vi vektoren \((1,2)\), som gir enklere tall. Komponenten av \((1,2)\) langs \(q=(x,y)\) er \(x+2y\), og etter regelen fra uke 4 er

\[\text{maksimum av } f(x,y)=x+2y \quad\text{når}\quad x^2+y^2=1\]

nådd i \((1,2)/\sqrt5\). Nå bytter vi ut sirkelen med ellipsen \(x^2+4y^2=1\). Målet er det samme.

Appleten gjør regningen for oss: den viser målverdien, to gradientpiler og en tangentpil i punktet du velger. Hvorfor akkurat gradientpilene er interessante, forklarer vi rett etter forsøket.

Hensikten er å finne det beste punktet på ellipsen og se hva som kjennetegner det, nå som regelen fra uke 4 ikke lenger gjelder.

Eksperiment 1 – fra sirkel til ellipse

Rolle Uttrykk Hva det betyr
Valg \(z=(x,y)\) Punktet vi flytter på.
Mål Maksimer \(f(x,y)=x+2y\) Skalarproduktet \((1,2)\cdot z\), som komponenten i uke 4.
Krav \(h(x,y)=x^2+4y^2-1=0\) Bare punkter på ellipsen er tillatt.

Dra punktet \(z\) langs ellipsen. Slik leser du figuren:

  • Stiplet brun linje: Nivålinjen \(x+2y=f(z)\) inneholder alle punkter med samme målverdi som \(z\).
  • Rød pil: Retningen til \(\nabla f=(1,2)\).
  • Grønn pil: Retningen til \(\nabla h=(2x,8y)\).
  • Grå pil: \(v\) er en enhetstangent til ellipsen. Tallet \(\nabla f\cdot v\) øverst i figuren sier hvor fort \(f\) endres når vi går langs ellipsen i pilens retning.
  • Grå sirkel og grått punkt: Svaret på sirkelen, etter regelen fra uke 4.

Prøv dette før du leser videre:

  1. Start i \(z=(1,0)\). I hvilken retning langs ellipsen må du gå for at \(f\) skal øke? Hva sier tallet \(\nabla f\cdot v\)?
  2. Trykk z langs (1, 2). Er dette fortsatt det beste punktet?
  3. Dra \(z\) til \(f\) blir størst mulig. Les av punktet, vinkelen og \(\nabla f\cdot v\).
  4. Hva gjør nivålinjen i det beste punktet?

Hva viser forsøket? Sammenlign målverdiene:

Punkt på ellipsen Målverdi
Punktet langs \((1,2)\) \(f\approx1.213\)
Beste punkt, \(z\approx(0.707,\,0.354)\) Omtrent \(1.414\)

Regelen fra uke 4, «pek langs vektoren», gjelder altså ikke lenger. Men tre ting gjelder fortsatt i det beste punktet:

  • tallet \(\nabla f\cdot v\) er null: det er positivt før punktet og negativt etter, så \(f\) slutter å vokse akkurat der;
  • nivålinjen berører ellipsen uten å krysse den;
  • den røde og den grønne pilen er parallelle: vinkelen er \(0^\circ\).

Et punkt der nivålinjen krysser kurven, kan ikke være best: på den ene siden av krysningen ligger tillatte punkter med høyere verdi. Resten av uken handler om denne observasjonen.

Tangent og normal

  • Tangentretning: Viser hvilken vei vi kan begynne å gå langs kurven fra et punkt.
  • Normalretning: Står vinkelrett på tangenten.
  • Gradienten som normal: Fra Matematikk 2 vet vi at gradienten står vinkelrett på nivåkurvene (gradienten selv møtte vi også i uke 6). Kurven \(h=0\) er en nivåkurve for \(h\), derfor er \(\nabla h\) en normal til kurven, så lenge \(\nabla h\ne0\).
  • Regulært krav: Når \(\nabla h\ne0\), kaller vi kravet regulært i punktet.

Regn for hånd. Vi undersøker punktet \((1,0)\) på ellipsen.

  1. \(\nabla h=(2x,8y)\), så \(\nabla h(1,0)=(2,0)\). Normalen peker langs \(x\)-aksen.
  2. En enhetstangent står vinkelrett på normalen: \(v=(0,1)\). Fra \((1,0)\) kan vi gå både oppover og nedover langs ellipsen.
  3. Målgradienten er \(\nabla f=(1,2)\). Den deriverte av \(f\) langs tangenten er \(\nabla f\cdot v=(1,2)\cdot(0,1)=2\).
  4. Fordi denne deriverte er positiv, øker \(f\) når vi begynner å gå oppover. Punktet \((1,0)\) er tillatt, men ikke et maksimum. Det stemmer med spørsmål 1 i appleten.

Appleten viser denne deriverte som tallet \(\nabla f\cdot v\). I det beste punktet er den null, og i 12.2 regner vi ut punktet eksakt.

Dette tar vi med oss.

  • Langs kurven: I et ekstremalpunkt må den deriverte av målet langs tangenten være null.
  • Normalene: Det er det samme som at \(\nabla f\) står vinkelrett på tangenten, altså er parallell med normalen \(\nabla h\).
  • Gradienten selv: Målgradienten trenger ikke være null, slik den må være i et indre ekstremum (se uke 8.3).

To parallelle normaler

At \(\nabla f\) og \(\nabla h\) er parallelle, betyr at den ene er et tall ganger den andre. Vi skriver det som

\[\nabla f+\lambda\nabla h=0.\]

  • Lagrangemultiplikator: Tallet \(\lambda\).
  • Lagrangefunksjonen: \(L(z,\lambda)=f(z)+\lambda h(z)\).

Et regulært lokalt ekstremum \(z_*\) må oppfylle begge Lagranges likninger:

\[\boxed{h(z_*)=0,\qquad \nabla f(z_*)+\lambda\nabla h(z_*)=0.}\]

  • Første likning: Punktet er tillatt.
  • Andre likning: Den deriverte langs tangenten er null.
  • Samlet fra \(L\): Begge får vi ved å sette alle partiellderiverte av \(L\) lik null, også den med hensyn på \(\lambda\).

Med to variabler er dette tre likninger med tre ukjente: \(x\), \(y\) og \(\lambda\).

  • Kandidat: Et punkt som oppfyller likningene, kalles stasjonært under bibetingelsen. Det er en kandidat, ikke automatisk et maksimum eller minimum.
  • Forutsetning: Regularitet, \(\nabla h(z_*)\ne0\), trengs fordi \(\nabla h\) ellers ikke er noen normal; se «Gå i dybden» nedenfor.

Ellipsen fra 12.1, steg for steg. La oss regne ut det appleten viste oss. Her er \(\nabla f=(1,2)\) og \(\nabla h=(2x,8y)\).

  1. Likningene er \(1+2\lambda x=0\), \(2+8\lambda y=0\) og \(x^2+4y^2=1\).
  2. Her er \(\lambda\ne0\), ellers sier den første likningen \(1=0\). Da er \(x=-\dfrac1{2\lambda}\) og \(y=-\dfrac2{8\lambda}=-\dfrac1{4\lambda}\), altså \(x=2y\).
  3. Sett \(x=2y\) inn i kravet: \((2y)^2+4y^2=8y^2=1\), så \(y=\pm\dfrac1{2\sqrt2}\) og \(x=2y=\pm\dfrac1{\sqrt2}\).
  4. Målverdiene er \(f=x+2y=\pm\Bigl(\dfrac1{\sqrt2}+\dfrac1{\sqrt2}\Bigr)=\pm\sqrt2\).
  5. Første likning gir \(\lambda=-\dfrac1{2x}=-\dfrac1{\sqrt2}\) i den positive kandidaten. Der er \(\nabla h=(\sqrt2,\,2\sqrt2)=\sqrt2\,(1,2)\), parallell med \(\nabla f\), slik appleten viste.

Den positive kandidaten er punktet appleten pekte ut, med \(f=\sqrt2\approx1.414\).

NoteHåndeksempel: sirkelen og regelen fra uke 4

Utgangspunkt. Maksimer \(f(x,y)=x+2y\) når \(h(x,y)=x^2+y^2-1=0\).

Prøv selv. Skriv opp de tre likningene og finn alle kandidatene. Hvilken gir størst verdi?

Regnegangen.

  1. Likningene er \(1+2\lambda x=0\), \(2+2\lambda y=0\) og \(x^2+y^2=1\). Her er \(\lambda\ne0\), ellers gir den første \(1=0\).
  2. Da er \(x=-1/(2\lambda)\) og \(y=-1/\lambda\), så \(y=2x\).
  3. Kravet gir \(x^2+(2x)^2=5x^2=1\). Kandidatene er \(\pm(1,2)/\sqrt5\), og \(\lambda=-1/(2x)=\mp\sqrt5/2\):
Kandidat \(f=x+2y\) \(\lambda\)
\((1,2)/\sqrt5\) \(\sqrt5\) \(-\sqrt5/2\)
\(-(1,2)/\sqrt5\) \(-\sqrt5\) \(\sqrt5/2\)
  1. Er kandidaten best på hele sirkelen? Cauchy–Schwarz-ulikheten \(|a\cdot b|\le\lVert a\rVert_2\lVert b\rVert_2\) gir for hvert tillatt \(z\) \[x+2y=(1,2)\cdot z\le\lVert(1,2)\rVert_2\,\lVert z\rVert_2=\sqrt5.\] Den første kandidaten oppnår grensen og er globalt maksimum.

Dette tar vi med oss.

  • Finn kandidaten: Lagranges likninger ga oss regelen fra uke 4 uten at vi trengte å dra i appleten.
  • Avgjør om den er best: Cauchy–Schwarz-ulikheten avgjorde dette.
  • Bruk samme triks på ellipsen: Med \(w=2y\) blir kravet \(x^2+w^2=1\), og \(x+2y=(1,1)\cdot(x,w)\le\sqrt2\).
Gå i dybden: kjerneregelen langs kurven, og flere krav

Hvorfor normalene er parallelle. La \(p(t)\) være en glatt kurve med \(h(p(t))=0\) og \(p(0)=z_*\). Kjerneregelen gir

\[0=\left.\frac{d}{dt}h(p(t))\right|_{t=0}=\nabla h(z_*)\cdot p'(0).\]

  1. Tangenten: Enhver tangent \(p'(0)\) står altså vinkelrett på \(\nabla h\).
  2. Ekstremum langs kurven: Hvis \(f\) har et lokalt ekstremum langs kurven i \(t=0\), gir samme regel \(\nabla f(z_*)\cdot p'(0)=0\).
  3. Én normalretning: Når \(\nabla h(z_*)\ne0\), beskriver likningen lokalt en glatt kurve, og normalretningen i planet er én linje. Siden begge gradientene står vinkelrett på tangenten, må \(\nabla f\) og \(\nabla h\) være parallelle.

På sirkelen kan vi se dette direkte med \(p(t)=(\cos t,\sin t)\): \((f\circ p)'(t)=-\sin t+2\cos t=\nabla f(p(t))\cdot p'(t)\).

Flere krav. For krav \(h_1(z)=0,\ldots,h_m(z)=0\):

  • Samle normalene: Jacobimatrisen \(J_h\) har gradientene \(\nabla h_i^T\) som rader.
  • Finn tangentene: En tangent \(v\) må oppfylle \(J_h(z_*)v=0\): tangentretningene er nullrommet til \(J_h\).
  • Kontroller regularitet: Hvis radene er lineært uavhengige, er kravene regulære.

Hvert krav får sin multiplikator:

\[h_i(z_*)=0\quad(i=1,\ldots,m),\qquad \nabla f(z_*)+\sum_{i=1}^m\lambda_i\nabla h_i(z_*)=0.\]

For eksempel gir \(x_1^2+x_2^2+x_3^2=1\) og \(x_3=0\) i punktet \((1,0,0)\) normalene \((2,0,0)\) og \((0,0,1)\). Tangentene er \((0,t,0)\). I 12.4 møter vi flere lineære krav, og i prosjektet ti krav samtidig.

Gå i dybden: når normalen forsvinner

Lagranges likninger forutsetter at \(\nabla h\ne0\). Se på målet \(f(x,y)=x\) med kravet \(h(x,y)=x^2+y^2=0\):

  1. Tillatt mengde: To kvadrater summerer til null bare i \((0,0)\), så dette er det eneste tillatte punktet.
  2. Ekstremum: Punktet er dermed både minimum og maksimum på den tillatte mengden.
  3. Normaltesten: Likevel er \(\nabla f(0,0)=(1,0)\) og \(\nabla h(0,0)=(0,0)\), og

\[\nabla f+\lambda\nabla h=(1,0)\quad\text{uansett hvilken }\lambda\text{ vi velger.}\]

Kravet er degenerert i punktet: normaltesten finner ikke ekstremumet.

Vil du se det med tall? Cellen prøver tre ulike multiplikatorer i det eneste tillatte punktet. Stasjonaritetsfeilen blir den samme hver gang, fordi normalen er nullvektoren.

Ekstremumet fant vi altså ved å se direkte på den tillatte mengden, ikke med Lagranges likninger.

Øv på dette: et krav uten normal i 12.6 (valgfri).

Et kort regneeksempel: nærmest origo på en linje

Lagranges metode virker like godt for minimum. Vi søker punktet på linjen \(x+y=2\) som ligger nærmest origo, og minimerer kvadratet av avstanden.

NoteHåndeksempel: nærmeste punkt på en linje

Utgangspunkt. Minimer \(f(x,y)=x^2+y^2\) når \(h(x,y)=x+y-2=0\).

Prøv selv. Sett opp Lagranges likninger og finn kandidaten og \(\lambda\).

Regnegangen.

  1. Likningene er \(2x+\lambda=0\), \(2y+\lambda=0\) og \(x+y=2\).
  2. De to første gir \(x=y\). Kravet gir \((x,y)=(1,1)\), og da er \(\lambda=-2\) og \(f(1,1)=2\).
  3. Kontroll av at det er minimum: på linjen er \(y=2-x\), og \(f(x,2-x)=2+2(x-1)^2\ge2\), med likhet bare for \(x=1\).

Dette tar vi med oss.

  • Kravet som system: \(Cz=d\) med \(C=\begin{bmatrix}1&1\end{bmatrix}\) og \(d=2\).
  • Korteste løsning: Pseudoinversen fra den valgfrie delen uke 7.7 gir det korteste \(z\) som løser et underbestemt system: \(C^+d=(1,1)\).
  • Samme svar: Lagrange og pseudoinversen gir samme punkt. I «Gå i dybden» i 12.4 ser vi hvorfor.

Øv på dette: normal og tangent på ellipsen, et annet mål på ellipsen og Lagrange på sirkelen i 12.6.

Multiplikatoren er en pris

Hva skjer med optimal verdi hvis vi flytter kravet litt? La linjen være \(x+y=r\). Vi bruker samme regning som i håndeksempelet:

  1. \(2x+\lambda=0\) og \(2y+\lambda=0\) gir \(x=y\).
  2. Kravet gir \(x=y=r/2\).
  3. Da er \(\lambda=-2x=-r\).

Optimal verdi og dens deriverte er

\[f_*(r)=\Bigl(\frac r2\Bigr)^2+\Bigl(\frac r2\Bigr)^2=\frac{r^2}{2},\qquad \frac{df_*}{dr}=r=-\lambda.\]

  • For linjen: Sammenhengen \(df_*/dr=-\lambda\) gjelder altså for alle \(r\), ikke bare for \(r=2\), der vi fant \(\lambda=-2\).

  • Generelt: Flytter vi kravet fra \(h(z)=0\) til \(h(z)=s\), og løsningen endrer seg glatt med \(s\), er

    \[\boxed{\frac{df_*}{ds}=-\lambda\quad\text{ved } s=0.}\]

I eksempelet er \(h=x+y-2\), så \(h=s\) betyr \(x+y=2+s\), altså \(r=2+s\). Hvorfor regelen gjelder for alle glatte problemer, viser «Gå i dybden» rett under.

Multiplikatoren sier hvor mye optimal verdi endres per enhet vi flytter kravet:

  • Koblingen til uke 11: Det er samme idé som i uke 11: hva er én enhet mer av en ressurs verdt?
  • Fortegnet: I uke 11 var prisen selve endringen, et positivt tall. Her er prisen \(-\lambda\), fordi vi skriver \(L=f+\lambda h\).
  • Enheten: Har \(f\) enhet kroner og \(s\) enhet kilo, har \(\lambda\) enhet kroner per kilo.
  • I prosjektet: Multiplikatorene er krefter, og «prisen» er energi per meter.

Dette tar vi med oss.

  • Likningene: \(h=0\) og \(\nabla f+\lambda\nabla h=0\) gir kandidater, både for maksimum og minimum.
  • Tolkningen: \(-\lambda\) er hvor mye optimal verdi endres per enhet vi flytter kravet.

Øv på dette: boksen med minst overflate i 12.6.

Gå i dybden: hvorfor prisformelen gjelder generelt

La \(z(s)\) være løsningen når kravet er \(h(z)=s\), og anta at den endrer seg glatt med \(s\). Da er \(f_*(s)=f(z(s))\).

  1. Kjerneregelen: \(\dfrac{df_*}{ds}=\nabla f(z(s))\cdot z'(s)\).
  2. Lagranges likning i løsningen er \(\nabla f=-\lambda\nabla h\), så \(\dfrac{df_*}{ds}=-\lambda\,\nabla h(z(s))\cdot z'(s)\).
  3. Kravet \(h(z(s))=s\) gjelder for alle \(s\). Deriver begge sider: \(\nabla h(z(s))\cdot z'(s)=1\).
  4. Sett inn: \(\dfrac{df_*}{ds}=-\lambda\).

Kontroll med linjen: \(z(s)=\bigl(\tfrac{2+s}2,\tfrac{2+s}2\bigr)\) gir \(z'(s)=(\tfrac12,\tfrac12)\) og \(\nabla h\cdot z'=(1,1)\cdot(\tfrac12,\tfrac12)=1\). Med \(\nabla f(1,1)=(2,2)\) blir \(df_*/ds=(2,2)\cdot(\tfrac12,\tfrac12)=2=-\lambda\).

Vi kan også kontrollere regelen uten Lagrange i det hele tatt. Cellen finner \(f_*(r)\) ved å minimere direkte langs linjen \(x+y=r\), og regner ut differansekvotienter rundt \(r=2\); de skal nærme seg \(-\lambda=2\).

Differansekvotientene \(2.05\), \(2.005\) og \(2.0005\) nærmer seg \(2=-\lambda\).

Fortegnet til \(\lambda\). Sammenlign eksemplene:

Ekstremum Multiplikator
Maksimum på sirkelen \(\lambda=-\sqrt5/2\)
Minimum på linjen \(\lambda=-2\)
Minimum i avstandsproblemet i 12.5 \(\lambda=+0.618\)
  • Ingen klassifisering: Fortegnet skiller altså ikke maksimum fra minimum. For et likhetskrav betyr fortegnet ingenting alene.
  • Avhenger av skrivemåten: Skriver vi kravet som \(-h=0\) i stedet for \(h=0\), er punktet det samme, men \(\lambda\) bytter fortegn.
  • Mening gjennom prisen: \(-\lambda\) er endringen i optimal verdi når vi flytter kravet i den retningen \(h\) er skrevet.
Gå i dybden: en multiplikator gir en nedre grense

Lagrangefunksjonen kan også bevise en grense for optimal verdi, slik dualprisene ga en øvre grense i uke 11. Vi bruker avstandsproblemet som vi løser numerisk i 12.5: minimer \(F(z)=\tfrac12\lVert z-a\rVert_2^2\) med \(a=(2,1)\) når \(h(z)=\lVert z\rVert_2^2-1=0\).

  • På sirkelen: \(h=0\), så \(L(z,\lambda)=F(z)\) for alle tillatte \(z\).
  • Grense for alle punkter: Hvis \(L(\cdot,\lambda)\) aldri går under et tall \(\beta\) for alle \(z\), er også \(F(z)\ge\beta\) for alle tillatte \(z\).
  1. Velg \(\lambda_*=(\sqrt5-1)/2\). Hessianen til \(L\) med hensyn på \(z\) er \((1+2\lambda_*)I=\sqrt5\,I\), som er SPD, så \(L\) er en skål.
  2. Bunnen av skålen finnes fra \(\nabla_zL=(1+2\lambda_*)z-a=0\), altså \(z_*=a/\sqrt5\).
  3. Punktet \(z_*\) ligger på sirkelen, og \(F(z_*)=\tfrac12\lVert a/\sqrt5-a\rVert_2^2=\tfrac12\cdot5\,(1-1/\sqrt5)^2=\tfrac12(\sqrt5-1)^2\). Da er \[F(z)=L(z,\lambda_*)\ge L(z_*,\lambda_*)=F(z_*)=\tfrac12(\sqrt5-1)^2\] for alle tillatte \(z\), og grensen er skarp.

Generelt er \(\varphi(\lambda)=\inf_zL(z,\lambda)\) en nedre grense for minste verdi over de tillatte punktene, for hver \(\lambda\). I eksempelet ligger bunnen av skålen i \(z(\lambda)=a/(1+2\lambda)\) når \(1+2\lambda>0\), og innsatt er \[\varphi(\lambda)=L(z(\lambda),\lambda)=\frac{5\lambda}{1+2\lambda}-\lambda =\tfrac52-\lambda-\frac5{2(1+2\lambda)}.\] En slik skarp grense er ikke garantert for alle problemer.

Øv på dette: en nedre grense fra Lagrangefunksjonen i 12.6 (valgfri).

Hittil har eksemplene gitt én eller to kandidater, og det var lett å se hvilken som var best. Nå ser vi hva som skjer når likningene gir flere kandidater. På enhetssirkelen bytter vi mål til \(f(x,y)=xy\) og søker både maksimum og minimum.

Sirkelen er kompakt og \(f\) er kontinuerlig, så ekstremalverdisetningen fra uke 8.2 lover at begge finnes. Spørsmålet er hvor, og om tangenttesten fra 12.1 kan skille dem.

Før vi løser Lagranges likninger, skanner vi hele sirkelen. Regningen bak skanningen er:

  1. Punkt på sirkelen: \((x,y)=(\cos t,\sin t)\).
  2. Tangent: \((-y,x)\), vinkelrett på radien.
  3. Derivert langs tangenten: \(\nabla f\cdot(-y,x)=(y,x)\cdot(-y,x)=x^2-y^2\). Den kan vi regne ut i mange punkter samtidig.

Målet er å finne alle punktene som består tangenttesten, og se om de er like gode.

Eksperiment 2 – hvor er den deriverte langs tangenten null?

  • Kjør cellen. Hvor mange punkter består tangenttesten, og hvilke verdier har \(f\) der?
  • Finn de samme punktene i figuren. Hvilke er topper, og hvilke er bunner?
  • Bytt til målet \(x+2y\) fra håndeksempelet: values = x + 2*y og slope = -y + 2*x. Hvor mange punkter får du nå?

Cellen regner ut \(f\) og den deriverte langs tangenten i tusen punkter på sirkelen, og skriver ut punktene der den deriverte skifter fortegn. En ferdig hjelpefunksjon tegner \(f\) som funksjon av vinkelen \(t\).

Hva viser forsøket? Fire punkter, omtrent \((\pm0.707,\pm0.707)\), består tangenttesten:

Antall Verdi Form i figuren
To punkter \(f=1/2\) Topper
To punkter \(f=-1/2\) Bunner

Tangenttesten finner kandidatene, men den skiller ikke maksimum fra minimum. Lagranges likninger skal nå vise at det ikke finnes flere kandidater, og gi de eksakte punktene. Med \(\nabla f=(y,x)\) og \(\nabla h=(2x,2y)\) får vi

\[y+2\lambda x=0,\qquad x+2\lambda y=0,\qquad x^2+y^2=1.\]

Regn for hånd.

  1. Ingen koordinat kan være null: \(x=0\) gir \(y=0\) i første likning, og det strider mot kravet. Tilsvarende for \(y=0\).
  2. Sett \(y=-2\lambda x\) inn i den andre likningen: \(x+2\lambda(-2\lambda x)=x(1-4\lambda^2)=0\). Siden \(x\ne0\), er \(4\lambda^2=1\), altså \(\lambda=\pm\tfrac12\).
  3. Med \(\lambda=-\tfrac12\) gir \(y=-2\lambda x\) at \(y=x\). Kravet blir \(2x^2=1\), så \(x=y=\pm1/\sqrt2\). Med \(\lambda=\tfrac12\) blir \(y=-x\), og igjen er \(x=\pm1/\sqrt2\).
\(\lambda\) Relasjon Kandidater Verdi \(xy\)
\(-1/2\) \(x=y\) \(\pm(1,1)/\sqrt2\) \(1/2\)
\(1/2\) \(x=-y\) \(\pm(1,-1)/\sqrt2\) \(-1/2\)

Klassifiser globalt.

  1. \((x-y)^2\ge0\) gir \(2xy\le x^2+y^2=1\).
  2. \((x+y)^2\ge0\) gir \(2xy\ge-1\).
  3. Dermed er \(-1/2\le xy\le1/2\) på hele sirkelen. De to kandidatene med verdi \(1/2\) er globale maksimumspunkter, og de to andre er globale minimumspunkter.

Dette tar vi med oss. Lagranges likninger gir en liste med kandidater. Hvilken som er best, avgjør vi ved å sammenligne verdiene, eller med en ulikhet som gjelder alle tillatte punkter.

Sammenligningen er nok fordi to ting gjelder her:

  • Eksistens: Kompaktheten garanterer at maksimum og minimum finnes.
  • Fullstendig kandidatliste: \(\nabla h=2z\ne0\) i alle punkter på sirkelen, så alle punktene er regulære, og derfor må maksimum og minimum stå i listen. Uten regularitet kan et optimum mangle i listen (se «Gå i dybden: når normalen forsvinner» i 12.2).

Øv på dette: en kvadratisk form på sirkelen i 12.6.

Gå i dybden: andrederivert langs kurven

Vil vi undersøke hvordan målet oppfører seg helt nær én kandidat, kan vi følge sirkelen med \(p(t)=(\cos t,\sin t)\). Da er \(f(p(t))=\tfrac12\sin2t\).

Vinkel Andrederivert Tolkning langs sirkelen
\(t=\pi/4\) \(-2\) Grafen bøyer nedover: lokalt maksimum.
\(t=-\pi/4\) \(+2\) Lokalt minimum.

Generelt, for en tillatt kurve \(\gamma(t)\) gjennom et regulært stasjonært punkt med tangent \(v=\gamma'(0)\):

  1. Derivér kravet \(h(\gamma(t))=0\) to ganger: \(v^T\nabla^2h\,v+\nabla h\cdot\gamma''(0)=0\).
  2. Den andrederiverte av målet langs kurven er \(v^T\nabla^2f\,v+\nabla f\cdot\gamma''(0)\), og \(\nabla f=-\lambda\nabla h\).
  3. Fjern leddet med \(\gamma''(0)\) ved hjelp av steg 1: \[(f\circ\gamma)''(0)=v^T\nabla^2_{zz}L(z_*,\lambda)\,v.\]

Kurven selv bøyer seg, så det er Hessianen til \(L\), ikke til \(f\), som teller langs tangentene:

  • Positiv form for alle tangenter \(v\ne0\): Strengt lokalt minimum.
  • Negativ form for alle tangenter \(v\ne0\): Strengt lokalt maksimum.
  • Null i en retning: Avgjør ikke saken.

For \(f=xy\) er \(\nabla^2_{zz}L=\left(\begin{smallmatrix}2\lambda&1\\1&2\lambda\end{smallmatrix}\right)\). Med \(\lambda=-1/2\) og \(v=(-1,1)/\sqrt2\) gir formen \(-2\), som over.

Kandidattabellen er en egenverditabell

Nå viser vi at kandidatene fra forrige del er egenvektorer. Skriv målet fra 12.3 med en symmetrisk matrise:

\[xy=z^TAz,\qquad A=\begin{bmatrix}0&\tfrac12\\\tfrac12&0\end{bmatrix}.\]

Hva er gradienten til \(z^TAz\)? Vi regner den ut i det lille tilfellet først.

  1. Utvid: For en symmetrisk \(2\times2\)-matrise er \(z^TAz=a_{11}x^2+2a_{12}xy+a_{22}y^2\).
  2. Derivér: De partiellderiverte er \(2a_{11}x+2a_{12}y\) og \(2a_{12}x+2a_{22}y\). Altså er \(\nabla(z^TAz)=2Az\) (det gjelder i alle dimensjoner).
  3. Kontroller med vår \(A\): \(2Az=2\bigl(\tfrac12y,\tfrac12x\bigr)=(y,x)=\nabla(xy)\).

For sirkelen er \(\nabla h=2z\), og Lagranges likning blir da

\[2Az+2\lambda z=0\qquad\Longleftrightarrow\qquad Az=-\lambda z.\]

En kandidat er en egenvektor, og \(-\lambda\) er egenverdien.

  • Målverdien: \(z^TAz=-\lambda\,z^Tz=-\lambda\).
  • Vår matrise: Egenverdiene til \(A\) er \(\pm\tfrac12\), med egenvektorer langs \((1,1)\) og \((1,-1)\). Det er akkurat tabellen i 12.3: \(\lambda=-\tfrac12\) gir maksimum \(\tfrac12\), og \(\lambda=\tfrac12\) gir minimum \(-\tfrac12\).
  • Koblingen til uke 5: På enhetssirkelen er \(z^TAz\) Rayleigh-kvotienten fra uke 5, og vi har vist:

Største og minste verdi av \(z^TAz\) når \(\lVert z\rVert_2=1\) er største og minste egenverdi av \(A\).

Begrunnelsen er den samme som i 12.3: maksimum og minimum finnes fordi sirkelen er kompakt, og hvert punkt på sirkelen er regulært, så maksimums- og minimumspunktene er blant kandidatene, altså egenvektorene.

Største strekk. I uke 7 sendte matrisen \(B=\begin{bmatrix}0&2\\1&0\end{bmatrix}\) (der het den \(A\)) enhetssirkelen til en ellipse, og største strekk var \(\sigma_1=2\). Nå kan vi utlede det:

  1. Skriv kvadrert strekk: Her er \(Bz=(2y,\,x)\), så \(\lVert Bz\rVert_2^2=x^2+4y^2=z^T(B^TB)z\) med \(B^TB=\operatorname{diag}(1,4)\). Det er samme type problem, og uttrykket er det samme som for ellipsen i 12.1.
  2. Bruk sirkelkravet: På sirkelen er \(x^2=1-y^2\), så \(x^2+4y^2=1+3y^2\le4\), med likhet i \(z=\pm e_2\).
  3. Ta kvadratroten: Største strekk er \(\sqrt4=2\).

Vi har vist med likninger at kandidatene er egenvektorer. Forsøket viser det samme i et bilde, og lar deg prøve andre matriser. Målet er å se at nivåkurvene berører sirkelen nøyaktig i egenvektorene, slik nivålinjen berørte ellipsen i 12.1.

Eksperiment 3 – se egenvektorene på sirkelen

  • Kjør cellen. Hvilke nivåkurver berører sirkelen, og hvor?
  • Bytt til plot_quadratic_on_circle(B.T @ B). Hvor ligger nå punktet med største strekk?
  • Velg en egen symmetrisk matrise, for eksempel [[2, 1], [1, 2]], og forutsi berøringspunktene før du kjører.

Cellen gir oss både tallene og bildet:

  • Tallene: np.linalg.eigh regner ut egenverdiene og egenvektorene. Den er som eigvalsh fra uke 8, men gir også egenvektorene.
  • Figuren: En ferdig hjelpefunksjon, plot_quadratic_on_circle(A), tegner nivåkurvene til \(z^TAz\), enhetssirkelen og egenvektorene.

Hva viser forsøket?

  • For \(A\): Nivåkurvene \(xy=\pm\tfrac12\) berører sirkelen nøyaktig i egenvektorene, og verdien der er egenverdien: eigh gir \(\pm0.5\).
  • For \(B^TB\): eigh gir \(1\) og \(4\). Nivåkurvene er ellipsene \(x^2+4y^2=c\), og kurven \(c=4\) berører sirkelen i \(\pm e_2\).
  • Strekket: Største strekk er \(\sqrt4=2\), og svd gir singulærverdiene \(2\) og \(1\).

Øv på dette: største strekk med Lagrange i 12.6.

Lineære krav gir et lineært system

  • Ett lineært krav: For \(c^Tz=d\) er normalen \(c\) den samme i alle punkter.
  • Flere lineære krav: Vi samler dem som \(Cz=d\), der hver rad i \(C\) er ett krav. Hvert krav får sin multiplikator \(\lambda_i\).

Lagranges likning blir

\[\nabla f(z)+C^T\lambda=0.\]

  • Gradienten: Likningen sier at \(\nabla f\) er en lineærkombinasjon av radene i \(C\), altså av normalene, akkurat som \(\nabla f\) var parallell med \(\nabla h\) i 12.2.
  • Tillatte retninger: De tillatte retningene utgjør nullrommet til \(C\) fra uke 3. Hvorfor \(\nabla f\) da står vinkelrett på dem, viser «Gå i dybden» under eksperimentet.

Når \(f\) er kvadratisk, er \(\nabla f\) lineær i \(z\), og alle likningene blir lineære. For linjeeksempelet i 12.2, \(f=x^2+y^2\) og \(x+y=2\), får vi

\[\underbrace{\begin{bmatrix}2&0&1\\0&2&1\\1&1&0\end{bmatrix}}_{K} \begin{bmatrix}x\\y\\\lambda\end{bmatrix} =\begin{bmatrix}0\\0\\2\end{bmatrix}.\]

De to første radene er \(\nabla f+\lambda\nabla h=0\), den siste er kravet. Et slikt system kalles et KKT-system (etter Karush, Kuhn og Tucker).

Systemet er symmetrisk, akkurat som systemene vi løste med CG i uke 6 og Cholesky i uke 10. Men begge metodene krevde mer: matrisen måtte være SPD. Målet er å finne ut om metodene fra uke 6 og 10 kan brukes på et KKT-system.

Eksperiment 4 – løs KKT-systemet og prøv Cholesky

Forutsi: \(K\) er symmetrisk. Er den SPD, slik at Cholesky fra uke 10 og CG fra uke 6 kan brukes?

  • Skriv ned forutsigelsen, og kjør cellen.
  • Bytt høyresiden til (0, 0, 4), altså linjen \(x+y=4\). Forutsi løsningen før du kjører. Endrer egenverdiene seg?

Cellen løser systemet med np.linalg.solve, som ikke krever SPD, regner ut egenverdiene og prøver Cholesky.

Hva viser forsøket?

  • Løsningen: \((1,1,-2)\), som for hånd i 12.2.
  • Matrisen: Egenverdiene er \(-0.73\), \(2\) og \(2.73\). Matrisen er symmetrisk, men indefinit, og Cholesky feiler.
  • Hvorfor det skjer: Nullen nederst til høyre gir \(e_3^TKe_3=0\), og en SPD-matrise har \(v^TKv>0\) for alle \(v\ne0\). Et KKT-system er derfor aldri SPD (se «Gå i dybden» under), og CG og Cholesky kan ikke brukes direkte.

Dette tar vi med oss. Når målet er kvadratisk, blir Lagranges likninger lineær algebra:

Krav Hva likningene blir
Sirkelkrav Egenverdiproblem, der kandidatene er egenvektorene.
Lineære krav Symmetrisk, men indefinit likningssett: CG og Cholesky virker ikke direkte.

Nullromsmetoden i «Gå i dybden» viser én vei rundt.

Øv på dette: KKT-systemet for en linje i 12.6 og KKT-systemet og pseudoinversen i 12.7.

Gå i dybden: nullrommet, og hvordan vi kan omgå det indefinitte systemet

Hvorfor \(\nabla f+C^T\lambda=0\) er riktig betingelse.

  1. Tillatte retninger: En retning \(v\) endrer ikke \(Cz\) når \(Cv=0\). De tillatte retningene er altså nullrommet til \(C\).
  2. Vinkelrett på radene: At \(Cv=0\) betyr at \(v\) står vinkelrett på hver rad i \(C\).
  3. Gradienten balanseres av normalene: Likningen sier at \(\nabla f=-C^T\lambda\) er en lineærkombinasjon av radene. Da står også \(\nabla f\) vinkelrett på alle tillatte retninger: \(\nabla f\cdot v=-\lambda^TCv=0\).

Målet endres altså ikke til første orden i noen tillatt retning.

Nullromsmetoden. Idéen er å skrive de tillatte punktene slik at kravet alltid er oppfylt. Ethvert tillatt punkt kan skrives \(z=z_0+tZ\):

  • \(z_0=(2,0)\) er én løsning av kravet.
  • \(Z=(1,-1)\) spenner ut nullrommet til \(C=\begin{bmatrix}1&1\end{bmatrix}\).

Da er kravet oppfylt for alle \(t\), og vi minimerer uten krav:

\[f(z_0+tZ)=(2+t)^2+t^2=4+4t+2t^2,\qquad \frac{d}{dt}=4+4t=0\ \Rightarrow\ t=-1,\ z=(1,1).\]

Det reduserte problemet har én variabel og positiv krumning. Cellen setter inn \(t=-1\), kontrollerer at punktet oppfyller kravet, og tegner bildet med en ferdig hjelpefunksjon.

  • Punkter og retning: Du ser \(z_0\), nullromsretningen \(Z\) og løsningen, der \(\nabla f=(2,2)\) er parallell med raden \((1,1)\) i \(C\).
  • Prikket sirkelbue: Nivåkurven \(f=2\), som berører linjen akkurat der.

Nullromsmetoden generelt.

  1. Parametriser: Bruk \(z=z_0+Zt\), der kolonnene i \(Z\) er en basis for nullrommet og \(t\) er en vektor med like mange tall som kolonner i \(Z\).
  2. Sett inn i målet: For \(f=\tfrac12z^TQz-b^Tz\) (som i neste boks) gir utvidelsen av \(\tfrac12(z_0+Zt)^TQ(z_0+Zt)-b^T(z_0+Zt)\) \[f(z_0+Zt)=\tfrac12t^T(Z^TQZ)t+t^TZ^T(Qz_0-b)+f(z_0),\] som vi minimerer uten krav.
  3. Velg løser: Matrisen \(Z^TQZ\) er SPD når \(Q\) er positiv definitt på nullrommet, og da virker både Cholesky og CG igjen.
Gå i dybden: det generelle KKT-systemet og pseudoinversen

For \(f(z)=\tfrac12z^TQz-b^Tz\) med symmetrisk \(Q\) og krav \(Cz=d\) er \(\nabla f=Qz-b\), og Lagranges likninger blir

\[\begin{bmatrix}Q&C^T\\C&0\end{bmatrix} \begin{bmatrix}z\\\lambda\end{bmatrix}=\begin{bmatrix}b\\d\end{bmatrix}.\]

  • Invertibel: Hvis \(C\) har \(m\) uavhengige rader og \(Q\) er positiv definitt på nullrommet til \(C\), er matrisen invertibel.
  • Aldri positiv definitt: For \(v=(0,w)\) er \(v^TKv=0\).
  • Negative egenverdier: Under disse forutsetningene kan man vise at matrisen har nøyaktig \(m\) negative egenverdier; i eksperiment 4 var \(m=1\).

Minste norm. Med \(Q=I\) og \(b=0\) minimerer vi \(\tfrac12\lVert z\rVert_2^2\) under \(Cz=d\):

  1. Første blokkrad gir \(z=-C^T\lambda\).
  2. Andre blokkrad gir \(-CC^T\lambda=d\).

Dermed er

\[z=C^T(CC^T)^{-1}d,\]

som er pseudoinversløsningen \(C^+d\) fra uke 7.7 når radene i \(C\) er uavhengige. Kodeoppgaven KKT-systemet og pseudoinversen i 12.7 kontrollerer dette.

For større problemer, som kjettingen i prosjekt 12 med ti krav, løser vi ikke Lagranges likninger for hånd. Vi bruker minimize med metoden SLSQP, som tar imot likhetskrav, og kontrollerer svaret selv.

Som eksempel bruker vi punktet \(a=(2,1)\), som ligger utenfor enhetssirkelen. Vi søker punktet på sirkelen som ligger nærmest.

Rolle Uttrykk
Valg \(z=(x,y)\)
Mål Minimer \(F(z)=\tfrac12\lVert z-a\rVert_2^2\)
Krav \(h(z)=\lVert z\rVert_2^2-1=0\)

Løseren gir en numerisk kandidat. At løseren melder at den stoppet normalt, erstatter ikke to kontroller vi må gjøre selv:

  • Betingelsesfeilen \(|h(z)|\): ligger punktet på sirkelen?
  • Stasjonaritetsfeilen \(\lVert\nabla F(z)+\lambda\nabla h(z)\rVert_2\): kan målgradienten balanseres av normalen?

Når vi trenger \(\lambda\), velger vi den \(\lambda\) som gjør stasjonaritetsfeilen minst. Det er et minste kvadraters problem med én ukjent, som i uke 4, og svaret er

\[\lambda=-\frac{\nabla F\cdot\nabla h}{\lVert\nabla h\rVert_2^2}.\]

Med flere krav bruker vi samme idé:

  1. Samle gradientene: \(\nabla h_i^T\) blir rader i Jacobimatrisen \(J\) (som i prosjekt 10).
  2. Løs minste kvadrater: Løs \(\min_\lambda\lVert\nabla F+J^T\lambda\rVert_2\) med np.linalg.lstsq. Det gjør vi i prosjektet.

Hvorfor vi ikke bruker SciPys egne multiplikatorer, står i SciPy-oppslaget.

Gå i dybden: formelen for multiplikatoren med minst feil

Kvadratet av stasjonaritetsfeilen er et andregradspolynom i \(\lambda\):

\[\lVert\nabla F+\lambda\nabla h\rVert_2^2=\nabla F\cdot\nabla F +2\lambda\,\nabla F\cdot\nabla h+\lambda^2\,\nabla h\cdot\nabla h.\]

  1. Derivér med hensyn på \(\lambda\): Den deriverte er \(2\,\nabla F\cdot\nabla h+2\lambda\,\nabla h\cdot\nabla h\).
  2. Sett lik null: Den er null for \(\lambda=-\nabla F\cdot\nabla h/\lVert\nabla h\rVert_2^2\).
  3. Kontroller minimum: Den andrederiverte, \(2\lVert\nabla h\rVert_2^2\), er positiv når kravet er regulært, så dette er minimum.

Nå kan vi prøve alt dette på avstandsproblemet. Målet er å se hva kontrollfeilene sier, og hva de ikke sier.

Eksperiment 5 – finn og kontroller et sirkelpunkt

  • Kjør cellen, og sammenlign punktet med \(a/\lVert a\rVert_2\).
  • Bytt startpunktet til np.array([-.9, -.45]), som ligger på linjen gjennom origo og \(a\). Hva rapporterer løseren nå, og hvilke av tallene avslører at punktet ikke er det nærmeste?
  • Flytt startpunktet litt bort fra linjen, for eksempel til np.array([-.9, -.5]). Hvor havner løseren nå?

Cellen kjører SLSQP fra punktet \((0.4,0.9)\), regner ut de to kontrollfeilene og velger \(\lambda\) med formelen over.

Hva viser forsøket? Sammenlign to startpunkter:

Startpunkt Funnet sirkelpunkt \(F\) og \(\lambda\)
\((0.4,0.9)\) \(z\approx(0.89442719,\,0.44721360)\) \(F\approx0.76393202\), \(\lambda\approx0.618034\)
\((-0.9,-0.45)\) \(z\approx(-0.894,-0.447)=-a/\lVert a\rVert_2\) \(F\approx5.236\), \(\lambda\approx-1.618\)

Punktet fra det første startpunktet stemmer med \(a/\lVert a\rVert_2\).

  • Samme kontrollresultat: Begge ganger er kontrollfeilene små, og løseren rapporterer success=True. Flagget betyr bare at løseren stoppet på vanlig måte.
  • Ulik kvalitet: Den andre kandidaten er det fjerneste punktet. Det andre startpunktet ligger på linjen gjennom origo og \(a\). Der peker både \(\nabla F\) og normalen langs linjen, så hvert steg blir liggende på linjen.
  • Litt endret start: Flytter du startpunktet litt bort fra linjen, finner løseren det nærmeste punktet igjen.
  • Hva kontrollene avgjør: Kontrollfeilene viser bare at punktet er en kandidat. Først verdien av \(F\), eller ulikheten under, avgjør hvilken kandidat som er best.

Er det globalt nærmest? For tillatte \(z\) gir Cauchy–Schwarz \(a\cdot z\le\lVert a\rVert_2=\sqrt5\), så

\[F(z)=\tfrac12\bigl(\lVert a\rVert_2^2+1-2a\cdot z\bigr)\ge\tfrac12(\sqrt5-1)^2,\]

med likhet bare i \(z=a/\sqrt5\). De to numeriske kontrollene viser at punktet er en kandidat; ulikheten viser at det er det beste.

Øv på dette: to kontrollfeil for et feil forslag i 12.6 og de tre første kodeoppgavene i 12.7.

En annen vei: straffemetoden.

  • Uten et eksplisitt krav: I stedet for å kreve \(h=0\) kan vi minimere \(F+\tfrac\mu2h^2\) uten krav, med et stort tall \(\mu\).
  • Gradienten: \(\nabla F+(\mu h)\nabla h\). Sammenlign med \(\nabla F+\lambda\nabla h\): tallet \(\mu h\) spiller rollen til \(\lambda\).
  • Tilnærmingen: Da blir \(h\) liten, men ikke null, og \(\mu h\) nærmer seg multiplikatoren. I prosjekt 12 ser du hva det koster når \(\mu\) blir stor.
Gå i dybden: hva rapporterer SLSQP underveis?

Hvordan kommer SLSQP fram til svaret? Cellen kjører samme søk med en callback som lagrer punktene SLSQP rapporterer, skriver ut \(h\) og \(F\) i hvert av dem, og tegner dem sammen med nivåkurvene til \(F\).

  • Linjestykkene: Viser bare rekkefølgen.
  • Mellompunktene: Trenger ikke ligge på sirkelen. Et punkt utenfor sirkelen kan ha lavere \(F\) enn det beste tillatte punktet.

Det andre rapporterte punktet har \(h=2.021\), langt utenfor sirkelen, og \(F=0.264\), lavere enn \(F=0.764\) i det beste punktet på sirkelen.

Begge de stasjonære punktene.

  1. Fra \(z-a+2\lambda z=0\) følger \(z=a/(1+2\lambda)\).
  2. Kravet gir \(|1+2\lambda|=\sqrt5\).
  3. Det nærmeste punktet \(a/\sqrt5\) og det fjerneste \(-a/\sqrt5\) er begge stasjonære.

Små kontrollfeil alene skiller dem ikke; verdien av \(F\) gjør det.

Gå i dybden: ulikhetskrav – skiven i stedet for sirkelen

Hva om punktet bare må ligge i skiven, \(g(z)=\lVert z\rVert_2^2-1\le0\)? Da er det to muligheter:

  • Ligger \(a\) inne i skiven, er \(z=a\) selv svaret. Kravet er ikke aktivt, og målet har gradient null der. Vi setter \(\lambda=0\).
  • Ligger \(a\) utenfor, er svaret på randen, som over. Kravet er aktivt.

Begge tilfellene dekkes av KKT-betingelsene for en minimering med \(g\le0\) og \(L=F+\lambda g\):

\[\nabla F+\lambda\nabla g=0,\qquad g\le0,\qquad \lambda\ge0,\qquad \lambda\,g=0.\]

  • Komplementær slakk: Den siste likningen er komplementær slakk fra uke 11: enten er kravet aktivt (\(g=0\)), eller så er prisen null (\(\lambda=0\)).
  • Fortegnskravet: \(\lambda\ge0\) sier at \(-\nabla F\), retningen der \(F\) avtar, peker ut av skiven. Å slippe opp kravet litt kan derfor bare gjøre minimumsverdien lavere eller la den være uendret.

Cellen prøver begge tilfellene med SLSQP: én \(a\) inne i skiven og én utenfor. For hvert svar sjekker den om kravet er aktivt, og regner i så fall ut \(\lambda\) med formelen for minste kvadrater fra 12.5.

SciPy skriver ulikheter som fun(z) >= 0, derfor sender vi 1 - q @ q.

Punktet vi søker nærmest Er kravet aktivt? Multiplikator
\(a=(0.5,0.25)\) Nei \(\lambda=0\)
\(a=(2,1)\) Ja \(\lambda=0.618034=(\sqrt5-1)/2\)

I det siste tilfellet er multiplikatoren den samme som med sirkelkravet.

Øv på dette: aktivt eller ikke aktivt krav i 12.6 (valgfri).

Hva de tolv ukene har bygget

Ukens spørsmål var hva som erstatter \(\nabla f=0\) når punktet må ligge på en kurve. Svaret bygger på tre deler:

  • Finn kandidater: Lagranges likninger er \(h=0\) og \(\nabla f+\lambda\nabla h=0\). De gir kandidater, ikke løsninger.
  • Avgjør hvilken som er best: Sammenlign verdier eller bruk en global ulikhet.
  • Regn og kontroller: For kvadratiske mål ble likningene lineær algebra. Et punkt fra en løser kontrollerte vi med to kontrollfeil.

Slik henger de tolv ukene sammen:

Uker Det vi bygget
1–7 Flyttall og avrunding, iterasjon, likningssett, nullrom og rang, minste kvadrater, egenverdier, SPD-matriser og CG, og singulærverdier.
8 Eksistens, Hessianen og konveksitet.
9–10 Gradient- og Newtonmetoden med kondisjonstallet og Cholesky.
11–12 Multiplikatorer som priser og optimalitetssertifikater.

Ukene 8–12 brukte altså verktøyene fra ukene 1–7 på optimering. Tre spørsmål har fulgt oss siden uke 8, og underveis kom et fjerde til:

  1. Finnes det et beste svar?
  2. Hva forteller krumningen?
  3. Er kandidaten vi fant, den beste?
  4. Hvordan kontrollerer vi et tall som en løser gir oss?

Denne uken svarte vi på dem med kompakthet, Lagranges likninger, en global ulikhet og to kontrollfeil. Den arbeidsmåten tar du med deg videre: regn ut et svar, og kontroller det med et argument eller en uavhengig test.

Oppgavene er sortert etter de tre ideene. De tre siste hører til «Gå i dybden»-boksene og er valgfrie.

  • Arbeidsmåte: Arbeid på papir først. Begrunnelsene skriver du i egne notater; feltene kontrollerer tallene.
  • Eksakte svar: Gi eksakte svar, for eksempel 1/sqrt(5). I uttrykksfeltene bruker du * for multiplikasjon.
  • Ja/nei: Skriv 1 for ja, 0 for nei.

Vi bruker \(h=0\) og \(L=f+\lambda h\). Ved et regulært ekstremum må \(h=0\) og \(\nabla f+\lambda\nabla h=0\). Løsningene av disse likningene er kandidater som må klassifiseres.

Idé 1: Lagranges likninger og prisen (12.1–12.2)

Ellipsen \(h(x,y)=x^2+4y^2-1=0\) fra 12.1 har sitt øverste punkt i \(p=(0,1/2)\). Finn normalen \(\nabla h(p)\) og en enhetstangent med positiv \(x\)-komponent.

Forklar: Kontroller at skalarproduktet av de to vektorene er null. Hva betyr det geometrisk?

Maksimer \(f(x,y)=2x+y\) når \(x^2+4y^2=1\). Bruk substitusjonen \(w=2y\), slik at kravet blir en sirkel, og bruk Cauchy–Schwarz som i håndeksempelet i 12.2.

Forklar: Kontroller svaret med Lagranges likninger, og kontroller at \(\nabla h\) er parallell med \((2,1)\) i punktet.

Maksimer \(f(x,y)=3x-4y\) på enhetssirkelen, med \(h=x^2+y^2-1=0\). Finn maksimumspunktet og multiplikatoren.

Forklar: Hvorfor er punktet globalt maksimum, og ikke bare en kandidat?

En sylinderformet boks har radius \(x>0\) og høyde \(y>0\). Volumet skal være \(V\), altså \(h(x,y)=\pi x^2y-V=0\). Overflaten er \(f(x,y)=2\pi x^2+2\pi xy\).

Gradientene er gitt:

\(\nabla f=\begin{bmatrix}4\pi x+2\pi y\\2\pi x\end{bmatrix},\qquad \nabla h=\begin{bmatrix}2\pi xy\\\pi x^2\end{bmatrix}.\)

  1. Sett opp vektorlikningen \(\nabla f+\lambda\nabla h=0\) sammen med \(h=0\).
  2. Bruk den andre komponentlikningen til å finne \(\lambda\) uttrykt med \(x\), og den første komponentlikningen til å finne forholdet mellom høyde og radius.
  3. Bruk til slutt prisformelen fra 12.2: hvor mye øker minste overflate \(A_*\) per enhet ekstra volum?

Forklar: Hvorfor er ekte hermetikkbokser ofte høyere enn dette? Nevn én ting modellen ser bort fra.

Idé 2: Kandidater, egenverdier og KKT-systemet (12.3–12.4)

La \(f(x,y)=x^2+4xy+y^2\) på enhetssirkelen og \(p=(1,1)/\sqrt2\).

  1. Skriv \(f=z^TAz\) med en symmetrisk \(A\), og finn egenverdiene og \(f(p)\).
  2. Finn multiplikatoren fra \(Ap=-\lambda p\).
  3. Krumningen langs sirkelen er gitt av \(v^TBv\), der \(B=2A+2\lambda I\) og enhetstangenten er \(v=(-1,1)/\sqrt2\). Regn ut matriseproduktet. Hva forteller fortegnet om kandidaten \(p\)?

La \(B=\begin{bmatrix}3&0\\4&5\end{bmatrix}\). Maksimer \(\lVert Bz\rVert_2^2=z^TB^TBz\) når \(\lVert z\rVert_2=1\). Regn ut \(B^TB\) og egenverdiene. Velg maksimumspunktet med positive koordinater.

Forklar: Sammenlign med np.linalg.svd(B).

Minimer \(f(x,y)=x^2+y^2\) når \(x+2y=5\). Skriv Lagranges likninger som et \(3\times3\)-system \(K(x,y,\lambda)^T=(0,0,5)^T\) og løs det. Regn ut determinanten til \(K\), og avgjør om \(K\) er SPD.

Forklar: Hvorfor viser fortegnet til determinanten alene at \(K\) ikke er SPD?

Idé 3: Kontroller et numerisk svar (12.5)

I avstandsproblemet fra 12.5 er \(a=(2,1)\), \(F(z)=\tfrac12\lVert z-a\rVert_2^2\) og \(h(z)=\lVert z\rVert_2^2-1\). En løser rapporterer \(z=(1,0)\) og \(\lambda=1/2\). Regn ut begge kontrollfeilene.

Forklar: Hvilken kontroll avslører at punktet ikke er stasjonært? Kan en annen \(\lambda\) gjøre stasjonaritetsfeilen mindre?

Til fordypningene (valgfritt)

Hører til «Gå i dybden: når normalen forsvinner» i 12.2. La \(f(x,y)=x+3y\) og \(h(x,y)=x^2+y^2=0\). Finn det eneste tillatte punktet og \(\nabla h\) der.

Forklar: Hvorfor kan ingen multiplikator gjøre \(\nabla f+\lambda\nabla h=0\), selv om punktet er et optimum?

Hører til «Gå i dybden: en multiplikator gir en nedre grense» i 12.2. Bruk \(F(z)=\tfrac12\lVert z-(2,1)\rVert_2^2\), \(h(z)=\lVert z\rVert_2^2-1\) og \(\lambda=1/2\). Da er \(L=F+\lambda h\) kvadratisk.

Finn:

  1. \(c\) slik at Hessianen til \(L\) er \(cI\),
  2. minimumsverdien av \(L\) over alle \(z\),
  3. \(F(1,0)\).

Forklar: Er grensen skarp? Sammenlign med \(\tfrac12(\sqrt5-1)^2\).

Hører til «Gå i dybden: ulikhetskrav» i 12.5. Finn punktet i skiven \(\lVert z\rVert_2^2\le1\) som ligger nærmest \(a\), med \(F=\tfrac12\lVert z-a\rVert_2^2\), \(g=\lVert z\rVert_2^2-1\) og \(L=F+\lambda g\). Gjør det for \(a=(0.3,0.4)\) og for \(a=(0,3)\).

Forklar: Kontroller fortegnskravet og komplementær slakk i begge tilfellene.

Oppgavene har egne importer og definisjoner og kan kjøres uavhengig av forsøkene. Fyll bare inn hullene merket TODO. De automatiske testene vurderer resultatet uten å vise løsningen.

SciPy-oppslag: SLSQP og multiplikatoren
Uttrykk Betydning
method="SLSQP" En metode i minimize som tar imot likhets- og ulikhetskrav.
{"type": "eq", "fun": h, "jac": grad_h} Krever \(h(z)=0\) og oppgir gradienten (normalen).
{"type": "ineq", "fun": lambda z: -g(z)} Krever at funksjonen er \(\ge0\). Et krav \(g(z)\le0\) sendes derfor som \(-g\).
options={"ftol": 1e-12, "maxiter": 100} Løserens stopptoleranse og grense for antall iterasjoner.
np.linalg.lstsq(J.T, -grad, rcond=None)[0] Multiplikatorene som gjør \(\lVert\nabla F+J^T\lambda\rVert_2\) minst, med grad \(=\nabla F\).

Flere krav: Bruk en liste med ordbøker, eller én fun som returnerer en vektor og en jac som returnerer Jacobimatrisen.

result.x, result.fun og result.success betyr det samme som i uke 8.

  • Nyere SciPy-versjoner: Gir også result.multipliers, men med motsatt fortegn av vårt (\(L=f-\lambda h\)).
  • SciPy 1.14 i nettleseren: Gir dem ikke.
  • Vår kontroll: Vi beregner derfor \(\lambda\) selv med lstsq, som virker overalt, og kontrollerer \(|h|\) og \(\lVert\nabla F+\lambda\nabla h\rVert_2\).

Normalen til ellipsen. For \(h(x,y)=x^2+4y^2-1\) skal grad_h(z) returnere gradienten som en NumPy-array.

Les et numerisk svar. For avstandsproblemet i 12.5 skal check(z, lam) returnere betingelsesfeilen \(|h(z)|\) og stasjonaritetsfeilen \(\lVert\nabla F(z)+\lambda\nabla h(z)\rVert_2\).

Send kravet til SLSQP. Fyll inn ordboken som angir \(h(z)=0\) og gradienten.

KKT-systemet og pseudoinversen. Valgfri: bygger på den valgfrie fanen 7.7. Minimer \(\tfrac12\lVert z\rVert_2^2\) når \(Cz=d\).

  1. Bygg blokkmatrisen \(K=\begin{bmatrix}I&C^T\\C&0\end{bmatrix}\) med np.block.
  2. Løs \(K(z,\lambda)^T=(0,d)^T\) og returner bare \(z\).
  3. Sammenlign etterpå med np.linalg.pinv(C) @ d.