TRƢỜNG ĐẠI HỌC SƢ PHẠM THÀNH PHỐ HỒ CHÍ MINH
KHOA TOÁN – TIN


BÀI TIỂU LUẬN
MÔN: LÍ THUYẾT TỐI ƢU PHI TUYẾN
ĐỀ TÀI:
TIÊU CHUẨN TỐI ƢU CỦA QUY HOẠCH PHI TUYẾN
VỚI GIẢ THIẾT KHẢ VI (PHẦN II)




NHÓM THỰC HIỆN
1. TRẦN VIỆT HÙNG
2. NGÔ THỊ THƢƠNG
3. PHẠM NGỌC THU TRANG





Thành phố HCM, tháng 2 năm 2015


MỤC LỤC
1. ĐỊNH NGHĨA TẬP LỒI
2. ĐỊNH NGHĨA HÀM LỒI, HÀM LÕM
a. Định nghĩa hàm lồi

b. Định nghĩa hàm lõm
3. NHẮC LẠI MỘT SỐ BÀI TOÁN
a. Bài toán cực tiểu MP
b. Bài toán cực tiểu địa phƣơng LMP
c. Bài toán điểm yên ngựa Fritz John (FJP)
d. Bài toán điểm yên ngựa Kuhn – Tucker (KTP)
4. BỔ ĐỀ TUYẾN TÍNH HÓA
5. MỘT SỐ RÀNG BUỘC ĐỊNH TÍNH
a. Ràng buộc định tính Slater
b. Ràng buộc định tính Karlin
c. Ràng buộc định tính nghiêm ngặt
d. Ràng buộc định tính Kuhn – Tucker
e. Ràng buộc định tính Arrow – Hurwicz –Uzawa
f. Ràng buộc định tính lồi đảo ngƣợc
6. MỘT SỐ ĐỊNH LÍ VÀ BỔ ĐỀ
a. Định lí Motzkin
b. Định lí tối ƣu cần cho bài toán điểm dừng Fritz John
c. Định lí Gordan
d. Bổ đề 1
e. Bổ đề 2
7. MỐI QUAN HỆ GIỮA CÁC RÀNG BUỘC ĐỊNH TÍNH
8. ĐỊNH LÍ TỐI ƢU CẦN CỦA BÀI TOÁN ĐIỂM DỪNG KUHN –
TUCKER
9. THIẾT LẬP ĐIỀU KIỆN TỐI ƢU KUHN – TUCKER CHO BÀI TOÁN
QUY HOẠCH PHI TUYẾN
a. Hàm Lagrange
b. Định lí 1
c. Định lí 2
d. Thiết lập điều kiện Kuhn-Tucker
e. Ví dụ minh họa

Tối ưu phi tuyến
Nhóm 11 Trang 3

1. Định nghĩa tập lồi
n
S 
là tập lồi
 
12
, , 0;1x x S

    
,
 
12
. 1 .x x x S

   

Nói cách khác tập
n
S 
là tập lồi nếu mọi đoạn thẳng nối
12
,x x S
đều
nằm trong S.
2. Hàm lồi, hàm lõm.
a. Định nghĩa hàm lồi
Hàm


xác định trên tập
n

được gọi là hàm lồi tại
*
x 
nếu:
**
*
0 1 (1 ) ( ) ( ) (1 )
(1 )
x
x x x x
xx
      



       

  

Hàm

được gọi là hàm lồi trên
n

nếu nó lồi với mọi
x


b. Định nghĩa hàm lõm
Hàm

xác định trên tập
n

được gọi là hàm lõm tại
*
x 
nếu:
**
*
0 1 (1 ) ( ) ( ) (1 )
(1 )
x
x x x x
xx
      



       

  

Hàm

được gọi là hàm lõm trên


nếu nó lõm với mọi
x

3. Nhắc lại một số bài toán
a. Bài toán cực tiểu MP
Cho hàm số
0
:
n
X


. Tìm
*
u
sao cho:
 
 
 
*0
12
*0
, , ,
,
n
n
n
u u u u X
x u x X



  


   



 Miền
0 n
X 
được gọi là tập các phương án chấp nhận được (hay miền
ràng buộc)
 Điểm
 
0
12
, , ,
n
n
x x x x X  
gọi là phương án chấp nhận được (hay
phương án khả thi hay phương án)
 Điểm
 
*0
12
, , ,
n
n

u u u u X  
được gọi là phương án tối ưu toàn cục.

