Optimalizace, kterou už děláte
Polovina téhle akademie už optimalizuje, jen o tom nemluví. KineLab řeší inverzní kinematiku tlumenými nejmenšími čtverci — a to je Levenberg-Marquardtova metoda, jen pod jiným jménem. VisionLab hledá parametry kamery minimalizací reprojekční chyby. FilterLab má Kalmanův filtr, což jsou rekurzivní nejmenší čtverce. A ladění regulátoru v ControlLabu je hledání minima, i když ho nikdo tak nenazve.
Tahle labka je ta mašina pod nimi, napsaná jednou a pořádně ověřená.
Jedna myšlenka, ze které plyne všechno ostatní
Účelovou funkci neumíme minimalizovat. Umíme minimalizovat její lokální model — jednoduchou náhradu platnou kousek kolem bodu, kde zrovna stojíme. Celý obor je pak jen dvě otázky: jaký model a jak daleko mu věřit.
| metoda | model | jak se vyjádří důvěra |
|---|---|---|
| nejstrmější spád | rovina | délkou kroku |
| Newton | kvadratika | věří celému kroku |
| Gauss-Newton | linearizovaná rezidua | věří celému kroku |
| Levenberg-Marquardt | kvadratika + tlumení μ | skrytě, hodnotou μ |
| dog-leg | kvadratika + poloměr Δ | otevřeně, hodnotou Δ |
To je celá taxonomie. Zbytek je účetnictví.
Ověření nezávisle na metodě: ‖∇f‖ = 0,000000, je to minimum · konvergovalo
Proč zrovna tohle údolí
Rosenbrockova funkce vypadá jako banán a je zlomyslná přesně tam, kde na tom záleží: sestoupit do údolí je triviální, ale dojít po jeho dně je těžké, protože dno je zahnuté. Metoda, která se dívá jen na gradient, se od jedné stěny odráží ke druhé a postupuje po milimetrech. Metoda, která si všímá zakřivení, zatáčí s údolím.
Poznámka k tomu, čemu se tady říká „minimum": všechny metody v téhle labce hledají lokální minimum, tedy bod, pod který se nedá dostat malým krokem. To, že je někde jinde ještě hlubší, žádná z nich nezjistí — a nezjistí to ani žádná levná metoda. Kapitola o čtyřech minimech ukazuje, jak moc to vadí.