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

NGUYỄN THỊ QUỲNH

PHƯƠNG PHÁP CHIẾU
GIẢI BÀI TOÁN CÂN BẰNG
VÀ ÁP DỤNG VÀO MỘT SỐ
BÀI TOÁN CÂN BẰNG HAI CẤP

LUẬN VĂN THẠC SỸ

Chuyên ngành :

TOÁN GIẢI TÍCH

Mã số : 60 46 01 02

Giáo viên hướng dẫn:
GS.TSKH NGUYỄN XUÂN TẤ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
sự hướng dẫn nghiêm túc và nhiệt tình của GS. TSKH. Nguyễn Xuân Tấn (Viện
Toán học, Viện Hàn lâm Khoa học và Công nghệ Việt Nam). Tôi xin bày tỏ
lòng biết ơn sâu sắc tới thầy và kính chúc thầy cùng gia đình luôn mạnh khỏe.
Tôi xin gửi lời cảm ơn các thầy cô giảng dạy tại Đại học sư phạm Hà Nội 2
và Viện toán học, Viện Hàn Lâm Khoa học và công nghệ Việt Nam đã mang lại

1.1

1.2

11

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ồi . . . . . . . . . . . . . . . . . 13

1.1.3

Đạo hàm và dưới vi phân của hàm lồi . . . . . . . . . . . . 16

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

Bài toán cân bằng . . . . . . . . . . . . . . . . . . . . . . . 19

1.2.2

Bài toán bất đẳng thức biến phân . . . . . . . . . . . . . . 19

1.2.3




1.4.2

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 . . . . . . . . . . . . . . . . . . . . . . . . 29

2 PHƯƠNG PHÁP CHIẾU GIẢI BÀI TOÁN CÂN BẰNG GIẢ
ĐƠN ĐIỆU
2.1

31

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

3 ỨNG DỤNG VÀO MỘT SỐ BÀI TOÁN CÂN BẰNG HAI
CẤP
3.1

47



không gian Euclide n chiều

H

không gian Hilbert thực

x =

x, x

x, y

chuẩn của véc tơ x
tích vô hướng của hai véctơ x và y

intC

phần trong của tập C

riC

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

xk → x

dãy xk hội tụ tới x

domf




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 f tại x

∇x f (x, y)

đạo hàm của f (., y) tại x

∇y f (x, x)

đạo hàm của f (x, .) tại y

∂2 f (x, x)

dưới vi phân của hàm f (x, .) tại x

EP (C, f )

bài toán cân bằng


1. LÝ DO CHỌ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 C là một tập lồi đóng trong không gian Hilbert thực H và
f : C × C → R ∪ +∞

là song hàm cân bằng, tức là f thỏa mãn f (x, x) = 0 với ∀x ∈ C . Xét bài toán:
Tìm x∗ ∈ C sao cho f (x∗ , y)
8

0, ∀y ∈ C .


Bài toán này được đưa ra lần đầu tiên bởi H.Nikaido và K.Isoda vào năm
1955 khi tổng quát hóa bài toán cân bằng Nash trong trò chơi không hợp tác,
được Ky Fan giới thiệu vào năm 1972 thường được gọi là bất đẳng thức Ky Fan.
Tuy nhiên, nó có tên gọi là bài toán cân bằng.
Bài toán cân bằng khá đơn giản về mặt hình thức nhưng nó bao hàm nhiều lớp
bài toán quan trọng trong thực tế như: bài toán tối ưu, bài toán bất đẳng thức



Chương 1
MỘT SỐ KIẾN THỨC CHUẨ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ổ
trợ cần thiết được sử dụng ở chương sau. Kiến thức của chương này được tham
khảo chủ yếu ở tài liệu [1], [3], [7].

1.1
1.1.1

Các khái niệm và các kết quả cơ bản
Một số khái niệm về tập lồi

Trước hết ta nhắc lại một số khái niệm, kết quả cơ sở của giải tích lồi.
Định nghĩa 1.1. Trong không gian Hilbert thực H tập C ⊂ H :
1. Tập C được gọi là lồi nếu ∀x, y ∈ C, ∀λ ∈ [0, 1] ⇒ λx + (1 − λ)y ∈ C ,
2. Tập C được gọi là nón có đỉnh tại 0 nếu ∀x ∈ C, ∀λ > 0 ⇒ λx ∈ C ,
3. Nếu tập C vừa lồi vừa là nón có đỉnh tại 0 thì được gọi là nón lồi.
Ví dụ 1.1. - Tập rỗng và cả không gian là tập lồi.
- Tập M , N , trong không gian Rn như sau được gọi là các nón lồi có đỉnh tại
0:
M = (x1 , ..., xn ) ∈ Rn : xi

