QuasiNewtonmetoder

Quasi-Newtonmetoder er en gruppe optimeringsmetoder som søker minimum av en funksjon ved å iterativt oppdatere en tilnærming til den inverse Hessian, eller Hessianen, uten å beregne hele andresordningen i hver iterasjon. Ideen bygger på Newtons metode, men i stedet for å beregne og invert Hessianen fra bunnen av brukes en oppdateringsregel som baserer seg på gradientendringene mellom påfølgende iterasjoner. Dette gir ofte raskere beregninger og bedre numerisk stabilitet enn en full Newton-tilnærming, særlig i mellomstore til store problemstillinger.

En vanlig implementasjon er BFGS-algoritmen, som oppdaterer den inverse Hessian H_k. Oppdateringen er H_{k+1} = H_k + (y_k y_k^T)/(s_k^T y_k) - (H_k s_k s_k^T H_k)/(s_k^T H_k s_k), der s_k = x_{k+1} - x_k og y_k = ∇f(x_{k+1}) - ∇f(x_k). Oppdateringene er designet slik at hvis den forrige matrisen var positiv definit, og s_k^T y_k > 0, så blir den nye inverse Hessianen også positiv definit, noe som gir stabile og berettede søketrinn.

L-BFGS er en begrenset hukommelsesversjon som passer godt for store dimensjoner ved å lagre et begrenset antall s_k og y_k-par og bruke dem indirekte for å beregne neste trinn. Mange quasi-Newtonmetoder kombineres med linjesøk eller trust-region-rammer for å sikre at hvert trinn gir fremgang og at metodens globale konvergens egenskaper beholdes. Quasi-Newtonmetoder brukes bredt i uavhengige og statistiske beregninger, ingeniørvitenskap og maskinlæring, spesielt for ukonstrainerte optimeringsproblemer.