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
$\begingroup$
$\endgroup$
4
-
$\begingroup$ What if in equation the variable x is not a vector but a matrix? How should the Armijo rule be updated? $\endgroup$– Frank PukCommented Aug 23, 2017 at 15:22
-
1$\begingroup$ nothing changes. you should simply reshape your $X_k$-matrix into a (column) vector $x_k$. $\endgroup$– GoHokiesCommented Aug 23, 2017 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 PukCommented Aug 23, 2017 at 21:16
-
1$\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$– GoHokiesCommented Aug 24, 2017 at 12:05
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
8
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.
-
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$– cjordan1Commented May 21, 2013 at 7:13
-
1$\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$– cjordan1Commented May 21, 2013 at 7:16
-
2$\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$– user4933Commented Aug 8, 2013 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$ Commented Mar 17, 2016 at 10:51
-
1$\begingroup$ @JorisBierkens It sounds like you are confusing what the point of Armijo's rule is. It is not to provide a condition which gives the step that lands at exactly the minimum possible value along a direction. In higher dimensional problems, this isn't even that helpful because the minimum isn't along that direction at all; the direction itself requires updating alongside choosing a step size. $\endgroup$ Commented Jan 1, 2023 at 17:33
$\begingroup$
$\endgroup$
2
Five years later, this question is still valid.
Here (pages 16 and 17) you can find a great explanation, including an Algorithm.
References
- Michael Hintermüller. Nonlinear Optimization. Berlin School of Mathematics
-
1$\begingroup$ I have updated the link, the original was removed. If you google "bms-basic-NLP_120609.pdf" you will find multiple instances of the document. $\endgroup$ Commented May 19, 2021 at 5:33
-
$\begingroup$ In case someone cannot access the original course "Nonlinear Optimization" here is version I found mega.nz/file/… $\endgroup$ Commented May 12, 2022 at 13:59
$\begingroup$
$\endgroup$
The armijo rule is a condition for an appropriate step size $\alpha$ inside an iterative gradient optimization method, where the search direction is $p_k$ at current evaluation point $x_k$. It's just a condition, so it just tells you wether $\alpha$ is appropriate or not. Actually finding $\alpha$ is done in several different ways, one way is to do it iteratively for a fixed $x_k$: start with a large $\alpha$ (around ~1) and test it, if it fails, multiply it by a fixed factor (usually around $\rho \approx 0.5$), and test again, and repeat until the the condition is fulfilled.
Then you can update $x_{k+1} = f(x_k + \alpha * p_k)$ (which is not part of the armijo rule, it's the gradient method that uses the armijo rule for finding the step size) and search for a new step size again.
To make sense of the armijo rule, let's look at a minimization problem and set $p_k = -\nabla f(x_k)$ and first ignore the second term on the right side of the armijo rule. It then states $f(x_k + \alpha p_k) =f(x_k - \alpha \nabla f(x_k)) \leq f(x_k)$. This means that $\alpha$ must be such that going in the direction of the steepest decline of the local gradient actually lands us on a smaller value of the function.
Now to the second weird part: A linear approximation of the value of $f(x_k + \alpha p_k)$ can be obtained by $f(x_k) + \alpha \nabla f(x_k)^Tp_k$ (under the assumption that either $||p_k||_2 = 1$ or $||\nabla f(x_k)||_2 = 1$).
So in total, for a minimzation problem, the armijo rule is
$f(x_k + \alpha p_k) \leq f(x_k) + \beta \alpha \nabla f(x_k)^Tp_k$
Also, $p_k$ has to fulfill $\nabla f(x_k)^Tp_k < 0$, or else we're going to ascend the function. Which is the opposite way to where we want to go.
The armijo rule not only ensures that alpha is small enough to not increase the function, but also big enough to actually decrease the function more than the local linear approximation would decrease. Well, the local linear approximation times a factor $\beta < 1$, which ensures that such an $\alpha$ exists, because that is not at all given, for example if the function flattens out in all directions around $x_k$. Or also just when $f$ is linear, but i guess then one should use more appropriate optimization methods than an iterative gradient method. So $\beta$ is usually selected very small (around $10^{-4}$) to ensure such an $\alpha$ exists.
Also the selection of $\beta$ to be so small might have something to do with the fact that the right side is only a linear approximation of the function under the assumption that $||p_k||_2 = 1$ or $||\nabla f(x_k)||_2 = 1$, which is not at all the case in most instances. So i guess $\beta$ has to account for that too.
Also, note that for a Maximization Problem, the armijo rule is
$f(x_k + \alpha p_k) \geq f(x_k) + \beta \alpha \nabla f(x_k)^Tp_k$
And also $\nabla f(x_k)^Tp_k > 0$
To be honest, i don't see the benefit of the armijo rule over adaptive step size methods such as RMSprop or Adam that estimate the diagonal of the hessian with just one function evaluation per step $k$. Though, i might just not be familiar with certain classes of problems that the Armijo Rule is more helpful for.
