Recipe
Run backtracking line search from a starting alpha
Use when: you have a descent direction d^{(k)} and want a step size satisfying the Armijo condition without solving for the exact line-search minimizer
Goal: a step size \alpha_k certified by the Armijo condition, found in finitely many cheap checks
Taught in Backtracking line search
Quick recipe
-
1
Fix c_1\in(0,1) (small, e.g.\ 0.2) and \rho\in(0,1) (e.g.
0.5). Set \alpha=\bar\alpha, a generous starting guess (often 1).Example
For f(x,y)=x^2+10y^2 at (1.5,0.6), d=(-0.2,-0.8): start \alpha=1.5, c_1=0.2, \rho=0.5.
Why: starting generous means the accepted step won't be needlessly small — backtracking only ever shrinks, so a large starting point costs nothing but a few extra checks.
-
2
Compute \varphi(\alpha)=f(x^{(k)}+\alpha d^{(k)}) and the Armijo line \varphi(0)+c_1\alpha\varphi'(0); compare.
Example
\varphi(0)=5.85, \varphi'(0)=-10.2. At \alpha=1.5: \varphi(1.5)=f(1.2,-0.6)=1.44+3.6=5.04; line =5.85+0.2(1.5)(-10.2)=2.79. Since 5.04>2.79, Armijo FAILS.
Why: this is exactly Section 7's inequality — the only check backtracking ever runs.
-
3
On failure, set \alpha\leftarrow\rho\alpha and return to Step 2. On success, accept the current \alpha as \alpha_k.
Example
Shrink: \alpha=0.75. \varphi(0.75)=f(1.35,0)=1.8225; line =5.85+0.2(0.75)(-10.2)=4.32. Since 1.8225\le4.32, Armijo HOLDS — accept \alpha_k=0.75.
Why: the fixed shrink factor guarantees termination in finitely many steps, since Armijo holds for all sufficiently small alpha (Section 7).
Common mistakes
- Shrinking by a factor that changes between iterations instead of a FIXED \rho — the termination guarantee relies on a consistent, predictable shrink rate.
- Starting \bar\alpha too small "to be safe" — this wastes the whole point of backtracking (a generous first try) and risks landing on a needlessly short step, exactly Section 8's failure mode.
- Forgetting to recompute \varphi(\alpha) at the NEW, shrunk \alpha each time — the Armijo line itself doesn't change (it only depends on \varphi(0) and \varphi'(0)), but \varphi(\alpha) does.