1

It is well known that the Hessian matrix of a convex function is positive semidefinite (PSD) and positive definite (PD) for strict convexity. I have rarely thought about the reverse direction, but it seems it is not true.

If a Hessian matrix of an arbitrary function is PSD, can any conclusions be made about the convexity? For this, I am considering 2 cases:

  1. PSD at a critical point.

  2. PSD everywhere.

In the single variable case, e.g., $f(x) = x^2$, the Hessian reduces to just a single second derivative, and the second derivative test can be applied for convexity, but for the general multivariable case, it seems no conclusions can be made. Is that correct?

Rodrigo de Azevedo
  • 1
user5965026
  • 677
  • Take a look at these functions. What does PSD-ness of the Hessian at a critical point tell you about convexity? – Rodrigo de Azevedo Aug 22 '20 at 16:57
  • @RodrigodeAzevedo Based on this and what I've read, it seems the test is inconclusive and you have to use other methods to determine convexity or lack thereof. – user5965026 Aug 22 '20 at 17:04
  • If you prove PSD-ness everywhere, that is another story. – Rodrigo de Azevedo Aug 22 '20 at 17:08
  • @RodrigodeAzevedo If it's PSD over the feasible region, then I believe that means the function is convex within that region? If it is PSD at a critical point, then you don't know if that critical point is a minimum or not, which implies that you don't know if the function is convex within that region (because if it is then you would surely know that critical point is a minimum in that region?) – user5965026 Aug 22 '20 at 17:09
  • I know nothing about convex analysis. Hopefully someone who does will comment. – Rodrigo de Azevedo Aug 22 '20 at 17:11

1 Answers1

2

A twice continuously differentiable function over an open convex set is convex if and only if its Hessian is a PSD matrix. If indeed it is PSD over the feasible open convex set, then it must be PSD at a critical (stationary) point as well. And the main advantage of convex functions is that a critical point is also a local and global minimum of the function (although it need not be unique).

iarbel84
  • 1,513
  • What if we can't show that the hessian is PSD over the feasible open convex set, and can only show that the hessian is PSD at the critical point? Then we cannot conclude anything about optima here right? – user5965026 Aug 23 '20 at 18:21
  • You cannot conclude anything in that case. Since you have a possibly non-convex function, second order conditions are necessary for optimality, they are not sufficient – iarbel84 Aug 24 '20 at 08:26
  • What are the sufficient conditions here? – user5965026 Aug 24 '20 at 14:50
  • Sufficient conditions exist only if the function is know to be convex over the feasible domain. This brings us back to your original question - the Hessian must be PSD over the entire feasible domain in order for the necessary conditions to be sufficient. Check KKT conditions for more info: https://en.wikipedia.org/wiki/Karush%E2%80%93Kuhn%E2%80%93Tucker_conditions#Second-order_sufficient_conditions – iarbel84 Aug 24 '20 at 15:03