Statistical Quasi-Newton: A New Look at Least Change

A new method for quasi-Newton minimization outperforms BFGS by combining least-change updates of the Hessian with step- sizes estimated from a Wishart model of uncertainty. The Hessian update is in the Broyden family but uses a negative parameter, outside the convex range that is usually regarded as the safe- zone. Although full Newton steps based on this update tend to be too long, excellent performance is obtained with shorter steps estimated from the Wishart model. In numerical comparisons to BFGS the new Statistical quasi-Newton (SQN) algorithm converges with about 20% fewer iterations and gradient evaluations and 10% fewer function evaluations on a suite of standard test functions. The framework used to derive SQN provides a simple way to understand differences among various Broyden updates such as BFGS and DFP and shows that these methods do not preserve Hessian accuracy while the new method does. In fact, BFGS, DFP and all other updates with non-negative Broyden parameters tend to inflate Hessian estimates and this accounts for their observed propensity to correct eigenvalues that are too small more readily than eigenvalues that are too large. Numerical results on three new test functions validate these conclusions.