I am working with a scheme that seeks an unconstrained local minimizer of some C^2 function f.
The scheme terminates when the necessary first-order optimality condition for the iterate x has been met, up to a prescribed tolerance \epsilon, i.e. ||\nabla f(x) || \leq \epsilon.
Now, my question is about finding a sound way to confirm that the iterate x also satisfies the necessary second-order optimality condition for being a local minimizer of f.
Namely, is there a sensible way to conclude that \nabla^2 f(x) is semi-definite enough, as related to \epsilon?
Below is a control flow sketch (assume hess(x) computes the dense Hessian matrix at x, by forward-mode AD)
function is_second_order_optimal(hess, x, eps)
H = hess(x)
# is it symmetric enough?
norm(H - H')/norm(H) > eps && return false
m = minimum(eigvals(H))
# second-order condition check: (is it pos semi-definite?)
m >= 0 && return true
# The statement under question:
abs(m) >= eps && return true # I pulled out of thin air...
# ...could see it also depending upon the dim(H) and machine epsilon.
end
I also realize that using AD to compute the Hessian may make this harder.
One possibility to check, and that may occur based on a sparse coupling between variables within constraints, is that the Hessian is diagonally dominant. Then the verification of a semidefinite condition can be done relatively cheaply by comparing the sizes of the matrix elements (compared to eigenvalue computation). There may even be scope to re-use calculation when checking symmetry of the matrix.
A quick comment based on Karush–Kuhn–Tucker conditions - Wikipedia
The sufficient second-order condition states that the Hessian should be SPD on the nullspace of the Jacobian of the active constraints. That is, it is a weaker condition than SPD in the whole space.