Trang 1


TRƯỜNG ĐẠI HỌC SƯ PHẠM TP.HCM
KHOA TOÁN – TIN
Lớp: Toán-VB2 khóa 2

TỐI ƯU PHI TUYẾN
Đề tài :
Tiêu chuẩn tối ưu của quy hoạch
không khả vi

Người thực hiện:
1. Lưu Thị Hảo
2. Nguyễn Thị Hồng Tiên
3. Đặng Lê Xuân Ánh Nguyệt



Trang 2

Mục lục
1. Bài toán cực tiểu hóa và bài toán điểm yên ngựa 3
1.1. Bài toán cực tiểu hóa (MP) 4
1.2. Bài toán cực tiểu hóa địa phương (LMP) 4
1.3. Bài toán điểm yên ngựa Fritz John(FJSP) 4
1.4. Bài toán điểm yên ngựa Kuhn-tucker (KTSP) 4
1.5. Chú ý: 5
1.6. Chú ý: 5
1.7. Chú ý: 5
2. Một vài kết quả nền tảng cho bài toán cực tiểu hóa và cực tiểu hóa địa phương 6

2. 1. Định lý: 6
2. 2. Đinh lý về tính duy nhất: 6
2. 3. Định lý: 6
2. 4. Định lý: 7
3. Tiêu chuẩn tối ưu đầy đủ 8
3.1. Định lý tối ưu đầy đủ 8
3.2. Bài toán 9
3.3. Hệ luận – kết quả tất nhiên 10
4. Điều kiện cần của tiêu chuẩn tối ưu 10
4.1 Định lý về kiều kiện cần cho tính tối ưu của bài toán điểm yên ngựa Fritz John 10
4.2 Bài toán 11
4.3 Tính chất ràng buộc Slater [Slater 50] 12
4.4 Tính chất ràng buộc Karlin [Karlin 59] 12
4.5 Tính chất ràng buộc ngặt 12
4.6 Bổ đề 12
4.7 Điều kiện tối ưu của định lý điểm yên ngựa Kuhn-Tucker 13
4.8 Định lý Kuhn-Tucker cần thiết cho tiêu chuẩn tối ưu trong sự hiện diện các ràng buộc tuyến
tính [Uzawa 58] 14
4.9 Mở rộng điều kiện tối ưu Kuhn-Tucker 16
5. Bài tập 16

Trang 3

Chương 5: Tiêu chuẩn tối ưu của quy hoạch
không khả vi
Mục tiêu của chương này là để suy ra tiêu chuẩn tối ưu điểm yên ngựa cho bài toán quy hoạch phi
tuyến tính. Để minh họa, ta xét ví dụ đơn giản sau
Xét bài toán cực tiểu hóa:
2
( ) ( ) m in

( ) (1)
20
uu
uR
u





  


hiển nhiên phương án tối ưu là
*
u2
và
 
m in ( ) : 4u u R


.
Tiêu chuẩn tối ưu cho bài toán này là: điều kiện cần và đủ để
*
u
là một phương án cuả bài toán
cực tiểu hóa là
*
R



(ở đây
*

= 4), sao cho
, , 0,u R R

    

* * * * * *
( ) ( 2) ( ) ( 2) ( ) ( 2)u u u u u u
     
          

Thật dễ dàng để thử lại rằng bất đẳng thức trên được thỏa mãn bởi
**
2, 4u


.
Vì vậy hàm

được định nghĩa trong R
2
bởi:
(u, ) (u ) ( u 2)       
là một điểm yên ngựa tại
**
2, 4u



, bởi vì nó có một giá trị nhỏ nhất tại
**
( , )u

với
uR
, và một giá trị lớn nhất
0, R

  

Đối với các bài toán đơn giản trên, tiêu chuẩn điểm yên ngựa có lẽ là cả điều kiện cần và đủ của
tiêu chuẩn tối ưu để
u
là phương án bài toán cực tiểu hóa (1).
Điều này không phải luôn luôn đúng trong mọi trường hợp. Chúng ta sẽ chứng minh trong chương
này là điều kiện điểm yên ngựa nói trên là điều kiện tối ưu đầy đủ mà không cần đòi hỏi tính lồi.
Tuy nhiên để thiết lập điều kiện điểm yên ngựa nói trên, chúng ta không chỉ cần tính lồi mà còn
cần chọn ra một vài điều kiện chính quy, một khả năng ràng buộc.
Điều kiện tối ưu cần thì phức tạp và khó hơn để thiết lập
Chúng ta sẽ phát triển tiêu chuẩn tối ưu của chương này mà không có bất kỳ giả thuyết khả vi nào
trong hàm đã được suy ra. Chương sau, chương 7 và 11, sẽ thiết lập tiêu chuẩn tối ưu để suy ra các
hàm khả vi.
1. Bài toán cực tiểu hóa và bài toán điểm yên ngựa
Tiêu chuẩn tối ưu của chương này liên quan đến phương án tối ưu của một bài toán cực tiểu hóa,
một bài toán cực tiểu hóa địa phương, và hai bài toán điểm yên ngựa mỗi loại. Chúng ta định nghĩa
những bài toán dưới đây.
Trang 4