Khi
0 n
X 
là một tập lồi và  là hàm lồi trên
0
X
thì Bài toán cực tiểu MP được
gọi là Bài toán quy hoạch lồi (BTQHL)

Tối ưu phi tuyến
Nhóm 11 Trang 4

b. Bài toán cực tiểu địa phƣơng LMP
Cho hàm số
0
:
n
X


. Tìm
u
sao cho:
tồn tại quả cầu mở
 
Bu


tâm
u
, bán kính
0


đủ nhỏ và
 
 
   
0
12
0
, , ,
,
n
n
u u u u X
x u x B u X



  


   





Điểm
 
0
12
, , ,
n
n
u u u u X  
được gọi là phương án tối ưu địa phương.
c. Bài toán điểm yên ngựa Fritz John (FJP)
Tìm
x
 X
0
,
0
r
 R,
r
 R
m
, (
0
r
,
r
)  0 (nếu có) sao cho:
     
 
   

000
0
00
, , , , , ,
0, ,
,,
m
x r r x r r x r r
r r R x X
x r r r x rg x



    


d. Bài toán điểm yên ngựa Kuhn -Tucker (KTP)
Tìm
x
 X
0
,
u
 R
m
,
u
 0 (nếu có) sao cho:
     
     

0
,,,
0, ,
,
m
x u x u x u
u u R x X
x u x ug x



    


*Tìm điểm yên ngựa, gtln – gtnn địa phƣơng

Dạng để: cho
 
fx

Cách làm:
- Đạo hàm theo
''
, : ,
xy
x y f f

- Giải hệ phương trình để tìm ra điểm
 
,

MM
M x y

Tối ưu phi tuyến
Nhóm 11 Trang 5

'
'
0
0
x
y
f
f



- Đạo hàm riêng hai lần theo
'' '' ''
, : , ,
xx yy xy
x y f f f

- Tính
 
2
'' '' ''
*
xx yy xy
D f f f


- Tính
 
,
MM
A D x y

+ Nếu
0A 
thì
f
đạt điểm yên ngựa tại
M

+ Nếu
0A 
thì không xác định
+ Nếu
0A 
và
 
''
,0
xx M M
f x y 
thì
f
đạt GTNN tại
M


+ Nếu
0A 
và
 
''
,0
xx M M
f x y 
thì
f
đạt GTLN tại
M

*Bài tập điểm yên ngựa
Ví dụ: Chứng minh rẳng phương trình
 
22
,f x y ax bxy cy  
với
2
40D ac b  
có điểm yên ngựa tại
 
0,0

Giải:
Với
0D 

Cho

y
là hằng số, chúng ta coi
 
,f x y
như là một hàm
 
22
z f x ax bxy cy   
với
 
 
2 2 2
40y b ac y D     

Chúng ta biết
 
fx
đạt GTNN hoặc GTLN tại
2
b
xy
a



Với
0a 
: tại
 
2

, f 0
24
GTNN
b
x y x y
aa
 
  

Cho
   
2
4
GTNN
g y f x y
a



Do đó
 
0
GTLN
gy 
khi
0y 

Vậy tại
 
0,0

chúng ta nhận được
 
0
GTLN
gy 
và
 
0
GTNN
fx 

Tối ưu phi tuyến
Nhóm 11 Trang 6

Với
0a 
: tại
 
2
, f 0
24
GTLN
b
x y x y
aa

  

Cho
   

2
4
GTLN
g y f x y
a



Do đó
 
0
GTNN
gy 
khi
0y 

Vậy tại
 
0,0
chúng ta nhận được
 
0
GTNN
gy 
và
 
0
GTLN
fx 


Vậy
 
0,0
là điểm yên ngựa của
 
,f x y
, với
0a 

Với
0a 
: chúng ta nhận:
 
2
,f x y bxy cy

Chúng ta có thể biểu diễn
 
,f x y
, trong hình cầu bằng nhau:
       
2
, sin cos sin sin sin sin( )f x y b c
       




   
22

sin cos sin sin sin( )bc
      
   

   

 
2
2
sin cos sin sin( )bc
    

   

   


Cho
 
2
sinMb




, chúng ta nhận được:
       
2
, sin sinf x y M cos c
  









Chúng ta xoay mặt phẳng
oxy
theo chiều ngược chiều kim đồng hồ một góc
4







Tối ưu phi tuyến
Nhóm 11 Trang 7








Đặt các góc độ mới là


