KvasiNewtonmenetelmien

Kvasi-Newtonmenetelmät ovat optimointialgoritmeja, joita käytetään funktion minimin tai maksimin löytämiseen. Ne ovat Newtonin menetelmän muunnoksia, jotka pyrkivät ratkaisemaan epälineaarisia yhtälöitä. Newtonin menetelmä vaatii funktion toisen derivaatan matriisin, Hessen matriisin, laskemista ja kääntämistä jokaisella iteraatiolla, mikä voi olla laskennallisesti raskasta ja vaikeaa, erityisesti suurissa ongelmissa. Kvasi-Newtonmenetelmät kiertävät tämän ongelman approksimoimalla Hessen matriisia tai sen käänteismatriisia.

Tärkeimpiä kvasi-Newtonmenetelmiä ovat BFGS (Broyden–Fletcher–Goldfarb–Shanno) ja DFP (Davidon–Fletcher–Powell). Nämä menetelmät päivittävät Hessen matriisin approksimaatiota jokaisella iteraatiolla käyttämällä gradienttitietoa edellisiltä ja nykyiseltä iteraatiopisteiltä. Päivitys tehdään siten, että approksimaatio säilyttää tietyt matemaattiset ominaisuudet, kuten symmetrisyyden ja positiivisen definiittisyyden, jotka ovat tärkeitä konvergenssin takaamiseksi. Approksimaation päivityskaava perustuu sekanttiehtoon.

Kvasi-Newtonmenetelmien etuna on, että ne eivät vaadi toisten derivaattojen laskemista, ja ne konvergoituvat usein nopeammin kuin gradienttimenetelmät. Ne ovat erityisen hyödyllisiä, kun funktion lauseke on monimutkainen tai kun Hessen matriisin laskeminen on epäkäytännöllistä. Ne ovat yleisesti käytettyjä koneoppimisessa ja operaatiotutkimuksessa. Menetelmät ovat tyypillisesti superlineaarisesti konvergoivia, eli niiden konvergenssinopeus on nopeampi kuin lineaarinen, mutta ei välttämättä yhtä nopea kuin Newtonin menetelmän neliöllinen konvergenssi.