# Inexact Line Search

The strategy of inexact line search is practical and has a significant geometric interpretation:

## 1 Sufficient Decrease

Consider a scalar function \phi(\alpha) at a point x_k:

\phi(\alpha) = f(x_k - \alpha\nabla f(x_k)), \alpha \geq 0

The first-order approximation of \phi(\alpha) near \alpha = 0 is:

\phi(\alpha) \approx f(x_k) - \alpha\nabla f(x_k)^\top \nabla f(x_k)

The inexact line search condition, known as the Armijo condition, states that \alpha should provide sufficient decrease in the function f, satisfying:

f(x_k - \alpha \nabla f (x_k)) \leq f(x_k) - c_1 \cdot \alpha\nabla f(x_k)^\top \nabla f(x_k)

for some constant c_1 \in (0,1). Note that setting c_1 = 1 corresponds to the first-order Taylor approximation of \phi(\alpha). However, this condition can accept very small values of \alpha, potentially slowing down the solution process. Typically, c_1 \approx 10^{−4} is used in practice.

Example

If f(x) represents a cost function in an optimization problem, choosing an appropriate c_1 value is crucial. For instance, in a machine learning model training scenario, an improper c_1 might lead to either very slow convergence or missing the minimum.

Question

How does the choice of c_1 affect the convergence speed in optimization problems?

## 2 Goldstein Conditions

Consider two linear scalar functions \phi_1(\alpha) and \phi_2(\alpha):

\phi_1(\alpha) = f(x_k) - c_1 \alpha \|\nabla f(x_k)\|^2

\phi_2(\alpha) = f(x_k) - c_2 \alpha \|\nabla f(x_k)\|^2

The Goldstein-Armijo conditions locate the function \phi(\alpha) between \phi_1(\alpha) and \phi_2(\alpha). Typically, c_1 = \rho and c_2 = 1 - \rho, with $(0.5, 1)$.

## 3 Curvature Condition

To avoid excessively short steps, we introduce a second criterion:

-\nabla f (x_k - \alpha \nabla f(x_k))^\top \nabla f(x_k) \geq c_2 \nabla f(x_k)^\top(- \nabla f(x_k))