use super::line_search::{LineSearchBuffers, LineSearchStart, strong_wolfe};
use crate::numeric::sum_in_order;
pub(crate) trait Problem {
fn dimension(&self) -> usize;
fn value_and_gradient(&mut self, point: &[f64], gradient: &mut [f64]) -> f64;
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(crate) enum OptimizeError {
NotConverged {
iterations: usize,
},
LineSearchFailed {
iterations: usize,
},
NonFiniteObjective {
iterations: usize,
},
}
#[derive(Clone, Copy, Debug, PartialEq)]
pub(crate) struct LbfgsOptions {
memory: usize,
max_iterations: usize,
gradient_tolerance: f64,
max_line_search_steps: usize,
max_zoom_steps: usize,
}
pub(crate) const DEFAULT_MEMORY: usize = 8;
const DEFAULT_LINE_SEARCH_STEPS: usize = 128;
const DEFAULT_ZOOM_STEPS: usize = 64;
impl LbfgsOptions {
pub(crate) fn new(max_iterations: usize, gradient_tolerance: f64) -> Self {
Self {
memory: DEFAULT_MEMORY,
max_iterations: max_iterations.max(1),
gradient_tolerance: if gradient_tolerance.is_finite() && gradient_tolerance > 0.0 {
gradient_tolerance
} else {
f64::EPSILON
},
max_line_search_steps: DEFAULT_LINE_SEARCH_STEPS,
max_zoom_steps: DEFAULT_ZOOM_STEPS,
}
}
#[cfg(test)]
pub(crate) fn with_memory(mut self, memory: usize) -> Self {
self.memory = memory.max(1);
self
}
pub(crate) const fn memory(&self) -> usize {
self.memory
}
pub(crate) const fn max_iterations(&self) -> usize {
self.max_iterations
}
pub(crate) const fn gradient_tolerance(&self) -> f64 {
self.gradient_tolerance
}
pub(crate) const fn max_line_search_steps(&self) -> usize {
self.max_line_search_steps
}
pub(crate) const fn max_zoom_steps(&self) -> usize {
self.max_zoom_steps
}
}
#[derive(Clone, Copy, Debug, PartialEq)]
pub(crate) struct LbfgsReport {
pub(crate) iterations: usize,
pub(crate) value: f64,
pub(crate) gradient_norm: f64,
}
pub(crate) struct LbfgsWorkspace {
dimension: usize,
memory: usize,
gradient: Vec<f64>,
direction: Vec<f64>,
trial_point: Vec<f64>,
trial_gradient: Vec<f64>,
steps: Vec<f64>,
gradient_deltas: Vec<f64>,
rho: Vec<f64>,
alpha: Vec<f64>,
head: usize,
stored: usize,
}
impl LbfgsWorkspace {
pub(crate) fn new(dimension: usize, memory: usize) -> Self {
let memory = memory.max(1);
Self {
dimension,
memory,
gradient: vec![0.0; dimension],
direction: vec![0.0; dimension],
trial_point: vec![0.0; dimension],
trial_gradient: vec![0.0; dimension],
steps: vec![0.0; memory * dimension],
gradient_deltas: vec![0.0; memory * dimension],
rho: vec![0.0; memory],
alpha: vec![0.0; memory],
head: 0,
stored: 0,
}
}
fn clear(&mut self) {
self.head = 0;
self.stored = 0;
}
fn slot(&self, age: usize) -> usize {
(self.head + self.memory - 1 - age) % self.memory
}
fn step(&self, slot: usize) -> &[f64] {
&self.steps[slot * self.dimension..(slot + 1) * self.dimension]
}
fn gradient_delta(&self, slot: usize) -> &[f64] {
&self.gradient_deltas[slot * self.dimension..(slot + 1) * self.dimension]
}
}
pub(super) fn dot(left: &[f64], right: &[f64]) -> f64 {
sum_in_order(left.iter().zip(right).map(|(&left, &right)| left * right))
}
fn infinity_norm(values: &[f64]) -> f64 {
values
.iter()
.fold(0.0_f64, |worst, value| worst.max(value.abs()))
}
pub(crate) fn minimize<P: Problem>(
problem: &mut P,
point: &mut [f64],
workspace: &mut LbfgsWorkspace,
options: &LbfgsOptions,
) -> Result<LbfgsReport, OptimizeError> {
debug_assert_eq!(point.len(), problem.dimension());
debug_assert_eq!(workspace.dimension, point.len());
debug_assert_eq!(workspace.memory, options.memory());
workspace.clear();
let mut value = problem.value_and_gradient(point, &mut workspace.gradient);
if !value.is_finite() || workspace.gradient.iter().any(|slot| !slot.is_finite()) {
return Err(OptimizeError::NonFiniteObjective { iterations: 0 });
}
for iteration in 0..options.max_iterations() {
let gradient_norm = infinity_norm(&workspace.gradient);
if gradient_norm <= options.gradient_tolerance() {
return Ok(LbfgsReport {
iterations: iteration,
value,
gradient_norm,
});
}
two_loop_direction(workspace);
let mut slope = dot(&workspace.gradient, &workspace.direction);
if slope >= 0.0 || !slope.is_finite() {
workspace.clear();
for (slot, &gradient) in workspace
.direction
.iter_mut()
.zip(workspace.gradient.iter())
{
*slot = -gradient;
}
slope = dot(&workspace.gradient, &workspace.direction);
if slope >= 0.0 || !slope.is_finite() {
return Err(OptimizeError::NonFiniteObjective {
iterations: iteration,
});
}
}
let initial_step = if workspace.stored == 0 {
let scale = sum_in_order(workspace.gradient.iter().map(|value| value.abs()));
if scale > 1.0 { 1.0 / scale } else { 1.0 }
} else {
1.0
};
let start = LineSearchStart {
value,
slope,
initial_step,
};
let outcome = {
let LbfgsWorkspace {
direction,
trial_point,
trial_gradient,
..
} = &mut *workspace;
let mut buffers = LineSearchBuffers {
trial_point,
trial_gradient,
};
strong_wolfe(problem, point, direction, &start, &mut buffers, options)
};
let outcome = match outcome {
Ok(outcome) => outcome,
Err(kind) => return Err(kind.at(iteration)),
};
debug_assert!(outcome.step > 0.0);
let slot = workspace.head;
let dimension = workspace.dimension;
let offset = slot * dimension;
{
let LbfgsWorkspace {
steps,
gradient_deltas,
trial_point,
trial_gradient,
gradient,
..
} = &mut *workspace;
for (target, (&trial, ¤t)) in steps[offset..offset + dimension]
.iter_mut()
.zip(trial_point.iter().zip(point.iter()))
{
*target = trial - current;
}
for (target, (&trial, ¤t)) in gradient_deltas[offset..offset + dimension]
.iter_mut()
.zip(trial_gradient.iter().zip(gradient.iter()))
{
*target = trial - current;
}
}
point.copy_from_slice(&workspace.trial_point);
workspace
.gradient
.copy_from_slice(&workspace.trial_gradient);
value = outcome.value;
let curvature = dot(
&workspace.steps[offset..offset + dimension],
&workspace.gradient_deltas[offset..offset + dimension],
);
if curvature > 0.0 && curvature.is_finite() {
workspace.rho[slot] = 1.0 / curvature;
workspace.head = (slot + 1) % workspace.memory;
workspace.stored = (workspace.stored + 1).min(workspace.memory);
}
}
Err(OptimizeError::NotConverged {
iterations: options.max_iterations(),
})
}
fn two_loop_direction(workspace: &mut LbfgsWorkspace) {
for (slot, &gradient) in workspace
.direction
.iter_mut()
.zip(workspace.gradient.iter())
{
*slot = -gradient;
}
if workspace.stored == 0 {
return;
}
let dimension = workspace.dimension;
for age in 0..workspace.stored {
let slot = workspace.slot(age);
let alpha = workspace.rho[slot] * dot(workspace.step(slot), &workspace.direction);
workspace.alpha[slot] = alpha;
for index in 0..dimension {
let delta = workspace.gradient_deltas[slot * dimension + index];
workspace.direction[index] -= alpha * delta;
}
}
let newest = workspace.slot(0);
let delta = workspace.gradient_delta(newest);
let denominator = dot(delta, delta);
if denominator > 0.0 {
let scale = 1.0 / (workspace.rho[newest] * denominator);
for slot in workspace.direction.iter_mut() {
*slot *= scale;
}
}
for age in (0..workspace.stored).rev() {
let slot = workspace.slot(age);
let beta = workspace.rho[slot] * dot(workspace.gradient_delta(slot), &workspace.direction);
let difference = workspace.alpha[slot] - beta;
for index in 0..dimension {
let iterate_delta = workspace.steps[slot * dimension + index];
workspace.direction[index] += difference * iterate_delta;
}
}
}
#[cfg(test)]
mod tests {
use super::*;
struct DiagonalQuadratic {
curvature: Vec<f64>,
centre: Vec<f64>,
evaluations: usize,
}
impl Problem for DiagonalQuadratic {
fn dimension(&self) -> usize {
self.centre.len()
}
fn value_and_gradient(&mut self, point: &[f64], gradient: &mut [f64]) -> f64 {
self.evaluations += 1;
let mut total = 0.0;
for index in 0..point.len() {
let offset = point[index] - self.centre[index];
gradient[index] = self.curvature[index] * offset;
total += 0.5 * self.curvature[index] * offset * offset;
}
total
}
}
struct Rosenbrock {
evaluations: usize,
}
impl Problem for Rosenbrock {
fn dimension(&self) -> usize {
2
}
fn value_and_gradient(&mut self, point: &[f64], gradient: &mut [f64]) -> f64 {
self.evaluations += 1;
let (x, y) = (point[0], point[1]);
gradient[0] = -400.0 * x * (y - x * x) - 2.0 * (1.0 - x);
gradient[1] = 200.0 * (y - x * x);
100.0 * (y - x * x) * (y - x * x) + (1.0 - x) * (1.0 - x)
}
}
fn solve<P: Problem>(
problem: &mut P,
start: &[f64],
options: &LbfgsOptions,
) -> (Vec<f64>, Result<LbfgsReport, OptimizeError>) {
let mut point = start.to_vec();
let mut workspace = LbfgsWorkspace::new(point.len(), options.memory());
let report = minimize(problem, &mut point, &mut workspace, options);
(point, report)
}
#[test]
fn reaches_the_analytic_minimum_of_a_well_conditioned_quadratic() {
let mut problem = DiagonalQuadratic {
curvature: vec![1.0, 2.0, 4.0, 8.0],
centre: vec![-3.0, 0.5, 7.0, 0.0],
evaluations: 0,
};
let options = LbfgsOptions::new(200, 1.0e-10);
let (point, report) = solve(&mut problem, &[0.0; 4], &options);
let report = report.expect("converged");
for (value, expected) in point.iter().zip(&[-3.0, 0.5, 7.0, 0.0]) {
assert!((value - expected).abs() <= 1.0e-9, "{point:?}");
}
assert!(report.value.abs() <= 1.0e-16, "value {}", report.value);
assert!(report.gradient_norm <= 1.0e-10);
}
#[test]
fn reaches_the_analytic_minimum_of_an_ill_conditioned_quadratic() {
let mut problem = DiagonalQuadratic {
curvature: vec![1.0e-3, 1.0, 1.0e3],
centre: vec![2.0, -1.0, 0.25],
evaluations: 0,
};
let options = LbfgsOptions::new(500, 1.0e-9);
let (point, report) = solve(&mut problem, &[0.0; 3], &options);
let report = report.expect("converged");
for (value, expected) in point.iter().zip(&[2.0, -1.0, 0.25]) {
assert!((value - expected).abs() <= 1.0e-5, "{point:?}");
}
assert!(report.iterations < 500);
}
#[test]
fn reaches_the_minimum_of_a_non_quadratic_valley() {
let mut problem = Rosenbrock { evaluations: 0 };
let options = LbfgsOptions::new(500, 1.0e-8);
let (point, report) = solve(&mut problem, &[-1.2, 1.0], &options);
report.expect("converged");
assert!((point[0] - 1.0).abs() <= 1.0e-5, "{point:?}");
assert!((point[1] - 1.0).abs() <= 1.0e-5, "{point:?}");
}
#[test]
fn a_starting_point_at_the_minimum_costs_no_iterations() {
let mut problem = DiagonalQuadratic {
curvature: vec![1.0, 3.0],
centre: vec![1.5, -2.5],
evaluations: 0,
};
let options = LbfgsOptions::new(50, 1.0e-12);
let (point, report) = solve(&mut problem, &[1.5, -2.5], &options);
let report = report.expect("converged");
assert_eq!(report.iterations, 0);
assert_eq!(problem.evaluations, 1);
assert_eq!(point, vec![1.5, -2.5]);
}
#[test]
fn identical_inputs_produce_bit_identical_iterates() {
let options = LbfgsOptions::new(200, 1.0e-11);
let mut first = Rosenbrock { evaluations: 0 };
let mut second = Rosenbrock { evaluations: 0 };
let (left, left_report) = solve(&mut first, &[-1.2, 1.0], &options);
let (right, right_report) = solve(&mut second, &[-1.2, 1.0], &options);
assert_eq!(
left.iter().map(|v| v.to_bits()).collect::<Vec<_>>(),
right.iter().map(|v| v.to_bits()).collect::<Vec<_>>()
);
assert_eq!(left_report, right_report);
assert_eq!(first.evaluations, second.evaluations);
}
#[test]
fn a_reused_workspace_forgets_the_previous_problem() {
let options = LbfgsOptions::new(200, 1.0e-11);
let mut workspace = LbfgsWorkspace::new(2, options.memory());
let mut warm = Rosenbrock { evaluations: 0 };
let mut scratch = vec![-1.2, 1.0];
minimize(&mut warm, &mut scratch, &mut workspace, &options).expect("first solve");
let mut second = DiagonalQuadratic {
curvature: vec![1.0, 5.0],
centre: vec![3.0, -4.0],
evaluations: 0,
};
let mut reused = vec![0.0, 0.0];
let warm_report = minimize(&mut second, &mut reused, &mut workspace, &options)
.expect("second solve on a reused workspace");
let mut fresh_problem = DiagonalQuadratic {
curvature: vec![1.0, 5.0],
centre: vec![3.0, -4.0],
evaluations: 0,
};
let (fresh, fresh_report) = solve(&mut fresh_problem, &[0.0, 0.0], &options);
assert_eq!(
reused.iter().map(|v| v.to_bits()).collect::<Vec<_>>(),
fresh.iter().map(|v| v.to_bits()).collect::<Vec<_>>()
);
assert_eq!(warm_report, fresh_report.expect("fresh solve"));
}
#[test]
fn exhausting_the_iteration_budget_is_an_error_rather_than_a_result() {
let mut problem = Rosenbrock { evaluations: 0 };
let options = LbfgsOptions::new(2, 1.0e-12);
let (_, report) = solve(&mut problem, &[-1.2, 1.0], &options);
assert_eq!(report, Err(OptimizeError::NotConverged { iterations: 2 }));
}
#[test]
fn a_non_finite_objective_is_reported_before_any_step() {
struct Broken;
impl Problem for Broken {
fn dimension(&self) -> usize {
1
}
fn value_and_gradient(&mut self, _point: &[f64], gradient: &mut [f64]) -> f64 {
gradient[0] = f64::NAN;
f64::NAN
}
}
let options = LbfgsOptions::new(10, 1.0e-8);
let (_, report) = solve(&mut Broken, &[0.0], &options);
assert_eq!(
report,
Err(OptimizeError::NonFiniteObjective { iterations: 0 })
);
}
#[test]
fn an_unbounded_objective_fails_the_line_search_rather_than_diverging() {
struct Linear;
impl Problem for Linear {
fn dimension(&self) -> usize {
1
}
fn value_and_gradient(&mut self, point: &[f64], gradient: &mut [f64]) -> f64 {
gradient[0] = -1.0;
-point[0]
}
}
let options = LbfgsOptions::new(10, 1.0e-8);
let (_, report) = solve(&mut Linear, &[0.0], &options);
assert!(
matches!(
report,
Err(OptimizeError::LineSearchFailed { .. })
| Err(OptimizeError::NonFiniteObjective { .. })
),
"{report:?}"
);
}
#[test]
fn a_solve_after_the_workspace_exists_performs_no_allocation() {
let options = LbfgsOptions::new(200, 1.0e-11).with_memory(3);
let mut workspace = LbfgsWorkspace::new(2, options.memory());
let capacities = (
workspace.steps.capacity(),
workspace.gradient_deltas.capacity(),
workspace.rho.capacity(),
workspace.alpha.capacity(),
workspace.direction.capacity(),
);
let mut problem = Rosenbrock { evaluations: 0 };
let mut point = vec![-1.2, 1.0];
let report =
minimize(&mut problem, &mut point, &mut workspace, &options).expect("converged");
assert!(report.iterations > 3, "the ring must actually wrap");
assert_eq!(workspace.stored, 3);
assert_eq!(
capacities,
(
workspace.steps.capacity(),
workspace.gradient_deltas.capacity(),
workspace.rho.capacity(),
workspace.alpha.capacity(),
workspace.direction.capacity(),
)
);
}
#[test]
fn a_smaller_memory_still_converges_on_the_same_problem() {
for memory in 1..=8 {
let options = LbfgsOptions::new(1_000, 1.0e-9).with_memory(memory);
let mut problem = Rosenbrock { evaluations: 0 };
let (point, report) = solve(&mut problem, &[-1.2, 1.0], &options);
report.unwrap_or_else(|error| panic!("memory {memory}: {error:?}"));
assert!(
(point[0] - 1.0).abs() <= 1.0e-4,
"memory {memory}: {point:?}"
);
}
}
#[derive(Clone, Debug)]
enum Spec {
Diagonal {
curvature: Vec<f64>,
centre: Vec<f64>,
},
Rosenbrock {
scale: f64,
},
}
struct ScaledRosenbrock {
scale: f64,
evaluations: usize,
}
impl Problem for ScaledRosenbrock {
fn dimension(&self) -> usize {
2
}
fn value_and_gradient(&mut self, point: &[f64], gradient: &mut [f64]) -> f64 {
self.evaluations += 1;
let (x, y) = (point[0], point[1]);
let gap = y - x * x;
gradient[0] = -4.0 * self.scale * x * gap - 2.0 * (1.0 - x);
gradient[1] = 2.0 * self.scale * gap;
self.scale * gap * gap + (1.0 - x) * (1.0 - x)
}
}
fn build(spec: &Spec) -> Box<dyn Problem> {
match spec {
Spec::Diagonal { curvature, centre } => Box::new(DiagonalQuadratic {
curvature: curvature.clone(),
centre: centre.clone(),
evaluations: 0,
}),
Spec::Rosenbrock { scale } => Box::new(ScaledRosenbrock {
scale: *scale,
evaluations: 0,
}),
}
}
impl Problem for Box<dyn Problem> {
fn dimension(&self) -> usize {
(**self).dimension()
}
fn value_and_gradient(&mut self, point: &[f64], gradient: &mut [f64]) -> f64 {
(**self).value_and_gradient(point, gradient)
}
}
#[test]
fn an_exhausted_budget_never_returns_an_iterate_and_every_answer_verifies() {
let mut rng = crate::numeric::OwnedRng::new(0x0b1e_c714_5eed_0002);
let (mut problems, mut budgets_tried) = (0_usize, 0_usize);
let (mut converged, mut not_converged, mut other_refusals) = (0_usize, 0, 0);
let mut worst_value_mismatch = 0_u64;
let mut worst_norm_mismatch = 0_u64;
let mut problems_needing_several_iterations = 0_usize;
let mut control_perturbed_points_over_tolerance = 0_usize;
for _ in 0..48 {
let spec = if rng.index(3) == 0 {
Spec::Rosenbrock {
scale: 10.0_f64.powf(rng.unit_f64() * 3.0),
}
} else {
let dimension = 1 + rng.index(5);
Spec::Diagonal {
curvature: (0..dimension)
.map(|_| 10.0_f64.powf(rng.unit_f64() * 4.0 - 2.0))
.collect(),
centre: (0..dimension).map(|_| rng.unit_f64() * 8.0 - 4.0).collect(),
}
};
let dimension = build(&spec).dimension();
let start = (0..dimension)
.map(|_| rng.unit_f64() * 4.0 - 2.0)
.collect::<Vec<_>>();
let tolerance = 10.0_f64.powi(-(6 + rng.index(4) as i32));
let mut first_answer: Option<(usize, Vec<u64>)> = None;
for budget in 1..=40_usize {
budgets_tried += 1;
let options = LbfgsOptions::new(budget, tolerance);
let mut problem = build(&spec);
let mut point = start.clone();
let mut workspace = LbfgsWorkspace::new(dimension, options.memory());
let report = minimize(&mut problem, &mut point, &mut workspace, &options);
match report {
Ok(report) => {
converged += 1;
let mut fresh = build(&spec);
let mut gradient = vec![0.0; dimension];
let value = fresh.value_and_gradient(&point, &mut gradient);
worst_value_mismatch = worst_value_mismatch
.max(value.to_bits().abs_diff(report.value.to_bits()));
let norm = infinity_norm(&gradient);
worst_norm_mismatch = worst_norm_mismatch
.max(norm.to_bits().abs_diff(report.gradient_norm.to_bits()));
assert!(
norm <= tolerance,
"an accepted point has gradient norm {norm} above tolerance \
{tolerance}"
);
assert!(
report.iterations <= budget,
"reported {} iterations under a budget of {budget}",
report.iterations
);
let displaced = point.iter().map(|value| value + 0.25).collect::<Vec<_>>();
let mut displaced_gradient = vec![0.0; dimension];
build(&spec).value_and_gradient(&displaced, &mut displaced_gradient);
if infinity_norm(&displaced_gradient) > tolerance {
control_perturbed_points_over_tolerance += 1;
}
let bits = point
.iter()
.map(|value| value.to_bits())
.collect::<Vec<_>>();
match &first_answer {
None => {
if budget > 1 {
problems_needing_several_iterations += 1;
}
first_answer = Some((budget, bits));
}
Some((first_budget, first_bits)) => assert_eq!(
&bits, first_bits,
"budget {budget} returned a different point than the \
smallest converging budget {first_budget}"
),
}
}
Err(OptimizeError::NotConverged { iterations }) => {
not_converged += 1;
assert_eq!(
iterations, budget,
"an exhausted budget must report the budget it exhausted"
);
assert!(
first_answer.is_none(),
"budget {budget} refused after a smaller budget had converged"
);
}
Err(_) => {
other_refusals += 1;
assert!(
first_answer.is_none(),
"budget {budget} refused after a smaller budget had converged"
);
}
}
}
problems += 1;
}
println!(
"lbfgs budgets: {problems} problems x 40 budgets = {budgets_tried} solves; \
{converged} converged, {not_converged} exhausted the budget, \
{other_refusals} refused otherwise"
);
println!(
"lbfgs verification: worst value mismatch {worst_value_mismatch} ulp, worst \
gradient-norm mismatch {worst_norm_mismatch} ulp, {problems_needing_several_iterations} \
problems needed more than one iteration"
);
println!(
"lbfgs control: a point displaced by 0.25 exceeds the tolerance in \
{control_perturbed_points_over_tolerance} of {converged} accepted solves"
);
assert_eq!(
worst_value_mismatch, 0,
"the report must describe the point"
);
assert_eq!(worst_norm_mismatch, 0, "the report must describe the point");
assert!(converged > 0 && not_converged > 0, "both branches must run");
assert!(
problems_needing_several_iterations * 2 > problems,
"only {problems_needing_several_iterations} of {problems} problems took more \
than one iteration, so the budget boundary was barely exercised"
);
assert_eq!(
control_perturbed_points_over_tolerance, converged,
"the gradient tolerance was satisfied at a displaced point too, so passing it \
at the returned point says nothing"
);
}
#[test]
fn the_objective_decreases_at_every_accepted_step() {
struct Recording {
inner: Rosenbrock,
accepted: Vec<f64>,
}
impl Problem for Recording {
fn dimension(&self) -> usize {
self.inner.dimension()
}
fn value_and_gradient(&mut self, point: &[f64], gradient: &mut [f64]) -> f64 {
let value = self.inner.value_and_gradient(point, gradient);
self.accepted.push(value);
value
}
}
let options = LbfgsOptions::new(200, 1.0e-10);
let mut problem = Recording {
inner: Rosenbrock { evaluations: 0 },
accepted: Vec::new(),
};
let mut point = vec![-1.2, 1.0];
let mut workspace = LbfgsWorkspace::new(2, options.memory());
let report =
minimize(&mut problem, &mut point, &mut workspace, &options).expect("converged");
assert!(report.value <= problem.accepted[0]);
assert!(report.value <= 1.0e-16, "value {}", report.value);
}
}