## Notes on Convexity Inequalities

In the analysis of randomized algorithms, we frequently use various inequalities to simplify expressions or make them easier to work with. These inequalities are usually obvious by plotting them, and proving them just uses basic calculus.

1. Facts from Convex Analysis

Let ${f : S \rightarrow {\mathbb R}}$ be a function defined on an interval ${S \subseteq {\mathbb R}}$.

Definition 1 We say that ${f}$ is convex on ${S}$ if

$\displaystyle f( \lambda x + (1-\lambda) y ) ~\leq~ \lambda f(x) + (1-\lambda) f(y)$

for all ${x, y \in S}$ and all ${\lambda \in [0,1]}$.

Geometrically, this say that the chord connecting the points ${(x,f(x))}$ and ${(y,f(y))}$ lies above the function ${f}$. The following example illustrates that ${f(x)=x^2}$ is convex.

An equivalent statement of this definition is as follows.

Fact 1 Suppose ${f : S \rightarrow {\mathbb R}}$ is convex. Then, for any points ${x, y \in S}$ with ${x, we have

$\displaystyle f(z) ~\leq~ \frac{f(y)-f(x)}{y-x} \cdot (z-x) + f(x)$

for all ${z \in [x,y]}$.

For sufficiently nice functions, one can easily determine convexity by looking at its second derivative.

Fact 2 Suppose ${f : S \rightarrow {\mathbb R}}$ is twice differentiable and that the second derivative ${f''}$ is non-negative on all of ${S}$. Then ${f}$ is convex.

In our example above we used ${f(x) = x^2}$. Its second derivative is ${f''(x)=2}$, which is non-negative, so ${f}$ is convex.

The next fact says that, for convex functions, the linear approximation at any point lies beneath the function.

Fact 3 (Subgradient Inequality) Suppose ${f : S \rightarrow {\mathbb R}}$ is convex, and ${f}$ is differentiable at a point ${x \in S}$. Then

$\displaystyle f(y) ~\geq~ f(x) + f'(x) (y-x),$

for any point ${y \in S}$.

The following example illustrates this for ${f(x)=x^2}$ at the point ${x=0.5}$.

2. The Inequalities

• Inequality 1.${1+y \leq e^y}$.Convexity of ${e^y}$ follows from Fact 2 since its second derivative is ${e^y}$. The inequality follows by applying Fact 3 at the point ${x=0}$.

• Inequality 2.${1/(1+2z) \leq 1-z}$ for all ${z \in [0,1/2]}$.Convexity of ${1/(1+2z)}$ on the set ${S=(0,\infty)}$ follows from Fact 2 since its second derivative is ${8/(1+2z)^3}$. The inequality follows by applying Fact 1 at the points ${x=0}$ and ${y=0.5}$.

• Inequality 3.${e^z \leq 1+(e-1) z}$.As above, convexity of ${e^z}$ follows from Fact 2. The inequality follows by applying Fact 1 at the points ${x=0}$ and ${y=1}$.