Line Search Methods

Use step-length selection strategies to ensure descent and globalization for gradient-based optimizers.

Line search augments gradient directions with chosen step sizes to guarantee sufficient decrease and convergence. Given a current iterate xk\mathbf{x}_k and descent direction pk\mathbf{p}_k, we seek αk>0\alpha_k > 0 solving xk+1=xk+αkpk\mathbf{x}_{k+1} = \mathbf{x}_k + \alpha_k \mathbf{p}_k. Wolfe conditions balance sufficient decrease, f(xk+αkpk)≤f(xk)+c1αk∇f(xk)⊤pkf(\mathbf{x}_k + \alpha_k \mathbf{p}_k) \le f(\mathbf{x}_k) + c_1 \alpha_k \nabla f(\mathbf{x}_k)^\top \mathbf{p}_k, and curvature, ∇f(xk+αkpk)⊤pk≥c2∇f(xk)⊤pk\nabla f(\mathbf{x}_k + \alpha_k \mathbf{p}_k)^\top \mathbf{p}_k \ge c_2 \nabla f(\mathbf{x}_k)^\top \mathbf{p}_k. These safeguards tame Newton and quasi-Newton steps, which appear in Direct Transcription and NMPC Overview.

Backtracking search provides a simple recipe: start with α=1\alpha = 1 and shrink until Armijo decrease appears. More sophisticated approaches (zoom, cubic interpolation) refine α\alpha based on derivative information. In constrained settings, projected line search respects feasibility while reusing the same sufficient decrease logic, linking back to KKT multipliers in Karush-Kuhn-Tucker Conditions. Trust-region methods offer an alternative globalization strategy by capping step norms; they interact with line search when implementing hybrid solvers inside Policy Gradient Methods.

import numpy as np

def backtracking(f, grad_f, x, p, alpha=1.0, rho=0.5, c=1e-4):
    while f(x + alpha * p) > f(x) + c * alpha * grad_f(x).dot(p):
        alpha *= rho
    return alpha

Convergence guarantees rely on Lipschitz continuity of gradients and descent directions satisfying ∇f(xk)⊤pk<0\nabla f(\mathbf{x}_k)^\top \mathbf{p}_k < 0. Monitoring these dot products is a practical diagnostic; if they turn positive, the direction stops being a descent direction, often signaling that Hessians or approximations have lost positive definiteness. In NMPC shooting solvers and Actor-Critic Architectures, adaptive line searches help balance exploitation of curvature with numerical stability.

See also

Nonlinear Optimization — 1 of 1
PrevNo entryNextNo entry