, chúng ta nhận được:
4



. Vì thế
 
2
, sin sin
4 4 4
f x y M cos c
  
  


     

    

     

     



     
2
2 2 1
sin sin sin

2 2 2
M cos cos c cos
     

    




 
 
 
22
11
sin 1 2sin ( )
22
M cos c cos
   

   



 
 
 
2
22
11
sin sin sin ( )

22
b cos c c cos
     


   




           
2 2 2
2 2 2
1 1 1
sin sin sin sin sin sin
2 2 2
b cos b bc cos bc
           
       
   
       

 
 
2
2 2 2 2
1 1 1
sin sin
2 2 2
bX bY bcXY bc cos

   

    


   
22
11
22
b bc X bc b Y bcXY    
(trong hình chữ nhật mới bằng nhau)
22
( , )AX CY BXY F X Y  

x
y
X
Y
Tối ưu phi tuyến
Nhóm 11 Trang 8

Và bây giờ chúng ta có một hàm mới với
0A 
hoặc
0C 
, chúng ta có thể làm các
bước với
0A 

Như vậy

 
0,0
là điểm yên ngựa của
 
,f x y


4. Bổ đề tuyến tính hóa
Giả sử
x
là một nghiệm của LMP,
0
X
là một tập mở,

và g khả vi tại
x
. Đặt:
{ | ( ) 0,
ii
V i g x g
lõm tại
x
}
Và
W { | ( ) 0,
ii
i g x g
không lõm tại
x

}
Khi đó:
W
( ) 0
( ) 0
( ) 0
V
xz
g x z
g x z




không có nghiệm z trong
n

Chứng minh:
Đặt:
W { | ( ) 0}
{ | ( ) 0}
i
i
I V i g x
J i g x
  


Do đó:
W {1,2, , }I J V m


Giả sử
x
là một nghiệm của LMP với


. Ta có thể chỉ ra rằng:
Nếu z thỏa
( ) 0xz


,
( ) 0g x z
,
( ) 0
V
g x z
thì xảy ra mâu thuẩn.
Giả sử z thỏa các bất phương trình trên
Do
0
X
là một tập mở nên
0


sao cho:
0
x ( )z X B x




với
0



Do

và g khả vi tại
x
nên:
Tối ưu phi tuyến
Nhóm 11 Trang 9

0
( ) ( ) ( ) ( , )x z x x z x z z
       
    

( ) ( ) ( ) ( , )
i i i i
g x z g x g x z x z z
    
    
, I = 1, 2, ………, m
Tại đó:
0
lim ( ) 0
i

xz




; I = 0, 1, 2,…, m
(i) Nếu

đủ nhỏ (
0


) thì
0
( ) ( , ) 0x z x z z
  
  

Do đó:
( ) ( ) 0x z x
  
  
(
0


)
(ii) Tương tự, vì
Wi
và


đủ nhỏ (
0


) nên:
( ) ( , ) 0
ii
g x z x z z



Do đó:
( ) ( ) 0
ii
g x z g x

  
,
0 , W
i
i

  

(iii) Vì
,
i
i V g
lõm tại

x
và
( ) 0
V
g x z
nên:
( ) ( ) ( ) 0
i i i
g x z g x g x z

    
,
0 , W
i
i

  

(iv) Vì
iJ
,
( ) 0
i
gx
nên với

đủ nhỏ
(0 )
i



, ta có:
( ) ( ) ( , ) 0
i i i
g x g x z x z z
   
   

Do đó:
( ) 0
i
g x z


,
0,
i
iJ

  

Đặt
0
min{ , , , }
i
    

, với
1,2, ,im


Khi đó, Với mọi

nằm trong khoảng
0


, ta có:
0
x z X



()
z
x z B x



( ) ( )x z x
  


( ) ( ) 0,
ii
g x z g x i I

   

( ) 0,
i

g x z i J

  

Do đó, với
0


, ta có
()
z
x z B x X


và
( ) 0( )x z x



Theo giả thiết,
x
là một nghiệm của LMP (với


). Do đó không tồn tại
n
z
thỏa:

W

( ) 0
( ) 0
( ) 0
V
xz
g x z
g x z




(đpcm).
Tối ưu phi tuyến
Nhóm 11 Trang 10

5. Một số ràng buộc định tính
a. Ràng buộc định tính Slater
0
X
là một tập lồi trên
n
, g là một hàm vecto m-chiều xác định trên
0
X
.
Hàm g được gọi là thỏa mãn ràng buộc định tính Staler trên
0
X
nếu tồn tại một
*0

