Quasi-Newton Algorithms with Updates from the Preconvex Part of Broyden's Family

Abstract

Most popular quasi-Newton methods for unconstrained optimization are from the one-parameter Broyden's family, especially from a subset of the family: the so-called convex class, i.e. members with the parameter 0≤φ≤1. In particular, the BFGS method corresponding to φ=0 is generally accepted as the best available. In this paper, we investigate the updates in Broyden's family that use negative parameter φ. We show that, for convex objective functions, these methods have the same global convergence property as BFGS and may also have superlinear convergence rate if φ≤0 is suitably chosen at each iteration. We present numerical evidence exhibiting that methods with φ≤ 0 can be more efficient than BFGS in terms of numbers of function evaluations and iterations. In particular, we compare two algorithms using φ≤0 with BFGS and show the relative merit of these algorithms.