1#![forbid(unsafe_code)]
64#![warn(missing_docs, missing_debug_implementations)]
65
66pub mod autodiff_opt;
67pub mod least_squares;
68
69pub use autodiff_opt::minimize_lbfgs_autodiff;
70pub mod linear_program;
71
72pub use least_squares::{
73 curve_fit, levenberg_marquardt, LeastSquaresOptions, LeastSquaresSolution, LsTermination,
74};
75
76pub use tpt_math_linalg;
77pub use tpt_math_linalg::tpt_math_linalg_dense;
78
79use tpt_math_linalg_dense::{DMatrix, DVector};
80use tpt_math_numeric::{SolveReport, SolveStatus};
81
82pub const DEFAULT_MAX_ITERS: u64 = 100;
84
85pub const DEFAULT_GRADIENT_TOLERANCE: f64 = 1e-9;
87
88const RESTART_ITERS: u64 = 10;
90
91const RESTART_ORTHOGONALITY: f64 = 0.1;
93
94pub type TaggedVec<U> = tpt_math_linalg::Vec<U, f64>;
96
97#[derive(Clone, Copy, Debug, PartialEq)]
99pub struct Options {
100 pub max_iters: u64,
102 pub gradient_tolerance: f64,
107}
108
109impl Default for Options {
110 fn default() -> Self {
111 Options {
112 max_iters: DEFAULT_MAX_ITERS,
113 gradient_tolerance: DEFAULT_GRADIENT_TOLERANCE,
114 }
115 }
116}
117
118impl Options {
119 pub fn new(max_iters: u64) -> Self {
130 Options {
131 max_iters,
132 ..Options::default()
133 }
134 }
135
136 pub fn with_gradient_tolerance(mut self, tolerance: f64) -> Self {
145 self.gradient_tolerance = tolerance;
146 self
147 }
148}
149
150#[derive(Clone, Debug, PartialEq)]
152pub struct Solution {
153 pub param: DVector<f64>,
155 pub cost: f64,
157 pub iters: u64,
159 pub converged: bool,
163 pub termination: String,
165 pub residual: f64,
169}
170
171impl Solution {
172 #[must_use]
176 pub fn report(&self) -> SolveReport<f64> {
177 let status = if self.converged {
178 SolveStatus::Converged
179 } else if self.termination == "LineSearchStalled" {
180 SolveStatus::Breakdown
181 } else {
182 SolveStatus::NotConverged
183 };
184 SolveReport {
185 status,
186 iterations: self.iters as usize,
187 residual: self.residual,
188 }
189 }
190}
191
192pub fn point_from_tagged<U>(v: &TaggedVec<U>) -> DVector<f64> {
201 v.raw().clone()
202}
203
204pub fn point_to_tagged<U>(point: DVector<f64>) -> TaggedVec<U> {
213 TaggedVec::from_raw(point)
214}
215
216pub fn minimize_gradient_descent<F, G>(
240 cost: F,
241 grad: G,
242 init: DVector<f64>,
243 max_iters: u64,
244) -> Result<DVector<f64>, String>
245where
246 F: Fn(&DVector<f64>) -> f64,
247 G: Fn(&DVector<f64>) -> DVector<f64>,
248{
249 minimize_gradient_descent_with(cost, grad, init, &Options::new(max_iters)).map(|s| s.param)
250}
251
252pub fn minimize_gradient_descent_with<F, G>(
274 cost: F,
275 grad: G,
276 init: DVector<f64>,
277 options: &Options,
278) -> Result<Solution, String>
279where
280 F: Fn(&DVector<f64>) -> f64,
281 G: Fn(&DVector<f64>) -> DVector<f64>,
282{
283 let mut state = OptimizerState::new(cost, grad, no_hessian, init, options)?;
284 let mut iters = 0;
285 loop {
286 if state.grad_norm() <= options.gradient_tolerance {
287 return Ok(state.finish(iters, true, "GradientTolerance"));
288 }
289 if iters >= options.max_iters {
290 return Ok(state.finish(iters, false, "MaxIters"));
291 }
292 let dir = -state.grad().clone();
294 let alpha = line_search(state.cost_fn(), state.grad_fn(), &state.param, &dir);
295 if alpha == 0.0 {
296 return Ok(state.finish(iters, false, "LineSearchStalled"));
297 }
298 state.step(&(dir * alpha));
299 iters += 1;
300 }
301}
302
303pub fn minimize_conjugate_gradient<F, G>(
330 cost: F,
331 grad: G,
332 init: DVector<f64>,
333 max_iters: u64,
334) -> Result<DVector<f64>, String>
335where
336 F: Fn(&DVector<f64>) -> f64,
337 G: Fn(&DVector<f64>) -> DVector<f64>,
338{
339 minimize_conjugate_gradient_with(cost, grad, init, &Options::new(max_iters)).map(|s| s.param)
340}
341
342pub fn minimize_conjugate_gradient_with<F, G>(
364 cost: F,
365 grad: G,
366 init: DVector<f64>,
367 options: &Options,
368) -> Result<Solution, String>
369where
370 F: Fn(&DVector<f64>) -> f64,
371 G: Fn(&DVector<f64>) -> DVector<f64>,
372{
373 let mut state = OptimizerState::new(cost, grad, no_hessian, init, options)?;
374 let mut iters = 0;
375 let mut prev_grad: Option<DVector<f64>> = None;
376 let mut direction: Option<DVector<f64>> = None;
377 loop {
378 if state.grad_norm() <= options.gradient_tolerance {
379 return Ok(state.finish(iters, true, "GradientTolerance"));
380 }
381 if iters >= options.max_iters {
382 return Ok(state.finish(iters, false, "MaxIters"));
383 }
384
385 let dir = match (&prev_grad, &direction) {
386 (None, None) => -state.grad().clone(),
387 (Some(g_prev), Some(d_prev)) => {
388 let denom = g_prev.dot(g_prev);
389 let beta = if denom > 0.0 {
390 let num = state.grad().dot(&(state.grad().clone() - g_prev.clone()));
391 num / denom
392 } else {
393 0.0
394 };
395 let beta = beta.max(0.0);
396 let restart = (iters % RESTART_ITERS == 0)
397 || (denom > 0.0
398 && (state.grad().dot(g_prev)).abs() / denom >= RESTART_ORTHOGONALITY);
399 let cand = if restart {
401 -state.grad().clone()
402 } else {
403 -state.grad().clone() + d_prev.clone() * beta
404 };
405 if cand.dot(state.grad()) >= 0.0 {
406 -state.grad().clone()
407 } else {
408 cand
409 }
410 }
411 _ => unreachable!("prev_grad and direction are set together"),
412 };
413
414 let alpha = line_search(state.cost_fn(), state.grad_fn(), &state.param, &dir);
415 if alpha == 0.0 {
416 if prev_grad.is_none() {
419 return Ok(state.finish(iters, false, "LineSearchStalled"));
420 }
421 prev_grad = None;
422 direction = None;
423 iters += 1;
424 continue;
425 }
426 state.step(&(dir.clone() * alpha));
427 prev_grad = Some(state.grad().clone());
428 direction = Some(dir);
429 iters += 1;
430 }
431}
432
433pub fn minimize_newton<F, G, H>(
463 cost: F,
464 grad: G,
465 hessian: H,
466 init: DVector<f64>,
467 max_iters: u64,
468) -> Result<DVector<f64>, String>
469where
470 F: Fn(&DVector<f64>) -> f64,
471 G: Fn(&DVector<f64>) -> DVector<f64>,
472 H: Fn(&DVector<f64>) -> DMatrix<f64>,
473{
474 minimize_newton_with(cost, grad, hessian, init, &Options::new(max_iters)).map(|s| s.param)
475}
476
477pub fn minimize_newton_with<F, G, H>(
504 cost: F,
505 grad: G,
506 hessian: H,
507 init: DVector<f64>,
508 options: &Options,
509) -> Result<Solution, String>
510where
511 F: Fn(&DVector<f64>) -> f64,
512 G: Fn(&DVector<f64>) -> DVector<f64>,
513 H: Fn(&DVector<f64>) -> DMatrix<f64>,
514{
515 let mut state = OptimizerState::new(cost, grad, hessian, init, options)?;
516 let mut iters = 0;
517 loop {
518 if state.grad_norm() <= options.gradient_tolerance {
519 return Ok(state.finish(iters, true, "GradientTolerance"));
520 }
521 if iters >= options.max_iters {
522 return Ok(state.finish(iters, false, "MaxIters"));
523 }
524 let neg_grad = -state.grad().clone();
525 let step = state
526 .hessian()?
527 .solve(&neg_grad)
528 .map_err(|_| "singular Hessian (Newton step undefined)".to_string())?;
529 state.step(&step);
530 iters += 1;
531 }
532}
533
534fn no_hessian(_: &DVector<f64>) -> DMatrix<f64> {
536 DMatrix::zeros(0, 0)
537}
538
539fn validate(init: &DVector<f64>, options: &Options) -> Result<(), String> {
541 if init.is_empty() {
542 return Err("initial parameter vector must not be empty".to_string());
543 }
544 if init.iter().any(|x| !x.is_finite()) {
545 return Err("initial parameter vector must be finite".to_string());
546 }
547 if options.gradient_tolerance.is_nan() || options.gradient_tolerance < 0.0 {
548 return Err("gradient tolerance must be finite and non-negative".to_string());
549 }
550 Ok(())
551}
552
553struct OptimizerState<F, G, H> {
555 cost: F,
556 grad: G,
557 hessian: H,
558 param: DVector<f64>,
559 grad_cache: DVector<f64>,
560 cost_cache: f64,
561}
562
563impl<F, G, H> OptimizerState<F, G, H>
564where
565 F: Fn(&DVector<f64>) -> f64,
566 G: Fn(&DVector<f64>) -> DVector<f64>,
567 H: Fn(&DVector<f64>) -> DMatrix<f64>,
568{
569 fn new(
570 cost: F,
571 grad: G,
572 hessian: H,
573 init: DVector<f64>,
574 options: &Options,
575 ) -> Result<Self, String> {
576 validate(&init, options)?;
577 let grad_cache = grad(&init);
578 if !grad_cache.iter().all(|x| x.is_finite()) {
579 return Err("initial gradient is non-finite".to_string());
580 }
581 let cost_cache = cost(&init);
582 Ok(OptimizerState {
583 cost,
584 grad,
585 hessian,
586 param: init,
587 grad_cache,
588 cost_cache,
589 })
590 }
591
592 fn cost_fn(&self) -> &F {
593 &self.cost
594 }
595 fn grad_fn(&self) -> &G {
596 &self.grad
597 }
598 fn grad(&self) -> &DVector<f64> {
599 &self.grad_cache
600 }
601 fn grad_norm(&self) -> f64 {
602 self.grad_cache.norm()
603 }
604 fn hessian(&self) -> Result<DMatrix<f64>, String> {
605 Ok((self.hessian)(&self.param))
606 }
607
608 fn step(&mut self, step: &DVector<f64>) {
610 self.param = self.param.clone() + step.clone();
611 self.grad_cache = (self.grad)(&self.param);
612 self.cost_cache = (self.cost)(&self.param);
613 }
614
615 fn finish(self, iters: u64, converged: bool, termination: &'static str) -> Solution {
616 let residual = self.grad_norm();
617 Solution {
618 param: self.param,
619 cost: self.cost_cache,
620 iters,
621 converged,
622 termination: termination.to_string(),
623 residual,
624 }
625 }
626}
627
628fn line_search<F, G>(cost: &F, grad: &G, x: &DVector<f64>, d: &DVector<f64>) -> f64
637where
638 F: Fn(&DVector<f64>) -> f64,
639 G: Fn(&DVector<f64>) -> DVector<f64>,
640{
641 let phi0 = cost(x);
642 let alpha = line_search_bracket(cost, grad, x, d);
643 if alpha.is_finite() && alpha > 0.0 && cost(&(x.clone() + d.clone() * alpha)) < phi0 {
646 alpha
647 } else {
648 0.0
649 }
650}
651
652fn line_search_bracket<F, G>(cost: &F, grad: &G, x: &DVector<f64>, d: &DVector<f64>) -> f64
653where
654 F: Fn(&DVector<f64>) -> f64,
655 G: Fn(&DVector<f64>) -> DVector<f64>,
656{
657 let c1 = 1e-4;
658 let c2 = 0.1;
659 let dphi0 = grad(x).dot(d);
660 if dphi0 >= 0.0 {
661 return 0.0; }
663 let phi0 = cost(x);
664
665 let mut a_lo = 0.0;
666 let mut phi_lo = phi0;
667 let mut dphi_lo = dphi0;
668 let mut a = 1.0;
669
670 for _ in 0..40 {
671 let xa = x.clone() + d.clone() * a;
672 let phi_a = cost(&xa);
673 if phi_a > phi0 + c1 * a * dphi0 || (a_lo != 0.0 && phi_a >= phi_lo) {
676 return zoom(cost, grad, x, d, a_lo, a, phi_lo, dphi_lo, phi_a);
677 }
678 let dphi_a = grad(&xa).dot(d);
679 if dphi_a.abs() <= -c2 * dphi0 {
680 return a;
681 }
682 if dphi_a >= 0.0 {
683 return zoom(cost, grad, x, d, a, a_lo, phi_a, dphi_a, phi_lo);
684 }
685 a_lo = a;
686 phi_lo = phi_a;
687 dphi_lo = dphi_a;
688 a *= 2.0;
689 }
690 a
691}
692
693#[allow(clippy::too_many_arguments)]
697fn zoom<F, G>(
698 cost: &F,
699 grad: &G,
700 x: &DVector<f64>,
701 d: &DVector<f64>,
702 mut a_lo: f64,
703 mut a_hi: f64,
704 mut phi_lo: f64,
705 mut dphi_lo: f64,
706 mut phi_hi: f64,
707) -> f64
708where
709 F: Fn(&DVector<f64>) -> f64,
710 G: Fn(&DVector<f64>) -> DVector<f64>,
711{
712 let c1 = 1e-4;
713 let c2 = 0.1;
714 let dphi0 = grad(x).dot(d);
715
716 for _ in 0..40 {
717 let mut dphi_hi = grad(&(x.clone() + d.clone() * a_hi)).dot(d);
718 let mut a = cubic_min(a_lo, phi_lo, dphi_lo, a_hi, phi_hi, dphi_hi);
719 if !(a > a_lo.min(a_hi) && a < a_lo.max(a_hi)) {
722 a = 0.5 * (a_lo + a_hi);
723 }
724 let xa = x.clone() + d.clone() * a;
725 let phi_a = cost(&xa);
726 if phi_a > cost(x) + c1 * a * dphi0 || phi_a >= phi_lo {
727 a_hi = a;
728 phi_hi = phi_a;
729 } else {
730 let dphi_a = grad(&xa).dot(d);
731 if dphi_a * (a_hi - a_lo) >= 0.0 {
732 a_hi = a_lo;
733 phi_hi = phi_lo;
734 dphi_hi = dphi_lo;
735 }
736 a_lo = a;
737 phi_lo = phi_a;
738 dphi_lo = dphi_a;
739 if dphi_a.abs() <= -c2 * dphi0 {
740 return a;
741 }
742 }
743 if (a_hi - a_lo).abs() <= 1e-12 * (1.0 + a_hi.abs()) {
744 return a;
745 }
746 }
747 0.5 * (a_lo + a_hi)
748}
749
750fn cubic_min(al: f64, phi_al: f64, dphi_al: f64, ah: f64, phi_ah: f64, dphi_ah: f64) -> f64 {
753 let d1 = dphi_al + dphi_ah - 3.0 * (phi_al - phi_ah) / (al - ah);
754 let d2_sq = d1 * d1 - dphi_al * dphi_ah;
755 if d2_sq < 0.0 {
756 return 0.5 * (al + ah);
757 }
758 let d2 = (ah - al).signum() * d2_sq.sqrt();
759 let denom = dphi_ah - dphi_al + 2.0 * d2;
760 if denom.abs() < 1e-300 {
761 return 0.5 * (al + ah);
762 }
763 ah - (ah - al) * (dphi_ah + d2 - d1) / denom
764}
765
766pub fn minimize_lbfgs<F, G>(
787 cost: F,
788 grad: G,
789 init: DVector<f64>,
790 memory: usize,
791 max_iters: u64,
792) -> Result<DVector<f64>, String>
793where
794 F: Fn(&DVector<f64>) -> f64,
795 G: Fn(&DVector<f64>) -> DVector<f64>,
796{
797 minimize_lbfgs_with(cost, grad, init, memory, &Options::new(max_iters)).map(|s| s.param)
798}
799
800pub fn minimize_lbfgs_with<F, G>(
806 cost: F,
807 grad: G,
808 init: DVector<f64>,
809 memory: usize,
810 options: &Options,
811) -> Result<Solution, String>
812where
813 F: Fn(&DVector<f64>) -> f64,
814 G: Fn(&DVector<f64>) -> DVector<f64>,
815{
816 validate(&init, options)?;
817 if memory == 0 {
818 return Err("L-BFGS memory must be at least 1".into());
819 }
820 let mut x = init;
821 let mut g = grad(&x);
822 let mut pairs: Vec<(DVector<f64>, DVector<f64>, f64)> = Vec::with_capacity(memory);
824 let mut iters: u64 = 0;
825 loop {
826 if g.norm() <= options.gradient_tolerance {
827 return Ok(lbfgs_solution(
828 &cost,
829 x,
830 iters,
831 true,
832 "GradientTolerance",
833 g.norm(),
834 ));
835 }
836 if iters >= options.max_iters {
837 return Ok(lbfgs_solution(&cost, x, iters, false, "MaxIters", g.norm()));
838 }
839
840 let mut q = g.clone();
842 let mut alphas = vec![0.0_f64; pairs.len()];
843 for (idx, (s, y, rho)) in pairs.iter().enumerate().rev() {
844 let a = rho * s.dot(&q);
845 alphas[idx] = a;
846 q = q - y.clone() * a;
847 }
848 let gamma = match pairs.last() {
849 Some((s, y, _)) => s.dot(y) / y.dot(y),
850 None => 1.0,
851 };
852 let mut r = q * gamma;
853 for (idx, (s, y, rho)) in pairs.iter().enumerate() {
854 let beta = rho * y.dot(&r);
855 r = r + s.clone() * (alphas[idx] - beta);
856 }
857 let mut dir = -r;
858 if g.dot(&dir) >= 0.0 {
859 pairs.clear();
861 dir = -g.clone();
862 }
863
864 let mut alpha = line_search(&cost, &grad, &x, &dir);
865 if alpha == 0.0 {
866 if pairs.is_empty() {
867 return Ok(lbfgs_solution(
868 &cost,
869 x,
870 iters,
871 false,
872 "LineSearchStalled",
873 g.norm(),
874 ));
875 }
876 pairs.clear();
878 dir = -g.clone();
879 alpha = line_search(&cost, &grad, &x, &dir);
880 if alpha == 0.0 {
881 return Ok(lbfgs_solution(
882 &cost,
883 x,
884 iters,
885 false,
886 "LineSearchStalled",
887 g.norm(),
888 ));
889 }
890 }
891
892 let x_new = x.clone() + dir * alpha;
893 let g_new = grad(&x_new);
894 let s = x_new.clone() - x.clone();
895 let y = g_new.clone() - g.clone();
896 let sy = s.dot(&y);
897 if sy > 1e-12 * y.dot(&y).sqrt() * s.norm() {
899 if pairs.len() == memory {
900 pairs.remove(0);
901 }
902 pairs.push((s, y, 1.0 / sy));
903 }
904 x = x_new;
905 g = g_new;
906 iters += 1;
907 }
908}
909
910fn lbfgs_solution<F>(
911 cost: &F,
912 param: DVector<f64>,
913 iters: u64,
914 converged: bool,
915 termination: &str,
916 residual: f64,
917) -> Solution
918where
919 F: Fn(&DVector<f64>) -> f64,
920{
921 Solution {
922 cost: cost(¶m),
923 param,
924 iters,
925 converged,
926 termination: termination.to_string(),
927 residual,
928 }
929}
930
931pub fn numerical_gradient<F>(cost: &F, x: &DVector<f64>, h: f64) -> DVector<f64>
946where
947 F: Fn(&DVector<f64>) -> f64,
948{
949 let n = x.len();
950 let mut g = vec![0.0_f64; n];
951 let mut probe = x.clone();
952 for (i, gi) in g.iter_mut().enumerate() {
953 let xi = x[i];
954 let step = h * xi.abs().max(1.0);
958 probe.as_mut_slice()[i] = xi + step;
959 let fp = cost(&probe);
960 probe.as_mut_slice()[i] = xi - step;
961 let fm = cost(&probe);
962 probe.as_mut_slice()[i] = xi;
963 *gi = (fp - fm) / (2.0 * step);
964 }
965 DVector::from_vec(g)
966}
967
968#[cfg(test)]
969mod numerical_gradient_scale_tests {
970 use super::*;
971
972 #[test]
973 fn gradient_is_resolved_far_from_the_origin() {
974 let cost = |p: &DVector<f64>| p[0];
977 let g = numerical_gradient(&cost, &DVector::from_vec(vec![-3.0e10]), 1e-6);
978 assert!((g[0] - 1.0).abs() < 1e-6, "{}", g[0]);
979 }
980}
981
982pub fn minimize_nelder_mead_with<F>(
1005 cost: F,
1006 init: DVector<f64>,
1007 step: f64,
1008 options: &Options,
1009) -> Result<Solution, String>
1010where
1011 F: Fn(&DVector<f64>) -> f64,
1012{
1013 validate(&init, options)?;
1014 if !(step.is_finite() && step > 0.0) {
1015 return Err(format!("initial simplex step must be positive, got {step}"));
1016 }
1017 const ALPHA: f64 = 1.0; const GAMMA: f64 = 2.0; const RHO: f64 = 0.5; const SIGMA: f64 = 0.5; let n = init.len();
1023 let mut simplex: Vec<(DVector<f64>, f64)> = Vec::with_capacity(n + 1);
1024 let f0 = cost(&init);
1025 simplex.push((init.clone(), f0));
1026 for i in 0..n {
1027 let mut v = init.clone();
1028 v.as_mut_slice()[i] += step;
1029 let fv = cost(&v);
1030 simplex.push((v, fv));
1031 }
1032
1033 let tol = options.gradient_tolerance;
1034 let mut iters: u64 = 0;
1035 loop {
1036 simplex.sort_by(|a, b| a.1.total_cmp(&b.1));
1037 let best = simplex[0].1;
1038 let worst = simplex[n].1;
1039 let x_best = simplex[0].0.clone();
1042 let diameter = simplex
1043 .iter()
1044 .map(|(x, _)| (x.clone() - x_best.clone()).norm())
1045 .fold(0.0_f64, f64::max);
1046 let x_scale = 1.0 + x_best.norm();
1047 if (worst - best).abs() <= tol * (1.0 + best.abs()) && diameter <= tol * x_scale {
1048 return Ok(nelder_mead_solution(simplex, iters, true, "CostTolerance"));
1049 }
1050 if iters >= options.max_iters {
1051 return Ok(nelder_mead_solution(simplex, iters, false, "MaxIters"));
1052 }
1053 iters += 1;
1054
1055 let mut centroid = DVector::zeros(n);
1057 for (x, _) in &simplex[..n] {
1058 centroid = centroid + x.clone();
1059 }
1060 let centroid = centroid / (n as f64);
1061 let x_worst = simplex[n].0.clone();
1062 let f_second_worst = simplex[n - 1].1;
1063
1064 let along = |t: f64| centroid.clone() + (centroid.clone() - x_worst.clone()) * t;
1065 let x_r = along(ALPHA);
1066 let f_r = cost(&x_r);
1067 if f_r < best {
1068 let x_e = along(ALPHA * GAMMA);
1069 let f_e = cost(&x_e);
1070 simplex[n] = if f_e < f_r { (x_e, f_e) } else { (x_r, f_r) };
1071 } else if f_r < f_second_worst {
1072 simplex[n] = (x_r, f_r);
1073 } else {
1074 let (x_c, f_c) = if f_r < worst {
1077 let x_c = centroid.clone() + (x_r.clone() - centroid.clone()) * RHO;
1078 let f_c = cost(&x_c);
1079 (x_c, f_c)
1080 } else {
1081 let x_c = centroid.clone() + (x_worst.clone() - centroid.clone()) * RHO;
1082 let f_c = cost(&x_c);
1083 (x_c, f_c)
1084 };
1085 if f_c < f_r.min(worst) {
1086 simplex[n] = (x_c, f_c);
1087 } else {
1088 let x_best = simplex[0].0.clone();
1090 for vertex in simplex.iter_mut().skip(1) {
1091 let v = x_best.clone() + (vertex.0.clone() - x_best.clone()) * SIGMA;
1092 vertex.1 = cost(&v);
1093 vertex.0 = v;
1094 }
1095 }
1096 }
1097 }
1098}
1099
1100pub fn minimize_nelder_mead<F>(
1107 cost: F,
1108 init: DVector<f64>,
1109 step: f64,
1110 max_iters: u64,
1111) -> Result<DVector<f64>, String>
1112where
1113 F: Fn(&DVector<f64>) -> f64,
1114{
1115 minimize_nelder_mead_with(cost, init, step, &Options::new(max_iters)).map(|s| s.param)
1116}
1117
1118fn nelder_mead_solution(
1119 mut simplex: Vec<(DVector<f64>, f64)>,
1120 iters: u64,
1121 converged: bool,
1122 termination: &'static str,
1123) -> Solution {
1124 let best = simplex.iter().map(|v| v.1).fold(f64::INFINITY, f64::min);
1127 let worst = simplex
1128 .iter()
1129 .map(|v| v.1)
1130 .fold(f64::NEG_INFINITY, f64::max);
1131 simplex.sort_by(|a, b| a.1.total_cmp(&b.1));
1132 let (param, cost) = simplex.swap_remove(0);
1133 Solution {
1134 param,
1135 cost,
1136 iters,
1137 converged,
1138 termination: termination.to_string(),
1139 residual: worst - best,
1140 }
1141}
1142
1143#[cfg(test)]
1144mod tests {
1145 use super::*;
1146
1147 fn bowl_cost(p: &DVector<f64>) -> f64 {
1149 (p[0] - 3.0).powi(2) + (p[1] - 2.0).powi(2)
1150 }
1151
1152 fn bowl_grad(p: &DVector<f64>) -> DVector<f64> {
1153 DVector::from_vec(vec![2.0 * (p[0] - 3.0), 2.0 * (p[1] - 2.0)])
1154 }
1155
1156 fn bowl_hess(_: &DVector<f64>) -> DMatrix<f64> {
1157 DMatrix::from_diagonal(&DVector::from_vec(vec![2.0, 2.0]))
1158 }
1159
1160 fn valley_cost(p: &DVector<f64>) -> f64 {
1162 (p[0] - 3.0).powi(2) + 50.0 * (p[1] - 2.0).powi(2)
1163 }
1164
1165 fn valley_grad(p: &DVector<f64>) -> DVector<f64> {
1166 DVector::from_vec(vec![2.0 * (p[0] - 3.0), 100.0 * (p[1] - 2.0)])
1167 }
1168
1169 fn assert_close(actual: &DVector<f64>, expected: &[f64], tol: f64) {
1170 assert_eq!(actual.len(), expected.len());
1171 for (i, want) in expected.iter().enumerate() {
1172 assert!(
1173 (actual[i] - want).abs() < tol,
1174 "component {i}: {} is not within {tol} of {want}",
1175 actual[i]
1176 );
1177 }
1178 }
1179
1180 #[test]
1181 fn line_search_expansion_then_overshoot_stays_finite() {
1182 let cost = |p: &DVector<f64>| -p[0] + 0.1 * p[0].powi(8);
1186 let grad = |p: &DVector<f64>| DVector::from_vec(vec![-1.0 + 0.8 * p[0].powi(7)]);
1187 let x = DVector::from_vec(vec![0.0]);
1188 let d = DVector::from_vec(vec![1.0]);
1189 let a = line_search(&cost, &grad, &x, &d);
1190 assert!(a.is_finite() && a > 0.0, "step was {a}");
1191 assert!(cost(&(x.clone() + d.clone() * a)) < cost(&x));
1192 let dphi = grad(&(x + d * a))[0];
1193 assert!(dphi.abs() <= 0.1 * 1.0, "curvature violated: {dphi}");
1194 }
1195
1196 #[test]
1197 fn gradient_descent_stops_when_line_search_stalls() {
1198 let s = minimize_gradient_descent_with(
1202 |p: &DVector<f64>| p[0],
1203 |_: &DVector<f64>| DVector::from_vec(vec![-1.0]),
1204 DVector::from_vec(vec![1.0]),
1205 &Options::new(1_000_000),
1206 )
1207 .unwrap();
1208 assert!(!s.converged);
1209 assert!(s.iters < 1_000_000);
1210 assert_eq!(s.termination, "LineSearchStalled");
1211 }
1212
1213 #[test]
1214 fn gradient_descent_minimizes_scalar_square() {
1215 let best = minimize_gradient_descent(
1217 |p: &DVector<f64>| p[0] * p[0],
1218 |p: &DVector<f64>| DVector::from_vec(vec![2.0 * p[0]]),
1219 DVector::from_vec(vec![7.5]),
1220 50,
1221 )
1222 .unwrap();
1223
1224 assert_close(&best, &[0.0], 1e-8);
1225 }
1226
1227 #[test]
1228 fn gradient_descent_minimizes_bowl() {
1229 let best = minimize_gradient_descent(bowl_cost, bowl_grad, DVector::zeros(2), 100).unwrap();
1230
1231 assert_close(&best, &[3.0, 2.0], 1e-6);
1232 assert!(bowl_cost(&best) < 1e-12);
1233 }
1234
1235 #[test]
1236 fn gradient_descent_reports_convergence_and_cost() {
1237 let solution = minimize_gradient_descent_with(
1238 bowl_cost,
1239 bowl_grad,
1240 DVector::from_vec(vec![-4.0, 9.0]),
1241 &Options::new(200),
1242 )
1243 .unwrap();
1244
1245 assert!(solution.converged, "termination: {}", solution.termination);
1246 assert!(solution.iters <= 200);
1247 assert!(!solution.termination.is_empty());
1248 assert!(solution.cost < 1e-12, "cost was {}", solution.cost);
1249 assert!((solution.cost - bowl_cost(&solution.param)).abs() < 1e-15);
1250 }
1251
1252 #[test]
1253 fn gradient_descent_survives_starting_at_the_optimum() {
1254 let solution = minimize_gradient_descent_with(
1256 bowl_cost,
1257 bowl_grad,
1258 DVector::from_vec(vec![3.0, 2.0]),
1259 &Options::new(25),
1260 )
1261 .unwrap();
1262
1263 assert!(solution.converged);
1264 assert!(solution.iters <= 1);
1265 assert_close(&solution.param, &[3.0, 2.0], 1e-15);
1266 }
1267
1268 #[test]
1269 fn conjugate_gradient_handles_ill_conditioned_valley() {
1270 let solution = minimize_conjugate_gradient_with(
1271 valley_cost,
1272 valley_grad,
1273 DVector::zeros(2),
1274 &Options::new(200),
1275 )
1276 .unwrap();
1277
1278 assert_close(&solution.param, &[3.0, 2.0], 1e-5);
1279 assert!(solution.cost < 1e-9, "cost was {}", solution.cost);
1280 }
1281
1282 #[test]
1283 fn conjugate_gradient_minimizes_rosenbrock() {
1284 let cost = |p: &DVector<f64>| (1.0 - p[0]).powi(2) + 100.0 * (p[1] - p[0] * p[0]).powi(2);
1286 let grad = |p: &DVector<f64>| {
1287 DVector::from_vec(vec![
1288 -2.0 * (1.0 - p[0]) - 400.0 * p[0] * (p[1] - p[0] * p[0]),
1289 200.0 * (p[1] - p[0] * p[0]),
1290 ])
1291 };
1292
1293 let best =
1296 minimize_conjugate_gradient(cost, grad, DVector::from_vec(vec![-1.2, 1.0]), 5000)
1297 .unwrap();
1298
1299 assert_close(&best, &[1.0, 1.0], 1e-3);
1300 }
1301
1302 #[test]
1303 fn newton_solves_quadratic_in_one_step() {
1304 let solution = minimize_newton_with(
1305 bowl_cost,
1306 bowl_grad,
1307 bowl_hess,
1308 DVector::from_vec(vec![-10.0, 40.0]),
1309 &Options::new(25),
1310 )
1311 .unwrap();
1312
1313 assert_close(&solution.param, &[3.0, 2.0], 1e-12);
1314 assert!(solution.converged);
1315 assert!(solution.iters <= 2, "took {} iterations", solution.iters);
1316 assert!(solution.cost < 1e-24);
1317 }
1318
1319 #[test]
1320 fn newton_minimizes_non_quadratic() {
1321 let best = minimize_newton(
1323 |p: &DVector<f64>| p[0].exp() - p[0],
1324 |p: &DVector<f64>| DVector::from_vec(vec![p[0].exp() - 1.0]),
1325 |p: &DVector<f64>| DMatrix::from_vec(1, 1, vec![p[0].exp()]),
1326 DVector::from_vec(vec![1.5]),
1327 50,
1328 )
1329 .unwrap();
1330
1331 assert_close(&best, &[0.0], 1e-7);
1332 }
1333
1334 #[test]
1335 fn solvers_agree_on_the_same_problem() {
1336 let init = DVector::from_vec(vec![-2.0, 6.5]);
1337 let gd = minimize_gradient_descent(bowl_cost, bowl_grad, init.clone(), 100).unwrap();
1338 let cg = minimize_conjugate_gradient(bowl_cost, bowl_grad, init.clone(), 100).unwrap();
1339 let newton = minimize_newton(bowl_cost, bowl_grad, bowl_hess, init, 100).unwrap();
1340
1341 assert_close(&gd, &[3.0, 2.0], 1e-6);
1342 assert_close(&cg, &[3.0, 2.0], 1e-6);
1343 assert_close(&newton, &[3.0, 2.0], 1e-12);
1344 }
1345
1346 #[test]
1347 fn max_iters_caps_the_run() {
1348 let solution = minimize_gradient_descent_with(
1350 valley_cost,
1351 valley_grad,
1352 DVector::from_vec(vec![-50.0, -50.0]),
1353 &Options::new(1),
1354 )
1355 .unwrap();
1356
1357 assert_eq!(solution.iters, 1);
1358 assert!(!solution.converged);
1359 assert!(solution.cost > 0.0);
1360 }
1361
1362 #[test]
1363 fn zero_iterations_returns_the_initial_point() {
1364 let init = DVector::from_vec(vec![1.0, -1.0]);
1365 let solution =
1366 minimize_gradient_descent_with(bowl_cost, bowl_grad, init.clone(), &Options::new(0))
1367 .unwrap();
1368
1369 assert_eq!(solution.param, init);
1370 assert_eq!(solution.iters, 0);
1371 assert!((solution.cost - bowl_cost(&init)).abs() < 1e-15);
1372 }
1373
1374 #[test]
1375 fn empty_initial_point_is_rejected() {
1376 let err =
1377 minimize_gradient_descent(bowl_cost, bowl_grad, DVector::zeros(0), 10).unwrap_err();
1378 assert!(err.contains("empty"), "unexpected message: {err}");
1379 }
1380
1381 #[test]
1382 fn non_finite_initial_point_is_rejected() {
1383 let err = minimize_gradient_descent(
1384 bowl_cost,
1385 bowl_grad,
1386 DVector::from_vec(vec![f64::NAN, 0.0]),
1387 10,
1388 )
1389 .unwrap_err();
1390 assert!(err.contains("finite"), "unexpected message: {err}");
1391 }
1392
1393 #[test]
1394 fn negative_gradient_tolerance_is_rejected() {
1395 let options = Options::new(10).with_gradient_tolerance(-1.0);
1396 let err = minimize_gradient_descent_with(bowl_cost, bowl_grad, DVector::zeros(2), &options)
1397 .unwrap_err();
1398 assert!(err.contains("tolerance"), "unexpected message: {err}");
1399 }
1400
1401 #[test]
1402 fn singular_hessian_is_reported_as_an_error() {
1403 let err = minimize_newton(
1404 bowl_cost,
1405 bowl_grad,
1406 |_: &DVector<f64>| DMatrix::zeros(2, 2),
1407 DVector::zeros(2),
1408 10,
1409 )
1410 .unwrap_err();
1411
1412 assert!(!err.is_empty());
1413 }
1414
1415 #[test]
1416 fn tagged_vectors_round_trip() {
1417 let tagged: TaggedVec<()> = point_to_tagged(DVector::from_vec(vec![3.0, 4.0]));
1418 let raw = point_from_tagged(&tagged);
1419
1420 let best = minimize_gradient_descent(bowl_cost, bowl_grad, raw, 100).unwrap();
1421 let back: TaggedVec<()> = point_to_tagged(best);
1422
1423 assert_close(back.raw(), &[3.0, 2.0], 1e-6);
1424 }
1425
1426 #[test]
1427 fn options_defaults_are_sane() {
1428 let options = Options::default();
1429 assert_eq!(options.max_iters, DEFAULT_MAX_ITERS);
1430 assert_eq!(options.gradient_tolerance, DEFAULT_GRADIENT_TOLERANCE);
1431 assert_eq!(Options::new(DEFAULT_MAX_ITERS), options);
1432 }
1433
1434 #[test]
1435 fn numerical_gradient_matches_analytic() {
1436 let cost = |p: &DVector<f64>| p[0] * p[0] * p[1];
1437 let g = numerical_gradient(&cost, &DVector::from_vec(vec![3.0, 2.0]), 1e-6);
1438 assert_close(&g, &[12.0, 9.0], 1e-6);
1439 }
1440
1441 #[test]
1442 fn nelder_mead_minimizes_bowl_without_gradients() {
1443 let s = minimize_nelder_mead_with(bowl_cost, DVector::zeros(2), 1.0, &Options::new(1000))
1444 .unwrap();
1445 assert!(s.converged, "termination: {}", s.termination);
1446 assert_close(&s.param, &[3.0, 2.0], 1e-6);
1447 }
1448
1449 #[test]
1450 fn nelder_mead_minimizes_rosenbrock() {
1451 let rosen = |p: &DVector<f64>| (1.0 - p[0]).powi(2) + 100.0 * (p[1] - p[0] * p[0]).powi(2);
1452 let x = minimize_nelder_mead(rosen, DVector::from_vec(vec![-1.2, 1.0]), 0.5, 5000).unwrap();
1453 assert_close(&x, &[1.0, 1.0], 1e-3);
1454 }
1455
1456 #[test]
1457 fn nelder_mead_rejects_bad_step() {
1458 assert!(minimize_nelder_mead(bowl_cost, DVector::zeros(2), 0.0, 10).is_err());
1459 }
1460
1461 #[test]
1462 fn lbfgs_minimizes_rosenbrock() {
1463 let rosen = |p: &DVector<f64>| (1.0 - p[0]).powi(2) + 100.0 * (p[1] - p[0] * p[0]).powi(2);
1464 let rosen_grad = |p: &DVector<f64>| {
1465 DVector::from_vec(vec![
1466 -2.0 * (1.0 - p[0]) - 400.0 * p[0] * (p[1] - p[0] * p[0]),
1467 200.0 * (p[1] - p[0] * p[0]),
1468 ])
1469 };
1470 let s = minimize_lbfgs_with(
1471 rosen,
1472 rosen_grad,
1473 DVector::from_vec(vec![-1.2, 1.0]),
1474 8,
1475 &Options::new(500),
1476 )
1477 .unwrap();
1478 assert!(s.converged, "termination: {}", s.termination);
1479 assert_close(&s.param, &[1.0, 1.0], 1e-5);
1480 }
1481
1482 #[test]
1483 fn lbfgs_handles_ill_conditioned_valley() {
1484 let best = minimize_lbfgs(valley_cost, valley_grad, DVector::zeros(2), 5, 200).unwrap();
1485 assert_close(&best, &[3.0, 2.0], 1e-6);
1486 }
1487
1488 #[test]
1489 fn lbfgs_rejects_zero_memory() {
1490 assert!(minimize_lbfgs(bowl_cost, bowl_grad, DVector::zeros(2), 0, 10).is_err());
1491 }
1492}
1493
1494#[cfg(test)]
1495mod report_tests {
1496 use super::*;
1497 use tpt_math_numeric::SolveStatus;
1498
1499 fn quadratic_cost(x: &DVector<f64>) -> f64 {
1500 (x[0] - 1.0).powi(2) + 2.0 * (x[1] + 2.0).powi(2)
1501 }
1502
1503 fn quadratic_grad(x: &DVector<f64>) -> DVector<f64> {
1504 DVector::from_vec(vec![2.0 * (x[0] - 1.0), 4.0 * (x[1] + 2.0)])
1505 }
1506
1507 #[test]
1508 fn converged_run_reports_converged_with_small_residual() {
1509 let (f, g) = (quadratic_cost, quadratic_grad);
1510 let opts = Options::new(500);
1511 let sol = minimize_lbfgs_with(f, g, DVector::from_vec(vec![5.0, 5.0]), 5, &opts).unwrap();
1512 let report = sol.report();
1513 assert_eq!(report.status, SolveStatus::Converged);
1514 assert!(report.residual <= opts.gradient_tolerance);
1515 assert_eq!(report.iterations, sol.iters as usize);
1516 }
1517
1518 #[test]
1519 fn exhausted_budget_reports_not_converged() {
1520 let (f, g) = (quadratic_cost, quadratic_grad);
1521 let sol = minimize_gradient_descent_with(
1522 f,
1523 g,
1524 DVector::from_vec(vec![5.0, 5.0]),
1525 &Options::new(1),
1526 )
1527 .unwrap();
1528 assert_eq!(sol.report().status, SolveStatus::NotConverged);
1529 assert!(sol.report().residual > 0.0);
1530 }
1531
1532 #[test]
1533 fn nelder_mead_residual_is_cost_spread() {
1534 let f = |x: &DVector<f64>| (x[0] - 3.0).powi(2);
1535 let sol =
1536 minimize_nelder_mead_with(f, DVector::from_vec(vec![0.0]), 1.0, &Options::new(400))
1537 .unwrap();
1538 assert!(sol.residual >= 0.0);
1539 assert!(sol.residual < 1e-6, "{}", sol.residual);
1540 }
1541}