xX
sao cho
*
( ) 0gx 

b. Ràng buộc định tính Karlin
0
X
là một tập lồi trên
n
, g là một hàm vecto m-chiều xác định trên
0
X
.
Hàm g được gọi là thỏa mãn ràng buộc định tính Karlin trên
0
X
nếu tồn tại một
,0
n
pp
sao cho
0
( ) 0,pg x x X  

c. Ràng buộc định tính nghiêm ngặt
0
X
là một tập lồi trên
n

, g là một hàm vecto m-chiều xác định trên
0
X
.
Hàm g được gọi là thỏa mãn ràng buộc định tính nghiêm ngặt trên
0
X
nếu tồn tại ít
nhất hai điểm phân biệt
12
,xx
sao cho g lồi nghiêm ngặt tại
1
x
.
d. Ràng buộc định tính Kuhn – Tucker
Cho
0
X
là một tập mở trong
n
,
g
là một hàm vectơ m-chiều trong
0
X
, đặt:
 
 
0

| , 0X x x X g x  

g
thỏa ràng buộc Kuhn – Tucker tại
xX
nếu
g
khả vi tại
x

và: nếu
 
0
n
I
y
g x y










Khi đó tồn tại một hàm vectơ
e
n-chiều được định nghĩa trên

 
0,1
sao cho:
a.
 
0ex

b.
 
,0 1eX

  

c.
e
khả vi tại
0


và
 
0de
y
d



với một
0



nào đó.
Trong đó:
 
 
|0
i
I i g x

e. Ràng buộc định tính Arrow – Hurwicz –Uzawa
Cho
0
X
là một tập mở trong
n
,
g
là một hàm vectơ m-chiều xác định trên
0
X
.
Đặt :
 
 
0
| , 0X x x X g x  

Tối ưu phi tuyến
Nhóm 11 Trang 11


g
thỏa ràng buộc Arrow – Hurwicz –Uzawa tại
xX
nếu
g
khả vi tại
x
và
 
 
w
0
0
v
g x z
g x z







có nghiệm
n
z

Trong đó:
 


| 0,
ii
V i g x g
lõm tại

x
và
 

W | 0,
ii
i g x g
không lõm tại

x

f. Ràng buộc định tính lồi đảo ngƣợc
Cho
0
X
là một tập mở trong
n
,
g
là một hàm vectơ m-chiều xác định trên
0
X
. Đặt
 
 

0
| , 0X x x X g x  

g
được gọi là thỏa ràng buộc nghịch đảo của tập lồi tại
xX
nếu
g
khả vi tại
x
và nếu với mỗi
iI
hoặc
i
g
lõm hoặc
i
g
tuyến tính trên
n
, trong đó:
 
 
|0
i
I i g x

6. Một số định lí và bổ đề
a. Định lí Motzkin
Cho các ma trận A, C và D với A là ma trận khác không. Khi đó chỉ xảy ra một và chỉ

một trong hai kết quả sau:
Hoặc
(I).
0Ax 

0Cx 

0Dx 
có một nghiệm x
Hoặc
(II)
' ' '
1 3 4
13
0
0; 0
A y C y D y
yy
  

có một nghiệm
1 3 4
,,y y y

b. Định lí tối ƣu cần cho bài toán điểm dừng Fritz John
Giả sử
x
là một nghiệm của LMP hoặc của MP,
0
X

là một tập mở,

và g khả vi tại
x
.
Khi đó, tồn tại
0
r
m

sao cho
0
( , , )x r r
là nghiệm của FJP và
0W
( , ) 0rr 

Trong đó:
W { | ( ) 0,
ii
i g x g
không lõm tại
x
}
Chứng minh:
Nếu
x
là nghiệm của MP thì
x
là nghiệm của LMP

Đặt:
{ | ( ) 0,
ii
V i g x g
lõm tại
x
}
{ | ( ) 0}
i
J i g x

Tối ưu phi tuyến
Nhóm 11 Trang 12

Theo bổ đề ở trên, ta có:
W
( ) 0
( ) 0
( ) 0
V
xz
g x z
g x z




không có nghiệm z trong
n


Do đó, theo định lí Motzkin 6.a thì tồn tại
0W
,,
V
r r r
sao cho:
0 W W
( ) ( ) ( ) 0
VV
r x r g x r g x

     
,
0W
( , ) 0rr 
,
0
V
r 

