Newtons metode i optimering

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

Definisjon[endre | endre wikiteksten]

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[endre | endre wikiteksten]

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.