I have this confusion about Armijo rule used in line search. I was reading back tracking line search but didn't get what this Armijo rule is all about. Can anyone elaborate what Armijo rule is? The wikipedia doesn't seem to explain well. Thanks
Once you obtain a descent direction $p$ for your objective function $f(x)$, you need to pick a "good" step length. You don't want to take a step that is too large such that the function at your new point is larger than your current point. At the same time, you don't want to make your step too small such that it takes forever to get to converge.
Armijo's condition basically suggests that a "good" step length is such that you have "sufficient decrease" in $f$ at your new point. The condition is mathematically stated as $$f(x_k+\alpha p_k)\leq f(x_k)+\beta\alpha\nabla f(x_k)^Tp_k$$ where $p_k$ is a descent direction at $x_k$ and $\beta\in(0,1)$.
The intuition behind this is that the function value at the new point $f(x_k+\alpha p_k)$ should be under the reduced "tangent line" at $x_k$ in the direction of $p_k$. See Nocedal & Wright's book "Numerical Optimization". In chapter 3, there's an excellent graphical description of armijo's sufficient decrease condition.
Five years later, this question is still valid.
Here (pages 16 and 17) you can find a great explanation, including an Algorithm.