Karush-Kuhn-Tucker Optimality Necessary Conditions

Advertisements

Previous Page
Next Page  

Consider the problem −

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

Let $S=\left \{ x \in X:g_i\left ( x \right )\leq 0, \forall i \right \}$

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, $\bigtriangledown g_i\left ( \hat{x} \right), i \in I$ are linearly independent. If $\hat{x}$ solves the above problem locally, then there exists $u_i,i \in I$ such that

$\bigtriangledown f\left ( x\right)+\displaystyle\sum\limits_{i\in I} u_i \bigtriangledown g_i\left ( \hat{x} \right)=0$, $\:\:u_i \geq 0, i \in I$

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

$\bigtriangledown f\left ( \hat{x}\right)+\displaystyle\sum\limits_{i= 1}^m u_i \bigtriangledown g_i\left ( \hat{x} \right)=0$

$u_ig_i\left ( \hat{x} \right)=0, \forall i=1,2,...,m$

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

Example

Consider the following problem −

$min \:f\left ( 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 \geq 0$ and $\hat{x}=\left ( 2,1 \right )$

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

$g_2\left ( x_1, x_2 \right)=x_{1}+2x_2-4$

$g_3\left ( x_1, x_2 \right)=-x_{1}$ and $g_4\left ( x_1,x_2 \right )=-x_2$

Thus the above constraints can be written as −

$g_1 \left ( x_1,x_2 \right)\leq 0, g_2 \left ( x_1,x_2 \right) \leq 0$

$g_3 \left ( x_1,x_2 \right)\leq 0,$ and $g_4 \left ( 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_1 \left ( \hat{x} \right)= \left ( 4,2 \right)$ and

$\bigtriangledown g_2\left ( \hat{x} \right ) =\left ( 1,2 \right )$

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.

Advertisements