LỜI CẢM ƠN

Em xin bày tỏ lòng biết ơn sâu sắc tới thầy ThS. Nguyễn Quốc Tuấn, 
giảng viên khoa Toán trường Đại học Sư phạm Hà Nội 2, đã tận tình hướng 
dẫn, giúp đỡ để em hoàn thành khóa luận này.
Trong quá trình học tập, đặc biệt là trong suốt quá trình làm khóa luận 
em đã nhận được sự dạy dỗ ân cần cũng như những động viên, chỉ bảo, tạo 
điều kiện của các thầy cô giáo tham gia giảng dạy, công tác tại trường Đại học 
Sư phạm Hà Nội 2. Qua đây, em xin được gửi lời cảm ơn tới các thầy cô giáo 
trong  tổ  Giải  tích,  khoa  Toán  trường  Đại  học  Sư  phạm  Hà  Nội  2,  cùng  các 
thầy cô giáo giảng dạy khóa học. 
 Một lần nữa em xin chân thành cảm ơn! 
 

Hà Nội, Ngày 04 tháng 05 năm 2012
                                                                               Sinh viên

                                                                     Hoàng Thị Hồng Hạnh

 

1 


LỜI CAM ĐOAN

Dưới  sự  hướng  dẫn  của  thầy  ThS.  Nguyễn  Quốc  Tuấn  khóa  luận  tốt 
nghiệp đại học chuyên ngành Toán với đề tài “Điều kiện cần và đủ cực trị cho 
bài  toán  quy  hoạch  toàn  phương  trên  tập  lồi  đa  diện”  được  hoàn  thành  bởi 
chính sự nhận thức của bản thân, không trùng với bất cứ khóa luận khác.
Trong quá trình nghiên cứu thực hiện khóa luận, em đã kế thừa những 


 

3 


LỜI MỞ ĐẦU
Hiện nay, tối ưu hóa đã trở thành một lĩnh vực rất phát triển, góp phần 
quan trọng trong việc ứng dụng khoa học công nghệ vào cuộc sống và sản xuất. 
Từ  thế  kỉ  XVIII,  một  hướng  của  Giải  tích  toán  học,  gọi  là  Phép  tính 
biến phân, chuyên nghiên cứu các bài toán cực trị với hàm mục tiêu là phiếm 
hàm tích phân được phát triển mạnh mẽ và trở thành ngôn ngữ của khoa học 
tự nhiên. Vào những năm cuối thập niên  30  40  của thế kỉ XX, nhu cầu cấp 
bách của kinh tế, kĩ thuật đã thúc đẩy hình thành một lý thuyết mới đó là lý
thuyết tối ưu. Có thể nói, lý thuyết tối ưu bắt đầu từ quy hoạch tuyến tính, tiếp 
đó là quy hoạch lồi. Đối tượng nghiên cứu của những lý thuyết đó ngày càng 
mở rộng, hình thành những hướng khác nhau của lý thuyết tối ưu. 
Bài  toán  tối  ưu  được  phát  biểu  như  sau:  “Cho  hàm  mục  tiêu  f   và 


n

  là  miền  ràng  buộc.  Tìm  x     sao  cho  f  x    nhận  giá  trị  cực  tiểu 

(trong trường hợp muốn tìm giá trị cực đại thì có thể thay  f  x    f  x  )”. 
Các bài toán tối ưu còn được gọi là các bài toán quy hoạch toán học, 
được chia ra thành các lớp sau đây: 


Bài toán quy hoạch tuyến tính; 

Trong thực tế, bài toán quy hoạch tuyến tính với hàm mục tiêu và các 

