Numerical analysis kuhn tucker eqn

GCE Kannur

1. D Nagesh Kumar, IIScOptimization Methods: M2L5
1
Optimization using Calculus
Kuhn-Tucker
Conditions

2. D Nagesh Kumar, IISc Optimization Methods: M2L5
2
Introduction ™
Optimization with multiple decision variables and equality
constraint : Lagrange Multipliers.
™
Optimization with multiple decision variables and inequality
constraint : Kuhn-Tucker (KT) conditions
™
KT condition: Both necessary and sufficient if the objective
function is concave and each constraint is linear or each constraint function is concave, i.e. the prob lems belongs to a class called the
convex programming problems.

3. D Nagesh Kumar, IISc Optimization Methods: M2L5
3
Kuhn Tucker Conditions: Optimization
Model
Consider the following optimization problem
Minimize f(X)
subject to
g
j(X) 0 for j=1,2,…,p
where the decision variable vector
X=[x
1
,x
2
,…,x
n
]
≤

4. D Nagesh Kumar, IISc Optimization Methods: M2L5
4
Kuhn Tucker Conditions
1
0 1,2,...,
0 1,2,...,
0 1,2,...,
0 1,2,...,
m
j
j ii
jj
j
j
fg
in
xx
gjm
gjm
jm
λ
λ
λ
=
∂∂
+==
∂∂
==
≤=
≥=
∑
Kuhn-Tucker conditions for X
*
= [x
1
*
x
2
*
. . . x
n
*
]to be a local minimum are

5. D Nagesh Kumar, IISc Optimization Methods: M2L5
5
Kuhn Tucker Conditions …contd.
j
λ
™
In case of minimization problems, if the constraints are
of the form g
j(
X
) 0, then have to be non-positive
™
On the other hand, if the problem is one of maximization
with the constraints in the form g
j(
X
) 0, then have to
be nonnegative.
≥
j
λ
≥

6. D Nagesh Kumar, IISc Optimization Methods: M2L5
6
Example (1) Minimize subject to
222
123
23
f
xxx =+ +
112 3
21 2 3
212
238
gxx x
gxxx
=−− ≤
=+ − ≤

7. D Nagesh Kumar, IISc Optimization Methods: M2L5
7
Example (1) …contd.
12
12
0
ii
i
gg
fxx
x
λλ
∂∂
∂
++
=
∂∂
∂
11
2
21
2
31
2
2
0



(
2
)
4
2
0


(
3
)
6
2
3
0


(
4
)
x x x
λ
λ
λλ
λλ
+
+=
−+
=
−−
=
0
jj
g
λ
=
11
2
3
21
2
3
(
2
12)
0


(
5
)
(
2
3
8
)
0



(
6
)
xx
x
xx
x
λ λ
−
−−
=
+−
−
=
0
j
g
≤
12
3
12
3
2
1
2
0


(
7
)
2
3
8
0


(
8
)
xx
x
xx
x
−
−−
≤
+−
−
≤
0
j
λ
≥
1 2
0




(9)
0




(10)
λ λ
≥ ≥
Kuhn –
T
ucker Conditions

8. D Nagesh Kumar, IISc Optimization Methods: M2L5
8
Example (1) …contd.
From (5)either = 0 or ,
Case 1
¾
From (2), (3) and (4)we have x
1
= x
2
= and x
3
=
¾
Using these in (6)we get
¾
From (10),, therefore, =0,
¾
Therefore, X
*
= [ 0, 0, 0 ]
This solution set satisfies all of (6)to (9)
1
λ
12 3
2120 xx x
−
−−=
2
/2
λ
−
2
/2
λ
2
22 2
80, 08or
λλ λ
+
=∴= −
2
0
λ
≥
2
λ

9. D Nagesh Kumar, IISc Optimization Methods: M2L5
9
Example (1) …contd.
Case 2:
¾
Using
(2)
,
(3) and (4),
we have
or
¾
But conditions
(9)
and
(10)
give us and simultaneously,
which cannot be possible with
Hence the solution set for this optimization problem is
X
*
= [ 0 0 0 ]
12 3
2120 xx x−− −=
12 1 2 1 2
223
12 0
243
λ
λλλ λλ
−
−− +
−− −=
12
17 12 144
λ
λ
+=−
1
0
λ
≥
2
0
λ
≥
12
17 12 144
λ
λ
+
=−

10. D Nagesh Kumar, IISc Optimization Methods: M2L5
10
Example (2) Minimize subject to
22
12 1
60
f
xx x =++
11
212
80 0
120 0
gx
gxx
=
−≥
=
+− ≥

11. D Nagesh Kumar, IISc Optimization Methods: M2L5
11
Example (2) …contd.
12
12
0
ii
i
gg
fxx
x
λλ
∂∂
∂
++
=
∂∂
∂
0
jj
g
λ
= 0
j
g
≤
0
j
λ
≥
Kuhn –
T
ucker Conditions
11
2
22
2
6
0
0
(
11)
2
0

(
12)
x x
λ
λ
λ
+
++
=
+=
11 21
2
(
8
0)
0
(13)
(
120)
0
(
14)
x xx
λ λ
−
=
+−
=
1 12
80
0

(
1
5)
120
0
(
16)
x xx
−
≥
++
≥
1 2
0


(
1
7)
0


(18)
λ λ
≤ ≤

12. D Nagesh Kumar, IISc Optimization Methods: M2L5
12
Example (2) …contd.
From (13)either = 0 or ,
Case 1
¾
From
(11) and (12)
we have and
¾
Using these in
(14)
we get
¾
Considering ,
X
*
= [ 30, 0]. But this solution set violates
(15)
and
(16)
¾
For ,
X
*
= [ 45, 75]. But this solution set violates
(15)
1
λ
1
(80)0 x
−
=
2
1
30
2
x
λ
=
−−
2
2
2
x
λ
=−
(
)
22
150 0
λλ
−
=
2
0150or
λ
∴
=−
2
0
λ
=
2
150
λ
=−

13. D Nagesh Kumar, IISc Optimization Methods: M2L5
13
Example (2) …contd.
Case 2:
¾
Using in
(11) and (12),
we have
¾
Substitute (19) in (14), we have
¾
For this to be true, either
1
( 80) 0 x−= 1
80 x=
22
12
2
2 220(19)
x
x
λ λ
=−
=−
(
)
22
2400xx
−
−=
22
0400 xorx
=
−=

14. D Nagesh Kumar, IISc Optimization Methods: M2L5
14
Example (2) …contd. ¾
For ,
¾
This solution set violates
(15)
and
(16)
¾
For ,
¾
This solution set is satisfying all equa tions from (15) to (19) and hence
the desired
¾
Thus, the solution set for th is optimization problem is
X
*
= [ 80 40 ].
2
0 x=
1
220
λ
=
−
2
40 0 x−=
12
14080 and
λ
λ
=
−=−

15. D Nagesh Kumar, IISc Optimization Methods: M2L5
15
Thank you