Skip to main content

ctrl_freeq/optim/
gradient.rs

1//! L-BFGS and the trust-region Newton method, from [argmin](https://argmin-rs.org).
2//!
3//! argmin runs a solver one iteration at a time and asks it whether to stop, so a thin [`Monitored`] wrapper around
4//! any argmin solver gives it progress reports, the target check and cancellation - the pattern Rusty-QOALA uses.
5//! [`Adapter`] presents an [`Objective`] to argmin and records every evaluation, so the best point ever evaluated,
6//! line-search trials included, is what a run returns.
7
8use std::cell::RefCell;
9
10use argmin::core::{
11    CostFunction, Error as ArgminError, Executor, Gradient, Hessian, IterState, KV, Problem, Solver, State,
12    TerminationReason, TerminationStatus,
13};
14use argmin::solver::linesearch::MoreThuenteLineSearch;
15use argmin::solver::quasinewton::LBFGS;
16use argmin::solver::trustregion::{Steihaug, TrustRegion};
17use nalgebra::{DMatrix, DVector};
18
19use super::{Derivatives, Eval, Exit, Monitor, Objective, OptimResult, Optimizer, RunControl};
20use crate::error::{Error, Result};
21
22/// L-BFGS history length.
23const LBFGS_MEMORY: usize = 10;
24
25type Iterate<H> = IterState<DVector<f64>, DVector<f64>, (), H, (), f64>;
26type LineSearch = MoreThuenteLineSearch<DVector<f64>, DVector<f64>, f64>;
27
28/// An [`Objective`] as an argmin problem.
29struct Adapter<'a, 's> {
30    obj: &'a dyn Objective,
31    monitor: &'a RefCell<Monitor<'s>>,
32}
33
34fn argmin_error(e: Error) -> ArgminError {
35    ArgminError::msg(e.to_string())
36}
37
38impl Adapter<'_, '_> {
39    fn record(&self, x: &DVector<f64>, e: Eval) {
40        self.monitor.borrow_mut().evaluated(x.as_slice(), e);
41    }
42}
43
44impl CostFunction for Adapter<'_, '_> {
45    type Param = DVector<f64>;
46    type Output = f64;
47
48    fn cost(&self, x: &Self::Param) -> std::result::Result<f64, ArgminError> {
49        let e = self.obj.value(x.as_slice()).map_err(argmin_error)?;
50        self.record(x, e);
51        Ok(e.cost)
52    }
53}
54
55impl Gradient for Adapter<'_, '_> {
56    type Param = DVector<f64>;
57    type Gradient = DVector<f64>;
58
59    fn gradient(&self, x: &Self::Param) -> std::result::Result<DVector<f64>, ArgminError> {
60        let (e, g) = self.obj.gradient(x.as_slice()).map_err(argmin_error)?;
61        self.record(x, e);
62        Ok(DVector::from_vec(g))
63    }
64}
65
66impl Hessian for Adapter<'_, '_> {
67    type Param = DVector<f64>;
68    type Hessian = DMatrix<f64>;
69
70    fn hessian(&self, x: &Self::Param) -> std::result::Result<DMatrix<f64>, ArgminError> {
71        let (e, _, h) = self.obj.hessian(x.as_slice()).map_err(argmin_error)?;
72        self.record(x, e);
73        Ok(h)
74    }
75}
76
77/// Any argmin solver with reporting and the shared stop checks around it.
78struct Monitored<'a, 's, S> {
79    inner: S,
80    monitor: &'a RefCell<Monitor<'s>>,
81    iteration: usize,
82    failure: Option<String>,
83}
84
85impl<'a, 's, S> Monitored<'a, 's, S> {
86    /// Report the state's current point as iteration `self.iteration`.
87    fn report<H>(
88        &mut self,
89        problem: &Problem<Adapter<'a, 's>>,
90        state: &Iterate<H>,
91    ) -> std::result::Result<(), ArgminError> {
92        let (Some(adapter), Some(x)) = (problem.problem.as_ref(), state.get_param()) else {
93            return Ok(());
94        };
95        // Usually the point just evaluated, so a cache hit in the objective.
96        let e = adapter.obj.value(x.as_slice()).map_err(argmin_error)?;
97        let grad_norm = state.get_gradient().map(|g| g.norm());
98        self.monitor.borrow_mut().report(self.iteration, e, grad_norm);
99        Ok(())
100    }
101}
102
103impl<'a, 's, S, H> Solver<Adapter<'a, 's>, Iterate<H>> for Monitored<'a, 's, S>
104where
105    S: Solver<Adapter<'a, 's>, Iterate<H>>,
106    H: Clone,
107{
108    fn name(&self) -> &str {
109        self.inner.name()
110    }
111
112    fn init(
113        &mut self,
114        problem: &mut Problem<Adapter<'a, 's>>,
115        state: Iterate<H>,
116    ) -> std::result::Result<(Iterate<H>, Option<KV>), ArgminError> {
117        let (state, kv) = self.inner.init(problem, state)?;
118        self.report(problem, &state)?;
119        Ok((state, kv))
120    }
121
122    fn next_iter(
123        &mut self,
124        problem: &mut Problem<Adapter<'a, 's>>,
125        state: Iterate<H>,
126    ) -> std::result::Result<(Iterate<H>, Option<KV>), ArgminError> {
127        // A solver that fails mid-iteration consumes the state; keep a copy so the run ends on the last good point.
128        let fallback = state.clone();
129        match self.inner.next_iter(problem, state) {
130            Ok((state, kv)) => {
131                self.iteration += 1;
132                self.report(problem, &state)?;
133                Ok((state, kv))
134            }
135            Err(e) => {
136                let message = e.to_string();
137                self.failure = Some(message.clone());
138                Ok((fallback.terminate_with(TerminationReason::SolverExit(message)), None))
139            }
140        }
141    }
142
143    fn terminate(&mut self, state: &Iterate<H>) -> TerminationStatus {
144        if self.monitor.borrow().exit.is_some() {
145            return TerminationStatus::Terminated(TerminationReason::SolverExit("monitor".into()));
146        }
147        self.inner.terminate(state)
148    }
149}
150
151/// Run `solver` on `obj` from `x0` with the shared monitoring.
152fn run<S, H>(solver: S, obj: &dyn Objective, x0: &[f64], ctl: &mut RunControl) -> Result<OptimResult>
153where
154    for<'a, 's> S: Solver<Adapter<'a, 's>, Iterate<H>>,
155    H: Clone,
156{
157    let max_iters = ctl.max_iter as u64;
158    let monitor = RefCell::new(Monitor::new(ctl));
159    let adapter = Adapter { obj, monitor: &monitor };
160    let wrapped = Monitored {
161        inner: solver,
162        monitor: &monitor,
163        iteration: 0,
164        failure: None,
165    };
166    let outcome = Executor::new(adapter, wrapped)
167        .configure(|state| state.param(DVector::from_column_slice(x0)).max_iters(max_iters))
168        .run();
169    let (iterations, exit) = match outcome {
170        Ok(result) => {
171            let failure = result.solver.failure.clone();
172            let iterations = result.solver.iteration;
173            let exit = match (failure, result.state.get_termination_reason()) {
174                (Some(m), _) => Exit::Failed(m),
175                (None, Some(TerminationReason::MaxItersReached)) => Exit::MaxIterations,
176                (None, Some(TerminationReason::Interrupt)) => Exit::Cancelled,
177                _ => Exit::Converged,
178            };
179            (iterations, exit)
180        }
181        Err(e) => (0, Exit::Failed(e.to_string())),
182    };
183    monitor.into_inner().finish(iterations, exit)
184}
185
186/// Limited-memory BFGS with a Moré–Thuente line search.
187#[derive(Clone, Copy, Debug, Default)]
188pub struct LBfgs;
189
190impl Optimizer for LBfgs {
191    fn name(&self) -> &'static str {
192        "l-bfgs"
193    }
194
195    fn derivatives(&self) -> Derivatives {
196        Derivatives::Gradient
197    }
198
199    fn minimize(&self, obj: &dyn Objective, x0: &[f64], ctl: &mut RunControl) -> Result<OptimResult> {
200        let solver: LBFGS<LineSearch, DVector<f64>, DVector<f64>, f64> =
201            LBFGS::new(MoreThuenteLineSearch::new(), LBFGS_MEMORY);
202        run::<_, ()>(solver, obj, x0, ctl)
203    }
204}
205
206/// Newton's method in a trust region on the exact Hessian, with the subproblem solved by Steihaug's truncated
207/// conjugate gradients, so indefinite Hessians are handled.
208#[derive(Clone, Copy, Debug, Default)]
209pub struct NewtonExact;
210
211impl Optimizer for NewtonExact {
212    fn name(&self) -> &'static str {
213        "newton-exact"
214    }
215
216    fn derivatives(&self) -> Derivatives {
217        Derivatives::Hessian
218    }
219
220    fn minimize(&self, obj: &dyn Objective, x0: &[f64], ctl: &mut RunControl) -> Result<OptimResult> {
221        let solver: TrustRegion<Steihaug<DVector<f64>, f64>, f64> = TrustRegion::new(Steihaug::new());
222        run::<_, DMatrix<f64>>(solver, obj, x0, ctl)
223    }
224}