ràng  buộc  tuyến  tính  có  một  số  lượng  lớn  các  ứng  dụng.  Bài  toán  mà  hàm 
mục tiêu của chúng không ở dạng tuyến tính mà có dạng bậc hai được gọi là 
bài toán quy hoạch toàn phương. Với bài toán này thì các phương pháp giải có 
mối quan hệ tới các mở rộng của bài toán quy hoạch tuyến tính. 
Điều kiện tối ưu đóng một vai trò quan trọng trong lý thuyết tối ưu hóa. 
Năm 1965, A. Ya. Dubovitskii và A. A. Milyutin đã đưa ra lý thuyết các điều 
kiện cần tối ưu dưới ngôn ngữ giải tích hàm và cho ta phương pháp giải tích 
hàm hiệu quả để nghiên cứu các bài toán tối ưu và điều khiển. 
Ngày nay, điều kiện cần và đủ cực trị đầu tiên cho bài toán quy hoạch 
toàn  phương  (không lồi) trong định lý 2.1  đã  được chứng  minh  trong nhiều 
sách.  Nó  được  xem  như  là  một  mở  rộng  tự  nhiên  của  định  lý  Fermat. 
McCormick (1967) là người đầu tiên đặt nền móng cho điều kiện cần và đủ 
cực trị thứ hai của bài toán toàn phương (xem [8]). Sau đó, Majthay (1971), 
Mangasarian (1980) và Contesse (1980) đã từng bước hoàn thiện chứng minh 
điều kiện cần và đủ cực trị thứ hai (định lý  2.4  2.5 ) cho bài toán quy hoạch 
toàn phương. 
Là  một  sinh  viên  sư  phạm  chuyên  ngành  Toán,  tôi  mong  muốn  được 
tìm  hiểu  sâu  hơn  về  lý  thuyết  tối  ưu  nói  chung  cũng  như  quy  hoạch  toàn 
phương nói riêng. Đặc biệt, dưới sự gợi mở, hướng dẫn, chỉ bảo tận tình của 
thầy ThS. Nguyễn Quốc Tuấn, tôi đã chọn đề tài
“Điều kiện cần và đủ cực trị cho bài toán quy hoạch toàn phương
trên tập lồi đa diện”. 
Khóa luận tập trung làm rõ một số nội dung liên quan đến bài toán quy 
hoạch toán học, quy hoạch toàn phương, điều kiện cần và đủ cực trị cho bài 

 

5 



Bài toán quy hoạch toàn phương
Bài  toán  quy  hoạch  toàn  phương  là  một  phần  của  bài  toán  học  quy 
hoạch phi  tuyến.  Chương này,  trình bày  một  số  nội dung  liên  quan  đến quy 
hoạch toán  học,  bài  toán quy  hoạch toàn  phương.  Chẳng hạn,  khái  niệm  bài 
toán quy hoạch toán học, nghiệm toàn cục, nghiệm địa phương, bài toán quy 
hoạch  toàn  phương,  ma  trận  xác  định  dương  (tương  ứng,  xác  định  âm),  ma 
trận xác định nửa dương (tương ứng, xác định nửa âm)…

1.1. Bài toán quy hoạch toán học 
Trong phần này, ta ký hiệu 
thẳng thực mở rộng, 

n

  ,   

     là đường 

 là không gian Euclid  n  chiều với chuẩn 
1/2

 n

x    xi2  ,  
 i 1 
n

với mọi  x   x1 , x2 ,..., xn  

Vì  vậy,  B  x,     y 

 

n

: y  x    , B  x,     y 

n

: y  x    . 

Hình cầu đóng đơn vị  B  0,1  được kí hiệu là  B n . Cho một tập   

n

, các 

kí hiệu  int  ,    và  bd  được sử dụng tương ứng để biểu thị phần trong của 
 , bao đóng của    và biên của   . 

Do  đó,     x 

 

n

trong 

:   0, B  x,         là  tập  đóng  nhỏ  nhất 


 


n

n

  là  một  hàm  khả  vi  liên  tục  cấp  hai  trên  tập 



, điểm  x , v 

n

. Khi đó, ta ký hiệu  f  x   là đạo hàm của hàm 

f   tại  điểm  x ,  ký  hiệu   2 f  x    là  đạo  hàm  cấp  hai  (ma  trận  Hessian)  của 

hàm  f  tại điểm  x  và ký hiệu  f   x , v   là đạo hàm theo hướng  v  của hàm  f  
tại điểm  x . Ta có, 

 

f   x , v   lim
t 0

f  x  tv   f  x 
 f  x  , v . 

  là một hàm cho trước,   

n

 là một tập hợp con xác 

định. Bài toán   P   có thể viết lại dưới dạng  
min  f ( x) : x   . 

