[Math] Backtracking line search algorithm – Why have non-zero alpha

convex optimizationgradient descentoptimization

Line search methods for convex optimization are of two main types

  1. Exact line search – explicit minimization $\min_\eta f(x+\eta \,\Delta x) $

  2. Inexact line search (Backtracking example) – Pick $\alpha \in (0,0.5), \beta \in (0,1), t=1$

while $f(x +t\,\Delta x) > f(x) + t \alpha x^T \, \nabla f(x) $:

$$t=\beta\cdot t$$

My question : Why is backtracking line search advantageous over a crude inexact minimization like the one below:

Set $\beta=.9, t=1$, check $f(x +t\,\Delta x)$,

If $f(x +t\,\Delta x) < f(x) $, terminate,
else $t=\beta\cdot t$

Why have an alpha parameter and complicate the termination condition like in the case of backtracking line search, the only thing it seems to guarantee is function decrease i.e $f(x+1)<f(x)$, but this can be done by the above simple crude procedure as well – discrete evaluations of $f(x +t\,\Delta x)$.

Best Answer

$ f(x_{k+1})<f(x_k) $ need not imply that the sequence $x_k$ converges, making such simplistic methods proposed above insufficient.

An example of such a non-convergent sequence is as below. enter image description here $f_k$ is decreasing, but the sequence of $x$ does not converge. This is taken from https://www.youtube.com/watch?v=8tqaXIM6kEE&t=2702s

Related Question