Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

A function $f$ is convex if $$f(\theta x + (1 − \theta)y) \leq \theta f(x) + (1 − \theta)f(y)$$ for all $x, y \in \mathcal{D}(f)$, the domain of $f$, and $\theta \in [0, 1]$.

How do I determine whether a function of many variables is convex or non-convex?

If I find the Hessian of my function and they are not all positive, is it a non-convex function?

share|cite|improve this question
    
First i think that the domain must be convex. Second it is depends on your function. If it is only continuous, you have only continuous techniques to prove it. If it is $C^1$ you have more techniques and if it is $C^2$, you can compute the Hessian and verify if it is positive. – Tomás Feb 2 '13 at 16:28
    
Convexity makes sense for functions $f:A\rightarrow \mathbb R$ where $A$ is a convex subset of a vectorial space $V$. In particular, $f$ must be real-valued. Otherwise the codomain should be equipped with a partial order relation such that the definition of convexity still makes sense. – AndreasT Feb 2 '13 at 16:40
up vote 5 down vote accepted

If the function is twice differentiable and the Hessian is positive semidefinite in the entire domain, then the function is convex. Note that the domain must be assumed to be convex too. If the Hessian has a negative eigenvalue at a point in the interior of the domain, then the function is not convex.

share|cite|improve this answer
1  
This is brilliant. Would you care to show me a reference for the proof? – Vim Mar 20 at 15:31
    
I added a proof of that as an answer. – Alnitak Apr 7 at 21:07

This is a proof that if $f:U \rightarrow \mathbb{R}$, $U$ is an open and convex set of $\mathbb{R}^n$ and f is twice differentiable, then $f''(x)$ positive definite imply $f$ convex.

Let $f''(x)(h²) \geq 0 $ $\forall x \in U, \forall h \in \mathbb{R}^n. $

If $f$ isn't convex, $\exists x_{1},x_{2} \in U , \exists \lambda $ st. $ f((1- \lambda)x_{1} + \lambda x_{2}) > (1-\lambda)f(x_{1}) + \lambda f(x_{2})$

Let $\phi:[0,1] \rightarrow \mathbb{R}, \phi(t) = f((1-t)x_{1} + tx_{2})$

Then $ \phi(\lambda) > (1- \lambda) \phi(0) + \lambda \phi(1)$

Using the Mean Value Theorem, $\exists t_{1}, t_{2}$ with $0<t_{1}<\lambda<t_{2}<1$ st.

$\phi(\lambda) - \phi(0) = \lambda \frac{d}{dt} \phi(t_{1}) $ and $\phi(1)-\phi(\lambda) = (1-\lambda) \frac{d}{dt} \phi(t_{2}) $

Observe that

$\lambda ( \phi(1) - \phi(0)) < \phi(\lambda) - \phi(0) = \lambda \frac{d}{dt} \phi(t_{1})$

and that

$ (1-\lambda) \frac{d}{dt} \phi(t_{2}) = \phi(1) - \phi(\lambda) < (1-\lambda) [ \phi(1) - \phi(0) ]$

Then $ \frac{d}{dt} \phi (t_{2}) < \phi(1) - \phi(0) < \frac{d}{dt} \phi(t_{1}).$

Again, using MVT,

$\exists t_{3} \in (t_{1}, t_{2})$ st. $\frac{d²}{dt²} \phi(t_3) < 0$

This is an absurd, since by hypothesis $\frac{d²}{dt²} \phi(t) \geq 0, \frac{d²}{dt²} \phi(t) = f''(\phi(t))(x_{2}-x_{1})²$

$\square$

share|cite|improve this answer

protected by user26857 Aug 20 '15 at 19:30

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site.

Would you like to answer one of these unanswered questions instead?

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