A new multipoint symmetric secant method with a dense initial matrix

Abstract

In large-scale optimization, when either forming or storing Hessian matrices are prohibitively expensive, quasi-Newton methods are often used in lieu of Newton's method because they only require first-order information to approximate the true Hessian. Multipoint symmetric secant (MSS) methods can be thought of as generalizations of quasi-Newton methods in that they attempt to impose additional requirements on their approximation of the Hessian. Given an initial Hessian approximation, MSS methods generate a sequence of possibly-indefinite matrices using rank-2 updates to solve nonconvex unconstrained optimization problems. For practical reasons, up to now, the initialization has been a constant multiple of the identity matrix. In this paper, we propose a new limited-memory MSS method for large-scale nonconvex optimization that allows for dense initializations. Numerical results on the CUTEst test problems suggest that the MSS method using a dense initialization outperforms the standard initialization. Numerical results also suggest that this approach is competitive with both a basic L-SR1 trust-region method and an L-PSB method.

Keywords:

• Quasi-Newton methods
• large-scale optimization
• nonlinear optimization
• trust-region methods

Acknowledgements

The authors would like to thank the referees. In particular, one referee provided an explanation that led to the inclusion of Lemma 3.5 and significantly improved the entire section. In fact, part of the proof is based on an observation by the referee.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Notes

1 For the numerical results, MATLAB's built-in ldl command, which uses rook pivoting[18,19], is used.

2 See https://www.cuter.rl.ac.uk/Problems/mastsif.shtml for further classification information.

Additional information

Funding

J. B. Erway's research work was funded by NSF [grant number IIS-1741264].

Notes on contributors

Jennifer B. Erway

Jennifer B. Erway is a professor at Wake Forest University. Her research interests include numerical optimization, computational math, and numerical linear algebra.

Mostafa Rezapour

Mostafa Rezapour is a teacher scholar postdoctoral fellow in the department of mathematics at Wake Forest University. His research interests include optimization, machine learning, deep learning and numerical linear algebra.