Giả sử
0
M
là tập hợp con của R
n
, giả sử

và
f
là một hàm số và một hàm véctơ m-chiều được
định nghĩa trong
0
M
.
1.1. Bài toán cực tiểu hóa (MP)
Tìm một
*
u
, nếu nó tồn tại, sao cho:
*
*
0
uM
(u ) (u ) (M P )
f (u ) 0, u M



  



  


Tập hợp M được gọi là tập phương án hoặc tập hợp ràng buộc,
*
u

là phương án tối ưu hoặc là
nghiệm, và
*
(u )
là nhỏ nhất. Tất cả các điểm u trong tập phương án M được gọi là các phương
án của bài toán.
Nếu M là một tập lồi, và nếu

lồi trong M, bài toán cực tiểu hóa MP thường được gọi là bài toán
quy hoạch lồi hoặc quy hoạch lồi.
(Chúng ta chú ý rằng bài toán cực tiểu hóa trên là một trường hợp đặc biệt của bài toán cực tiểu
hóa tổng quát 1.6.9, trong đó thêm đẳng thức véctơ k- chiều ràng buộc h(x)=0 đã có. Lý do cho
trường hợp không khả vi này là chúng có điều kiện tối ưu không có nghĩa cho bài toán với tính
chất ràng buộc không tuyến tính. Tuy nhiên một vài kết quả cho tính ràng buộc tuyến tính sẽ đạt
được. Xem 5.3.2, 5.4.2, 5.4.8)
1.2. Bài toán cực tiểu hóa địa phương (LMP)
Tìm một
*
u
trong M, nếu nó tồn tại, sao cho quả cầu mở
*
B (u )


bao quanh
*
u
với bán kính
0

*
*
*
u B (u ) M
(u ) (u )
(LM P )
u B (u ) M




 



  



1.3. Bài toán điểm yên ngựa Fritz John(FJSP)
Tìm
00
* 0 * * m *

