12 Notation and definitions

$\mathbb{R}$ and $\mathbb{Z}$ denote the sets of real numbers and integers, respectively. ${\mathbb{R}}^n$ denotes the set of $n$-dimensional vectors of real numbers (and similarly for ${\mathbb{Z}}^n$ and $\{0,1{\}}^n$); in most cases we denote such vectors by lower case letters, e.g., $a\in {\mathbb{R}}^n$. A subscripted value $a_i$ then refers to the $i$-th entry in $a$, i.e.,

$$a=(a_1,a_2,\dots ,a_n).$$

The symbol $e$ denotes the all-ones vector $e=(1,\dots ,1{)}^T$, whose length always follows from the context.

All vectors are interpreted as column-vectors. For $a,b\in {\mathbb{R}}^n$ we use the standard inner product,

$$⟨a,b⟩:=a_1{b}_1+a_2{b}_2+\cdots +a_n{b}_n,$$

which we also write as $a^{T}b:=⟨a,b⟩$. We let ${\mathbb{R}}^{m\times n}$ denote the set of $m\times n$ matrices, and we use upper case letters to represent them, e.g., $B\in {\mathbb{R}}^{m\times n}$ is organized as

$$\begin{array}{r}B=\left[\begin{array}{cccc}{b}_{11}& b_{12}& \dots & b_{1n}\\ b_{21}& b_{22}& \dots & b_{2n}\\ ⋮& ⋮& \ddots & ⋮\\ b_{m1}& b_{m2}& \dots & b_{mn}\end{array}\right]\end{array}$$

For matrices $A,B\in {\mathbb{R}}^{m\times n}$ we use the inner product

$$⟨A,B⟩:=\sum _{i=1}^m\sum _{j=1}^n{a}_{ij}{b}_{ij}.$$

For a vector $x\in {\mathbb{R}}^n$ we have

$$\begin{array}{r}\mathbf{Diag}(x):=\left[\begin{array}{cccc}{x}_1& 0& \dots & 0\\ 0& x_2& \dots & 0\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \dots & x_n\end{array}\right],\end{array}$$

i.e., a square matrix with $x$ on the diagonal and zero elsewhere. Similarly, for a square matrix $X\in {\mathbb{R}}^{n\times n}$ we have

$$\mathbf{diag}(X):=(x_{11},x_{22},\dots ,x_{nn}).$$

A set $S\subseteq {\mathbb{R}}^n$ is convex if and only if for any $x,y\in S$ and $\theta \in [0,1]$ we have

$$\theta x+(1-\theta )y\in S$$

A function $f:{\mathbb{R}}^n\mapsto \mathbb{R}$ is convex if and only if its domain $\mathbf{dom}(f)$ is convex and for all $\theta \in [0,1]$ we have

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

A function $f:{\mathbb{R}}^n\mapsto \mathbb{R}$ is concave if and only if $-f$ is convex. The epigraph of a function $f:{\mathbb{R}}^n\mapsto \mathbb{R}$ is the set

$$\mathbf{epi}(f):=\{(x,t)\mid x\in \mathbf{dom}(f),f(x)\le t\},$$

shown in Fig. 12.1.

Fig. 12.1 The shaded region is the epigraph of the function $f(x)=-\log (x)$.

Thus, minimizing over the epigraph

$$\begin{array}{r}\begin{array}{ll}\text{minimize}& t\\ \text{subject to}& f(x)\le t\end{array}\end{array}$$

is equivalent to minimizing $f(x)$. Furthermore, $f$ is convex if and only if $\mathbf{epi}(f)$ is a convex set. Similarly, the hypograph of a function $f:{\mathbb{R}}^n\mapsto \mathbb{R}$ is the set

$$\mathbf{hypo}(f):=\{(x,t)\mid x\in \mathbf{dom}(f),f(x)\ge t\}.$$

Maximizing $f$ is equivalent to maximizing over the hypograph

$$\begin{array}{r}\begin{array}{ll}\text{maximize}& t\\ \text{subject to}& f(x)\ge t,\end{array}\end{array}$$

and $f$ is concave if and only if $\mathbf{hypo}(f)$ is a convex set.