Convex functions¶

$$ \newcommand{\eg}{{\it e.g.}} \newcommand{\ie}{{\it i.e.}} \newcommand{\argmin}{\operatornamewithlimits{argmin}} \newcommand{\mc}{\mathcal} \newcommand{\mb}{\mathbb} \newcommand{\mf}{\mathbf} \newcommand{\minimize}{{\text{minimize}}} \newcommand{\argmin}{{\text{argmin}}} \newcommand{\diag}{{\text{diag}}} \newcommand{\cond}{{\text{cond}}} \newcommand{\rank}{{\text{rank }}} \newcommand{\range}{{\mathcal{R}}} \newcommand{\null}{{\mathcal{N}}} \newcommand{\tr}{{\text{trace}}} \newcommand{\dom}{{\text{dom}}} \newcommand{\dist}{{\text{dist}}} \newcommand{\E}{\mathbf{E}} \newcommand{\var}{\mathbf{var}} \newcommand{\R}{\mathbf{R}} \newcommand{\SM}{\mathbf{S}} \newcommand{\ball}{\mathcal{B}} \newcommand{\bmat}[1]{\begin{bmatrix}#1\end{bmatrix}} $$

Jong-Han Kim (jonghank@inha.ac.kr)

Definition¶

$f:\R^n\rightarrow \R$ is convex if $\dom f$ is a convex set and

$$ f\left( \theta x + (1-\theta)y\right) \le \theta f(x) + (1-\theta) f(y) $$

for all $x,y\in \dom f$ and $0\le \theta\le 1$.

• $f$ is concave is $-f$ is convex
• $f$ is strictly convex if $\dom f$ is convex and

$$ f\left( \theta x + (1-\theta)y\right) < \theta f(x) + (1-\theta) f(y) $$

for all $x,y\in \dom f$, $x\ne y$, and $0\le \theta\le 1$.

• $f$ is affine if $a$ is convex and concave

Convexity condition¶

• 1st order condition: differentiable $f$ with convex domain is convex if and only if

$$ f(y) \ge f(x) + \nabla f(x)^T (y-x) \quad \text{for all } x,y\in\dom f $$

• 2nd order condition: twice differentiable $f$ with convex domain is convex if and only if

$$ \nabla^2 f(x) \succeq 0 \quad \text{for all } x\in\dom f $$

Basic examples¶

Convex functions:

• $a^Tx+b$
• $e^{ax}$
• $x^p$ on $\R_{++}$, for $p\ge 1$ or $p\le0$
• $\|x\|$ (any norm)
• $x\log x$ on $\R_{++}$
• $x^TPx$, for $P\succeq 0$
• $\max\left\{x_1, x_2, \dots, x_n \right\}$

Concave functions:

• $x^p$, for $0\le p \le 1$
• $\log x$, for $x>0$
• $\sqrt{xy}$
• $x^TPx$, for $P\preceq 0$
• $\min\left(x_1, x_2, \dots, x_n \right)$

Less basic examples¶

Convex functions:

• $x^2/y$, for $y>0$
• $x^Tx/y$, for $y>0$
• $x^TY^{-1}x$, for $Y \succ 0$
• $\log \left(e^{x_1} + \cdots + e^{x_n}\right)$
• $\left(\prod_{k=1}^n x_k\right)^{1/n}$
• $x_{[1]} + \cdots + x_{[k]}$ (sum of largest $k$ entries)
• $x \log\left(x/y\right)$, for $x,y>0$
• $\lambda_{\max} \left(X\right)$, for $X\in\SM$

Concave functions:

• $\log \det X$, for $X \succ 0$
• $ \left( \det X \right)^{1/n}$, for $X\succ 0$
• $\lambda_{\min} \left(X\right)$, for $X\in\SM$

Calculus rules¶

• Nonnegative scaling:

$$ f \text{ convex}, \alpha\ge 0 \Longrightarrow \alpha f \text{ convex} $$

• Sum:

$$ f, g \text{ convex} \Longrightarrow f+g \text{ convex} $$

• Affine composition:

$$ f \text{ convex} \Longrightarrow f(Ax+b) \text{ convex} $$

• Pointwise maximum:

$$ f_1,\dots, f_m \text{ convex} \Longrightarrow \max_{i} f_i(x) \text{ convex} $$

• Pointwise supremum

$$ f(x,y) \text{ convex in } x \text{ for each } y\in\mc{A} \Longrightarrow \sup_{y\in\mc{A}} f(x,y) \text{ convex} $$

• Minimization

$$ f(x,y) \text{ convex in } (x,y) \text{ and } C \text{ a convex set} \Longrightarrow \inf_{y\in C} f(x,y) \text{ convex} $$

• Perspective

$$ f(x) \text{ convex }\Longrightarrow t f(x/t) \text{ convex } on \{ (x,t) \ | \ x/t \in \dom f,\ t>0\} $$

• Composition:

\begin{align*} & h \text{ convex nondecreasing}, f \text{ convex} \Longrightarrow h\left(f(x)\right) \text{ convex} \\ & h \text{ convex nonincreasing}, f \text{ concave} \Longrightarrow h\left(f(x)\right) \text{ convex} \\ & h \text{ concave nondecreasing}, f \text{ concave} \Longrightarrow h\left(f(x)\right) \text{ concave} \\ & h \text{ concave nonincreasing}, f \text{ convex} \Longrightarrow h\left(f(x)\right) \text{ concave} \\ \end{align*}

Examples¶

• Piecewise-linear function:

$$ \max_{i=1,\dots,k} \left( a_i^Tx+b_i \right) $$

• Least squares cost:

$$ \|Ax-b\|_2^2 $$

• Regularized least squares cost:

$$ \|Ax-b\|_2^2 + \lambda\|Fx\|_2 + \nu\|x\|_1 $$

• Sum of largest $k$ elements of $x$:

$$ x_{[1]} + \cdots + x_{[k]} $$

• log-barrier:

$$ -\sum_{i} \log\left( -f_i(x) \right), \quad\text{ on } \{x\ | \ f_i(x)<0 \}, f_i\text{ convex} $$

• log-barrier for linear inequalities

$$ -\sum_{i} \log\left( b_i-a_i^Tx \right), \quad\text{ on } \{x\ | \ a_i^Tx<b_i \} $$

• KL divergence:

$$ \sum_{i} \left( u_i\log (u_i/v_i) - u_i + v_i \right), \quad\text{ for } u,v>0 $$

• Support function of a set $C$:

$$ \sup_{y\in{C}} y^Tx $$

• Distance to farthest point in a set $C$:

$$ \sup_{y\in{C}} \|x-y\| $$

• Distance to a convex set $C$:

$$ \inf_{y\in{C}} \|x-y\|, \quad \text{ for convex $C$} $$

• Schur complement:

$$ \bmat{A & B \\ B^T & C }\succeq 0, \ A \succ 0 \Longrightarrow C-B^T A^{-1}B \succeq 0 $$

• Maximum eigenvalue of symmetric matrix $X\in\SM^n$

$$ \lambda_\max(X) = \sup_{\|y\|_2=1} y^TXy $$

A general composition rule¶

$c(x) = h\left( f_1(x), \dots, f_k(x)\right)$ is convex when $h$ is convex and for each $i$

• $h$ is nondecreasing in argument $i$ and $f_i$ is convex, or
• $h$ is nonincreasing in argument $i$ and $f_i$ is concave, or
• $f_i$ is affine

Rough idea: for $x\in\R$ with differentiable $f$ and $h$, $$ c''(x) = f'(x)^T \nabla^2 h\left(f(x)\right)f'(x) + \nabla h\left(f(x)\right)^Tf''(x) $$

Example¶

• For $u,v>0$,

$$ f(u,v) = (u+1) \log \left( (u+1)/\min(u,v)\right) $$

is convex.

• For $x,y<1$,

$$ \frac{(x-y)^2}{1-\max(x,y)} $$

is convex.

• For any $x$,

$$ \sqrt{1+x^2} $$

is convex.

• $\exp g(x)$ is convex if $g$ is convex
• $1/g(x)$ is convex if $g$ is concave and positive
• $\sum_{i=1}^m \log g_i(x)$ is concave if $g_i$ are concave and positive
• $\log \sum_{i=1}^m \exp g_i(x)$ is convex if $g_i$ are convex