Convex Functions

L. El Ghaoui

Convex Functions

Definition
Alternate characterizations of convex functions
Operations that preserve convexity:
- Composition with an affine function
- Point-wise maximum
- Nonnegative weighted sum
- Partial minimum
- Composition with monotone convex functions

Definition
Domain of a function
The domain of a function $f: \mathbf{R}^n \rightarrow \mathbf{R}$ is the set $\operatorname{dom} f \subseteq \mathbf{R}^n$ over which $f$ is well-defined, in other words:

$\operatorname{dom} f:=\left\{x \in \mathbf{R}^n:-\infty<f(x)<+\infty\right\} .$

Here are some examples:
– The function with values $f(x)=\log (x)$ has domain $\operatorname{dom} f=\mathbf{R}_{++}$ .
– The function with values $f(X)=\log \operatorname{det}(X)$ has domain $\operatorname{dom} f=\mathcal{S}_{++}^n$ (the set of positive-definite matrices).
Definition of convexity
A function $f: \mathbf{R}^n \rightarrow \mathbf{R}$ is convex if
1. $\operatorname{dom} f$ is convex;
2. In addition,

$\forall x_1, x_2 \in \operatorname{dom} f, \quad \forall \theta \in[0,1], f(\theta x+(1-\theta) y) \leq \theta f(x)+(1-\theta) f(y) .$

Note that the convexity of the domain is required. For example, the function $f: \mathbf{R} \rightarrow \mathbf{R}$ defined as

$f(x)= \begin{cases}x & \text { if } x \notin[-1,1] \\ +\infty & \text { otherwise }\end{cases}$

is not convex, although is it linear (hence, convex) on its domain $]-\infty,-1) \cup(1,+\infty[$ .
We say that a function is concave if $-f$ is convex.
Examples:
– The function $f: \mathbf{R} \rightarrow \mathbf{R}$ defined as $f(x)=1 / x$ for $x>0$ and $f(x)=+\infty$ for $x \leq 0$ is convex. However, the function with domain the whole line except $\{0\}$ is not, since that domain is not convex.
Alternate characterizations of convexity
Let $f: \mathbf{R}^n \rightarrow \mathbf{R}$ . The following are equivalent conditions for $f$ to be convex.
Epigraph
A function $f: \mathbf{R}^n \rightarrow \mathbf{R}$ is convex if and only if its epigraph

$\text { epi } f:=\left\{(x, t) \in \mathbf{R}^{n+1}: t \geq f(x)\right\}$

is convex. $t I-X \in \mathcal{S}_{+}^n$
First-order condition
If $f$ is differentiable (that is, dom $f$ is open and the gradient exists everywhere on the domain), then $f$ is convex if and only if

$\forall x, y: f(y) \geq f(x)+\nabla f(x)^T(y-x) .$

The geometric interpretation is that the graph of $f$ is bounded below everywhere by anyone of its tangents.
Restriction to a line
The function $f$ is convex if and only if its restriction to /any $\}$ line is convex, meaning that for every $x_0 \in \mathbf{R}^n$ , and $v \in \mathbf{R}^n$ , the function $g(t):=f\left(x_0+t v\right)$ is convex.

Examples:
– Convexity of the log-determinant function.
Second-order condition
Examples:
– Convexity of a quadratic function.
– Convexity of the square-to-linear function.
– Convexity of the log-sum-exp function.
Operations that preserve convexity
Composition with an affine function
Point-wise maximum
The pointwise maximum of a family of convex functions is convex: if $\left(f_\alpha\right)_{\alpha \in \mathcal{A}}$ is a family of convex functions index by $\alpha$ , then the function

$f(x):=\max _{\alpha \in \mathcal{A}} f_\alpha(x)$

is convex. This is one of the most powerful ways to prove convexity.
Examples:
– Dual norm: for a given norm, we define the dual norm as the function

$x \rightarrow \max _{y:\|y\| \leq 1} y^T x .$

This function is convex, as the maximum of convex (in fact, linear) functions (indexed by the vector $y$ ). The dual norm earns its name, as it satisfies the properties of a norm.
– Largest singular value of a matrix: Another example is the largest singular value (see also here) of a matrix $A$ :

$f(A)=\sigma_{\max }(A)=\max _{x:\|x\|_2=1}\|A x\|_2 .$

Here, each function (indexed by $x \in \mathbf{R}^n$ ) $A \rightarrow\|A x\|_2$ is convex, since it is the composition of the Euclidean norm (a convex function) with an affine function $A \rightarrow A x$ .
Nonnegative weighted sum
The nonnegative weighted sum of convex functions is convex.
Example: Negative entropy function.
Partial minimum
If $f$ is a convex function in $x=(y, z)$ , then the function $g(y):=\min _z f(y, z)$ is convex. (Note that joint convexity in $(y, z)$ is essential.)
Example:
– Case when $f$ is quadratic: the Schur complement lemma.
Composition with monotone convex functions
The composition with another function does not always preserve convexity. However, if $f=h \circ g$ , with $h, g$ convex and $h$ increasing, then $f$ is convex.
Indeed, the condition $f(x) \leq t$ is equivalent to the existence of $y$ such that

$h(y) \leq t, \quad g(x) \leq y .$

Example: proving convexity via monotonicity.
More generally, if the functions $g_i: \mathbf{R}^n \rightarrow \mathbf{R}, i=1, \ldots, k$ are convex and $h: \mathbf{R}^k \rightarrow \mathbf{R}$ is convex and non-decreasing in each argument, with dom $g_i=\mathbf{d o m} h=\mathbf{R}$ , then $x \rightarrow(h \circ g)(x):=h\left(g_1(x), \ldots, g_k(x)\right)$ is convex.
For example, if $g_i$ ‘s are convex, then $\log \sum_i \exp g_i$ also is.

Convex Functions

License

Share This Book