A function \(f: D \subseteq \R^n \rightarrow \R\) is convex in its domain \(D\) if:
\[\begin{equation*}
\label{CONVEX}
\forall {\boldsymbol p}, {\boldsymbol w} \in D \text{ and } \forall \lambda \in [0,1] \text{ we have } ~ f\big(\lambda \; {\boldsymbol p} + (1-\lambda)\;{\boldsymbol w}\big)~~ {\le}~~ \lambda \; f({\boldsymbol p}) + (1-\lambda)\; f({\boldsymbol w}) \tag{3.1}
\end{equation*}\]
and the domain \(D\) of the function \(f\) is a convex set.
A function is convex in its domain if, for any two points in its convex domain, the value at any convex combination of the two points is smaller than or equal to the convex combination of the values at those two points.
If \(D=[a,b] \subseteq \R\) (an interval which is by nature a convex set), the graph of a convex function is given by the following picture:
A function \(f: D \subseteq \R^n \rightarrow \R\) is concave in its domain \(D\) if:
\[\begin{equation*}
\label{CONCAVE}
\forall {\boldsymbol p}, {\boldsymbol w} \in D \text{ and } \forall \lambda \in [0,1] \text{ we have } ~ f\big(\lambda \; {\boldsymbol p} + (1-\lambda)\;{\boldsymbol w}\big)~~ {\ge}~~ \lambda \; f({\boldsymbol p}) + (1-\lambda)\; f({\boldsymbol w}) \tag{3.2}
\end{equation*}\]
and the domain \(D\) of the function \(f\) is a convex set.
A function is concave in its domain if, for any two points in its convex domain, the value at any convex combination of the two points is greater than or equal to the convex combination of the values at those two points.
If \(D=[a,b] \subseteq \R\) (an interval which is by nature a convex set), the graph of a concave function is given by the following picture:
In this chapter we also consider nonlinear functions. The convexity of a function is always proved by checking the definition: for arbitrary points \({\boldsymbol p}, {\boldsymbol w}\) of the domain and an arbitrary \(\lambda \in [0,1]\), we verify the inequality of the definition. For the quadratic functions of the first examples, we use the following inequality.
Observation 3.3
For every \(a, b \in \R\) and every \(\lambda \in [0,1]\), we have
For every pair of points \({\boldsymbol p} = \begin{pmatrix} p_1 \\ p_2 \end{pmatrix}, {\boldsymbol w} = \begin{pmatrix} w_1 \\ w_2 \end{pmatrix} \in \R^2\) and every \(\lambda \in [0,1]\), we have:
(with equality). By nature, the domain \(\R^2\) is a convex set. Accordingly, the function is convex in its domain. Since the equality holds, also the inequality with \(\ge\) holds: the function is also concave in its domain.
Example 3.4: a convex quadratic function of two variables
For every pair of points \({\boldsymbol p} = \begin{pmatrix} p_1 \\ p_2 \end{pmatrix}, {\boldsymbol w} = \begin{pmatrix} w_1 \\ w_2 \end{pmatrix} \in \R^2\) and every \(\lambda \in [0,1]\), we have:
In the figure, the segment joining \((p, f(p))\) and \((w, f(w))\) (violet) lies above the graph of \(f\) (blue).
Example 3.6: the minimum of two linear functions is a concave function
Consider the function \(f: [-2,4] \rightarrow \R\), \(f(x) = \min\{\, x+2, \; 4-\frac{1}{2}x \,\}\). For every pair of points \(p, w \in [-2,4]\) and every \(\lambda \in [0,1]\), we have:
The domain \([-2,4]\) is an interval, hence a convex set. Accordingly, the function is concave in its domain.
The two lines meet at \(x=\frac{4}{3}\), where \(f(\frac{4}{3}) = \frac{10}{3}\). For example, with \(p=-1\), \(w=4\) and \(\lambda=\frac{1}{2}\) we obtain \(\lambda \, p + (1-\lambda)\, w = \frac{3}{2}\) and
A norm on \(\R^n\) is a function \(\|\cdot\|: \R^n \rightarrow \R\) such that, for every \({\boldsymbol p}, {\boldsymbol w} \in \R^n\) and every \(\alpha \in \R\):
\(\|{\boldsymbol p}\| \ge 0\), and \(\|{\boldsymbol p}\| = 0\) if and only if \({\boldsymbol p} = {\boldsymbol 0}\) (positivity);
By nature, the domain \(\mathbb{R}^{n}\) is a convex set. Accordingly, the function is convex in its domain. □
Observation 3.7: convexity of every norm
For every norm \(\|\cdot\|\) on \(\R^n\) (in particular \(\|\cdot\|_1\), \(\|\cdot\|_2\), \(\|\cdot\|_q\) with \(q \ge 1\), and \(\|\cdot\|_\infty\)), the function
By nature, the domain \(\mathbb{R}^{n}\) is a convex set. Accordingly, the function is convex in its domain. □
The next proof is more direct and does not require the use of the Cauchy–Schwarz inequality and the inequality \(2ab \le a^2 + b^2\) for every \(a,b \in \mathbb{R}\).
Proof
For every pair of points \(\boldsymbol{p}, \boldsymbol{w} \in \mathbb{R}^n\) and every \(\lambda \in [0,1]\), we have:
The domain \(D\) is a convex set, since \(f\) is convex in \(D\). Accordingly, the function \(-f\) is concave in its domain. The converse is proved in the same way, starting from the inequality of the concave function \(-f\) and multiplying it by \(-1\). □
Observation 3.12
Let \(f, g: D \subseteq \R^n \rightarrow \R\) be convex in \(D\) and let \(\alpha, \beta \ge 0\). Then the function \(\alpha \, f + \beta \, g\) is convex in \(D\). The same holds for concave functions.
Proof
For every pair of points \({\boldsymbol p}, {\boldsymbol w} \in D\) and every \(\lambda \in [0,1]\), we have:
\[
(\alpha f + \beta g)\big(\lambda {\boldsymbol p} + (1-\lambda){\boldsymbol w}\big) \le \lambda \, (\alpha f + \beta g)({\boldsymbol p}) + (1-\lambda) \, (\alpha f + \beta g)({\boldsymbol w})
\]
The domain \(D\) is a convex set, since \(f\) is convex in \(D\). Accordingly, the function \(\alpha f + \beta g\) is convex in its domain. For concave functions the same argument holds with \(\ge\). □
The point-wise maximum of convex functions is itself a convex function: this allows us to combine multiple convex functions into a single one while preserving convexity.
Observation 3.13
For every \(m\) functions \(f_i : D_i \subseteq \R^n \rightarrow \R\) convex in their domains, with \(i \in \{1,2,\dots,m\}\), the function
The domain \(\bigcap_{i=1}^m D_i\) is a convex set, since it is the intersection of convex sets. Accordingly, the function \(f\) is convex in its domain. The statement for the minimum of concave functions follows by applying this one to \(-f_1, \dots, -f_m\). □
The absolute value \(|x| = \max\{x, -x\}\) of Example 3.5 is the maximum of the two functions \(x\) and \(-x\), which are convex (and concave), since the definition holds with equality: \(-\big(\lambda p + (1-\lambda) w\big) = \lambda (-p) + (1-\lambda)(-w)\). The function of Example 3.6 is the minimum of the two functions \(x+2\) and \(4-\frac{1}{2}x\), which are concave for the same reason: \(\big(\lambda p + (1-\lambda) w\big) + 2 = \lambda (p+2) + (1-\lambda)(w+2)\) and \(4-\frac{1}{2}\big(\lambda p + (1-\lambda) w\big) = \lambda \big(4-\frac{1}{2}p\big) + (1-\lambda)\big(4-\frac{1}{2}w\big)\). By the previous observation, we find again that the two functions are convex and concave, respectively.
Example 3.10: maximum of convex functions
Consider the following two convex functions (Examples 3.2 and Example 3.1):
For every pair of points \({\boldsymbol p}\) and \({\boldsymbol w}\) in the set and every \(\lambda \in [0,1]\), the point \(\lambda {\boldsymbol p} + (1-\lambda){\boldsymbol w}\) belongs to \(\bigcap_{i=1}^m D_i\), since \({\boldsymbol p},{\boldsymbol w} \in D_i\) and each domain \(D_i\) is convex, and for every \(i \in \{1,2,\dots,m\}\) we have:
The function \(f_1\) is convex because \(|x_1| = \max\{x_1, -x_1\}\) and \(|x_2| = \max\{x_2, -x_2\}\) are maxima of convex functions (as \(|x| = \max\{x,-x\}\) above), and the sum of convex functions is convex; \(f_2\) is convex by Example 3.3. Also in this case, according to the same observation, the following is a convex set:
It is the square with vertices \((\pm 2, 0)\) and \((0, \pm 2)\) (dashed) cut by the half-plane \(x_1 + x_2 \le 1\) (red line): the quadrilateral with vertices \((-2,0)\), \((0,-2)\), \((\frac{3}{2},-\frac{1}{2})\) and \((-\frac{1}{2},\frac{3}{2})\) shaded in red.
The points that satisfy a finite number of constraints \(f_i({\boldsymbol x}) \le 0\) with convex functions \(f_i\) form a convex set. For instance, every half-space \(\{{\boldsymbol x} \in \R^n : {\boldsymbol a}'{\boldsymbol x} \le b\}\), with \({\boldsymbol a} \in \R^n\) and \(b \in \R\), is a convex set of this kind, since the linear function \({\boldsymbol a}'{\boldsymbol x} - b\) is convex; so is every intersection of finitely many half-spaces, as the polyhedra of linear programming.
