B Ộ G IÁ O D Ụ C VÀ Đ À O TẠO
TR Ư Ờ N G ĐẠ I HỌC s ư PH Ạ M HÀ NỘI 2

N G U Y Ễ N THỊ Q U Ỳ N H

PHUƠNG

p h á p c h iế u

GIẢI B À I TO Á N C Â N B Ằ N G
VÀ Á P D Ụ N G VÀO M ỘT s ố
BÀ I TO Á N C Â N B Ằ N G H AI CA P

L U Ậ N V Ă N T H Ạ C SỸ

C huyên ngành

:

T O Á N G IẢ I TÍCH

M ã số : 60 46 01 02

Giáo viên hướng dẫn:
G S .T S K H N G U Y Ễ N X U Â N T A N

H À N Ộ I , 2016


Lời cảm ơn
Luận văn này được hoàn thành tại trường Đại học Sư phạm Hà Nội 2, dưới

M ỏ dầu

1

8

M Ộ T SỐ K IẾ N T H Ứ C C H U A N b ị

11

1.1

Các khái niệm và các kết quả cơ bản

11

1.1.1

Một số khái niệm về tập lồi

11

1.1.2

Một số khái niệm về hàm lồ]

13

1.1.3


Bài toán điểm bất đông

21

1.2.5

Bài toán cân bằng Nash trong trò chơi không hợp tác

22

1.2.6

Bài toán điểm yên ngựa

23

1.2.7

Sự tồn tại nghiệm của bài toán cân bằng

24

1.3

Bài toán cân bằng tương đương

27

1.4


Một phương pháp chiếu cho bài toán bất đẳng thức biến phân giả
đờn điệu

31

2.2

Bài toán cân bằng giả đớn điệu

35

2.3

Thuật toán cho bài toán cân bằng giả đơn điệu

39

Ứ N G D Ụ N G VÀO M Ộ T s ố

BÀI TOÁN CÂN BANG h a i

CẮP
3.1

47
Áp dụng vào bài toán tìm cực tiểu của hàm chuẩn Euclide trẽn
tập nghiệm của bài toán cân bằng giả đơn điệu

3.2


R"

không gian Euclide n chiều

e

không gian Hilbert thực

INI = -y/{x, x)

chuẩn của véc tơ X

{x, y}

tích vô hướng của hai véctơ X và y

in te

phần trong của tập

riC

phần trong tương đối của tập

xk

c

dãy Xk hội tụ tới X



tập các điểm cực tiểu của / trên

dc (x)

khoảng cách từ điểm X đến tập

c

Pc{x)

hình chiếu của điểm X trên tập

c

6


Nc( x)

nón pháp tuyến của tập c tại điểm X

B [a, r}

cầu đóng tâm a bán kính r

f ' (x, d)

đạo hàm theo hướng d của / tại X


bài toán bất đẳng thức biến phân trên
tập nghiệm của bài toán cân bằng

B V I P ( C, F , G )

bài toán bất đẳng thức biến phân hai cấp

BEP(C, f, g)

bài toán cân bằng hai cấp

7


Mở đầu
1. LÝ D O C H Ọ N Đ Ề TÀ I

Sự cân bằng thường được hiểu như là một trạng thái đồng đều nhau giữa những
lực lượng đối lập hay giữa những đối tượng có ảnh hưởng qua lại lẫn nhau, phụ
thuộc nhau. Thuật ngữ này được sử dụng rộng rãi trong nhiều ngữ cảnh khoa
học và kỹ thuật như trong Vật lí, Hóa học, Sinh h ọ c ...
Trong Vật lí, trạng thái cân bằng của một hệ, theo thuật ngữ cổ điển, xảy ra
khi hợp lực tác động lên hệ bằng không và trạng thái này được duy trì trong
một thời gian dài.
Trong Hóa học, cân bằng hóa học xảy ra khi tốc độ của phản ứng thuận bằng
với tốc độ phản ứng nghịch. Trong Sinh học, cân bằng sinh thái là trạng thái ổn
định tự nhiên của hệ sinh thái, hướng tới sự thích nghi cao nhất với điều kiện
sống.
Trong Toán học:
Cho

