1BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2

NGUYỄN THỊ HIỂN
PHƯƠNG PHÁP SỐ GIẢI BÀI TOÁN
QUY HOẠCH TOÀN PHƯƠNG

Chuyên ngành: Toán Giải tích
Mã số: 60 46 01 02
LUẬN VĂN THẠC SĨ TOÁN HỌC

Người hướng dẫn khoa học: PGS. TS. Tạ Duy Phượng
HÀ NỘI, 2014

2


Học viên

Nguyễn Thị Hiển
4Mục lục
Lời nói đầu…………………………………………………………… 6
Chương 1. Bài toán quy hoạch toàn phương………………………… 8
1.1. Bài toán tối ưu…………………………………………………… 8
1.2. Một số khái niệm cơ bản………………………………………… 9
1.3. Định lí tồn tại nghiệm của bài toán quy hoạch toàn phương………. 10
1.4. Các điều kiện cực trị 16
Chương 2. Một số phương pháp số giải bài toán quy hoạch toàn phương
…………………………………………………………………………… 21
2.1. Phương pháp hạn chế tích cực……………………………………… 21
2.2. Phương pháp hạn chế giả định…………………………………… 29
2.3. Phương pháp Gradient đối ngẫu……………………………………. 33
2.4. Phương pháp điểm trong……………………………………………. 38
Kết luận………………………………………………………………… 50
Tài liệu tham khảo………………………………………………………… 51

L X Y
Không gian các toán tử tuyến tính liên tục từ X vào Y.

 
2
;
a b
L
6MỞ ĐẦU
1. Lý do chọn đề tài
Trong những năm gần đây, các phương pháp tối ưu đã được áp dụng sâu rộng
và hiệu quả vào cách ngành kinh tế kỹ thuật, công nghệ thông tin và các
ngành khoa học khác. Nhờ các công cụ tính toán ngày càng hoàn thiện mà các
công trình nghiên cứu lý thuyết và thực hành của Tối ưu hóa ngày càng mở
rộng và phát triển.
Ngày nay, đối với các kỹ sư và các nhà nghiên cứu khoa học, kỹ thuật, kinh
tế, công nghệ thông tin, sự hiểu biết về các phương pháp tối ưu cũng cần thiết
như các kiến thức cơ sở của Giải tích, Vật lý, Hóa học,…
Bài toán quy hoạch toàn phương đã được nhiều người nghiên cứu, nhưng cho
đến nay nó vẫn là bài toán mang tính thời sự. Với mong muốn tìm hiểu sâu
hơn và nghiên cứu về phương pháp số giải bài toán quy hoạch toàn phương

8

Chương 1
Bài toán quy hoạch toàn phương
1.1 Bài toán tối ưu
Tối ưu hóa là một lĩnh vực toán học nghiên cứu lí thuyết và các thuật toán giải
bài toán cực trị.
Nhiều vấn đề thực tế khác nhau dẫn tới việc giải bài toán cực trị sau:
Tìm cự tiểu của phiếm hàm


min
f x  (1)
với các điều kiện:





   
 
1
2
0, 1,2, , 2
0, 1,2, , 3

4
i
j
n

i j
g h
gọi là các hàm ràng buộc (các hạn
chế). Tập hợp các vectơ
n
x X
 

thỏa mãn các ràng buộc (2), (3) gọi là
tập phương án hay miền chấp nhận được (miền ràng buộc) bài toán trên.
Phương án
*
x
thỏa mãn




*
f x f x

với mọi phương án chấp nhận
x
gọi
là phương án tối ưu hay lời giải của bài toán,


*
f x
được gọi là giá trị tối


  
trong đó A là ma trận xác định dương,

là hằng số, còn các hàm ràng buộc






1 2
, , 1, , 1,
i j
g x h x i m j m
  đều là
các hàm tuyến tính. Đối với quy hoạch toàn phương đã có những thuật toán
rất nổi tiếng của Beale, Frank-Wolfe,….
Bài toán quy hoạch toàn phương được xét ở đây là trường hợp đặc biệt của
bài toán quy hoạch lồi.
Bài toán quy hoạch lồi là bài toán:



