Necessary Second-Order Optimality Condition of Iterate within a Specified Tolerance


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. 

I also realize that using AD to compute the Hessian may make this harder.

Thanks in advance for any ideas or resources!

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.

1 Like

The classic check is m >= -tol, where tol > 0.

1 Like

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.

Have a look here (slide 27) to figure out the correct test to perform:

The op is talking about unconstrained problems.

Oops, my bad! A (semi-)definite proof I should’ve gone to bed.