Vậy:
W
( ) 0gx
và
( ) 0
V
gx

Nếu ta định nghĩa:
0

J
r 
và
W
( , , )
VJ
r r r r
thì
W
( ) w ( ) ( ) ( ) 0
VJ
rg x r g x rVg x rJg x    

0
( ) ( ) 0r x r g x

   

0
( , ) 0rr

Do đó:
xX
,
( ) 0gx

Vậy:
0
( , , )x r r
là nghiệm của FJP,

0W
( , ) 0rr 

c. Định lí Gordan
Cho ma trận A tùy ý. Khi đó, một và chỉ một trong hai hệ phương trình sau có nghiệm:

A0x 


'
0
0
Ay
y






d. Bổ đề 1
Ràng buộc định tính Slater và ràng buộc định tính Karlin là tương đương nhau.
Ràng buộc định tính nghiêm ngặt thì bao gồm cả ràng buộc Slater và ràng buộc Karlin.
Chứng minh:
 Theo định lí Gordan tổng quát thì ràng buộc Slater và ràng buộc Karlin là
tương đương nhau.
 Do
0
X
là tập lồi, với mỗi

,0 1


, ta có:
1 2 0
(1 )x x X

  

Tối ưu phi tuyến
Nhóm 11 Trang 13

Do g lồi nghiêm ngặt tại
1
x
nên:
1 2 1 2
[(1- )x + x ]<(1- )g(x )+ (x )gg
   

mà
12
g(x ) 0,g(x ) 0

nên ta có
1 2 1 2
[(1- )x + x ]<(1- )g(x )+ (x ) 0gg
   



Vì vậy, g thỏa ràng buộc định tính Staler và do đó cũng thỏa ràng buộc định tính
Karlin.
e. Bổ đề 2
Cho
0
X
là một tập mở trong
n
,
g
là một hàm vectơ m-chiều xác định trên
0
X
. Đặt
 
 
0
| , 0X x x X g x  

i) Nếu
g
thỏa ràng buộc 5.f tại
x
thì
g
thỏa ràng buộc 5.e tại
x

ii) Nếu
g

thỏa ràng buộc 5.f tại
x
thì
g
thỏa ràng buộc 5.d tại
x

iii) Giả sử
0
X
lồi,
g
lồi trên
X
,
g
khả vi tại
x
. Nếu
g
thỏa ràng buộc Slater trên
0
X
,
thỏa ràng buộc Karlin trên
0
X
hoặc thỏa ràng buộc định tính nghiêm ngặt trên
0
X

thì
g
thỏa ràng buộc 5.e tại
x

Chứng minh:
i) Giả sử
g
thỏa ràng buộc 5.f tại
x
thì tập
W
xác định trong 5.e là tập rỗng và
0z 

thỏa:
   
 
 
0
|0
vI
i
g x z g x z
I i g x
   


Do đó
g

thỏa ràng buộc 5.e tại
x

ii) Giả sử
g
thỏa ràng buộc 5.f tại
x
. Ta định nghĩa:
 
 
|0
i
I i g x
và
 
 
|0
i
J i g x

Lấy
y
là một vectơ bất kì trong
n
thỏa:
 
0
v
g x y


Đặt:
 
e x y
 

với
0


nào đó
Hiển nhiên, các điều kiện (a) và (c) của ràng buộc 5.d được thỏa mãn. Ta sẽ chỉ ra rằng
điều kiện (b) cũng được thỏa mãn.
Vì
0
X
là tập mở,
I
g
lõm và khả vi tại
x
nên ta có:
0
x y X


và
 
       
0
I I I I I

g e g x y g x g x y g x y
   
       



Tối ưu phi tuyến
Nhóm 11 Trang 14

Với
0 1;0
  
   

Do
0 1;0
  
   
nên ta có
 
0
I
ge




vì
iJ
nên:

       
,
i i i i
g x y g x g x y x y y
   

    


 
0
lim , 0
i
xy

 



     
,
i i i
g x g x x y y
  

   


<0 (với


nào đó thỏa
0


)
Trong đó bất đẳng thức cuối cùng đúng vì
 
0
J
gx
và
 
0
lim , 0
i
xy

 



Do đó
 
0
I
ge





với
01



Vì
 
0
I
ge




với
01


nên ta có
 
eX


với
01