min
f x 
với các điều kiện:




 
gọi là hàm toàn phương nếu có dạng
10

     
1 1 1
1 1
, ,
2 2
1
,
2
T T
n n n
ij i j i i
i j i
f x x Dx c x x Dx c x
d x x c x
 

  
     
  
 

trong đó D là một ma trận cấp n×n, c là một vectơ n chiều, α là một số.
Nhận xét Vì
 
1
,



là tập đa diện (polyhedral set).
Nếu f lồi thì (P) được gọi là bài toán quy hoạch toàn phương lồi.
Định nghĩa
Ma trận D được gọi là xác định dương nếu
0, 0.
T
v Dv v
  

Ma trận D được gọi là xác định không âm (nửa xác đinh dương) nếu
0.
T
v Dv


Nhận xét Nếu D là ma trận đối xứng, nửa xác định dương thì f là hàm lồi.
1.3 Định lí tồn tại nghiệm của bài toán quy hoạch toàn phương
Xét bài toán (P):
11 
1
Minimize : ,
2
s.t. , ,
T T
n

Nếu
  
thì có hai trường hợp xảy ra:




là một số thực


.

 



 
thì bài toán (P) không có nghiệm.
Câu hỏi 1 Khi

 
thì tồn tại hay không một điểm
x

để hàm số đạt
giá trị cực tiểu, tức là tồn tại hay không một điểm
x

sao cho



Ta thấy




inf : 1 0
f x x
 
nhưng không tồn tại
x
để


0
f x

.
Định lí 1.1 (Frank-Wolfe, 1956) Nếu




inf :f x x

 
là hữu hạn thì bài
toán (P) có nghiệm, tức là tồn tại
x




Với




2
1 2 1 2 1 2
, : 1, 0, 0
x x x x x x x
      

ta có:




inf : 0
f x x

  

nhưng không tồn tại


1 2
,
x x x
 sao cho





2
1 2 1 2
, : 0, 0 .
x x x x x     


Chọn
1
,1
k
x k
k
 
 
 
 
thì
 
 
2
2 2
1 1 2
1 1 0,
k
k
f x k


 

vô nghiệm.
Câu hỏi 2 Khi nào


f x
bị chặn dưới trên trên tập
?


Định lí 1.2 (Eaves, 1971) Bài toán (P) có nghiệm khi và chỉ khi ba điều kiện
sau được thỏa mãn:
1.
  

2. Nếu
, 0
n
v Av
 

thì
0
T
v Dv

.
3. Nếu

  

Giả sử
n
v


và
0.
Av


13

Do


, 0
A x tv Ax tAv b t
     
nên
, 0.
x tv t
   

Vì
x
là nghiệm nên



T
T
t v Dv t Dx c v t
    
, hay
0
T
v Dv

.
Chứng tỏ điều kiện 2 được thỏa mãn.
Từ trên ta thấy, nếu
x
là nghiệm của bài toán (P) thì điều kiện 2 được thỏa
mãn, tức là
0
T
v Dv

với mọi
n
v


mà
0.
Av

Bây giờ giả sử
0

hay
       
1
, 0,
2
T
T
x tv D x tv c x tv f x t
      

tức là
 
2
1 1
, 0.
2 2
T T T T T
x Dx t v Dv tx Dv c x tc v f x t
      

Do
0
T
v Dv

nên biểu thức trên trở thành
   
1
, 0.
2

0
T
Dx c v
 
.
Chứng minh
Hiển nhiên, điều kiện 1 và điều kiện 3 của Định lí Eaves được thỏa mãn.
Vì
D
là ma trận đối xứng nửa xác định dương nên
0, ,
T n
x Dx x  

hay
0, .
T n
v Dv v  

Do đó điều kiện 2 của Định lí Eaves (Định lí 1.2) được
thỏa mãn.
Hệ quả 1.2 Giả sử
D
là ma trận đối xứng nửa xác định âm. Khi đó (P) có
nghiệm khi và chỉ khi các điều kiện sau được thỏa mãn:
(i)
  
.
(ii) Nếu
, 0


hay
0, .
T n
v Dv v  


Theo điều kiện 2 của Định lí Eaves (Định lí 1.2) thì từ
, 0
n
v Av
 

, suy ra
0.
T
v Dv

Chứng tỏ
0.
T
v Dv


Mặt khác, từ điều kiện
0
Av

