1) g i ( x ∗ ) − b i g_{i}(x^*)-b_{i} g i ( x ∗ ) − b i is feasible for i = 1 , 2.... m i=1,2....m i = 1 , 2.... m
Where g i ( x ∗ ) g_{i}(x^*) g i ( x ∗ ) is optional value
Writing the equation in residue form
f ) x ) = 2 x 1 + 3 x 2 − x 1 2 − 2 x 2 2 f)x)=2x_{1}+3x_{2}-x_{1}^2-2x_{2}^{2} f ) x ) = 2 x 1 + 3 x 2 − x 1 2 − 2 x 2 2
g 1 ( x ) = x 1 + 3 x 2 − 6 g_1(x)=x_1+3x_2-6 g 1 ( x ) = x 1 + 3 x 2 − 6
g 2 ( x ) = 5 x 1 + 2 x 2 − 10 g_2(x)=5x_1+2x_2-10 g 2 ( x ) = 5 x 1 + 2 x 2 − 10
Applying the Kuhn-Tucker conditions (Optimality Condition)
2)
( ∂ f ∂ x 1 ∂ f ∂ x 2 ) \begin{pmatrix}
\frac { \partial\>f}{\partial\>x_1} \\\\
\frac{\partial\>f}{\partial\>x_2}
\end{pmatrix} ⎝ ⎛ ∂ x 1 ∂ f ∂ x 2 ∂ f ⎠ ⎞ + λ 1 +\lambda1 + λ 1 ( ∂ g 1 ∂ x 1 ∂ g 1 ∂ x 2 ) \begin{pmatrix}
\frac{\partial\>g_1}{\partial\>x_1} \\\\
\frac{\partial\>g_1}{\partial\>x_2}
\end{pmatrix} ⎝ ⎛ ∂ x 1 ∂ g 1 ∂ x 2 ∂ g 1 ⎠ ⎞ + λ 2 +\lambda2 + λ 2 ( ∂ g 2 ∂ x 1 ∂ g 2 ∂ x 2 ) = 0 \begin{pmatrix}
\frac{\partial\>g_2}{\partial\>x_1} \\\\
\frac{\partial\>g_2}{\partial\>x_2}
\end{pmatrix}=0 ⎝ ⎛ ∂ x 1 ∂ g 2 ∂ x 2 ∂ g 2 ⎠ ⎞ = 0
2 − 2 x 1 + λ 1 + 5 λ 2 = 0...... ( 1 ) 2-2x_1+\lambda_1+5\lambda_2=0......(1) 2 − 2 x 1 + λ 1 + 5 λ 2 = 0...... ( 1 )
3 − 4 x 2 + 3 λ 1 + 2 λ 2 = 0..... ( 2 ) 3-4x_2+3\lambda_1+2\lambda_2=0.....(2) 3 − 4 x 2 + 3 λ 1 + 2 λ 2 = 0..... ( 2 )
Feasibility condition
x 1 + 3 x 2 ≤ 6 x_1+3x_2\le6 x 1 + 3 x 2 ≤ 6 . . . . . . ( 3 ) ......(3) ...... ( 3 )
5 x 1 + 2 x 2 ≤ 10 . . . . . . ( 4 ) 5x_1+2x_2\le10\>\>......(4) 5 x 1 + 2 x 2 ≤ 10 ...... ( 4 )
Complimentary slackness property
λ 1 ( x 1 + 3 x 2 − 6 ) = 0 \lambda_1(x_1+3x_2-6)=0 λ 1 ( x 1 + 3 x 2 − 6 ) = 0 . . . . ( 5 ) ....(5) .... ( 5 )
λ 2 ( 5 x 1 + 2 x 2 − 10 ) = 0 . . . . . ( 6 ) \lambda_2(5x_1+2x_2-10)=0\>.....(6) λ 2 ( 5 x 1 + 2 x 2 − 10 ) = 0 ..... ( 6 )
Non-negativity constraints
λ 1 ≥ 0 , λ 2 ≥ 0 . . . . . ( 7 ) \lambda_1\ge0,\>\>\lambda_2\ge0\>\>.....(7) λ 1 ≥ 0 , λ 2 ≥ 0 ..... ( 7 )
Case (i)
λ 1 = 0 , λ 2 = 0 \lambda_1=0,\lambda_2=0 λ 1 = 0 , λ 2 = 0
From (1) and(2), 2 − 2 x 1 = 0 ⟹ x 1 = 1 2-2x_1=0\implies\>x_1=1 2 − 2 x 1 = 0 ⟹ x 1 = 1
3 − 4 x 2 = 0 ⟹ x 2 = 3 4 3-4x_2=0\implies\>x_2=\frac{3}{4} 3 − 4 x 2 = 0 ⟹ x 2 = 4 3
Point ( 1 , 3 4 ) (1,\frac{3}{4}) ( 1 , 4 3 ) is a KKT point
Case (ii)
λ 1 = 0 , λ 2 ≠ 0 \lambda_1=0,\lambda_2\ne0 λ 1 = 0 , λ 2 = 0
Using (1),(2) and (6)
2 − 2 x 1 + 5 λ 2 = 0 2-2x_1+5\lambda_2=0 2 − 2 x 1 + 5 λ 2 = 0
3 − 4 x 2 + 2 λ 2 = 0 3-4x_2+2\lambda_2=0 3 − 4 x 2 + 2 λ 2 = 0
5 x 1 + 2 x 2 − 10 = 0 5x_1+2x_2-10=0 5 x 1 + 2 x 2 − 10 = 0
x 1 = 2 + 5 λ 2 2 , x 2 = 3 + 2 λ 2 4 x_1=\frac{2+5\lambda_2}{2},\>\>x_2=\frac{3+2\lambda_2}{4} x 1 = 2 2 + 5 λ 2 , x 2 = 4 3 + 2 λ 2
5 ( 2 + 5 λ 2 2 ) + 2 ( 3 + 2 λ 2 4 ) = 0 5(\frac{2+5\lambda_2}{2})+2(\frac{3+2\lambda_2}{4})=0 5 ( 2 2 + 5 λ 2 ) + 2 ( 4 3 + 2 λ 2 ) = 0
54 λ 2 = 14 54\lambda_2=14 54 λ 2 = 14
λ 2 = 7 27 \lambda_2=\frac{7}{27} λ 2 = 27 7
x 1 = 2 + 5 ( 7 27 ) 2 = 89 54 x_1=\frac{2+5(\frac{7}{27})}{2}=\frac{89}{54} x 1 = 2 2 + 5 ( 27 7 ) = 54 89
x 2 = 3 + 2 ( 7 27 ) 4 = 95 108 x_2=\frac{3+2(\frac{7}{27})}{4}=\frac{95}{108} x 2 = 4 3 + 2 ( 27 7 ) = 108 95
This could be a KKT point
Case(iii)
λ 1 ≠ 0 , λ 2 = 0 \lambda_1\ne0,\lambda_2=0 λ 1 = 0 , λ 2 = 0
2 − 2 x 1 + λ 1 = 0 2-2x_1+\lambda_1=0 2 − 2 x 1 + λ 1 = 0
3 − 4 x 2 + 3 λ 1 = 0 3-4x_2+3\lambda_1=0 3 − 4 x 2 + 3 λ 1 = 0
x 1 + 3 x 2 − 6 = 0 x_1+3x_2-6=0 x 1 + 3 x 2 − 6 = 0
x 1 = 2 + λ 1 2 x_1=\frac{2+\lambda_1}{2} x 1 = 2 2 + λ 1 x 2 = 3 + 3 λ 1 4 x_2=\frac{3+3\lambda_1}{4} x 2 = 4 3 + 3 λ 1
2 + λ 1 2 + 3 ( 3 + 3 λ 1 ) 4 = 6 \frac{2+\lambda_1}{2}+\frac{3(3+3\lambda_1)}{4}=6 2 2 + λ 1 + 4 3 ( 3 + 3 λ 1 ) = 6
⟹ λ 1 = 1 \implies\>\lambda_1=1 ⟹ λ 1 = 1
Substituting in x 1 x_1 x 1 and x 2 x_2 x 2
x 1 = 3 2 , x 2 = 3 2 x_1=\frac{3}{2},\>\>x_2=\frac{3}{2} x 1 = 2 3 , x 2 = 2 3
But 5 x 1 + 2 x 2 = 10.5 5x_1+2x_2=10.5 5 x 1 + 2 x 2 = 10.5
This violate ......(4)
∴ ( 3 2 , 3 2 ) \therefore(\frac{3}{2},\frac{3}{2}) ∴ ( 2 3 , 2 3 ) is not a KKT point.
Case (iv)
λ 1 ≠ 0 , λ 2 ≠ 0 \lambda_1\ne0,\>\lambda_2\ne0 λ 1 = 0 , λ 2 = 0
2 − 2 x 1 + λ 1 + 5 λ 2 = 0 . . . . . . ( i ) 2-2x_1+\lambda_1+5\lambda_2=0\>......(i) 2 − 2 x 1 + λ 1 + 5 λ 2 = 0 ...... ( i )
3 − 4 x 2 + 3 λ 1 + 2 λ 2 = 0 . . . . ( i i ) 3-4x_2+3\lambda_1+2\lambda_2=0\>....(ii) 3 − 4 x 2 + 3 λ 1 + 2 λ 2 = 0 .... ( ii )
x 1 + 3 x 2 = 6 . . . . . ( i i i ) x_1+3x_2=6\>.....(iii) x 1 + 3 x 2 = 6 ..... ( iii )
5 x 1 + 2 x 2 = 10 . . . . . ( i v ) 5x_1+2x_2=10\>.....(iv) 5 x 1 + 2 x 2 = 10 ..... ( i v )
Solving (iii) and (iv)
5 x 1 + 15 x 2 = 30 5x_1+15x_2=30 5 x 1 + 15 x 2 = 30
5 x 1 + 2 x 2 = 10 5x_1+2x_2=10 5 x 1 + 2 x 2 = 10
⟹ 13 x 2 = 20 \implies13x_2=20 ⟹ 13 x 2 = 20
x 2 = 20 13 x_2=\frac{20}{13} x 2 = 13 20
x 1 = 18 13 x_1=\frac{18}{13} x 1 = 13 18
Substituting x 1 x_1 x 1 and x 2 x_2 x 2 in (i) and (ii)
λ 1 + 5 λ 2 = 10 13 \lambda_1+5\lambda_2=\frac{10}{13} λ 1 + 5 λ 2 = 13 10
3 λ 1 + 2 λ 2 = 41 13 3\lambda_1+2\lambda_2=\frac{41}{13} 3 λ 1 + 2 λ 2 = 13 41
Solving
3 λ 1 + 15 λ 2 = 30 13 3\lambda_1+15\lambda_2=\frac{30}{13} 3 λ 1 + 15 λ 2 = 13 30
3 λ 1 + 2 λ 2 = 41 13 3\lambda_1+2\lambda_2=\frac{41}{13} 3 λ 1 + 2 λ 2 = 13 41
λ 2 = − 11 169 , λ 1 = 185 169 \lambda_2=\frac{-11}{169},\>\lambda_1=\frac{185}{169} λ 2 = 169 − 11 , λ 1 = 169 185
λ 2 < 0 \lambda_2<0 λ 2 < 0
This violates (7)
z = 2 x 1 + 3 x 2 − x 1 2 − 2 x 2 2 z=2x_1+3x_2-x_1^2-2x_2^2 z = 2 x 1 + 3 x 2 − x 1 2 − 2 x 2 2
Substituting point ( 1 , 3 4 ) (1,\frac{3}{4}) ( 1 , 4 3 )
z = 2 ( 1 ) + 3 ( 3 4 ) − ( 1 ) 2 − 2 ( 3 4 ) 2 z=2(1)+3(\frac{3}{4})-(1)^2-2(\frac{3}{4})^2 z = 2 ( 1 ) + 3 ( 4 3 ) − ( 1 ) 2 − 2 ( 4 3 ) 2
= 2.125 =2.125 = 2.125
Substituting point ( 89 54 , 95 108 ) (\frac{89}{54},\frac{95}{108}) ( 54 89 , 108 95 )
z = 2 ( 89 54 ) + 3 ( 95 108 − ( 89 54 ) 2 − 2 ( 95 108 ) 2 z=2(\frac{89}{54})+3(\frac{95}{108}-(\frac{89}{54})^2-2(\frac{95}{108})^2 z = 2 ( 54 89 ) + 3 ( 108 95 − ( 54 89 ) 2 − 2 ( 108 95 ) 2
= 1.671296 =1.671296 = 1.671296
Minimum z = 1.671296 z=1.671296 z = 1.671296
at point ( 89 54 , 95 108 ) (\frac{89}{54},\frac{95}{108}) ( 54 89 , 108 95 )
Comments