Định nghĩa 1.1. Bài toán  P  được gọi là một bài toán quy hoạch toán học.
Hàm f gọi là hàm mục tiêu và ∆ là tập ràng buộc (hay miền chấp nhận
được) của bài toán  P  . Các phần tử của tập ràng buộc ∆ được gọi là các
vector chấp nhận được của bài toán  P  .
Nếu   

n

 thì ta nói bài toán   P   là một bài toán không có ràng buộc, 

ngược lại, bài toán   P   là bài toán có ràng buộc. 
Ví dụ 1.1. Bài toán  min f  x   cx1  cx2  ...  cn xn , với điều kiện ràng buộc    
 a11 x1  a12 x2  ...  a1n xn  b1
 a x  a x  ...  a x  b
2n n
2
 21 1 22 2
 ............................................  
a x  a x  ...  a x  b
mn n
m

Ta nói, x   là nghiệm tối ưu địa phương của bài toán  P  nếu

f  x    và tồn tại một lân cận U của x sao cho
f  x   f  x  , x    U .                                    (1.1) 

Tập  các nghiệm  tối  ưu  toàn  cục  của  bài  toán   P  ,  kí  hiệu  là  Sol  P   
(hoặc  Sol  f  ). Tập các nghiệm tối ưu địa phương của bài toán   P  , kí hiệu 
là  loc  P    (hoặc  loc  f  ).  Hai  bài  toán  tối  ưu  gọi  là  tương  đương  nếu  tập 
nghiệm của chúng trùng nhau. 
Định nghĩa 1.3. Giá trị tối ưu  ( P) của  P  được xác định bởi

 ( P)  inf  f ( x) : x   .

(1.2)

Nếu    thì qui ước  ( P)  .  
Nhận xét 1.1. Hiển nhiên, ta có  Sol  P   loc  P  , vì theo định nghĩa 

Sol ( P)   x   : f ( x)  ; f ( x)   ( P)  loc  p  . 

 

10 


Ví dụ 1.3. Xét bài toán   P   với  f  x   cos x,   x   

. Khi đó,  min f  x  ,  

với mọi  x   , có vô số nghiệm tối ưu toàn cục, cụ thể 


1,5
 

O 

x
 

2
 

  

f  x  x  2  

Hình 1.1. 
Nhận xét 1.2. Nói chung,  loc( P ) \ Sol ( P )   . 
Ví dụ 1.5. Cho bài toán   P   với hàm  f ( x)  2 x3  3x 2  1 và tập     1,    
thì  x  1  là nghiệm địa phương nhưng không phải là nghiệm toàn cục của bài 
toán   P  , vì  Sol  P   1 . 

f  x  

 
 

2 

1  


: x12  x22  4, x12  1 .  Hàm 

f   có  nghiệm  toàn  cục  là  x   2,0   

và có vô số nghiệm địa phương, đó là 





cả  đoạn  thẳng  nối  x  1, 3   và 





x  1,  3 . 

Giá 

trị 

tối 

ưu 

  f  x    2 . 
 


2

x
 

12 


 

 
 
 
 
Hình 1.4 

Nhận xét 1.3. Thay bài toán   P   ở trên bằng bài toán tìm giá trị lớn nhất sau 
max f ( x) ,  x   .                                             P1   

Nghiệm  x  được gọi là nghiệm (nghiệm tối ưu toàn cục) của   P1   nếu 

f  x      và  f  x   f  x  , với mọi  x   . 
Ta  nói,  x     là nghiệm  địa  phương  của   P1    nếu  f  x      và  tồn 
tại một lân cận  U  của  x  sao cho  f  x   f  x  , với mọi  x    U . 
Trong hình 1.5 các điểm 

A, C , E  là nghiệm cực tiểu địa phương; 
B, D  là nghiệm cực đại địa phương; 
C  là nghiệm cực tiểu toàn cục; 
F  là nghiệm cực đại toàn cục. 

của bài toán   P1   khi và chỉ khi  x  là nghiệm tối ưu (tương ứng, nghiệm tối ưu 
địa phương) của bài toàn tìm giá trị nhỏ nhất sau 
min( f ( x)) ,  x   . 

Do vậy, bất kì bài toán tìm giá trị lớn nhất dưới dạng   P1   đều có thể 
đưa về bài toán tìm giá trị nhỏ nhất dưới dạng   P  . Chẳng hạn, ta xét bài toán 
tìm giá trị lớn nhất dạng 
max f  x   3x1  x2  x32 , 

