use crate::error::{BarracudaError, Result};
pub fn nelder_mead<F>(
f: F,
x0: &[f64],
bounds: &[(f64, f64)],
max_iter: usize,
tol: f64,
) -> Result<(Vec<f64>, f64, usize)>
where
F: Fn(&[f64]) -> f64,
{
let n = x0.len();
if bounds.len() != n {
return Err(BarracudaError::InvalidInput {
message: format!("Bounds length {} must match x0 length {}", bounds.len(), n),
});
}
const ALPHA: f64 = 1.0; const GAMMA: f64 = 2.0; const RHO: f64 = 0.5; const SIGMA: f64 = 0.5;
let mut simplex = Vec::with_capacity(n + 1);
let mut f_vals = Vec::with_capacity(n + 1);
let x0_bounded = project_bounds(x0, bounds);
let f0 = f(&x0_bounded);
simplex.push(x0_bounded);
f_vals.push(f0);
for i in 0..n {
let mut x = x0.to_vec();
let delta = 0.05 * (bounds[i].1 - bounds[i].0).max(0.1);
x[i] += delta;
let x_bounded = project_bounds(&x, bounds);
let fx = f(&x_bounded);
simplex.push(x_bounded);
f_vals.push(fx);
}
let mut n_evals = n + 1;
for _iter in 0..max_iter {
let mut indices: Vec<usize> = (0..=n).collect();
indices.sort_by(|&i, &j| {
f_vals[i]
.partial_cmp(&f_vals[j])
.unwrap_or(std::cmp::Ordering::Equal)
});
let best_idx = indices[0];
let worst_idx = indices[n];
let second_worst_idx = indices[n - 1];
let f_mean: f64 = f_vals.iter().sum::<f64>() / (n + 1) as f64;
let f_std =
(f_vals.iter().map(|&fi| (fi - f_mean).powi(2)).sum::<f64>() / (n + 1) as f64).sqrt();
if f_std < tol {
return Ok((simplex[best_idx].clone(), f_vals[best_idx], n_evals));
}
let mut centroid = vec![0.0; n];
for &idx in &indices[..n] {
for (j, c) in centroid.iter_mut().enumerate() {
*c += simplex[idx][j];
}
}
for c in &mut centroid {
*c /= n as f64;
}
let x_reflect = reflect(&simplex[worst_idx], ¢roid, ALPHA);
let x_reflect = project_bounds(&x_reflect, bounds);
let f_reflect = f(&x_reflect);
n_evals += 1;
if f_reflect < f_vals[best_idx] {
let x_expand = reflect(&simplex[worst_idx], ¢roid, GAMMA);
let x_expand = project_bounds(&x_expand, bounds);
let f_expand = f(&x_expand);
n_evals += 1;
if f_expand < f_reflect {
simplex[worst_idx] = x_expand;
f_vals[worst_idx] = f_expand;
} else {
simplex[worst_idx] = x_reflect;
f_vals[worst_idx] = f_reflect;
}
} else if f_reflect < f_vals[second_worst_idx] {
simplex[worst_idx] = x_reflect;
f_vals[worst_idx] = f_reflect;
} else {
let x_contract = if f_reflect < f_vals[worst_idx] {
reflect(&simplex[worst_idx], ¢roid, ALPHA * RHO)
} else {
reflect(&simplex[worst_idx], ¢roid, -RHO)
};
let x_contract = project_bounds(&x_contract, bounds);
let f_contract = f(&x_contract);
n_evals += 1;
if f_contract < f_vals[worst_idx] {
simplex[worst_idx] = x_contract;
f_vals[worst_idx] = f_contract;
} else {
let best_row = simplex[best_idx].clone();
for i in 0..=n {
if i != best_idx {
for (j, slot) in simplex[i].iter_mut().enumerate() {
*slot = SIGMA.mul_add(*slot - best_row[j], best_row[j]);
}
simplex[i] = project_bounds(&simplex[i], bounds);
f_vals[i] = f(&simplex[i]);
n_evals += 1;
}
}
}
}
if n_evals >= max_iter {
break;
}
}
let best_idx = f_vals
.iter()
.enumerate()
.min_by(|(_, a), (_, b)| a.partial_cmp(b).unwrap_or(std::cmp::Ordering::Equal))
.map_or(0, |(idx, _)| idx);
Ok((simplex[best_idx].clone(), f_vals[best_idx], n_evals))
}
fn reflect(x: &[f64], centroid: &[f64], alpha: f64) -> Vec<f64> {
centroid
.iter()
.zip(x.iter())
.map(|(&c, &xi)| alpha.mul_add(c - xi, c))
.collect()
}
fn project_bounds(x: &[f64], bounds: &[(f64, f64)]) -> Vec<f64> {
x.iter()
.zip(bounds.iter())
.map(|(&xi, &(lo, hi))| xi.clamp(lo, hi))
.collect()
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_nelder_mead_quadratic() {
let f = |x: &[f64]| (x[1] - 3.0).mul_add(x[1] - 3.0, (x[0] - 2.0).powi(2));
let x0 = vec![0.0, 0.0];
let bounds = vec![(-10.0, 10.0), (-10.0, 10.0)];
let (x_best, f_best, _) = nelder_mead(f, &x0, &bounds, 1000, 1e-8).unwrap();
assert!((x_best[0] - 2.0).abs() < 1e-4);
assert!((x_best[1] - 3.0).abs() < 1e-4);
assert!(f_best < 1e-6);
}
#[test]
fn test_nelder_mead_rosenbrock() {
let f = |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 x0 = vec![0.0, 0.0];
let bounds = vec![(-5.0, 5.0), (-5.0, 5.0)];
let (x_best, f_best, _) = nelder_mead(f, &x0, &bounds, 2000, 1e-6).unwrap();
assert!((x_best[0] - 1.0).abs() < 1e-2);
assert!((x_best[1] - 1.0).abs() < 1e-2);
assert!(f_best < 1e-3);
}
#[test]
fn test_nelder_mead_with_bounds() {
let f = |x: &[f64]| x[1].mul_add(x[1], x[0].powi(2));
let x0 = vec![5.0, 5.0];
let bounds = vec![(0.0, 10.0), (0.0, 10.0)];
let (x_best, f_best, _) = nelder_mead(f, &x0, &bounds, 1000, 1e-8).unwrap();
assert!((x_best[0] - 0.0).abs() < 1e-4);
assert!((x_best[1] - 0.0).abs() < 1e-4);
assert!(f_best < 1e-6);
}
#[test]
fn test_nelder_mead_1d() {
let f = |x: &[f64]| (x[0] - 3.0).powi(2);
let x0 = vec![0.0];
let bounds = vec![(-10.0, 10.0)];
let (x_best, f_best, _) = nelder_mead(f, &x0, &bounds, 500, 1e-10).unwrap();
assert!((x_best[0] - 3.0).abs() < 1e-6);
assert!(f_best < 1e-10);
}
#[test]
fn test_nelder_mead_bounds_mismatch() {
let f = |x: &[f64]| x[0].powi(2);
let x0 = vec![0.0, 0.0];
let bounds = vec![(0.0, 1.0)];
let result = nelder_mead(f, &x0, &bounds, 100, 1e-8);
assert!(result.is_err());
}
#[test]
fn test_nelder_mead_constrained_minimum() {
let f = |x: &[f64]| x[0] + x[1];
let x0 = vec![1.5, 1.5];
let bounds = vec![(1.0, 2.0), (1.0, 2.0)];
let (x_best, f_best, _) = nelder_mead(f, &x0, &bounds, 500, 1e-8).unwrap();
assert!((x_best[0] - 1.0).abs() < 1e-4);
assert!((x_best[1] - 1.0).abs() < 1e-4);
assert!((f_best - 2.0).abs() < 1e-4);
}
}