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 ${\displaystyle f}$, altså baserer han seg på ei minimering av ${\displaystyle \Delta f(x)}$ i staden for ei minimering av ${\displaystyle f(x)}$ som i newtons metode i kalkulus.

Definisjon

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

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

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

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

${\displaystyle 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å ${\displaystyle h}$ for å utleia newtonsteget ${\displaystyle h}$.

Ei andreordens taylorpolynomtilnærming for funksjonen ${\displaystyle f}$ er:

${\displaystyle 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:

${\displaystyle {\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:

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

Med omsyn på h, som gjev newtonsteget ${\displaystyle h}$ i algoritmen:

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

Som gjev den iterative algoritmen

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

kjend som Newtons metode i optimering.