Newtons metode i optimering

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 $\Delta f(x)$ i staden for ei minimering av $f(x)$ som i newtons metode i kalkulus.

Definisjon

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

$x_{n+1}=x_{n}-(\Delta ^{2}f(x_{n}))^{-1}\Delta f(x_{n})$

I høvet der $f$ berre er ein funksjon av ein variabel, så er $\Delta f(x_{n})$ den deriverte til funksjonen $f$ og $\Delta ^{2}f(x_{n})$ er den dobbeltderiverte. I det høvet der $f$ er ein fleirvariabels funksjon så er $\Delta f(x_{n})$ kjend som gradienten av $f$ og $\Delta ^{2}f(x_{n})$ kjend som hessematrisa for $f$. $(\Delta ^{2}f(x_{n}))^{-1}$ er inversen av denne hessematrisa.

Under særskilde føresetnadar bundne av valet av startpunkt $x_{k}$, så vil følgja $x_{n+1}$ konvergera mot løysinga av likninga $\Delta f(x_{x+1})=0$, altså er $x_{n+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:

$x_{k+1}=x_{k}+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(x_{k}+h)=f(x_{k})+\Delta f(x_{k})^{T}h+{\frac {1}{2}}\Delta ^{2}f(x_{k})h^{T}h$

Den deriverte av tilnærminga er:

${\frac {\partial }{\partial h}}\left(f(x_{k})+\Delta f(x_{k})^{T}h+{\frac {1}{2}}\Delta ^{2}f(x_{k})h^{T}h\right)=\Delta f(x_{k})^{T}+\Delta ^{2}f(x_{k})h$

Og ein minimiserer denne funksjonen ved å løysa:

$\Delta f(x_{k})^{T}+\Delta ^{2}f(x_{k})h=\displaystyle 0$

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

$h=-(\Delta ^{2}f(x_{k}))^{-1}\Delta f(x_{k})$

Som gjev den iterative algoritmen

$x_{n+1}=x_{n}-(\Delta ^{2}f(x_{n}))^{-1}\Delta f(x_{n})$

kjend som Newtons metode i optimering.