0, i = 1, n (tập M được gọi là orthant không âm.

N = (x1 , ..., xn ) ∈ Rn : xi > 0, i = 1, n (tập N được gọi là orthant dương).
11



2. ω = PC (x) ⇔ x − ω, y − ω

0, ∀y ∈ C ,

3. Ánh xạ x → PC (x) có tính chất:
a. Tính không giãn: PC (x) − PC (y)

x − y , ∀x, y ∈ H,

b. Tính đồng bức: PC (x) − PC (y), x − y

PC (x) − PC (y) 2 ,
∀x, y ∈ H,

c. x − PC (x), x − y

1.1.2

x − PC (x)

2

, ∀y ∈ C .

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

Cho tập hợp C khác rỗng, lồi của không gian Hilbert thực H và ánh xạ
f : C → R ∪ {+∞}

Định nghĩa 1.4. Khi đó:

Nếu domf = ø và f (x) > −∞ với mọi x ∈ C thì hàm f được gọi là hàm chính
thường.
Ví dụ 1.2. Các hàm chuẩn như : f (x) = x

1 , f (x)

= x

2 , f (x)

= maxi=1,n |xi |

là các hàm lồi trên Rn .
Hàm f (x, y) = x2 + y 2 là hàm lồi mạnh.
Hàm f (x) =

|x| là hàm tựa lồi trên R.

Định lý 1.2. (xem [2], Định lý 2.3). Giả sử f : X → R ∪ {+∞} là hàm lồi và
α ∈ [−∞, +∞]. Khi đó các tập mức
L0α (f ) = {x ∈ X : f (x) < α},
Lα (f ) = {x ∈ X : f (x)

α},

là các tập lồi.
Định nghĩa 1.5. Giả sử f : H → R, H là không gian Hilbert thực. Khi đó:
1. Hàm f được gọi là nửa liên tục dưới tại x0 ∈ H nếu
limx→x0 f (x)



K x−x

.

(1.1)

Nếu f Lipschitz địa phương tại mọi x ∈ D thì hàm f được gọi là Lipschitz địa
phương trên tập D ⊂ H.
Nếu (1.1) đúng với ∀x, x ∈ D thì hàm f được gọi là Lipschitz với hằng số K
trên tập D.

15


Định lý 1.4. (Xem [2], Định lý 2.10). Cho f là hàm lồi trên tập mở D ⊂ H,
f bị chặn trong một lân cận của điểm nào đó thuộc D, H là không gian Hilbert

thực. Khi đó f Lipschitz địa phương trên tập D.
Hệ quả 1.1. f : D → R là hàm lồi, liên tục tại điểm x0 thuộc tập lồi mở D thì
f được gọi là Lipschitz địa phương trên tập D.

1.1.3

Đạo hàm và dưới vi phân của hàm lồi

Phép tính vi phân là một trong những phép tính cơ bản nhất của giải tích.
Nhờ những tính chất đặc thù của hàm lồi mà phép tính vi phân của nó ngày
càng trở nên đa dạng và phong phú hơn.
Định nghĩa 1.7. Giả sử f : H → R, x ∈ H và d ∈ H {0}. Khi đó hàm f được

f (x, d) = inf

Vậy ta thấy, nếu f là hàm lồi, chính thường trên Rn thì ∀x ∈ domf, ∀d ∈
Rn , d = 0 ta có f (x, d)

f (x + d) − f (x).

Định lý 1.6. Cho f : Rn → R ∪ {+∞} khả vi, C ⊂ Rn là tập lồi đóng. Khi đó
các điều kiện sau là tương đương:
1. f là hàm δ lồi mạnh trên C ;
∇f (x), y − x + δ y − x 2 ;

2. f (y) − f (x)

3. ∇f (y) − ∇f (x), y − x

δ y − x 2.

Định nghĩa 1.8. Cho hàm f : H → R ∪ {+∞} là hàm lồi chính thường trên H.
Ta nói phần tử ω ∈ H là dưới đạo hàm của hàm f tại x ∈ H nếu
f (y) − f (x)

ω, y − x , ∀ ∈ H.

Tập tất cả các dưới đạo hàm của hàm f tại x được gọi là dưới vi phân của
hàm f tại x và kí hiệu là ∂f (x). Hàm f được gọi là khả dưới vi phân tại x nếu
∂f (x) khác rỗng.

Định lý 1.7. (Xem [3], Mệnh đề 11.3). Cho f : Rn → ∪ {+∞} là hàm lồi chính
thường. Khi đó:

argminx∈C f (x) của f 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 C . Nếu f lồi mạnh thì hàm số luôn có duy
nhất một điểm cực tiểu toàn cục trên C .
Định lý 1.11. (Xem [3], Mệnh đề 11.12). Giả sử C là tập lồi khác rỗng trong
R và f : Rn → R ∪ {+∞} là hàm lồi khả dưới vi phân trên C . Khi đó x0 là điểm
cực tiểu của f trên C khi chỉ khi:
0 ∈ ∂f (x0 ) + NC (x0 ).

Như vậy, với các giả thiết trong định lý (1.11) thì điểm x0 ∈ intC là điểm cực
tiểu của f trên C khi và chỉ khi 0 ∈ ∂f (x0 ). Đặc biệt, nếu hàm f khả vi thì điều
kiện này trở thành ∇f (x0 ) = 0.
18


1.2
1.2.1

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

Giả sử C là tập lồi đóng khác rỗng trong không gian Hilbert thực H và
f : C × C → R ∪ {+∞} thỏa mãn f (x, x) = 0 với ∀x ∈ C ; một hàm f 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∗ ∈ C sao cho f (x∗ , y)

0, ∀y ∈ C .


0, ∀y ∈ C} là nón cực của C (xem [3], trang

220-221). Vậy bài toán CP (C, F ) là một trường hợp riêng của bài toán cân bằng
EP (C, f ).

