basin 1.8.0

Numerical optimization in pure Rust, with pluggable linear-algebra backends and WASM support.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126

//! Line searches: produce a step size `α` along a caller-supplied descent
//! direction. Used by first-order solvers (gradient descent, BFGS).

/// Backtracking line search (Armijo-only).
pub mod backtracking;
/// Hager–Zhang line search with approximate-Wolfe safeguards.
pub mod hager_zhang;
/// Moré–Thuente line search (MINPACK-2 `dcsrch` + `dcstep`).
pub mod more_thuente;
/// Strong-Wolfe line search (Nocedal & Wright algorithms 3.5/3.6).
pub mod wolfe;

pub use backtracking::Backtracking;
pub use hager_zhang::HagerZhang;
pub use more_thuente::MoreThuente;
pub use wolfe::Wolfe;

use crate::core::math::Scalar;
use crate::core::problem::Problem;

/// Outcome of a line-search attempt.
#[derive(Debug, Clone, Copy, PartialEq)]
#[non_exhaustive]
pub enum LineSearchOutcome<F> {
    /// The line search selected this step size.
    Step(F),
    /// The line search could not produce a usable step.
    Failed,
}

/// Compute a step size `α` along a caller-supplied descent direction `d`.
///
/// Convention: `direction` is a *descent* direction (`gᵀd < 0`); the caller
/// applies `x_new = x + α d`. Solvers that descend along `−∇f` (e.g. plain
/// gradient descent) compute `d = −∇f` themselves and pass it in.
///
/// # Eval counting
///
/// Line searches receive `&mut Problem<P>` so every probe (`problem.cost(x)`,
/// `problem.cost_and_gradient(x)`) bumps the wrapper's
/// [`EvalCounts`](crate::core::problem::EvalCounts) automatically. There is
/// no count returned out-of-band: callers read counts off the wrapper if
/// they need them (the [`Executor`](crate::Executor) mirrors them onto the
/// state after the enclosing
/// [`Solver::next_iter`](crate::core::solver::Solver::next_iter)).
///
/// # Error type
///
/// `Error` is the hard-abort error the line search propagates; concrete
/// impls set `type Error = P::Error;` (with `P: CostFunction`) so the
/// user's typed problem error bubbles untouched through the solver out of
/// [`Executor::run`](crate::Executor::run). See the
/// [`problem`](crate::core::problem) module docs for the soft-reject and
/// hard-abort split.
///
/// `F` defaults to `f64` so legacy `LineSearch<P, V>` bounds on
/// gradient-based solvers (still f64-only pending the linalg-tier
/// migration) keep resolving unchanged.
pub trait LineSearch<P, V, F = f64> {
    /// Hard-abort error type, mirroring the underlying problem's `Error`.
    type Error;

    /// Returns the chosen step size `α`. Counts are tracked on the
    /// wrapper via every `problem.cost`/`problem.cost_and_gradient`
    /// probe inside the search. Returns `Err` if any inner problem call
    /// hard-aborts.
    fn next(
        &mut self,
        problem: &mut Problem<P>,
        param: &V,
        cost: F,
        gradient: &V,
        direction: &V,
    ) -> Result<F, Self::Error>;

    /// Returns the step together with a distinguishable soft-failure outcome.
    ///
    /// The default wraps [`next`](Self::next) in
    /// [`LineSearchOutcome::Step`] for compatibility with existing line-search
    /// implementations. Implementations that can exhaust without a usable step
    /// should override this method and return [`LineSearchOutcome::Failed`].
    fn next_with_outcome(
        &mut self,
        problem: &mut Problem<P>,
        param: &V,
        cost: F,
        gradient: &V,
        direction: &V,
    ) -> Result<LineSearchOutcome<F>, Self::Error> {
        self.next(problem, param, cost, gradient, direction)
            .map(LineSearchOutcome::Step)
    }
}

/// Constant step size: returns the wrapped `α` regardless of input.
/// Useful when the caller already knows a good fixed step.
pub struct Constant<F = f64>(pub F);

impl<F: Scalar> Constant<F> {
    /// Constant step of size `alpha`.
    pub fn new(alpha: F) -> Self {
        Self(alpha)
    }
}

impl<P, V, F> LineSearch<P, V, F> for Constant<F>
where
    P: crate::core::problem::CostFunction,
    F: Scalar,
{
    // `Constant` makes no problem calls and so could declare any error
    // type, but solver bounds expect `L::Error = P::Error`; matching here
    // means callers never need a conversion glue layer.
    type Error = P::Error;

    fn next(
        &mut self,
        _problem: &mut Problem<P>,
        _param: &V,
        _cost: F,
        _gradient: &V,
        _direction: &V,
    ) -> Result<F, Self::Error> {
        Ok(self.0)
    }
}