Convex Optimization - Fritz-John Conditions

Necessary Conditions

Theorem

Consider the problem − $min fleft ( x ight )$ such that $x in X$ where X is an open set in $mathbb{R}^n$ and let $g_i left ( x ight ) leq 0, forall i =1,2,....m$.

Let $f:X ightarrow mathbb{R}$ and $g_i:X ightarrow mathbb{R}$

Let $hat{x}$ be a feasible solution and let f and $g_i, i in I$ are differentiable at $hat{x}$ and $g_i, i in J$ are continuous at $hat{x}$.

If $hat{x}$ solves the above problem locally, then there exists $u_0, u_i in mathbb{R}, i in I$ such that $u_0 igtriangledown fleft ( hat{x} ight )+displaystylesumpmits_{iin I} u_i igtriangledown g_i left ( hat{x} ight )$=0

where $u_0,u_i geq 0,i in I$ and $left ( u_0, u_I ight ) eq left ( 0,0 ight )$

Furthermore, if $g_i,i in J$ are also differentiable at $hat{x}$, then above conditions can be written as −

$u_0 igtriangledown fleft ( hat{x} ight )+displaystylesumpmits_{i=1}^m u_i igtriangledown g_ileft ( hat{x} ight )=0$

$u_ig_ileft (hat{x} ight )$=0

$u_0,u_i geq 0, forall i=1,2,....,m$

$left (u_0,u ight ) eq left ( 0,0 ight ), u=left ( u_1,u_2,s,u_m ight ) in mathbb{R}^m$

Remarks

$u_i$ are called Lagrangian multippers.

The condition that $hat{x}$ be feasible to the given problem is called primal feasible condition.

The requirement $u_0 igtriangledown fleft (hat{x} ight )+displaystylesumpmits_{i=1}^m u-i igtriangledown g_ileft ( x ight )=0$ is called dual feasibipty condition.

The condition $u_ig_ileft ( hat{x} ight )=0, i=1, 2, ...m$ is called comppmentary slackness condition. This condition requires $u_i=0, i in J$

Together the primal feasible condition, dual feasibipty condition and comppmentary slackness are called Fritz-John Conditions.

Sufficient Conditions

Theorem

If there exists an $varepsilon$-neighbourhood of $hat{x}N_varepsilon left ( hat{x} ight ),varepsilon >0$ such that f is pseudoconvex over $N_varepsilon left ( hat{x} ight )cap S$ and $g_i,i in I$ are strictly pseudoconvex over $N_varepsilon left ( hat{x} ight )cap S$, then $hat{x}$ is local optimal solution to problem described above. If f is pseudoconvex at $hat{x}$ and if $g_i, i in I$ are both strictly pseudoconvex and quasiconvex function at $hat{x},hat{x}$ is global optimal solution to the problem described above.

Example

$min :fleft ( x_1,x_2 ight )=left ( x_1-3 ight )^2+left ( x_2-2 ight )^2$

such that $x_{1}^{2}+x_{2}^{2} leq 5, x_1+2x_2 leq 4, x_1,x_2 geq 0$ And $hat{x}=left ( 2,1 ight )$

Let $g_1left (x_1,x_2 ight )=x_{1}^{2}+x_{2}^{2} -5,$

$g_2left (x_1,x_2 ight )=x_1+2x_2-4,$

$g_3left (x_1,x_2 ight )=-x_1$ and $g_4left ( x_1, x_2 ight )= -x_2$.

Thus the above constraints can be written as −

$g_1left (x_1,x_2 ight )leq 0,$

$g_2left (x_1,x_2 ight )leq 0,$

$g_3left (x_1,x_2 ight )leq 0$ and

$g_4left (x_1,x_2 ight )leq 0$ Thus, $I = left {1,2 ight }$ therefore, $u_3=0,u_4=0$

$igtriangledown f left (hat{x} ight )=left (2,-2 ight ),igtriangledown g_1left (hat{x} ight )=left (4,2 ight )$ and $igtriangledown g_2left (hat{x} ight )=left (1,2 ight )$

Thus putting these values in the first condition of Fritz-John conditions, we get −

$u_0=frac{3}{2} u_2, ::u_1= frac{1}{2}u_2,$ and let $u_2=1$, therefore $u_0= frac{3}{2},::u_1= frac{1}{2}$

Thus Fritz John conditions are satisfied.

$min fleft (x_1,x_2 ight )=-x_1$.

such that $x_2-left (1-x_1 ight )^3 leq 0$,

$-x_2 leq 0$ and $hat{x}=left (1,0 ight )$

Let $g_1left (x_1,x_2 ight )=x_2-left (1-x_1 ight )^3$,

$g_2left (x_1,x_2 ight )=-x_2$

Thus the above constraints can be wriiten as −

$g_1left (x_1,x_2 ight )leq 0,$

$g_2left (x_1,x_2 ight )leq 0,$

Thus, $I=left {1,2 ight }$

$igtriangledown fleft (hat{x} ight )=left (-1,0 ight )$

$igtriangledown g_1 left (hat{x} ight )=left (0,1 ight )$ and $g_2 left (hat{x} ight )=left (0, -1 ight )$

Thus putting these values in the first condition of Fritz-John conditions, we get −

$u_0=0,:: u_1=u_2=a>0$

Thus Fritz John conditions are satisfied.