inversion_ideas.minimize.backtracking_line_search

inversion_ideas.minimize.backtracking_line_search(phi, model, search_direction, *, contraction_factor=0.5, c_factor=0.5, maxiter=20, initial_step_length=1.0, phi_value=None, phi_gradient=None)

Implement the backtracking line search algorithm.

Parameters:

phibase.Objective

Objective function to which the line search will be applied.

model(n_params,) array

Current model.

search_direction: (n_params,) array

Vector used as a search direction.

contraction_factorfloat, optional

Contraction factor for the step length. Must be greater than 0 and lower than 1.

c_factorfloat, optional

The c factor used in the descent condition. Must be greater than 0 and lower than 1.

maxiterint, optional

Maximum number of line search iterations.

initial_step_lengthfloat, optional

Initial value for the step length.

phi_valuefloat or None, optional

Precomputed value of phi(model). If None, it will be computed. Pass a value to avoid retriggering a call of phi in case you’ve already called it.

phi_gradient(n_params,) array or None, optional

Precomputed value of phi.gradient(model). If None, it will be computed. Pass a value to avoid retriggering a call of phi.gradient in case you’ve already called it.

Returns:

step_lengthfloat or None

Alpha for which x_new = x0 + alpha * pk, or None if the line search algorithm did not converge.

n_iterationsint

Number of line search iterations.

Notes

Given an objective function \(\phi\) that is being iteratively minimized, a current model \(\mathbf{m}_k\) and a search direction \(\mathbf{p}_k\), the backtracking line search algorithm offers a way to choose the step length \(\alpha\) that we will take in the direction of \(\mathbf{p}_k\) to obtain the next model \(\mathbf{m}_{k+1}\):

\[\mathbf{m}_{k+1} = \mathbf{m}_k + \alpha_k \mathbf{p}_k\]

Ideally, the step length alpha_k should be choose such as the sufficient decrease and the curvature conditions are met. These are also know as the Wolfe conditions. Respectively:

\[\begin{split}\begin{aligned} \phi(\mathbf{m}_k + \alpha_k \mathbf{p}_k) &\le \phi(\phi(\mathbf{m}_k) + c_1 \alpha_k {\nabla\phi(\mathbf{m}_k)}^\text{T} \mathbf{p}_k \\ {\nabla\phi(\mathbf{m}_k + \alpha_k \mathbf{p}_k)}^\text{T} \mathbf{p}_k &\ge c_2 {\nabla\phi(\mathbf{m}_k)}^\text{T} \mathbf{p}_k \end{aligned}\end{split}\]

with \(0 < c_1 < c_2 < 1\).

The backtracking line search approach consists in disposing the curvature condition and choosing the candidate step lengths appropriately.

Note

We would like to avoid enforcing the curvature condition since it involves computing the gradient of \(\phi\) once per step length candidate. If computing the gradient of \(\phi\) for a given model is a costly operation, that could make the minimization algorithm to take considerable time.

The backtracking line search can be summarized in:

1. Choose an initial positive value for the step length. Usually this value is set to one.

2. Choose values \(\in (0, 1)\) for the contraction factor \(\rho\) and the factor \(c\).

3. Check if the condition \(\phi(\mathbf{m}_k + \alpha\mathbf{p}_k) \le \phi(\mathbf{m}_k) + c \alpha {\nabla\phi(\mathbf{m}_k)}^\text{T} \mathbf{p}_k\) holds.

   • If it does, then finish the algorithm. Use the current value of \(\alpha\) as the step length.

   • If it doesn’t, continue to next step.

4. Update the step length as \(\alpha \leftarrow \rho\alpha\).

References

Nocedal, J., & Wright, S. J. (1999). Numerical optimization. Springer. Page 41.