Sufficient & Necessary Conditions for Global Optima

Theorem

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

Proof

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

Therefore,

$fleft ( ar{x} +lambda d ight )=fleft ( ar{x} ight )+lambda igtriangledown fleft ( ar{x} ight )^T d+lambda^2d^THleft ( ar{x} ight )d+lambda^2d^THleft ( ar{x} ight )d+$

$lambda^2left | d ight |^2eta left ( ar{x}, lambda d ight )$

But $igtriangledown fleft ( ar{x} ight )=0$ and $etaleft ( ar{x}, lambda d ight ) ightarrow 0$ as $lambda ightarrow 0$

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

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

Theorem

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

Proof

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

$igtriangledown fleft ( ar{x} ight )^T left ( x-ar{x} ight ) leq fleft (x ight )-fleft (ar{x} ight ),forall x in S$

Since $igtriangledown fleft ( ar{x} ight )=0, fleft ( x ight )geq fleft ( ar{x} ight )$

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

Theorem

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

Then:

$ar{x}$ is a global optimal solution.

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

Proof

Let $ar{x}$ be another global optimal solution to the problem such that $x eq ar{x}$ and $fleft ( ar{x} ight )=fleft ( hat{x} ight )$

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

$Rightarrow fleft ( frac{hat{x}+ar{x}}{2} ight )< frac{1}{2} fleft (ar{x} ight )+frac{1}{2} fleft (hat{x} ight )=fleft (hat{x} ight )$

This is contradiction.

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

Corollary

Let $f:S subset mathbb{R}^n ightarrow mathbb{R}$ be a differentiable convex function where $phi eq Ssubset mathbb{R}^n$ is a convex set. Consider the problem $min fleft (x ight ),x in S$,then $ar{x}$ is an optimal solution if $igtriangledown fleft (ar{x} ight )^Tleft (x-ar{x} ight ) geq 0,forall x in S.$

Proof

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

$Rightarrow fleft (x ight )=fleft (ar{x} ight )geq 0$

$fleft (x ight )=fleft (ar{x} ight )+igtriangledown fleft (ar{x} ight )^Tleft (x-ar{x} ight )+left | x-ar{x} ight |alpha left ( ar{x},x-ar{x} ight )$

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

$Rightarrow fleft (x ight )-fleft (ar{x} ight )=igtriangledown fleft (ar{x} ight )^Tleft (x-ar{x} ight )geq 0$

Corollary

Let f be a differentiable convex function at $ar{x}$,then $ar{x}$ is global minimum iff $igtriangledown fleft (ar{x} ight )=0$

Examples

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

$igtriangledown fleft (x ight )=0 Rightarrow x= -1,0,1$.

$igtriangledown^2fleft (pm 1 ight )=0, igtriangledown^2 fleft (0 ight )=6>0$.

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

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

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

${f} x=1+log x$

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

Thus, this function is strictly convex.

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