Skip to main content

ctrl_freeq/optim/
newton_cg.rs

1//! Truncated Newton: Newton steps from conjugate gradients on Hessian-vector products.
2//!
3//! This is the line-search Newton-CG of Nocedal and Wright (Algorithm 7.1), as torchmin and scipy implement it: the
4//! Newton system `H·p = −g` is solved by conjugate gradients only as accurately as the forcing term
5//! `min(0.5, √‖g‖)·‖g‖` asks, stopping early on negative curvature, and each step is found by backtracking until
6//! the Armijo condition holds.  It needs only Hessian-vector products, which the objective computes exactly, so a
7//! step costs a few gradient evaluations rather than a whole Hessian.
8
9use super::{Derivatives, Eval, Exit, Monitor, Objective, OptimResult, Optimizer, RunControl};
10use crate::error::{Error, Result};
11
12/// Sufficient-decrease constant of the Armijo condition.
13const ARMIJO: f64 = 1e-4;
14/// Gradient norm at which a run has converged.
15const TOL_GRAD: f64 = 1e-12;
16/// Smallest step fraction tried before the line search gives up.
17const MIN_STEP: f64 = 1e-12;
18
19fn dot(a: &[f64], b: &[f64]) -> f64 {
20    a.iter().zip(b).map(|(x, y)| x * y).sum()
21}
22
23fn norm(a: &[f64]) -> f64 {
24    dot(a, a).sqrt()
25}
26
27/// Line-search Newton-CG with exact Hessian-vector products.
28#[derive(Clone, Copy, Debug, Default)]
29pub struct NewtonCg;
30
31impl Optimizer for NewtonCg {
32    fn name(&self) -> &'static str {
33        "newton-cg"
34    }
35
36    fn derivatives(&self) -> Derivatives {
37        Derivatives::Hessian
38    }
39
40    fn minimize(&self, obj: &dyn Objective, x0: &[f64], ctl: &mut RunControl) -> Result<OptimResult> {
41        let mut monitor = Monitor::new(ctl);
42        let mut iterations = 0;
43        let outcome = iterate(obj, x0, &mut monitor, &mut iterations);
44        match outcome {
45            Ok(exit) => monitor.finish(iterations, exit),
46            Err(e) if monitor.best.is_some() => monitor.finish(iterations, Exit::Failed(e.to_string())),
47            Err(e) => Err(e),
48        }
49    }
50}
51
52/// The iterations; returns the exit to use when no stop condition fired first.
53fn iterate(obj: &dyn Objective, x0: &[f64], monitor: &mut Monitor, iterations: &mut usize) -> Result<Exit> {
54    let n = x0.len();
55    let mut x = x0.to_vec();
56    let (mut e, mut g) = obj.gradient(&x)?;
57    monitor.evaluated(&x, e);
58    monitor.report(0, e, Some(norm(&g)));
59    while monitor.exit.is_none() {
60        let gnorm = norm(&g);
61        if gnorm < TOL_GRAD {
62            return Ok(Exit::Converged);
63        }
64        let mut p = newton_direction(obj, &x, &g, n)?;
65        let mut slope = dot(&g, &p);
66        if slope.is_nan() || slope >= 0.0 {
67            p = g.iter().map(|v| -v).collect();
68            slope = -gnorm * gnorm;
69        }
70        let Some((xn, en)) = backtrack(obj, &x, &p, &e, slope, monitor)? else {
71            return Ok(Exit::Converged);
72        };
73        let (en2, gn) = obj.gradient(&xn)?;
74        debug_assert_eq!(en.cost, en2.cost);
75        x = xn;
76        e = en2;
77        g = gn;
78        *iterations += 1;
79        monitor.report(*iterations, e, Some(norm(&g)));
80    }
81    Ok(Exit::Converged)
82}
83
84/// Approximately solve `H·p = −g` by conjugate gradients, truncated by the forcing term and at negative curvature.
85fn newton_direction(obj: &dyn Objective, x: &[f64], g: &[f64], n: usize) -> Result<Vec<f64>> {
86    let gnorm = norm(g);
87    let tol = 0.5f64.min(gnorm.sqrt()) * gnorm;
88    let mut z = vec![0.0; n];
89    let mut r = g.to_vec();
90    let mut d: Vec<f64> = g.iter().map(|v| -v).collect();
91    let mut rr = dot(&r, &r);
92    for j in 0..(2 * n).max(20) {
93        let hd = obj.hvp(x, &d)?;
94        if hd.len() != n || hd.iter().any(|v| !v.is_finite()) {
95            return Err(Error::Numerical("the Hessian-vector product is not finite".into()));
96        }
97        let curvature = dot(&d, &hd);
98        if curvature <= 0.0 {
99            return Ok(if j == 0 { d } else { z });
100        }
101        let alpha = rr / curvature;
102        for i in 0..n {
103            z[i] += alpha * d[i];
104            r[i] += alpha * hd[i];
105        }
106        let rr_new = dot(&r, &r);
107        if rr_new.sqrt() < tol {
108            return Ok(z);
109        }
110        let beta = rr_new / rr;
111        for i in 0..n {
112            d[i] = -r[i] + beta * d[i];
113        }
114        rr = rr_new;
115    }
116    Ok(z)
117}
118
119/// Halve the step from 1 until the Armijo condition holds.  `None` if no step decreases the cost.
120fn backtrack(
121    obj: &dyn Objective,
122    x: &[f64],
123    p: &[f64],
124    e: &Eval,
125    slope: f64,
126    monitor: &mut Monitor,
127) -> Result<Option<(Vec<f64>, Eval)>> {
128    let mut step = 1.0;
129    while step >= MIN_STEP {
130        let xn: Vec<f64> = x.iter().zip(p).map(|(a, b)| a + step * b).collect();
131        match obj.value(&xn) {
132            Ok(en) => {
133                monitor.evaluated(&xn, en);
134                if en.cost <= e.cost + ARMIJO * step * slope {
135                    return Ok(Some((xn, en)));
136                }
137            }
138            // A step into a region where the objective fails is treated as too long.
139            Err(Error::Numerical(_)) => {}
140            Err(other) => return Err(other),
141        }
142        step *= 0.5;
143    }
144    Ok(None)
145}