Detecting negative eigenvalues of exact and approximate Hessian matrices in optimization
From MaRDI portal
Abstract: 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.
Recommendations
- A spectral characterization and an approximation scheme for the Hessian eigenvalue
- Eigenvalues and nonsmooth optimization
- Negativity compensation in the nonnegative inverse eigenvalue problem
- Accurate Eigenvalues and SVDs of Totally Nonnegative Matrices
- On Eigenvalue Optimization
- Least-squares solution for inverse eigenpair problem of nonnegative definite matrices
- The inverse eigenvalue problem for nonnegative matrices
- scientific article; zbMATH DE number 1560263
- Optimization of the spectral radius of nonnegative matrices
- scientific article; zbMATH DE number 967335
Cites work
- A decoupled first/second-order steps technique for nonconvex nonlinear unconstrained optimization with improved complexity bounds
- A modification of Armijo's step-size rule for negative curvature
- A nonmonotone truncated Newton-Krylov method exploiting negative curvature directions, for large scale unconstrained optimization
- A second-order globally convergent direct-search method and its worst-case complexity
- A subclass of generating set search with convergence to second-order stationary points
- Algorithm 457: finding all cliques of an undirected graph
- Complexity analysis of second-order line-search algorithms for smooth nonconvex optimization
- Complexity bounds for second-order optimality in unconstrained optimization
- Concise complexity analyses for trust region methods
- Curvilinear path steplength algorithms for minimization which use directions of negative curvature
- CUTEst: a constrained and unconstrained testing environment with safe threads for mathematical optimization
- Derivative-free and blackbox optimization
- Global convergence of general derivative-free trust-region algorithms to first- and second-order critical points
- scientific article; zbMATH DE number 1049353 (Why is no real title available?)
- scientific article; zbMATH DE number 852532 (Why is no real title available?)
- Introduction to Derivative-Free Optimization
- On the use of directions of negative curvature in a modified newton method
- Trust Region Methods
This page was built for publication: Detecting negative eigenvalues of exact and approximate Hessian matrices in optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6057628)
