Convex Optimization - Differentiable Function

Let S be a non-empty open set in $mathbb{R}^n$,then $f:S ightarrow mathbb{R}$ is said to be differentiable at $hat{x} in S$ if there exist a vector $igtriangledown fleft ( hat{x} ight )$ called gradient vector and a function $alpha :mathbb{R}^n ightarrow mathbb{R}$ such that

$fleft ( x ight )=fleft ( hat{x} ight )+igtriangledown fleft ( hat{x} ight )^Tleft ( x-hat{x} ight )+left | x=hat{x} ight |alpha left ( hat{x}, x-hat{x} ight ), forall x in S$ where

$alpha left (hat{x}, x-hat{x} ight ) ightarrow 0 igtriangledown fleft ( hat{x} ight )=left [ frac{partial f}{partial x_1}frac{partial f}{partial x_2}...frac{partial f}{partial x_n} ight ]_{x=hat{x}}^{T}$

Theorem

let S be a non-empty, open convexset in $mathbb{R}^n$ and let $f:S ightarrow mathbb{R}$ be differentiable on S. Then, f is convex if and only if for $x_1,x_2 in S, igtriangledown fleft ( x_2 ight )^T left ( x_1-x_2 ight ) leq fleft ( x_1 ight )-fleft ( x_2 ight )$

Proof

Let f be a convex function. i.e., for $x_1,x_2 in S, lambda in left ( 0, 1 ight )$

$fleft [ lambda x_1+left ( 1-lambda ight )x_2 ight ]leq lambda fleft ( x_1 ight )+left ( 1-lambda ight )fleft ( x_2 ight )$

$ Rightarrow fleft [ lambda x_1+left ( 1-lambda ight )x_2 ight ]leq lambda left ( fleft ( x_1 ight )-fleft ( x_2 ight ) ight )+fleft ( x_2 ight )$

$ Rightarrowlambda left ( fleft ( x_1 ight )-fleft ( x_2 ight ) ight )geq fleft ( x_2+lambda left ( x_1-x_2 ight ) ight )-fleft ( x_2 ight )$

$Rightarrow lambda left ( fleft ( x_1 ight )-fleft ( x_2 ight ) ight )geq fleft ( x_2 ight )+igtriangledown fleft ( x_2 ight )^Tleft ( x_1-x_2 ight )lambda +$

$left | lambda left ( x_1-x_2 ight ) ight |alpha left ( x_2,lambdaleft (x_1 - x_2 ight )-fleft ( x_2 ight ) ight )$

where $alphaleft ( x_2, lambdaleft (x_1 - x_2 ight ) ight ) ightarrow 0$ as$lambda ightarrow 0$

Dividing by $lambda$ on both sides, we get −

$fleft ( x_1 ight )-fleft ( x_2 ight ) geq igtriangledown fleft ( x_2 ight )^T left ( x_1-x_2 ight )$

Converse

Let for $x_1,x_2 in S, igtriangledown fleft ( x_2 ight )^T left ( x_1-x_2 ight ) leq fleft ( x_1 ight )-f left ( x_2 ight )$

To show that f is convex.

Since S is convex, $x_3=lambda x_1+left (1-lambda ight )x_2 in S, lambda in left ( 0, 1 ight )$

Since $x_1, x_3 in S$, therefore

$fleft ( x_1 ight )-f left ( x_3 ight ) geq igtriangledown fleft ( x_3 ight )^T left ( x_1 -x_3 ight )$

$ Rightarrow fleft ( x_1 ight )-f left ( x_3 ight )geq igtriangledown fleft ( x_3 ight )^T left ( x_1 - lambda x_1-left (1-lambda ight )x_2 ight )$

$ Rightarrow fleft ( x_1 ight )-f left ( x_3 ight )geq left ( 1- lambda ight )igtriangledown fleft ( x_3 ight )^T left ( x_1 - x_2 ight )$

Since, $x_2, x_3 in S$ therefore

$fleft ( x_2 ight )-fleft ( x_3 ight )geq igtriangledown fleft ( x_3 ight )^Tleft ( x_2-x_3 ight )$

$Rightarrow fleft ( x_2 ight )-fleft ( x_3 ight )geq igtriangledown fleft ( x_3 ight )^Tleft ( x_2-lambda x_1-left ( 1-lambda ight )x_2 ight )$

$Rightarrow fleft ( x_2 ight )-fleft ( x_3 ight )geq left ( -lambda ight )igtriangledown fleft ( x_3 ight )^Tleft ( x_1-x_2 ight )$

