2
$\begingroup$

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

1 Answers 1

1

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.

  • 0
    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?2016-03-17