Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Optimization

The solow-optimize crate provides the unconstrained numerical optimizers that sit underneath Solow's maximum-likelihood estimators, together with the finite-difference derivatives those optimizers and the standard-error machinery depend on. Two solvers are exposed as free functions — newton_stationary, a damped Newton iteration that uses analytic score and Hessian, and minimize_bfgs, a quasi-Newton BFGS minimizer that needs only a gradient — plus approx_fprime and approx_hess for central-difference gradients and Hessians. Every run returns a single OptimizeResult.

This crate is deliberately small relative to the reference's optimizer collection: it ships Newton–Raphson and BFGS with backtracking line search and finite-difference derivatives, but does not (yet) include the full menu of methods such as conjugate gradient, Powell, Nelder–Mead, or L-BFGS-B.

Background

Maximum-likelihood estimation reduces to an unconstrained smooth optimization problem. Writing the log-likelihood as \( \ell(\theta) \), its gradient (the score) and Hessian are

\[ g(\theta) = \nabla \ell(\theta), \qquad H(\theta) = \nabla^2 \ell(\theta). \]

A stationary point of \( \ell \) satisfies \( g(\theta) = 0 \). Both solvers generate a sequence \( \theta_0, \theta_1, \dots \) that drives the gradient toward zero.

Newton–Raphson. The Newton update solves the local quadratic model exactly,

\[ \theta_{k+1} = \theta_k - H(\theta_k)^{-1} g(\theta_k), \]

giving quadratic convergence near the optimum. The displacement \( \Delta_k = H^{-1} g \) is the Newton step, and \( \lVert \Delta_k \rVert \) the Newton decrement. newton_stationary drives the gradient to zero regardless of curvature, so it converges to a local maximum or minimum according to the sign of \( H \); for a concave log-likelihood the stationary point is the MLE. When \( H \) is singular the step is computed from a least-squares (pseudoinverse) solve instead of a direct solve.

To stay globally convergent on ill-scaled problems, the Newton step is damped: the solver takes the largest fraction \( t \in {1, \tfrac12, \tfrac14, \dots} \) of the step for which the gradient norm strictly decreases and stays finite,

\[ \theta_{k+1} = \theta_k - t, H(\theta_k)^{-1} g(\theta_k). \]

Near the optimum the full step \( t = 1 \) is accepted on the first try, so the quadratic convergence of pure Newton is preserved.

Quasi-Newton (BFGS). When the Hessian is unavailable or expensive, BFGS maintains an approximation \( B_k \approx H_k^{-1} \) to the inverse Hessian and forms the search direction \( d_k = -B_k g_k \). With the curvature pair

\[ s_k = \theta_{k+1} - \theta_k, \qquad y_k = g_{k+1} - g_k, \qquad \rho_k = \frac{1}{s_k^\top y_k}, \]

the inverse-Hessian update is

\[ B_{k+1} = (I - \rho_k, s_k y_k^\top), B_k, (I - \rho_k, y_k s_k^\top) + \rho_k, s_k s_k^\top , \]

applied only when the curvature condition \( s_k^\top y_k > 0 \) holds (here, above a small tolerance). The iteration starts from \( B_0 = I \).

Line search. BFGS chooses the step length \( \alpha \) by backtracking until the Armijo sufficient-decrease condition holds,

\[ f(\theta_k + \alpha d_k) \le f(\theta_k) + c,\alpha, g_k^\top d_k, \qquad c = 10^{-4}, \]

starting at \( \alpha = 1 \) and halving (\( \rho = \tfrac12 \)) on each failure. Note that minimize_bfgs minimizes: to maximize a log-likelihood, minimize its negative.

Convergence. A run is declared converged when the gradient norm falls below the tolerance, \( \lVert g(\theta_k) \rVert < \texttt{gtol} \). In addition, newton_stationary accepts a scale-aware test: if the Newton step shrinks to \( \lVert \Delta_k \rVert \le 10^{-12}(1 + \lVert \theta_k \rVert) \) it also declares convergence, which catches well-conditioned MLEs whose raw gradient norm has a floating-point roundoff floor just above gtol.

Numerical derivatives. When analytic derivatives are not at hand, central differences approximate them. With a per-coordinate step \( h_i \),

\[ [\nabla f]_i \approx \frac{f(\theta + h_i e_i) - f(\theta - h_i e_i)}{2 h_i}, \]

