ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC SƯ PHẠM
––––––––––––––––––
PHẠM NGỌC SƠN

NGHIỆM SIÊU HỮU HIỆU CỦA BÀI TOÁN
TỐI ƯU VÀ BÀI TOÁN CÂN BẰNG VECTƠ
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 ĐỖ VĂN LƯU

THÁI NGUYÊN - 2015


LUẬN VĂN

MỞ ĐẦU

NỘI DUNG

KẾT LUẬN


Bài toán cân bằng vectơ (VEP) được đưa vào nghiên cứu bởi Ansari, Oettli
và Schlager và Bianchi, Hadjisavvas và Schaible vào năm 1997.
Gần đây bài toán cân bằng vectơ được nghiên cứu rộng rãi, bởi vì nó bao
gồm nhiều bài toán khác, các trường hợp đặc biệt như: bài toán bất đẳng thức
biến phân vectơ, bài toán tối ưu vectơ trong đó bao gồm tối ưu hóa một tập, bài
toán cân bằng Nash vectơ,...

Trong lý thuyết của bài toán cân bằng vectơ cũng như trong lý thuyết tối ưu
vectơ người ta thường xét các nghiệm hữu hiệu yếu, nghiệm hữu hiệu Pareto,
nghiệm hữu hiệu toàn cục, nghiệm hữu hiệu Henig và nghiệm siêu hữu hiệu.
Nghiệm siêu hữu hiệu có nhiều tính chất phong phú và được nhiều nhà toán học
quan tâm nghiên cứu. Zheng – Yang – Teo (2007) đã thiết lập các tính chất đặc
trưng cho điểm siêu hữu hiệu trong tối ưu vectơ. Gong (2011) đã chứng minh
điều kiện đủ và các tính chất đặc trưng cho nghiệm siêu hữu hiệu của bài toán
cân bằng vectơ. Đây là đề tài được nhiều tác giả trong và ngoài nước quan tâm
nghiên cứu. Chính vì thế mà tôi chọn đề tài: “ Nghiệm siêu hữu hiệu của bài
toán tối ưu và bài toán cân bằng vectơ ”.


Chương 1
TÍNH CHẤT ĐẶC TRƯNG CỦA ĐIỂM SIÊU HỮU HIỆU
CỦA MỘT TẬP ĐÓNG.

NỘI
DUNG
Chương 2
TÍNH CHẤT ĐẶC TRƯNG CỦA NGHIỆM
SIÊU HỮU HIỆU CỦA BÀI TOÁN CÂN BẰNG VECTƠ


1.1 ĐIỂM SIÊU HỮU HIỆU CỦA MỘT
TẬP ĐÓNG

Chương 1
1.2 CÁC TÍNH CHẤT ĐẶC TRƯNG CỦA
ĐIỂM SIÊU HỮU HIỆU CỦA
MỘT TẬP ĐÓNG



Giả sử X là một không gian Banach và X* là không gian đối ngẫu
của X. Giả sử C là nón nhọn lồi đóng trong X xác định thứ tự bộ phận
 trong X:
x  x  x  x C .
C

1

C

2

2

1

Giả sử  là một tập con đóng của X và a  . Nhắc lại rằng a là
một điểm hữu hiệu Pareto của  , kí hiệu a  E  , C  , nếu
x  và x  a  0  x  a  0 .
C

Theo Borwein và Zhuang 5 , ta nói rằng điểm a là điểm siêu hữu hiệu
(superefficient point) của  nếu tồn tại một số thực M > 0 sao cho
cl cone(  a) ( B  C )  MB ,
X

X


trong đó B là hình cầu đơn vị của X. Nghiệm siêu hữu hiệu có nhiều
tính chất phong phú và được nghiên cứu rộng rãi.
X


Ký hiệu SE(  ,C) là tập tất cả các điểm siêu hữu hiệu của  . Ta biết
rằng a  SE  , C  nếu và chỉ nếu tồn tại M > 0 sao cho
x  , y  X và x  a  y  x  a  M y .
C

(1.1)

Ta suy ra SE  , C   E  , C  .
Ta nói rằng a  là một điểm siêu hữu hiệu địa phương của  , ký
hiệu a  SE  , C  , nếu tồn tại   0 sao cho
L

a  SE    B  a,   ,C  ,

