Proofs you probably weren't taught

We want to prove that

A function f(x), which is differentiable, is convex if and only if its domain is a convex set and if the following inequality condition is satisfied:

$f\left(y\right) \; \geq \; f\left(x\right) + \left( \nabla_x f\left(x\right) \right)^T \left(y - x\right) ; \;\;\;\; \forall x,y \in Domain(f)$

Intuitively, this condition says that the tangent/first-order-taylor-series approximation is globally an under-estimator of f(x).

Proof:

Before beginning the proof, let us first review the fundamental definition of a convex function:

Definition of a convex function: A function f(x) is said to be convex if and only if its domain is a convex set and if it satisfies the following inequality condition:

$\dpi{120} f\left( t y + \left( 1 - t\right) x \right) \leq t f\left( y \right) + \left( 1 - t\right) f\left( x \right)$ $\dpi{120} \forall x,y \in Domain(f) \; and \; t \in \left[ 0, 1 \right]$

Let us assume that f(x) is convex. Then, according to the fundamental definition of convex functions, the following inequality condition must be satisfied:

$\dpi{120} f\left( t y + \left( 1 - t\right) x \right) \leq t f\left( y \right) + \left( 1 - t\right) f\left( x \right) \;\;\;\; (1)$ $\dpi{120} \forall x,y \in Domain(f) \; and \; t \in \left[ 0, 1 \right]$

Now by a simple re-arrangement of terms we can rewrite Eq.(1) as follows:

$\dpi{120} f\left( t y + \left( 1 - t\right) x \right) \leq t f\left( y \right) + \left( 1 - t\right) f\left( x \right)$

$\dpi{120} \implies f\left( x + t \left( y - x\right)\right) \leq f\left( x \right) + t \left(f\left(y \right ) - f\left(x \right ) \right )$

$\dpi{120} \implies f\left( x + t \left( y - x\right)\right) - f\left( x \right) \leq t \left(f\left(y \right ) - f\left(x \right ) \right )$

$\dpi{120} \implies \frac{f\left( x + t \left( y - x\right)\right) - f\left( x \right)}{t} \leq f\left( y \right) - f\left( x \right)$

$\dpi{120} \implies f\left( y \right) \geq f\left( x \right) + \frac{f\left( x + t \left( y - x\right)\right) - f\left( x \right)}{t} \;\;\;\; (2)$

Now, let

$\dpi{120} g\left( t \right ) = f\left( x + t \left( y - x\right)\right)$

We now express Eq.(2) in terms of g(t), as shown below:

$\dpi{120} f\left( y \right) \geq f\left( x \right) + \frac{g\left(t \right ) - g\left( 0 \right)}{t} \;\;\;\; (3)$

where we have used the fact that g(0) = f(x).

Now taking the limit as t –> 0 on both sides of Eq. (3), we get:

$\dpi{120} f\left( y \right) \geq f\left( x \right) + \lim_{t \to 0} \left\{ \frac{g\left(t \right ) - g\left( 0 \right)}{t} \right\}$

$\dpi{120} \implies f\left( y \right) \geq f\left( x \right) + g^\prime\left(0 \right ) \;\;\;\; (4)$

Now, we need to find g’(o). Instead, let us compute the more general g’(t) which is given below:

$\dpi{120} g^\prime\left(t \right ) = \left( \nabla_x f\left( x + t\left(y-x \right )\right) \right )^T\left(y - x \right )$

Now substituting “t = 0” in the above equation, we get:

$\dpi{120} g^\prime\left(0 \right ) = \left( \nabla_x f\left( x \right) \right )^T\left(y - x \right )$

Now, substituting the above result into Eq. (4), we get:

$f\left(y\right) \; \geq \; f\left(x\right) + \left( \nabla_x f\left(x\right) \right)^T \left(y - x\right) ; \;\;\;\; \forall x,y \in Domain(f) \;\;\;\; (5)$

Notice that this is exactly the inequality condition we wanted to prove.

We have thus proved that:

"if the function f(x) is convex and differentiable then it is necessary that the inequality condition shown in Eq. (5) must be satisfied".

However, our proof is not yet complete

We now have to prove the "sufficiency" part of this condition i.e. we want to prove that:

"if a function f(x) satisfies the inequality condition in Eq. (5) then it sufficient to conclude that f(x) is a convex function".

Showing this part will complete our proof.

To begin with, let us assume that the inequality condition shown in Eq. (5) is satisfied.

Now, consider

$z = t x + \left(1 - t \right )y; \;\;\;\; where \; t \in \left[0,1 \right ]$

Notice that, since Domain(f) is a convex set, z should belong to Domain(f). Also, since we assumed that the inequality condition in Eq. (5) is satisfied, the following two inequalities must hold true:

$\dpi{120} f\left( x \right) \geq f\left( z \right) + \left( \nabla_z f\left( z \right) \right )^T\left(x - z \right) \;\;\;\; (6)$ $\dpi{120} f\left( y \right) \geq f\left( z \right) + \left( \nabla_z f\left( z \right) \right )^T\left(y - z \right) \;\;\;\; (7)$

Now multiplying the inequalities in Eqs. (6) and (7) with t and (1-t) respectively and adding the results we get:

$\dpi{120} t f\left( x \right) + \left(1 - t \right )f\left( y \right) \geq f\left( z \right) + \left( \nabla_z f\left( z \right) \right )^T\left(tx + \left(1 -t \right )y - z \right)$

$\dpi{120} \implies t f\left( x \right) + \left(1 - t \right )f\left( y \right) \geq f\left( tx + \left(1 -t \right )y \right)$

Observe that this is exactly the inequality that f(x) must satisfy in order to be considered as a convex function. Hence, we have proved that, if f(x) satisfies the inequality condition in Eq.(5) then it is sufficient to conclude that f(x) is a convex function.

This ends our proof of the first-order condition of convexity.