const SUFFICIENT_DECREASE: f64 = 1.0e-4;
const MAX_HALVINGS: usize = 60;
#[derive(Clone, Copy, Debug, PartialEq)]
pub(crate) struct DampedStep {
pub(crate) factor: f64,
pub(crate) value: f64,
}
pub(crate) fn armijo_backtracking(
point: &mut [f64],
step: &[f64],
trial: &mut [f64],
value: f64,
decrement: f64,
mut value_at: impl FnMut(&[f64]) -> f64,
) -> Option<DampedStep> {
debug_assert_eq!(point.len(), step.len());
debug_assert_eq!(point.len(), trial.len());
let mut factor = 1.0_f64;
for _ in 0..MAX_HALVINGS {
for (slot, (&start, &delta)) in trial.iter_mut().zip(point.iter().zip(step)) {
*slot = start - factor * delta;
}
let candidate = value_at(trial);
if candidate < value && candidate <= value - SUFFICIENT_DECREASE * factor * decrement {
point.copy_from_slice(trial);
return Some(DampedStep {
factor,
value: candidate,
});
}
factor *= 0.5;
}
None
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn an_exact_step_on_a_quadratic_is_accepted_whole() {
let mut point = [3.0_f64];
let mut trial = [0.0_f64];
let value_at = |probe: &[f64]| 0.5 * probe[0] * probe[0];
let step = [3.0_f64];
let decrement = 3.0 * 3.0;
let outcome = armijo_backtracking(
&mut point,
&step,
&mut trial,
value_at(&[3.0]),
decrement,
value_at,
)
.expect("a quadratic's exact step decreases the objective");
assert_eq!(outcome.factor, 1.0);
assert_eq!(point, [0.0]);
assert_eq!(outcome.value, 0.0);
}
#[test]
fn an_overlong_step_is_halved_to_a_power_of_two() {
let value_at = |probe: &[f64]| probe[0] * probe[0] * probe[0] * probe[0];
let mut point = [1.0_f64];
let mut trial = [0.0_f64];
let step = [16.0_f64];
let decrement = 4.0 * 16.0;
let outcome = armijo_backtracking(
&mut point,
&step,
&mut trial,
value_at(&[1.0]),
decrement,
value_at,
)
.expect("halving reaches a decreasing step");
assert!(
outcome.factor < 1.0,
"factor {} was not damped",
outcome.factor
);
assert_eq!(
outcome.factor,
outcome.factor.recip().recip(),
"an exact power of two survives a round trip through its reciprocal"
);
assert_eq!(outcome.factor.log2(), outcome.factor.log2().trunc());
assert!(
outcome.value < 1.0,
"value {} did not decrease",
outcome.value
);
}
#[test]
fn a_non_descent_direction_is_refused_and_leaves_the_point_alone() {
let value_at = |probe: &[f64]| 0.5 * probe[0] * probe[0];
let mut point = [1.0_f64];
let mut trial = [0.0_f64];
let step = [-1.0_f64];
assert_eq!(
armijo_backtracking(
&mut point,
&step,
&mut trial,
value_at(&[1.0]),
1.0,
value_at
),
None
);
assert_eq!(point, [1.0]);
}
#[test]
fn a_zero_step_is_refused() {
let value_at = |probe: &[f64]| 0.5 * probe[0] * probe[0];
let mut point = [0.0_f64];
let mut trial = [0.0_f64];
assert_eq!(
armijo_backtracking(&mut point, &[0.0], &mut trial, 0.0, 0.0, value_at),
None
);
assert_eq!(point, [0.0]);
}
#[test]
fn a_non_finite_objective_is_refused() {
let mut point = [1.0_f64];
let mut trial = [0.0_f64];
assert_eq!(
armijo_backtracking(&mut point, &[1.0], &mut trial, 1.0, 1.0, |_| f64::NAN),
None
);
assert_eq!(point, [1.0]);
assert_eq!(
armijo_backtracking(&mut point, &[1.0], &mut trial, 1.0, 1.0, |_| f64::INFINITY),
None
);
assert_eq!(point, [1.0]);
}
#[test]
fn the_accepted_factor_is_reproducible() {
let value_at = |probe: &[f64]| probe[0] * probe[0] * probe[0] * probe[0];
let run = || {
let mut point = [1.0_f64];
let mut trial = [0.0_f64];
armijo_backtracking(&mut point, &[16.0], &mut trial, 1.0, 64.0, value_at).map(
|outcome| {
(
outcome.factor.to_bits(),
outcome.value.to_bits(),
point[0].to_bits(),
)
},
)
};
assert_eq!(run(), run());
}
}