Jennifer B. Erway

Jennifer B. Erway, Roummel F. Marcia

In this paper, we investigate a formula to solve systems of the form (B + σI)x = y, where B is a limited-memory BFGS quasi-Newton matrix and σ is a positive constant. These types of systems arise naturally in large-scale optimization such as trust-region methods as well as doubly-augmented Lagrangian methods. We show that provided a simple condition holds on B_0 and σ, the system (B + σI)x = y can be solved via a recursion formula that requies only vector inner products. This formula has complexity M^2n, where M is the number of L-BFGS updates and n >> M is the dimension of x.

Jennifer B. Erway, Roummel F. Marcia

A MATLAB implementation of the More-Sorensen sequential (MSS) method is presented. The MSS method computes the minimizer of a quadratic function defined by a limited-memory BFGS matrix subject to a two-norm trust-region constraint. This solver is an adaptation of the More-Sorensen direct method into an L-BFGS setting for large-scale optimization. The MSS method makes use of a recently proposed stable fast direct method for solving large shifted BFGS systems of equations [13, 12] and is able to compute solutions to any user-defined accuracy. This MATLAB implementation is a matrix-free iterative method for large-scale optimization. Numerical experiments on the CUTEr [3, 16]) suggest that using the MSS method as a trust-region subproblem solver can require significantly fewer function and gradient evaluations needed by a trust-region method as compared with the Steihaug-Toint method.

Jennifer B. Erway, Roummel F. Marcia

We consider the problem of solving linear systems of equations arising with limited-memory members of the restricted Broyden class of updates and the symmetric rank-one (SR1) update. In this paper, we propose a new approach based on a practical implementation of the compact representation for the inverse of these limited-memory matrices. Numerical results suggest that the proposed method compares favorably in speed and accuracy to other algorithms and is competitive with several update-specific methods available to only a few members of the Broyden class of updates. Using the proposed approach has an additional benefit: The condition number of the system matrix can be computed efficiently.

Jennifer B. Erway, Vibhor Jain, Roummel F. Marcia

We investigate fast direct methods for solving systems of the form (B + G)x = y, where B is a limited-memory BFGS matrix and G is a symmetric positive-definite matrix. These systems, which we refer to as shifted L-BFGS systems, arise in several settings, including trust-region methods and preconditioning techniques for interior-point methods. We show that under mild assumptions, the system (B + G)x = y can be solved in an efficient and stable manner via a recursion that requies only vector inner products. We consider various shift matrices G and demonstrate the effectiveness of the recursion methods in numerical experiments.

Lasith Adhikari, Jennifer B. Erway, Shelby Lockhart et al.

In this paper, we solve the l2-l1 sparse recovery problem by transforming the objective function of this problem into an unconstrained differentiable function and apply a limited-memory trust-region method. Unlike gradient projection-type methods, which uses only the current gradient, our approach uses gradients from previous iterations to obtain a more accurate Hessian approximation. Numerical experiments show that our proposed approach eliminates spurious solutions more effectively while improving the computational time to converge.

Jennifer B. Erway, Joshua Griffin, Roummel F. Marcia et al.

Machine learning (ML) problems are often posed as highly nonlinear and nonconvex unconstrained optimization problems. Methods for solving ML problems based on stochastic gradient descent are easily scaled for very large problems but may involve fine-tuning many hyper-parameters. Quasi-Newton approaches based on the limited-memory Broyden-Fletcher-Goldfarb-Shanno (BFGS) update typically do not require manually tuning hyper-parameters but suffer from approximating a potentially indefinite Hessian with a positive-definite matrix. Hessian-free methods leverage the ability to perform Hessian-vector multiplication without needing the entire Hessian matrix, but each iteration's complexity is significantly greater than quasi-Newton methods. In this paper we propose an alternative approach for solving ML problems based on a quasi-Newton trust-region framework for solving large-scale optimization problems that allow for indefinite Hessian approximations. Numerical experiments on a standard testing data set show that with a fixed computational time budget, the proposed methods achieve better results than the traditional limited-memory BFGS and the Hessian-free methods.

Omar DeGuchy, Jennifer B. Erway, Roummel F. Marcia

In this paper, we present the compact representation for matrices belonging to the the Broyden class of quasi-Newton updates, where each update may be either rank-one or rank-two. This work extends previous results solely for the restricted Broyden class of rank-two updates. In this article, it is not assumed the same Broyden update is used each iteration; rather, different members of the Broyden class may be used each iteration. Numerical experiments suggest that a practical implementation of the compact representation is able to accurately represent matrices belonging to the Broyden class of updates. Furthermore, we demonstrate how to compute the compact representation for the inverse of these matrices, as well as a practical algorithm for solving linear systems with members of the Broyden class of updates. We demonstrate through numerical experiments that the proposed linear solver is able to efficiently solve linear systems with members of the Broyden class of matrices to high accuracy. As an immediate consequence of this work, it is now possible to efficiently compute the eigenvalues of any limited-memory member of the Broyden class of matrices, allowing for the computation of condition numbers and the ability perform sensitivity analysis.

Jennifer B. Erway, Roummel F. Marcia

In this paper, we consider the problem of efficiently computing the eigenvalues of limited-memory quasi-Newton matrices that exhibit a compact formulation. In addition, we produce a compact formula for quasi-Newton matrices generated by any member of the Broyden convex class of updates. Our proposed method makes use of efficient updates to the QR factorization that substantially reduces the cost of computing the eigenvalues after the quasi-Newton matrix is updated. Numerical experiments suggest that the proposed method is able to compute eigenvalues to high accuracy. Applications for this work include modified quasi-Newton methods and trust-region methods for large-scale optimization, the efficient computation of condition numbers and singular values, and sensitivity analysis.