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}\)

requirements

\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

additional information

log conditions

• \(f\) is log-linear IFF log \(f\) is affine
• \(f\) is log-concave iff log \(f\) is concave
• \(f\) is log-convex IFF log \(f\) is convex

check if something is a convex function

• check definition
• restrict it to a line: convexity preserve line restriction
• 1st order condition
• 2nd order condition
• show that \(f\) is constructed by operations that preserve fuction convexity

some convex functions

• 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

some concave fuctions

• 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}\)

sublevel set

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

constituents

• set \(C\)
• \(\theta \in \mathbb{R}\)

requirements

A set \(C\) is a convex set if:

\begin{equation} x_1, x_2 \in C, 0 \leq \theta \leq 1 \implies \theta x_{1} + \qty(1-\theta) x_{2} \in C \end{equation}

definitions

standard definitions

additional information

operations that preserve convexity

Convex sets is a calculus! Methods to showing complexity:

Anything in Euclidian Geometry Crash Course

1. apply definition: show \(x_1, x_2 \in C, 0 \leq \theta \leq 1 \implies \theta x_1 + \qty(1-\theta) x_2 \in C\)
2. use convex functions
3. show that \(C\) is obtained from convex sets via the following operations

intersection

Intersections of any number of convex sets, include infinite, are convex.

introducing new variables

Consider the original problem:

\begin{align} \min_{x}\quad & \norm{Ax - b} \end{align}

Now, we can reformulate and write \(y = Ax - b\). Now, remember the conjugate of the norm is:

\begin{equation} \norm{z} = \begin{cases} 0, \norm{z} \leq 1\\ \infty \end{cases} \end{equation}

And remember the dual is some massaging of the conjugate. And thus we can formulate a “norm conjugate”:

\begin{align} \max_{v}\quad & b^{T}v \\ \textrm{s.t.} \quad & A^{T}v = 0 \\ & \norm{v} \leq 1 \end{align}

Lagrange Dual Problem

Given the Lagrange Dual Function, we can formulate the Lagrange Dual Problem:

\begin{align} \max_{\lambda, v}\quad & g\qty(\lambda,v) \\ \textrm{s.t.} \quad & \lambda \succeq 0 \end{align}

• finds the best lower bound on \(p^{*}\), obtained from Lagrange dual function
• a convex optimization problem, even if original primal fiction is not
• dual optimal value denoted \(d^{*}\)

\(\lambda, v\) as “dual feasible” if \(\lambda \succeq 0, \qty(\lambda, v) \in \text{dom } g\).

Example Dual Problems

LPs

\begin{align} \min_{x}\quad & c^{T}x \\ \textrm{s.t.} \quad & Ax = b \\ & x \succeq x \end{align}

Consider feasible problems.

\begin{align} \min_{x}\quad & 0 \\ \textrm{s.t.} \quad & \dots \end{align}

so the optimal is either \(p^{*} = 0\) or \(p^{*} = +\infty\). And thus the Lagrange Dual Problem boils down to checking if \(d^{*} \geq 0\), if so, then the original problem is’nt feasible (since dual gives a lower bound.)