suy ra
0.

 
Kết hợp với Hệ quả 1.1 ta có điều phải chứng minh.
Hệ quả 1.4 Giả sử D là ma trận đối xứng xác định âm. Khi ấy (P) có nghiệm
khi và chỉ khi

khác rỗng và compact.
15

Chứng minh Do D là ma trận đối xứng nửa xác định âm nên điều kiện (ii),
(iii) của Hệ quả 1.2 được thỏa mãn khi và chỉ khi tập


: : 0
n
L v Av
  


chứa một phần tử
0
v

. Vì
L
là nón lùi xa của tập đa diện lồi


:
n
x Ax b


: , 0 .
n
x Ax b x
      


2. Nếu
, 0
n
v Av
 

, thì
0.
T
v Dv


3. Nếu
, , 0, 0, 0, , 0
n n T
v x Av v v Dv Ax b x
      
 
thì


0.
T

x Dx c x x Ax b Cx d
 
   
 
 

(P2)
có nghiệm khi và chỉ khi các điều kiện sau thỏa mãn:
1.


: , ;
n
x Ax b Cx d
      


2. Nếu
, 0, 0
n
v Av Cv
  

thì
0;
T
v Dv


16

 
   
   
 
   


Khi đó bài toán (P2) có thể viết lại thành


1
min : , .
2
T T n
x Dx c x x Ax b
 
  
 
 



Áp dụng Định lí 1.2 suy ra điều phải chứng minh.
1.3 Các điều kiện cực trị
1.3.1 Điều kiện cực trị cấp 1
Định lí 1.3 Giả sử
x
là nghiệm của bài toán sau đây:

 


, 0, \
Dx c x x x x
     , (1.3)
thì
x
là nghiệm địa phương của (1.1), hơn nữa tồn tại
0


và
0


sao cho






, , .
f x f x x x x B x
 
     

Chứng minh
i) Nếu
x
là nghiệm địa phương của (P), thì tồn tại






, , 0, .
x t x x B x t
 
     
Suy ra






0.
f x t x x f x
   

Bởi vậy






 
 
0

0
0, 0
0
T
T
Dx A c
Ax b
Ax b




  

  


 

(1.5)
Chứng minh Kí hiệu
i
A
là dòng thứ i của A, và tập
,
T
i i
a A

i



1
: ,
i i
I i I a x b
  
.
Giả sử
n
v


thỏa mãn


0
, 0, .
i
a v i I
  

Tương tự như chứng minh Định lí 1.3 (ii), tồn tại
1
0


sao cho



Dx c v
 
Khi đó
ta có


, 0
Dx c v
  
với mỗi
n
v


thỏa mãn


0
, 0,
i
a v i I
   
.
Theo Định lí 1.3 tồn các số thực không âm


0
i
i I


T
i i
a A i I
  
với, từ (*) ta thu được phương trình đầu tiên trong (1.5).
Do
x

và


0
i i i
A x b

 
với mỗi
i I

, những điều kiện khác trong (1.5)
cũng được thỏa mãn. Định lí được chứng minh.
Hệ quả 1.7 (Murty, 1972) Nếu
n
x


là nghiệm địa phương của bài toán
1
min : , , 0
2


   


    


(1.6)
Hệ quả 1.8 Nếu
n
x


là nghiệm địa phương của bài toán (P2)
1
min : , ,
2
T T n
x Dx c x x Ax b Cx d
 
   
 
 

thì tồn tại
n



và

n
x


là
nghiệm địa phương của bài toán (P2) là tồn tại một cặp vectơ




1 1
, , , , , ,
m s
m s
     
  
 
sao cho
i) Hệ
 
0
0, , 0 (1.8)
0
T T
T
Dx A C c
Ax b Cx d
Ax b
 


: , 0 , : , 0
i i i i i i
I i Ax b I i Ax b
 
     

thì
0.
T
v Dv


Chứng minh Xem [1] trang 50, 52-58.
Định lí 1.6 (Cottle, 1992) Điểm
n
x


là nghiệm địa phương của bài toán
(P2) nếu hai điều kiện sau được thỏa mãn:
i)






, 0, ,
f x v Dx c v T x



 
trong đó








: , 0 .
n
f x v f x v

    

