Newtons metode i optimering

Frå testwiki
Hopp til navigering Hopp til søk

I matematisk optimering baserer Newtons metode på å finna stasjonære punkt (minima, maksima, sadelpunkt, både lokale og globale) for ein gjeven funksjon f, altså baserer han seg på ei minimering av Δf(x) i staden for ei minimering av f(x) som i newtons metode i kalkulus.

Definisjon

Gjeve eit startpunkt xn for algoritmen og ein funksjon f ein ønskjer å finna stasjonære punkt for, så er newtons algoritme i optimering gjeven som

xn+1=xn−(Δ2f(xn))−1Δf(xn)

I høvet der f berre er ein funksjon av ein variabel, så er Δf(xn) den deriverte til funksjonen f og Δ2f(xn) er den dobbeltderiverte. I det høvet der f er ein fleirvariabels funksjon så er Δf(xn) kjend som gradienten av f og Δ2f(xn) kjend som hessematrisa for f. (Δ2f(xn))−1 er inversen av denne hessematrisa.

Under særskilde føresetnadar bundne av valet av startpunkt xk, så vil følgja xn+1 konvergera mot løysinga av likninga Δf(xx+1)=0, altså er xn+1 eit stasjonært punkt.

Motivering av definisjon

Utleiinga av algoritmen er særs lik som for utleiinga av newtons metode i kalkulus. Ein nyttar ei taylorpolynomtilnærming til å utleia eit newtonsteg, som vert steget h i ein iterativ descentalgoritme, gjeven som:

xk+1=xk+h

I motsetning til newtons metode i kalkulus nyttar ein ei andreordens taylorpolynomtilnærming av i staden for ei førsteordens. Denne tilnærminga vert derivert og vidare minimisert med omsyn på h for å utleia newtonsteget h.

Ei andreordens taylorpolynomtilnærming for funksjonen f er:

f(xk+h)=f(xk)+Δf(xk)Th+12Δ2f(xk)hTh

Den deriverte av tilnærminga er:

∂∂h(f(xk)+Δf(xk)Th+12Δ2f(xk)hTh)=Δf(xk)T+Δ2f(xk)h

Og ein minimiserer denne funksjonen ved å løysa:

Δf(xk)T+Δ2f(xk)h=0

Med omsyn på h, som gjev newtonsteget h i algoritmen:

h=−(Δ2f(xk))−1Δf(xk)

Som gjev den iterative algoritmen

xn+1=xn−(Δ2f(xn))−1Δf(xn)

kjend som Newtons metode i optimering.

Henta frå «https://nn.wiki.beta.math.wmflabs.org/w/index.php?title=Newtons_metode_i_optimering&oldid=937»