Quasi-Newton methods for unconstrained optimization are important computational tools in many scientific fields and are a standard subject in textbooks on computation. The BFGS method, proposed individually by Broyden (1970), Fletcher (1970), Goldfarb (1970), and Shanno (1970), is implemented in most optimization software and is widely recognized as efficient. A new method for quasi-Newton minimization, called the Statisticalquasi-Newton (SQN) algorithm, 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 for Broyden updates. 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 SQN algorithm typically converges with about 25% fewer iterations, functions and gradient evaluations on the top 1/3 hardest unconstrained problems in the CUTE library. Typical improvement on the 1/3 easiest problems is about 5%. 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 accuracy of the Hessian, in a certain sense, 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.

Joint work with Scott Vander Wiel.