2
$\begingroup$

Does a local minimum of a function always satify the Armijo rule?

$\endgroup$

1 Answer 1

1
$\begingroup$

Assuming that the function $f$ is continuous (and so $\nabla f$ is defined), then the Armijo rule can't be satisfied as an equality for a global minimum. That is you can rewrite the rule as:
$$f(\mathbf{x}_k+\alpha_k\mathbf{p}_k)\leq f(\mathbf{x}_k)+c_1\alpha_k\mathbf{p}_k^{\mathrm T}\nabla f(\mathbf{x}_k) = f(\mathbf{x}_k)$$
since $\nabla f(\mathbf{x}_k)=0$, but the LHS is larger than the RHS because the point $\mathbf{x}_k$ is a minimum. But if the minimum is only local, then you could meet the condition by arranging for the step to be to a lower minimum.

$\endgroup$
1
  • $\begingroup$ After reading this discussion I am still confused about the 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 $c_1>1/2$, then $f(x_k+\alpha p_k)=0>1−2 c_1 =f(x_k)+c_1 \alpha f′(x_k)p_k$. So Armijo's rule is not satisfied at the actual minimum for this choice of $c_1$. 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$ Mar 17, 2016 at 11:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .