use crate::error::{BarracudaError, Result};
#[derive(Debug, Clone)]
pub struct LbfgsConfig {
pub memory: usize,
pub max_iter: usize,
pub gtol: f64,
pub ftol: f64,
pub c1: f64,
pub c2: f64,
pub max_linesearch: usize,
}
impl Default for LbfgsConfig {
fn default() -> Self {
Self {
memory: 10,
max_iter: 1000,
gtol: 1e-6,
ftol: 1e-8,
c1: 1e-4,
c2: 0.9,
max_linesearch: 20,
}
}
}
#[derive(Debug, Clone)]
pub struct LbfgsResult {
pub x: Vec<f64>,
pub f_val: f64,
pub gradient: Vec<f64>,
pub iterations: usize,
pub function_evaluations: usize,
pub converged: bool,
}
pub fn lbfgs<F, G>(f: F, grad: G, x0: &[f64], config: &LbfgsConfig) -> Result<LbfgsResult>
where
F: Fn(&[f64]) -> f64,
G: Fn(&[f64], &mut [f64]),
{
let n = x0.len();
if n == 0 {
return Err(BarracudaError::InvalidInput {
message: "L-BFGS requires at least 1 dimension".to_string(),
});
}
if config.memory == 0 {
return Err(BarracudaError::InvalidInput {
message: "L-BFGS memory must be >= 1".to_string(),
});
}
let m = config.memory;
let mut x = x0.to_vec();
let mut g = vec![0.0; n];
let mut f_val = f(&x);
grad(&x, &mut g);
let mut n_evals = 1usize;
let mut s_history: Vec<Vec<f64>> = Vec::with_capacity(m);
let mut y_history: Vec<Vec<f64>> = Vec::with_capacity(m);
let mut rho_history: Vec<f64> = Vec::with_capacity(m);
let mut x_prev = vec![0.0; n];
let mut g_prev = vec![0.0; n];
for iter in 0..config.max_iter {
let g_norm = g.iter().map(|v| v * v).sum::<f64>().sqrt();
if g_norm < config.gtol {
return Ok(LbfgsResult {
x,
f_val,
gradient: g,
iterations: iter,
function_evaluations: n_evals,
converged: true,
});
}
let d = two_loop_recursion(n, &g, &s_history, &y_history, &rho_history);
let (alpha, f_new, evals) =
backtracking_line_search(&f, &x, &d, f_val, &g, config.c1, config.max_linesearch);
n_evals += evals;
if (f_val - f_new).abs() < config.ftol * (1.0 + f_val.abs()) && iter > 0 {
return Ok(LbfgsResult {
x,
f_val,
gradient: g,
iterations: iter,
function_evaluations: n_evals,
converged: true,
});
}
x_prev.copy_from_slice(&x);
g_prev.copy_from_slice(&g);
for i in 0..n {
x[i] = alpha.mul_add(d[i], x[i]);
}
f_val = f_new;
grad(&x, &mut g);
n_evals += 1;
let mut s_k = vec![0.0; n];
let mut y_k = vec![0.0; n];
let mut sy = 0.0;
for i in 0..n {
s_k[i] = x[i] - x_prev[i];
y_k[i] = g[i] - g_prev[i];
sy = s_k[i].mul_add(y_k[i], sy);
}
if sy > 1e-30 {
let rho_k = 1.0 / sy;
if s_history.len() == m {
s_history.remove(0);
y_history.remove(0);
rho_history.remove(0);
}
s_history.push(s_k);
y_history.push(y_k);
rho_history.push(rho_k);
}
}
Ok(LbfgsResult {
x,
f_val,
gradient: g,
iterations: config.max_iter,
function_evaluations: n_evals,
converged: false,
})
}
pub fn lbfgs_numerical<F>(f: F, x0: &[f64], config: &LbfgsConfig) -> Result<LbfgsResult>
where
F: Fn(&[f64]) -> f64,
{
let h = 1e-7;
let n = x0.len();
lbfgs(
&f,
|x: &[f64], grad: &mut [f64]| {
let mut x_plus = x.to_vec();
let mut x_minus = x.to_vec();
for i in 0..n {
let orig = x[i];
x_plus[i] = orig + h;
x_minus[i] = orig - h;
grad[i] = (f(&x_plus) - f(&x_minus)) / (2.0 * h);
x_plus[i] = orig;
x_minus[i] = orig;
}
},
x0,
config,
)
}
fn two_loop_recursion(
n: usize,
g: &[f64],
s_history: &[Vec<f64>],
y_history: &[Vec<f64>],
rho_history: &[f64],
) -> Vec<f64> {
let k = s_history.len();
let mut q = g.to_vec();
let mut alpha_buf = vec![0.0; k];
for i in (0..k).rev() {
let dot: f64 = s_history[i].iter().zip(q.iter()).map(|(a, b)| a * b).sum();
alpha_buf[i] = rho_history[i] * dot;
for j in 0..n {
q[j] = alpha_buf[i].mul_add(-y_history[i][j], q[j]);
}
}
if k > 0 {
let last = k - 1;
let sy: f64 = s_history[last]
.iter()
.zip(y_history[last].iter())
.map(|(a, b)| a * b)
.sum();
let yy: f64 = y_history[last].iter().map(|v| v * v).sum();
if yy > 1e-30 {
let gamma = sy / yy;
for v in &mut q {
*v *= gamma;
}
}
}
for i in 0..k {
let dot: f64 = y_history[i].iter().zip(q.iter()).map(|(a, b)| a * b).sum();
let beta = rho_history[i] * dot;
for j in 0..n {
q[j] = (alpha_buf[i] - beta).mul_add(s_history[i][j], q[j]);
}
}
for v in &mut q {
*v = -*v;
}
q
}
fn backtracking_line_search<F>(
f: &F,
x: &[f64],
d: &[f64],
f0: f64,
g: &[f64],
c1: f64,
max_iter: usize,
) -> (f64, f64, usize)
where
F: Fn(&[f64]) -> f64,
{
let n = x.len();
let dg: f64 = d.iter().zip(g.iter()).map(|(a, b)| a * b).sum();
let mut alpha = 1.0;
let mut x_trial = vec![0.0; n];
let mut evals = 0;
for _ in 0..max_iter {
for i in 0..n {
x_trial[i] = x[i] + alpha * d[i];
}
let f_trial = f(&x_trial);
evals += 1;
if f_trial <= (c1 * alpha).mul_add(dg, f0) {
return (alpha, f_trial, evals);
}
alpha *= 0.5;
}
for i in 0..n {
x_trial[i] = x[i] + alpha * d[i];
}
let f_trial = f(&x_trial);
evals += 1;
(alpha, f_trial, evals)
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_lbfgs_rosenbrock() {
let rosenbrock = |x: &[f64]| {
let (a, b) = (1.0, 100.0);
(a - x[0]).mul_add(a - x[0], b * x[0].mul_add(-x[0], x[1]).powi(2))
};
let grad_rosenbrock = |x: &[f64], g: &mut [f64]| {
let (a, b) = (1.0, 100.0);
g[0] = (-2.0f64).mul_add(
a - x[0],
2.0 * b * x[0].mul_add(-x[0], x[1]) * (-2.0 * x[0]),
);
g[1] = 2.0 * b * x[0].mul_add(-x[0], x[1]);
};
let config = LbfgsConfig {
memory: 10,
max_iter: 2000,
gtol: 1e-8,
..Default::default()
};
let result = lbfgs(rosenbrock, grad_rosenbrock, &[-1.0, 1.0], &config).unwrap();
assert!(result.converged, "L-BFGS did not converge");
assert!(
(result.x[0] - 1.0).abs() < 1e-4,
"x[0] = {}, expected 1.0",
result.x[0]
);
assert!(
(result.x[1] - 1.0).abs() < 1e-4,
"x[1] = {}, expected 1.0",
result.x[1]
);
}
#[test]
fn test_lbfgs_quadratic() {
let quad = |x: &[f64]| x[0].mul_add(x[0], 4.0 * x[1] * x[1]);
let grad_quad = |x: &[f64], g: &mut [f64]| {
g[0] = 2.0 * x[0];
g[1] = 8.0 * x[1];
};
let result = lbfgs(quad, grad_quad, &[5.0, 3.0], &LbfgsConfig::default()).unwrap();
assert!(result.converged);
assert!(result.f_val < 1e-8, "f = {}", result.f_val);
}
#[test]
fn test_lbfgs_numerical_gradient() {
let quad = |x: &[f64]| x[2].mul_add(x[2], x[0].mul_add(x[0], x[1] * x[1]));
let result = lbfgs_numerical(quad, &[3.0, 4.0, 5.0], &LbfgsConfig::default()).unwrap();
assert!(result.converged);
assert!(result.f_val < 1e-6, "f = {}", result.f_val);
}
#[test]
fn test_lbfgs_memory_depth() {
let quad = |x: &[f64]| x.iter().map(|v| v * v).sum::<f64>();
let grad = |x: &[f64], g: &mut [f64]| {
for (gi, xi) in g.iter_mut().zip(x.iter()) {
*gi = 2.0 * xi;
}
};
let config = LbfgsConfig {
memory: 3,
..Default::default()
};
let x0: Vec<f64> = (0..20).map(|i| (i as f64) + 1.0).collect();
let result = lbfgs(quad, grad, &x0, &config).unwrap();
assert!(result.converged);
assert!(result.f_val < 1e-8);
}
}