Exact linesearch limited-memory quasi-Newton methods for minimizing a quadratic function

• Published in: Computational optimization and applications 2021-07, Vol.79 (3), p.789-816
• Main Authors: Ek, David, Forsgren, Anders
• Format: Article
• Language: English
• Subjects: Approximation; Arithmetic; Conjugate gradient method; Convex and Discrete Geometry; Exact linesearch method; Limited-memory method; Linear equations; Management Science; Mathematical analysis; Mathematics; Mathematics and Statistics; Method of conjugate gradients; Operations Research; Operations Research/Decision Theory; Optimization; Quadratic equations; Quasi Newton methods; Quasi-Newton method; Representations; Statistics; Unconstrained quadratic program
• ISSN: 0926-6003; 1573-2894; 1573-2894
• DOI: 10.1007/s10589-021-00277-4

The main focus in this paper is exact linesearch methods for minimizing a quadratic function whose Hessian is positive definite. We give a class of limited-memory quasi-Newton Hessian approximations which generate search directions parallel to those of the BFGS method, or equivalently, to those of the method of preconditioned conjugate gradients. In the setting of reduced Hessians, the class provides a dynamical framework for the construction of limited-memory quasi-Newton methods. These methods attain finite termination on quadratic optimization problems in exact arithmetic. We show performance of the methods within this framework in finite precision arithmetic by numerical simulations on sequences of related systems of linear equations, which originate from the CUTEst test collection. In addition, we give a compact representation of the Hessian approximations in the full Broyden class for the general unconstrained optimization problem. This representation consists of explicit matrices and gradients only as vector components.