u M , a R , a R , (a , a) 0,   
nếu nó tồn tại, sao cho
0 0 0
* * * * * * *
m0
00
(u , a , a ) ( u , a , a ) ( (u , a , a )
a 0, a R , u M , (FJSP )
(u , a , a ) a (u ) af ( u )
   
    
  

1.4. Bài toán điểm yên ngựa Kuhn-tucker (KTSP)
Trang 5

Tìm
* 0 * m *
u M , R , 0,    
nếu nó tồn tại, sao cho
* * * *
m0
0
(u , ) (u , ) (u , )
0, a R , u M , (K T S P )
(u , a , a ) ( x ) f (u )
       
     
    


1.5. Chú ý:
Nếu
0
* * *
(u , a , a )
là một nghiệm của FJSP và , thì
0
* * *
(u , a / a )
là một nghiệm của KTSP. Ngược
lại, nếu
**
(u , )
là một nghiệm của KTSP thì
**
(u ,1, a )
là một nghiệm của FJSP.
1.6. Chú ý:
Hàm số
0
(u , a , a )
và
(u , )
được định nghĩa ở trên thì thường được gọi là hàm lagrange hoặc
đơn giản là Lagrange, và
*
a
là véctơ m-chiều và
*


là phép nhân Lagrange hoặc giá trị đối ngẫu.
Phép nhân này được tính theo quy tắc trong quy hoạch tuyến tính và không tuyến tính mà nó thì
giống với quy tắc tính bởi phép nhân Lagrange của phép tính cổ điển nơi mà một hàm của một vài
biến thì được cực tiểu để thỏa tính ràng buộc của đẳng thức ( xem ví dụ Fleming trang 65). Ở đây,
bởi vì chúng ta có bất đẳng thức ràng buộc, phép nhân Lagrange được thay đổi để không âm. Khi
chúng ta chú ý đến đẳng thức ràng buộc trong 5.3.2, 5.4.2 và 5.4.8, phép nhân liên đới với những
đẳng thức này sẽ không được đòi hỏi không âm.
1.7. Chú ý:
Bất đẳng thức đúng của bài toán điểm yên ngựa, FJSP 3 và KTSP 4:
00
* * * * *
(u , a , a ) (u , a , a ) 
với mọi
0
uM

và
* * *
(u , ) (u , )   
với mọi
0
uM

Có thể được thể hiện như 1 nguyên lý cực tiểu, giống nguyên lý cực đại Pontryagin [Pontryagin ví
dụ ở trang 62]. Nguyên lý Pontryagin trong điểm xuất phát của nó là điều kiện cần để kiểm soát
tính tối ưu của hệ thống được miêu tả bởi các phương trình khả vi thông thường. Chẳng hạn như,
nó là một điều kiện cần cho bài toán quy hoạch, không phải trong R
n
, nhưng trong một vài không
gian khác. Gần đây [Halkin 66, Canon ví dụ trang 66, Mangasarian-Fromovitz 67] một nguyên lý

cực tiểu thì được thiết lập để kiểm soát tính tối ưu được miêu tả bởi các phương trình khả vi thông
thường. Đây là một bài toán quy hoạch trong R
n
, nói chung thì không có tính lồi tổng quát, và vì
vậy kết quả của chương này thì không được ứng dụng. tuy nhiên điều kiện tối ưu của chương 7 và
11, cái mà dựa trên sự tuyến tính và không dựa trên tính lồi, được ứng dụng để kiểm soát tính tối
ưu của bài toán miêu tả bởi phương trình khả vi không tuyến tính.
Trang 6

2. Một vài kết quả nền tảng cho bài toán cực tiểu hóa và cực tiểu hóa địa
phương
Chúng ta thiết lập một vài kết quả nền tảng liên quan đến tập hợp nghiệm của bài toán cực tiểu hóa
và liên quan đến nghiệm của bài toán cực tiểu hóa và cực tiểu hóa địa phương cho mỗi loại.
2. 1. Định lý:
Cho M là tập lồi, và cho

là một hàm lồi trong M. tập hợp các nghiệm của MP 5.1.1 là lồi.
Chú ý: một điều kiện đủ nhưng không cần cho tính lồi của M là M
0
là một tập lồi và f lồi trong M
0
.
Điều này do 4.1.10 và 3.1.9.
Chứng minh: cho u
1
và u
2
là nghiệm của MP. Thì
12
uM

(u ) (u ) m in (u )

    

Nó kéo theo bởi tính lồi của M và, nó cho
12
0 1, (1 )u (u ) M       
và
1 2 1 2 1
uM
[(1 )u u ] (1 ) (u ) (u ) (u ) m in (u )

               

Vì vậy
12
(1 )u u   
là một nghiệm của MP, và tập nghiệm thì lồi.
+ Pontryagin tạo 1 nguyên lý cực đại thay thế bởi nguyên lý cực tiểu bởi vì hàm Lagrange
của ông là hàm Lagrange âm của quy hoạch không tuyến tính.
2. 2. Đinh lý về tính duy nhất:
Cho M lồi và
*
u
là một nghiệm của MP 5.1.1. Nếu

là lồi ngặt tại
*
u
, thì

*
u
là nghiệm duy nhất
của MP.
Chứng minh: cho
*
u ' u
là nghiệm khác của MP, thì,
u ' M
và
*
(u ') (u )  
. Từ M lồi, thì
*
(1 )u u ' M    
với
01  
, và bởi tính lồi ngặt của

tại
*
u

* * *
[(1 )u u '] (1 ) (u ) (u ') (u )             

Giả thiết mâu thuẫn này dẫn tới
*
(u )
là một giá trị nhỏ nhất, và từ đó

u'
không thể là 1 nghiệm
khác.
2. 3. Định lý:
Cho M lồi, và cho

là một hàm hằng lõm không đổi trong M thì không có điểm trong của M là
phương án của MP 5.1.1, hoặc bất kì 1 phương án tối ưu tương đương
*
u
của MP, nếu nó tồn tại,
phải là một điểm biên của M.
Chứng minh:
Trang 7

Nếu MP 5.1.1 vô nghiệm thì định lý đúng một cách hiển nhiên. Cho là một nghiệm của MP.
Do

không đổi trong M, nên tồn tại 1 điểm
uM
sao cho
*
(u ) (u )  
. Nếu z là 1 điểm
trong của M, thì tồn tại điểm
yM
sao cho tồn tại
, 0 1   

z (1 )u y    






Hình 5.2.1
Do đó:
**
*
(z) [(1 )u y ] (1 ) (u ) (y)
(1 ) (u ) (u )
(u )
             
      


Và không đạt được giá trị nhỏ nhất của nó tại một điểm trong z







*
u


Hình 5.2.2 một ví dụ đơn giản của định lý 3 trong R.
2. 4. Định lý:

Trang 8

Nếu
*
u
là một phương án của MP 5.1.1, thì nó cũng là 1 phương án của LMP 5.1.2. Ngược lại thì
đúng nếu M lồi và

là lồi tại
*
u
.
Chứng minh:
Nếu
*
u
thỏa mãn MP, thì
*
u
thỏa mãn LMP với bất kì
0
.
Để chứng minh ngược lại, giả sử
*
u
thỏa mãn LMP với một vài
0
, và cho M lồi và

lồi

tại
*
u
.
Cho u’ là 1 điểm bất kì trong M phân biệt với
*
u
.
Bởi vì M lồi,
*
(1 )u u ' M    
với
01  
. Bằng việc chọn

đủ nhỏ, sao cho
*
0 / u ' u    
và
1
, chúng ta có
* * *
u (u ' u ) (1 )u u ' B (u ) M

         

Do đó
* * *
(u ) u (u ' u )


     

( bởi vì
*
u
thỏa mãn LMP)
*
(1 ) (u ) (u ')      
(bởi tính lồi của

tại
*
u
)
Từ đó, kéo theo:
*
(u ) (u ')  

3. Tiêu chuẩn tối ưu đầy đủ
Tiêu chuẩn tối ưu đầy đủ chính được phát triển ở đây không đòi hỏi giả thuyết về tính lồi trong bài
toán cực tiểu hóa MP 5.1.1. những tiêu chuẩn này thì dường như tịnh tiến để đạt được và không
cần công cụ để suy ra. Kết quả đầu tiên của loại này đã đạt được trong [Uzawa 58].
3.1. Định lý tối ưu đầy đủ
Nếu
*
u
là một nghiệm của KTSP 5.1.4, thì
*
u
là một nghiệm của MP 5.1.1. Nếu

* * *
0
(u , a , a )
là
một nghiệm của FJSP 5.1.3, và
0
*
a0
, thì
*
u
là một nghiệm của MP 5.1.1
Chứng minh:
Dạng 2 của định lý kéo theo một cách thông thường từ dạng đầu tiên bởi chú ý 5.1.5.
Cho
**
(u , )
là một nghiệm của KTSP 5.1.4. Thì với mọi
0
trong R
m
và mọi u trong M
0

* * * * *
(u ) f (u (u ) f (u ) (u ) f (u )          

Trang 9

Từ bất đẳng thức đầu tiên chúng ta có:

**
( )f (u ) 0   
với mọi
0

Tồn tại j,
1 j m
, cho
i
j
*
i
*
j
voi i 1, 2, , j 1, j 1, , m
1
     
   

Nó kéo theo
*
j
f (u ) 0
. Lặp lại điều này cho hết tất cả các j, chúng ta nhận được
*
f (u ) 0
, và
do đó
*
u


là một phương án chấp nhận được, do đó,
*
uM

Bây giờ, bởi vì
*
0
và
*
f (u ) 0
, chúng ta có
**
f (u ) 0
. Nhưng lặp lại từ bất đẳng thức
đầu tiên của bài toán điểm yên ngựa chúng ta có, đặt
0


, có
**
f (u ) 0
. Do đó
**
f (u ) 0

Cho u là một phương án bất kì trong M, từ bất đẳng thức 2 của bài toán điểm yên ngựa ta nhận
được
**
(u ) (u ) f ( u )    

[ vì
**
f (u ) 0
]
(u )
[ vì
*
0, f (u ) 0 ]  

Do đó
u*

là 1 phương án của MP.
Điều được chú ý ở đây là vì không có giả thiết lồi được tạo trong định lý trên, nên đẳng thức ràng
buộc có thể được sử dụng lại bởi việc thay thế chúng bởi 2 bất đẳng thức ràng buộc. Đó là, thay
thế
h (u ) 0
bởi
h (u ) 0
và
h (u ) 0
.
3.2. Bài toán
Xét bài toán cực tiểu hóa
 
0
uM
(u*) m in (u ) u* M u u M , f (u ) 0, h (u ) 0

       


Trong đó h là một hàm véctơ k-chiều trong M
0
và tất cả mọi thứ còn lại thì được định nghĩa như
trong MP 5.1.1. Cho
00
(u , a , a , s ) a (u ) af (u ) sh ( u )    

Và
(u, , ) (u ) f (u ) vh (u)       

Chứng minh rằng nếu tồn tại
0 m k
u* M , * R , * 0 , * R      
sao cho
m k 0
(u*, , ) (u*, *, *) (u, *, *)
voi m oi 0, R , R , u M
        
      

Hoặc nếu tồn tại
00
0 m k
u* M , a * R , a * 0, a* R , a * 0, s* R     
sao cho
Trang 10

0 0 0
m k 0

(u*, a * , a , s) (u*, a * , a *, s*) (u , a * , a*, s*)
voi m oi a 0, a R , s R , u M
  
   

Thì
u*
là một nghiệm của bài toán cực tiểu hóa. (Chú ý rằng

và s không bị hạn chế về dấu)
Vấn đề này có thể được nâng lên để biết loại điểm nào là điểm
u*
nếu
0
(u*, a * , a*)
là một nghiệm
của FJSP 5.1.3 và chúng ta không đòi hỏi
0
*
a0
. Một câu trả lời cho vấn đề này được cho bởi kết
quả sau.
3.3. Hệ luận – kết quả tất nhiên
Nếu
0
* * *
(u , a , a )
là một nghiệm của FJSP 5.1.3, thì
*
u

là nghiệm MP 5.1.1 hay M không có phần
trong đối với
f (u ) 0
, đó là,
 
0
u u M , f (u ) 0   

Chứng minh: bằng việc chứng minh tương tự như trong định lý 1 trên, chúng ta chứng minh rằng
*
f (u ) 0

và
**
a f (u ) 0
. Nếu
0
*
a0
, thì
*
u

thỏa mãn MP bởi định lý 1. Nếu
0
*
a0
, thì
*
a0


và chúng ta có từ bất đẳng thức thứ 2 của FJSP 5.1.3 :
* * *
0 a f (u ) a f (u )
với mọi
0
uM

Nếu tập hợp
 
0
u u M , f (u ) 0
là khác rỗng, thì với bất kì 1 phần tử
u'
làm cho
*
a f (u ') 0
,
điều này mâu thuẫn với thiết lập ở phía trên:
*
a f (u ) 0
với mọi
0
uM
. Do đó
 
0
u u M , f (u ) 0   

4. Điều kiện cần của tiêu chuẩn tối ưu

Vấn đề điều kiện cần thì phức tạp hơn so với điều kiện đủ của tiêu chuẩn tối ưu. 2 trường hợp này
được so sánh trong bảng dưới đây:
Điều kiện cần
Điều kiện đủ
(a) Cần tính lồi
(b) Hệ quả của định lý tách của tập hợp lồi
thì cần thiết
(c) Điều kiện tổng quát (các tính chất ràng
buộc) thì quan trọng hơn trong điều
kiện cần (7 điều kiện dưới)
Không cần tính lồi
Hệ quả của định lý tách của tập hợp lồi thì
không cần thiết
Không cần tính chất ràng buộc

Chúng ta bắt đầu thiết lập các điều kiện cho tiêu chuẩn tối ưu mà không đòi hỏi bất kì một điều
kiện tổng quát nào. Tiêu chuẩn này giống điều kiện cho tiêu chuẩn tối ưu của Fritx John [John 48]
(xem chương 7), cái mà được suy ra cho trường hợp hàm

và
f
khả vi mà không lồi. chúng ta
không sử dụng tính khả vi nhưng chúng ta sử dụng tính lồi. Tiêu chuẩn hiện có là một tiêu chuẩn
điểm yên ngựa, trong khi tiêu chuẩn của Friz John là 1 tiêu chuẩn gradien. Điểm chính của sự
giống nhau là sự hiện diện của nhân tử
0
*
a
trong cả 2 tiêu chuẩn.
4.1 Định lý về kiều kiện cần cho tính tối ưu của bài toán điểm yên ngựa Fritz John

Cho M
0
là một tập lồi trong R
n
, và cho

và
f
lồi trong M
0
. Nếu
*
u
là 1 nghiệm của MP 5.1.1, thì
u*
và một vài
00
m
a * R , a* R , (a * ,a*) 0  
thỏa FJSP 5.1.3 và
a * f (u*) 0

Chứng minh:
Trang 11

Vì
u*
thỏa mãn MP
(u ) (u*) 0
f (u) 0

   

Không có nghiệm
0
uM

Bởi hệ luận 4.2.2 tồn tại
00
m
a * R , a* R , (a * , a*) 0  
sao cho
 
0
a * (u ) (u*) a * f (u ) 0    

với mọi
0
uM

Bởi cách đặt
u u *
như trên, chúng ta nhận được
a * f (u*) 0
. nhưng bởi vì
a * 0
và
*
f (u ) 0
, chúng ta có
**

a f (u ) 0
. Do đó
**
a f ( u ) 0
và
00
* * * * * *
a (u ) a f (u ) a (u) a f (u)    
với
mọi
0
uM

Là bất đẳng thức thứ 2 của FJSP 5.1.3
Bởi vì
*
f (u ) 0
, nên
*
af ( u ) 0
với mọi
m
a 0, a R
và do đó,
**
a f ( u ) 0

00
* * * * * * *
a (u ) af (u ) a (u ) a f (u )    

với mọi
m
a 0, a R
là bất đẳng thức thứ nhất của FJSP
5.1.3
4.2 Bài toán
Xét bài toán cực tiểu hóa
 
* * 0
uM
(u ) m in (u ) u M u u M , f (u ) 0, h (u ) 0

       

Trong đó h là một hàm véctơ tuyến tính k-chiều trong R
n
,

và f lồi trong M
0
và tất cả mọi thứ còn
lại thì được định nghĩa như trong MP 5.1.1. chứng minh rằng nếu
*
u
là một nghiệm của bài toán
trên thì
*
u
và một vài
0 0 0

* * m * k * * * * *
a R , a R , s R , (a , a ) 0, (a , a , s ) 0    
thỏa mãn
**
a f ( u ) 0
và:
0 0 0
00
* * * * * * * * *
m k 0
(u , a , a , s ) (u , a , a , s ) (u , a , a , s )
a 0 , a R , s R , u M
(u , a , a , s ) a (u ) af ( u ) sh (u )
  
    
    

Gợi ý: sử dụng lại hệ luận Corollary 4.2.2
Điều được lưu ý ở đây là trong điềk kiện cần của tiêu chuẩn tối ưu trên thì không đảm bảo
0
*
a0
.
Trong trường hợp
0
*
a0
, rõ ràng là điều kiện cần của tiêu chuẩn tối ưu FJSP 5.1.3 thì không
được đề cập nhiều như bài toán cực tiểu hóa MP 5.1.1., bởi vì hàm


không xuất hiện từ 5.1.3 và
bất kỳ một hàm nào khác có thể tuân thủ quy tắc của nó. Để mà loại trừ những trường hợp như
vậy, chúng ta có đưa vào 1 vài điều kiện chính quy. Những điều kiện chính quy này thì được liên
hệ với một vài tài liệu như tính chất ràng buộc. chúng ta sẽ có cơ hội để sử dụng những tính chất
ràng buộc này trong suốt cuốn sách này. Một vài những tính chất ràng buộc đó (giống như 3 cái
được giới thiệu dưới đây) chỉ sử dụng tính lồi của hàm được định nghĩa trong miền chấp nhận
Trang 12

được của M. một vài tính chất ràng buộc khác, được đưa vào sau, trong chương 7 phần ví dụ, hầu
hết sử dụng tính khả vi của hàm được định nghĩa trong miền chấp nhận được của M.

4.3 Tính chất ràng buộc Slater [Slater 50]
Cho là một M
0
tập lồi trong R
n
. hàm véctơ lồi m-chiều f trong M
0
được định nghĩa là lồi trong miền
chấp nhận được
 
0
M u u M , f (u ) 0  
thì thỏa mãn tính chất ràng buộc Slater (trong X
0
) nếu tồn
tại
*0
uM
sao cho

*
f (u ) 0
với mọi
0
uM

4.4 Tính chất ràng buộc Karlin [Karlin 59]
Cho là một M
0
tập lồi trong R
n
. Hàm véctơ lồi m-chiều f trong M
0
được định nghĩa là lồi trong
miền chấp nhận được
 
0
M u u M , f (u ) 0  
thì thỏa mãn tính chất ràng buộc Karlin (trong M
0
)
nếu không tồn tại
m
p R , p 0
sao cho
pf (u ) 0
với mọi
0
uM


4.5 Tính chất ràng buộc ngặt
Cho là một M
0
tập lồi trong R
n
. hàm véctơ lồi m-chiều f trong M
0
được định nghĩa là lồi trong miền
chấp nhận được
 
0
M u u M , f (u ) 0  
thì thỏa mãn tính chất ràng buộc ngặt (trong M
0
) nếu M
chứa ít nhất 2 điểm phân biệt
12
u , u
sao cho f là lồi ngặt tại
1
u

4.6 Bổ đề
Tính chất ràng buộc Slater 3 và tính chất ràng buộc Karlin 4 thì tương đương. Tính chất ràng buộc
ngặt 5 kéo theo tính chất ràng buộc Slater 3 và Karin 4.
Chứng minh:
(
34
) bằng định lý tổng quát Gordan 4.2.3 thì 3 và 4 tương đương
(5 3)

bởi vì M
0
là tập lồi, với bất kỳ
, 0 1   

1 2 0
(1 )u u M    

Bởi vì f là lồi ngặt tại
1
u
, từ 4.1.4 nó kéo theo rằng
1 2 1 2
f (1 )u u (1 )f (u ) f (u ) 0

         


Trong đó bất đẳng thức cuối kéo theo từ sự việc
1
f (u ) 0
và
2
f (u ) 0
. Vì vậy f thỏa mãn tính
chất ràng buộc Slater 3 và vì vậy tính chất ràng buộc Karlin 4 cũng thỏa mãn.
Chúng ta sẵn sàng để suy ra một điều kiện cần quan trọng nhất của tiêu chuẩn tối ưu không sử
dụng tính khả vi. Định lý được biết một cách rộng rãi dưới tên Kuhn-Tucker [Kuhn-Tucker 51],
tuy nhiên cả Kuhn và Tucker đều đòi hỏi cả tính lồi lẫn tính khả vi trong phép lấy đạo hàm từ
Trang 13


chính nó. Dạng hiện tại của định lý, không có đòi hỏi tính khả vi, là thuộc tính của Uzuwa [Uzuwa
58] và Karlin [Karlin 59].
4.7 Điều kiện tối ưu của định lý điểm yên ngựa Kuhn-Tucker
Cho M là tập mở rỗng trong R
n
và các hàm
, : , 1,
n
i
f g R R i m
. Xét bài toánP:
 
( ) m in,
: ( ) 0, 1,
i
f u u S
s u M g u i m




    


, cho
*uS
.
Kí hiệu
 

: ( *) 0
i
I i g u
. Giả sử các hàm
,,
i
f g i I
khả vi tại
*u
, còn
i
g
liên tục
tại
*,u i I
. Ngoài ra, giả sử
( *),
i
g u i I  
là các véctơ độc lập tuyến tính. Lúc đó, nếu
*u
là
điểm cực tiểu địa phương của bài toán P thì sao cho:
( * ) ( *) 0 0,
i i i
iI
f u g u voi i I


      



Hơn nữa, nếu
,
i
i I g
cũng khả vi tại
*u
thì
, 1,
i
im

  
sao cho:
( * ) ( *) 0
( * ) 0, 1,
0, 1,
m
ii
iI
ii
i
f u g u
g u i m
im






   



   


  





Tóm lại nếu
*u
là một phương án tối ưu địa phương thì
*u
thỏa mãn điều kiện Kuhn-Tucker và
được viết một cách ngắn gọn hơn như sau:
( * ) ( *) 0
( * ) 0
0
i
t
f u g u
gu




   








Trong đó
( *)gu
là ma trận với các cột là
( *), 1,
i
g u i m  
, còn
1 2 3
( , , , , )
m
    

là các
véctơ m chiều. Vậy điều kiện Kuhn-Tucker là điều kiện cần để
*u
là phương án tối ưu địa phương.
Định lý: cho tập mở khác rỗng
n
XR
và các hàm
, : , 1,

n
i
f g R R i m  
. Xét bài toán
 
( ) m in,
: ( ) 0, 1,
i
f u u S
s u M g u i m




    


, cho
*uS
.
Trang 14

Ký hiệu
 
: ( *) 0
i
I i g u
. Giả sử các hàm
,,
i

f g i I
là các hàm lồi và khả vi tại
*u
. Lúc đó,
nếu
0,
i
iI

   
sao cho:
( * ) ( *) 0
ii
iI
f u g u


   

thì
*u
là phương án tối ưu của bài toán P.
4.8 Định lý Kuhn-Tucker cần thiết cho tiêu chuẩn tối ưu trong sự hiện diện các ràng buộc
tuyến tính [Uzawa 58]
Lấy
, f

là một hàm hằng và một hàm vec tơ m-chiều mà cả hai hàm đều có tính lồi
trong
n

R
, nghĩa là, h(u)=Bu – d, trong đó B là ma trận k X n, và d là một k-vec tơ. Lấy
*u
là một nghiệm của bài toán cực tiểu hóa
 
( *) m in ( ) * | , ( ) 0,
n
uM
u u u M u u R f u Bu d


     

Và lấy f và h thỏa mãn tất cả các tiêu chuẩn ràng buộc:
(i) (Khái quát Slater 3) là có một nghiệm
n
xR










Hình 5.4.1: mối liên hệ giữa nghiệm của bài toán cực tiểu hóa địa phương
(LMP) 5.1.2, bài toán cực tiểu hóa (MP) 5.1.1, bài toán điểm yên ngựa Fritz
John (FJSP) 5.1.3, và bài toán điểm yên ngựa (KTSP) 5.1.4

(ii) (Khái quát Karlin 4) trong đó không tồn tại
0, ,
mk
p p R q R  
để mà

   
0pf u q Bu d  
cho tất cả
n
uR

(iii) (Khái quát Strict 5) X chứa hai điểm nhỏ nhất
1
u
và
2
u
để mà g là lồi chặt chẽ
tại
1
u

Khi đó
*
u
và một vài
* , * 0, *
mk
RR

  
  
thỏa mãn
 
* * 0fu


, và
     
       
*, , *, *, * , *, *
0, , ,
,,
m k n
u u u
R R u M
u u f u B u d
        
  
     

    
   

Trang 15

Chứng minh:
Chúng ta nên thiết lập nhóm đầu tiên để
 
( ) ( )iii i ii

và sau đó chứng
minh định lý dưới (ii).
[
( ) ( )iii i
] :
Vì
   
1 2 1 2
0, 0, ,f u f u Bu d Bu d   
, chúng ta phải cho
01


điều
đó
 
12
1B u u d


  

và
   
1 2 1 2
1 1 ( ) ( ) 0f u u f u f u
   

     



Do đó (i) cố định
[
( ) ( )i ii
] :
Nếu
 
*0fu 
và
*Bu d
khi đó với mọi
0,
m
p p R
và với mọi
   
, * * 0
k
q R pf u q Bu d   

Do đó (ii) cố định
Chúng ta thiết lập định lý dưới (ii). Điều đó sẽ không mất tính tổng quát nếu
chúng ta giả định các hàng
1
, . . .,
k
BB
của B độc lập tuyến tính, vì giả sử rằng một
số hàng, B
k


độc lập tuyến tính
11
, . . ., ,
k
BB

trong đó
1
1
k
k i i
i
B s B




trong đó
11
, . . .,
k
ss

là số
thực được xác định. Khi đó
11
11
kk
k k i i k i i k

ii
B u d s B u d s d d


    


với mọi u thỏa mãn
, 1, , 1 .
ii
B u d i k  
Nhưng vì
*uM
, và
, 1, , ,
ii
B u d i k

nó kéo theo
1
1
0
k
i i k
i
s d d





và
0
kk
B u d
với mọi u thỏa mãn
, 1, , 1 .
ii
B u d i k  

Do đó sự ràng buộc đẳng thức
kk
B u d
là thừa nghiệm và có thể được giảm từ
bài toán cực tiểu hóa không thay đổi nghiệm
*u
. Khi đó, một lần nữa chúng ta
thiết lập định lý cho các hàng độc lập tuyến tính của B, chúng ta có thể biến đổi
các hàng
k
B
(mà không làm thay đổi bài toán cực tiểu hóa) và bộ
*0
k


trong
bài toán điểm yên ngựa
Bằng 2 định lý trên, tồn tại
   
0 0 0

, , , , 0, , , 0
mk
r R r R s R r r r r s    

mà thỏa
 
* * 0a f u 
và thỏa bài toán điểm yên ngựa của 2. Nếu
0
*0a 
, khi
đó
00
* * / * , * * / *a a s a


giải quyết bài toán bởi định lý mà chúng ta đã làm.
Cho
0
*0a 
. Khi đó vì
 
* * 0a f u 
và
*0Bu d
, chúng ta có bất đẳng thức
thứ hai của bài toán điểm yên ngựa của 2 là
 
0 * * ( ) 0a f u s Bu d   
với mọi

n
uR

Trang 16

Mâu thuẫn với phần (ii) trên, nếu
*
0a 
. Giả sử rằng
*0a 
khi đó
*0s 
và
* ( ) 0s Bu d
với mọi u trong
n
R
. Do đó( xem phần chứng minh của 4.2.4) ,
mâu thuẫn với giả thiết là các hàng của B là độc lập tuyến tính. Vậy
0
*0a 

4.9 Mở rộng điều kiện tối ưu Kuhn-Tucker
Định lý: (điều kiện tối ưu cần và đủ)
Cho tập mở khác rỗng
n
MR
. Xét bài toán:
( ) m in ,
: ( ) 0, 1, ,

( ) 0, 1, , ,
n
i
n
i
f u u S
P g u i m u M R
h u i r u M R



   


   


Giả sử
*
uS
và các hàm
,,
i
f g i I
(với
 
*
: ( ) 0
i
I i g u

) là khả vi tại
*
u
, còn
các hàm
i
g
là liên tục tại
*,u i I
, các hàm
i
h
là khả vi liên tục tại
*, 1,u i r
.
Ngoài ra, giả sử
( *),
i
g u i I  
và
( *), 1,
i
h u i r  
là các véc tơ độc lập tuyến
tính.
Lúc đó nếu
*u
là điểm cực tiểu địa phương của bài toán P thì
, , 1,
ii

i I va i r

    
sao cho:
( *) ( *) ( *) 0
0,
r
i i i i
i I i I
i
f u g u h u
iI




     



  



Nếu ngoài ra, các hàm
:,
n
i
g R R i I  
: cũng khả vi tại

*
uS
, thì điều kiện
Kuhn-Tucker (điều kiện cần) để là phương án tối ưu có thể được viết như sau:
( * ) ( *) ( *) 0
( * ) 0, 1,
0, 1,
mr
i i i i
i I i I
ii
i
f u g u h u
g u i m
im





     



  


  






Ngược lại, cho
*
uS
và các điều kiện sau đây được thỏa mãn:

0, 0, 1,
ii
i I va i r

       
, sao cho:
( *) ( *) ( * ) 0
r
i i i i
i I i I
f u g u h u


     


 Các hàm
,,
i
f g i I
lồi và khả vi tại
*u



 
i J : 0
i
i

   
, các hàm
i
h
là lồi, còn
 
:0
i
i K i

   
, các hàm
i
h
là lồi
Lúc đó,
*u
là phương án tối ưu của bài toán P
5. Bài tập
Xét bài toán quy hoạch lồi:
Trang 17

22

1 2 1 2 1 2
12
12
1
2
( ) 2 3 4 6 3 m in
1
: 2 3 2 4
0
0
f u u u u u u u
uu
P u u
u
u

     









  


Ta có thể viết lại

   
11
12
22
44
1
( ) 6 3
46
2
uu
f u u u
uu
   

   
   


   

Lúc này điều kiện Kuhn-Tucker có dạng:
12
1 2 3 4
21
1 1 2
2 1 2
31
42
4 4 6
1 2 1 0

0
6 4 3 1 3 0 1
( 1) 0
(2 3 4 ) 0
:
0
0
0, 1, 4
i
uu
uu
uu
uu
P
u
u
i
   









       
    



       
  
       



  


  







  



Chọn u
2
=0, khi đó u
1
=1.
Xét
1
*

0
u




. Từ hệ điều kiện trên ta có
23
0


nên
14
2 1 0
0
1 1 1


     
  
     

     
Do đó
14
2, 1



Vậy

1
*
0
u




là phương án tối ưu toàn cục