tập nghiệm của bài toán cân bằng.
Phần trọng tâm của luận văn này là trình bày một phương pháp chiếu giải bài
toán cân bằng giả đơn điệu và áp dụng vào một số bài toán cân bằng hai cấp.
Cấu trúc luận văn gồm 3 chương:
• Chương 1. Một số kiến thức chuẩn bị.
• Chương 2. Một phương pháp chiếu cho bài toán cân bằng giả đơn điệu.
• Chương 3. ứng dụng vào một số bài toán cân bằng hai cấp.
Luận văn này được hoàn thành tại Viện Toán học, Viện hàn lâm Khoa học
và Công nghệ Việt Nam. Tác giả luận văn xin cảm ơn GS.TSKH Nguyễn Xuân
Tấn đã dành nhiều thời gian hướng dẫn tận tình giúp tác giả hoàn thiện luận
9


văn.
Tác giả cũng xin bày tỏ lòng biết ơn các thầy cô và cán bộ công nhân viên của
Viện Toán học đã quan tâm giúp đỡ trong suốt quá trình tác giả học tập và
nghiên cứu tại Viện.
Trong quá trình viết luận văn cũng như xử lý văn bản chắc chắn không tránh
khỏi những sai sót. Tác giả mong nhận được sự đóng góp của quý thầy cô và
bạn đọc để luận văn được hoàn thiện hơn.

10


Chương 1
MỘT SỐ K IẾN THỨC C H U Ẩ N

bị

Trong chương này, chúng tôi nhắc lại khái niệm cũng như các kết quả bổ

c

c

c}

tại x° và tập - N c (x°) được gọi là nón

tại x ũ.

Ta nhận thấy 0 e Nc( x°) và theo định nghĩa trên ta thấy Nc( x°) là một nón
lồi đóng.
Đ ịn h n g h ĩa 1.3. Giả sử

c

là tập con khác rỗng của không gian Hilbert thực

HI và véc tơ y £ HI bất kỳ, gọi

dc (y) = inf \\x - y II,
i€ C

ta nói d c ( y ) là khoảng cách từ y đến

c.

Nếu tồn tại Pc { y ) £

Ily —Pc(y)\\, thì ta nói P c ( y ) là hình chiếu của y trên

1.1.2

M ột số khái niệm về hàm lồi

Cho tập hợp
/ :c

—>R u

c

khác rỗng, lồi của không gian Hilbert thực H và ánh xạ

{+oo}

Đ ịn h n g h ĩa 1.4. Khi đó:
1. Hàm số / được gọi là tựa lồi trên

c nếu VA Ễ M tập mức {x G c : ỉ(x)


ep iị = {(x,t) e C x l : f ( x ) < t},
lần lượt gọi là miền hữu hiệu và trên đồ thị của f.
Nếu dom f Ỷ 0 và f ( x) > —00 với mọi X e

c

thì hàm / được gọi là hàm chính

thường.
V í dụ 1.2. c ác hàm chuẩn như : f ( x) = Ila: Il , f ( x ) = ||x||2 ,/(a;) = m axi=Y^\xi\
là các hàm lồi trên R”.
Hàm f ( x , y ) = X2 + y2 là hàm lồi mạnh.
Hàm f ( x ) = yj\x\ là hàm tựa lồi trên R.
Đ ịn h lý 1.2. (xem [2], Đ ịnh lý 2.3). Giả sử f : X -> E u {+oo} là hàm lồi và
a e [-oo,+oo]. K hi đó các tập mức
Ll ư ) = (x e X : f ( x ) < a},
L a ( f ) = {x e X : f ( x ) < a},
là các tập lồi.
Đ ịn h n g h ĩa 1.5. Giả sử / : HI -» R, H là không gian Hilbert thực. Khi đó:
1. Hàm / được gọi là nửa liên tục dưới tại x° e HI nếu

l imx^ xof(x) ^ ỉ (x°)

14


