  Nonconvex minimization algorithms often benefit from the use of second-order
information as represented by the Hessian matrix. When the Hessian at a
critical point possesses negative eigenvalues, the corresponding eigenvectors
can be used to search for further improvement in the objective function value.
Computing such eigenpairs can be computationally challenging, particularly if
the Hessian matrix itself cannot be built directly but must rather be sampled
or approximated. In blackbox optimization, such derivative approximations are
built at a significant cost in terms of function values.
  In this paper, we investigate practical approaches to detect negative
eigenvalues in Hessian matrices without access to the full matrix. We propose a
general framework that begins with the diagonal and gradually builds
submatrices to detect negative curvature. Crucially,our approach works both
when exact Hessian coordinate values are available and when Hessian coordinate
values are approximated. We compare several instances of our framework on a
test set of Hessian matrices from a popular optimization library, and
finite-differences approximations thereof. Our experiments highlight the
importance of the variable order in the problem description, and show that
forming submatrices is often an efficient approach to detect negative
curvature.
