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 , altså baserer han seg på ei minimering av  i staden for ei minimering av  som i newtons metode i kalkulus.

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

I høvet der  berre er ein funksjon av ein variabel, så er  den deriverte til funksjonen  og  er den dobbeltderiverte. I det høvet der  er ein fleirvariabels funksjon så er  kjend som gradienten av   og  kjend som hessematrisa for .  er inversen av denne hessematrisa. 

Under særskilde føresetnadar bundne av valet av startpunkt , så vil følgja  konvergera mot løysinga av likninga , altså er  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  i ein iterativ descentalgoritme, gjeven som:

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å  for å utleia newtonsteget .

Ei andreordens taylorpolynomtilnærming for funksjonen  er:

Den deriverte av tilnærminga er:

Og ein minimiserer denne funksjonen ved å løysa:

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

Som gjev den iterative algoritmen

kjend som Newtons metode i optimering.
Kategori:Matematisk optimalisering
Kategori:Algoritmar