Tổng quát hơn, xét bài toán bất đẳng thức biến phân đa trị M V IP (C, F )
sau:




Tìm x∗ ∈ C, u∗ ∈ F (x∗ ) sao cho



 u∗ , y − x∗

0, ∀y ∈ C.

Trong đó, C ⊆ H là một lồi đóng và F : C → 2H là ánh xạ đa trị. Với mỗi
x ∈ C, F (x) là một tập lồi, compact và khác rỗng, ta sẽ đặt :
f (x, y) = supu∈F (x) u, y − x .

Bài toán M V IP (C, F ) trở thành bài toán cân bằng EP (C, f ) (xem [9], trang
1160) .
Một trường hợp riêng quen thuộc của bài toán M V IP (C, F ) là bài toán quy
hoạch lồi COP (C, h) được định nghĩa:
Tìm x∗ ∈ C sao cho h(x∗ )

h(y), ∀y ∈ C .

Bài toán tối ưu

Cho tập C ⊂ H lồi đóng khác rỗng, H là không gian Hilbert thực. h : C → R
là hàm số xác định trên C . Bài toán tối ưu được phát biểu:
Tìm x∗ ∈ C sao cho h(x∗ )

h(y), ∀y ∈ C .

Ta đặt f (x, y) := h(y) − h(x) thì bài toán tối ưu đươc đưa về bài toán cân
bằng EP (C, f ).

1.2.4

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

Giả sử C ⊂ H là một tập lồi đóng khác rỗng, H là không gian Hilbert thực
và ánh xạ đơn trị F : C → C . Khi đó, bài toán điểm bất dộng F P (C, F ) là bài
toán:
Tìm x∗ ∈ C sao cho x∗ = F (x∗ ).
Đặt:
f (x, y) = x − F (x), y − x ∀x, y ∈ C .

21


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ị M F P (C, F ) là bài toán tổng quát
hơn có dạng:
Tìm x∗ ∈ C sao cho x∗ ∈ F (x∗ ),
ở đó F : C → 2C là ánh xạ đa trị có giá trị lồi compact khác rỗng. Đặt

Nếu đặt
p
i=1 [fi (x1 , ..., xi , ..., xp ) − fi (x1 , ..., yi , ..., xp )].

f (x, y) =

Bài toán cân bằng Nash được đưa về bài toán cân bằng EP (C, f ). Hàm f xác
định bởi công thức trên được gọi là song hàm Nikaido - Isoda.

1.2.6

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

Cho A, B là tập lồi đóng khác rỗng trong không gian Hilbert thực H,
ϕ : A × B → R. Bài toán điểm yên ngựa được phát biểu như sau:





Tìm (x∗ , y ∗ ) ∈ A × B, sao cho



ϕ(x∗ , y)

ϕ(x∗ , y ∗ )

ϕ(x, y ∗ ), ∀(x, y) ∈ A × B.



ϕ(x, y ∗ ), ∀(x, y) ∈ A × B.

Do đó,
ϕ(x, y ∗ ) − ϕ(x∗ , y)

0, ∀(x, y) ∈ A × B,

và với x = x , y = y khi đó
ϕ(x , y ∗ ) − ϕ(x∗ , y )

Theo cách đặt, ta có f (u∗ , v)

0, ∀(x , y ) ∈ A × B .

0, ∀v ∈ C hay u∗ = (x∗ , y ∗ ) ∈ C là nghiệm của

bài toán cân bằng EP (C, f ).

1.2.7

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

Trong phần này chúng tôi trình bày một số điều kiện về sự tồn tại nghiệm
và một số tính chất của tập nghiệm của bài toán cân bằng EP (C, f ) .
Định lý 1.12. ( Xem [7], Ky Fan’s Theorem). Cho song hàm cân bằng f :
C × C → R ∪ {+∞} có các tính chất sau:

1. f (., y) nửa liên tục trên với mỗi y ∈ C ,
2. f (x, .) tựa lồi trên C với mỗi x ∈ C .

c) đơn điệu trên C nếu
f (x, y) + f (y, x)

0, ∀x, y ∈ C ;

d) giả đơn điệu trên C nếu
∀x, y ∈ C : f (x, y)
25

0 ⇒ f (y, x)

0;