Line Searchers
==============

Introduction
------------

**Line searchers** (``LineSearcher``) determine how far to move along a search direction
at each optimization iteration. Gradient-based :doc:`optimizers` and proximal methods
(FISTA, inner SDMM loops) call a line searcher after computing :math:`d_k`.

.. figure:: diagrams/png/fig06_linesearch_seeders-1.png
   :alt: Line search hierarchy
   :width: 100%

   **Line-search hierarchy** (``LineSearcher`` and concrete search methods).

Mathematical foundation
-----------------------

The parameter update is

.. math::

   x_{k+1} = x_k + \alpha_k \, d_k

where :math:`d_k` is the search direction (e.g. :math:`-g_k` for steepest descent or a
conjugate-gradient direction) and :math:`\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:

Step size geometry: too short, too long, and why seeders help
-------------------------------------------------------------

On a smooth objective, each iterate moves from :math:`x_k` along the ray
:math:`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
:math:`d_k`. A **convergence trajectory plot** (optimization path on level curves) shows
those ellipses and the sequence :math:`x_0, x_1, \ldots` connected by arrows.

.. figure:: diagrams/png/fig_step_size_trajectories.png
   :alt: Optimization paths on quadratic level curves for small, large, and seeded steps
   :width: 100%

   **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 :math:`x^*`. Illustrative trajectories (not live optimizer output).

**Step too small**

- The iterate still decreases :math:`f`, but progress toward :math:`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 :math:`f`.
- Backtracking Armijo **halves** (or scales by ``decrease``) :math:`\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 :math:`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
:doc:`step_size_seeders` estimates :math:`\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                                                   |
+==================+==================================================================+
| :doc:`step_size_seeders` | Estimate :math:`\alpha_k^{(0)}` from history (optional)  |
+------------------+------------------------------------------------------------------+
| ``LineSearcher`` | Accept, expand, or backtrack from :math:`\alpha_k^{(0)}`         |
+------------------+------------------------------------------------------------------+

When ``LineSearcher.seeder`` is set, :meth:`~pyralysis.optimization.linesearch.LineSearcher._get_initial_step_size`
calls ``seeder.estimate_step_size(x, objective_function)``. Otherwise the line searcher
uses its ``step`` attribute (default ``1.0``).

.. code-block:: python

   from pyralysis.optimization.linesearch import BacktrackingArmijo, BarzilaiBorweinAlternating

   bb = BarzilaiBorweinAlternating(min_step=1e-10)
   ls = BacktrackingArmijo(objective_function=of, seeder=bb)

See :doc:`step_size_seeders` for every seeder class, formulas, and selection guidance.

Available line searchers
------------------------

BacktrackingArmijo
~~~~~~~~~~~~~~~~~~

**Class:** ``BacktrackingArmijo``

**Armijo sufficient decrease** (backtracking):

.. math::

   f(x_k + \alpha d_k) \leq f(x_k) + c_1 \alpha \nabla f(x_k)^T d_k

Starting from the seeder estimate (or ``step``), :math:`\alpha` is multiplied by
``decrease`` (default ``0.5``) until the condition holds or ``min_step`` is reached.

**Parameters:** ``contraction`` (:math:`c_1`, default ``1e-4``), ``decrease``, ``min_step``.

**Use when:** default choice for gradient-based :doc:`optimizers`; robust on
ill-conditioned imaging objectives.

GLLArmijo
~~~~~~~~~

**Class:** ``GLLArmijo``

**Non-monotonic Armijo** (Grippo–Lampariello–Lucidi):

.. math::

   f(x_k + \alpha d_k) \leq \max_{0 \leq j \leq m(k)} f(x_{k-j})
   + c_1 \alpha \nabla f(x_k)^T d_k

**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``):

.. math::

   f(x_k) + c_2 \alpha \nabla f(x_k)^T d_k \leq f(x_k + \alpha d_k)
   \leq f(x_k) + c_1 \alpha \nabla f(x_k)^T d_k

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 :math:`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 :math:`\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 :doc:`compressed_sensing` **FISTA**. Inherits backtracking
machinery but searches for a Lipschitz constant :math:`L_k` satisfying the quadratic upper
bound from Beck & Teboulle (2009):

.. math::

   F(p_L(y_k)) \leq Q_L(p_L(y_k), y_k)

where :math:`y_k` is the FISTA accelerated point, :math:`F = f + g`, and
:math:`p_L(y) = \operatorname{prox}_{g/L}(y - \nabla f(y)/L)`.

An optional :doc:`step_size_seeders` (typically ``ProximalBarzilaiBorwein``) supplies an
initial :math:`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
---------------

+-----------------------------+----------------------------------------+
| Situation                   | Suggested line searcher                |
+=============================+========================================+
| Default smooth optimization | ``BacktrackingArmijo`` + BB seeder     |
+-----------------------------+----------------------------------------+
| Non-convex / local minima   | ``GLLArmijo``                          |
+-----------------------------+----------------------------------------+
| Armijo steps too small      | ``Goldstein``                          |
+-----------------------------+----------------------------------------+
| FISTA                       | ``FISTABacktracking`` + proximal BB  |
+-----------------------------+----------------------------------------+
| Known fixed step            | ``Fixed``                              |
+-----------------------------+----------------------------------------+
| Derivative-free 1D search   | ``Brent``, ``GoldenSection``,          |
|                             | ``Fibonacci``                          |
+-----------------------------+----------------------------------------+

Implementation examples
-----------------------

**Armijo with Barzilai–Borwein seeder**

.. code-block:: python

   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**

.. code-block:: python

   from pyralysis.optimization.optimizer import LBFGS

   optim = LBFGS(
       parameter=image,
       objective_function=of,
       linesearch=ls,
       max_iter=100,
   )
   result = optim.optimize()

See :doc:`optimizers` for optimizer-specific usage and :doc:`step_size_seeders` for seeder
details.

See also
--------

- :doc:`step_size_seeders` — initial step estimation and BB variants
- :doc:`optimizers` — conjugate gradient and L-BFGS drivers
- :doc:`optimization` — building objective functions and workflow overview
- :doc:`compressed_sensing` — FISTA and ``FISTABacktracking``

----

:doc:`step_size_seeders` | :doc:`optimizers` | :doc:`optimization`