Khoá luận tốt nghiệp                                                                      Vi Thị Tuyến 
LỜI CẢM ƠN
 

  

Bước  đầu  làm  quen  với  việc  tiến  hành  nghiên  cứu  khoa  học  nên  em 

không khỏi bỡ ngỡ và gặp nhiều khó khăn. Để có được khoá luận hoàn thiện 
em đã nhận được sự giúp đỡ của các thầy cô trong khoa Toán cùng các thầy 
cô  trong  trường  ĐHSPHN2  và  đặc  biệt  là  sự  tân  tình  chỉ  bảo  và  đóng  góp 
những ý kiến quý báu của thầy Hoàng Ngọc Tuấn trong thời gian qua. 
 

Do  điều  kiện  thời  gian  cùng  với  vốn  kiến  thức  chắc  chắn  sẽ  không 

tránh khỏi những sai sót. Em rất mong nhận được sự chỉ bảo, đóng góp của 
thầy cô và các bạn để tìm được những ý tưởng tốt hơn bổ sung cho khóa luận 
được hoàn thiện hơn nữa và sẽ là tài liệu tham khảo thật sự bổ ích cho tất cả 
những độc giả có niềm đam mê môn Toán. 
  

Qua đây em xin gửi lời cảm ơn chân thành tới các thầy cô trong tổ Giải 

tích,  các  thầy  cô  trong  khoa  Toán  và  đặc  biệt  là  thầy  Hoàng  Ngọc  Tuấn đã 
hướng dẫn em hoàn thành khóa luận này. 
 

Em xin chân thành cảm ơn! 

Hà Nội, tháng 05 năm 2012 
Sinh viên 
 
Vi Thị Tuyến
 

 
 


 
 

Khoá luận tốt nghiệp                                                                      Vi Thị Tuyến 

LỜI CAM ĐOAN
Tôi xin cam đoan bản khóa luận này được hoàn thành do sự cố gắng nỗ 
lực tìm hiểu, nghiên cứu của bản thân, cùng với sự giúp đỡ tận tình của thầy 
Hoàng Ngọc Tuấn. 
Khóa luận này không trùng với kết quả của tác giả khác. Nếu trùng tôi 
xin hoàn toàn chịu trách nhiệm. 
Rất mong được sự đóng góp ý kiến của bạn đọc để bản khóa luận được 
hoàn thiện hơn. 

Hà Nội, tháng 05 năm 2012 
Sinh viên 
 
Vi Thị Tuyến

 

 
 


 
 

Khoá luận tốt nghiệp                                                                      Vi Thị Tuyến 

MỤC LỤC
PHẦN MỞ ĐẦU............................................................................................ 1 
CHƯƠNG 1. BẤT ĐẲNG THỨC BIẾN PHÂN AFFINE ............................. 3 
1.1 Bất đẳng thức biến phân ........................................................................... 3 
1.2 Bài toán bù  .............................................................................................. 8 
1.3 Bất đẳng thức biến phân affine ................................................................. 9 
1.4 Bài toán bù tuyến tính............................................................................. 17 
CHƯƠNG  2.  SỰ  TỒN  TẠI  NGHIỆM  CỦA  BẤT  ĐẲNG  THỨC  BIẾN 
PHÂN AFFINE............................................................................................ 21 
2.1 Sự tồn tại nghiệm dưới điều kiện đơn điệu ............................................. 21 
2.2 Sự tồn tại nghiệm dưới tính đồng dương................................................. 26 
CHƯƠNG  3.  TÍNH  LIÊN  TỤC  LIPSCHITZ  TRÊN  CỦA  ÁNH  XẠ 
NGHIỆM TRONG BẤT ĐẲNG THỨC BIẾN PHÂN................................. 34 
3.1 Định lý Walkup – Wets .......................................................................... 34 
3.2 Tính Liên tục Lipschitz trên với tham biến tuyến tính ............................ 37 
KẾT LUẬN.................................................................................................. 45 
TÀI LIỆU THAM KHẢO ............................................................................ 46 

 

 
 
 
 
 
 
 
 
 


 
 

Khoá luận tốt nghiệp                                                                        Vi Thị 
Tuyến 

PHẦN MỞ ĐẦU
1. Lý do chọn đề tài
Bất đẳng thức biến phân là một bất đẳng thức liên quan tới một hàm mà 
phải được giải với mọi giá trị của một biến cho trước, biến này thường thuộc 
vào một tập hợp lồi.  Lý thuyết của bất đẳng thức biến phân được phát triển từ 
việc giải quyết các bài toán cân bằng, và hiện này nó có những ứng dụng rỗng 
rãi trong nhiều lĩnh vực như kinh tế, tài chính, tối ưu và lý thuyết trò chơi. 
Bất đẳng thức biến  phân  affine  là  một  trường  hợp  riêng  của  bất đẳng 
thức  biến  phân,  khi  mà  hàm  trong  bất  đẳng  thức  là  hàm  affine.  Sự  tồn  tại 
nghiệm của bài toán và tính chất của ánh xạ nghiệm là những vấn đề cần thiết 
rất đáng để nghiên cứu và tìm hiểu sâu thêm. 
Vì những lí do trên nên em chọn đề tài: 
Bất đẳng thức biến phân affine

và cũng với hi vọng hiểu sâu được nội dung được vài toán và tầm quan trọng 
của nó. 
2. Mục đích nghiên cứu
Bước đầu làm quen với công việc nghiên cứu khoa học và tìm hiểu cấu 
trúc bài toán Bất đẳng thức biến phân affine. 
3. Nhiệm vụ nghiên cứu
Nghiên cứu các điều kiện cho sự tồn tại nghiệm của Bất đẳng thức biến 
phân affine, và đưa ra một số tính chất của ánh xạ nghiệm của bài toán. 
4. Đối tượng và phạm vi nghiên cứu
Bất đẳng thức biến phân affine. 
5. Phương pháp nghiên cứu
Sử dụng các lý luận, các công cụ toán học và phương pháp nghiên cứu 
của lý thuyết tối ưu, lý thuyết biến phân.              

                                                                                                                                       
1 
 


 
 

