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<y}, 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}.

Advertisements
This entry was posted in Uncategorized. Bookmark the permalink.

3 Responses to Notes on Convexity Inequalities

  1. Pingback: Lecture 2: Markov Inequality, Amplification by Independent Trials, Chernoff Bounds | UBC CPSC 536N

  2. Pingback: Lecture 3: Balls and Bins, Congestion Minimization, Quicksort | UBC CPSC 536N

  3. Pingback: Lecture 6: Dimensionality Reduction by the Johnson-Lindenstrauss Lemma | UBC CPSC 536N

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s