A structured quasi-Newton algorithm for optimizing with incomplete Hessian information

Cosmin Petra(petra1llnl.gov)
Naiyuan Chiang(sorakid507gmail.com)
Mihai Anitescu(anitescumcs.anl.gov)

Abstract: 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 BFGS secant update formula that approximates only the missing Hessian terms, and we propose a line-search 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).

Keywords: structured quasi-Newton, secant approximation, BFGS, incomplete Hessian

Category 1: Nonlinear Optimization (Unconstrained Optimization )

Citation: Lawrence Livermore National Laboratory, Report LLNL-JRNL-745068, Jan 2018.

Download: [PDF]

Entry Submitted: 02/02/2018
Entry Accepted: 02/02/2018
Entry Last Modified: 02/02/2018

Modify/Update this entry