Khoá luận tốt nghiệp                                                                        Vi Thị 
Tuyến 
6. Cấu trúc khóa luận
Ngoài phần mở đầu, kết luận và danh mục tài liệu tham khảo, khóa luận 
của em gồm ba chương: 
Chương 1. Bất đẳng thức biến phân affine 
Chương 2. Sự tồn tại nghiệm của bất đẳng thức biến phân affine 
Chương 3. Tính liên tục Lipschitz trên của ánh xạ nghiệm trong bất đẳng thức 

biến phân affine 
 
 
 
 
 
 
 
 

2 
 


 
 

Khoá luận tốt nghiệp                                                                        Vi Thị 
Tuyến 
CHƯƠNG 1. BẤT ĐẲNG THỨC BIẾN PHÂN AFFINE
 

1.1 Bất đẳng thức biến phân 
Bài toán bất  đẳng  thức biến phân bắt nguồn  một  cách  tự nhiên trong khuôn 
khổ của bài toán tối ưu. 
       Cho f : n 

là  một  hàm  thuộc  lớp  C1 và   

n


  là  một  tập  lồi 

đóng khác rỗng 
Mệnh đề 1.1. Nếu  x  là một nghiệm địa phương của bài toán tối ưu 
      min  f  x  : x                                               (1.1) 
thì  
                                      f ( x ), y  x  0 y  .                                   (1.2) 
Chứng minh.
Đặt 
 f ( x) 
 x 
 1 
    (x)  f (x)         x 


 f ( x) 
 x 
 n 

n

,                                  (1.3) 

ta có (1.2)  được viết lại là  
                                            (x), y  x  0 y.                                  (1.4) 
Định nghĩa 1.1. Nếu   

n


 là tập đóng lồi khác rỗng và   :  

n

 được 

cho là toán tử (ánh xạ) khi đó bài toán đặt ra là tìm một số  x    thỏa mãn 
(1.4) được  gọi là  bài  toán bất  đẳng  thức biến phân,  thường  gọi  là,  bất đẳng 
thức biến phân (kí hiệu, VI). Kí hiệu là VI  ,   .  Tập nghiệm Sol (VI  ,   ) 
của VI  ,    là tập hợp tất cả các  x    thỏa mãn (1.4). 
       Mệnh đề 1.1 chỉ ra rằng một bài toán tối ưu là trơn, có thể dẫn đến bài 
toán  bất  đẳng  thức  biến phân  như  thế  nào?  Câu  hỏi  tự  nhiên  đặt  ra  là:  Cho 
3 
 


 
 

Khoá luận tốt nghiệp                                                                        Vi Thị 
Tuyến 
trước  một  bất  đẳng  thức  biến  phân  VI  ,     với  một  toán  tử  liên  tục 

:

n



n


,  có thể tìm được một hàm -  C1   f :

n



 sao cho VI  ,    có 

thể lấy được từ bài toán tối ưu (1.1) bằng cách đã nêu ra hay không? Nếu hàm 
f  như vậy tồn tại, ta phải có  

                 ( x)  f ( x), x  .                                    (1.5) 
         Ta thấy nếu f là một hàm thuộc lớp  C 2  thì toán tử   :

n



n

xác định 

bởi (1.3) có một ma trận Jacobian đối xứng. Nhắc lại rằng nếu một hàm véc tơ 
là   :

n




n

 có các thành phần trơn  1 ,,n  thì ma trận Jacobian của    tại 

x  được xác định bởi công thức 

 ( x) 
 1 ( x) 1 ( x)
 1
 x
x2
xn 
1


J  ( x)   


.  


 n ( x) n ( x)  1 ( x) 
 x
x2
xn 
1

Vì  f  là một hàm thuộc lớp  C 2 ,  từ (1.3) ta có : 

 


 i ( x )  2 f ( x )  2 f ( x)  j ( x)
                                  
  



x j
x j xi
xi x j
xi

 với mọi  i, j.  Điều này dẫn tới  J  ( x)  là một ma trận đối xứng. 
Mệnh đề 1.2. Cho   

n

 là một tập đóng lồi khác rỗng. Nếu   :

một  hàm  véc  tơ  với các  thành phần  trơn sao cho   

n



n

 là 

 i ( x )  j ( x)


  với  mọi 
x j
xi

i, j   (toán  tử  trơn  đối  xứng),  thì  tồn  tại  một  hàm  thuộc  lớp  C 2 toán  tử  
f :

n



 sao cho hệ thức (1.5) thỏa mãn. Điều này có nghĩa là bài toán 

bất đẳng thức  biến phân  VI  ,     có thể  coi là điều kiện cần tối ưu của bài 
toán (1.1). 
4 
 


 
 

Khoá luận tốt nghiệp                                                                        Vi Thị 
Tuyến 
       Các  mệnh  đề  đơn  giản  sau  đây  cho  thấy,  không  giống  nghiệm  của  bài 
toán quy  hoạch  toán học, nghiệm của bài toán  VI  có đặc trưng  địa phương. 
Mệnh đề 1.3. Cho  x   . Nếu tồn tại    0  sao cho  
              ( x ), y  x  0 y    B  x ,   ,                           (1.6) 
thì  x   Sol (VI  ,   ). 

Chứng minh.  Giả  sử  rằng    0   thỏa  mãn  (1.6).  Với  mỗi  y  ,   tồn  tại 
t  t ( y )  (0,1)  sao cho  y (t ) : x  t ( y  x )  thuộc vào    B ( x ,  ).  Bởi (1.6), 
0   ( x ), y (t )  x  t  ( x ), y  x .  Điều này dẫn tới   ( x ), y  x  0  với mọi 

y  .  Do đó  x  Sol(VI( ,  )).    

       Định lý Hartman – Stampacchia sau đây là định lí tồn tại cơ bản cho bài 
