# 12 Notation and definitions¶

$$\R$$ and $$\integral$$ denote the sets of real numbers and integers, respectively. $$\R^n$$ denotes the set of $$n$$-dimensional vectors of real numbers (and similarly for $$\integral^n$$ and $$\{0,1\}^n$$); in most cases we denote such vectors by lower case letters, e.g., $$a \in \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,\ldots,1)^T$$, whose length always follows from the context.

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

$\langle a, b \rangle := a_1 b_1 + a_2 b_2 + \dots + a_n b_n,$

which we also write as $$a^T b := \langle a, b\rangle$$. We let $$\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 \R^{m\times n}$$ is organized as

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

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

$\langle A, B \rangle := \sum_{i=1}^m \sum_{j=1}^n a_{ij} b_{ij}.$

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

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

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

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

A set $$S\subseteq \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:\R^n \mapsto \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) \leq \theta f(x) + (1-\theta) f(y).$

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

$\mathbf{epi}(f) := \{ (x,t) \mid x \in \mathbf{dom}(f), \: f(x) \leq 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{split}\begin{array}{ll} \mbox{minimize}& t\\ \mbox{subject to}& f(x) \leq t \end{array}\end{split}$

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:\R^n \mapsto \R$$ is the set

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

Maximizing $$f$$ is equivalent to maximizing over the hypograph

$\begin{split}\begin{array}{ll} \mbox{maximize} & t\\ \mbox{subject to} & f(x) \geq t, \end{array}\end{split}$

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