Quasi-Newton Method (BFGS)

This documentation was generated with the assistance of AI. Please report any inaccuracies.

Quasi-Newton (variable metric) methods share the same goal as conjugate gradient methods — accumulate information from successive line minimizations so that, for a quadratic form, of them reach the exact minimum — but store and update that information differently: as a full approximation to the inverse Hessian, rather than an set of vectors. This package implements the Broyden-Fletcher-Goldfarb- Shanno (BFGS) variant, described in Press et al., 2007, Section 10.9 (page 521), as QuasiNewtonMultiOptimizer in the com.irurueta.numerical.optimization package.

From Newton’s method to "quasi" Newton

Newton’s method for finding a zero of the gradient uses the local quadratic approximation \(f(\mathbf{x}) \approx f(\mathbf{x}_i) + (\mathbf{x}-\mathbf{x}_i)^\top\nabla f(\mathbf{x}_i) + \tfrac{1}{2}(\mathbf{x}-\mathbf{x}_i)^\top A (\mathbf{x}-\mathbf{x}_i)\) to jump directly to where the gradient should vanish:

The true Hessian is not known, so quasi-Newton methods instead build up a sequence of matrices converging toward — ideally within iterations, as for a true quadratic form. This turns out to be not just a practical necessity but often genuinely better than using the real Hessian: far from the minimum, need not be positive-definite, and taking the literal Newton step could move uphill. Starting as the identity matrix (positive-definite and symmetric) and updating it in a way that provably preserves both properties guarantees the method always has a downhill direction available, and recovers Newton’s quadratic convergence once close enough to the minimum for to have converged.

The BFGS update

Writing and , the update is built to satisfy the secant condition — requiring the new approximation to behave, along the step just taken, exactly like would. The DFP formula (Davidon-Fletcher-Powell, an earlier variant) is:

where is the outer product. BFGS — empirically the more robust of the two in practice, and the variant this package implements — adds one further rank-one correction term:

The update is skipped on any iteration where is not comfortably positive — guarding against roundoff pushing toward becoming singular or indefinite.

An approximate line search

Unlike Powell’s method and conjugate gradient, the quasi-Newton method does not need an accurate 1D line minimization along the Newton direction — only enough progress to guarantee the function actually decreases. This package’s internal line search takes the full Newton step whenever it can, and backtracks (via a quadratic/cubic fit to the step already tried) whenever that step overshoots, is rejected by an Armijo-style sufficient-decrease condition, or exceeds a maximum allowed step length.

flowchart TD A["H0 = identity; g = gradient(p)"] --> B["Newton direction: xi = -H * g"] B --> C["Approximate line search along xi:\ntake full step if it decreases f enough, else backtrack"] C --> D{"step size or gradient norm\nbelow tolerance?"} D -->|"yes"| E["Done: return p"] D -->|"no"| F["Compute step s and gradient change dg;\nskip update if s . dg is not safely positive"] F --> G["Apply the BFGS update to H"] G --> B

Library implementation

QuasiNewtonMultiOptimizer extends MultiOptimizer directly (its line search is the internal backtracking routine above, not the shared LineMultiOptimizer/DerivativeLineMultiOptimizer machinery used by Powell’s Method and Conjugate Gradient Methods):

  • setGradientListener(…​) — supplies ; as with Conjugate Gradient Methods, wrapping a numerical GradientEstimator here works just as well as an analytic gradient.

  • setStartPoint(double[]) / getStartPoint() — the initial point.

  • getTolerance() / setTolerance(double) — the convergence criterion on the (scaled) gradient norm; default 3e-8.

  • getIterations() — the number of iterations used, after minimize() completes.

Up to ITMAX = 200 iterations are attempted; convergence is additionally checked on the step size between iterations (TOLX), independent of the gradient-norm test.

Press et al., 2007 reports that quasi-Newton methods tend to outperform conjugate gradient whenever the storage for the inverse-Hessian approximation is affordable — and work well even when the gradient itself is only numerically estimated, which is why the authors describe it as an effective first choice whether or not computing an analytic gradient is practical.

Example

final var listener = new MultiDimensionFunctionEvaluatorListener() {
    @Override
    public double evaluate(final double[] point) {
        final var dx = point[0] - 1.0;
        final var dy = point[1] + 2.0;
        return dx * dx + dy * dy;
    }
};
final var gradientListener = new GradientFunctionEvaluatorListener() {
    @Override
    public void evaluateGradient(final double[] params, final double[] result) {
        result[0] = 2.0 * (params[0] - 1.0);
        result[1] = 2.0 * (params[1] + 2.0);
    }
};

final var optimizer = new QuasiNewtonMultiOptimizer(
        listener, gradientListener, new double[]{0.0, 0.0}, 3e-8);
optimizer.minimize();

final var xmin = optimizer.getResult();          // approximately [1.0, -2.0]
final var fmin = optimizer.getEvaluationAtResult(); // approximately 0.0