Line Searchers#
Introduction#
Line searchers (LineSearcher) determine how far to move along a search direction
at each optimization iteration. Gradient-based Optimizers and proximal methods
(FISTA, inner SDMM loops) call a line searcher after computing \(d_k\).
Line-search hierarchy (LineSearcher and concrete search methods).#
Mathematical foundation#
The parameter update is
where \(d_k\) is the search direction (e.g. \(-g_k\) for steepest descent or a conjugate-gradient direction) and \(\alpha_k\) is chosen by the line searcher.
The line search balances sufficient decrease, computational cost (function and gradient evaluations along the ray), and numerical stability.
Step size geometry: too short, too long, and why seeders help#
On a smooth objective, each iterate moves from \(x_k\) along the ray \(x_k + \alpha d_k\). For a quadratic with elongated level sets (ill-conditioned Hessian), the level curves are ellipses and the ideal step depends on curvature along \(d_k\). A convergence trajectory plot (optimization path on level curves) shows those ellipses and the sequence \(x_0, x_1, \ldots\) connected by arrows.
Illustrative optimization paths on level curves of an ill-conditioned quadratic: (a) step too small — many short moves (slow zig-zag); (b) step too large — dashed jumps that overshoot and oscillate across the valley; (c) seeded / near-optimal steps — smooth, accelerated path toward \(x^*\). Illustrative trajectories (not live optimizer output).#
Step too small
The iterate still decreases \(f\), but progress toward \(x^*\) is slow.
On elongated valleys you see a zig-zag or crawling path (panel a).
Each optimizer iteration is cheap, but you need many outer iterations to converge.
Goldstein-style search may expand the step when the lower bound fails.
Step too large
The trial point can overshoot across level curves or even increase \(f\).
Backtracking Armijo halves (or scales by
decrease) \(\alpha\) until the sufficient-decrease condition holds (panel b: dashed = rejected trial).Every backtrack costs an extra objective evaluation along the ray — expensive when each evaluation is a full visibility transform.
Step in a good range
One or few trials satisfy Armijo (or Goldstein’s bracket), so the line search returns quickly.
The outer optimizer spends time on useful gradient/CG/L-BFGS work, not repeated \(f(x)\).
Role of step size seeders
Without a seeder, LineSearcher starts from a fixed default (often step=1.0), which
may be far from the acceptable range on the first backtracking loop. A
Step Size Seeders estimates \(\alpha_k^{(0)}\) from recent gradients (Barzilai–Borwein),
function values (interpolation), or proximal residuals (FISTA).
That does not remove the line search — it still enforces decrease — but it typically:
Cuts the number of backtracking trials per iteration.
Reduces total function evaluations over the full optimization.
Makes wall-clock time shorter even when outer iteration counts are similar.
In imaging, one chi-squared evaluation dominates cost; saving even one backtrack per iteration across hundreds of CG/L-BFGS steps is often noticeable.
Architecture: seeders + searchers#
Pyralysis separates initial step estimation from step acceptance:
Component |
Responsibility |
|---|---|
Step Size Seeders | Estimate \(\alpha_k^{(0)}\) from history (optional) |
|
|
Accept, expand, or backtrack from \(\alpha_k^{(0)}\) |
When LineSearcher.seeder is set, _get_initial_step_size()
calls seeder.estimate_step_size(x, objective_function). Otherwise the line searcher
uses its step attribute (default 1.0).
from pyralysis.optimization.linesearch import BacktrackingArmijo, BarzilaiBorweinAlternating
bb = BarzilaiBorweinAlternating(min_step=1e-10)
ls = BacktrackingArmijo(objective_function=of, seeder=bb)
See Step Size Seeders for every seeder class, formulas, and selection guidance.
Available line searchers#
BacktrackingArmijo#
Class: BacktrackingArmijo
Armijo sufficient decrease (backtracking):
Starting from the seeder estimate (or step), \(\alpha\) is multiplied by
decrease (default 0.5) until the condition holds or min_step is reached.
Parameters: contraction (\(c_1\), default 1e-4), decrease, min_step.
Use when: default choice for gradient-based Optimizers; robust on ill-conditioned imaging objectives.
GLLArmijo#
Class: GLLArmijo
Non-monotonic Armijo (Grippo–Lampariello–Lucidi):
Parameters: memory_window (default 5), plus Armijo backtracking parameters.
Use when: non-convex landscapes where strict monotonic decrease traps the iterate in poor regions.
Goldstein#
Class: Goldstein
Enforces lower and upper bounds on the step (with 0 < c_1 < c_2 < 1):
Backtracks when the upper bound fails; expands when the lower bound fails.
Use when: Armijo alone yields steps that are too small.
Brent#
Class: Brent
Derivative-free bracketing on the 1D objective along \(d_k\), combining golden-section search and parabolic interpolation (Brent’s method).
Use when: gradients along the search ray are unavailable or expensive to evaluate repeatedly (unusual in Pyralysis imaging, but available for experimentation).
GoldenSection#
Class: GoldenSection
Pure golden-ratio interval reduction; derivative-free and robust for unimodal 1D functions.
Fibonacci#
Class: Fibonacci
Fibonacci-number interval reduction; optimal number of evaluations for a fixed bracket width if the iteration count is known in advance.
Fixed#
Class: Fixed
Constant step \(\alpha_k = \texttt{step}\) for all iterations; no seeder integration beyond the fixed value.
Use when: the optimal step is known a priori or for debugging.
FISTABacktracking#
Class: FISTABacktracking
Specialized line searcher for Compressed Sensing & Proximal Methods FISTA. Inherits backtracking machinery but searches for a Lipschitz constant \(L_k\) satisfying the quadratic upper bound from Beck & Teboulle (2009):
where \(y_k\) is the FISTA accelerated point, \(F = f + g\), and \(p_L(y) = \operatorname{prox}_{g/L}(y - \nabla f(y)/L)\).
An optional Step Size Seeders (typically ProximalBarzilaiBorwein) supplies an
initial \(L_0 \approx 1/\alpha\) from proximal BB history.
Use when: running FISTA on objectives with one non-smooth term (e.g. L1 + smooth
:data fidelity). Not for multi-prox SDMM splitting.
Selection guide#
Implementation examples#
Armijo with Barzilai–Borwein seeder
from pyralysis.optimization.linesearch import (
BacktrackingArmijo,
GLLArmijo,
Goldstein,
BarzilaiBorweinAdaptiveMin1,
CubicInterpolationSeeder,
)
bb = BarzilaiBorweinAdaptiveMin1(min_step=1e-10, tau=0.8, window=10)
ls = BacktrackingArmijo(objective_function=of, seeder=bb)
# Non-monotonic variant
ls_gll = GLLArmijo(objective_function=of, seeder=bb, memory_window=5)
# Cubic interpolation initial step
cubic = CubicInterpolationSeeder(min_step=1e-10)
ls_cubic = BacktrackingArmijo(objective_function=of, seeder=cubic)
Attach to an optimizer
from pyralysis.optimization.optimizer import LBFGS
optim = LBFGS(
parameter=image,
objective_function=of,
linesearch=ls,
max_iter=100,
)
result = optim.optimize()
See Optimizers for optimizer-specific usage and Step Size Seeders for seeder details.
See also#
Step Size Seeders — initial step estimation and BB variants
Optimizers — conjugate gradient and L-BFGS drivers
Optimization in Pyralysis — building objective functions and workflow overview
Compressed Sensing & Proximal Methods — FISTA and
FISTABacktracking