Convex Functions

Convex Functions

Convex Function

A function \newcommand{\R}{\mathbb{R}} f\colon A \to \R is convex if $A\subset {\mathbb{R}}^n$ is convex and $f(\theta x+(1-\theta )y)\le \theta f(x)+(1-\theta )f(y)$for all $x,y\in A$ and $0\le \theta \le 1$. It is strictly convex if the above inequality is strict.

Strongly Convex

A convex function $f$ is strongly convex if it has minimum positive curvature everywhere. That is $f$ is strongly convex on $S$ if there exists an $m>0$ such that ${\nabla }^{2}f(x)⪰mI\text{for all x∈S}$

Concave Function

A function $f:A\to \mathbb{R}$ is concave if $-f$ is convex.

e.g. Affine functions are convex and concave; All norms are convex.

Thrm A function $f:{\mathbb{R}}^n\to \mathbb{R}$ is convex if and only if the function $g:\mathbb{R}\to \mathbb{R}$ that
$g(t)=f(x+tv),\text{dom}g=\{t\mid x+tv\in \text{dom}f\}$
is convex for any $x\in \text{dom}f,v\in {\mathbb{R}}^n$

Def Extended-Value Extension
The extended-value extension $\tilde{f}$ of $f$ is
$\tilde{f}(x)=\{\begin{array}{ll}f(x),& x\in \text{dom}f\\ \infty ,& x\notin \text{dom}f\end{array}$

Convex Conditions

Thrm $f:{\mathbb{R}}^n\to \mathbb{R}$ is differentiable if $\text{dom}f$ is open and the gradient $\nabla f(x)$ exists at each $x\in \text{dom}f$.

Thrm First-Order Condition
A differentiable $f$ with convex domain is convex iff: $f(y)\ge f(x)+\nabla f(x{)}^{\top }(y-x)\text{ for all }x,y\in \text{dom}f$

Thrm $f$ is twice differentiable if $\text{dom}f$ is open and the Hessian ${\nabla }^{2}f(x)\in {\mathbb{S}}^n$ exists at each $x\in \text{dom}f$

Thrm Second-Order Condition
For twice differentiable $f$ with convex domain, $f$ is convex if and only if ${\nabla }^{2}f(x)⪰0$ for all $x\in \text{dom}f$.

Operations that Preserve Convexity

Here are some practical 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)⪰0$.
3. Show that $f$ is obtained from simple convex functions by operations that preserve convexity.
   

Def Perspective
The perspective of a function $f:{\mathbb{R}}^n\to \mathbb{R}$ is the function $g:{\mathbb{R}}^n\times \mathbb{R}\to \mathbb{R}$ such that $g(x,t)=tf(\frac{x}{t}),\text{dom}g=\{(x,t)\mid x/t\in \text{dom}f,t>0\}$

Legendre Transformation

The conjugate or Legendre transformation of a convex function $f$ is $f^{\ast }(y)={\sup }_{x\in \text{dom}f}(y^{\top }x-f(x))$

Proposition

The Legendre transformation is involutive: $f^{\ast \ast }=f$ for convex $f$.

Proof

Young's Inequality

Suppose $f$ is convex, then $yx\le f(x)+f^{\ast }(y)$

Lemma

The values of a quadratic form $f$ and of its Legendre transformation $f^{\ast }$ coincide at corresponding points: $f(\mathbf{x})=f^{\ast }(\nabla f(\mathbf{x}))$

Operations that Preserve Convexity

The following operations preserve convexity:

• Nonnegative Multiple: $\alpha f$ is convex if $f$ is convex and $\alpha \ge 0$
• Sum: $f_1+f_2$ is convex if $f_1,f_2$ convex (extends to infinite sums, integrals)
• Composition with Affine Function: $f(Ax+b)$ is convex if $f$ is convex.
• Pointwise Maximum: if $f_1,f_2,\dots ,f_n$ are convex, then $f(x)=\max \{f_1(x),f_2(x),\dots ,f_n(x)\}$ is convex.
• Pointwise Supremum: if $f(x,y)$ is convex in $X$ for each $y\in \mathcal{A}$, then $g(x)={\sup }_{y\in \mathcal{A}}f(x,y)$ is convex.
• Composition with Scalar Map: Suppose $g:{\mathbb{R}}^n\to \mathbb{R}$ and $h:\mathbb{R}\to \mathbb{R}$ and $f=h\circ g$, then $f$ is convex if either
  • $g$ convex, $h$ convex, $\tilde{h}$ nondecreasing
  • $g$ concave, $h$ convex, $\tilde{h}$ nonincreasing
• Composition with Vector Map: Suppose $g:{\mathbb{R}}^n\to {\mathbb{R}}^k$ and $h:\mathbb{R}\to \mathbb{R}$ and $f=h\circ g$, then $f$ is convex if either
  • $g$ convex, $h$ convex, $\tilde{h}$ nondecreasing
  • $g$ concave, $h$ convex, $\tilde{h}$ nonincreasing
• Perspective Transformation: The perspective of $f:{\mathbb{R}}^n\to \mathbb{R}$ is convex if $f$ is convex.
• Conjugate: The conjugate of a function is always convex.
  

Epigraph and Sublevel Set

Def Sublevel Set
The $\alpha$-sublevel set of $f:{\mathbb{R}}^n\to \mathbb{R}$ is
$C_{\alpha }=\{x\in \text{dom}f\mid f(x)\le \alpha \}$

Prop Sublevel sets of convex functions are convex.

Epigraph

The epigraph of $f:{\mathbb{R}}^2\to \mathbb{R}$ is $\text{epi}f=\{(x,t)\in {\mathbb{R}}^{n+1}\mid x\in \text{dom}f,f(x)\le t\}$

Prop $f$ is convex if and only if $\text{epi}f$ is a convex set

Quasiconvex

Quasiconvex

$f:{\mathbb{R}}^n\to \mathbb{R}$ is quasiconvex if $\text{dom}f$ is convex and the sublevel sets $S_{\alpha }=\{x\in \text{dom}f\mid f(x)\le \alpha \}$ are convex for all $\alpha$. Equivalently, $f$ is quasiconvex if for all $x,y\in \text{dom}f$ and $\theta \in [0,1]$ we have $f(\theta x+(1-\theta )y)\le \max \left\{f(x),f(y)\right\}$We say $f$ is strictly quasiconvex if $f(\theta x+(1-\theta )y)<\max \left\{f(x),f(y)\right\}$

Def Quasiconcave
$f$ is quasiconcave if $-f$ is quasiconvex.

Prop All convex functions are quasiconvex.

Def Quasilinear
$f$ is quasilinear if it is quasiconvex and quasiconcave.

Thrm Modified Jensen Inequality
Function $f$ is quasiconvex if and only if: $0\le \theta \le 1⟹f(\theta x+(1-\theta )y)\le \max \{f(x),f(y)\}$

Thrm First-order Condition
Differentiable $f$ with convex domain is quasiconvex if and only if: $f(y)\le f(x)⟹\nabla f(x{)}^{\mathrm{T}}(y-x)\le 0$

Prop Sums of quasiconvex functions are not necessarily quasiconvex

Generalized Convexity

Def $f:{\mathbb{R}}^n\to {\mathbb{R}}^m$ is $K$-convex if $\text{dom}f$ is convex and $f(\theta x+(1-\theta )y){⪯}_K\theta f(x)+(1-\theta )f(y)$for all $x,y\in \text{dom}f,0\le \theta \le 1$.
e.g. $f:{\mathbb{S}}^m\to {\mathbb{S}}^m$, $f(X)=X^2$ is ${\mathbb{S}}_{+}^m$-convex.