với các ràng buộc 
 x1  x2  x3  0
 

2
 x1  2 x2  x3  0.

Ta có, bài toán tìm giá trị nhỏ nhất dạng 
min   f  x    3 x1  x2  x32 , 

 

14 


với các ràng buộc 
 x1  x2  x3  0
 

2
 x1  2 x2  x3  0.


 

f  x  

f  x  x  

x  0,
 
x  0.

f  x  

 

f  x 

1
 
x

 
x 
O 

 

 
 


cấp n , một vector c 

n

và

một số thực  thỏa mãn

f ( x) 

1 T
1
x Dx  cT x    x, Dx  c, x   , x 
2
2

n

.          (1.3)

 d11 ... d1n 
 c1 
 x1 




Nếu  D   ... ... ...   ;  c   ...   ;  x   ...    thì (1.3) có nghĩa là 
d


D  DT  . Do đó, chúng ta 

2

giả thiết rằng các ma trận vuông của hàm toàn phương là đối xứng. Tập các 
ma trận đối xứng cấp  n  n  được kí hiệu là 

nn
S

. 

Định nghĩa 1.5. Bài toán  P  được gọi là bài toán quy hoạch toàn phương
trên tập lồi đa diện nếu hàm f là một hàm toàn phương và  là một tập lồi
đa diện.
Trong  (1.3), nếu  ma  trận  D  là  ma trận không  thì hàm  f   là  một  hàm 
afin. Do đó, việc nghiên cứu bài toán tuyến tính là một phần của bài toán toàn 
phương. Nói chung, bài toán toàn phương là bài toán không lồi. 
Rõ  ràng,  nếu  xóa  hằng  số    của  f   trong  công  thức  (1.3)  thì  chúng 
không  làm  thay  đổi  các  giả  thiết  của  bài  toán  min  f ( x) : x     trong  đó 



n

  là một tập lồi đa diện.  

Vì vậy, để đơn giản hóa hàm mục tiêu, chúng ta thay (1.3) bằng công thức 
f ( x) 


n


, Ax  b, x  0  ,  


, Ax  b, Cx  d .  


lần lượt là dạng chuẩn tắc, dạng chính tắc và tổng quát. Trong đó, 
D  là ma trận vuông đối xứng cấp  n ; 
A là ma trận cấp  m  n ; 

C  là ma trận cấp  s  n ; 

c  là vector  n  chiều mô tả hệ số của hàm mục tiêu; 
x là vector biến quyết định; 
b  là vector  m  chiều; 

d  là vector  s  chiều. 
Các định nghĩa trên của quy hoạch toàn phương được chấp nhận bởi vì  
quy  hoạch  tuyến  tính  là  dạng  đặc  biệt  của  quy  hoạch  toàn  phương  (với  D  
nhận ma trận không). 
Định nghĩa 1.6. Một ma trận vuông D 

nn

cấp n được gọi là xác định

dương (tương ứng, xác định âm) nếu vT Dv  0, (tương ứng, vT Dv  0 ), với

và

  . Nếu D là một ma trận nửa xác định dương thì f là một hàm lồi. 
Chứng minh. Ta  biết,  f :

n

 , x  cT x     là  hàm  lồi  và  tổng  của  hai 

hàm lồi là một hàm lồi. Suy ra, ta cần chứng minh  f1 ( x) :

1 T
x Dx  là hàm lồi.
2

Khi  D   là  một  ma  trận  nửa  xác  định  dương,  đối  với  mỗi  u 
v

n

n

  và 

 ta có, 
T

T

T

n

 và  t   0,1 , đặt  z  tx  1  t  y  ta có, 

z T Dz  (1  t ) z T Dz  tz T Dz  (1  t ) y T Dy  txT Dx , suy ra, 

f (tx  (1  t ) y )  tf ( x)  (1  t ) f ( y ) , 

với mọi  x 

n

,  y 

n

 và  t   0,1 . 

Trong  trường  hợp  ma  trận  D   không  phải  là  nửa  xác  định  dương  và 
cũng không phải là nửa xác định âm, ta nói rằng  f ( x) 
đó  c 

n

