L-BFGS-B on Rosenbrock in 100 dimensions
The problem
Rosenbrock's function, chained over 100 variables:
f(x) = Σᵢ₌₁⁹⁹ 100 (xᵢ₊₁ − xᵢ²)² + (xᵢ − 1)²
Its minimum is 0, at (1, …, 1). Both runs start from the classic start, (−1.2, 1) repeated, where f = 24,926, and stop once f ≤ 1e-10.
What makes it hard
Each term couples a variable to the next, so the valley of the two-dimensional function becomes a curved valley in 100 dimensions: a step that improves one pair spoils the next. The way to the minimum bends at every variable, and a method has to learn that curvature as it goes. Here a gradient-based method needs the gradient, a vector of 100 derivatives, at every point it tries.
Representation
A Real genome of 100 genes in [−30, 30], the box of genoxide's problems::Rosenbrock, which
also gives the analytic gradient. The box never comes into play.
Algorithm
Lbfgsb: L-BFGS-B (Byrd, Lu, Nocedal and Zhu, 1995), with the default memory of 10 correction
pairs. Each iteration models the function by its gradient and the curvature of the last 10 steps
(a limited-memory BFGS matrix), steps to the model's minimum within the box, and searches along
that step with the Moré-Thuente line search, which tries the full step first. Near the minimum,
the full step is accepted at nearly every iteration.
The gradient comes from one of two sources:
- Analytic (
Gradients::Auto, as the problem supplies it): the function computes its gradient with its value, one evaluation per point. - Forward differences (
Gradients::Forward): 100 more points per point, each moving one gene by about 1.5e-8 of its value, evaluated in the same round. Their gradient is accurate to about 7 digits.
The tolerances are turned off (gradient_tolerance(0.0), function_tolerance(0.0)), so each
run goes on until Stop::target(1e-10).
Output
A row every 50 rounds and at the end of each run: the evaluations so far and the best value, for
each source of the gradient. A round is one point the line search tries, with its gradient. Then
each run's iterations and evaluations, and the ratio of the evaluations. In Python, run
evaluates the problem in Rust, gradient included, so both versions print the same.
Round for round the two runs are nearly the same: forward differences change the gradient in its eighth digit, and the path differs only near the end. The cost is not: 101 evaluations per round against 1.
The project page plays the runs back: the best value and the evaluations per round, for both sources of the gradient.
Good results
The minimum is 0 at (1, …, 1). With the analytic gradient, the run reaches f = 3.0e-11 in 520 iterations and 613 evaluations. With forward differences, it reaches f = 9.9e-11 in 523 iterations and 61,206 evaluations: 100 times as many, of which 60,600 compute the gradient.
Supply the gradient whenever there's one: for n genes, forward differences cost n times the evaluations. They cost nothing to set up, so they suit a function without a formula for its gradient, a few genes, or a fast function.
Known optimum: 0 (at (1, …, 1))
Source: examples/lbfgsb
Interactive run: tachsin.gr/projects/genoxide/examples/lbfgsb
cargo run --release --example lbfgsb
//! L-BFGS-B: minimize Rosenbrock's function in 100 dimensions from the classic start
//! (−1.2, 1, −1.2, 1, …) to f ≤ 1e-10, once with its analytic gradient and once with forward
//! differences, to compare their cost.
//!
//! Both runs take about the same steps: the gradient is the same to about 7 digits. The analytic
//! gradient costs one evaluation per trial point, forward differences 101.
//!
//! With `GENOXIDE_TRACE=<file>`, it also writes a trace of its runs for the plot on the example's
//! page, with `trace.rs`.
//!
//! ```text
//! cargo run --release --example lbfgsb
//! ```
mod trace;
use genoxide::gradient::Gradients;
use genoxide::prelude::*;
use genoxide::problems::{Problem, Rosenbrock};
const N: usize = 100;
// a row of the table every this many rounds
const EVERY: u64 = 50;
// a round of a run: its evaluations and best value
#[derive(Clone, Copy)]
struct Round {
evaluations: u64,
best: f64,
}
// the rounds of a run to f ≤ 1e-10, its outcome and its iterations
fn run(gradients: Gradients) -> Result<(Vec<Round>, Outcome<Reals>, u64)> {
let problem = Rosenbrock::new(N);
let start: Reals = (0..N)
.map(|i| if i % 2 == 0 { -1.2 } else { 1.0 })
.collect();
let lbfgsb = Lbfgsb::builder(problem.representation())
.initial_genome(start)
.gradients(gradients)
.gradient_tolerance(0.0)
.function_tolerance(0.0)
.minimize()
.build()?;
let mut rounds = Vec::new();
let mut engine = Engine::new(lbfgsb, problem)
.stop_when(Stop::target(1e-10).or(Stop::evaluations(200_000)))
.on_generation(|snapshot| {
let progress = snapshot.progress();
rounds.push(Round {
evaluations: progress.evaluations(),
best: progress.best().and_then(Fitness::score).expect("valid"),
});
});
let outcome = engine.run()?;
let iterations = engine.algorithm().iterations();
drop(engine);
Ok((rounds, outcome, iterations))
}
fn main() -> Result<()> {
let start: Reals = (0..N)
.map(|i| if i % 2 == 0 { -1.2 } else { 1.0 })
.collect();
let value = Rosenbrock::new(N).evaluate(&start);
let (analytic, analytic_outcome, analytic_iterations) = run(Gradients::Auto)?;
let (forward, forward_outcome, forward_iterations) = run(Gradients::Forward { step: None })?;
println!(
"Rosenbrock's function in {N} dimensions, from (-1.2, 1, -1.2, 1, ...) where f = {value:.0}"
);
println!(
"L-BFGS-B with 10 pairs to f <= 1e-10: the analytic gradient, and forward differences"
);
println!(" analytic gradient forward differences");
println!("round evaluations best value evaluations best value");
let rounds = analytic.len().max(forward.len());
let cell = |rounds: &[Round], round: usize| match rounds.get(round) {
Some(row) => format!("{:>11} {:>10}", row.evaluations, scientific(row.best)),
None => format!("{:>11} {:>10}", "", ""),
};
for round in 0..rounds {
let last = round + 1 == analytic.len() || round + 1 == forward.len();
if (round as u64).is_multiple_of(EVERY) || last {
println!(
"{round:>5} {} {}",
cell(&analytic, round),
cell(&forward, round)
);
}
}
for (name, outcome, iterations) in [
("analytic gradient", &analytic_outcome, analytic_iterations),
("forward differences", &forward_outcome, forward_iterations),
] {
assert_eq!(outcome.stop_reason(), StopReason::Target);
println!(
"{name}: f = {} after {iterations} iterations and {} evaluations",
scientific(outcome.best_fitness().score().expect("valid")),
outcome.evaluations()
);
}
println!(
"forward differences took {:.0} times the evaluations",
forward_outcome.evaluations() as f64 / analytic_outcome.evaluations() as f64
);
// with GENOXIDE_TRACE=<file>, a trace of the runs for the plot on the example's page
let analytic: Vec<(u64, f64)> = analytic.iter().map(|r| (r.evaluations, r.best)).collect();
let forward: Vec<(u64, f64)> = forward.iter().map(|r| (r.evaluations, r.best)).collect();
trace::write_runs(&analytic, &forward);
Ok(())
}
// two significant digits, e.g. 1.2e-7
fn scientific(value: f64) -> String {
format!("{value:.1e}")
}
python examples/lbfgsb/main.py
"""L-BFGS-B: minimize Rosenbrock's function in 100 dimensions from the classic start
(-1.2, 1, -1.2, 1, ...) to f <= 1e-10, once with its analytic gradient and once with forward
differences, to compare their cost.
Both runs take about the same steps: the gradient is the same to about 7 digits. The analytic
gradient costs one evaluation per trial point, forward differences 101.
With ``GENOXIDE_TRACE=<file>``, it also writes a trace of its runs for the plot on the example's
page, with trace.py.
python examples/lbfgsb/main.py
"""
import genoxide as gx
import trace
N = 100
# a row of the table every this many rounds
EVERY = 50
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 run(gradients):
"""The rounds of a run to f <= 1e-10, as (evaluations, best value), its result and its
iterations."""
problem = gx.problems.Rosenbrock(N)
lbfgsb = gx.Lbfgsb(
problem.genome,
initial_genome=[-1.2, 1.0] * (N // 2),
gradients=gradients,
gradient_tolerance=0.0,
function_tolerance=0.0,
objective="minimize",
)
rounds = []
iterations = []
def on_generation(progress):
rounds.append((progress.evaluations, progress.best_fitness))
def control(algorithm, progress):
iterations.append(algorithm.iterations)
result = lbfgsb.run(
problem,
target=1e-10,
evaluations=200_000,
on_generation=on_generation,
control=control,
)
return rounds, result, iterations[-1]
value = gx.problems.Rosenbrock(N)([-1.2, 1.0] * (N // 2))
analytic, analytic_result, analytic_iterations = run("auto")
forward, forward_result, forward_iterations = run("forward")
print(
f"Rosenbrock's function in {N} dimensions, from (-1.2, 1, -1.2, 1, ...) where f = {value:.0f}"
)
print("L-BFGS-B with 10 pairs to f <= 1e-10: the analytic gradient, and forward differences")
print(" analytic gradient forward differences")
print("round evaluations best value evaluations best value")
def cell(rounds, round_):
if round_ < len(rounds):
evaluations, best = rounds[round_]
return f"{evaluations:>11} {scientific(best):>10}"
return f"{'':>11} {'':>10}"
for round_ in range(max(len(analytic), len(forward))):
last = round_ + 1 in (len(analytic), len(forward))
if round_ % EVERY == 0 or last:
print(f"{round_:>5} {cell(analytic, round_)} {cell(forward, round_)}")
for name, result, iterations in [
("analytic gradient", analytic_result, analytic_iterations),
("forward differences", forward_result, forward_iterations),
]:
assert result.stop_reason == "target"
print(
f"{name}: f = {scientific(result.best_fitness)} after {iterations} iterations and "
f"{result.evaluations} evaluations"
)
print(
"forward differences took "
f"{forward_result.evaluations / analytic_result.evaluations:.0f} times the evaluations"
)
# with GENOXIDE_TRACE=<file>, a trace of the runs for the plot on the example's page
trace.write_runs(analytic, forward)
What it prints, from a seeded run:
Rosenbrock's function in 100 dimensions, from (-1.2, 1, -1.2, 1, ...) where f = 24926
L-BFGS-B with 10 pairs to f <= 1e-10: the analytic gradient, and forward differences
analytic gradient forward differences
round evaluations best value evaluations best value
0 1 2.5e4 101 2.5e4
50 51 9.3e1 5151 9.3e1
100 101 8.3e1 10201 8.3e1
150 151 7.4e1 15251 7.4e1
200 201 6.5e1 20301 6.5e1
250 251 5.7e1 25351 5.7e1
300 301 4.8e1 30401 4.8e1
350 351 4.0e1 35451 3.9e1
400 401 3.2e1 40501 3.0e1
450 451 2.3e1 45551 2.1e1
500 501 1.4e1 50601 1.3e1
550 551 5.7e0 55651 3.5e0
600 601 3.3e-5 60701 5.3e-9
605 606 1.9e-7 61206 9.9e-11
612 613 3.0e-11
analytic gradient: f = 3.0e-11 after 520 iterations and 613 evaluations
forward differences: f = 9.9e-11 after 523 iterations and 61206 evaluations
forward differences took 100 times the evaluations