Kvasi-Newtonilaiset menetelmät

Kvasinewtonilaiset menetelmät ovat optimointimenetelmiä , jotka perustuvat gradientin muutoksen havaintojen perusteella kerättyyn tiedon keräämiseen tavoitefunktion kaarevuudesta , mikä eroaa olennaisesti Newtonin menetelmistä . Kvasi-Newtonin menetelmien luokka eliminoi Hessenin matriisin eksplisiittisen muodostumisen ja korvaa sen jollain approksimaatiolla.

Kuvaus

Laajennetaan alkuperäisen funktion gradienttia Taylor-sarjassa algoritmin seuraavan askeleen potenssien seuraavan approksimaatiopisteen läheisyydessä : ${\vec {g}}({\vec {x}}_{k})$ ${\vec {x}}_{k}$ ${\vec {s}}_{k}$

{\vec {g}}({\vec {x}}_{k}+{\vec {s}}_{k})\noin {\vec {g}}({\vec {x}}_ {k})+G({\vec {x}}_{k}){\vec {s}}_{k}

Tällöin Hessenin matriisin estimaatin tulee tyydyttää yhtäläisyys: $B_{{k+1}}$

B_{{k+1}}{\vec {s}}_{k}={\vec {y}}_{k}

missä ${\vec {y}}_{k}={\vec {g}}({\vec {x}}_{k}+{\vec {s}}_{k})-{\vec {g }} }}({\vec {x}}_{k})$

tätä ehtoa kutsutaan kvasi-newtonilaiseksi .

Jokaisessa iteraatiossa seuraava hakusuunta määritetään painikkeella ja matriisi päivitetään äskettäin saaduilla kaarevuustiedoilla: $B_{k}$ ${\vec {p}}_{k}$ $B$

B_{k}{\vec {p}}_{k}=-{\vec {g}}({\vec {x}}_{k})

B_{{k+1}}=B_{k}+U_{k}

jossa on matriisi, joka luonnehtii seuraavassa vaiheessa käyttöönotettua korjausta. $U_k$

Identiteettimatriisia käytetään alustavana approksimaationa , joten ensimmäinen suunta osuu täsmälleen jyrkimmän laskusuunnan kanssa . $B_{0}$ ${\vec {p}}_{0}$

Single Rank Muutos

Algoritmin yksi askel antaa tietoa kaarevuudesta yhdessä suunnassa, joten matriisin sijoitusta pidetään pienenä ja jopa yhtenäisenä: $U_k$

B_{{k+1}}=B_{k}+{\vec {u}}{\vec {v}}^{T}

missä ja ovat jotkin vektorit. ${\vec {u}}$ $\vec{v}$

Sitten kvasi-Newtonin ehto saa muodon:

(B_{k}+{\vec {u}}{\vec {v}}^{T}){\vec {s}}_{k}={\vec {y}}_{k}

{\vec {u}}({\vec {v}}^{T}{\vec {s}}_{k})={\vec {y}}_{k}-B_{k}{\ vec{s}}_{k}

Olettaen, että edellinen matriisi seuraavassa vaiheessa ei täytä kvasi-Newtonin ehtoa (eli ero oikealla puolella ei ole nolla) ja että vektori ei ole ortogonaalinen kohtaan , saadaan lauseke ja : $B_{k}$ $\vec{v}$ ${\vec {s}}_{k}$ ${\vec {u}}$ $B_{{k+1}}$

{\vec {u}}={\frac {1}{{\vec {v}}^{T}{\vec {s}}_{k}}}({\vec {y}}_{k }-B_{k}{\vec {s}}_{k})

B_{{k+1}}=B_{k}+{\frac {1}{{\vec {v}}^{T}{\vec {s}}_{k}}}({\vec { y}}_{k}-B_{k}{\vec {s}}_{k}){\vec {v}}^{T}

Hessenin matriisin symmetriasta johtuen vektori on otettu kollineaariseksi : $\vec{v}$ ${\vec {u}}$

B_{{k+1}}=B_{k}+{\frac {1}{({\vec {y}}_{k}-B_{k}{\vec {s}}_{k}) ^{T}{\vec {s}}_{k}}}({\vec {y}}_{k}-B_{k}{\vec {s}}_{k})({\vec {y}}_{k}-B_{k}{\vec {s}}_{k})^{T}

Tuloksena olevaa yhtälöä kutsutaan ykköstason symmetriseksi kaavaksi .

Sijoita kaksi muutosta

Yksi tapa rakentaa toisen asteen korjauksia on muodostaa konvergentti matriisien sarja . Ota alkuarvoksi , laske kaavalla: $B^{{(j)}}$ $B^{{(0)}}$ $B_{k}$ $B^{{(1)}}$

B^{{(1)}}=B^{{(0)}}+{\frac {1}({\vec {v}}^{T}{\vec {s}}_{k}} }({\vec {y}}_{k}-B^{{(0)}}{\vec {s}}_{k}){\vec {v}}^{T}

Sitten se on symmetrisoitu:

B^{{(2)}}={\frac {B^{{(1)}}+B^{{(1)T}}}{2}}

Tuloksena oleva matriisi ei kuitenkaan enää täytä kvasi-Newtonin ehtoa. Tämän korjaamiseksi toimenpide toistetaan. Tämän seurauksena -: nnessa vaiheessa: $j$