Thus, combining the above equations, we get −

$lambda left ( fleft ( x_1 ight )-fleft ( x_3 ight ) ight )+left ( 1- lambda ight )left ( fleft ( x_2 ight )-fleft ( x_3 ight ) ight )geq 0$

$Rightarrow fleft ( x_3 ight )leq lambda fleft ( x_1 ight )+left ( 1-lambda ight )fleft ( x_2 ight )$

Theorem

let S be a non-empty open convex set in $mathbb{R}^n$ and let $f:S ightarrow mathbb{R}$ be differentiable on S, then f is convex on S if and only if for any $x_1,x_2 in S,left ( igtriangledown f left ( x_2 ight )-igtriangledown f left ( x_1 ight ) ight )^T left ( x_2-x_1 ight ) geq 0$

Proof

let f be a convex function, then using the previous theorem −

$igtriangledown fleft ( x_2 ight )^Tleft ( x_1-x_2 ight )leq fleft ( x_1 ight )-fleft ( x_2 ight )$ and

$igtriangledown fleft ( x_1 ight )^Tleft ( x_2-x_1 ight )leq fleft ( x_2 ight )-fleft ( x_1 ight )$

Adding the above two equations, we get −

$igtriangledown fleft ( x_2 ight )^Tleft ( x_1-x_2 ight )+igtriangledown fleft ( x_1 ight )^Tleft ( x_2-x_1 ight )leq 0$

$Rightarrow left ( igtriangledown fleft ( x_2 ight )-igtriangledown fleft ( x_1 ight ) ight )^Tleft ( x_1-x_2 ight )leq 0$

$Rightarrow left ( igtriangledown fleft ( x_2 ight )-igtriangledown fleft ( x_1 ight ) ight )^Tleft ( x_2-x_1 ight )geq 0$

Converse

Let for any $x_1,x_2 in S,left (igtriangledown f left ( x_2 ight )- igtriangledown f left ( x_1 ight ) ight )^T left ( x_2-x_1 ight )geq 0$

To show that f is convex.

Let $x_1,x_2 in S$, thus by mean value theorem, $frac{fleft ( x_1 ight )-fleft ( x_2 ight )}{x_1-x_2}=igtriangledown fleft ( x ight ),x in left ( x_1-x_2 ight ) Rightarrow x= lambda x_1+left ( 1-lambda ight )x_2$ because S is a convex set.

$Rightarrow fleft ( x_1 ight )- fleft ( x_2 ight )=left ( igtriangledown fleft ( x ight )^T ight )left ( x_1-x_2 ight )$

for $x,x_1$, we know −

$left ( igtriangledown fleft ( x ight )-igtriangledown fleft ( x_1 ight ) ight )^Tleft ( x-x_1 ight )geq 0$

$Rightarrow left ( igtriangledown fleft ( x ight )-igtriangledown fleft ( x_1 ight ) ight )^Tleft ( lambda x_1+left ( 1-lambda ight )x_2-x_1 ight )geq 0$

$Rightarrow left ( igtriangledown fleft ( x ight )- igtriangledown fleft ( x_1 ight ) ight )^Tleft ( 1- lambda ight )left ( x_2-x_1 ight )geq 0$

$Rightarrow igtriangledown fleft ( x ight )^Tleft ( x_2-x_1 ight )geq igtriangledown fleft ( x_1 ight )^Tleft ( x_2-x_1 ight )$

Combining the above equations, we get −

$Rightarrow igtriangledown fleft ( x_1 ight )^Tleft ( x_2-x_1 ight )leq fleft ( x_2 ight )-fleft ( x_1 ight )$

Hence using the last theorem, f is a convex function.

Twice Differentiable function

Let S be a non-empty subset of $mathbb{R}^n$ and let $f:S ightarrow mathbb{R}$ then f is said to be twice differentiable at $ar{x} in S$ if there exists a vector $igtriangledown fleft (ar{x} ight ), a :nXn$ matrix $Hleft (x ight )$(called Hessian matrix) and a function $alpha:mathbb{R}^n ightarrow mathbb{R}$ such that $fleft ( x ight )=fleft ( ar{x}+x-ar{x} ight )=fleft ( ar{x} ight )+igtriangledown fleft ( ar{x} ight )^Tleft ( x-ar{x} ight )+frac{1}{2}left ( x-ar{x} ight )Hleft ( ar{x} ight )left ( x-ar{x} ight )$

where $ alpha left ( ar{x}, x-ar{x} ight ) ightarrow Oasx ightarrow ar{x}$