use ndarray::{Array1, Array2};
use solow_core::error::Result;
use solow_linalg::{lstsq, solve};
#[derive(Clone, Debug)]
pub struct OptimizeResult {
pub x: Array1<f64>,
pub fval: f64,
pub iters: usize,
pub converged: bool,
pub grad_norm: f64,
}
pub fn newton_stationary<F>(
start: &Array1<f64>,
mut fgh: F,
maxiter: usize,
gtol: f64,
) -> Result<OptimizeResult>
where
F: FnMut(&Array1<f64>) -> (f64, Array1<f64>, Array2<f64>),
{
let mut x = start.clone();
let mut fval;
let mut gnorm;
let mut converged = false;
let mut it = 0;
loop {
let (f, g, h) = fgh(&x);
fval = f;
gnorm = g.dot(&g).sqrt();
if gnorm < gtol {
converged = true;
break;
}
if it >= maxiter {
break;
}
let step = match solve(&h, &g) {
Ok(s) => s,
Err(_) => lstsq(&h, &g)?,
};
let step_norm = step.dot(&step).sqrt();
let xnorm = x.dot(&x).sqrt();
let mut t = 1.0;
let mut x_new = &x - &step;
for _ in 0..40 {
let g_new = fgh(&x_new).1;
let gnew_norm = g_new.dot(&g_new).sqrt();
if gnew_norm.is_finite() && gnew_norm < gnorm {
break;
}
t *= 0.5;
x_new = &x - &(t * &step);
if t < 1e-12 {
break;
}
}
x = x_new;
it += 1;
if step_norm <= 1e-12 * (1.0 + xnorm) {
converged = true;
break;
}
}
Ok(OptimizeResult {
x,
fval,
iters: it,
converged,
grad_norm: gnorm,
})
}
pub fn minimize_bfgs<F, G>(
start: &Array1<f64>,
mut f: F,
mut grad: G,
maxiter: usize,
gtol: f64,
) -> Result<OptimizeResult>
where
F: FnMut(&Array1<f64>) -> f64,
G: FnMut(&Array1<f64>) -> Array1<f64>,
{
let n = start.len();
let mut x = start.clone();
let mut hinv = Array2::<f64>::eye(n); let mut g = grad(&x);
let mut fval = f(&x);
let mut converged = false;
let mut it = 0;
while it < maxiter {
let gnorm = g.dot(&g).sqrt();
if gnorm < gtol {
converged = true;
break;
}
let d = hinv.dot(&g).mapv(|v| -v);
let slope = g.dot(&d);
let mut alpha = 1.0;
let c = 1e-4;
let rho = 0.5;
let mut x_new = &x + &(alpha * &d);
let mut f_new = f(&x_new);
let mut ls = 0;
while f_new > fval + c * alpha * slope && ls < 50 {
alpha *= rho;
x_new = &x + &(alpha * &d);
f_new = f(&x_new);
ls += 1;
}
let g_new = grad(&x_new);
let s = &x_new - &x;
let yv = &g_new - &g;
let sy = s.dot(&yv);
if sy > 1e-12 {
let rho_bfgs = 1.0 / sy;
let i = Array2::<f64>::eye(n);
let sy_outer = outer(&s, &yv).mapv(|v| v * rho_bfgs);
let ys_outer = outer(&yv, &s).mapv(|v| v * rho_bfgs);
let left = &i - &sy_outer;
let right = &i - &ys_outer;
hinv = left.dot(&hinv).dot(&right) + outer(&s, &s).mapv(|v| v * rho_bfgs);
}
x = x_new;
g = g_new;
fval = f_new;
it += 1;
}
Ok(OptimizeResult {
x,
fval,
iters: it,
converged,
grad_norm: g.dot(&g).sqrt(),
})
}
fn outer(a: &Array1<f64>, b: &Array1<f64>) -> Array2<f64> {
let n = a.len();
let m = b.len();
let mut o = Array2::<f64>::zeros((n, m));
for i in 0..n {
for j in 0..m {
o[[i, j]] = a[i] * b[j];
}
}
o
}
#[cfg(test)]
mod tests {
use super::*;
use crate::numdiff::approx_fprime;
use approx::assert_abs_diff_eq;
use ndarray::array;
#[test]
fn newton_minimizes_quadratic() {
let fgh = |x: &Array1<f64>| {
let f = (x[0] - 3.0).powi(2) + 2.0 * (x[1] + 1.0).powi(2);
let g = array![2.0 * (x[0] - 3.0), 4.0 * (x[1] + 1.0)];
let h = array![[2.0, 0.0], [0.0, 4.0]];
(f, g, h)
};
let r = newton_stationary(&array![0.0, 0.0], fgh, 50, 1e-10).unwrap();
assert!(r.converged);
assert_abs_diff_eq!(r.x[0], 3.0, epsilon = 1e-8);
assert_abs_diff_eq!(r.x[1], -1.0, epsilon = 1e-8);
}
#[test]
fn bfgs_minimizes_rosenbrock() {
let f = |x: &Array1<f64>| (1.0 - x[0]).powi(2) + 100.0 * (x[1] - x[0] * x[0]).powi(2);
let g = |x: &Array1<f64>| approx_fprime(x, f);
let r = minimize_bfgs(&array![-1.2, 1.0], f, g, 1000, 1e-8).unwrap();
assert!(r.converged, "did not converge (grad_norm {})", r.grad_norm);
assert_abs_diff_eq!(r.x[0], 1.0, epsilon = 1e-4);
assert_abs_diff_eq!(r.x[1], 1.0, epsilon = 1e-4);
}
}