convex function

a function for which, given any two points, the function between those points sits at (lines are convex!) or below the plane given those points

constituents

For \(f: \mathbb{R}^{n} \to \mathbb{R}\)

\begin{equation} f\qty(\theta x + \qty(1-\theta) y) \leq \theta f\qty(x) + \qty(1-\theta) f\qty(y) \end{equation}

strictly convex is the strict inequality

affine: \(ax + b\)
exponential: \(e^{ax}\)
powers on \(R_{++}\): \(x^{\alpha}\) for \(\alpha \geq 1\) or \(\alpha \leq 0\)
\(|x|^{p}\) for \(p \geq 1\)
relu
any norm
sum of squares: \(\qty {x}^{2}_{2} = x_1^{2} + … + x_{n}^{2}\)
max function: \(\max \qty(x) = \max \qty {x_1 \dots x_{n}}\)
softmax: \(\log \qty(\exp x_1 + \dots + \exp x_{n})\)
general affine function: \(f\qty(X) = tr\qty(A^{T} X) + b\) (“an inner product”)
spectral norm: \(f\qty(X) = \norm{X}_{2} = \sigma_{\max}\qty(X)\) (the maximum singular value of \(X\)
logsumexp: \(f\qty(x) = \log \sum_{k=1}^{n} \exp x_{k}\)
quadratic over linear: \(f\qty(x,y) = \frac{x^{2}}{y}, y >0\)
quadratic: \(f\qty(x) = \frac{1}{2} x^{T} P x + q^{T} x + r\), with \(P \succeq 0\) is convex
least squares: \(f\qty(x) = \norm{Ax - b}^{2}_{2}\) is convex for any \(A\)
inverse product: \(f\qty(x) = \frac{1}{\prod_{i=1}^{n} x_{i}}\)
inv_pos on \(R_{++}\): \(f\qty(x) = \frac{1}{x}\) is convex if \(x\) is concave and positive

affine
square root
fractional powers
min
logs: \(\log x\)
entropy: \(- x \log x\)
negative part (opposite relu)
log determinant: \(f\qty(X) = \log \text{det} X\)
geometric mean: \(f\qty(x) = \qty(\prod_{k=1}^{n} x_{k})^{\frac{1}{n}}\) an \(\mathbb{R}_{++}^{n}\)

\begin{equation} C_{\alpha} = \qty {x \in \text{dom f} \mid f\qty(x) \leq \alpha } \end{equation}

sublevel sets of convex functions are convex sets (but converse is false)

\begin{equation} \text{epi } f = \qty {\qty(x, t) \in \mathbb{R}^{n+1} \mid x \in \text{dom } f, f\qty(x) \leq t} \end{equation}

f is convex IFF epi f is a convex set

“shaded area above the graph”