Když Hessián není: BFGS a Nelder-Mead
Newton chce druhé derivace a ty často nejsou k mání — buď je drahé je spočítat, nebo účelová funkce vůbec není vzorec, ale výsledek simulace či měření.
BFGS: zakřivení se dá odposlechnout
Sousední gradienty o zakřivení něco vědí. Když se udělá krok s a gradient se přitom změní o y, platí přibližně y ≈ H s — a to je informace, kterou lze sbírat. BFGS z ní postupně skládá odhad inverzního Hessiánu, takže krok je pak jen násobení maticí, žádné řešení soustavy:
Výsledek je superlineární konvergence bez jediné druhé derivace. Pro úlohy do řádu stovek proměnných je BFGS výchozí volba, a v téhle labce je to metoda, kterou používá multistart.
Podmínka sᵀy > 0 v kódu není kosmetika. Když neplatí, znamená to, že se zakřivení podél kroku chová nefyzikálně, a aktualizace by rozbila pozitivní definitnost odhadu. Tehdy se krok prostě přeskočí. A když se odhad přesto zkazí natolik, že vyrobí směr do kopce, restartuje se na jednotkovou matici — tedy na jeden krok obyčejného gradientního sestupu.
Nelder-Mead: bez derivací úplně
Simplex o n+1 vrcholech se plazí prostorem: nejhorší vrchol se zrcadlí přes těžiště ostatních, a podle toho, jak to dopadne, se navíc protáhne, stáhne nebo se celý simplex smrskne. Žádná derivace v tom není.
Je to pomalé a na hladké úloze výrazně horší než BFGS. Za to umí něco, co ostatní ne: funkci se zlomem, funkci z měření, funkci se šumem. Testy tady na něj pouštějí |x−1| + |y+2|, kde derivace v řešení neexistuje — a projde.
| metoda | co potřebuje | kdy sáhnout |
|---|---|---|
| Newton | gradient + Hessián | málo proměnných, levné derivace |
| BFGS | jen gradient | výchozí volba pro hladké úlohy |
| Nelder-Mead | jen hodnoty funkce | zlomy, šum, simulace, měření |