0
$\begingroup$

Overview

Line search typically consists of four stages:

  1. Direction: Search direction
  2. Initial Step Size: length to search along the line on the first sub-iteration
  3. Bracket: find an interval along the line that contains the minimum
  4. Selection: zoom in on the minimum

In non-linear line search routines it is often desirable to have inexact termination conditions so that the algorithm may be restarted at the direction stage at any point in these four stages. This prevents large amount of computation time being wasted on exact line minimisation. Here are some common tactics:

Reduction: $$f(\textbf{x}_k + \alpha \textbf{p}_k) \leq f(\textbf{x}_k) $$

Armijo: $$f(\textbf{x}_k + \alpha \textbf{p}_k) \leq f(\textbf{x}_k) + c_1 \alpha \nabla f(\textbf{x}_k)^T \textbf{p}_k $$

Curvature: $$\nabla f(\textbf{x}_k + \alpha \textbf{p}_k)^T \textbf{p}_k \geq c_2 \nabla f(\textbf{x}_k)^T \textbf{p}_k $$

Wolfe: (Both Armijo and Curvature)

Observation

An example can easily be thought of where the Armijo conditions (esp with a high $0<c_1<1$) exclude the minimum of the line search from the feasible solution. The simpler reduction case does not have this disadvantage.

Assume that we have bracketed our minimum $(a_l, a_u)$, and we are now zooming on the a better solution, the minimum is close to $a_u$, but is not in the Armijo feasible region. We are using the Wolfe termination conditions. Selection algorithm would put in a lot of work to push away from this minimum to instead find a feasible solution.

Question

Why is Armijo considered better than simple reduction in the literature? What are its advantages?

$\endgroup$
1
$\begingroup$

As a first remark, line search methods do not look for the global minimum of $f$ on the ray $x_k + \alpha p_k$. This can be only done in special cases (e.g. quadratic $f$). Moreover, the linesearch rules do not deliver an interval enclosing the global minimum on the ray, but an interval containing a point with sufficiently smaller function value.

Simple reduction is not enough to guarantee convergence. Armijo linesearch is the cheapest linesearch (it only needs function evaluations). Moreover, one can prove convergence of steepest descent and Newton methods usind Armijo linesearch.

$\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.