Vậy điều kiện (b) của ràng buộc 5.d được thỏa mãn
iii) Do bổ đề 6.c nên ta có ràng buộc Slater và ràng buộc Karlin là tương đương nhau

và từ ràng buộc định tính nghiêm ngặt ta suy ra được cả hai ràng buộc Slater và Karlin.
Do đó ta chỉ cần thiết lập bổ đề với ràng buộc Slater
Nếu
g
thỏa ràng buộc Slater trên
0
X
thì tồn tại
0
xX
sao cho
 
0gx

Do
g
khả vi tại
x
nên ta có:
   
   
 
0
I I I I
g x g x g x g x x x     

Trong đó:
 
 
|0

i
I i g x

Do
g x x
nên ta có
 
0
I
g x z
và do đó ràng buộc 5.e được thỏa mãn
7. Mối quan hệ giữa các ràng buộc định tính













Karlin’s CQ 5.b
Slater CQ 5.a
Strict CQ
5.c
X

0
lồi
g lồi
Reverse Convex
CQ 5.f
Arrow – Hurwicz – Uzawa CQ
5.e
Kuhn – Tucker CQ 5.d
Hình: Mối quan hệ giữa các ràng buộc định tính khác nhau
Tối ưu phi tuyến
Nhóm 11 Trang 15









8. Định lý tối ƣu cần của bài toán điểm dừng Kuhn – Tucker
Cho
0
X
là một tập con mở của
,
n

và
g

xác định trên
0
X
,
x
là nghiệm của bài toán
LMP 3.b ,

và
g
thỏa:
i) Ràng buộc Kuhn – Tucker 5.d tại
x
, hoặc
ii) Ràng buộc Arrow – Hurwicz – Uzawa 5.e tại
x
, hoặc
iii) Ràng buộc tập lồi nghịch đảo 5.f tại
x
, hoặc
iv) Ràng buộc Slater 5.a trên
0
X
, hoặc
v) Ràng buộc Karlin 5.b trên
0
X
, hoặc
vi) Ràng buộc nghiêm ngặt 5.c trên
0

X

Thì tồn tại một
m
u
sao cho
 
,xu
là nghiệm của KTP 3.d
Chứng minh: Theo bổ đề 2, ta chỉ cần thiết lập định lý với điều kiện (i) hoặc (ii)
i) Giả sử
x
là ngiệm của LMP 3.b với



Đặt
 
 
|0
i
I i g x
;

 
 
|0
i
J i g x


Có hai trường hợp:
I
rỗng và
I
khác rỗng
 TH1:
I 

Lấy
y
là một vectơ bất kì trong
n
sao cho
1yy 
thì
       
, , 1,2, ,
i i i i
g x y g x g x y x y i m
   

     


Vì
 
0
i
gx
và

 
0
lim , 0
i
xy




nên với một số

đủ nhỏ thì
0


,
 
0
i
g x y


và
0
x y X



Do
x

là nghiệm của LMP 3.b nên ta có:
Tối ưu phi tuyến
Nhóm 11 Trang 16

       
0,x y x x y x y y
      

     

vì
0



Do đó,
   
,0x y x y
  
  

Vì
 
0
lim , 0xy




nên khi ta chuyển qua giới hạn biểu thức trên với


tiến tới 0 ta suy
ra
 
0xy



Do
y
là một vectơ bất kỳ trong
n
thỏa
1yy 
nên ta có thể lấy
i
ye
, trong đó
in
e 

là một vectơ mà chỉ có thành phần thứ
i
bằng 1, các thành phần còn lại đều bằng 0.
Khi đó:
 
0x




Do đó:
x
và
u
=0 thỏa KTP 3.b
 TH2:
I 

Giả sử
g
thỏa ràng buộc Kuhn- Tucker 5.d tại
x
,
n
y
thỏa
 
0
I
g x y

Khi đó, tồn tại một hàm vectơ
e
n-chiều xác định trên [0,1] sao cho
   
0,e x e X


với
01



,
e
khả vi tại
0


và:
 
0de
y
d



với một
0


nào đó
Do
01


nên:
   
 
 
0

0 0, , 1,
i
i i i
de
e e i
d
   


   



Trong đó:
 
0
lim 0, 0





Vì vậy, với

đủ nhỏ thì
01


, ta có:
   

e B x




Do
 
eX


với
01


và
x
là nghiệm của LMP 3.b, ta có:
   
0 ,0ee
    
  
   
   

Ta có:
     
 
 
0
0 0 0 0,

