Skip to main content

ctrl_freeq/optim/
mod.rs

1//! Optimisation: the objective and optimiser interfaces, the optimiser registry, and the algorithms.
2//!
3//! Every optimiser minimises an [`Objective`] through the same [`Optimizer`] trait and reports to the same
4//! [`ProgressSink`], which can also cancel the run.  All of them stop when the target fidelity is reached, return the
5//! best point they evaluated, and never see threads: parallelism lives inside the objective.
6//!
7//! A new algorithm is one type implementing [`Optimizer`] plus one entry in [`optimizer`] and [`optimizer_names`];
8//! [`Monitor`] gives it progress reports, cancellation, the target check and best-point tracking.
9
10mod cobyla;
11mod derivative_free;
12mod gradient;
13mod newton_cg;
14
15pub use derivative_free::{Bobyqa, Cobyla};
16pub use gradient::{LBfgs, NewtonExact};
17pub use newton_cg::NewtonCg;
18
19use nalgebra::DMatrix;
20use serde::{Deserialize, Serialize};
21
22use crate::error::{Error, Result};
23use crate::time::Instant;
24
25/// One evaluation of the objective.
26#[derive(Clone, Copy, Debug, PartialEq, Serialize, Deserialize)]
27pub struct Eval {
28    /// What is minimised: `penalty − fidelity`.
29    pub cost: f64,
30    /// Mean fidelity over the batch.
31    pub fidelity: f64,
32    /// Amplitude penalty.
33    pub penalty: f64,
34}
35
36impl Eval {
37    /// `fidelity − penalty`, the quantity compared with the target fidelity.
38    pub fn score(&self) -> f64 {
39        self.fidelity - self.penalty
40    }
41}
42
43/// A function to minimise.
44pub trait Objective: Sync {
45    /// Number of parameters.
46    fn dim(&self) -> usize;
47    /// The objective at `x`.
48    fn value(&self, x: &[f64]) -> Result<Eval>;
49    /// The objective and its gradient at `x`.
50    fn gradient(&self, x: &[f64]) -> Result<(Eval, Vec<f64>)>;
51    /// The objective, its gradient and its Hessian at `x`.
52    fn hessian(&self, x: &[f64]) -> Result<(Eval, Vec<f64>, DMatrix<f64>)>;
53    /// The Hessian at `x` applied to `v`.  The default forms the whole Hessian; objectives that can do better
54    /// override it.
55    fn hvp(&self, x: &[f64], v: &[f64]) -> Result<Vec<f64>> {
56        let (_, _, h) = self.hessian(x)?;
57        Ok((h * nalgebra::DVector::from_column_slice(v)).as_slice().to_vec())
58    }
59}
60
61/// What an optimiser asks the objective for.
62#[derive(Clone, Copy, Debug, PartialEq, Eq)]
63pub enum Derivatives {
64    /// Values only.
65    None,
66    /// Values and gradients.
67    Gradient,
68    /// Values, gradients and Hessians.
69    Hessian,
70}
71
72/// One row of progress.
73#[derive(Clone, Debug, PartialEq, Serialize, Deserialize)]
74pub struct IterationReport {
75    /// Iteration number; `0` is the starting point for gradient methods.  For derivative-free methods an
76    /// iteration is one function evaluation, counted from 1.
77    pub iteration: usize,
78    /// Mean fidelity.
79    pub fidelity: f64,
80    /// Amplitude penalty.
81    pub penalty: f64,
82    /// `penalty − fidelity`.
83    pub cost: f64,
84    /// Gradient norm, for gradient methods.
85    pub grad_norm: Option<f64>,
86    /// Objective evaluations so far.
87    pub evaluations: usize,
88    /// Seconds since the optimiser started.
89    pub elapsed_s: f64,
90}
91
92/// Something that watches an optimisation and can stop it.
93pub trait ProgressSink {
94    /// Called once per iteration.
95    fn on_iteration(&mut self, report: &IterationReport);
96    /// Asked after every report.  Returning `true` ends the run with [`Exit::Cancelled`], keeping the best point.
97    fn should_cancel(&self) -> bool {
98        false
99    }
100}
101
102/// A sink that ignores everything.
103#[derive(Clone, Copy, Debug, Default)]
104pub struct NoProgress;
105
106impl ProgressSink for NoProgress {
107    fn on_iteration(&mut self, _: &IterationReport) {}
108}
109
110/// A sink that keeps every report.
111#[derive(Clone, Debug, Default)]
112pub struct RecordingSink {
113    /// Every report, in order.
114    pub reports: Vec<IterationReport>,
115}
116
117impl ProgressSink for RecordingSink {
118    fn on_iteration(&mut self, report: &IterationReport) {
119        self.reports.push(report.clone());
120    }
121}
122
123/// A sink that prints an iteration table to standard output, every `every`-th row.
124#[derive(Clone, Copy, Debug)]
125pub struct ConsoleSink {
126    /// Print one row in this many; 1 prints them all.
127    pub every: usize,
128    header: bool,
129}
130
131impl ConsoleSink {
132    /// Print every `every`-th iteration.
133    pub fn new(every: usize) -> Self {
134        ConsoleSink {
135            every: every.max(1),
136            header: false,
137        }
138    }
139}
140
141impl ProgressSink for ConsoleSink {
142    fn on_iteration(&mut self, r: &IterationReport) {
143        if !self.header {
144            println!(
145                "{:>9}  {:>10}  {:>10}  {:>10}  {:>9}",
146                "iteration", "fidelity", "penalty", "|grad|", "time (s)"
147            );
148            self.header = true;
149        }
150        if r.iteration.is_multiple_of(self.every) {
151            let g = r.grad_norm.map_or("-".to_string(), |g| format!("{g:.3e}"));
152            println!(
153                "{:>9}  {:>10.6}  {:>10.3e}  {:>10}  {:>9.2}",
154                r.iteration, r.fidelity, r.penalty, g, r.elapsed_s
155            );
156        }
157    }
158}
159
160/// Why an optimisation ended.
161#[derive(Clone, Debug, PartialEq, Serialize, Deserialize)]
162pub enum Exit {
163    /// Fidelity minus penalty reached the target.
164    TargetReached,
165    /// The optimiser met its own convergence test.
166    Converged,
167    /// The iteration limit was reached.
168    MaxIterations,
169    /// The progress sink asked to stop.
170    Cancelled,
171    /// The optimiser or the objective failed; the best point so far is kept.
172    Failed(String),
173}
174
175impl Exit {
176    /// A short sentence for display.
177    pub fn message(&self) -> String {
178        match self {
179            Exit::TargetReached => "target fidelity reached".into(),
180            Exit::Converged => "converged".into(),
181            Exit::MaxIterations => "iteration limit reached".into(),
182            Exit::Cancelled => "cancelled".into(),
183            Exit::Failed(m) => format!("stopped: {m}"),
184        }
185    }
186}
187
188/// What an optimisation produced.
189#[derive(Clone, Debug, PartialEq, Serialize, Deserialize)]
190pub struct OptimResult {
191    /// The best parameters evaluated.
192    pub x: Vec<f64>,
193    /// The objective there.
194    pub eval: Eval,
195    /// Iterations completed.
196    pub iterations: usize,
197    /// Objective evaluations.
198    pub evaluations: usize,
199    /// Why the run ended.
200    pub exit: Exit,
201}
202
203/// Run settings shared by every optimiser.
204pub struct RunControl<'a> {
205    /// Iteration limit (function evaluations for derivative-free methods).
206    pub max_iter: usize,
207    /// Stop once fidelity minus penalty reaches this.
208    pub target_fidelity: f64,
209    /// Where progress goes, and where cancellation comes from.
210    pub sink: &'a mut dyn ProgressSink,
211}
212
213/// An optimisation algorithm.
214pub trait Optimizer: Send + Sync {
215    /// The name the configuration uses.
216    fn name(&self) -> &'static str;
217    /// What it needs from the objective.
218    fn derivatives(&self) -> Derivatives;
219    /// Minimise `obj` from `x0`.
220    fn minimize(&self, obj: &dyn Objective, x0: &[f64], ctl: &mut RunControl) -> Result<OptimResult>;
221}
222
223/// The optimiser with configuration name `name`.
224pub fn optimizer(name: &str) -> Result<Box<dyn Optimizer>> {
225    Ok(match name {
226        "l-bfgs" => Box::new(LBfgs),
227        "newton-cg" => Box::new(NewtonCg),
228        "newton-exact" => Box::new(NewtonExact),
229        "cobyla" => Box::new(Cobyla),
230        "bobyqa" => Box::new(Bobyqa),
231        _ => {
232            return Err(Error::NotSupported(format!(
233                "algorithm \"{name}\" is not available; choose one of {}",
234                optimizer_names().join(", ")
235            )));
236        }
237    })
238}
239
240/// Every optimiser name, in the order the interface lists them.
241pub fn optimizer_names() -> &'static [&'static str] {
242    &["l-bfgs", "newton-cg", "newton-exact", "cobyla", "bobyqa"]
243}
244
245/// Bookkeeping every optimiser shares: progress reports, the stop checks and the best point.
246pub struct Monitor<'s> {
247    sink: &'s mut dyn ProgressSink,
248    target: f64,
249    max_iter: usize,
250    started: Instant,
251    /// Objective evaluations so far.
252    pub evaluations: usize,
253    /// The best point evaluated and its value.
254    pub best: Option<(Vec<f64>, Eval)>,
255    /// Set once a stop condition has fired.
256    pub exit: Option<Exit>,
257}
258
259impl<'s> Monitor<'s> {
260    /// A monitor for `ctl`'s limits and sink.
261    pub fn new(ctl: &'s mut RunControl) -> Monitor<'s> {
262        Monitor {
263            target: ctl.target_fidelity,
264            max_iter: ctl.max_iter,
265            sink: &mut *ctl.sink,
266            started: Instant::now(),
267            evaluations: 0,
268            best: None,
269            exit: None,
270        }
271    }
272
273    /// Count an evaluation and keep it if it is the best so far.
274    pub fn evaluated(&mut self, x: &[f64], e: Eval) {
275        self.evaluations += 1;
276        if self.best.as_ref().is_none_or(|(_, b)| e.cost < b.cost) {
277            self.best = Some((x.to_vec(), e));
278        }
279    }
280
281    /// Send a report, then check the stop conditions.  `iteration` is compared with the limit.
282    pub fn report(&mut self, iteration: usize, e: Eval, grad_norm: Option<f64>) {
283        self.sink.on_iteration(&IterationReport {
284            iteration,
285            fidelity: e.fidelity,
286            penalty: e.penalty,
287            cost: e.cost,
288            grad_norm,
289            evaluations: self.evaluations,
290            elapsed_s: self.started.elapsed().as_secs_f64(),
291        });
292        if self.exit.is_some() {
293            return;
294        }
295        if e.score() >= self.target {
296            self.exit = Some(Exit::TargetReached);
297        } else if self.sink.should_cancel() {
298            self.exit = Some(Exit::Cancelled);
299        } else if iteration >= self.max_iter {
300            self.exit = Some(Exit::MaxIterations);
301        }
302    }
303
304    /// The result: the best point, with `exit` unless a stop condition fired first.
305    pub fn finish(self, iterations: usize, exit: Exit) -> Result<OptimResult> {
306        let exit = self.exit.unwrap_or(exit);
307        match self.best {
308            Some((x, eval)) => Ok(OptimResult {
309                x,
310                eval,
311                iterations,
312                evaluations: self.evaluations,
313                exit,
314            }),
315            None => Err(match exit {
316                Exit::Failed(m) => Error::Numerical(m),
317                other => Error::Numerical(format!(
318                    "the optimiser stopped ({}) before any evaluation",
319                    other.message()
320                )),
321            }),
322        }
323    }
324}