trong đó B  a,   là hình cầu mở tâm a, bán kính  . Như vậy,
a  SE  , C  nếu và chỉ nếu tồn tại hằng số M,   0 sao cho
L

x   B  a,   , y  X và x  a  y  x  a  M y .
C

Rõ ràng là SE  , C   SE  , C  .
L

(1.2)



Khi  lồi ta sẽ chứng minh rằng SE  , C   SEL  , C  . Trong trường hợp 
không lồi có lẽ thích hợp hơn là ta xét nghiệm siêu hữu hiệu địa phương. Nhiều kết
quả đã biết về nghiệm siêu hữu hiệu đòi hỏi giả thiết lồi. Chẳng hạn, với giả thiết 
là lồi và C có một cơ sở bị chặn, Borwein và Zhuang 5 chứng minh rằng

a  SE  , C   c  int  C
*



 sao cho

c , a  min  c , x : x  ,
*

*

trong đó

C : x  X *: x , c  0, c  C .


*

*

Chú ý rằng khi  là lồi


c , a  min  c , x : x   c  N  , a 
*

*

*

c

(trong đó N c ( .,. ) ký hiệu nón pháp tuyến Clarke), kết quả Borwein và Zhuang có thể
viết lại như sau:

a  SE  , C   x  N  , a  sao cho 0  int  C  x


*

c

*




Nhắc lại rằng nón thứ tự C được gọi là có một cơ sở bị chặn nếu tồn tại
một tập con lồi bị chặn
C = t : t  0,  và 0  cl (Θ).
Ta biết rằng C là cơ sở bị chặn nếu và chỉ nếu int  C   Ø. Khi bỏ giả
thiết nón thứ tự có một cơ sở bị chặn, ta mở rộng được kết quả của
Borwein và Zhuang cho trường hợp  bán dưới trơn (semi-subsmooth)

tại a (khái niệm này được định nghĩa ở dưới). Giả sử  là bán dưới trơn
tại a. Chúng ta sẽ chứng minh rằng các mệnh đề sau tương đương:
(i) a  SE  , C  .
(ii) Tồn tại M,   (0, ) sao cho
x  a  M  y  d  x,    với bất kỳ  x, y   B  a,    X với x  a  y
trong đó d  x,    inf  x  u : u .


L

C

(iii) 0  int  C  N  , a  .


c


Trong trường hợp  lồi ta chứng minh các phát biểu sau là tương
đương:
(i) a  SE  , C  .
(ii) a  SE  , C  .
(iii) Tồn tại hằng số M > 0 sao cho
x  a  M  y  d  x,    với bất kỳ  x, y   X  X với
xa  y.
(iv) 0  int  C  N  , a  .
Bây giờ ta giả sử X là không gian Banach được trang bị thứ tự bộ
phận bởi một nón lồi đóng C. Với một tập con đóng A của X và a
 A, giả sử T  A, a  và là nón tiếp liên của A tại a:
T  A, a  : {h  X : t  0, h  h với a  t h  A

L

C



c

n

n

n

n


Ta biết rằng T  A, a  là một nón lồi đóng trong X còn T  A, a  là một nón
đóng có thể không lồi. Giả sử N  A, a  là nón pháp tuyến Clarke của A
tại a.
c

c

Như vậy,
T  A, a  = h  X : x , h  0, x  N  A,a  .
*

(1.4)


*

c

c

f được gọi là hàm chính thường nếu dom
f  x     x  D  .

Hàm

f  Ø

và

Giả sử f : X  R   là hàm nửa liên tục dưới, chính thường và
 f  x  là dưới vi phân Clarke của f tại x (với f  x    ), tức là,
c

 f  x  := x  X :  x , 1  N  epi( f  ,  x, f  x   ,
*

c

*

*

c


trong đó epi  f  :  u, t   X  R : f  u   t (xem 1 )


Nếu A và

f

là lồi, thì ta biết rằng

N  A, a 

:= x  X

*

 f  x

:=x  X

: x ,u  x  f  u   f  x  , u  X  .

c

*

: x ,a  x  0, x  A

(1.5)

*


và
c

*

*

*

(1.6)

Nhắc lại rằng tập A là chính quy gần kề tại a nếu tồn tại  ,   0
sao cho x , x  A  B  a,  và x  N  A, x   B , i 1,2 , ta có
*

1

2

i

c

X*

i

x  x , x  x   x  x
*


*

2

1

2

1

2

1

2

.

Mới đây, Aussel, Daniilidis và Thibault đã đưa vào nghiên cứu khái
niệm dưới trơn (subsmoothness), bán dưới trơn (semi subsmoothness).


Ta nói rằng tập A là dưới trơn tại

a A

  0,   0

nếu với bất kỳ


sao cho
ta có

x , x  A  B  a,  
1

2

và x  N  A, x   B
*

i

c

X*

i

x  x , x  x   x  x
*

*

2

1

2


1

2

.

1

Ta nói rằng A là bán dưới trơn tại

  0,   0

sao cho

x  A  B  a,   , a  N  A, a   B
*

ta có

c

X*

và

x  a , x  a   x  a
*

*


, i 1,2 ,

a A

nếu với bất kỳ

x  N  A, a   B
*

c

.

X*

,


Rõ ràng là:
Tính lồi
dưới trơn.



tính chính quy gần kề



tính dưới trơn


Nhắc lại rằng tập A được gọi là chính quy tại a
(theo nghĩa Clarke)
nếu T  A, a   T  A, a  .
c

Ta có :
Tính bán dưới trơn  tính chính quy



tính bán


Thật vậy, giả sử h T  A, a  và a  N  A, a   B , và lấy các dãy t  0
và h  h sao cho a  th  A với mọi số tự nhiên n. Khi đó, do tính
bán dưới trơn của A tại a, với bất kỳ   0 tồn tại số tự nhiên n sao
cho
t a , h  0  a ,  a  t h   a   t h , n  n .
Từ đó và h  h kéo theo a , h   h . Cho   0 , ta suy ra a , h  0 .
Bởi vì h và a là tùy ý tương ứng trong T  A, a  và N  A, a   B ,
Cho nên
T  A, a   h  X : a , h  0, a  N  A, a   T  A, a  .
Chú ý rằng bao hàm thức T  A, a   T  A, a  luôn đúng.
Do đó ta có T  A, a   T  A, a  . Điều này chỉ ra A là chính quy tại a theo
nghĩa Clarke.
Trong chương này khái niệm bán dưới trơn và chính quy sẽ đóng vai
trò quan trọng.



*

c

n

n

X

*

n

n

0

*

n

*

n

n

n


n

n

0

*

*

n

*

c

*

*

c

c

c

c

X*



Nhận xét 1.1
Từ chứng minh định lý 1.1 ta thấy rằng các suy luận (ii)
 (iii)

không đòi hỏi giả thiết

đi giả thiết







(i) và(i)

là bán dưới trơn tại a. Nhưng khi bỏ

là bán dưới trơn tại a suy luận (iii)

đúng thậm chí trong không gian hữu hạn chiều.



(i) có thể không


Định lý 1.1
Giả thiết rằng  là bán dưới trơn tại a. Khi đó, các phát biểu

sau là tương đương:
(i) a  SE  , C  .
(ii) Tồn tại M,   (0, ) sao ch
x  a  M  y  d  x,    với bất kỳ  x, y   B  a,    X với
xa  y.
(iii) 0  int  C  N  , a  .
L

C



c

Nhận xét 1.1
Từ chứng minh định lý 1.1 ta thấy rằng các suy luận (ii)  (i) và
(i)  (iii) không đòi hỏi giả thiết  là bán dưới trơn tại a.
Nhưng khi bỏ đi giả thiết  là bán dưới trơn tại a suy luận (iii)
 (i) có thể không đúng thậm chí trong không gian hữu hạn
chiều.


Định lý 1.2
Giả sử  lồi. Khi đó, các phát biểu sau là tương
đương:
(i) a  SE  , C  .
(ii) a  SE  , C  .
(iii) Tồn tại M,   (0, ) sao cho
x  a  M  y  d  x,    với bất kỳ  x, y   B  a,    X với
xa  y.

(iv) Tồn tại một hằng số M   0,   sao cho
x  a  M  y  d  x,    với bất kỳ  x, y   X  X
với x  a  y .
(v) 0  int  C  N  , a  .
L

C

C



c


Nhận xét 1.2
Lấy X  l , C  x l : mỗi tọa độ của x là không âm} và
  C.
Như vậy, với kết quả của Borwein và Zhuang, ta không thể
kiểm tra được rằng liệu 0 có là một điểm siêu hữu hiệu của 
theo C hay không.
Mặt khác, chú ý rằng 0  int  C  N  ,0   , bởi vì
N  ,0   C  C và l  C  C . Từ Định lý 1.2 suy ra
0  SE  , C  .
Cuối cùng, ta xét trường hợp  là compact địa phương tại a
(tức là tồn tại   0 , sao cho    a   B  là compact).
Ta biết rằng  là compact địa phương tại mỗi điểm của 
nếu X là hữu hạn chiều.
2


2



c



c

2

X


Định lý 1.3
Giả sử  là compact địa phương tại a và  chính quy tại
a theo nghĩa Clarke. Khi đó, các phát biểu sau là tương
đương:
(i) a  SE  , C  .
L

(ii) 0  SE T  , a  , C .
(iii) 0  E T  , a  , C .
(iv) 0  int  C  N  , a  .


c



2.1 KIẾN THỨC CHUẨN BỊ

Chương 2
2.2 CÁC TÍNH CHẤT ĐẶC TRƯNG CHO
NGHIỆM SIÊU HỮU HIỆU CỦA
BÀI TOÁN CÂN BẰNG VECTƠ


Giả sử X là không gian vectơ tôpô Hausdorff thực, Y là không gian vectơ
tôpô lồi địa phương thực, A là tập con của X và F : A A  Y là song
hàm.
Xét bài toán cân bằng vectơ (viết tắt là VEP): tìm x  A sao cho
F  x, y   K \ 0 , y  A ,
trong đó K là một nón lồi trong Y.
Giả sử X là không gian vectơ tôpô Hausdorff thực và Y là không gian
Banach thực, C là nón nhọn lồi đóng trong Y và giả sử Y* là không gian
đối ngẫu tôpô trongY và nón C sinh ra thứ tự bộ phận trong Y được định
nghĩa bởi

y  y  y  y  C.
C được gọi là chuẩn tắc nếu U  C   U  C  bị chặn, trong đó U là
hình cầu đơn vị đóng trong Y .
Giả sử
C   y  Y : y , y  0, y  C
là nón đối ngẫu của C .
1

*

*


2

2

*

1


Với mỗi

x  A , ta ký hiệu
F  x, A  

yA

F  x, y .

Giả sử D là tập con khác rỗng của Y . Bao nón của D được định
nghĩa bởi
cone  D   td : t  0, d  D.
Ký hiệu nón đối ngẫu của D bởi

D :  y  Y : y , d  0, d  D.
Ký hiệu phần trong của D bởi int D .
*

*


*

*

Định nghĩa 2.1
Một vectơ x  A được gọi là một nghiệm siêu hữu hiệu của bài toán
(VEP) nếu tồn tại số thực M  0 sao cho
cone F  x, A  U  C   MU .





Ký hiệu là VS  A, F  là tập các nghiệm siêu hữu hiệu (superefficient
solution) của bài toán (VEP).


Định nghĩa 2.2
Một vectơ x  A được gọi là một nghiệm siêu hữu hiệu nón (conesuperefficient solution) của bài toán (VEP) nếu tồn tại số thực
M  0 sao cho
cone F  x, A  C  U  C   MU .





Ký hiệu là VCS  A, F  là tập các nghiệm siêu hữu hiệu nón của
bài toán (VEP).
Bài toán (VEP) bao gồm bài toán tối ưu vectơ như trường hợp đặc
biệt nếu.

F  x, y   y  x, ( x, y  A ),
thì một nghiệm siêu hữu hiệu (VEP) là một điểm siêu hữu hiệu của
một tập A trong Y như đã trình bày trong chương 1.


Giả sử X là không gian vectơ tôpô Hausdorff thực và Y là không gian
Banach thực. Giả sử C là một nón nhọn lồi đóng trong Y .
Từ định nghĩa của nghiệm siêu hữu hiệu, ta dễ dàng nhận được bổ đề
sau.
Bổ đề 2.1
x0 VS  A, F  nếu và chỉ nếu tồn tại hằng số M  0 sao cho với
bất kỳ

x  A và y  Y , nếu F  x , x   y thì
F  x , x  M y .
0

0

Định lý 2.1
Nếu 0  int C   F  x , A  thì x0 VS  A, F  .



*

*

0




Hệ quả 2.1
Nếu Y *  C *   F  x0 , A * thì x V  A, F  .
0

S