solow_optimize/
optimizer.rs1use ndarray::{Array1, Array2};
8use solow_core::error::Result;
9use solow_linalg::{lstsq, solve};
10
11#[derive(Clone, Debug)]
13pub struct OptimizeResult {
14 pub x: Array1<f64>,
16 pub fval: f64,
18 pub iters: usize,
20 pub converged: bool,
22 pub grad_norm: f64,
24}
25
26pub 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 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 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
104pub 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); 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 let d = hinv.dot(&g).mapv(|v| -v);
132 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 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 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 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 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}