Nelder-Mead on Rosenbrock
The problem
Rosenbrock's function in two dimensions:
f(x₁, x₂) = 100 (x₂ − x₁²)² + (x₁ − 1)²
Its minimum is 0, at (1, 1). Rosenbrock (1960) started his searches from (−1.2, 1), where f is 24.2, and this example starts there too. The search is limited to x₁ in [−2, 2] and x₂ in [−1, 3], the region where the plot is drawn; the bounds never come into play.
What makes it hard
The minimum lies at the end of a narrow valley along the parabola x₂ = x₁². From (−1.2, 1), the way to (1, 1) goes around the bend of the valley: first down and to the right, then up. Along the floor f falls slowly, while across it f rises fast, so a method has to keep turning to stay inside. A method that only compares values, without a gradient to point down the slope, has to work out the direction from the points it tries.
Representation
A Real genome of 2 genes, x₁ in [−2, 2] and x₂ in [−1, 3]. The fitness is f, to minimize:
genoxide's problems::Rosenbrock in 2 dimensions, used here with this smaller box.
Algorithm
NelderMead: the simplex method of Nelder and Mead (1965), as Lagarias, Reeds, Wright and Wright
(1998) state it precisely. In two dimensions the simplex is a triangle. Each iteration takes its
worst vertex and tries the point opposite it, through the midpoint of the other two (the
reflection):
- if that point is better than the best vertex, a point twice as far out (the expansion);
- if it's no better than the second worst, a point between the midpoint and the better of the reflection and the worst vertex (a contraction);
- if even the contraction isn't better, the whole triangle shrinks towards its best vertex.
The accepted point replaces the worst vertex. The triangle stretches along the valley when steps succeed, and contracts across it when they fail, so it turns with the bend without any derivative. The coefficients are Gao and Han's (2012), which in two dimensions are the standard ones: 1 for the reflection, 2 for the expansion, 1/2 for contractions and shrinks.
The first triangle is the start (−1.2, 1) and two copies moved by 0.1 of each gene's range: (−0.8,
1) and (−1.2, 1.4). The run has converged when every vertex is within 1e-9 of that first step
(1e-10 of the range) of the best vertex in each gene; the engine then stops with
StopReason::Converged.
A round is one batch of evaluations: one trial point, or the two vertices of a shrink. Then the same run again with speculative asks: each iteration evaluates the reflection, the expansion and both contractions in one round, so that a parallel engine can evaluate them at once.
Output
A row every 20 rounds and the last: the evaluations, the best value, and the size of the triangle
(the largest difference between a vertex and the best one in a gene, as a fraction of its range).
The last line is the speculative run. In Python, run evaluates the function in Rust, so both
versions print the same.
The best value falls slowly at first, while the triangle travels along the valley, then fast once it's at the minimum: from round 120 on, each 20 rounds gain about two or three digits. The size grows again around round 80, when the triangle stretches along the straighter part of the valley.
The project page plays this run back, with the triangle drawn on the contour of the function.
Good results
The minimum is 0 at (1, 1). The run converges after 234 evaluations, at (1, 1) to 10 decimal places, with f = 1.7e-20. Speculative asks take the same triangles to the same end in 126 rounds instead of 231, for 507 evaluations: worth it only when a round of 4 points in parallel costs about as much as one.
From 1,000 random starts in the box, every run converges with f below 1e-12, the worst at 8.9e-20.
Known optimum: 0 (at (1, 1))
Source: examples/nelder_mead
Interactive run: tachsin.gr/projects/genoxide/examples/nelder-mead
cargo run --release --example nelder_mead
//! Nelder-Mead: minimize Rosenbrock's function in two dimensions from the classic start
//! (−1.2, 1), with the simplex method, to its minimum at (1, 1).
//!
//! The simplex is a triangle that reflects, expands, contracts and shrinks down the curved valley
//! of the function. The run stops when the triangle has collapsed on the minimum. Then the same
//! run with speculative asks: the same triangles in fewer rounds of evaluations.
//!
//! With `GENOXIDE_TRACE=<file>`, it also writes a trace of its run for the plot on the example's
//! page, with `trace.rs`.
//!
//! ```text
//! cargo run --release --example nelder_mead
//! ```
mod trace;
use genoxide::observer::Snapshot;
use genoxide::prelude::*;
use genoxide::problems::Rosenbrock;
// a row of the table every this many rounds
const EVERY: u64 = 20;
fn main() -> Result<()> {
let real = Real::new([-2.0..=2.0, -1.0..=3.0])?;
let nelder_mead = |speculative| {
NelderMead::builder(real.clone())
.initial_genome(Reals::from(vec![-1.2, 1.0]))
.speculative(speculative)
.minimize()
.build()
};
// with GENOXIDE_TRACE=<file>, a trace of the run for the plot on the example's page
let mut trace = trace::Trace::from_env();
let mut rows = Vec::new();
let outcome = Engine::new(nelder_mead(false)?, Rosenbrock::new(2))
.stop_when(Stop::evaluations(10_000))
.on_generation(|snapshot| {
trace.record(snapshot);
rows.push(row(snapshot, &real));
})
.run()?;
println!("Rosenbrock's function in two dimensions, from (-1.2, 1) where f = 24.2");
println!("Nelder-Mead with Gao and Han's coefficients, a first simplex of 0.1 of each range");
println!("round evaluations best value simplex size");
let last = rows.len() - 1;
for (round, row) in rows.iter().enumerate() {
if (round as u64).is_multiple_of(EVERY) || round == last {
println!("{row}");
}
}
let best = outcome.best_genome();
assert_eq!(outcome.stop_reason(), StopReason::Converged);
println!(
"converged after {} rounds and {} evaluations, at ({:.10}, {:.10}), f = {}",
outcome.generations(),
outcome.evaluations(),
best[0],
best[1],
scientific(outcome.best_fitness().score().expect("valid"))
);
let speculative = Engine::new(nelder_mead(true)?, Rosenbrock::new(2))
.stop_when(Stop::evaluations(10_000))
.run()?;
let same = if speculative.best_genome() == best {
"the same end"
} else {
"another end"
};
println!(
"speculative asks: {same} after {} rounds and {} evaluations",
speculative.generations(),
speculative.evaluations()
);
trace.write();
Ok(())
}
// a row of the table: the round, the evaluations, the best value and the simplex size, the
// largest difference between a vertex and the best one in a gene, as a fraction of its range
fn row(snapshot: &Snapshot<'_, Reals>, real: &Real) -> String {
let progress = snapshot.progress();
let vertices = snapshot.population().as_slice();
let best = vertices[0].genome();
let mut size = 0.0f64;
for vertex in &vertices[1..] {
for ((x, b), range) in vertex.genome().iter().zip(best.iter()).zip(real.bounds()) {
size = size.max((x - b).abs() / (range.end() - range.start()));
}
}
let value = progress.best().and_then(Fitness::score).expect("valid");
format!(
"{:>5} {:>11} {:>10} {:>12}",
progress.generation(),
progress.evaluations(),
scientific(value),
scientific(size)
)
}
// two significant digits, e.g. 1.2e-7
fn scientific(value: f64) -> String {
format!("{value:.1e}")
}
python examples/nelder_mead/main.py
"""Nelder-Mead: minimize Rosenbrock's function in two dimensions from the classic start (-1.2, 1),
with the simplex method, to its minimum at (1, 1).
The simplex is a triangle that reflects, expands, contracts and shrinks down the curved valley of
the function. The run stops when the triangle has collapsed on the minimum. Then the same run
with speculative asks: the same triangles in fewer rounds of evaluations.
With ``GENOXIDE_TRACE=<file>``, it also writes a trace of its run for the plot on the example's
page, with trace.py.
python examples/nelder_mead/main.py
"""
import numpy as np
import genoxide as gx
from trace import Trace
# a row of the table every this many rounds
EVERY = 20
BOUNDS = [(-2.0, 2.0), (-1.0, 3.0)]
def scientific(value):
"""Two significant digits, e.g. 1.2e-7."""
mantissa, exponent = f"{value:.1e}".split("e")
return f"{mantissa}e{int(exponent)}"
def nelder_mead(speculative):
return gx.NelderMead(
gx.Real(BOUNDS),
initial_genome=[-1.2, 1.0],
speculative=speculative,
objective="minimize",
)
def row(progress):
"""A row of the table: the round, the evaluations, the best value and the simplex size, the
largest difference between a vertex and the best one in a gene, as a fraction of its range."""
vertices = progress.population
widths = np.array([high - low for low, high in BOUNDS])
size = float(np.max(np.abs(vertices[1:] - vertices[0]) / widths))
return (
f"{progress.generation:>5} {progress.evaluations:>11} "
f"{scientific(progress.best_fitness):>10} {scientific(size):>12}"
)
# with GENOXIDE_TRACE=<file>, a trace of the run for the plot on the example's page
trace = Trace()
rows = []
def on_generation(progress):
trace.record(progress)
rows.append(row(progress))
rosenbrock = gx.problems.Rosenbrock(2)
result = nelder_mead(False).run(rosenbrock, evaluations=10_000, on_generation=on_generation)
print("Rosenbrock's function in two dimensions, from (-1.2, 1) where f = 24.2")
print("Nelder-Mead with Gao and Han's coefficients, a first simplex of 0.1 of each range")
print("round evaluations best value simplex size")
for round_, line in enumerate(rows):
if round_ % EVERY == 0 or round_ == len(rows) - 1:
print(line)
assert result.stop_reason == "converged"
best = result.best_genome
print(
f"converged after {result.generations} rounds and {result.evaluations} evaluations, "
f"at ({best[0]:.10f}, {best[1]:.10f}), f = {scientific(result.best_fitness)}"
)
speculative = nelder_mead(True).run(rosenbrock, evaluations=10_000)
same = "the same end" if np.array_equal(speculative.best_genome, best) else "another end"
print(
f"speculative asks: {same} after {speculative.generations} rounds and "
f"{speculative.evaluations} evaluations"
)
trace.write()
What it prints, from a seeded run:
Rosenbrock's function in two dimensions, from (-1.2, 1) where f = 24.2
Nelder-Mead with Gao and Han's coefficients, a first simplex of 0.1 of each range
round evaluations best value simplex size
0 3 5.0e0 1.0e-1
20 23 2.3e0 8.7e-2
40 43 1.1e0 3.1e-2
60 63 5.5e-1 1.2e-2
80 83 7.4e-2 4.6e-2
100 103 6.1e-3 2.4e-2
120 123 6.5e-5 5.0e-3
140 143 5.7e-8 4.6e-4
160 163 3.8e-10 2.1e-5
180 183 7.2e-13 8.4e-7
200 203 1.3e-15 1.9e-8
220 223 1.2e-18 1.0e-9
231 234 1.7e-20 8.3e-11
converged after 231 rounds and 234 evaluations, at (1.0000000000, 1.0000000000), f = 1.7e-20
speculative asks: the same end after 126 rounds and 507 evaluations