Jak dlouhý krok: Armijova podmínka
Směr sám o sobě nestačí — pořád je potřeba říct, jak daleko po něm jít. Nabízí se najít podél toho směru přesné minimum. Je to nápad, který se skoro nikdy nevyplatí: stojí to spoustu vyhodnocení funkce a ten směr se stejně za chvíli změní.
Co se opravdu potřebuje, je dost velký pokles. Přesně to říká Armijova podmínka:
Vpravo je přímka o něco méně strmá než tečna. Krok se přijme, když se funkce dostane pod ni. A hledá se tak, že se začne s α = 1 a půlí se, dokud podmínka neplatí — proto „backtracking".
Podmínka nežádá nejlepší α — jen dost velký pokles. Přísnější c₁ hledá déle a nezaručuje lepší výsledek.
Proč zrovna 10⁻⁴
Vypadá to jako podivně malé číslo a je za tím záměr. Podmínka nemá krok vybírat, má jen vyloučit kroky, které skoro nic nepřinesly. Kdyby bylo c₁ velké, odmítala by i dobré dlouhé kroky a metoda by zbytečně ustupovala. Prakticky se c₁ nikdy nedolaďuje.
Armijova podmínka sama o sobě nestačí k důkazu konvergence: splní ji i posloupnost kroků, které se zkracují tak rychle, že se nikam nedojde. Proto teorie přidává druhou, Wolfeho podmínku na zakřivení, která zakazuje kroky příliš krátké. V praxi s půlením a startem od α = 1 tenhle případ prakticky nenastane, takže sem druhá podmínka není zavedená — a je poctivé to říct, ne to zamlčet.
Jedna past, kterou je vidět v testech
Když směr nemíří dolů (skalární součin s gradientem není záporný), žádné zkracování nepomůže. Solver to pozná a řekne to, místo aby půlil šedesátkrát a vrátil nulu. U Newtonovy metody se to stane vždy, když je Hessián indefinitní — a je to signál, že se má tlumit, ne že se má hledat jinak.