Skip to main content

solow_optimize/
optimizer.rs

1//! Unconstrained optimizers: Newton–Raphson (analytic derivatives) and BFGS
2//! (gradient only, with backtracking line search).
3//!
4//! Both *minimize*. To maximize a log-likelihood, minimize its negative — or use
5//! [`newton_stationary`], which simply drives the gradient to zero (max or min).
6
7use ndarray::{Array1, Array2};
8use solow_core::error::Result;
9use solow_linalg::{lstsq, solve};
10
11/// Outcome of an optimization run.
12#[derive(Clone, Debug)]
13pub struct OptimizeResult {
14    /// The located point.
15    pub x: Array1<f64>,
16    /// Objective value there.
17    pub fval: f64,
18    /// Iterations performed.
19    pub iters: usize,
20    /// Whether the convergence test was met.
21    pub converged: bool,
22    /// Final gradient norm.
23    pub grad_norm: f64,
24}
25
26/// Newton iteration that drives the gradient of an objective to zero.
27///
28/// `fgh(x)` returns `(value, gradient, hessian)`. The update is
29/// `x ← x − H⁻¹ g`, which converges to a local maximum or minimum depending on
30/// the curvature. A pseudoinverse fallback is used if `H` is singular.
31pub fn newton_stationary<F>(
32    start: &Array1<f64>,
33    mut fgh: F,
34    maxiter: usize,
35    gtol: f64,
36) -> Result<OptimizeResult>
37where
38    F: FnMut(&Array1<f64>) -> (f64, Array1<f64>, Array2<f64>),
39{
40    let mut x = start.clone();
41    let mut fval;
42    let mut gnorm;
43    let mut converged = false;
44    let mut it = 0;
45    loop {
46        let (f, g, h) = fgh(&x);
47        fval = f;
48        gnorm = g.dot(&g).sqrt();
49        if gnorm < gtol {
50            converged = true;
51            break;
52        }
53        if it >= maxiter {
54            break;
55        }
56        let step = match solve(&h, &g) {
57            Ok(s) => s,
58            Err(_) => lstsq(&h, &g)?,
59        };
60        let step_norm = step.dot(&step).sqrt();
61        let xnorm = x.dot(&x).sqrt();
62        // Damped Newton: take the largest fraction `t ∈ {1, 1/2, 1/4, …}` of the
63        // Newton step that reduces the gradient norm. Near the optimum the full step
64        // (`t = 1`) is always accepted on the first try, preserving Newton's quadratic
65        // convergence (and identical iterates for well-behaved problems); on ill-scaled
66        // designs the backtracking keeps the solver globally convergent instead of
67        // overshooting into a non-finite region.
68        let mut t = 1.0;
69        let mut x_new = &x - &step;
70        for _ in 0..40 {
71            let g_new = fgh(&x_new).1;
72            let gnew_norm = g_new.dot(&g_new).sqrt();
73            if gnew_norm.is_finite() && gnew_norm < gnorm {
74                break;
75            }
76            t *= 0.5;
77            x_new = &x - &(t * &step);
78            if t < 1e-12 {
79                break;
80            }
81        }
82        x = x_new;
83        it += 1;
84        // Scale-aware convergence: the full (undamped) Newton step — the Newton
85        // decrement `‖H⁻¹g‖` — has shrunk to nothing relative to the parameters. This
86        // catches ill-scaled designs where the raw gradient norm has a floating-point
87        // roundoff floor above `gtol` even though the MLE has been reached. The Newton
88        // step is small only *near* the optimum, so for well-behaved problems the
89        // `gnorm < gtol` test above fires first and the converged iterate is unchanged.
90        if step_norm <= 1e-12 * (1.0 + xnorm) {
91            converged = true;
92            break;
93        }
94    }
95    Ok(OptimizeResult {
96        x,
97        fval,
98        iters: it,
99        converged,
100        grad_norm: gnorm,
101    })
102}
103
104/// Minimize `f` with gradient `grad` using BFGS and Armijo backtracking.
105pub fn minimize_bfgs<F, G>(
106    start: &Array1<f64>,
107    mut f: F,
108    mut grad: G,
109    maxiter: usize,
110    gtol: f64,
111) -> Result<OptimizeResult>
112where
113    F: FnMut(&Array1<f64>) -> f64,
114    G: FnMut(&Array1<f64>) -> Array1<f64>,
115{
116    let n = start.len();
117    let mut x = start.clone();
118    let mut hinv = Array2::<f64>::eye(n); // inverse-Hessian approximation
119    let mut g = grad(&x);
120    let mut fval = f(&x);
121    let mut converged = false;
122    let mut it = 0;
123
124    while it < maxiter {
125        let gnorm = g.dot(&g).sqrt();
126        if gnorm < gtol {
127            converged = true;
128            break;
129        }
130        // Search direction d = -Hinv g.
131        let d = hinv.dot(&g).mapv(|v| -v);
132        // Backtracking line search (Armijo).
133        let slope = g.dot(&d);
134        let mut alpha = 1.0;
135        let c = 1e-4;
136        let rho = 0.5;
137        let mut x_new = &x + &(alpha * &d);
138        let mut f_new = f(&x_new);
139        let mut ls = 0;
140        while f_new > fval + c * alpha * slope && ls < 50 {
141            alpha *= rho;
142            x_new = &x + &(alpha * &d);
143            f_new = f(&x_new);
144            ls += 1;
145        }
146        let g_new = grad(&x_new);
147        // BFGS update of the inverse Hessian.
148        let s = &x_new - &x;
149        let yv = &g_new - &g;
150        let sy = s.dot(&yv);
151        if sy > 1e-12 {
152            let rho_bfgs = 1.0 / sy;
153            let i = Array2::<f64>::eye(n);
154            // (I - ρ s yᵀ) Hinv (I - ρ y sᵀ) + ρ s sᵀ
155            let sy_outer = outer(&s, &yv).mapv(|v| v * rho_bfgs);
156            let ys_outer = outer(&yv, &s).mapv(|v| v * rho_bfgs);
157            let left = &i - &sy_outer;
158            let right = &i - &ys_outer;
159            hinv = left.dot(&hinv).dot(&right) + outer(&s, &s).mapv(|v| v * rho_bfgs);
160        }
161        x = x_new;
162        g = g_new;
163        fval = f_new;
164        it += 1;
165    }
166
167    Ok(OptimizeResult {
168        x,
169        fval,
170        iters: it,
171        converged,
172        grad_norm: g.dot(&g).sqrt(),
173    })
174}
175
176fn outer(a: &Array1<f64>, b: &Array1<f64>) -> Array2<f64> {
177    let n = a.len();
178    let m = b.len();
179    let mut o = Array2::<f64>::zeros((n, m));
180    for i in 0..n {
181        for j in 0..m {
182            o[[i, j]] = a[i] * b[j];
183        }
184    }
185    o
186}
187
188#[cfg(test)]
189mod tests {
190    use super::*;
191    use crate::numdiff::approx_fprime;
192    use approx::assert_abs_diff_eq;
193    use ndarray::array;
194
195    #[test]
196    fn newton_minimizes_quadratic() {
197        // f(x) = (x0-3)^2 + 2 (x1+1)^2, min at (3, -1).
198        let fgh = |x: &Array1<f64>| {
199            let f = (x[0] - 3.0).powi(2) + 2.0 * (x[1] + 1.0).powi(2);
200            let g = array![2.0 * (x[0] - 3.0), 4.0 * (x[1] + 1.0)];
201            let h = array![[2.0, 0.0], [0.0, 4.0]];
202            (f, g, h)
203        };
204        let r = newton_stationary(&array![0.0, 0.0], fgh, 50, 1e-10).unwrap();
205        assert!(r.converged);
206        assert_abs_diff_eq!(r.x[0], 3.0, epsilon = 1e-8);
207        assert_abs_diff_eq!(r.x[1], -1.0, epsilon = 1e-8);
208    }
209
210    #[test]
211    fn bfgs_minimizes_rosenbrock() {
212        // Rosenbrock: min at (1,1).
213        let f = |x: &Array1<f64>| (1.0 - x[0]).powi(2) + 100.0 * (x[1] - x[0] * x[0]).powi(2);
214        let g = |x: &Array1<f64>| approx_fprime(x, f);
215        let r = minimize_bfgs(&array![-1.2, 1.0], f, g, 1000, 1e-8).unwrap();
216        assert!(r.converged, "did not converge (grad_norm {})", r.grad_norm);
217        assert_abs_diff_eq!(r.x[0], 1.0, epsilon = 1e-4);
218        assert_abs_diff_eq!(r.x[1], 1.0, epsilon = 1e-4);
219    }
220}