#[derive(Debug, Clone, Copy)]
pub struct LbfgsConfig {
pub memory: usize,
pub max_iters: usize,
pub gtol: f64,
pub c1: f64,
pub max_line_search: usize,
}
impl Default for LbfgsConfig {
fn default() -> Self {
Self {
memory: 8,
max_iters: 200,
gtol: 1e-8,
c1: 1e-4,
max_line_search: 30,
}
}
}
#[derive(Debug, Clone)]
pub struct LbfgsResult {
pub x: Vec<f64>,
pub fx: f64,
pub iterations: usize,
pub converged: bool,
}
#[inline]
pub(super) fn dot(a: &[f64], b: &[f64]) -> f64 {
a.iter().zip(b).map(|(x, y)| x * y).sum()
}
#[inline]
fn inf_norm(a: &[f64]) -> f64 {
a.iter().fold(0.0_f64, |m, &x| m.max(x.abs()))
}
#[derive(Debug, Clone)]
pub struct LbfgsMemory {
memory: usize,
dim: Option<usize>,
s_buf: Vec<f64>,
y_buf: Vec<f64>,
rho_buf: Vec<f64>,
head: usize,
len: usize,
}
impl LbfgsMemory {
#[must_use]
pub fn new(memory: usize) -> Self {
Self {
memory: memory.max(1),
dim: None,
s_buf: Vec::new(),
y_buf: Vec::new(),
rho_buf: Vec::new(),
head: 0,
len: 0,
}
}
#[must_use]
pub fn len(&self) -> usize {
self.len
}
#[must_use]
pub fn is_empty(&self) -> bool {
self.len == 0
}
#[inline]
fn pair_slot(&self, i: usize) -> usize {
debug_assert!(i < self.len, "pair index {i} out of range len={}", self.len);
(self.head + self.memory - 1 - i) % self.memory
}
#[inline]
fn s_row(&self, i: usize) -> &[f64] {
let n = self.dim.expect("direction() called before any push()");
let slot = self.pair_slot(i);
&self.s_buf[slot * n..(slot + 1) * n]
}
#[inline]
fn y_row(&self, i: usize) -> &[f64] {
let n = self.dim.expect("direction() called before any push()");
let slot = self.pair_slot(i);
&self.y_buf[slot * n..(slot + 1) * n]
}
#[must_use]
pub fn direction(&self, g: &[f64]) -> Vec<f64> {
let k = self.len;
if k == 0 {
return g.iter().map(|&gi| -gi).collect();
}
let n = self
.dim
.expect("invariant: len > 0 implies dim was recorded on first push");
assert_eq! {
g.len(),
n,
"LbfgsMemory::direction: gradient length {} != stored dim {n}",
g.len()
};
let mut q = g.to_vec();
let mut alpha = vec![0.0_f64; k];
#[expect(
clippy::needless_range_loop,
reason = "i is the logical ring index for s_row/y_row/pair_slot, not just alpha position"
)]
for i in 0..k {
let s_i = self.s_row(i);
let y_i = self.y_row(i);
let rho_i = self.rho_buf[self.pair_slot(i)];
let a = rho_i * dot(s_i, &q);
alpha[i] = a;
q.iter_mut()
.zip(y_i.iter())
.for_each(|(qj, &yj)| *qj -= a * yj);
}
let s_newest = self.s_row(0);
let y_newest = self.y_row(0);
let sy = dot(s_newest, y_newest);
let yy = dot(y_newest, y_newest);
let gamma = if yy > 0.0 { sy / yy } else { 1.0 };
let mut r: Vec<f64> = q.iter().map(|&qi| gamma * qi).collect();
for i in (0..k).rev() {
let s_i = self.s_row(i);
let y_i = self.y_row(i);
let rho_i = self.rho_buf[self.pair_slot(i)];
let beta = rho_i * dot(y_i, &r);
let coef = alpha[i] - beta;
r.iter_mut()
.zip(s_i.iter())
.for_each(|(rj, &sj)| *rj += coef * sj);
}
r.iter().map(|&ri| -ri).collect()
}
pub fn push(&mut self, s: Vec<f64>, y: Vec<f64>) -> bool {
let n = s.len();
if n == 0 || n != y.len() {
return false;
}
let sy = dot(&s, &y);
if sy <= 1e-12 {
return false;
}
match self.dim {
None => {
self.dim = Some(n);
self.s_buf = vec![0.0_f64; self.memory * n];
self.y_buf = vec![0.0_f64; self.memory * n];
self.rho_buf = vec![0.0_f64; self.memory];
}
Some(recorded) => {
debug_assert_eq!(
recorded, n,
"LbfgsMemory::push: pair length {n} != stored dim {recorded}"
);
}
}
let slot = self.head;
self.s_buf[slot * n..(slot + 1) * n].copy_from_slice(&s);
self.y_buf[slot * n..(slot + 1) * n].copy_from_slice(&y);
self.rho_buf[slot] = 1.0 / sy;
self.head = (self.head + 1) % self.memory;
if self.len < self.memory {
self.len += 1;
}
true
}
}
pub fn minimize<F, G>(x0: Vec<f64>, mut f: F, mut grad: G, config: LbfgsConfig) -> LbfgsResult
where
F: FnMut(&[f64]) -> f64,
G: FnMut(&[f64]) -> Vec<f64>,
{
let n = x0.len();
let mut x = x0;
let mut fx = f(&x);
let mut g = grad(&x);
let mut mem = LbfgsMemory::new(config.memory);
if inf_norm(&g) < config.gtol {
return LbfgsResult {
x,
fx,
iterations: 0,
converged: true,
};
}
for it in 1..=config.max_iters {
let dir = mem.direction(&g);
let gd = dot(&g, &dir); let mut step = if mem.is_empty() {
(1.0 / inf_norm(&g)).min(1.0)
} else {
1.0
};
let mut x_new = x.clone();
let mut fx_new = fx;
let mut accepted = false;
for _ in 0..config.max_line_search {
for j in 0..n {
x_new[j] = x[j] + step * dir[j];
}
fx_new = f(&x_new);
if fx_new <= fx + config.c1 * step * gd {
accepted = true;
break;
}
step *= 0.5;
}
if !accepted {
return LbfgsResult {
x,
fx,
iterations: it,
converged: inf_norm(&g) < config.gtol,
};
}
let g_new = grad(&x_new);
let s: Vec<f64> = (0..n).map(|j| x_new[j] - x[j]).collect();
let y: Vec<f64> = (0..n).map(|j| g_new[j] - g[j]).collect();
mem.push(s, y);
x = x_new;
fx = fx_new;
g = g_new;
if inf_norm(&g) < config.gtol {
return LbfgsResult {
x,
fx,
iterations: it,
converged: true,
};
}
}
LbfgsResult {
x,
fx,
iterations: config.max_iters,
converged: false,
}
}