use crate::error::{BarracudaError, Result};
use crate::optimize::eval_record::EvaluationCache;
use crate::sample::latin_hypercube;
#[derive(Debug, Clone)]
pub struct SolverResult {
pub x_best: Vec<f64>,
pub f_best: f64,
pub n_evals: usize,
pub converged: bool,
}
pub fn multi_start_nelder_mead<F>(
f: F,
bounds: &[(f64, f64)],
n_starts: usize,
max_iter_per_start: usize,
tol: f64,
seed: u64,
) -> Result<(SolverResult, EvaluationCache, Vec<SolverResult>)>
where
F: Fn(&[f64]) -> f64,
{
if n_starts == 0 {
return Err(BarracudaError::InvalidInput {
message: "n_starts must be > 0".to_string(),
});
}
if bounds.is_empty() {
return Err(BarracudaError::InvalidInput {
message: "bounds must be non-empty".to_string(),
});
}
let n_dims = bounds.len();
let initial_points = latin_hypercube(n_starts, bounds, seed)?;
let mut global_cache = EvaluationCache::with_capacity(n_starts * max_iter_per_start);
let mut all_results = Vec::with_capacity(n_starts);
for x0 in &initial_points {
let result = run_single_nm(
&f,
x0,
bounds,
n_dims,
max_iter_per_start,
tol,
&mut global_cache,
);
all_results.push(result);
}
let best_idx = all_results
.iter()
.enumerate()
.min_by(|(_, a), (_, b)| {
a.f_best
.partial_cmp(&b.f_best)
.unwrap_or(std::cmp::Ordering::Equal)
})
.map_or(0, |(idx, _)| idx);
let best = all_results[best_idx].clone();
Ok((best, global_cache, all_results))
}
fn run_single_nm<F>(
f: &F,
x0: &[f64],
bounds: &[(f64, f64)],
n: usize,
max_iter: usize,
tol: f64,
cache: &mut EvaluationCache,
) -> SolverResult
where
F: Fn(&[f64]) -> f64,
{
const ALPHA: f64 = 1.0; const GAMMA: f64 = 2.0; const RHO: f64 = 0.5; const SIGMA: f64 = 0.5;
let eval = |x: &[f64], cache: &mut EvaluationCache| -> f64 {
let val = f(x);
cache.record(x.to_vec(), val);
val
};
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 = eval(&x0_bounded, cache);
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 = eval(&x_bounded, cache);
simplex.push(x_bounded);
f_vals.push(fx);
}
let mut n_evals = n + 1;
let mut converged = false;
for _iter in 0..max_iter {
if n_evals >= max_iter {
break;
}
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 {
converged = true;
break;
}
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 = eval(&x_reflect, cache);
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 = eval(&x_expand, cache);
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 = eval(&x_contract, cache);
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] = eval(&simplex[i], cache);
n_evals += 1;
}
}
}
}
}
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);
SolverResult {
x_best: simplex[best_idx].clone(),
f_best: f_vals[best_idx],
n_evals,
converged,
}
}
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_multi_start_quadratic() {
let f = |x: &[f64]| (x[1] - 3.0).mul_add(x[1] - 3.0, (x[0] - 2.0).powi(2));
let bounds = vec![(-10.0, 10.0), (-10.0, 10.0)];
let (best, cache, results) = multi_start_nelder_mead(f, &bounds, 5, 500, 1e-8, 42).unwrap();
assert!((best.x_best[0] - 2.0).abs() < 1e-3);
assert!((best.x_best[1] - 3.0).abs() < 1e-3);
assert!(best.f_best < 1e-5);
assert_eq!(results.len(), 5);
assert!(cache.len() > 5); }
#[test]
fn test_multi_start_rosenbrock() {
let f =
|x: &[f64]| (1.0 - x[0]).mul_add(1.0 - x[0], 100.0 * x[0].mul_add(-x[0], x[1]).powi(2));
let bounds = vec![(-5.0, 5.0), (-5.0, 5.0)];
let (best, cache, _) = multi_start_nelder_mead(f, &bounds, 10, 2000, 1e-8, 42).unwrap();
assert!((best.x_best[0] - 1.0).abs() < 0.1);
assert!((best.x_best[1] - 1.0).abs() < 0.1);
assert!(best.f_best < 0.01);
assert!(cache.len() > 100); }
#[test]
fn test_multi_start_rastrigin() {
let rastrigin = |x: &[f64]| {
let n = x.len() as f64;
10.0f64.mul_add(
n,
x.iter()
.map(|&xi| xi.mul_add(xi, -(10.0 * (2.0 * std::f64::consts::PI * xi).cos())))
.sum::<f64>(),
)
};
let bounds = vec![(-5.12, 5.12), (-5.12, 5.12)];
let (best, cache, results) =
multi_start_nelder_mead(rastrigin, &bounds, 16, 500, 1e-8, 42).unwrap();
assert!(best.f_best < 5.0); assert_eq!(results.len(), 16);
assert!(cache.len() > 100);
}
#[test]
fn test_multi_start_captures_all_evals() {
let f = |x: &[f64]| x[0].powi(2);
let bounds = vec![(-10.0, 10.0)];
let (_, cache, results) = multi_start_nelder_mead(f, &bounds, 3, 50, 1e-8, 42).unwrap();
let total_individual: usize = results.iter().map(|r| r.n_evals).sum();
assert_eq!(cache.len(), total_individual);
}
#[test]
fn test_multi_start_training_data() {
let f = |x: &[f64]| x[1].mul_add(x[1], x[0].powi(2));
let bounds = vec![(-5.0, 5.0), (-5.0, 5.0)];
let (_, cache, _) = multi_start_nelder_mead(f, &bounds, 5, 100, 1e-8, 42).unwrap();
let (x_data, y_data) = cache.training_data();
assert_eq!(x_data.len(), y_data.len());
assert_eq!(x_data.len(), cache.len());
for (xi, &yi) in x_data.iter().zip(y_data.iter()) {
let expected = xi[1].mul_add(xi[1], xi[0].powi(2));
assert!(
(expected - yi).abs() < 1e-10,
"Inconsistent: f({xi:?}) = {expected} != {yi}"
);
}
}
#[test]
fn test_multi_start_high_dimensional() {
let f = |x: &[f64]| {
x.iter()
.enumerate()
.map(|(i, &xi)| (xi - i as f64).powi(2))
.sum::<f64>()
};
let bounds: Vec<(f64, f64)> = (0..5).map(|_| (-10.0, 10.0)).collect();
let (best, cache, results) =
multi_start_nelder_mead(f, &bounds, 10, 1000, 1e-6, 42).unwrap();
assert!(best.f_best < 1.0);
assert_eq!(results.len(), 10);
assert!(cache.len() > 50);
}
#[test]
fn test_multi_start_errors() {
let f = |x: &[f64]| x[0].powi(2);
let bounds = vec![(-1.0, 1.0)];
assert!(multi_start_nelder_mead(f, &bounds, 0, 100, 1e-8, 42).is_err());
assert!(multi_start_nelder_mead(f, &[], 5, 100, 1e-8, 42).is_err());
}
#[test]
fn test_multi_start_convergence_info() {
let f = |x: &[f64]| (x[0] - 1.0).powi(2);
let bounds = vec![(-10.0, 10.0)];
let (_, _, results) = multi_start_nelder_mead(f, &bounds, 5, 500, 1e-6, 42).unwrap();
let n_converged = results.iter().filter(|r| r.converged).count();
assert!(n_converged > 0, "At least one solver should converge");
}
#[test]
fn test_multi_start_global_vs_local() {
let f = |x: &[f64]| {
let x0 = x[0];
let well1 = (x0 - 1.0).powi(2);
let well2 = (x0 + 3.0).mul_add(x0 + 3.0, -1.0);
well1.min(well2)
};
let bounds = vec![(-5.0, 5.0)];
let (best, _, _) = multi_start_nelder_mead(f, &bounds, 10, 500, 1e-8, 42).unwrap();
assert!(best.f_best < 0.0, "Should find the deeper well (f < 0)");
}
}