(nghĩa là với Ve > 0 ,3 7 > 0 sao cho Vz € H thỏa mãn || íc —ÍC° II < 7 ta có
f(x)



Ễ

int(domf),f(x)


0 sao cho:

Vx, x' Ễ U : If ( x ) — /(a:,)| ^ K ||x —a/ỊI .

( 1. 1)

Nếu / Lipschitz địa phương tại mọi X € D thì hàm / được gọi là Lipschitz địa
phương trên tập D c HI.
Nếu (1.1) đúng với Mx,x' e D thì hàm / được gọi là Lipschitz với hằng số K
trên tập D.

15


Đ ịn h lý 1.4. (X e m [2], Định lý 2.10). Cho f là hàm lồi trên tập mở D c H,


khi đó X* được gọi là đạo hàm của / tại X và được kí hiệu là v / ( x ) hoặc /'(x);
2. Có đạo hàm theo hướng d tại X nếu tồn tại giới hạn
f ' ( x; d ) = lim

f ( x + td) - f ( x )
t

í-> 0 +

Như vậy, nếu hàm / khả vi tại X thì nó có đạo hàm theo mọi hướng tại X và
ta có f ’(x;d) =
0 ta có /'(:£, d) ^ /( x + d) —/(x ).

Đ ịn h lý 1.6. Cho ỉ : R" -» R u { + 00} khả vi,

c

c Rn /ầ íáp ỉồi đóng, K hi đó

các điều kiện sau là tương đương:
1. / là hầm 5 lồi m ạnh trên C;
2- f ( y) - f ( x) ^ ( V f ( x ) , y - x) + ỏ IIy - x||2;
3- ( Vf ( y ) - X f ( x ) , y - x) ^ ỗ IIy - x\\2.

Đ ịn h n g h ĩa 1.8. Cho hàm / : H -» R u { + 00 } là hàm lồi chính thường trên H.
Ta nói phần tử UI e H là dưới đạo hàm của hàm / tại X G H nếu
ỉ(y) - f ( x) > ( w , í i - i ị , V ẽ I .

Tập tất cả các dưới đạo hàm của hàm / tại X được gọi là dưới vi phân của
hàm / tại X và kí hiệu là df (x). Hàm / được gọi là khả dưới vi phân tại X nếu
d f ( x ) khác rỗng.
Đ ịn h lý 1.7. ( Xem [3'], M ệnh đề 11.3). Cho ỉ : R" -» U {+oo} là hàm lồi chính
thường. K hi đó:
1. Nếu X Ỷ dom Ị thì df ( x) bằng rỗng.
2. Nếu X e int (domf ) thì df ( x ) khác rỗng và compact.
Đ ịn h lý 1.8. ( Xe m [2], Định lý 4 .3). Cho f là hàm lồi chính thường trên R".
K hi đó các điều kiện sau tương đương:
1. CƯe df ( x) .
2 . f ' ( x, d) ^ {u,d)
17

I u { + 0° } là hàm lồi.
Giả sử

c

là tập lồi đóng khác rỗng trong R. K hi đó, m ọi điểm cực tiểu địa

phương của f trên

c

đều là cực tiểu toàn cục, ngoài ra tập các điểm cực tiểu

argmi nxec f ( x ) của / trên

c

là m ột tập lồi. Hơn nữa, nếu f lồi chặt thì hàm số

có không quá m ột điểm cực tiểu trên
nhất m ột điểm cực tiểu toàn cục trên

c . N ếu

f lồi m ạnh thì hàm số luôn có duy

c.

1.2
1.2.1

B ài to á n cân b ằn g và m ộ t số bài to á n m ô tả
dưới d ạn g cân b ằn g
B ài toán cân bằng

Giả sử
/ :c X

c

c

là tập lồi đóng khác rỗng trong không gian Hilbert thực HI và

->• R u { + 00} thỏa mãn f ( x , x ) = 0 với Vx € C; một hàm / như vậy

được gọi là song hàm cân bằng. Bài toán cân bằng được phát biểu:
Tìm

X* e

c

sao cho f (x*, y)

^

0,Vj/ e


c.
Như ta đã biết, điểm

là nghiệm của bài toán COP(C, h) khi và chỉ khi nó là nghiệm của bài

toán bất đẳng thức biến phân đa trị M V I P ( C , d h ) sau:
'
Tìm X* e c,u * € dh(x*) sao cho


21

-

x)Mx, y e

c.


Bài toán F P ( C , F ) trở thành bài toán EP ( C , f ) .
Bài toán điểm bất động của ánh xạ đa trị MF P( C, F) là bài toán tổng quát
hơn có dạng:
Tìm X* e

c

sao cho X* e F(x*),

ở đó F : c -> 2C là ánh xạ đa trị có giá trị lồi compact khác rỗng. Đặt
f(x,y):=

Khi đó, X* e

max {x - u , y - x) , x , y €

u€ F ( x)

c.

c là nghiệm của bài toán MF P( C, F ) khi và chỉ khi X* là nghiệm

lược của họ. Về mặt toán học, điểm X* e

c

được gọi là điểm cân bằng Nash nếu

ỉi(x \, ...,x*ị_v x^,x*i+v ...,£*) ^ fi(x*v ...,x*ị_v yi,x*i+1,...,x l),V y i € Cị và Vỉ = 1,p.
22


Bài toán tìm điểm cân bằng Nash X* được gọi là bài toán cân bằng Nash.
Nếu đặt

f ( x ,y)

=

J2P
i=1 [fi(x 1 , -

, xũ - ,

xp )

-

fi(x i,

-



hay