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

**URL:** <https://discourse.julialang.org/t/necessary-second-order-optimality-condition-of-iterate-within-a-specified-tolerance/69334>\
**Category:** Optimization (Mathematical)\
**Tags:** question\
**Created:** [October 6, 2021, 9:23pm UTC](https://discourse.julialang.org/t/necessary-second-order-optimality-condition-of-iterate-within-a-specified-tolerance/69334 "2021-10-06T21:23:14Z")\
**Posts on this page:** 6\
**Page:** 1

<div class="post-metadata">

**Author:** ![danphenderson](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/danphenderson/32/28317_2.png) [@danphenderson](https://discourse.julialang.org/u/danphenderson)\
**Post date:** [October 6, 2021, 9:23pm UTC](https://discourse.julialang.org/t/necessary-second-order-optimality-condition-of-iterate-within-a-specified-tolerance/69334/1 "2021-10-06T21:23:14Z")

</div>

Hello,

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)

```julia
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.

Thanks in advance for any ideas or resources!

---

<div class="post-metadata">

**Author:** ![jd-foster](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jd-foster/32/35824_2.png) [@jd-foster](https://discourse.julialang.org/u/jd-foster)\
**Post date:** [October 7, 2021, 5:17am UTC](https://discourse.julialang.org/t/necessary-second-order-optimality-condition-of-iterate-within-a-specified-tolerance/69334/2 "2021-10-07T05:17:07Z")

</div>

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.

> **[Diagonally dominant matrix | Applications and properties](https://en.wikipedia.org/wiki/Diagonally_dominant_matrix#Applications_and_properties)**
>
> The following results can be proved trivially from Gershgorin's circle theorem. Gershgorin's circle theorem itself has a very short proof.
> A strictly diagonally dominant matrix (or an irreducibly diagonally dominant matrix) is non-singular.
> A Hermitian diagonally dominant matrix 
>   
>     
>       
> A
>       
>     
> {\\displaystyle A}
>   
> with real non-negative diagonal entries is positive semidefinite. This follows from the eigenvalues being real, and Gershgorin's circle theorem. If the sym...

---

<div class="post-metadata">

**Author:** ![dpo](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dpo/32/3335_2.png) [@dpo](https://discourse.julialang.org/u/dpo)\
**Post date:** [October 7, 2021, 4:12pm UTC](https://discourse.julialang.org/t/necessary-second-order-optimality-condition-of-iterate-within-a-specified-tolerance/69334/3 "2021-10-07T16:12:50Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![cvanaret](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/cvanaret/32/11594_2.png) [@cvanaret](https://discourse.julialang.org/u/cvanaret)\
**Post date:** [October 8, 2021, 11:20pm UTC](https://discourse.julialang.org/t/necessary-second-order-optimality-condition-of-iterate-within-a-specified-tolerance/69334/4 "2021-10-08T23:20:00Z")

</div>

A quick comment based on [Karush–Kuhn–Tucker conditions - Wikipedia](https://en.wikipedia.org/wiki/Karush%E2%80%93Kuhn%E2%80%93Tucker_conditions#Sufficient_conditions)  
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: [https://web.stanford.edu/class/msande311/lecture07.pdf](https://web.stanford.edu/class/msande311/lecture07.pdf)

---

<div class="post-metadata">

**Author:** ![dpo](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dpo/32/3335_2.png) [@dpo](https://discourse.julialang.org/u/dpo)\
**Post date:** [October 9, 2021, 12:01pm UTC](https://discourse.julialang.org/t/necessary-second-order-optimality-condition-of-iterate-within-a-specified-tolerance/69334/5 "2021-10-09T12:01:27Z")

</div>

The op is talking about unconstrained problems.

---

<div class="post-metadata">

**Author:** ![cvanaret](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/cvanaret/32/11594_2.png) [@cvanaret](https://discourse.julialang.org/u/cvanaret)\
**Post date:** [October 9, 2021, 1:21pm UTC](https://discourse.julialang.org/t/necessary-second-order-optimality-condition-of-iterate-within-a-specified-tolerance/69334/6 "2021-10-09T13:21:29Z")

</div>

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