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