A Structured Quasi-Newton Algorithm for Optimizing with Incomplete Hessian Information

Research paper by Cosmin G. Petra, Naiyuan Chiang, Mihai Anitescu

Indexed on: 12 Apr '19Published on: 11 Apr '19Published in: SIAM journal on optimization : a publication of the Society for Industrial and Applied Mathematics


SIAM Journal on Optimization, Volume 29, Issue 2, Page 1048-1075, January 2019. We present a structured quasi-Newton algorithm for unconstrained optimization problems that have unavailable second-order derivatives or Hessian terms. We provide a formal derivation of the well-known Broyden--Fletcher--Goldfarb--Shanno (BFGS) secant update formula that approximates only the missing Hessian terms, and we propose a linesearch quasi-Newton algorithm based on a modification of Wolfe conditions that converges to first-order optimality conditions. We also analyze the local convergence properties of the structured BFGS algorithm and show that it achieves superlinear convergence under the standard assumptions used by quasi-Newton methods using secant updates. We provide a thorough study of the practical performance of the algorithm on the CUTEr suite of test problems and show that our structured BFGS-based quasi-Newton algorithm outperforms the unstructured counterpart(s).