de
e e e
d
       

    
     
     

Trong đó:
 
0
lim 0, 0





Do đó:
 
 
 
0
0 0, 0,0
de
e
d
      

    




Chuyển qua giới hạn khi

tiến tới 0 ta được:
 
 
0
00
de
e
d






Do
 
0ex
và
 
0de
y
d




với
0


nào đó
Tối ưu phi tuyến
Nhóm 11 Trang 17

Ta có:
 
0xy



Ta đã chỉ ra rằng:
   
00
I
g x y x y

   

Hoặc
 
 
0
0
I
xy
g x y





không có nghiệm
y
trong
n

Theo định lý Motzkin 6.a thì tồn tại một
0
r
và
I
r
sao cho:
   
0
0
II
r x r g x

   

0
0; 0
I
rr

Do

0
r
là một số thực
0
0r 
nên
0
0r 

Đặt:
 
0
; 0; ,
I
I J I J
r
u u u u u
r
  

Ta có:
   
 
0
0
0
x u g x
ug x
u


   



Và do
xX
nên ta có
 
0gx

Do đó,
 
,xu
là nghiệm của KTP 3.b
ii) Giả sử
x
là nghiệm của MP 3.a theo định lý Fritz John 2 thì tồn tại một
0
r 
và
một
m
r
sao cho
 
0
,,x r r
là nghiệm của FJP 3.c và
 
0w

,0rr 

Trong đó:
Đặt
 

W | 0,
ii
i g x g
không lõm tại

x

 

| 0,
ii
V i g x g
lõm tại

x

 
 
|0
i
J i g x

Ta chỉ cần chỉ ra rằng
0

0r 

Do
 
0w
,0rr 
nên
0
0r 
nếu
W 

Giả sử
W0
, ta sẽ chứng minh bằng phương pháp phản chứng
Giả sử
0
0r 

Do
0
J
r 
, ta có:
Tối ưu phi tuyến
Nhóm 11 Trang 18

   
 
ww

0 *
vv
r g x r g x   

w
0 ; 0
v
rr

Do
g
thỏa ràng buộc 5.e tại
x
, nên tồn tại
n
z

Sao cho:
 
 
w
0
0
v
g x z
g x z









   
ww
0
vv
r g x z r g x z    
( trái (*))
Vậy
0
0r 

9. Thiết lập điều kiện tối ƣu Kuhn – Tucker cho bài toán quy hoạch phi tuyến
a. Hàm Lagrange
Xét bài toán quy hoạch phi tuyến tổng quát:
Min/Max f(x) với
{ :g ( ) 0, i=1,m}
n
i
x D x x    
(*)
Lúc đó, hàm Lagrange tương ứng với bài toán trên có dạng:
1
( , ) ( )
m
ii
i
F x f x g





với
0, 1,
i
im

  

Khi đó, các điểm
( , )x

được gọi là điểm dừng Lagrange.
b. Định lí 1
Mọi phương án tối ưu của bài toán quy hoạch lồi cũng là phương án tối ưu toàn cục.
c. Định lí 2
Cho
*
x
là phương án tối ưu của bài toán quy hoạch phi tuyến tổng quát (*) với hàm mục
tiêu f(x) và các ràng buộc
g ( ), i=1,m
i
x 
là các hàm khả vi.
Xét tập các chỉ số
*
{i:g (x )=0}

i
I 

Giả sử các vectơ
*
( ),
i
g x i I  
là độc lập tuyến tính.
Khi đó, tồn tại vectơ có m tọa độ

sao cho
*
( , )x

là điểm dừng Lagrange.
Trong số các vectơ
* n
x 
, tồn tại vectơ có m tọa độ

sao cho
*
( , )x

là điểm dừng
của hàm Lagrange có thể tìm được phương án tối ưu địa phương của bài toán quy hoạch
phi tuyến (*). Theo định lí 1 ở trên, ta có thể tìm được phương án tối ưu toàn cục trong số
các điểm dừng trên.
d. Thiết lập điều kiện Kuhn-Tucker

Xét hệ điều kiện bao gồm điều kiện điểm dừng của hàm Lagrange và điều kiện ràng buộc
của bài toán quy hoạch phi tuyến:
Tối ưu phi tuyến
Nhóm 11 Trang 19

1
()
0, 1,
( ) 0, 1,
( ) 0, 1,
0, 1,
m
i
i
i
jj
ii
i
i
f g x
jn
xx
g x i m
g x i m
im







   




  


  


  



