Notes on convex functions

Basic Properties

[TODO]

Examples

• Affine functions are both convex and concave
• All norms are convex (e.g. Frobenius norm, Spectral norm)
• Max function $f(x) = \max_i x_i$ is convex on $\mathbb{R}^n$
• Quadratic-over-linear function $f(x,y)=x^2/y$ is convex on $\text{dom }f=\mathbb{R}\times\mathbb{R}_{++}$
• Log-sum-exp $f(x)=\log \sum^n_{i=1}e^{x_i}$ is convex on $\mathbb{R}^n$
• Geometric mean $f(x)=(\prod^n_{i=1}x_i)^{1/n}$ is concave on $\text{dom }f=\mathbb{R}^n_{++}$
• Log-det is concave on $\text{dom }f=\mathbf{S}^n_{++}$

Restriction of a convex function to a line

$f:\mathbb{R}^n \rightarrow \mathbb{R}$ is convex iff the function $g:\mathbb{R} \rightarrow \mathbb{R}$, 

$$g(t) = f(x+tv), \quad \text{dom } g = \{ t\; |\; x + tv \in \text{dom } f \}$$

is convex in $t$ for any $x \in  \text{dom } f$, $v \in \mathbf{R}^n$

Upshot: can check convexity of $f$ by checking convexity of functions of one variable.

Epigraph and sublevel set 

$\alpha$-sublevel set of $f:\mathbb{R}^n \rightarrow \mathbb{R}$, is defined as all x for which the value of $f(x)$ is less then $\alpha$

$$C_\alpha = \{ x \in \text{dom } f \; | \; f(x) \leq \alpha \}$$

Property: sublevel sets of convex functions are convex (converse is false)

epigraph of $f:\mathbb{R}^n \rightarrow \mathbb{R}$:

$$\text{epi } f = \{ (x,t) \in \mathbb{R}^{n+1} \; | \; x \in \text{dom } f, f(x) \leq t \}$$

Property: $f$ is convex iff  $\text{epi }f$ is a convex set

Operations that perserve convexity

methods for establishing convexity of a function

1. verify definition (often simplified by restricting to a line)
2. for twice differentiable functions, show $\nabla^2 f(x) \succeq 0$
3. show that $f$ is obtained from simple convex functions by operations that preserve convexity
• nonnegative weighted sum
• composition with affine function
• pointwise maximum and supremum
• composition
• minimization
• perspective