Mètodes quasi-Newton

Els mètodes quasi-Newton són mètodes utilitzats per trobar zeros o màxims i mínims locals de funcions, com a alternativa al mètode de Newton. Es poden utilitzar si el jacobià o el hessià no està disponible o és massa car per calcular-lo en cada iteració. El mètode "complet" de Newton requereix el jacobià per cercar zeros, o el hessià per trobar extrems.

Mètode de Newton per trobar zeros d'una funció $g$ de múltiples variables ve donada per $x_{n+1}=x_{n}-[J_{g}(x_{n})]^{-1}g(x_{n})$, on $[J_{g}(x_{n})]^{-1}$ és la inversa esquerra de la matriu jacobiana $J_{g}(x_{n})$ de $g$ avaluat per $x_{n}$.

En sentit estricte, qualsevol mètode que substitueixi el jacobià exacte $J_{g}(x_{n})$ amb una aproximació és un mètode quasi-Newton. Per exemple, el mètode d'acords (on $J_{g}(x_{n})$ es substitueix per $J_{g}(x_{0})$ per a totes les iteracions) és un exemple senzill. Els mètodes que es donen a continuació per a l'optimització fan referència a una subclasse important de mètodes quasi-Newton, mètodes secants.

Utilitzar mètodes desenvolupats per trobar extrems per trobar zeros no sempre és una bona idea, ja que la majoria dels mètodes utilitzats per trobar extrems requereixen que la matriu que s'utilitza sigui simètrica. Tot i que això és vàlid en el context de la recerca d'extrems, poques vegades s'aplica quan es busquen zeros. Els mètodes "bons" i "dolents" de Broyden són dos mètodes que s'utilitzen habitualment per trobar extrems que també es poden aplicar per trobar zeros. Altres mètodes que es poden utilitzar són el mètode d'actualització de columnes, el mètode d'actualització de columnes inversa, el mètode de mínims quadrats de quasi Newton i el mètode de mínims quadrats inversos de quasi Newton.

La cerca d'un mínim o màxim d'una funció de valor escalar no és altra cosa que la cerca dels zeros del gradient d'aquesta funció. Per tant, els mètodes quasi-Newton es poden aplicar fàcilment per trobar extrems d'una funció. En altres paraules, si $g$ és el gradient de $f$, després cercant els zeros de la funció de valors vectorials $g$ correspon a la cerca dels extrems de la funció escalar $f$; el jacobi de $g$ ara esdevé el Hessian de $f$. La principal diferència és que la matriu hessiana és una matriu simètrica, a diferència de la jacobiana quan es busquen zeros. La majoria dels mètodes quasi-Newton utilitzats en l'optimització exploten aquesta propietat.

En optimització, els mètodes quasi-Newton (un cas especial de mètodes de mètrica variable) són algorismes per trobar màxims i mínims locals de funcions. Els mètodes quasi-Newton es basen en el mètode de Newton per trobar el punt estacionari d'una funció, on el gradient és 0. El mètode de Newton suposa que la funció es pot aproximar localment com a quadràtica a la regió al voltant de l'òptim, i utilitza la primera i segona derivades per trobar el punt estacionari. En dimensions superiors, el mètode de Newton utilitza el gradient i la matriu de Hesse de segones derivades de la funció a minimitzar.