Theorem

Let f be twice differentiable function. If $bar{x}$ is a local minima, then $bigtriangledown fleft ( bar{x} right )=0$ and the Hessian matrix $Hleft ( bar{x} right )$ is a positive semidefinite.

Proof

Let $d in mathbb{R}^n$. Since f is twice differentiable at $bar{x}$.

Therefore,

$fleft ( bar{x} +lambda dright )=fleft ( bar{x} right )+lambda bigtriangledown fleft ( bar{x} right )^T d+lambda^2d^THleft ( bar{x} right )d+lambda^2d^THleft ( bar{x} right )d+$

$lambda^2left | d right |^2beta left ( bar{x}, lambda d right )$

But $bigtriangledown fleft ( bar{x} right )=0$ and $betaleft ( bar{x}, lambda d right )rightarrow 0$ as $lambda rightarrow 0$

$Rightarrow fleft ( bar{x} +lambda d right )-fleft ( bar{x} right )=lambda ^2d^THleft ( bar{x} right )d$

Since $bar{x }$ is a local minima, there exists a $delta > 0$ such that $fleft ( x right )leq fleft ( bar{x}+lambda d right ), forall lambda in left ( 0,delta right )$

Theorem

Let $f:S rightarrow mathbb{R}^n$ where $S subset mathbb{R}^n$ be twice differentiable over S. If $bigtriangledown fleft ( xright )=0$ and $Hleft ( bar{x} right )$ is positive semi-definite, for all $x in S$, then $bar{x}$ is a global optimal solution.

Proof

Since $Hleft ( bar{x} right )$ is positive semi-definite, f is convex function over S. Since f is differentiable and convex at $bar{x}$

$bigtriangledown fleft ( bar{x} right )^T left ( x-bar{x} right ) leq fleft (xright )-fleft (bar{x}right ),forall x in S$

Since $bigtriangledown fleft ( bar{x} right )=0, fleft ( x right )geq fleft ( bar{x} right )$

Hence, $bar{x}$ is a global optima.

Theorem

Suppose $bar{x} in S$ is a local optimal solution to the problem $f:S rightarrow mathbb{R}$ where S is a non-empty subset of $mathbb{R}^n$ and S is convex. $min :fleft ( x right )$ where $x in S$.

Then:

• $bar{x}$ is a global optimal solution.

• If either $bar{x}$ is strictly local minima or f is strictly convex function, then $bar{x}$ is the unique global optimal solution and is also strong local minima.

Proof

Let $bar{x}$ be another global optimal solution to the problem such that $x neq bar{x}$ and $fleft ( bar{x} right )=fleft ( hat{x} right )$

Since $hat{x},bar{x} in S$ and S is convex, then $frac{hat{x}+bar{x}}{2} in S$ and f is strictly convex.

$Rightarrow fleft ( frac{hat{x}+bar{x}}{2} right )

This is contradiction.

Hence, $hat{x}$ is a unique global optimal solution.

Corollary

Let $f:S subset mathbb{R}^n rightarrow mathbb{R}$ be a differentiable convex function where $phi neq Ssubset mathbb{R}^n$ is a convex set. Consider the problem $min fleft (xright ),x in S$,then $bar{x}$ is an optimal solution if $bigtriangledown fleft (bar{x}right )^Tleft (x-bar{x}right ) geq 0,forall x in S.$

Proof

Let $bar{x}$ is an optimal solution, i.e, $fleft (bar{x}right )leq fleft (xright ),forall x in S$

$Rightarrow fleft (xright )=fleft (bar{x}right )geq 0$

$fleft (xright )=fleft (bar{x}right )+bigtriangledown fleft (bar{x}right )^Tleft (x-bar{x}right )+left | x-bar{x} right |alpha left ( bar{x},x-bar{x} right )$

where $alpha left ( bar{x},x-bar{x} right )rightarrow 0$ as $x rightarrow bar{x}$

$Rightarrow fleft (xright )-fleft (bar{x}right )=bigtriangledown fleft (bar{x}right )^Tleft (x-bar{x}right )geq 0$

Corollary

Let f be a differentiable convex function at $bar{x}$,then $bar{x}$ is global minimum iff $bigtriangledown fleft (bar{x}right )=0$

Examples

• $fleft (xright )=left (x^2-1right )^{3}, x in mathbb{R}$.

  $bigtriangledown fleft (xright )=0 Rightarrow x= -1,0,1$.

  $bigtriangledown^2fleft (pm 1 right )=0, bigtriangledown^2 fleft (0 right )=6>0$.

  $fleft (pm 1 right )=0,fleft (0 right )=-1$

  Hence, $fleft (x right ) geq -1=fleft (0 right )Rightarrow fleft (0 right ) leq f left (x right)forall x in mathbb{R}$

• $fleft (x right )=xlog x$ defined on $S=left { x in mathbb{R}, x> 0 right }$.

  ${f}”x=1+log x$

  ${f}””x=frac{1}{x}>0$

  Thus, this function is strictly convex.

• $f left (x right )=e^{x},x in mathbb{R}$ is strictly convex.