B^{{(2j+1)}}=B^{{(2j)))+{\frac {1}{{\vec {v}}^{T}{\vec {s}}_{k ))}({\vec {y}}_{k}-B^{{(2j))){\vec {s}}_{k}){\vec {v}}^{T}

B^{{(2j+2)}}={\frac {B^{{(2j+1)}}+B^{{(2j+1)T}}}{2}}

Tämän sarjan raja on:

B_{{k+1}}=B_{k}+{\frac {1}{{\vec {v}}^{T}{\vec {s}}_{k}}}[({\vec {y}}_{k}-B_{k}{\vec {s}}_{k}){\vec {v}}^{T}+{\vec {v}}({\vec {y }}_{k}-B_{k}{\vec {s}}_{k})^{T}]-{\frac {({\vec {y}}_{k}-B_{k} {\vec {s}}_{k})^{T}{\vec {s}}_{k}}{({\vec {v}}^{T}{\vec {s}}_{ k})^{2))}{\vec {v}}{\vec {v}}^{T}

Kun valitset erilaisia (ei-ortogonaalisia ), saadaan erilaisia kaavoja matriisin uudelleenlaskentaa varten : $\vec{v}$ ${\vec {s}}_{k}$ $B$

${\vec {v}}={\vec {y}}_{k}-B_{k}{\vec {s}}_{k}$ johtaa ykkösluokan symmetriseen kaavaan ;
${\vec {v}}={\vec {s}}_{k}$ johtaa symmetriseen Powell-Broydenin kaavaan (PSB) ;
${\vec {v}}={\vec {y}}_{k}$ johtaa symmetriseen Devidon-Fletcher-Powell (DFP) -kaavaan :

B_{k+1}=B_{k}-{\frac {1}({\vec {s}}_{k}^{T}B_{k}{\vec {s}}_{ k}}}B_{k}{\vec {s}}_{k}{\vec {s}}_{k}^{T}B_{k}^{T}+{\frac {1}{ {\vec {y}}_{k}^{T}{\vec {s}}_{k}}}{\vec {y}}_{k}{\vec {y}}_{k} ^{T}+({\vec {s}}_{k}^{T}B_{k}{\vec {s}}_{k}){\vec {\omega }}_{k}{ \vec {\omega }}_{k}^{T}

missä ${\vec {\omega }}_{k}={\frac {1}({\vec {y}}_{k}^{T}{\vec {s}}_{k}}}{\ vec {y}}_{k}-{\frac {1}{{\vec {s}}_{k}^{T}B_{k}{\vec {s}}_{k}}}B_ {k}{\vec {s}}_{k}$

On helppo tarkistaa, että se on ortogonaalinen . Näin ollen termin lisääminen ei riko kvasi-Newtonin ehtoa eikä symmetriaehtoa. Siksi tehtiin useita teoreettisia tutkimuksia, joissa viimeinen termi skaalattiin parhaan likiarvon saamiseksi. Tämän seurauksena omaksuttiin näkemys, että paras vaihtoehto on se, joka vastaa viimeisen lukukauden täydellistä poissaoloa. Tämä muunnosvaihtoehto tunnetaan Broyden-Fletcher-Goldfarb-Shanno- kaavana (BFGS) : ${\vec {\omega ))_{k}$ ${\vec {s}}_{k}$ ${\vec {\omega }}_{k}{\vec {\omega }}_{k}^{T}$

B_{k+1}=B_{k}-{\frac {1}({\vec {s}}_{k}^{T}B_{k}{\vec {s}}_{ k}}}B_{k}{\vec {s}}_{k}{\vec {s}}_{k}^{T}B_{k}^{T}+{\frac {1}{ {\vec {y}}_{k}^{T}{\vec {s}}_{k}}}{\vec {y}}_{k}{\vec {y}}_{k} ^{T}

Kirjallisuus

Gill F., Murray W., Wright M. Käytännön optimointi = käytännön optimointi.

Optimointimenetelmät _
Yksiulotteinen	kultaisen leikkauksen menetelmä Dikotomia Paraabeli menetelmä Verkkohaku Yhtenäinen lohkohakumenetelmä Fibonaccin menetelmä Kolminkertainen haku Piyavsky menetelmä Vahva menetelmä
Nolla järjestys	Gaussin menetelmä Nelder-Meadin menetelmä Hook-Jeeves -menetelmä Rosenbrockin menetelmä Powellin menetelmä
Ensimmäinen tilaus	gradienttilasku Zeutendijkin menetelmä Koordinaattilasku Konjugaattigradienttimenetelmä Kvasi-Newtonilaiset menetelmät Levenberg-Marquardt-algoritmi
toinen tilaus	Newtonin menetelmä Newton-Raphsonin menetelmä Broyden-Fletcher-Goldfarb-Shanno-algoritmi (BFGS)
Stokastinen	Monte Carlon menetelmä Simuloitu hehkutus Evoluutioalgoritmit differentiaalinen evoluutio Ant algoritmi Hiukkasparvimenetelmä Mehiläisyhdyskunnan algoritmi Satunnainen kävelymenetelmä
Lineaariset ohjelmointimenetelmät _	Yksinkertainen menetelmä Gomorin algoritmi Ellipsoidi menetelmä Potentiaalinen menetelmä
Epälineaariset ohjelmointimenetelmät	Jaksottainen neliöllinen ohjelmointi