L-BFGS-B on a minimum at the bound
The problem
Rosenbrock's function in two dimensions,
f(x₁, x₂) = 100 (x₂ − x₁²)² + (x₁ − 1)²,
in the box x₁ ∈ [−2, 0.5], x₂ ∈ [−1, 3], from the classic start (−1.2, 1). The unconstrained minimum, (1, 1), is outside the box: the bound x₁ ≤ 0.5 cuts the valley before its end.
The minimum in the box is on that bound. With x₁ = 0.5, f = 100 (x₂ − 0.25)² + 0.25 is least at x₂ = 0.25, so the minimum is f = 0.25 at (0.5, 0.25). There the gradient is (−1, 0): f falls only by growing x₁, beyond the bound. That is the optimality condition of a bound-constrained problem (a gradient that points out of the box, or is 0, in every gene), so (0.5, 0.25) is the minimum.
What makes it hard
The minimum isn't a point where the gradient is 0, so a method can't find it by driving the gradient to 0; it has to learn which bounds hold at the minimum (the active set) and land on them. A method that only steps in the open box approaches the bound ever more closely without reaching it.
Representation
A Real genome of 2 genes with the bounds of the box. The fitness is f, to minimize: genoxide's
problems::Rosenbrock in 2 dimensions, with its analytic gradient, in this box.
Algorithm
Lbfgsb with its defaults. Each iteration of L-BFGS-B (Byrd, Lu, Nocedal and Zhu, 1995) models
f by a quadratic and finds the first minimum of that model along the path of steepest descent,
bent at the bounds: the generalized Cauchy point. The genes that path holds at a bound are the
active set; the step then minimizes the model over the other genes, projected back into the box
(Morales and Nocedal, 2011), and a line search along it never leaves the box. Once x₁ reaches 0.5,
it stays there: the path of steepest descent holds it at the bound, and the steps move x₂ alone.
A run has converged when the projected gradient, the step of steepest descent cut back at the bounds, is at most 1e-5 in every gene: at a minimum on a bound, the component that points out of the box doesn't count.
Then, for contrast, Nelder-Mead from the same start in the same box: it mirrors trial points that leave the box back into it.
Output
The current point after each round: the evaluations, x₁, x₂, f, and the largest component of the
projected gradient. A round is one point the line search tries. Then where each method ended. In
Python, run evaluates the function in Rust, so both versions print the same.
The first rounds follow the valley up and to the right, as on the full function. At round 26, x₁ reaches 0.5 exactly and stays there; two rounds later x₂ is 0.25 and the projected gradient is 0.
The project page plays the run back: the points the search stood at, on the contour of the function in the box.
Good results
The minimum in the box is 0.25 at (0.5, 0.25). L-BFGS-B ends exactly there, (0.5, 0.25) with f = 0.25 and a projected gradient of 0, after 29 evaluations, and stops as converged.
Nelder-Mead ends at (0.49999999999999956, 0.24999999980867693), f = 0.25000000000000044, after 257 evaluations: close, but on the inside of the bound, and nine times the evaluations without a gradient to use.
Known optimum: 0.25 (at (0.5, 0.25), on the bound x₁ = 0.5)
Source: examples/lbfgsb_bounds
Interactive run: tachsin.gr/projects/genoxide/examples/lbfgsb-bounds
cargo run --release --example lbfgsb_bounds
//! L-BFGS-B with a bound that cuts the valley: minimize Rosenbrock's function in the box
//! [−2, 0.5] × [−1, 3], whose minimum (1, 1) lies outside it. The minimum in the box is on its
//! edge, at (0.5, 0.25), where f = 0.25, and L-BFGS-B lands on it exactly.
//!
//! Then Nelder-Mead in the same box, for contrast: it approaches the bound without reaching it.
//!
//! 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 lbfgsb_bounds
//! ```
mod trace;
use genoxide::prelude::*;
use genoxide::problems::Rosenbrock;
fn main() -> Result<()> {
let real = Real::new([-2.0..=0.5, -1.0..=3.0])?;
let start = Reals::from(vec![-1.2, 1.0]);
let lbfgsb = Lbfgsb::builder(real.clone())
.initial_genome(start.clone())
.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 mut criterion = None;
let mut engine = Engine::new(lbfgsb, Rosenbrock::new(2))
.stop_when(Stop::evaluations(1_000))
.on_generation(|snapshot| trace.record(snapshot))
.control(|lbfgsb: &mut Lbfgsb, progress| {
let x = lbfgsb.population()[0].genome();
let value = lbfgsb.population()[0].fitness().and_then(Fitness::score);
rows.push(format!(
"{:>5} {:>11} {:>9.6} {:>9.6} {:>9.6} {:>18}",
progress.generation(),
progress.evaluations(),
x[0],
x[1],
value.expect("valid"),
scientific(lbfgsb.projected_gradient())
));
criterion = lbfgsb.converged();
Ok(())
});
let outcome = engine.run()?;
drop(engine);
println!(
"Rosenbrock's function in [-2, 0.5] x [-1, 3], from (-1.2, 1); its minimum (1, 1) is outside"
);
println!("L-BFGS-B, the current point after each round");
println!("round evaluations x1 x2 f projected gradient");
for row in &rows {
println!("{row}");
}
assert_eq!(outcome.stop_reason(), StopReason::Converged);
assert_eq!(criterion, Some(lbfgsb::Criterion::ProjectedGradient));
let x = outcome.best_genome();
// the gradient at the end: −400 x₁ (x₂ − x₁²) − 2 (1 − x₁), and 200 (x₂ − x₁²)
let valley = x[1] - x[0] * x[0];
let gradient = [-400.0 * x[0] * valley + 2.0 * (x[0] - 1.0), 200.0 * valley];
println!(
"L-BFGS-B: converged at ({:?}, {:?}), f = {:?}, after {} evaluations",
x[0],
x[1],
outcome.best_fitness().score().expect("valid"),
outcome.evaluations()
);
println!(
"the gradient there is ({:?}, {:?}): f falls only beyond the bound x1 = 0.5",
gradient[0], gradient[1]
);
let nelder_mead = NelderMead::builder(real)
.initial_genome(start)
.minimize()
.build()?;
let contrast = Engine::new(nelder_mead, Rosenbrock::new(2))
.stop_when(Stop::evaluations(10_000))
.run()?;
let y = contrast.best_genome();
println!(
"Nelder-Mead, for contrast: ({:?}, {:?}), f = {:?}, after {} evaluations",
y[0],
y[1],
contrast.best_fitness().score().expect("valid"),
contrast.evaluations()
);
trace.write();
Ok(())
}
// two significant digits, e.g. 1.2e-7
fn scientific(value: f64) -> String {
format!("{value:.1e}")
}
python examples/lbfgsb_bounds/main.py
"""L-BFGS-B with a bound that cuts the valley: minimize Rosenbrock's function in the box
[-2, 0.5] x [-1, 3], whose minimum (1, 1) lies outside it. The minimum in the box is on its edge,
at (0.5, 0.25), where f = 0.25, and L-BFGS-B lands on it exactly.
Then Nelder-Mead in the same box, for contrast: it approaches the bound without reaching it.
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/lbfgsb_bounds/main.py
"""
import genoxide as gx
from trace import Trace
BOUNDS = [(-2.0, 0.5), (-1.0, 3.0)]
START = [-1.2, 1.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)}"
# with GENOXIDE_TRACE=<file>, a trace of the run for the plot on the example's page
trace = Trace()
rows = []
criteria = []
def control(lbfgsb, progress):
x = progress.population[0]
rows.append(
f"{progress.generation:>5} {progress.evaluations:>11} {x[0]:>9.6f} {x[1]:>9.6f} "
f"{progress.scores[0]:>9.6f} {scientific(lbfgsb.projected_gradient):>18}"
)
criteria.append(lbfgsb.converged)
rosenbrock = gx.problems.Rosenbrock(2)
lbfgsb = gx.Lbfgsb(gx.Real(BOUNDS), initial_genome=START, objective="minimize")
result = lbfgsb.run(rosenbrock, evaluations=1_000, on_generation=trace.record, control=control)
print("Rosenbrock's function in [-2, 0.5] x [-1, 3], from (-1.2, 1); its minimum (1, 1) is outside")
print("L-BFGS-B, the current point after each round")
print("round evaluations x1 x2 f projected gradient")
for row in rows:
print(row)
assert result.stop_reason == "converged"
assert criteria[-1] == "projected_gradient"
x = [float(gene) for gene in result.best_genome]
# the gradient at the end: -400 x1 (x2 - x1^2) - 2 (1 - x1), and 200 (x2 - x1^2)
valley = x[1] - x[0] * x[0]
gradient = [-400.0 * x[0] * valley + 2.0 * (x[0] - 1.0), 200.0 * valley]
print(
f"L-BFGS-B: converged at ({x[0]!r}, {x[1]!r}), f = {result.best_fitness!r}, "
f"after {result.evaluations} evaluations"
)
print(
f"the gradient there is ({gradient[0]!r}, {gradient[1]!r}): "
"f falls only beyond the bound x1 = 0.5"
)
nelder_mead = gx.NelderMead(gx.Real(BOUNDS), initial_genome=START, objective="minimize")
contrast = nelder_mead.run(rosenbrock, evaluations=10_000)
y = [float(gene) for gene in contrast.best_genome]
print(
f"Nelder-Mead, for contrast: ({y[0]!r}, {y[1]!r}), f = {contrast.best_fitness!r}, "
f"after {contrast.evaluations} evaluations"
)
trace.write()
What it prints, from a seeded run:
Rosenbrock's function in [-2, 0.5] x [-1, 3], from (-1.2, 1); its minimum (1, 1) is outside
L-BFGS-B, the current point after each round
round evaluations x1 x2 f projected gradient
0 1 -1.200000 1.000000 24.200000 2.0e0
1 2 -1.200000 1.000000 24.200000 2.0e0
2 3 -1.068165 1.155100 4.297256 2.2e0
3 4 -1.069587 1.150927 4.287965 1.4e0
4 5 -1.069176 1.147217 4.283154 1.6e0
5 6 -1.064751 1.130668 4.264113 1.6e0
6 7 -1.050615 1.090760 4.222010 1.9e0
7 8 -1.010282 0.991250 4.127783 2.0e0
8 9 -0.947934 0.853665 3.996166 2.1e0
9 10 -0.871791 0.708197 3.772158 2.3e0
10 11 -0.750285 0.519042 3.256083 2.5e0
11 12 -0.643758 0.404061 2.712679 2.1e0
12 13 -0.643758 0.404061 2.712679 2.1e0
13 14 -0.549242 0.269766 2.501914 2.7e0
14 15 -0.382191 0.085933 2.272099 2.9e0
15 16 -0.357501 0.115638 1.857615 2.4e0
16 17 -0.202458 0.013388 1.522091 3.0e0
17 18 -0.054524 -0.045690 1.348826 3.0e0
18 19 -0.001524 -0.002038 1.003466 5.0e-1
19 20 0.171300 -0.010348 0.844285 3.0e0
20 21 0.151224 0.014616 0.727231 1.7e0
21 22 0.245888 0.051377 0.576937 1.8e0
22 23 0.245888 0.051377 0.576937 1.8e0
23 24 0.328856 0.087658 0.492410 2.9e0
24 25 0.434179 0.162541 0.387599 2.8e0
25 26 0.495001 0.244737 0.255032 5.8e-2
26 27 0.500000 0.249614 0.250015 7.7e-2
27 28 0.500000 0.250040 0.250000 8.0e-3
28 29 0.500000 0.250000 0.250000 0.0e0
L-BFGS-B: converged at (0.5, 0.25), f = 0.25, after 29 evaluations
the gradient there is (-1.0, 0.0): f falls only beyond the bound x1 = 0.5
Nelder-Mead, for contrast: (0.49999999999999956, 0.24999999980867693), f = 0.25000000000000044, after 257 evaluations