how to determine whether a function is convex or not?

Question

I have a function $f:(u,v) \in \mathbb{R}^n×\mathbb{R}^n \rightarrow \mathbb{R}$, and $f$ is differentiable with respect to both $u$ and $v$. how can I proof the convexity of function $f$?

Answer 1

If $f$ is twice-differentiable, you could try to show that the Hessian is always positive semidefinite. This is easiest for functions from $\mathbb{R}$ to itself.

Otherwise, I find it's usually easiest to show convexity by "building up" your function from convex building blocks. For instance,

1) All norms are convex

2) any convex function composed with an affine operator is still convex

3) arbitrary suprema of convex functions remains convex, e.g. a max of two convex functions is convex

4) any sum of convex functions with positive coefficients remains convex

5) if you marginalize out a variable via infemum, this also preserves convexity.

6) any linear operator (e.g. an inner product with fixed slope) is convex

7) The distance (or squared distance) to any closed convex set is convex.

Using these tools (and there are many more), you can build up all sorts of wacky functions. Let's do an example! If $A$ is a matrix and $b,c$ are in $\mathbb{R}^n$, you can show $2\|\cdot\|_1 + \|A\cdot-b\|_2^2 - \langle c,\cdot\rangle$ is convex, and more importantly you can prove they are convex in just a few lines!

For my example: $\langle - c, \cdot \rangle$ is linear so it is convex. $\|\cdot\|_1$ is a norm so it's convex. $\|\cdot\|^2$ is convex (this one is due to a result a bit more technical concerning the composition of even functions with convex functions that vanish at zero). Since $\|\cdot\|^2$ is convex and $A\cdot-b$ is affine, $\|A\cdot-b\|^2$ is convex as well. Since addition with positive coefficients preserves convexity, we've just shown that the complicated function above is convex!