use super::{Derivatives, Eval, Exit, Monitor, Objective, OptimResult, Optimizer, RunControl};
use crate::error::{Error, Result};
const ARMIJO: f64 = 1e-4;
const TOL_GRAD: f64 = 1e-12;
const MIN_STEP: f64 = 1e-12;
fn dot(a: &[f64], b: &[f64]) -> f64 {
a.iter().zip(b).map(|(x, y)| x * y).sum()
}
fn norm(a: &[f64]) -> f64 {
dot(a, a).sqrt()
}
#[derive(Clone, Copy, Debug, Default)]
pub struct NewtonCg;
impl Optimizer for NewtonCg {
fn name(&self) -> &'static str {
"newton-cg"
}
fn derivatives(&self) -> Derivatives {
Derivatives::Hessian
}
fn minimize(&self, obj: &dyn Objective, x0: &[f64], ctl: &mut RunControl) -> Result<OptimResult> {
let mut monitor = Monitor::new(ctl);
let mut iterations = 0;
let outcome = iterate(obj, x0, &mut monitor, &mut iterations);
match outcome {
Ok(exit) => monitor.finish(iterations, exit),
Err(e) if monitor.best.is_some() => monitor.finish(iterations, Exit::Failed(e.to_string())),
Err(e) => Err(e),
}
}
}
fn iterate(obj: &dyn Objective, x0: &[f64], monitor: &mut Monitor, iterations: &mut usize) -> Result<Exit> {
let n = x0.len();
let mut x = x0.to_vec();
let (mut e, mut g) = obj.gradient(&x)?;
monitor.evaluated(&x, e);
monitor.report(0, e, Some(norm(&g)));
while monitor.exit.is_none() {
let gnorm = norm(&g);
if gnorm < TOL_GRAD {
return Ok(Exit::Converged);
}
let mut p = newton_direction(obj, &x, &g, n)?;
let mut slope = dot(&g, &p);
if slope.is_nan() || slope >= 0.0 {
p = g.iter().map(|v| -v).collect();
slope = -gnorm * gnorm;
}
let Some((xn, en)) = backtrack(obj, &x, &p, &e, slope, monitor)? else {
return Ok(Exit::Converged);
};
let (en2, gn) = obj.gradient(&xn)?;
debug_assert_eq!(en.cost, en2.cost);
x = xn;
e = en2;
g = gn;
*iterations += 1;
monitor.report(*iterations, e, Some(norm(&g)));
}
Ok(Exit::Converged)
}
fn newton_direction(obj: &dyn Objective, x: &[f64], g: &[f64], n: usize) -> Result<Vec<f64>> {
let gnorm = norm(g);
let tol = 0.5f64.min(gnorm.sqrt()) * gnorm;
let mut z = vec![0.0; n];
let mut r = g.to_vec();
let mut d: Vec<f64> = g.iter().map(|v| -v).collect();
let mut rr = dot(&r, &r);
for j in 0..(2 * n).max(20) {
let hd = obj.hvp(x, &d)?;
if hd.len() != n || hd.iter().any(|v| !v.is_finite()) {
return Err(Error::Numerical("the Hessian-vector product is not finite".into()));
}
let curvature = dot(&d, &hd);
if curvature <= 0.0 {
return Ok(if j == 0 { d } else { z });
}
let alpha = rr / curvature;
for i in 0..n {
z[i] += alpha * d[i];
r[i] += alpha * hd[i];
}
let rr_new = dot(&r, &r);
if rr_new.sqrt() < tol {
return Ok(z);
}
let beta = rr_new / rr;
for i in 0..n {
d[i] = -r[i] + beta * d[i];
}
rr = rr_new;
}
Ok(z)
}
fn backtrack(
obj: &dyn Objective,
x: &[f64],
p: &[f64],
e: &Eval,
slope: f64,
monitor: &mut Monitor,
) -> Result<Option<(Vec<f64>, Eval)>> {
let mut step = 1.0;
while step >= MIN_STEP {
let xn: Vec<f64> = x.iter().zip(p).map(|(a, b)| a + step * b).collect();
match obj.value(&xn) {
Ok(en) => {
monitor.evaluated(&xn, en);
if en.cost <= e.cost + ARMIJO * step * slope {
return Ok(Some((xn, en)));
}
}
Err(Error::Numerical(_)) => {}
Err(other) => return Err(other),
}
step *= 0.5;
}
Ok(None)
}