toán VI. 
Định lý 1.1. Nếu   

n

 là lồi, compact, khác rỗng và   :  

n

 là liên tục 

thì bài toán VI  ,    có nghiệm. 
        Dưới điều kiện bức, ta có các định lý tồn tại cho bài toán trên các tập lồi 
không compact. 
Định lý 1.2. Cho   

n

 là tập lồi, đóng, khác rỗng và    :  

n

 là một 


toán tử liên tục. Nếu tồn tại  x 0    sao cho  
         ( x)   ( x 0 ), y  x 0 y  x 0    và  y  , y  ,          (1.7)  
thì bài toán VI  ,    có nghiệm. 
Hiển  nhiên     là  compact  thì,  với  mọi  x 0  ,   (1.7)  là  đúng.  Nếu  tồn  tại 
x 0    sao cho (1.7) đúng thì ta nói điều kiện bức được thỏa mãn. Điều kiện 

bức  có vai trò rất quan trọng trong nghiên cứu các bất đẳng  thức  biến phân 
trên  tập  hợp  không  compact.  Chú  ý,  (1.7)  là  một  trong nhiều  hình  thức  của 
điều kiện bức. 
5 
 


 
 

Khoá luận tốt nghiệp                                                                        Vi Thị 
Tuyến 
     Nếu tồn tại  x 0    và    0  sao cho  
2

 ( y )   ( x 0 ), y  x 0   y  x 0 y                                 (1.8) 
thì, (1.7) là đúng. Nếu tồn tại    0  sao cho  
2

              ( y )   ( x), y  x   y  x x  , y  ,                         (1.9) 
thì (1.8) thỏa mãn. 
Định nghĩa 1.2. Nếu tồn tại    0  sao cho (1.9) được thỏa mãn thì ta nói    là 
đơn điệu mạnh trên  .  Nếu các điều kiện yếu hơn sau đây  

                   ( y )   ( x), y  x  0, x  , y  , x  y,                  (1.10) 
và  
       ( y )   ( x), y  x  0, x  , y  ,                        (1.11) 
đúng, thì    tương ứng được gọi là đơn điệu chặt trên   và đơn điệu trên  .  
 Ví dụ 1.1. Cho   

n

 là tập đóng, lồi, khác rỗng. Cho  D 

Nếu  ma trận  D là xác  định dương thì toán tử   :  

n

nn

 và  c 

n

.       

 được  xác  định bởi 

 ( x)  Dx  c, x    là đơn điệu mạnh trên  .   Trong trường hợp này,  ta dễ 
dàng thấy rằng    0  thỏa mãn (1.9) có thể xác định bằng cách đặt  

  inf vT Dv : v 

n


, v  1.  

Tương  tự,  nếu  D  là  nửa  xác  định  dương  cho  bởi  công  thức   ( x)  Dx  c,  
x  ,  xác định một toán tử đơn điệu. 

Mệnh đề 1.4. Ta có các khẳng định sau: 
(i)    Nếu    là đơn điệu chặt trên    thì bài toán VI  ,    không có nhiều hơn 
một nghiệm; 
(ii)    Nếu     là  liên  tục  và  đơn  điệu  trên     thì  tập  nghiệm  của  bài  toán 
VI  ,    là đóng và lồi (có thể là tập rỗng). 
          Để chứng minh được khẳng định thứ hai trong mệnh đề đó ta cần một 
bổ đề sau.  
6 
 


 
 

Khoá luận tốt nghiệp                                                                        Vi Thị 
Tuyến 
Bổ đề 1.1. Nếu   

n

 là tập đóng, lồi và   :  

n


 là một toán tử liên tục, 

đơn điệu thì  x  Sol(VI  ,   ) khi và chỉ khi  x    và 
                                          ( y ), y  x  0, y   .                              (1.12) 
Chứng minh. 
Điều kiện cần: Cho  x  Sol(VI  ,   ). Áp dụng tính đơn điệu của   , ta có  
                                     ( y )   ( x ), y  x  0, y   . 
Kết hợp với (1.4) ta có kết quả 
                                   ( y ), y  x   ( x ), y  x  0, y   . 
Điều kiện (1.12) đã được chứng minh. 
 Điều kiện đủ: Giả sử  x    và (1.12) đã thỏa mãn. Cố định  y   . Do tính 
