I am trying to learn about how to prove whether functions or sets are convex. Unfortunately my teacher uses very hard to understand (for me anyway) notation and I am struggling to get my head around it. I understand that a set is convex if the the line between two points in the set is contained in the set, but are there specific steps to follow or things to check whether or not a function is convex?
–
I have two examples that I am unsure if I am approaching correctly:
(1) Is $x -> (Px,x)^{1/2} $ convex for $P>0?$
This gives $\sqrt{x^TPx}$. So if I take $P=\begin{pmatrix}1&0\\0&1\end{pmatrix}$
then
$x^tPx$ = $(x_1 x_2)$$\begin{pmatrix}1&0\\0&1\end{pmatrix}$$\begin{pmatrix}x_1\\x_2\end{pmatrix}$ = $x_1^2 + x_2^2$
This result will always be positive, therefore for any P > 0, the function will be convex. Is this method a correct way to prove convexity?
(2) Is the following set convex:
${x: ‖x‖_p ≤1},p=1,2,3 $
I take it as this is the p-norm of $x$ which is the same as writing:
$$(\sum_{i=1}^3 |x_i|^p)^{1/2}$$ where p=1,2,3
So if $f(x)=‖x‖_p$, then f is convex for any p because
$f(x)=‖x‖_p,1≤p< +∞$ (any natural number which includes 1,2 & 3)
$f(0)+(x,y)≤‖x‖_p ‖x‖_q,$ where $1/p+1/q=1$
$∂f(0)={c(0): ‖c(0)‖_q≤1}$
Where ∂f(v) is the set of all sub-gradients of f at point v (also known as the sub-differential).
Does this make sense? I got this from my lectures but I am a little unsure what it actual means in layman terms
–
Any extra advice or pointers in general about checking whether a set is convex or not would be greatly appreciated!
Best Answer
(1) In general, any norm is convex. This follows from $\| tx + (1-t)y\| \le t \|x\| + (1-t) \|y\|$ for $t \in [0,1]$.
Note that $x \mapsto \langle Px, x \rangle$ is a norm iff $P>0$.
(2) In general, if $f$ is convex, then the set $L = \{ x | f(x) \le C \}$ is convex. To see this note that if $x,y \in L$, then $f(tx+(1-t)y) \le t f(x)+(1-t) f(y) \le C$, hence $tx+(1-t)y \in L$.
Note that the functions $x \mapsto \|x\|_p$ are norms for $p \ge 1$.