Karush-Kuhn-Tucker Optimapty Necessary Conditions

Consider the problem −

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

Let $S=left { x in X:g_ileft ( x ight )leq 0, forall i ight }$

Let $hat{x} in S$ 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}$. Furthermore, $igtriangledown g_ileft ( hat{x} ight), i in I$ are pnearly independent. If $hat{x}$ solves the above problem locally, then there exists $u_i,i in I$ such that

$igtriangledown fleft ( x ight)+displaystylesumpmits_{iin I} u_i igtriangledown g_ileft ( hat{x} ight)=0$, $::u_i geq 0, i in I$

If $g_i,i in J$ are also differentiable at $hat{x}$. then $hat{x}$, then

$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, forall i=1,2,...,m$

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

Example

Consider the following problem −

$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 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_1 left ( x_1,x_2 ight)leq 0, g_2 left ( x_1,x_2 ight) leq 0$

$g_3 left ( x_1,x_2 ight)leq 0,$ and $g_4 left ( 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_1 left ( 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 Karush-Kuhn-Tucker conditions, we get −

$u_1=frac{1}{3}$ and $u_2=frac{2}{3}$

Thus Karush-Kuhn-Tucker conditions are satisfied.