and the second derivatives use the standard central stencils. approx_fprime uses \( h_i = 10^{-6}(1 + |\theta_i|) \) and approx_hess uses \( h_i = 10^{-4}(1 + |\theta_i|) \); the off-diagonal Hessian entries are computed with the symmetric four-point formula and the result is symmetrized.

Example

Two short examples: a BFGS minimization of the Rosenbrock function using a finite-difference gradient, and a Newton solve of a smooth objective with analytic derivatives.

BFGS with a finite-difference gradient

#![allow(unused)]
fn main() {
use ndarray::{array, Array1};
use solow_optimize::{approx_fprime, minimize_bfgs};

// Rosenbrock: f(x) = (1 - x0)^2 + 100 (x1 - x0^2)^2, global min at (1, 1).
let f = |x: &Array1<f64>| (1.0 - x[0]).powi(2) + 100.0 * (x[1] - x[0] * x[0]).powi(2);

// Supply the gradient by central differences rather than deriving it by hand.
let grad = |x: &Array1<f64>| approx_fprime(x, f);

let start = array![-1.2, 1.0];
let res = minimize_bfgs(&start, f, grad, 1000, 1e-8).unwrap();

assert!(res.converged);
println!("minimizer = {:?}", res.x);     // close to [1.0, 1.0]
println!("fval      = {:.3e}", res.fval); // close to 0
println!("iters     = {}", res.iters);
println!("grad_norm = {:.3e}", res.grad_norm);
}

The fitted OptimizeResult exposes the located point x, the objective value fval there, the number of iterations iters, the converged flag, and the final grad_norm. For the Rosenbrock start above the solver converges to the valley floor at \( (1, 1) \) with fval near zero.

Newton with analytic score and Hessian

#![allow(unused)]
fn main() {
use ndarray::{array, Array1, Array2};
use solow_optimize::newton_stationary;

// f(x) = (x0 - 3)^2 + 2 (x1 + 1)^2, stationary point (minimum) at (3, -1).
let fgh = |x: &Array1<f64>| {
    let f = (x[0] - 3.0).powi(2) + 2.0 * (x[1] + 1.0).powi(2);
    let g = array![2.0 * (x[0] - 3.0), 4.0 * (x[1] + 1.0)];
    let h = array![[2.0, 0.0], [0.0, 4.0]];
    (f, g, h)
};

let res = newton_stationary(&array![0.0, 0.0], fgh, 50, 1e-10).unwrap();

assert!(res.converged);
println!("solution = {:?}", res.x); // close to [3.0, -1.0]
}

The closure passed to newton_stationary returns the triple (value, gradient, hessian); the solver applies the damped Newton update until the gradient norm (or the Newton step) is small enough. This is exactly the pattern Solow's likelihood-based estimators use internally, swapping in the model's score and information matrix.

Illustrative output. The printed values above describe where each solver lands for these starting points; exact iteration counts and residual norms depend on the platform's floating-point arithmetic.

If you only have the objective, build the gradient and Hessian with approx_fprime and approx_hess and feed them to whichever solver you prefer.

Module reference

Functions

NameDescription
newton_stationaryDamped Newton iteration driving the gradient to zero from a (value, gradient, hessian) closure; falls back to a least-squares solve when the Hessian is singular.
minimize_bfgsBFGS quasi-Newton minimizer with Armijo backtracking line search, taking separate value and gradient closures.
approx_fprimeCentral-difference gradient of a scalar objective.
approx_hessCentral-difference Hessian of a scalar objective (symmetrized).

Results

NameDescription
OptimizeResultOutcome of an optimization run: fields x, fval, iters, converged, grad_norm.

Full API: see the generated rustdoc for solow-optimize.

References

  • Nocedal, J., and Wright, S. J. Numerical Optimization, 2nd ed. Springer, 2006.
  • Fletcher, R. Practical Methods of Optimization, 2nd ed. Wiley, 1987.
  • Broyden, C. G. "The Convergence of a Class of Double-Rank Minimization Algorithms." Journal of the Institute of Mathematics and Its Applications, 6(1):76–90, 1970.
  • Dennis, J. E., and Schnabel, R. B. Numerical Methods for Unconstrained Optimization and Nonlinear Equations. SIAM, 1996.