Skip to main content

tpt_math_optimize_general/
lib.rs

1//! General numerical optimization — in-house smooth, unconstrained minimizers.
2//!
3//! This crate provides closure-driven entry points for the common smooth,
4//! unconstrained minimization cases, built directly on
5//! [`tpt_math_linalg_dense`]'s [`DVector`]/[`DMatrix`] (no `argmin`/`faer`
6//! dependency):
7//!
8//! | Convenience function | Method |
9//! |---|---|
10//! | [`minimize_gradient_descent`] | steepest descent + More-Thuente line search |
11//! | [`minimize_conjugate_gradient`] | nonlinear CG (Polak–Ribière+) + More-Thuente line search, periodic restarts |
12//! | [`minimize_newton`] | Newton's method (full step, analytic Hessian) |
13//!
14//! Parameters are plain [`DVector<f64>`](tpt_math_linalg_dense::DVector)s; unit-tagged
15//! [`tpt_math_linalg::Vec`] values move in and out with
16//! [`point_from_tagged`] / [`point_to_tagged`]. Optimization itself is
17//! deliberately unit-less: a cost mixes every unit in the problem, so there is
18//! no meaningful tag for a search direction or a step length.
19//!
20//! # Examples
21//!
22//! Minimize `f(x, y) = (x - 3)² + (y - 2)²` by gradient descent:
23//!
24//! ```
25//! use tpt_math_optimize_general::{minimize_gradient_descent, tpt_math_linalg_dense::DVector};
26//!
27//! let cost = |p: &DVector<f64>| (p[0] - 3.0).powi(2) + (p[1] - 2.0).powi(2);
28//! let grad = |p: &DVector<f64>| DVector::from_vec(vec![2.0 * (p[0] - 3.0), 2.0 * (p[1] - 2.0)]);
29//!
30//! let best = minimize_gradient_descent(cost, grad, DVector::zeros(2), 100).unwrap();
31//!
32//! assert!((best[0] - 3.0).abs() < 1e-6);
33//! assert!((best[1] - 2.0).abs() < 1e-6);
34//! ```
35//!
36//! The `*_with` variants take [`Options`] and return a [`Solution`], which
37//! also reports the cost, the iteration count and why the solver stopped:
38//!
39//! ```
40//! use tpt_math_optimize_general::{minimize_newton, tpt_math_linalg_dense::{DMatrix, DVector}};
41//!
42//! // f(x) = exp(x) - x, minimized at x = 0 with f(0) = 1.
43//! let cost = |p: &DVector<f64>| p[0].exp() - p[0];
44//! let grad = |p: &DVector<f64>| DVector::from_vec(vec![p[0].exp() - 1.0]);
45//! let hess = |p: &DVector<f64>| DMatrix::from_vec(1, 1, vec![p[0].exp()]);
46//!
47//! let best = minimize_newton(cost, grad, hess, DVector::from_vec(vec![1.0]), 50).unwrap();
48//!
49//! assert!(best[0].abs() < 1e-6);
50//! ```
51//!
52//! # Conventions
53//!
54//! * Every run stops at `max_iters`, or earlier once the gradient's L2 norm
55//!   falls to [`Options::gradient_tolerance`]. The early stop matters: a solver
56//!   that has already reached its optimum would otherwise keep iterating and
57//!   report a worse (or non-finite) point.
58//! * The reported [`Solution::param`] is the best parameter vector found, and
59//!   [`Solution::cost`] is the user cost function re-evaluated there.
60//! * A non-finite or empty initial point, or a non-invertible Hessian (Newton),
61//!   is reported as an `Err` with a human-readable message.
62
63#![forbid(unsafe_code)]
64#![warn(missing_docs, missing_debug_implementations)]
65
66pub mod autodiff_opt;
67pub mod least_squares;
68
69pub use autodiff_opt::minimize_lbfgs_autodiff;
70pub mod linear_program;
71
72pub use least_squares::{
73    curve_fit, levenberg_marquardt, LeastSquaresOptions, LeastSquaresSolution, LsTermination,
74};
75
76pub use tpt_math_linalg;
77pub use tpt_math_linalg::tpt_math_linalg_dense;
78
79use tpt_math_linalg_dense::{DMatrix, DVector};
80use tpt_math_numeric::{SolveReport, SolveStatus};
81
82/// Default iteration budget used by [`Options::default`].
83pub const DEFAULT_MAX_ITERS: u64 = 100;
84
85/// Default gradient L2 norm at or below which a run counts as converged.
86pub const DEFAULT_GRADIENT_TOLERANCE: f64 = 1e-9;
87
88/// Iterations between forced conjugate-gradient restarts (β reset to zero).
89const RESTART_ITERS: u64 = 10;
90
91/// Orthogonality threshold that triggers a conjugate-gradient restart.
92const RESTART_ORTHOGONALITY: f64 = 0.1;
93
94/// A unit-tagged vector of `f64`s, as used by [`tpt_math_linalg`].
95pub type TaggedVec<U> = tpt_math_linalg::Vec<U, f64>;
96
97/// Knobs shared by every convenience minimizer.
98#[derive(Clone, Copy, Debug, PartialEq)]
99pub struct Options {
100    /// Hard cap on solver iterations.
101    pub max_iters: u64,
102    /// Stop as soon as the gradient's L2 norm is at or below this value.
103    ///
104    /// Setting it to `0.0` effectively runs the full iteration budget, since
105    /// only an exactly zero gradient then counts as converged.
106    pub gradient_tolerance: f64,
107}
108
109impl Default for Options {
110    fn default() -> Self {
111        Options {
112            max_iters: DEFAULT_MAX_ITERS,
113            gradient_tolerance: DEFAULT_GRADIENT_TOLERANCE,
114        }
115    }
116}
117
118impl Options {
119    /// Options with the given iteration budget and the default gradient
120    /// tolerance.
121    ///
122    /// ```
123    /// use tpt_math_optimize_general::{Options, DEFAULT_GRADIENT_TOLERANCE};
124    ///
125    /// let opts = Options::new(250);
126    /// assert_eq!(opts.max_iters, 250);
127    /// assert_eq!(opts.gradient_tolerance, DEFAULT_GRADIENT_TOLERANCE);
128    /// ```
129    pub fn new(max_iters: u64) -> Self {
130        Options {
131            max_iters,
132            ..Options::default()
133        }
134    }
135
136    /// Set the gradient tolerance, returning the updated options.
137    ///
138    /// ```
139    /// use tpt_math_optimize_general::Options;
140    ///
141    /// let opts = Options::new(10).with_gradient_tolerance(1e-6);
142    /// assert_eq!(opts.gradient_tolerance, 1e-6);
143    /// ```
144    pub fn with_gradient_tolerance(mut self, tolerance: f64) -> Self {
145        self.gradient_tolerance = tolerance;
146        self
147    }
148}
149
150/// The outcome of a minimization run.
151#[derive(Clone, Debug, PartialEq)]
152pub struct Solution {
153    /// Best parameter vector found.
154    pub param: DVector<f64>,
155    /// The user cost function evaluated at [`Solution::param`].
156    pub cost: f64,
157    /// Number of iterations actually performed.
158    pub iters: u64,
159    /// `true` if the run stopped because the gradient tolerance was met,
160    /// `false` if it merely ran out of iterations (or stopped for any other
161    /// reason).
162    pub converged: bool,
163    /// Human-readable reason the solver stopped.
164    pub termination: String,
165    /// The solver's residual at the returned point: the gradient norm for the
166    /// gradient-based methods, and the cost spread over the simplex for
167    /// Nelder–Mead.
168    pub residual: f64,
169}
170
171impl Solution {
172    /// The outcome as a [`SolveReport`]. `Converged` when the solver met its
173    /// tolerance, `Breakdown` when the line search stalled, and `NotConverged`
174    /// when the iteration budget ran out.
175    #[must_use]
176    pub fn report(&self) -> SolveReport<f64> {
177        let status = if self.converged {
178            SolveStatus::Converged
179        } else if self.termination == "LineSearchStalled" {
180            SolveStatus::Breakdown
181        } else {
182            SolveStatus::NotConverged
183        };
184        SolveReport {
185            status,
186            iterations: self.iters as usize,
187            residual: self.residual,
188        }
189    }
190}
191
192/// Copy a unit-tagged [`tpt_math_linalg::Vec`] into a raw parameter vector.
193///
194/// ```
195/// use tpt_math_optimize_general::{point_from_tagged, TaggedVec, tpt_math_linalg_dense::DVector};
196///
197/// let tagged: TaggedVec<()> = TaggedVec::from_raw(DVector::from_vec(vec![1.0, 2.0]));
198/// assert_eq!(point_from_tagged(&tagged), DVector::from_vec(vec![1.0, 2.0]));
199/// ```
200pub fn point_from_tagged<U>(v: &TaggedVec<U>) -> DVector<f64> {
201    v.raw().clone()
202}
203
204/// Tag a raw parameter vector with the unit `U`, undoing [`point_from_tagged`].
205///
206/// ```
207/// use tpt_math_optimize_general::{point_to_tagged, TaggedVec, tpt_math_linalg_dense::DVector};
208///
209/// let tagged: TaggedVec<()> = point_to_tagged(DVector::from_vec(vec![1.0, 2.0]));
210/// assert_eq!(tagged.len(), 2);
211/// ```
212pub fn point_to_tagged<U>(point: DVector<f64>) -> TaggedVec<U> {
213    TaggedVec::from_raw(point)
214}
215
216/// Minimize a smooth objective by gradient descent with a More-Thuente line
217/// search.
218///
219/// `cost` and `grad` must describe the same function; `init` is the starting
220/// point and `max_iters` the iteration budget. Returns the best parameter
221/// vector found, or a message string on bad input.
222///
223/// # Examples
224///
225/// ```
226/// use tpt_math_optimize_general::{minimize_gradient_descent, tpt_math_linalg_dense::DVector};
227///
228/// // f(x) = x², minimized at x = 0.
229/// let cost = |p: &DVector<f64>| p[0] * p[0];
230/// let grad = |p: &DVector<f64>| DVector::from_vec(vec![2.0 * p[0]]);
231///
232/// let best = minimize_gradient_descent(cost, grad, DVector::from_vec(vec![5.0]), 50).unwrap();
233/// assert!(best[0].abs() < 1e-8);
234/// ```
235///
236/// # Errors
237///
238/// Returns `Err` if `init` is empty or non-finite.
239pub fn minimize_gradient_descent<F, G>(
240    cost: F,
241    grad: G,
242    init: DVector<f64>,
243    max_iters: u64,
244) -> Result<DVector<f64>, String>
245where
246    F: Fn(&DVector<f64>) -> f64,
247    G: Fn(&DVector<f64>) -> DVector<f64>,
248{
249    minimize_gradient_descent_with(cost, grad, init, &Options::new(max_iters)).map(|s| s.param)
250}
251
252/// [`minimize_gradient_descent`] with explicit [`Options`], reporting a full
253/// [`Solution`].
254///
255/// # Examples
256///
257/// ```
258/// use tpt_math_optimize_general::{minimize_gradient_descent_with, Options, tpt_math_linalg_dense::DVector};
259///
260/// let cost = |p: &DVector<f64>| (p[0] - 1.0).powi(2);
261/// let grad = |p: &DVector<f64>| DVector::from_vec(vec![2.0 * (p[0] - 1.0)]);
262///
263/// let options = Options::new(100).with_gradient_tolerance(1e-10);
264/// let solution = minimize_gradient_descent_with(cost, grad, DVector::zeros(1), &options).unwrap();
265///
266/// assert!(solution.converged);
267/// assert!(solution.cost < 1e-12);
268/// ```
269///
270/// # Errors
271///
272/// As [`minimize_gradient_descent`].
273pub fn minimize_gradient_descent_with<F, G>(
274    cost: F,
275    grad: G,
276    init: DVector<f64>,
277    options: &Options,
278) -> Result<Solution, String>
279where
280    F: Fn(&DVector<f64>) -> f64,
281    G: Fn(&DVector<f64>) -> DVector<f64>,
282{
283    let mut state = OptimizerState::new(cost, grad, no_hessian, init, options)?;
284    let mut iters = 0;
285    loop {
286        if state.grad_norm() <= options.gradient_tolerance {
287            return Ok(state.finish(iters, true, "GradientTolerance"));
288        }
289        if iters >= options.max_iters {
290            return Ok(state.finish(iters, false, "MaxIters"));
291        }
292        // Steepest descent: full negative gradient, scaled by the line search.
293        let dir = -state.grad().clone();
294        let alpha = line_search(state.cost_fn(), state.grad_fn(), &state.param, &dir);
295        if alpha == 0.0 {
296            return Ok(state.finish(iters, false, "LineSearchStalled"));
297        }
298        state.step(&(dir * alpha));
299        iters += 1;
300    }
301}
302
303/// Minimize a smooth objective with nonlinear conjugate gradients
304/// (Polak–Ribière+ β update with periodic restarts, More-Thuente line search).
305///
306/// Usually a much better default than plain gradient descent on ill-conditioned
307/// problems, at the same cost per iteration (one cost and one gradient
308/// evaluation plus the line search).
309///
310/// # Examples
311///
312/// ```
313/// use tpt_math_optimize_general::{minimize_conjugate_gradient, tpt_math_linalg_dense::DVector};
314///
315/// // A stretched quadratic: gradient descent zig-zags here, CG does not.
316/// let cost = |p: &DVector<f64>| (p[0] - 3.0).powi(2) + 50.0 * (p[1] - 2.0).powi(2);
317/// let grad = |p: &DVector<f64>| {
318///     DVector::from_vec(vec![2.0 * (p[0] - 3.0), 100.0 * (p[1] - 2.0)])
319/// };
320///
321/// let best = minimize_conjugate_gradient(cost, grad, DVector::zeros(2), 100).unwrap();
322/// assert!((best[0] - 3.0).abs() < 1e-5);
323/// assert!((best[1] - 2.0).abs() < 1e-5);
324/// ```
325///
326/// # Errors
327///
328/// As [`minimize_gradient_descent`].
329pub fn minimize_conjugate_gradient<F, G>(
330    cost: F,
331    grad: G,
332    init: DVector<f64>,
333    max_iters: u64,
334) -> Result<DVector<f64>, String>
335where
336    F: Fn(&DVector<f64>) -> f64,
337    G: Fn(&DVector<f64>) -> DVector<f64>,
338{
339    minimize_conjugate_gradient_with(cost, grad, init, &Options::new(max_iters)).map(|s| s.param)
340}
341
342/// [`minimize_conjugate_gradient`] with explicit [`Options`], reporting a full
343/// [`Solution`].
344///
345/// # Examples
346///
347/// ```
348/// use tpt_math_optimize_general::{minimize_conjugate_gradient_with, Options, tpt_math_linalg_dense::DVector};
349///
350/// let cost = |p: &DVector<f64>| (p[0] - 3.0).powi(2) + (p[1] + 1.0).powi(2);
351/// let grad = |p: &DVector<f64>| {
352///     DVector::from_vec(vec![2.0 * (p[0] - 3.0), 2.0 * (p[1] + 1.0)])
353/// };
354///
355/// let solution =
356///     minimize_conjugate_gradient_with(cost, grad, DVector::zeros(2), &Options::new(50)).unwrap();
357/// assert!(solution.cost < 1e-12);
358/// ```
359///
360/// # Errors
361///
362/// As [`minimize_gradient_descent`].
363pub fn minimize_conjugate_gradient_with<F, G>(
364    cost: F,
365    grad: G,
366    init: DVector<f64>,
367    options: &Options,
368) -> Result<Solution, String>
369where
370    F: Fn(&DVector<f64>) -> f64,
371    G: Fn(&DVector<f64>) -> DVector<f64>,
372{
373    let mut state = OptimizerState::new(cost, grad, no_hessian, init, options)?;
374    let mut iters = 0;
375    let mut prev_grad: Option<DVector<f64>> = None;
376    let mut direction: Option<DVector<f64>> = None;
377    loop {
378        if state.grad_norm() <= options.gradient_tolerance {
379            return Ok(state.finish(iters, true, "GradientTolerance"));
380        }
381        if iters >= options.max_iters {
382            return Ok(state.finish(iters, false, "MaxIters"));
383        }
384
385        let dir = match (&prev_grad, &direction) {
386            (None, None) => -state.grad().clone(),
387            (Some(g_prev), Some(d_prev)) => {
388                let denom = g_prev.dot(g_prev);
389                let beta = if denom > 0.0 {
390                    let num = state.grad().dot(&(state.grad().clone() - g_prev.clone()));
391                    num / denom
392                } else {
393                    0.0
394                };
395                let beta = beta.max(0.0);
396                let restart = (iters % RESTART_ITERS == 0)
397                    || (denom > 0.0
398                        && (state.grad().dot(g_prev)).abs() / denom >= RESTART_ORTHOGONALITY);
399                // Fall back to steepest descent if β yields a non-descent dir.
400                let cand = if restart {
401                    -state.grad().clone()
402                } else {
403                    -state.grad().clone() + d_prev.clone() * beta
404                };
405                if cand.dot(state.grad()) >= 0.0 {
406                    -state.grad().clone()
407                } else {
408                    cand
409                }
410            }
411            _ => unreachable!("prev_grad and direction are set together"),
412        };
413
414        let alpha = line_search(state.cost_fn(), state.grad_fn(), &state.param, &dir);
415        if alpha == 0.0 {
416            // A conjugate direction stalled: restart from steepest descent once.
417            // If steepest descent itself stalled, there is no progress left.
418            if prev_grad.is_none() {
419                return Ok(state.finish(iters, false, "LineSearchStalled"));
420            }
421            prev_grad = None;
422            direction = None;
423            iters += 1;
424            continue;
425        }
426        state.step(&(dir.clone() * alpha));
427        prev_grad = Some(state.grad().clone());
428        direction = Some(dir);
429        iters += 1;
430    }
431}
432
433/// Minimize a smooth objective with `Newton`'s method, using the analytic
434/// Hessian.
435///
436/// Newton converges quadratically near a minimum — a quadratic objective is
437/// solved in a single iteration — but it needs a Hessian that is invertible
438/// (and, to descend rather than ascend, positive definite) along the path. Fall
439/// back to [`minimize_conjugate_gradient`] when that cannot be guaranteed.
440///
441/// The step is the full Newton step `x - H⁻¹ ∇f` (no damping); a singular
442/// Hessian is reported as an error.
443///
444/// # Examples
445///
446/// ```
447/// use tpt_math_optimize_general::{minimize_newton, tpt_math_linalg_dense::{DMatrix, DVector}};
448///
449/// // f(x, y) = (x - 3)² + (y - 2)²: one Newton step lands exactly on (3, 2).
450/// let cost = |p: &DVector<f64>| (p[0] - 3.0).powi(2) + (p[1] - 2.0).powi(2);
451/// let grad = |p: &DVector<f64>| DVector::from_vec(vec![2.0 * (p[0] - 3.0), 2.0 * (p[1] - 2.0)]);
452/// let hess = |_: &DVector<f64>| DMatrix::from_diagonal(&DVector::from_vec(vec![2.0, 2.0]));
453///
454/// let best = minimize_newton(cost, grad, hess, DVector::zeros(2), 25).unwrap();
455/// assert!((best[0] - 3.0).abs() < 1e-12);
456/// assert!((best[1] - 2.0).abs() < 1e-12);
457/// ```
458///
459/// # Errors
460///
461/// As [`minimize_gradient_descent`], plus a non-invertible Hessian.
462pub fn minimize_newton<F, G, H>(
463    cost: F,
464    grad: G,
465    hessian: H,
466    init: DVector<f64>,
467    max_iters: u64,
468) -> Result<DVector<f64>, String>
469where
470    F: Fn(&DVector<f64>) -> f64,
471    G: Fn(&DVector<f64>) -> DVector<f64>,
472    H: Fn(&DVector<f64>) -> DMatrix<f64>,
473{
474    minimize_newton_with(cost, grad, hessian, init, &Options::new(max_iters)).map(|s| s.param)
475}
476
477/// [`minimize_newton`] with explicit [`Options`], reporting a full
478/// [`Solution`].
479///
480/// # Examples
481///
482/// ```
483/// use tpt_math_optimize_general::{
484///     minimize_newton_with, Options,
485///     tpt_math_linalg_dense::{DMatrix, DVector},
486/// };
487///
488/// let cost = |p: &DVector<f64>| p[0].powi(2);
489/// let grad = |p: &DVector<f64>| DVector::from_vec(vec![2.0 * p[0]]);
490/// let hess = |_: &DVector<f64>| DMatrix::from_vec(1, 1, vec![2.0]);
491///
492/// let solution =
493///     minimize_newton_with(cost, grad, hess, DVector::from_vec(vec![9.0]), &Options::new(10))
494///         .unwrap();
495///
496/// assert!(solution.converged);
497/// assert!(solution.iters <= 2);
498/// ```
499///
500/// # Errors
501///
502/// As [`minimize_newton`].
503pub fn minimize_newton_with<F, G, H>(
504    cost: F,
505    grad: G,
506    hessian: H,
507    init: DVector<f64>,
508    options: &Options,
509) -> Result<Solution, String>
510where
511    F: Fn(&DVector<f64>) -> f64,
512    G: Fn(&DVector<f64>) -> DVector<f64>,
513    H: Fn(&DVector<f64>) -> DMatrix<f64>,
514{
515    let mut state = OptimizerState::new(cost, grad, hessian, init, options)?;
516    let mut iters = 0;
517    loop {
518        if state.grad_norm() <= options.gradient_tolerance {
519            return Ok(state.finish(iters, true, "GradientTolerance"));
520        }
521        if iters >= options.max_iters {
522            return Ok(state.finish(iters, false, "MaxIters"));
523        }
524        let neg_grad = -state.grad().clone();
525        let step = state
526            .hessian()?
527            .solve(&neg_grad)
528            .map_err(|_| "singular Hessian (Newton step undefined)".to_string())?;
529        state.step(&step);
530        iters += 1;
531    }
532}
533
534/// A placeholder Hessian function for the first-order solvers (never called).
535fn no_hessian(_: &DVector<f64>) -> DMatrix<f64> {
536    DMatrix::zeros(0, 0)
537}
538
539/// Reject inputs that the solvers would only reject later, with a worse message.
540fn validate(init: &DVector<f64>, options: &Options) -> Result<(), String> {
541    if init.is_empty() {
542        return Err("initial parameter vector must not be empty".to_string());
543    }
544    if init.iter().any(|x| !x.is_finite()) {
545        return Err("initial parameter vector must be finite".to_string());
546    }
547    if options.gradient_tolerance.is_nan() || options.gradient_tolerance < 0.0 {
548        return Err("gradient tolerance must be finite and non-negative".to_string());
549    }
550    Ok(())
551}
552
553/// Mutable solver state shared by all three minimizers.
554struct OptimizerState<F, G, H> {
555    cost: F,
556    grad: G,
557    hessian: H,
558    param: DVector<f64>,
559    grad_cache: DVector<f64>,
560    cost_cache: f64,
561}
562
563impl<F, G, H> OptimizerState<F, G, H>
564where
565    F: Fn(&DVector<f64>) -> f64,
566    G: Fn(&DVector<f64>) -> DVector<f64>,
567    H: Fn(&DVector<f64>) -> DMatrix<f64>,
568{
569    fn new(
570        cost: F,
571        grad: G,
572        hessian: H,
573        init: DVector<f64>,
574        options: &Options,
575    ) -> Result<Self, String> {
576        validate(&init, options)?;
577        let grad_cache = grad(&init);
578        if !grad_cache.iter().all(|x| x.is_finite()) {
579            return Err("initial gradient is non-finite".to_string());
580        }
581        let cost_cache = cost(&init);
582        Ok(OptimizerState {
583            cost,
584            grad,
585            hessian,
586            param: init,
587            grad_cache,
588            cost_cache,
589        })
590    }
591
592    fn cost_fn(&self) -> &F {
593        &self.cost
594    }
595    fn grad_fn(&self) -> &G {
596        &self.grad
597    }
598    fn grad(&self) -> &DVector<f64> {
599        &self.grad_cache
600    }
601    fn grad_norm(&self) -> f64 {
602        self.grad_cache.norm()
603    }
604    fn hessian(&self) -> Result<DMatrix<f64>, String> {
605        Ok((self.hessian)(&self.param))
606    }
607
608    /// Advance `param` by `step`, refreshing the cached gradient and cost.
609    fn step(&mut self, step: &DVector<f64>) {
610        self.param = self.param.clone() + step.clone();
611        self.grad_cache = (self.grad)(&self.param);
612        self.cost_cache = (self.cost)(&self.param);
613    }
614
615    fn finish(self, iters: u64, converged: bool, termination: &'static str) -> Solution {
616        let residual = self.grad_norm();
617        Solution {
618            param: self.param,
619            cost: self.cost_cache,
620            iters,
621            converged,
622            termination: termination.to_string(),
623            residual,
624        }
625    }
626}
627
628/// More-Thuente (1994) cubic-interpolation line search along descent direction
629/// `d` from `x`. Returns a non-negative step length `alpha`.
630///
631/// Uses the analytic gradient (no finite differences): `phi(alpha) =
632/// cost(x + alpha*d)`, `phi'(alpha) = grad(x + alpha*d)·d`. Implements the
633/// strong Wolfe conditions (sufficient decrease `c1 = 1e-4`, curvature `c2 =
634/// 0.1`) with cubic interpolation between bracketed points (Nocedal & Wright
635/// Algorithms 3.5/3.6).
636fn line_search<F, G>(cost: &F, grad: &G, x: &DVector<f64>, d: &DVector<f64>) -> f64
637where
638    F: Fn(&DVector<f64>) -> f64,
639    G: Fn(&DVector<f64>) -> DVector<f64>,
640{
641    let phi0 = cost(x);
642    let alpha = line_search_bracket(cost, grad, x, d);
643    // Return 0 ("no progress") unless the step is finite, positive and actually
644    // decreases the cost; callers treat 0 as a stall.
645    if alpha.is_finite() && alpha > 0.0 && cost(&(x.clone() + d.clone() * alpha)) < phi0 {
646        alpha
647    } else {
648        0.0
649    }
650}
651
652fn line_search_bracket<F, G>(cost: &F, grad: &G, x: &DVector<f64>, d: &DVector<f64>) -> f64
653where
654    F: Fn(&DVector<f64>) -> f64,
655    G: Fn(&DVector<f64>) -> DVector<f64>,
656{
657    let c1 = 1e-4;
658    let c2 = 0.1;
659    let dphi0 = grad(x).dot(d);
660    if dphi0 >= 0.0 {
661        return 0.0; // not a descent direction
662    }
663    let phi0 = cost(x);
664
665    let mut a_lo = 0.0;
666    let mut phi_lo = phi0;
667    let mut dphi_lo = dphi0;
668    let mut a = 1.0;
669
670    for _ in 0..40 {
671        let xa = x.clone() + d.clone() * a;
672        let phi_a = cost(&xa);
673        // The bracket is [a_lo, a]: a_lo is the last point that satisfied
674        // sufficient decrease, and `a` is the trial that just failed.
675        if phi_a > phi0 + c1 * a * dphi0 || (a_lo != 0.0 && phi_a >= phi_lo) {
676            return zoom(cost, grad, x, d, a_lo, a, phi_lo, dphi_lo, phi_a);
677        }
678        let dphi_a = grad(&xa).dot(d);
679        if dphi_a.abs() <= -c2 * dphi0 {
680            return a;
681        }
682        if dphi_a >= 0.0 {
683            return zoom(cost, grad, x, d, a, a_lo, phi_a, dphi_a, phi_lo);
684        }
685        a_lo = a;
686        phi_lo = phi_a;
687        dphi_lo = dphi_a;
688        a *= 2.0;
689    }
690    a
691}
692
693/// Zoom phase of the More-Thuente line search: narrow the bracket `[a_lo, a_hi]`
694/// (where `a_lo` satisfies the sufficient-decrease condition and has a descent
695/// gradient) by cubic interpolation until the strong Wolfe conditions hold.
696#[allow(clippy::too_many_arguments)]
697fn zoom<F, G>(
698    cost: &F,
699    grad: &G,
700    x: &DVector<f64>,
701    d: &DVector<f64>,
702    mut a_lo: f64,
703    mut a_hi: f64,
704    mut phi_lo: f64,
705    mut dphi_lo: f64,
706    mut phi_hi: f64,
707) -> f64
708where
709    F: Fn(&DVector<f64>) -> f64,
710    G: Fn(&DVector<f64>) -> DVector<f64>,
711{
712    let c1 = 1e-4;
713    let c2 = 0.1;
714    let dphi0 = grad(x).dot(d);
715
716    for _ in 0..40 {
717        let mut dphi_hi = grad(&(x.clone() + d.clone() * a_hi)).dot(d);
718        let mut a = cubic_min(a_lo, phi_lo, dphi_lo, a_hi, phi_hi, dphi_hi);
719        // Bisect unless the trial lies strictly inside the (possibly reversed)
720        // bracket; the negated form also catches a NaN from `cubic_min`.
721        if !(a > a_lo.min(a_hi) && a < a_lo.max(a_hi)) {
722            a = 0.5 * (a_lo + a_hi);
723        }
724        let xa = x.clone() + d.clone() * a;
725        let phi_a = cost(&xa);
726        if phi_a > cost(x) + c1 * a * dphi0 || phi_a >= phi_lo {
727            a_hi = a;
728            phi_hi = phi_a;
729        } else {
730            let dphi_a = grad(&xa).dot(d);
731            if dphi_a * (a_hi - a_lo) >= 0.0 {
732                a_hi = a_lo;
733                phi_hi = phi_lo;
734                dphi_hi = dphi_lo;
735            }
736            a_lo = a;
737            phi_lo = phi_a;
738            dphi_lo = dphi_a;
739            if dphi_a.abs() <= -c2 * dphi0 {
740                return a;
741            }
742        }
743        if (a_hi - a_lo).abs() <= 1e-12 * (1.0 + a_hi.abs()) {
744            return a;
745        }
746    }
747    0.5 * (a_lo + a_hi)
748}
749
750/// Cubic-interpolation minimizer in `(al, ah)` given `phi`/`dphi` at both ends
751/// (Nocedal & Wright, eq. 3.59).
752fn cubic_min(al: f64, phi_al: f64, dphi_al: f64, ah: f64, phi_ah: f64, dphi_ah: f64) -> f64 {
753    let d1 = dphi_al + dphi_ah - 3.0 * (phi_al - phi_ah) / (al - ah);
754    let d2_sq = d1 * d1 - dphi_al * dphi_ah;
755    if d2_sq < 0.0 {
756        return 0.5 * (al + ah);
757    }
758    let d2 = (ah - al).signum() * d2_sq.sqrt();
759    let denom = dphi_ah - dphi_al + 2.0 * d2;
760    if denom.abs() < 1e-300 {
761        return 0.5 * (al + ah);
762    }
763    ah - (ah - al) * (dphi_ah + d2 - d1) / denom
764}
765
766/// Minimize a smooth objective with limited-memory BFGS (L-BFGS).
767///
768/// Keeps the last `memory` curvature pairs `(s, y)` and applies the inverse
769/// Hessian approximation with the two-loop recursion; steps come from the same
770/// strong-Wolfe line search as the other solvers.
771///
772/// # Errors
773///
774/// As [`minimize_gradient_descent`], plus `memory == 0`.
775///
776/// # Examples
777///
778/// ```
779/// use tpt_math_optimize_general::{minimize_lbfgs, tpt_math_linalg_dense::DVector};
780///
781/// let cost = |p: &DVector<f64>| (p[0] - 3.0).powi(2) + 50.0 * (p[1] - 2.0).powi(2);
782/// let grad = |p: &DVector<f64>| DVector::from_vec(vec![2.0 * (p[0] - 3.0), 100.0 * (p[1] - 2.0)]);
783/// let best = minimize_lbfgs(cost, grad, DVector::zeros(2), 5, 100).unwrap();
784/// assert!((best[0] - 3.0).abs() < 1e-6 && (best[1] - 2.0).abs() < 1e-6);
785/// ```
786pub fn minimize_lbfgs<F, G>(
787    cost: F,
788    grad: G,
789    init: DVector<f64>,
790    memory: usize,
791    max_iters: u64,
792) -> Result<DVector<f64>, String>
793where
794    F: Fn(&DVector<f64>) -> f64,
795    G: Fn(&DVector<f64>) -> DVector<f64>,
796{
797    minimize_lbfgs_with(cost, grad, init, memory, &Options::new(max_iters)).map(|s| s.param)
798}
799
800/// [`minimize_lbfgs`] with explicit [`Options`], reporting a full [`Solution`].
801///
802/// # Errors
803///
804/// As [`minimize_lbfgs`].
805pub fn minimize_lbfgs_with<F, G>(
806    cost: F,
807    grad: G,
808    init: DVector<f64>,
809    memory: usize,
810    options: &Options,
811) -> Result<Solution, String>
812where
813    F: Fn(&DVector<f64>) -> f64,
814    G: Fn(&DVector<f64>) -> DVector<f64>,
815{
816    validate(&init, options)?;
817    if memory == 0 {
818        return Err("L-BFGS memory must be at least 1".into());
819    }
820    let mut x = init;
821    let mut g = grad(&x);
822    // Curvature pairs, oldest first: (s, y, ρ = 1 / (sᵀy)).
823    let mut pairs: Vec<(DVector<f64>, DVector<f64>, f64)> = Vec::with_capacity(memory);
824    let mut iters: u64 = 0;
825    loop {
826        if g.norm() <= options.gradient_tolerance {
827            return Ok(lbfgs_solution(
828                &cost,
829                x,
830                iters,
831                true,
832                "GradientTolerance",
833                g.norm(),
834            ));
835        }
836        if iters >= options.max_iters {
837            return Ok(lbfgs_solution(&cost, x, iters, false, "MaxIters", g.norm()));
838        }
839
840        // Two-loop recursion: d = −H g with H the implicit inverse Hessian.
841        let mut q = g.clone();
842        let mut alphas = vec![0.0_f64; pairs.len()];
843        for (idx, (s, y, rho)) in pairs.iter().enumerate().rev() {
844            let a = rho * s.dot(&q);
845            alphas[idx] = a;
846            q = q - y.clone() * a;
847        }
848        let gamma = match pairs.last() {
849            Some((s, y, _)) => s.dot(y) / y.dot(y),
850            None => 1.0,
851        };
852        let mut r = q * gamma;
853        for (idx, (s, y, rho)) in pairs.iter().enumerate() {
854            let beta = rho * y.dot(&r);
855            r = r + s.clone() * (alphas[idx] - beta);
856        }
857        let mut dir = -r;
858        if g.dot(&dir) >= 0.0 {
859            // Not a descent direction: fall back to steepest descent and forget history.
860            pairs.clear();
861            dir = -g.clone();
862        }
863
864        let mut alpha = line_search(&cost, &grad, &x, &dir);
865        if alpha == 0.0 {
866            if pairs.is_empty() {
867                return Ok(lbfgs_solution(
868                    &cost,
869                    x,
870                    iters,
871                    false,
872                    "LineSearchStalled",
873                    g.norm(),
874                ));
875            }
876            // A stale quasi-Newton direction stalled: restart from steepest descent.
877            pairs.clear();
878            dir = -g.clone();
879            alpha = line_search(&cost, &grad, &x, &dir);
880            if alpha == 0.0 {
881                return Ok(lbfgs_solution(
882                    &cost,
883                    x,
884                    iters,
885                    false,
886                    "LineSearchStalled",
887                    g.norm(),
888                ));
889            }
890        }
891
892        let x_new = x.clone() + dir * alpha;
893        let g_new = grad(&x_new);
894        let s = x_new.clone() - x.clone();
895        let y = g_new.clone() - g.clone();
896        let sy = s.dot(&y);
897        // Keep only pairs with positive curvature, which keeps H positive definite.
898        if sy > 1e-12 * y.dot(&y).sqrt() * s.norm() {
899            if pairs.len() == memory {
900                pairs.remove(0);
901            }
902            pairs.push((s, y, 1.0 / sy));
903        }
904        x = x_new;
905        g = g_new;
906        iters += 1;
907    }
908}
909
910fn lbfgs_solution<F>(
911    cost: &F,
912    param: DVector<f64>,
913    iters: u64,
914    converged: bool,
915    termination: &str,
916    residual: f64,
917) -> Solution
918where
919    F: Fn(&DVector<f64>) -> f64,
920{
921    Solution {
922        cost: cost(&param),
923        param,
924        iters,
925        converged,
926        termination: termination.to_string(),
927        residual,
928    }
929}
930
931/// Central finite-difference approximation of the gradient of `cost` at `x`,
932/// with step `h · max(1, |xᵢ|)` in each coordinate. Use it when no analytic
933/// gradient exists.
934///
935/// # Examples
936///
937/// ```
938/// use tpt_math_optimize_general::{numerical_gradient, tpt_math_linalg_dense::DVector};
939///
940/// let cost = |p: &DVector<f64>| p[0] * p[0] * p[1];
941/// let g = numerical_gradient(&cost, &DVector::from_vec(vec![3.0, 2.0]), 1e-6);
942/// assert!((g[0] - 12.0).abs() < 1e-6); // d/dx = 2xy
943/// assert!((g[1] - 9.0).abs() < 1e-6); // d/dy = x²
944/// ```
945pub fn numerical_gradient<F>(cost: &F, x: &DVector<f64>, h: f64) -> DVector<f64>
946where
947    F: Fn(&DVector<f64>) -> f64,
948{
949    let n = x.len();
950    let mut g = vec![0.0_f64; n];
951    let mut probe = x.clone();
952    for (i, gi) in g.iter_mut().enumerate() {
953        let xi = x[i];
954        // Scale the step with |xᵢ| so that the two probes stay distinct in floating
955        // point far from the origin. An absolute step rounds to zero there and
956        // reports a flat gradient.
957        let step = h * xi.abs().max(1.0);
958        probe.as_mut_slice()[i] = xi + step;
959        let fp = cost(&probe);
960        probe.as_mut_slice()[i] = xi - step;
961        let fm = cost(&probe);
962        probe.as_mut_slice()[i] = xi;
963        *gi = (fp - fm) / (2.0 * step);
964    }
965    DVector::from_vec(g)
966}
967
968#[cfg(test)]
969mod numerical_gradient_scale_tests {
970    use super::*;
971
972    #[test]
973    fn gradient_is_resolved_far_from_the_origin() {
974        // d/dx (x) = 1 holds at every point, including |x| = 3e10, where an
975        // absolute step of 1e-6 would round to zero.
976        let cost = |p: &DVector<f64>| p[0];
977        let g = numerical_gradient(&cost, &DVector::from_vec(vec![-3.0e10]), 1e-6);
978        assert!((g[0] - 1.0).abs() < 1e-6, "{}", g[0]);
979    }
980}
981
982/// Minimize a derivative-free objective with the Nelder–Mead simplex method.
983///
984/// The initial simplex is `init` plus `step` along each coordinate axis.
985/// Convergence is declared when the spread of costs over the simplex and the
986/// simplex diameter are both at most `options.gradient_tolerance` (relative to
987/// the best cost's and point's magnitudes).
988///
989/// # Errors
990///
991/// Returns an error for an empty or non-finite `init`, a negative tolerance, or
992/// a non-positive or non-finite `step`.
993///
994/// # Examples
995///
996/// ```
997/// use tpt_math_optimize_general::{minimize_nelder_mead_with, Options, tpt_math_linalg_dense::DVector};
998///
999/// let cost = |p: &DVector<f64>| (p[0] - 3.0).powi(2) + (p[1] + 1.0).powi(2);
1000/// let s = minimize_nelder_mead_with(cost, DVector::zeros(2), 1.0, &Options::new(500)).unwrap();
1001/// assert!((s.param[0] - 3.0).abs() < 1e-5);
1002/// assert!((s.param[1] + 1.0).abs() < 1e-5);
1003/// ```
1004pub fn minimize_nelder_mead_with<F>(
1005    cost: F,
1006    init: DVector<f64>,
1007    step: f64,
1008    options: &Options,
1009) -> Result<Solution, String>
1010where
1011    F: Fn(&DVector<f64>) -> f64,
1012{
1013    validate(&init, options)?;
1014    if !(step.is_finite() && step > 0.0) {
1015        return Err(format!("initial simplex step must be positive, got {step}"));
1016    }
1017    const ALPHA: f64 = 1.0; // reflection
1018    const GAMMA: f64 = 2.0; // expansion
1019    const RHO: f64 = 0.5; // contraction
1020    const SIGMA: f64 = 0.5; // shrink
1021
1022    let n = init.len();
1023    let mut simplex: Vec<(DVector<f64>, f64)> = Vec::with_capacity(n + 1);
1024    let f0 = cost(&init);
1025    simplex.push((init.clone(), f0));
1026    for i in 0..n {
1027        let mut v = init.clone();
1028        v.as_mut_slice()[i] += step;
1029        let fv = cost(&v);
1030        simplex.push((v, fv));
1031    }
1032
1033    let tol = options.gradient_tolerance;
1034    let mut iters: u64 = 0;
1035    loop {
1036        simplex.sort_by(|a, b| a.1.total_cmp(&b.1));
1037        let best = simplex[0].1;
1038        let worst = simplex[n].1;
1039        // Stop only when both the cost spread and the simplex diameter are small:
1040        // a flat cost spread alone can hold the simplex ~√tol away from the optimum.
1041        let x_best = simplex[0].0.clone();
1042        let diameter = simplex
1043            .iter()
1044            .map(|(x, _)| (x.clone() - x_best.clone()).norm())
1045            .fold(0.0_f64, f64::max);
1046        let x_scale = 1.0 + x_best.norm();
1047        if (worst - best).abs() <= tol * (1.0 + best.abs()) && diameter <= tol * x_scale {
1048            return Ok(nelder_mead_solution(simplex, iters, true, "CostTolerance"));
1049        }
1050        if iters >= options.max_iters {
1051            return Ok(nelder_mead_solution(simplex, iters, false, "MaxIters"));
1052        }
1053        iters += 1;
1054
1055        // Centroid of every vertex except the worst.
1056        let mut centroid = DVector::zeros(n);
1057        for (x, _) in &simplex[..n] {
1058            centroid = centroid + x.clone();
1059        }
1060        let centroid = centroid / (n as f64);
1061        let x_worst = simplex[n].0.clone();
1062        let f_second_worst = simplex[n - 1].1;
1063
1064        let along = |t: f64| centroid.clone() + (centroid.clone() - x_worst.clone()) * t;
1065        let x_r = along(ALPHA);
1066        let f_r = cost(&x_r);
1067        if f_r < best {
1068            let x_e = along(ALPHA * GAMMA);
1069            let f_e = cost(&x_e);
1070            simplex[n] = if f_e < f_r { (x_e, f_e) } else { (x_r, f_r) };
1071        } else if f_r < f_second_worst {
1072            simplex[n] = (x_r, f_r);
1073        } else {
1074            // Contract toward the centroid: outside if the reflection improved on
1075            // the worst vertex, inside otherwise.
1076            let (x_c, f_c) = if f_r < worst {
1077                let x_c = centroid.clone() + (x_r.clone() - centroid.clone()) * RHO;
1078                let f_c = cost(&x_c);
1079                (x_c, f_c)
1080            } else {
1081                let x_c = centroid.clone() + (x_worst.clone() - centroid.clone()) * RHO;
1082                let f_c = cost(&x_c);
1083                (x_c, f_c)
1084            };
1085            if f_c < f_r.min(worst) {
1086                simplex[n] = (x_c, f_c);
1087            } else {
1088                // Shrink every vertex toward the best one.
1089                let x_best = simplex[0].0.clone();
1090                for vertex in simplex.iter_mut().skip(1) {
1091                    let v = x_best.clone() + (vertex.0.clone() - x_best.clone()) * SIGMA;
1092                    vertex.1 = cost(&v);
1093                    vertex.0 = v;
1094                }
1095            }
1096        }
1097    }
1098}
1099
1100/// Minimize a derivative-free objective with Nelder–Mead, returning only the
1101/// best point. See [`minimize_nelder_mead_with`].
1102///
1103/// # Errors
1104///
1105/// As [`minimize_nelder_mead_with`].
1106pub fn minimize_nelder_mead<F>(
1107    cost: F,
1108    init: DVector<f64>,
1109    step: f64,
1110    max_iters: u64,
1111) -> Result<DVector<f64>, String>
1112where
1113    F: Fn(&DVector<f64>) -> f64,
1114{
1115    minimize_nelder_mead_with(cost, init, step, &Options::new(max_iters)).map(|s| s.param)
1116}
1117
1118fn nelder_mead_solution(
1119    mut simplex: Vec<(DVector<f64>, f64)>,
1120    iters: u64,
1121    converged: bool,
1122    termination: &'static str,
1123) -> Solution {
1124    // The residual is the cost spread over the simplex, measured before the
1125    // sort because it is the same either way.
1126    let best = simplex.iter().map(|v| v.1).fold(f64::INFINITY, f64::min);
1127    let worst = simplex
1128        .iter()
1129        .map(|v| v.1)
1130        .fold(f64::NEG_INFINITY, f64::max);
1131    simplex.sort_by(|a, b| a.1.total_cmp(&b.1));
1132    let (param, cost) = simplex.swap_remove(0);
1133    Solution {
1134        param,
1135        cost,
1136        iters,
1137        converged,
1138        termination: termination.to_string(),
1139        residual: worst - best,
1140    }
1141}
1142
1143#[cfg(test)]
1144mod tests {
1145    use super::*;
1146
1147    /// f(x, y) = (x - 3)² + (y - 2)², minimum 0 at (3, 2).
1148    fn bowl_cost(p: &DVector<f64>) -> f64 {
1149        (p[0] - 3.0).powi(2) + (p[1] - 2.0).powi(2)
1150    }
1151
1152    fn bowl_grad(p: &DVector<f64>) -> DVector<f64> {
1153        DVector::from_vec(vec![2.0 * (p[0] - 3.0), 2.0 * (p[1] - 2.0)])
1154    }
1155
1156    fn bowl_hess(_: &DVector<f64>) -> DMatrix<f64> {
1157        DMatrix::from_diagonal(&DVector::from_vec(vec![2.0, 2.0]))
1158    }
1159
1160    /// f(x, y) = (x - 3)² + 50 (y - 2)²: same minimum, condition number 50.
1161    fn valley_cost(p: &DVector<f64>) -> f64 {
1162        (p[0] - 3.0).powi(2) + 50.0 * (p[1] - 2.0).powi(2)
1163    }
1164
1165    fn valley_grad(p: &DVector<f64>) -> DVector<f64> {
1166        DVector::from_vec(vec![2.0 * (p[0] - 3.0), 100.0 * (p[1] - 2.0)])
1167    }
1168
1169    fn assert_close(actual: &DVector<f64>, expected: &[f64], tol: f64) {
1170        assert_eq!(actual.len(), expected.len());
1171        for (i, want) in expected.iter().enumerate() {
1172            assert!(
1173                (actual[i] - want).abs() < tol,
1174                "component {i}: {} is not within {tol} of {want}",
1175                actual[i]
1176            );
1177        }
1178    }
1179
1180    #[test]
1181    fn line_search_expansion_then_overshoot_stays_finite() {
1182        // g(a) = -a + 0.1 a⁸ along d = 1 from x = 0: the first trial a = 1
1183        // satisfies sufficient decrease but not the curvature condition, and
1184        // a = 2 overshoots. The zoom must bracket on [1, 2], not on [1, 1].
1185        let cost = |p: &DVector<f64>| -p[0] + 0.1 * p[0].powi(8);
1186        let grad = |p: &DVector<f64>| DVector::from_vec(vec![-1.0 + 0.8 * p[0].powi(7)]);
1187        let x = DVector::from_vec(vec![0.0]);
1188        let d = DVector::from_vec(vec![1.0]);
1189        let a = line_search(&cost, &grad, &x, &d);
1190        assert!(a.is_finite() && a > 0.0, "step was {a}");
1191        assert!(cost(&(x.clone() + d.clone() * a)) < cost(&x));
1192        let dphi = grad(&(x + d * a))[0];
1193        assert!(dphi.abs() <= 0.1 * 1.0, "curvature violated: {dphi}");
1194    }
1195
1196    #[test]
1197    fn gradient_descent_stops_when_line_search_stalls() {
1198        // The cost rises along the descent direction -grad = +1 (inconsistent
1199        // gradient), so no step decreases it. The solver must stop instead of
1200        // spinning to `max_iters`.
1201        let s = minimize_gradient_descent_with(
1202            |p: &DVector<f64>| p[0],
1203            |_: &DVector<f64>| DVector::from_vec(vec![-1.0]),
1204            DVector::from_vec(vec![1.0]),
1205            &Options::new(1_000_000),
1206        )
1207        .unwrap();
1208        assert!(!s.converged);
1209        assert!(s.iters < 1_000_000);
1210        assert_eq!(s.termination, "LineSearchStalled");
1211    }
1212
1213    #[test]
1214    fn gradient_descent_minimizes_scalar_square() {
1215        // f(x) = x², minimum 0 at x = 0.
1216        let best = minimize_gradient_descent(
1217            |p: &DVector<f64>| p[0] * p[0],
1218            |p: &DVector<f64>| DVector::from_vec(vec![2.0 * p[0]]),
1219            DVector::from_vec(vec![7.5]),
1220            50,
1221        )
1222        .unwrap();
1223
1224        assert_close(&best, &[0.0], 1e-8);
1225    }
1226
1227    #[test]
1228    fn gradient_descent_minimizes_bowl() {
1229        let best = minimize_gradient_descent(bowl_cost, bowl_grad, DVector::zeros(2), 100).unwrap();
1230
1231        assert_close(&best, &[3.0, 2.0], 1e-6);
1232        assert!(bowl_cost(&best) < 1e-12);
1233    }
1234
1235    #[test]
1236    fn gradient_descent_reports_convergence_and_cost() {
1237        let solution = minimize_gradient_descent_with(
1238            bowl_cost,
1239            bowl_grad,
1240            DVector::from_vec(vec![-4.0, 9.0]),
1241            &Options::new(200),
1242        )
1243        .unwrap();
1244
1245        assert!(solution.converged, "termination: {}", solution.termination);
1246        assert!(solution.iters <= 200);
1247        assert!(!solution.termination.is_empty());
1248        assert!(solution.cost < 1e-12, "cost was {}", solution.cost);
1249        assert!((solution.cost - bowl_cost(&solution.param)).abs() < 1e-15);
1250    }
1251
1252    #[test]
1253    fn gradient_descent_survives_starting_at_the_optimum() {
1254        // Zero gradient at the start: the run must stop immediately, converged.
1255        let solution = minimize_gradient_descent_with(
1256            bowl_cost,
1257            bowl_grad,
1258            DVector::from_vec(vec![3.0, 2.0]),
1259            &Options::new(25),
1260        )
1261        .unwrap();
1262
1263        assert!(solution.converged);
1264        assert!(solution.iters <= 1);
1265        assert_close(&solution.param, &[3.0, 2.0], 1e-15);
1266    }
1267
1268    #[test]
1269    fn conjugate_gradient_handles_ill_conditioned_valley() {
1270        let solution = minimize_conjugate_gradient_with(
1271            valley_cost,
1272            valley_grad,
1273            DVector::zeros(2),
1274            &Options::new(200),
1275        )
1276        .unwrap();
1277
1278        assert_close(&solution.param, &[3.0, 2.0], 1e-5);
1279        assert!(solution.cost < 1e-9, "cost was {}", solution.cost);
1280    }
1281
1282    #[test]
1283    fn conjugate_gradient_minimizes_rosenbrock() {
1284        // The classic banana valley: minimum 0 at (1, 1).
1285        let cost = |p: &DVector<f64>| (1.0 - p[0]).powi(2) + 100.0 * (p[1] - p[0] * p[0]).powi(2);
1286        let grad = |p: &DVector<f64>| {
1287            DVector::from_vec(vec![
1288                -2.0 * (1.0 - p[0]) - 400.0 * p[0] * (p[1] - p[0] * p[0]),
1289                200.0 * (p[1] - p[0] * p[0]),
1290            ])
1291        };
1292
1293        // Nonlinear CG on Rosenbrock converges slowly without preconditioning;
1294        // give it a generous iteration budget.
1295        let best =
1296            minimize_conjugate_gradient(cost, grad, DVector::from_vec(vec![-1.2, 1.0]), 5000)
1297                .unwrap();
1298
1299        assert_close(&best, &[1.0, 1.0], 1e-3);
1300    }
1301
1302    #[test]
1303    fn newton_solves_quadratic_in_one_step() {
1304        let solution = minimize_newton_with(
1305            bowl_cost,
1306            bowl_grad,
1307            bowl_hess,
1308            DVector::from_vec(vec![-10.0, 40.0]),
1309            &Options::new(25),
1310        )
1311        .unwrap();
1312
1313        assert_close(&solution.param, &[3.0, 2.0], 1e-12);
1314        assert!(solution.converged);
1315        assert!(solution.iters <= 2, "took {} iterations", solution.iters);
1316        assert!(solution.cost < 1e-24);
1317    }
1318
1319    #[test]
1320    fn newton_minimizes_non_quadratic() {
1321        // f(x) = exp(x) - x, minimum 1 at x = 0.
1322        let best = minimize_newton(
1323            |p: &DVector<f64>| p[0].exp() - p[0],
1324            |p: &DVector<f64>| DVector::from_vec(vec![p[0].exp() - 1.0]),
1325            |p: &DVector<f64>| DMatrix::from_vec(1, 1, vec![p[0].exp()]),
1326            DVector::from_vec(vec![1.5]),
1327            50,
1328        )
1329        .unwrap();
1330
1331        assert_close(&best, &[0.0], 1e-7);
1332    }
1333
1334    #[test]
1335    fn solvers_agree_on_the_same_problem() {
1336        let init = DVector::from_vec(vec![-2.0, 6.5]);
1337        let gd = minimize_gradient_descent(bowl_cost, bowl_grad, init.clone(), 100).unwrap();
1338        let cg = minimize_conjugate_gradient(bowl_cost, bowl_grad, init.clone(), 100).unwrap();
1339        let newton = minimize_newton(bowl_cost, bowl_grad, bowl_hess, init, 100).unwrap();
1340
1341        assert_close(&gd, &[3.0, 2.0], 1e-6);
1342        assert_close(&cg, &[3.0, 2.0], 1e-6);
1343        assert_close(&newton, &[3.0, 2.0], 1e-12);
1344    }
1345
1346    #[test]
1347    fn max_iters_caps_the_run() {
1348        // One iteration is nowhere near enough for this starting point.
1349        let solution = minimize_gradient_descent_with(
1350            valley_cost,
1351            valley_grad,
1352            DVector::from_vec(vec![-50.0, -50.0]),
1353            &Options::new(1),
1354        )
1355        .unwrap();
1356
1357        assert_eq!(solution.iters, 1);
1358        assert!(!solution.converged);
1359        assert!(solution.cost > 0.0);
1360    }
1361
1362    #[test]
1363    fn zero_iterations_returns_the_initial_point() {
1364        let init = DVector::from_vec(vec![1.0, -1.0]);
1365        let solution =
1366            minimize_gradient_descent_with(bowl_cost, bowl_grad, init.clone(), &Options::new(0))
1367                .unwrap();
1368
1369        assert_eq!(solution.param, init);
1370        assert_eq!(solution.iters, 0);
1371        assert!((solution.cost - bowl_cost(&init)).abs() < 1e-15);
1372    }
1373
1374    #[test]
1375    fn empty_initial_point_is_rejected() {
1376        let err =
1377            minimize_gradient_descent(bowl_cost, bowl_grad, DVector::zeros(0), 10).unwrap_err();
1378        assert!(err.contains("empty"), "unexpected message: {err}");
1379    }
1380
1381    #[test]
1382    fn non_finite_initial_point_is_rejected() {
1383        let err = minimize_gradient_descent(
1384            bowl_cost,
1385            bowl_grad,
1386            DVector::from_vec(vec![f64::NAN, 0.0]),
1387            10,
1388        )
1389        .unwrap_err();
1390        assert!(err.contains("finite"), "unexpected message: {err}");
1391    }
1392
1393    #[test]
1394    fn negative_gradient_tolerance_is_rejected() {
1395        let options = Options::new(10).with_gradient_tolerance(-1.0);
1396        let err = minimize_gradient_descent_with(bowl_cost, bowl_grad, DVector::zeros(2), &options)
1397            .unwrap_err();
1398        assert!(err.contains("tolerance"), "unexpected message: {err}");
1399    }
1400
1401    #[test]
1402    fn singular_hessian_is_reported_as_an_error() {
1403        let err = minimize_newton(
1404            bowl_cost,
1405            bowl_grad,
1406            |_: &DVector<f64>| DMatrix::zeros(2, 2),
1407            DVector::zeros(2),
1408            10,
1409        )
1410        .unwrap_err();
1411
1412        assert!(!err.is_empty());
1413    }
1414
1415    #[test]
1416    fn tagged_vectors_round_trip() {
1417        let tagged: TaggedVec<()> = point_to_tagged(DVector::from_vec(vec![3.0, 4.0]));
1418        let raw = point_from_tagged(&tagged);
1419
1420        let best = minimize_gradient_descent(bowl_cost, bowl_grad, raw, 100).unwrap();
1421        let back: TaggedVec<()> = point_to_tagged(best);
1422
1423        assert_close(back.raw(), &[3.0, 2.0], 1e-6);
1424    }
1425
1426    #[test]
1427    fn options_defaults_are_sane() {
1428        let options = Options::default();
1429        assert_eq!(options.max_iters, DEFAULT_MAX_ITERS);
1430        assert_eq!(options.gradient_tolerance, DEFAULT_GRADIENT_TOLERANCE);
1431        assert_eq!(Options::new(DEFAULT_MAX_ITERS), options);
1432    }
1433
1434    #[test]
1435    fn numerical_gradient_matches_analytic() {
1436        let cost = |p: &DVector<f64>| p[0] * p[0] * p[1];
1437        let g = numerical_gradient(&cost, &DVector::from_vec(vec![3.0, 2.0]), 1e-6);
1438        assert_close(&g, &[12.0, 9.0], 1e-6);
1439    }
1440
1441    #[test]
1442    fn nelder_mead_minimizes_bowl_without_gradients() {
1443        let s = minimize_nelder_mead_with(bowl_cost, DVector::zeros(2), 1.0, &Options::new(1000))
1444            .unwrap();
1445        assert!(s.converged, "termination: {}", s.termination);
1446        assert_close(&s.param, &[3.0, 2.0], 1e-6);
1447    }
1448
1449    #[test]
1450    fn nelder_mead_minimizes_rosenbrock() {
1451        let rosen = |p: &DVector<f64>| (1.0 - p[0]).powi(2) + 100.0 * (p[1] - p[0] * p[0]).powi(2);
1452        let x = minimize_nelder_mead(rosen, DVector::from_vec(vec![-1.2, 1.0]), 0.5, 5000).unwrap();
1453        assert_close(&x, &[1.0, 1.0], 1e-3);
1454    }
1455
1456    #[test]
1457    fn nelder_mead_rejects_bad_step() {
1458        assert!(minimize_nelder_mead(bowl_cost, DVector::zeros(2), 0.0, 10).is_err());
1459    }
1460
1461    #[test]
1462    fn lbfgs_minimizes_rosenbrock() {
1463        let rosen = |p: &DVector<f64>| (1.0 - p[0]).powi(2) + 100.0 * (p[1] - p[0] * p[0]).powi(2);
1464        let rosen_grad = |p: &DVector<f64>| {
1465            DVector::from_vec(vec![
1466                -2.0 * (1.0 - p[0]) - 400.0 * p[0] * (p[1] - p[0] * p[0]),
1467                200.0 * (p[1] - p[0] * p[0]),
1468            ])
1469        };
1470        let s = minimize_lbfgs_with(
1471            rosen,
1472            rosen_grad,
1473            DVector::from_vec(vec![-1.2, 1.0]),
1474            8,
1475            &Options::new(500),
1476        )
1477        .unwrap();
1478        assert!(s.converged, "termination: {}", s.termination);
1479        assert_close(&s.param, &[1.0, 1.0], 1e-5);
1480    }
1481
1482    #[test]
1483    fn lbfgs_handles_ill_conditioned_valley() {
1484        let best = minimize_lbfgs(valley_cost, valley_grad, DVector::zeros(2), 5, 200).unwrap();
1485        assert_close(&best, &[3.0, 2.0], 1e-6);
1486    }
1487
1488    #[test]
1489    fn lbfgs_rejects_zero_memory() {
1490        assert!(minimize_lbfgs(bowl_cost, bowl_grad, DVector::zeros(2), 0, 10).is_err());
1491    }
1492}
1493
1494#[cfg(test)]
1495mod report_tests {
1496    use super::*;
1497    use tpt_math_numeric::SolveStatus;
1498
1499    fn quadratic_cost(x: &DVector<f64>) -> f64 {
1500        (x[0] - 1.0).powi(2) + 2.0 * (x[1] + 2.0).powi(2)
1501    }
1502
1503    fn quadratic_grad(x: &DVector<f64>) -> DVector<f64> {
1504        DVector::from_vec(vec![2.0 * (x[0] - 1.0), 4.0 * (x[1] + 2.0)])
1505    }
1506
1507    #[test]
1508    fn converged_run_reports_converged_with_small_residual() {
1509        let (f, g) = (quadratic_cost, quadratic_grad);
1510        let opts = Options::new(500);
1511        let sol = minimize_lbfgs_with(f, g, DVector::from_vec(vec![5.0, 5.0]), 5, &opts).unwrap();
1512        let report = sol.report();
1513        assert_eq!(report.status, SolveStatus::Converged);
1514        assert!(report.residual <= opts.gradient_tolerance);
1515        assert_eq!(report.iterations, sol.iters as usize);
1516    }
1517
1518    #[test]
1519    fn exhausted_budget_reports_not_converged() {
1520        let (f, g) = (quadratic_cost, quadratic_grad);
1521        let sol = minimize_gradient_descent_with(
1522            f,
1523            g,
1524            DVector::from_vec(vec![5.0, 5.0]),
1525            &Options::new(1),
1526        )
1527        .unwrap();
1528        assert_eq!(sol.report().status, SolveStatus::NotConverged);
1529        assert!(sol.report().residual > 0.0);
1530    }
1531
1532    #[test]
1533    fn nelder_mead_residual_is_cost_spread() {
1534        let f = |x: &DVector<f64>| (x[0] - 3.0).powi(2);
1535        let sol =
1536            minimize_nelder_mead_with(f, DVector::from_vec(vec![0.0]), 1.0, &Options::new(400))
1537                .unwrap();
1538        assert!(sol.residual >= 0.0);
1539        assert!(sol.residual < 1e-6, "{}", sol.residual);
1540    }
1541}