Convexity

Alexei Gilchrist

2 Convexity

Quick introduction to convex sets, convex functions and Jensen’s inequality

❦

1 A convex set

A set \(C\) is convex if for all \(a,b\in C\) and \(0<\lambda<1\), the element \(\lambda a + (1-\lambda)b\) is also in \(C\).

Geometrically, if a line is connected between \(a\) and \(b\) then every point on the line is also in the set as depicted below.

2 A convex function

A function \(f\) is convex over the convex domain \(C\) if for all \(x_{1},x_{2}\in C\) and \(\lambda\in[0,1]\)

\[\begin{equation*}f(\lambda x_{1}+(1-\lambda)x_{2}) \le \lambda f(x_{1}) + (1-\lambda)f(x_{2})\end{equation*}\]

The function is strictly convex if equality only holds for \(\lambda=0\) or \(\lambda=1\). Note that if \(-f\) is convex we call the function concave.

If the domain is the real numbers and \(f\) is twice differentiable then \(d^{2}f/dx^{2}\ge 0\) implies \(f\) is convex, and if \(d^{2}f/dx^{2}> 0\) then \(f\) is strictly convex.

3 Jensen’s inequality

For a convex function \(f(x)\),

\[\begin{equation*}\langle f(x) \rangle \ge f(\langle x\rangle)\end{equation*}\]

where \(\langle\cdot\rangle\) denotes average.

If equality holds \(\langle f(x) \rangle = f(\langle x\rangle)\) and \(f(x)\) is strictly convex, then \(x_{j}=\langle x\rangle\).

Jensen’s inequality can be easily proved by induction on the number of terms in the average:

Proof

With \(m\) terms, the averages are \(\langle x\rangle = \sum_{j=1}^{m} p_{j} x_{j}\) and \(\langle f(x) \rangle= \sum_{j=1}^{m}p_{j} f(x_{j})\) where \(p_{j}\) is the probability of \(x_{j}\). The case \(m=1\) is trivially true. The case \(m=2\) is

\[\begin{equation*}p_{1}f(x_{1})+p_{2}f(x_{2}) \ge f(p_{1}x_{1}+p_{2}x_{2})\end{equation*}\]

which is just the definition of convexity for \(f(x)\). Now assume the result holds for \(m=n\) and look at \(m=n+1\). First note that if \(p_{1}=1\) then all the other probabilities are zero and we are back to the case \(m=1\) so we can assume \(p_{1}<1\).

\[\begin{align*}\langle f(x) \rangle\equiv \sum_{j=1}^{m+1}p_{j} f(x_{j}) &= p_{1}f(x_{1})+ (1-p_{1})\sum_{j=2}^{n+1}\frac{p_{j}}{1-p_{1}}f(x_{j})\\ &\ge p_{1}f(x_{1})+(1-p_{1})f\left(\sum_{j=2}^{n+1}\frac{p_{j}}{1-p_{1}}x_{j}\right)\\ &\ge f\left(p_{1}x_{1}+(1-p_{1})\sum_{j=2}^{n+1}\frac{p_{j}}{1-p_{1}}x_{j} \right)\\ &= f\left(\sum_{j=1}^{m+1}x_{j}\right) \equiv f(\langle x \rangle)\end{align*}\]

The first inequality is from using the assumed expression for \(m=n\), and the second from the expression for \(m=2\).☐