Gauss-Newton a Powellova past

Tohle je statická kopie kapitoly pro vyhledávače. Interaktivní verze má animované obrázky, kontrolní otázky a tlačítka, která příklad načtou do kalkulačky.

Nelineární nejmenší čtverce jsou nejčastější optimalizační úloha v celé robotice: máme model, máme měření, hledáme parametry. Účelová funkce má vždycky týž tvar — součet čtverců reziduí:

F(x) = ½ ‖f(x)‖² = ½ Σ fᵢ(x)²ta jedna polovina má důvod, viz níže

Ten tvar se dá využít. Gradient i Hessián se dají napsat přes Jakobián reziduí:

∇F = Jᵀfa právě kvůli té ½ tu není dvojka

∇²F = JᵀJ + Σ fᵢ ∇²fᵢdruhý člen je ten drahý

Gauss-Newton je Newton, který ten druhý člen zahodí. Je to výhodný obchod, protože JᵀJ dostaneme z prvních derivací zadarmo — a člen, který zmizel, je násobený rezidui fᵢ. Když jsou rezidua v řešení malá, nechybí skoro nic:

(JᵀJ) h = −JᵀfGauss-Newtonův krok

A tady je ta past

Když rezidua v řešení malá nejsou — nebo když je Jakobián v řešení singulární — ten zahozený člen chybí a metoda může dojít někam úplně jinam. Powell to v roce 1970 ukázal na příkladu, který se dá zapsat na dva řádky:

f(x) = [ x₁ , 10x₁/(x₁+0,1) + 2x₂² ]Powell 1970; jediné řešení je x = 0

Z bodu [3, 1] s přesným line searchem Gauss-Newton konverguje k [1,8016, 0]. Tam reziduum není nula, takže to není řešení — a metoda se přesto zastaví a tváří se spokojeně.

Tohle je nejpoučnější selhání v celém oboru, a to hned dvakrát. Zaprvé ukazuje, že Gauss-Newton není spolehlivý. Zadruhé — a to je horší — ukazuje, že lepší line search může věci zhoršit: s přesným hledáním metoda uvázne, protože se dokonale zabydlí ve špatném směru. Solver tenhle příklad počítá a testy ověřují, že skončí u 1,8016 ± 0,003, zatímco tlumené metody z téhož startu dojdou do nuly.

Co se s tím dělá

Nic z toho nevede k zahození Gauss-Newtona — vede to k jeho tlumení. Přesně o tom je následující kapitola: přidat k JᵀJ člen, který v nejistých situacích krok zkrátí a otočí ke gradientu. Výsledkem je Levenberg-Marquardt, a ten Powellovu past projde.