Chứng minh Xem [1], trang 52.
Định lí 1.7 (Mangasarian 1980, Contesse 1980) Điểm
n
x


là nghiệm địa
20

phương của bài toán (P2) khi và chỉ khi tồn tại


,

I i A x b


  
  

thì
0.
T
v Dv


Chứng minh Xem [1], trang 58 - 60.
Định lí 1.8 Điểm
n
x


là nghiệm địa phương duy nhất của bài toán (P2)
khi và chỉ khi hai điều kiện sau đây được thỏa mãn:
i)








, 0,

trong đó








: , 0 .
n
f x v f x v

    
Chứng minh Xem [1], trang 60 - 61.
Định lí 1.9 Nếu
n
x


là nghiệm địa phương duy nhất của bài toán (P2) thì
tồn tại
0, 0
 
 
sao cho





2.1.1 Bài toán quy hoạch toàn phương
Xét bài toán quy hoạch toàn phương (PQ)
1
min ( ) ,
2
, ,
, ,
T T
T
i i
T
i i
f x x Dx c x
a x b i I
a x b i E

 



 


 



(PQ)
trong đó
D


* *
* *
*
0,
( ) 0, ,
0, .
i i
i I E
T
i i i
i
Dx c a
b a x i I
i I





  


  


 




,
x x M

thì
1 2
x x M
 
 
với mọi
,
 


.
Ta có điều kiện cực trị sau cho bài toán (EP):
n
x


là nghiệm của bài toán (EP) khi và chỉ khi tồn tại
m



sao cho
0,
T
Dx c A

  

,
n m


2
Q
là ma trận cấp
( ).
n n m
 

Vì
Q
là ma trận trực giao nên ta có:
23

1 1 2 2 1 2
, , , 0.
T T T T
n m m n
Q Q I Q Q I Q Q I Q Q

   

Suy ra
2 1 2 1 2
( ) 0.
T T T
AQ Q R Q R Q Q
  

thì
0 1 1
1 1 1 1
( ) ( ) ( ) .
T T T T T
Ax Q R Q R b R Q Q R b b
 
  

Giả xử
x
là điểm chấp nhận được của bài toán (EP), tức là
.
Ax b

Khi ấy
0
( ) 0,
A x x
 
do đó
0
( ).
x x N A
 
Bài toán (EP) được đưa về bài toán tối ưu toàn phương không hạn chế:
min ( ),
,
n m
f z

  
    
    


Theo điều kiện cần cực trị cho bài toán tối ưu không có hạn chế ta có:
z
là
nghiệm của bài toán (P) khi và chỉ khi
z
là nghiệm của hệ tuyến tính
0
2 2 2
( ) ( ) ( ) 0.
T T
f z Q DQ z Q Dx c
    


Do đó
0
2 2 2
( ) ( ).
T T
Q DQ z Q Dx c
  
(2.3)
24

Trong công thức trên

Q R Dx c

 
Do đó
1
1
( )
R Q Dx c


 
hay
1
( ),
T
R Q Dx c

 
trong đó R là ma trận tam giác trên khả nghịch.
Giải hệ phương trình này từ dưới lên trên ta tìm được
.


Nhận xét Nếu ma trận
2 2
T
D Q DQ


là xác định dương thì

: .
k T k
i i
A E i I a x b
  

Cùng với bài toán (EP)
1
min ( ) ,
2
, ;
,
T T
T
i
T
i
f x x Dx c x
a x b i I
a x b i E

 



 


 



( ).
k k k
c Dx c f x
    (2.4)
Theo điều kiện cần và đủ cực trị, điểm
k
s
thỏa mãn điều kiện tối ưu khi và
chỉ khi tồn tại các
k
i

không đồng nhất bằng 0 sao cho
0
0,
k
k k k
i i
i A
T k k
i
Ds c a
a s i A



  



s
là nghiệm tối ưu của bài toán
k
(EP )
khi và chỉ khi
k k
x x s

 
là nghiệm tối ưu của bài toán
k
(PQ )

1
min
2
,
T T
T k
i i
x Dx x c
a x b i A





 



.
k k k
x x x s


  

 Nếu tồn tại
k
i A

để
0
T k
i
a s

thì ta phải đi theo hướng
k
s
để tìm
điểm chấp nhận được. Đặt