13
$\begingroup$

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

$\endgroup$

migrated from stats.stackexchange.com Mar 8 '13 at 20:27

This question came from our site for people interested in statistics, machine learning, data analysis, data mining, and data visualization.

  • $\begingroup$ What if in equation the variable x is not a vector but a matrix? How should the Armijo rule be updated? $\endgroup$ – Frank Puk Aug 23 '17 at 15:22
  • $\begingroup$ nothing changes. you should simply reshape your $X_k$-matrix into a (column) vector $x_k$. $\endgroup$ – GoHokies Aug 23 '17 at 15:48
  • $\begingroup$ That's where I got stuck. When $x_k$ becomes a matrix, the value on the left hand side ($f(x_k+\alpha p_k)$) is still a scalar. But the value on the right hand side is not - instead, it's a matrix ($f(x_k)$ is a scalar and $\beta\alpha∇f(x_k)^Tp_k$ is a matrix.) $\endgroup$ – Frank Puk Aug 23 '17 at 21:16
  • $\begingroup$ you will need to work with a vector, not a matrix. so you reshape your $N \times N$ matrix of control variables (I've denoted it by $X_k$) into a vector $x_k$ with $N^2$ elements. The search direction and the gradient will be also vectors with $N^2$ elements. this way both the RHS and LHS of the Armijo condition are scalars and can be compared. $\endgroup$ – GoHokies Aug 24 '17 at 12:05
19
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Rather than thinking of it as a tangent line you can also think of it as the first order Taylor expansion. In this case the $\beta$ merely ensures that such a step-size $\alpha$ exists. $\endgroup$ – cjordan1 May 21 '13 at 7:13
  • $\begingroup$ The reason this matters at all, i.e. why a "good" step is necessary, is that many optimization schemes will converge slower, as Paul says, or might not converge at all. So line searches--which come in several varieties, Armijo is just the most popular--can be used to give algorithms more robust convergence properties. $\endgroup$ – cjordan1 May 21 '13 at 7:16
  • 1
    $\begingroup$ Paul: your explanation is incomplete. This inequality alone does not guarantee the 'sufficient' decrease. In fact, you can have alpha=0, and still satisfies the inequality you wrote. An important feature is Armijo rule is to bound the step size away from zero, which is done by another inequality: f(gamma * x_new)-f(x_old) > beta * (gamma * x_new-x_old)^T * grad(f(x_old)) $\endgroup$ – user4933 Aug 8 '13 at 10:40
  • $\begingroup$ After reading this discussion I am still confused about Armijo rule. Consider $f(x) = x^2$, $x_k = -1$ and $p_k = -2$ (the steepest descent direction). The choice of $\alpha$ which minimizes $f(x_k + \alpha p_k)$ is $\alpha = 1/2$. However, if $\beta > 1/2$, then $f(x_k + 1/2 p_k) = 0 > 1 - 2 \beta = f(x_k) + \beta \alpha f'(x_k) p_k$. So Armijo's rule is not satisfied at the actual minimum for this choice of $\beta$. In particular if you have a line search which iteratively searches for a local minimum, it may end up in an infinite loop. Am I missing something? $\endgroup$ – Joris Bierkens Mar 17 '16 at 10:51
  • $\begingroup$ To add to my above comment, you might say that $\beta > 1/2$ is much too large (Nocedal, Wright mention the common choice $\beta = 10^{-4}$), but on the other hand, for any choice of $\beta$ you can construct an example as above. $\endgroup$ – Joris Bierkens Mar 17 '16 at 10:58
-1
$\begingroup$

Five years later, this question is still valid.

Here (pages 16 and 17) you can find a great explanation, including an Algorithm.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.