Hệ điều kiện trên đây được gọi là điều kiện Kuhn – Tucker của bài toán quy hoạch phi
tuyến
Điều kiện Karush-Kuhn-Tucker: Cho bài toán quy hoạch
 
P
, với mỗi điểm
*
P
xS
,
điều kiện KKT (KKT conditions) tương ứng của là tồn tại sao cho
1. :
2. : .
trong đó là nón trực giao với nón tâm của tại .

Định lý (điều kiện của nghiệm tối ƣu của bài toán quy hoạch lồi): Cho bài toán quy
hoạch lồi
1. (Điều kiện đủ) Nếu thỏa mãn điều kiện KKT thì là nghiệm tối ưu của
bài toán quy hoạch .
2. (Điều kiện cần và đủ) Nếu là bài toán quy hoạch lồi thỏa mãn điều kiện Slater
thì là nghiệm tối ưu của nếu và chỉ nếu thỏa mãn điều kiện KKT.
Chứng minh (1): Xét hàm Lagrange . Hàm này là hàm lồi trên và

hơn nữa thỏa mãn điều kiện nên là cực tiểu của hàm :
.
Do thỏa mãn điều kiện nên
.
Tối ưu phi tuyến
Nhóm 11 Trang 20

Như vậy, là điểm yên ngựa của hàm trên tập . Suy ra, là
nghiệm tối ưu của bài toán quy hoạch .
Chứng minh (2):
“ “: Hiển nhiên theo (1).
“ “: Giả sử là bài toán quy hoạch lồi thỏa mãn điều kiện Slater và là nghiệm
tối ưu của . Suy ra, tồn tại sao cho là điểm yên ngựa của hàm trên
tập :

Xét hàm Lagrange . Hàm này là hàm lồi trên và

như vậy để đạt cực tiểu tại ta phải có
.
Còn để hàm đạt cực đại tại , do dễ thấy ta phải có
.
Tức là phải thỏa mãn điều kiện KKT.


e. Ví dụ:
Xét bài toán quy hoạch phi tuyến sau:
22
12
inf( ) ( 1) ( 1)M x x x   

Với điều kiện
12
( , )x x x D
là miền ràng buộc xác định bởi:
1
2
12
20
10
,0
x
x
xx









11

22
31
42
( ) 2 0
( ) 1 0
( ) 0
( ) 0
g x x
g x x
g x x
g x x
  


  



  


  


Tối ưu phi tuyến
Nhóm 11 Trang 21

Đây là bài toán quy hoạch lồi (Theo phần lí thuyết ở phần Tính khả vi của hàm lồi, hàm
lõm nhóm đã báo cáo)
Ta có hàm Lagrange:

22
1 2 1 1 2 2 3 1 4 2
( , ) ( 1) ( 1) ( 2) ( 1)F x x x x x x x
    
         
,
0, 1,4
i
i

  

Khi đó, điều kiện Kuhn – Tucker của bài toán này được viết như sau:
1 1 3
2 2 4
11
22
31
42
1
2
1
2
1 2 3 4
2( 1) 0
2( 1) 0
( 2) 0
( 1) 0
( ) 0
( ) 0

20
10
0
0
, , , 0
x
x
x
x
x
x
x
x
x
x






   
   


   




























(1)
(2)
(3)
(4)
(5)
(6)
(7)

(8)
(9)
(10)

Từ (1) và (3) ta suy ra
1
0x 
. Theo (3) ta suy ra
1
0



Từ (2) và (6) ta suy ra
(3)
22
(3)
2 2 2 2
00
2( 1) 0 1; 0
Theo
Theo
x
xx



  



     




Xét 2 điểm là (0,0) và (0,1) ta thấy phương án tối ưu toàn cục có thể là:
 (0;0) với
1 2 3 4
0, 2, 2
   
    
. Đây không phải là điểm dừng của hàm
Lagrange (
4
20

  
)
 (0;1) với
1 2 3 4
0, 2
   
   
. Đây là điểm dừng của hàm Lagrange
Khi đó, Min f(x) = 1.
Kết luận: Vậy Min f(x) = 1 tại (0,1).


TÀI LIỆU THAM KHẢO


1. Olvi.Mangasarian - Nonlinear programming
2. Nguyễn Hải Thanh – Tối ưu hóa – NXB Bách Khoa Hà Nội – 2006
3. Một số tài liệu từ Internet