ctrl_freeq/optim/
newton_cg.rs1use super::{Derivatives, Eval, Exit, Monitor, Objective, OptimResult, Optimizer, RunControl};
10use crate::error::{Error, Result};
11
12const ARMIJO: f64 = 1e-4;
14const TOL_GRAD: f64 = 1e-12;
16const 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#[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
52fn 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
84fn 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
119fn 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 Err(Error::Numerical(_)) => {}
140 Err(other) => return Err(other),
141 }
142 step *= 0.5;
143 }
144 Ok(None)
145}