KvasiNewtonin

Kvasi-Newtonin menetelmät ovat joukko optimointialgoritmeja, jotka parantavat Newtonin menetelmän suorituskykyä ilman tarvetta laskea Hessianin täydellistä todennäköisyyttä. Ne rakentavat iteratiivisesti Hessianin tai sen käänteisen likimäärän ja käyttävät sitä etsiessään minimoituvan pisteen gradientin muutoksen perusteella. Tämä lähestymistapa yhdistää Newtonin menetelmän nopeuden gradienttitason kustannuksia säästämällä.

Jokaisessa iteraatiossa määritellään s_k = x_{k+1} - x_k ja y_k = ∇f(x_{k+1}) - ∇f(x_k). Päivitys tuottaa uuden Hessianin tai sen käänteisen. Esimerkiksi BFGS-tyypin päivitys on:

H_{k+1} = H_k + (y_k y_k^T)/(s_k^T y_k) - (H_k y_k y_k^T H_k)/(y_k^T H_k y_k)

tai vastaavasti

B_{k+1} = B_k + (y_k y_k^T)/(s_k^T y_k) - (B_k s_k s_k^T B_k)/(s_k^T B_k s_k)

jossa s_k^T y_k > 0 varmistaa, että suuntauksella on laskevuusominaisuus.

Yleisesti käytetyimmät ovat DFP ja BFGS, joista BFGS on yleisesti suosituin sen numerinen vakaus ja tuloksellisuus. L-BFGS, rajoitettua muistia käyttävä muoto, soveltuu suurten mittaisten ongelmien ratkaisuun, koska se tarvitsee vain rajoitettua määrää gradientti- ja muutoshistorian arvoja.

Kvasi-Newtonin menetelmät soveltuvat pääasiassa epälineaaristen, gradientillisesti saatavien funktioiden minimointiin. Ne ovat laajasti käytössä koneoppimisessa, tilastotieteessä ja insinöörityön sovelluksissa sekä tieteellisissä optimointitehtävissä. Käytännössä ne hyödyntävät line searchia tai Wolfe-ehtoja varmistaakseen laskevuuden ja vakauden.