lồi của   ,  y (t ) : x  t ( y  x )  thuộc vào    với mọi  t  (0,1) . Thay  y  y (t )  
vào (1.12) ta có  
0   ( y (t )), y (t )  x   ( x  t ( y  x ), t ( y  x ) .
 
Điều này dẫn tới 
                                              ( x  t ( y  x ), y  x  0, t  (0,1).  
Cho  t  0,  do tính liên tục của    ta có   ( x ), y  x  0  từ bất đẳng thức cuối 

cùng cố định với mọi  y  ,  ta kết luận  x  Sol(VI   ,    .                                                   
 
 Chứng minh của mệnh đề 1.4.
(i)    Giả  sử,  ngược  lại  rằng,     là  đơn  điệu  chặt  trên     nhưng  bài  toán 
(VI  ,   có  hai  nghiệm  phân  biệt  x   và  y .  Ta  có   ( x ), y  x  0   và 

 ( y ), x  y  0.  Kết hợp các bất đẳng thức lại ta có   ( x )   ( y ), y  x  0.  
Bất đẳng thức cuối cùng mâu thuẫn với sự kiện   ( y )   ( x ), y  x  0.
(ii)  Giả sử    là liên tục và đơn điệu trên  .  Với mọi  y  ,  kí hiệu  ( y )  là 
tập hợp gồm tất cả các  x    thỏa mãn bất đẳng thức   ( y ), y  x  0.  Ta có 
( y )  là đóng, lồi. Từ Bổ đề 1.1 ta suy ra  

7 
 


 
 

Khoá luận tốt nghiệp                                                                        Vi Thị 
Tuyến 
                                    Sol(VI   ,     =   ( y ).  
y

Do đó Sol(VI  ,   ) là đóng và lồi (có thể rỗng).  

 
       Từ  Định  lý  1.2  và  Mệnh  đề  1.4  (i)  ta  có  nếu     là  khác  rỗng  và 

 : 

n

  là  ánh  xạ  liên  tục,  đơn  điệu  mạnh  thì  bài  toán  VI  ,     có  một 

nghiệm duy nhất. 
       Trong phần sau, ta xét bài toán bất đẳng thức biến phân trong trường hợp 
tập    là một nón. 
1.2 Bài toán bù
Mệnh đề 1.5. Nếu    là một nón lồi, đóng, bài toán VI  ,   bất đẳng thức có 
thể được viết lại dưới dạng tương đương như sau
                  x   ,   ( x )    ,  ( x ), x  0,                                   (1.13) 

ở đây       R n :  , v  0 v    ký hiệu là nón đối ngẫu dương của   . 
Chứng minh.
Giả sử  x  là một nghiệm của (1.4). Với mọi  v   , vì    là một nón lồi, ta có 
x  v  .  Từ (1.4) suy ra 

0   ( x ), ( x  v)  x   ( x ), v .  
1
Vì vậy   ( x )    .  Hơn nữa, vì  x    và  2 x  ,  áp dụng (1.4) ta có  
2
            

1
1
0   ( x ), x  x    ( x ), x  
2
2

và 

0   ( x ),2 x  x   ( x ), x .  

Do đó   ( x ), x  0.  Ta đã chứng minh (1.13) được thỏa mãn. 
        Bây giờ, lấy  x  sao cho (1.13) đúng. Với mọi  y  ,  từ    ( x ), x = 0 và 

 ( x )    ,  ta có  
                                       ( x ), y  x   ( x ), y  0.  
8 
 



 
 

Khoá luận tốt nghiệp                                                                        Vi Thị 
Tuyến 
Điều này chứng tỏ   x  Sol(VI   ,    .  

 

Định nghĩa 1.3.  Bài  toán  (1.13)  ở  đó   

:

n



n

 
n

 

 

 

  là  một  nón  lồi  đóng  và 


,   được  kí  hiệu  là  NCP( , )   và  được  gọi  là  bài  toán  bù  (phi 

tuyến) xác định bởi    và   .  
        Vì bài toán bù là dạng đặc biệt của bài toán bất đẳng thức biến phân, 
các định lý tồn tại cho bài toán VI có thể áp dụng cho chúng. 
1.3 Bất đẳng thức biến phân affine
Theo  lý  thuyết  quy  hoạch  toàn  phương  với  ràng  buộc  tuyến  tính,  nếu  x   là 
một nghiệm địa phương của bài toán quy hoạch toàn phương
1


                   min  f ( x)  xT Mx  qT x : x    ,                                     (1.14) 
2



ở  đây  M 

nn
S

, q

n

,   và   

n

  là  một  tập  lồi  đa  diện,  thì 


Mx  q, y  x  0   sao  cho  mọi  y  .   Kéo  theo  có  x   là  một  nghiệm  của 

bài  toán  VI  ,   ,   ở  đó   ( x)  Mx  q   là  ánh  xạ  affine  có  dạng  ma  trận 
Jacobian đối xứng không đổi M. 
nn
S

Định nghĩa 1.4. Cho  M 

,q 

n

 và. Gọi   

n

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

Bài toán bất đẳng thức biến phân  
            Tìm  x   : Mx  q, y  x  0 y                                            (1.15)  
được gọi là bài toán bất đẳng thức biến phân affine (kí hiệu, AVI) xác định 
bởi tập hợp các dữ liệu  M , q,  và kí hiệu là  AVI(M,q, ).  Tập nghiệm của 
bài toán được kí hiệu là Sol( AVI(M,q,  ) ). 
 Định lý 1.3. Véc tơ  x 

n

 là một nghiệm của (1.15) ở đó    được cho bởi 


công thức 
                              x 

n

: x  b                                                  (1.16) 

9 
 


 
 

Khoá luận tốt nghiệp                                                                        Vi Thị 
Tuyến 
với   

mn

,b 

m





,  nếu và chỉ nếu tồn tại    1 ,...., m 


m

 sao cho  

 Mx  AT x  q  0,

                             Ax  b,   0,                                                    (1.17) 
 T
 ( Ax  b)  0.

Chứng minh.  
Ta kí hiệu là  i , i là hàng thứ  i của A và  bi  là kí hiệu phần thứ  i của véc tơ  b. 
Ta  lấy  ai  AiT   với  mọi  i  =  1,...........,m.  Cho  x  Sol(AVI(M,q, )).   Đặt 
I  1,...m,

v

n

I 0  i  I :

ai , x  bi    và  I1  i  I : ai , x  bi .   Với  mọi 

 thỏa mãn 
ai , v  0 i  I 0  

dễ dàng thấy tồn tại  1  0  sao cho  ai , x  tv  bi  với mọi  i  I  và  t  (0, 1 ).  
Đặt  y  x  tv,  ở đó  t  (0, 1 ),  từ (1.15) ta có  Mx  q, v  0.  Vì vậy             


 Mx  q, v  0  
với mọi  v 

n

 thỏa mãn  
 ai , v  0 i  I 0 . 

       Áp  dụng  bổ  đề  Farkas  (xem  Rockafellar  (1970)),  tồn  tại  một  số  thực 
không âm  i (i  I 0 )  sao cho  
                                    i ( ai )   Mx  q.                                         (1.18) 
iI 0





Đặt   i  0   với  mọi  i  I1   và    1 ,...., m .   Từ  ai  AiT   với  mọi  i  I ,   Từ 
(1.18)  ta  có  được  bất  đẳng  thức  đầu  tiên  trong  (1.17).  Từ  x  ( A, b)   và 

 i ( Ai x  bi )  0, i  I  các điều kiện khác trong (1.17) cũng thỏa mãn. 





         Để chứng minh điều kiện đủ, giả sử tồn tại    1 ,...., m 
(1.17) đúng. Do đó, lấy mọi  y  ,  ta có  

10 

 

m

 sao cho 


 
 

Khoá luận tốt nghiệp                                                                        Vi Thị 
Tuyến 
Mx  q, y  x  AT  , y  x   ,( Ay  b)  ( Ax  b)
T

T

  ( Ay  b)   ( Ax  b)

 

T

  ( Ay  b)  0.

Suy ra,  x  là một nghiệm của (1.15). Ta có điều phải chứng minh.        
         Xuất phát từ Định lý 1.3 ta suy ra được hai hệ quả sau, phụ thuộc vào sự 
biểu diễn của    trường hợp 1  
  x 


n

: Ax  b, x  0                                        (1.19) 

Và trong trường hợp khác ở đó    có sự biểu diễn 
                            x 
Do đó                 A 

mn

Hệ quả 1.1. Véc tơ  x 

n

m

,b 
n

: Ax  b, Cx  d .                                      (1.20) 
sn

,C 

,d 

s

. 


 là một nghiệm của (1.15) ở đó    được cho bởi 





(1.19) khi và chỉ khi tồn tại    1 ,...., m  R m  sao cho  
 Mx  AT   q  0,

                   Ax  b, x  0,   0,
                    (1.21) 
 T
T
T
 x ( Mx  A   q )   ( Ax  b)  0.

Chứng minh. 
Định nghĩa ma trận  A 

( m  n )n

 và véc tơ  b 

(mn )

 A

b

 


 

 với  

  A    ;   b    ,  
E
0
 trong đó E biểu thị ma trận đơn vị trong 
n

n n

 và 0 biểu thị vectơ không trong 

 Bài toán (1.15), ở đó   được cho bởi (1.19), tương đương với bài toán 
  b   sao cho     
 tìm  x   : =  x  n: Ax
 

 Mx  q, y  x  0 y   .





Áp dụng Định lý 5.3 cho bài toán AVI ta suy ra  x  là một nghiệm bài toán khi 
và chỉ khi tồn tại    (1 ,..., m n ) 

m n


 sao cho  

11 
 


 
 

Khoá luận tốt nghiệp                                                                        Vi Thị 
Tuyến 
 T   q  0, 
 x  b ,   0, T ( 
 x  b )  0.  
Mx  
Lấy    ( 1 ,...,  m )   ở  đó  i  i   với  mọi  i  1,..., m,   nhận  được  tính  chất 
(1.21). 
Hệ quả 1.2. Véc tơ  x 

n

 là một nghiệm của (1.15) ở đó    cho bởi (1.20) 

khi và chỉ khi tồn tại    ( 1 ,...,  m )  R n  và    ( 1 ,...,  s ) 

s

 sao cho  


 Mx  T   C T   q  0,

                 Ax  b, Cx  d ,   0,                                         (1.22) 
 T (Ax  b)  0.


Chứng minh.  Định nghĩa  A 

 m  2 s n

 và  b 

m2s

 với  

A 
b 


                                            A   C  , b   d  .  
 C 
 d 


 

. 
 Bài toán(1.15), ở đó    cho bởi (1.20) tương đương với bài toán 
Tìm  x   := x  R n : Ãx  b  sao cho 

 


 Mx  q, y  x  0 y  .





Áp dụng Định lý 1.3 cho bài toán AVI suy ra  x  là một nghiệm bài toán khi và 
chỉ khi tồn tại    (1 ,..., m 2 s ) 

m 2 s

 sao cho  

Mx  ÃT   q  0, Ãx  b,   0,  T (Ãx  b )  0.  

Lấy    ( 1 ,...,  m )   và    ( 1 ,...,  s )   ở  đó  i  i   với  mọi  i  1,..., m   và 

i  m j  m s  j  với mọi  j  1,..., s,  nhận được tính chất (1.22).                                     
         Không  giống  như  tập  nghiệm  và  tập  nghiệm  đia  phương  của  bài  toán 
quy  hoạch  toàn  phương  không  lồi,tập  nghiệm  của  bài  toán    AVI  thì  có  cấu 
khá trúc đơn giản. 
Định lý 1.4. Tập nghiệm của bài toán bất đẳng thức biến phân affine là hợp 
của hữu hạn các tập lồi đa diện. 
12 
 



 
 

Khoá luận tốt nghiệp                                                                        Vi Thị 
Tuyến 
Chứng minh. Xét bài toán AVI tổng quát dạng (1.15). Vì    là một tập lồi đa 
diện, tồn tại  m  N , A 

mn

,b 

m

 sao cho     x 

: Ax  b.  Theo Định 

n

lý 1.3,  x  Sol(AVI(M,q,  ))   khi và chỉ khi  tồn tại     1 ,...., m  

m

  sao 

cho  
 Mx  AT   q  0,

                                    Ax  b,   0,                                               (1.23) 

 T ( Ax  b)  0.


Lấy  I  1,..., m.  Cho điểm  x  Sol(AVI(M,q, )),  ta có tập 
                            I 0  i  I : Ai x  bi  , I1  I \ I 0  i  I : Ai x  bi .  
 Từ bất đẳng thức cuối cùng trong (1.23) ta có  i  0

i  I1.  Do đó  ( x,  )  

thỏa mãn hệ  
 Mx  AT   q  0,

 AI0 x  bI 0 , xI0  0,                                                  (1.24) 

 AI1 x  bI1 , I1  0.

Cho bất kỳ  I 0  I   và  kí hiệu  QI0   là tập hợp  tất cả  các  cặp  ( x,  )  thỏa  mãn 
(1.24). Dễ thấy  QI0  là tập lồi đa diện. Từ những kết quả trên ta suy ra  





           Sol ( AVI ( M , q, ))   PrRn (QI 0 ) : I 0  I ,                                      (1.25)  
ở đó  PrR n ( x,  ) :  x.  Vì  PrRn (.) :

n




m



n

 là một toán tử tuyến tính, với 

mọi  I 0  I ,  ở đây  PrR n (QI0 )  là tập lồi đa diện. Từ (1.25) ta chứng minh được 
Sol ( AVI ( M , q, ))  là hợp hữu hạn các tập lồi đa diện.   

Định nghĩa 1.5. Nửa đường thẳng     x  tv : t  0 ,  ở đó  v 

n

\ 0  mà, 

là một tập con của  Sol ( AVI ( M , q, )),  được gọi là tia nghiệm của (1.15). 

13 
 


 
 

Khoá luận tốt nghiệp                                                                        Vi Thị 
Tuyến 
Định nghĩa 1.6. Đoạn  thẳng     x  tv : t   o,   ,  ở  đó  v 


n

\ 0   và 

  0,  là một tập con của  Sol(AVI(M,q,  )),  được gọi là khoảng nghiệm của 
(1.15).  
Hệ quả 1.3. Ta có các khẳng định sau: 
(i)   Tập nghiệm của bài toán bất đẳng thức biến phân affine là một tập 
đóng (có thể rỗng); 
(ii)    Nếu  tập  nghiệm  của  bài  toán  bất  đẳng  thức  biến  phân  affine  là 
không bị chặn, nó chứa một tia nghiệm; 
(iii)  Nếu tập nghiệm của bài toán bất đẳng thức biến phân affine là vô 
hạn, thì nó chứa một khoảng nghiệm; 
Chứng minh. Phát biểu (i) được suy ra trực tiếp từ công thức (1.25) bởi vì, 
với  mọi  tập  hợp  I 0  I , tập  PrR n (QI0 )   là  tập  đa  diện  lồi,  đóng.  Nếu 
Sol ( AVI ( M , q, ))  là không bị chặn từ, (1.25) suy ra tồn tại tập chỉ số  I 0  I  

sao cho  
                               I0 : PrR n (QI0 )                                                       (1.26) 
là tập không bị chặn. Vì   I 0  là tập lồi đa diện, nếu nó là tập đóng, lồi không 
bị chặn. Theo Định lý 8.4 trong Rockafellar (1970),   I0  có phương lùi xa; tức 
là tồn tại  v  R n \ 0  sao cho  
                          x  tv   I0 x  I0 ,

t  0.                                    (1.27) 

Lấy tùy ý   x   I0 suy ra từ (1.25) và (1.27) ta có  x  tv  sol  ( AVI ( M , q, ))  
với mọi  t  0.  Chúng ta đã chứng minh bài toán (1.15) là một tia nghiệm. Nếu 
Sol(AVI(M,q, ))  là vô hạn, thì từ (1.25)  ta suy ra tồn tại một tập các chỉ số  
I 0  I  sao cho tập lồi đa diện   I 0  được xác định bởi (1.26) là vô hạn. Do đó 


tồn  tại  hai  điểm  phân  biệt  x  I0  và  y  I0 .   Rõ  ràng  tập  hợp 

 x, y  :  x  t ( y  x) : t  0,1  là một khoảng nghiệm của (1.15). 
14 
 

  


 
 

Khoá luận tốt nghiệp                                                                        Vi Thị 
Tuyến 
Sử dụng Định lí 1.4 ta có thể nhận được đặc trưng đầy đủ cho tính chất không 
bị chặn của tập nghiệm của AVI. Ta xem xét bài toán (1.15) ở đó    được cho 
bởi (1.16) và đưa ra các kí hiệu sau: 

 ( A)  v  R n : Av  0 ,
 ( A)    z  R n : z T v  0 v   ( A) ,  
l ( M )   z  R n : z T Mz  0.

Chú ý   ( A) và  v  R n : Av   ( A)   là nón lồi đa diện, trong khi  l ( M ) , nói 
chung là nón đóng không lồi. Chú ý rằng   ( A)  0    và   (A  )=(0 )  .  
Định lý 1.5. Tập nghiệm của (1.15) là không bị chặn khi và chỉ khi có một 
cặp   v, u 0  

n


 

n

, v  0, u 0  sol(AVI(M , q,  )) , sao cho  

(i)   v   ( A),     Mv   ( A) ,      v  l ( M );

        (ii)  ( Mu 0  q)T v  0;

 

(iii)  Mv, y  u 0  0     y  .

Chứng Minh.
Điều  kiện  đủ:  Giả  sử  rằng  có  một  cặp   v, u 0  

n



n

, v  0,   u 0  sol 

(AVI(M , q, ))   sao  cho  (i)  –  (iii)  được  thỏa  mãn.  Đặt  xt  u 0  tv, t  0.   Với  

mọi  y   , suy ra từ (i) – (iii) ta suy ra 
Mxt  q, y  xt  M (u 0  tv)  q, y  (u 0  tv )
                


              = Mu 0  q, y  u 0  t Mu 0  q, v  
 


0

                        

0

+t Mv, y  u 0  t 2 Mv, v  0.

 
0

0

Suy ra có  xt  Sol( AVI ( M , q, )),  với mọi  t  0.  Do đó tập nghiệm là không 
bị chặn. 

15 
 


 
 

Khoá luận tốt nghiệp                                                                        Vi Thị 
Tuyến 

       Điều kiện cần: Giả sử tập nghiệm  Sol(AVI(M,q, ))  là không bị chặn. 
Bởi  (1.25),  tồn  tại  I 0  I   sao  cho  tập   I0   xác  định  bởi  (1.26)  là  không  bị 
chặn. Áp dụng Định lý 8.4 từ Rockafellar (1970), ta có thể khẳng định rằng  
tồn tại  v  R n , v  0 và  u 0  I0  sao cho  
                         u 0  tv  I0   Sol(AVI(M , q, ))     t  0.                      (1.28) 
Vì    A(u 0  tv )  b,   với  mọi  t  0,   ta  suy  ra  Av  0.   Nghĩa  là  v   ( A).   Từ 
(1.28), ta có  
                      M (u 0  tv)  q, y  (u 0  tv )  0    y  .                           (1.29) 
Cố định  y   , suy ra từ (1.29) rằng 
                             

1
1 1
1
Mu 0  Mv  q, y  u 0  v  0     t  0.  
t
t t
t

Vậy 
                                          Mv, v  0.                                                    (1.30) 
Thay  y  u 0  t 2v,    ở đó  t  1 , vào (1.29) và chia bất đẳng thức cho  t  t 2  1 , 
ta có  
                               

1 0
1
Mu  Mv  q, v  0     t  1.  
t
t


Cho  t  , ta được  Mv, v  0.  Kết hợp điều này với (1.30) ta được  
                                             Mv, v  0.                                                      (1.31) 
Điều này chứng tỏ rằng  v  l ( M ).  Thay  y  u 0  vào (1.29) và sử dụng (1.31) ta 
có  Mu 0  q, v  0.  Thay y  u 0  t 2v,  sao cho t  1,  trong (1.29) và (1.31)  ta 
suy ra được   Mu 0  q, v  0.   Điều này và bất đẳng thức trước đó chỉ ra rằng 
(ii) được thỏa mãn. Bởi (1.29), (1.31) và (ii), với mọi  y    ta có  
0  Mu 0  q  tMv, y  u 0  tv  = Mu 0  q, y  u 0  t Mv, y  u 0  
16 
 


 
 

Khoá luận tốt nghiệp                                                                        Vi Thị 
Tuyến 
với mọi t > 0. Điều này suy ra bất đẳng thức  Mv, y  u 0  0  là sai. Vậy ta có 
                                     Mv, y  u 0  0      y  .                                  (1.32) 
Thay  y  u 0   ,   ở  đó      A  ,   vào  (1.32)  suy  ra  Mv,   0,  với  mọi 

    A  .  Nghĩa là  Mv   ( A)  .  Ta đã chỉ ra rằng cả 3 tính chất trong (i) đều 
đúng. Ta có điều phải chứng minh. 

 

          Một  số  điều kiện  đủ trong (1.15)  để  có  tập  nghiệm là  compact có thể 
nhận được trực tiếp từ các định lý trước. 
Hệ quả 1.4. Bài toán (1.15) có tập nghiệm là compact (có thể rỗng) khi và chỉ 
khi một trong các điều kiện sau đây được thỏa mãn: 

(  1 )  nón l(M) bao gồm một và chỉ một phần tử 0; 
(  2 )  Các giao của các nón l(M) và  v 

n

: Mv   ( A)    bao gồm một và chỉ 

một phần tử 0; 
(  3 ) Các giao của các nón l(M),  v  R n : Mv   ( A)    và   ( A)  bao gồm một 
và chỉ một phần tử 0. 
1.4 Bài toán bù tuyến tính 
Định nghĩa 1.7. Bài toán (1.13) với   
và  q 

n

n


 và   ( x)  Mx  q  ở đó   M 

nxn

 

,  kí hiệu  LCP(M , q )  và được gọi là bài toán bù tuyến tính xác định 

bởi M và q. Tập nghiệm của bài toán này được kí hiệu là  Sol(M , q).  Ta có thể 
viết LCP (M , q)  như sau 
                          x  0,      Mx  q  0,      x T ( Mx  q)  0.                           (1.33) 

Vậy LCP là trường hợp đặc biệt của bài toán NCP, ở đó   

n


  và    là toán 

tử affine. 
     

 Nếu  x  là nghiệm địa phương của bài toán quy hoạch toàn phương ở 

(2.1) ở đó   

n


,  thì   x 

n


 và, bởi Định lý 2.1,  
17 

 


 
 


Khoá luận tốt nghiệp                                                                        Vi Thị 
Tuyến 
Dx  c, y  x  0     y 

n


. 

Suy ra  x  là một nghiệm của bài toán bù tuyến tính LCP(D,C) xác định với D 
và c.  
     

Áp dụng hệ quả trong điều kiện tối ưu bậc  một, nếu  x  là nghiệm địa 

phương của phương trình toàn phương 

1 T
T
                            min  x Dx  c x : x 
2
 sau đó tồn tại    (1 ,..., m ) 

m


, Ax  b, x  0  



n

 sao cho 

 Dx  AT   c  0,

                             Ax  b  0, x  0,   0,
 
 T
T
T
 x Dx  A   c    Ax  b   0.





 thỏa mãn.   
Đặt  
 D        AT 
c 
x
                   M  
 ,      q    ,     z    ,                           (1.34) 
 b 
 
 A          0 

ta  có  M 


 n m x nm 

,q 

n m

,z 

nm

.   Dễ  kiểm  tra  rằng  hệ  trên  tương 

đương với hệ 
                             z  0, Mz  q  0, z T ( Mz  q )  0.  
Vậy hệ trên có thể hiểu như là một bài toán LCP.  
Định nghĩa 1.8. Nếu    là  một nón lồi đa diện và tồn tại  M 

nxn

, q

n

, 

sao cho   (x)  Mx  q  với mọi  x  ,  thì (1.13) được gọi là bài toán bù tuyến 
tính tổng quát. Kí hiệu là  GLCP(M , p, ).  
Định lí 1.5 có thể được phát biểu cho bài toán LCP như sau. 
Mệnh đề 1.6. Tập nghiệm của (1.33) là không bị chặn khi và chỉ khi tồn tại 
một cặp  (v, u 0 ) 


n



n

, v  0, u 0  Sol(M , q ),  sao cho 

18 
 


 
 

Khoá luận tốt nghiệp                                                                        Vi Thị 
Tuyến 
(i)   v  0, Mv  0, v  l ( M );
T

(ii)    Mu 0  q  v  0;

 

(iii)   Mv, u 0  0.

        Hệ quả 1.4 được đặc biệt hóa cho bài toán LCP như sau. 
Hệ quả 1.5. Bài toán (1.33) có tập nghiệm là compact (có thể rỗng) khi và chỉ 
khi  một trong các điều kiện sau đây được thỏa mãn: 


 1 )   nón l(M) bao gồm chỉ có một phần tử 0; 
 2 )  giao của các nón l(M) và  v 

n

: Mv  0  bao gồm chỉ có  một 

phần tử 0; 

 3 )  giao của các nón l(M) và  v 

n

: Mv  0    và   

n


, bao gồm chỉ 

có một phần tử 0. 
Ví dụ 1.2. Chú ý bài toán (1.33) với 
 q1 
1     0 
,
   
q

                                M  

 

 0     -1
 q2 

2

,     n  2 . 

       Tính  toán  trực  tiếp  cho  thấy  giao  của  các  nón  l ( M ),v : Mv  0 và 

v

: v  0,  chỉ gồm duy nhất một phần tử  0. Áp dụng Hệ quả 1.5, tập nghiệm 

Sol(M,q) là một tập compact. 
Ví dụ 1.3. Xét bài toán (1.13) với 
1    0 
 1
M 
, q   

 0   0 
 

2

,   0, n  2 . 

Tính toán trực tiếp chỉ ra rằng giao các nón  l ( M ),v : Mv  0  và  v : v  0  là 

tập hợp  v   0, v2  

: v2  0.  Để kiểm tra điều kiện (ii) trong Mệnh đề 1.6 

2

không mất tính tổng quát ta giả sử  v  (0,1).  Dễ thấy không tồn tại có  u 0  0  
T

sao  cho   Mu 0  q  v  0   và  Mv, u 0  0.   Bởi  Mệnh  đề  1.6,  tập  nghiệm 
Sol(M,q) là tập compact.  
19 
 


 
 

Khoá luận tốt nghiệp                                                                        Vi Thị 
Tuyến 
Ví dụ 1.4. Xét bài toán (1.13) với 
1    0 
 1 
M 
,q   

 0   0 
0 

2


, n  2.  

Giao của các nón  l ( M ),v : Mv  0 và  v : v  0, là tập : 

v   0, v  
2

2

: v2  0.  

Do đó điều kiện (i)-(iii) trong Mệnh đề 1.6 là thỏa mãn nếu ta chọn  v  (0,1)  
và  u 0  (0,1).  Theo Mệnh đề 1.6, Sol(M,q) là tập không bị chặn. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

 
 
 
 
 

20 
 


 
 

Khoá luận tốt nghiệp                                                                        Vi Thị 
Tuyến 
CHƯƠNG 2. SỰ TỒN TẠI NGHIỆM CỦA BẤT ĐẲNG THỨC BIẾN
PHÂN AFFINE
2.1 Sự tồn tại nghiệm dưới điều kiện đơn điệu 
Xét  bài  toán  (2.1).  Nếu     là  tập  lồi  đa  diện,  tồn  tại  m  N , A
b

m

mxn

  và 

, 

sao cho  

                                            =  x 

n

: Ax  b.                                       (2.2) 

Định lý 2.1. Nếu hai điều kiện sau đây được thỏa mãn 
T

(i)   tồn tại  x   sao cho   Mx  q  v  0 ,   v  0 ;  
(ii) 

 

( y  x)T M ( y  x )  0 , x   và 

y  ;  

thì 

tập 

nghiệm 

Sol( AVI(M , q, ) ) là khác rỗng. 
Cho 
 x
   z    
  
                          

 x
   =  z    
  

Ta kí hiệu I là một ma trận trong 

n m

 A   0 
 b 
:  M  AT  z  q, 
z   

 0    E 
 0 

 


n m
: Mx  AT   q  0, Ax  b,   0  ,

mxm

.  Lấy 
T

q 
1
                                f ( z )  z T ( M  M T ) z    z ,  

2
 b 

ở đó 
 M     -AT 

                         M  

 A       0 

( n  m ) x(n  m )

x
, z   
 

n m

. 

Ta có bài toán  quy hoạch toàn phương bổ trợ sau đây 
                                 min  f  z  : z   .                                                     (2.3) 

21 
 


 
 


Khoá luận tốt nghiệp                                                                        Vi Thị 
Tuyến 
Bổ đề 2.1.  Tập     là  khác  rỗng  khi  và  chỉ  khi  tồn  tại  x     sao  cho                    
T

 Mx  q 

v  0,  với mọi  v  0 .  

Chứng Minh.
x 
Điều kiện cần: Nếu      thì tồn tại  z    
 

n m

 sao cho 

                                  Mx  AT   q  0, Ax  b,   0.                              (2.4) 
Lấy  v  0 .  Bởi, (2.2), ta có  Av  0.  Từ (2.4) ta nhận được   
T

                            0   Mx  AT   q  v  ( Mx  q)T v   T Av.  
Do đó                              ( Mx  q)T v   T Av  0.  
T

Điều kiện đủ: Giả sử tồn tại  x     sao cho   Mx  q  v  0,  v  0    ( A).  
Xét bài toán tuyến tính sau 
                                           min cT y : y  ,                                              (2.5) 
ở 


đó 

c : Mx  q.  

Từ 
T

 Mx  q 

giả 

sử 

v  0   v 

n

trên 

ta 

có 

   

và                   

, Av  0.  


 Theo lý thuyết quy hoạch tuyến tính (2.5) có nghiệm. và tồn tại   

m

 sao 

cho 
                                         AT   c  0,   0.                                            (2.6) 
x 
Khi  x   , ta có  Ax  b . Kết hợp với (2.6) ta có kết luận  z :     .  Sao 
 
cho      .                                 

Bổ đề 2.2. Nếu tồn tại  x    sao cho  ( Mx  q)v  0     v  0 ,  thì bài toán 
quy hoạch toàn phương bổ trợ (2.3) có nghiệm. 
Chứng minh. Áp  dụng Bổ  đề  2.1,  từ  giả  thiết  ta  có     là  khác  rỗng.  Cho 
x
z      .  Ta có 
 

22