1
$\begingroup$

Let $f(X)\geq 0$ be a nonconvex $C^\infty$ function: $\mathbb R^3\to \mathbb R$.

Give any fixed $X_0$ such that $f(X_0)=\epsilon^+$, and the level set: ${L}=\{X\in \mathbb R^3:f(X)\leq \epsilon^+\}$ is a convex set.

And $\forall X_0$, $L$ is always a convex set.

Then what is the necessary and sufficient conditions, for $f(X)$ to be locally convex on ${L}$? (A mild sufficient condition would also be OK).

The sufficient condition better be easily (e.g. numerically) verifiable.

$\endgroup$

2 Answers 2

1
$\begingroup$

Equivalent to convexity is that the Hessian matrix is positive semidefinite for all $x \in L$. This can be done by checking if all eigenvalues of this symmetric matrix are nonegative. The eigenvalues in turn can be calculated by the zeros of the characteristic polynomial. They are real. In your special case $L\subset \mathbb{R}^3$, the characteristic polynomial is a polynomial of degree at most 3, that means the zeros can be found even analytically by Cardano's formula. The zeros would clearly depend on $X_0$.

Note that you assumed implicitely $\min f < \epsilon^+$ in order to avoid empty $L$.

$\endgroup$
2
  • $\begingroup$ Is there any sufficient condition which can be numerically verified? Since it is impossible to check all Hessians on $L$ $\endgroup$ Jan 17, 2014 at 14:05
  • 1
    $\begingroup$ Yes, I'll edit my answer. $\endgroup$ Jan 17, 2014 at 14:09
1
$\begingroup$

I came across this question following a link of "realted qustions", and I think it is worth adding a few comments:

1) To check that a function is locally convex you have to , in some way or another, check a conditiona at every point. The situeation is similar to chacking that a function is $ C^{\infty} $, often you verify that the function is smooth by verifying it is built out of smooth functions by steps that preserve smoothnes. See for example Chapter 3 of "Convex Optimization", Boyd for operations that preserve convexity.

In general, it can be difficult to check that a function is convex.

2) As @Horst points out, local convexity is equivalent to checking the Hessian is positive semidefinite, but that is also the criteria for global convexity, thus local and global convexity are the same concept.

3) There are criteria for determining if a matrix is positive definite that do not involve the characteristic polynomila, namely: a symmetric matrix is possitive semidefinite iff all the determinants of the diagonal submatrices going from entry (1,1) to entry (k,k) are possitive. Granted, for semidefinite the criteria is not iff and it will give only necessary conditions. However, for tri-diagonal matrices (and you are working in $\mathbb R^3$, so tri-diagonality is immediate), the criteria work. See page 228 of "Numerical Linear Algebra", L. N. Trefethen and D. Bau III. The change in sign in the sequence of the 3 minor determinants counts the number of negative eigenvalues!.

4) To check that the characteristic polynomial has no negative roots it is not necessary to find that roots, for example, one can use a Sturm sequence to check that there are no roots on the negative real axis.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.