1 T
x Dx  cT x  trong 
2

 là một hàm toàn phương không xác định. 


toán toàn phương là lồi hay không.  
Ví dụ 1.10. Bài toán toàn phương sau đây là không lồi 
min  f ( x)  x12  x22 : x   x1 , x2  ,1  x1  3,1  x2  3 . 

 

20 


2 0 
Ta thấy,  f  là một hàm không lồi, vì với  D  
 , tại   x  1,3  ta có 
 0 2 

 x1

 x1 
 2 0   x1 
2
2
x2  
 x    2 x1 2 x2   x   2 x1  2 x2 , 

 0 2   2 
 2
2

không  lớn  hơn  0   với  mọi  x  1,3 ,  nên    trận  D   không  xác  định  dương. 
Nghiệm của bài toán  Sol  P   1,3  và  ( P)  8 . 
Ví dụ 1.11. Cho  k  điểm  a1 , a2 ,..., ak  trong 


f ( x )  0 . Từ  f ( x )  2kx  2 ai , ta có thể viết điều kiện  0  f ( x )  tương 
i 1

1 k
1 k
ứng với  x   ai . Do đó,  x   ai  là kết quả duy nhất của bài toán này. 
k i 1
k i 1

Điểm  x  đặc biệt này được gọi là trọng tâm của  a1 , a2 ,..., ak  . 
Ví dụ hình học sau đây dẫn đến một bài toán toàn phương (không lồi) 
của dạng tổng quát. 
Ví dụ 1.12. Cho     x 
và  d 

S

n

: Ax  b, Cx  d  ,  với  A 

mn

, C

S n

, b



M   x  R n :  i xi    0  và  M   x  R n :  i xi    0   
i 1
i 1





là hai siêu phẳng trong 

n

. 

Ta  tìm  x     sao  cho  hàm  f ( x)  (d ( x, M )) 2  (d ( x, M )) 2 ,   trong  đó 

d ( x, )  inf  x  z : z     là  khoảng  cách  từ  x   đến  tập  hợp  con   

n

. 

Ta có,  
n

d ( x, M ) 

 x   .                                       (1.6) 
i i



2

  khi   : (1 ,..., n ).  Hay, khi  z  M  

    ,x 


2

 ,   . 

Từ điều kiện (1.5) chúng ta có,    2   , x    . Khi đó, 

2

( d ( x, M ))  x  z

2

 x  (x 


2

2

)  


n

n

  ) x  (  2   2 ).  
                 ( i j   i j ) xi x j  2 (  i 
i
i
j 1 i 1

i 1

Từ điều này, chúng ta kết luận rằng  f  x   là một hàm toàn phương, vì 
thế bài toán tối ưu hóa được xem như bài toán toàn phương dạng tổng quát. 
Dễ dàng chứng minh được, nếu chúng ta chọn  

 

23 


1 0
1
0 1
1


,  b    ,    (1,0),     0,     (0,1),     0 , 
A
 1 0 


   d ( x, M )  x1 ,  

 

 

   d ( x, M )  x2 . 

 
 
 

Chương 2 

Điều kiện cần và đủ cực trị
cho bài toán quy hoạch toàn phương
Chương này, tập trung làm rõ điều kiện cần và đủ cực trị cho bài toán 
quy hoạch toàn phương. Cụ thể, chúng ta nghiên cứu điều kiện cần và đủ cực 
trị đầu tiên (định lý 2.1), điều kiện cần và đủ tối ưu thứ hai (định lý 2.4-2.5) 

 

24 


của bài toán quy hoạch toàn phương và điều kiện để bài toán có nghiệm duy 
nhất (định lý 2.6-2.7).
2.1. Điều kiện cực trị đầu tiên
 


i) Nếu x là nghiệm địa phương của bài toán này thì
Dx  c, x  x  0 , x   .

ii) Nếu Dx  c, x  x  0 , x   \  x  ,

(2.2) 
(2.3) 

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

Chứng minh. 
 

i)  Cho  x   là  nghiệm  địa  phương  của  bài  toán  (2.1).  Chọn    0   thỏa 

mãn f ( x )  f  x  ,  với mọi  x    B  x ,   .
 

 

Với bất kỳ  x   \  x  , ta thấy tồn tại    0  sao cho 

25