Necessary Conditions

Theorem

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

Let $f:X rightarrow mathbb{R}$ and $g_i:X rightarrow 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 bigtriangledown fleft ( hat{x} right )+displaystylesumlimits_{iin I} u_i bigtriangledown g_i left ( hat{x} right )$=0

where $u_0,u_i geq 0,i in I$ and $left ( u_0, u_I right ) neq left ( 0,0 right )$

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

$u_0 bigtriangledown fleft ( hat{x}right )+displaystylesumlimits_{i=1}^m u_i bigtriangledown g_ileft ( hat{x} right )=0$

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

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

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

Remarks

• $u_i$ are called Lagrangian multipliers.

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

• The requirement $u_0 bigtriangledown fleft (hat{x} right )+displaystylesumlimits_{i=1}^m u-i bigtriangledown g_ileft ( x right )=0$ is called dual feasibility condition.

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

• Together the primal feasible condition, dual feasibility condition and complimentary slackness are called Fritz-John Conditions.

Sufficient Conditions

Theorem

If there exists an $varepsilon$-neighbourhood of $hat{x}N_varepsilon left ( hat{x} right ),varepsilon >0$ such that f is pseudoconvex over $N_varepsilon left ( hat{x} right )cap S$ and $g_i,i in I$ are strictly pseudoconvex over $N_varepsilon left ( hat{x}right )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 right )=left ( x_1-3 right )^2+left ( x_2-2 right )^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 right )$

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

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

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

  Thus the above constraints can be written as −

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

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

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

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

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

  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_2right )=-x_1$.

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

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

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

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

  Thus the above constraints can be wriiten as −

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

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

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

  $bigtriangledown fleft (hat{x} right )=left (-1,0right )$

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

  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.