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

LÊ THỊ HUỆ

MỘT SỐ PHƯƠNG PHÁP
GIẢI BÀI TOÁN
BẤT ĐẲNG THỨC BIẾN PHÂN

LUẬN VĂN THẠC SĨ TOÁN HỌC

Hà Nội, 2017


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

LÊ THỊ HUỆ

MỘT SỐ PHƯƠNG PHÁP
GIẢI BÀI TOÁN
BẤT ĐẲNG THỨC BIẾN PHÂN

LUẬN VĂN THẠC SĨ TOÁN HỌC
Chuyên ngành: Toán giải tích
Mã số: 60460102

Người hướng dẫn khoa học
TS. Nguyễn Thế Vinh

HÀ NỘI, 2017

1.5.4. Phương pháp chiếu gradient . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

13
14
17
22

Chương 2. Phương pháp extragradient giải bài toán bất đẳng thức biến
phân . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.1. Giới thiệu phương pháp và minh họa hình học . . . . . . . . . . . . . . . . . . 26
2.2. Sự hội tụ của phương pháp extragradient . . . . . . . . . . . . . . . . . . . . . . . 27
2.2.1. Kết quả hội tụ mạnh . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.2. Kết quả hội tụ yếu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Chương 3. Các dạng cải tiến của phương pháp extragradient . . . . . . .
3.1. Phương pháp subgradient extragradient . . . . . . . . . . . . . . . . . . . . . . . .
3.1.1. Giới thiệu phương pháp và minh họa hình học . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1.2. Sự hội tụ của thuật toán subgradient extragradient . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

27
34

37
37
38
39

3.2. Phương pháp Popov subgradient extragradient. . . . . . . . . . . . . . . . . .
3.3. Phương pháp chiếu gradient đối xứng . . . . . . . . . . . . . . . . . . . . . . . . .



Lời cam đoan
Tôi xin cam đoan, dưới sự hướng dẫn của TS Nguyễn Thế Vinh, luận văn
thạc sĩ chuyên ngành Toán giải tích với đề tài "Một số phương pháp giải bài
toán bất đẳng thức biến phân" được hoàn thành bởi chính sự nhận thức của
bản thân tác giả.
Trong suốt quá trình nghiên cứu thực hiện luận văn, tác giả đã kế thừa những
thành tựu của các nhà khoa học với sự trân trọng và biết ơn.
Hà Nội, tháng 06 năm 2017
Tác giả
Lê Thị Huệ


Mở đầu
1. Lý do chọn đề tài
Năm 1966, Hartman và Stampacchia [7] đã công bố những nghiên cứu đầu
tiên của mình về bài toán bất đẳng thức biến phân, liên quan đến việc giải các
bài toán biến phân, bài toán điều khiển tối ưu và các bài toán biên trong lý thuyết
phương trình đạo hàm riêng. Năm 1980, trong cuốn sách "An Introduction to
Variational Inequalities and Their Applications", Kinderlehrer và Stampacchia
[11] đã nghiên cứu bài toán bất đẳng thức biến phân trong không gian vô hạn
chiều và ứng dụng của nó. Năm 1984, trong cuốn sách "Variational and Quasivariational Inequalities " của Baiocchi và Capelo [3] đã áp dụng bất đẳng thức
biến phân và tựa biến phân để giải các bài toán biên tự do.
Hiện nay bài toán bất đẳng thức biến phân đã được mở rộng và phát triển
cho nhiều dạng khác nhau như bất đẳng thức biến phân véctơ, bất đẳng thức tựa
biến phân, bất đẳng thức biến phân ẩn, bất đẳng thức biến phân suy rộng. Bài
toán này đã thu hút được sự quan tâm của đông đảo các nhà toán học trên thế
giới vì nó là mô hình hợp nhất của nhiều bài toán quan trọng trong lý thuyết và
thực tiễn như tối ưu hóa, bài toán bù, lí tuyết trò chơi, cân bằng Nash, cân bằng
mạng giao thông,. . .


6. Đóng góp của luận văn
• Luận văn đã trình bày một cách hệ thống và chi tiết một số phương pháp
giải bài toán bất đẳng thức biến phân.
• Luận văn trình bày các thuật toán quan trọng được sử dụng nhiều để giải
bài toán bất đẳng thức biến phân trong vòng 50 năm trở lại đây như thuật
toán chiếu gradient, thuật toán extragradient, thuật toán subgradient extragradient, thuật toán Popov subgradient extragradient và thuật toán chiếu
gradient đối xứng cùng với các kết quả hội tụ của chúng.
• Luận văn sẽ là tài liệu tham khảo hữu ích cho những ai quan tâm đến các
phương pháp giải bài toán bất đẳng thức biến phân để áp dụng vào các lĩnh
vực liên quan như điểm bất động, tối ưu, phương trình đạo hàm riêng,...

7. Tổng quan và bố cục của luận văn
Bài toán bất đẳng thức biến phân là bài toán
Tìm x ∈ K sao cho F (x) , y − x ≥ 0 với mọi y ∈ K,

(VIP(K, F ))

trong đó K là tập con lồi, đóng, khác rỗng của không gian Hilbert thực H và F :
K → H là ánh xạ đơn trị.
2


Lý thuyết bài toán bất đẳng thức biến phân đóng vai trò quan trọng trong
nhiều lĩnh vực như quy hoạch toán học, nghiên cứu mạng giao thông, lý thuyết
trò chơi,... và đã trở thành một lĩnh vực nghiên cứu quan trọng trong vòng 50
năm trở lại đây (xem Ansari [2], Giannessi [6], Kinderlehrer và Stampacchia
[11], Konnov [12]). Nhờ vào tính chất của phép chiếu, ta biết rằng bài toán
VIP(K, F ) tương đương với bài toán điểm bất động sau:
Tìm x¯ sao cho x = PK (x − λF (x)) ,

Ngoài phần mở đầu và phần tài liệu tham khảo, luận văn được chia làm 3
chương.
Chương 1: nhắc lại một số kiến thức cơ bản về giải tích lồi, giới thiệu bài
3


toán bất đẳng thức biến phân và các ứng dụng, đồng thời trình bày sự tồn tại
nghiệm của bài toán và phương pháp chiếu gradient.
Chương 2: trình bày phương pháp extragradient, phân tích sự hội tụ yếu và
hội tụ mạnh của phương pháp này.
Chương 3: trình bày các dạng cải tiến của phương pháp extragradient, cụ
thể trình bày về phương pháp subgradient extragradient, phương pháp Popov
subgradient extragradient, phương pháp chiếu gradient đối xứng, đồng thời xét
đến sự hội tụ của các phương pháp trong không gian Hilbert.

4


Chương 1
Một số kiến thức chuẩn bị
Trong chương này, chúng ta 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 ở các chương sau. Các kết quả chủ yếu tham khảo trong
[1, 2].

1.1. Các khái niệm
1.1.1. Tập lồi và nón pháp tuyến của một tập lồi
Định nghĩa 1.1. Cho H là một không gian Hilbert thực, tập hợp C ⊂ H được
gọi là tập lồi nếu
∀x, y ∈ C, ∀λ ∈ [0, 1] ⇒ λx + (1 − λ)y ∈ C.
Ví dụ 1.1. Hình cầu đóng B (x, r) = {a ∈ H : a − x ≤ r} là tập lồi.


6


Định nghĩa 1.5. Cho a ∈ H là một vectơ khác không và λ ∈ R.
a) H ++ = {x ∈ H : a, x > λ} được gọi là nửa không gian mở trên.
b) H −− = {x ∈ H : a, x < λ} được gọi là nửa không gian mở dưới.
c) H + = {x ∈ H : a, x ≥ λ} được gọi là nửa không gian đóng trên.
d) H − = {x ∈ H : a, x ≤ λ} được gọi là nửa không gian đóng dưới.

Hình 1.4: Nửa không gian đóng.

Nhận xét 1.1. a) Một siêu phẳng sẽ chia không gian thành hai nửa không gian.
b) Các nửa không gian là các tập lồi.
Định nghĩa 1.6. Cho S ⊂ H khác rỗng và x nằm trên biên của S. Siêu phẳng
H = {x ∈ H : a, x − x = 0, a = 0, a ∈ H}
được gọi là siêu phẳng tựa của S tại x nếu
S ⊆ H + , tức là a, x − x ≥ 0 ∀x ∈ S,
hoặc
S ⊆ H − , tức là a, x − x ≤ 0 ∀x ∈ S.
Nhận xét 1.2. Định nghĩa 1.6 có thể phát biểu tương đương như sau: Siêu phẳng
H = {x ∈ H : a, x − x = 0}
là siêu phẳng tựa của S tại x nằm trên biên của S nếu
a, x = inf { a, x : x ∈ S} ,
hoặc
a, x = sup { a, x : x ∈ S} .
Nhận xét 1.3. Mỗi điểm biên của một tập lồi đều có một siêu phẳng tựa đi qua.
7



∀x, y ∈ H (tính

∀x ∈ H và y ∈ K.

Hình 1.5: Tính không giãn của phép chiếu metric.

1.1.4. Sự hội tụ yếu, hội tụ mạnh trong không gian Hilbert
Định nghĩa 1.7. Cho không gian Hilbert thực H.
a) Dãy xk ⊂ H được gọi là hội tụ yếu tới điểm x ∈ H nếu ∀y ∈ H dãy
y, xk hội tụ tới y, x . Ta gọi x là giới hạn yếu của dãy xk và viết
xk
x. Nếu dãy con {xnk } ⊆ xk hội tụ yếu tới x thì x được gọi là điểm
tụ yếu của dãy xk .
8


b) Ta nói xk hội tụ mạnh tới x nếu lim xk − x = 0.
k→∞

Mệnh đề 1.3. Dãy hội tụ yếu có các tính chất sau:
a) Nếu dãy xk ⊂ H hội tụ yếu thì nó có đúng một giới hạn yếu,
b) Nếu dãy xk ⊂ H hội tụ yếu thì nó bị chặn,
c) Nếu dãy xk ⊂ H bị chặn thì nó chứa một dãy con hội tụ yếu,
d) Nếu dãy xk
xk
x,

⊂ H bị chặn và có đúng một điểm tụ yếu x ∈ H thì

e) Nếu dãy xk hội tụ mạnh tới x ∈ H thì nó hội tụ yếu tới x ∈ H,

duy nhất, phương pháp tìm điểm bất động và đánh giá được độ chính xác tại
mỗi bước lặp. Tuy nhiên, điều kiện co là khá ngặt. Việc nghiên cứu về điểm bất
động của ánh xạ không giãn sẽ phức tạp hơn nhiều so với ánh xạ co. Nó đòi hỏi
phải có những công cụ đặc biệt. Dưới đây, chúng tôi xin trình bày một số định
lý điểm bất động cổ điển.
9


Định lí 1.2. (Brouwer, 1912) Cho C là một tập con lồi, compact, khác rỗng của
một không gian Hilbert hữu hạn chiều H và T : C → C là một ánh xạ liên tục.
Khi đó T có một điểm bất động.
Định lý điểm bất động Brouwer tương đương với nguyên lý ánh xạ KKM sau
đây.
Định lí 1.3. Cho C là một tập hợp trong không gian véctơ tôpô tách X và F :
C → 2X là ánh xạ đa trị thỏa mãn:
a) F (x) đóng với mọi x ∈ C,
b) F là ánh xạ KKM, tức là với mọi tập hợp hữu hạn x1 , x2 , x3 , · · · , xk ⊂
C ta có
k

co

1

2

3

k



a) đơn điệu mạnh trên K nếu tồn tại δ > 0 sao cho
F (x) − F (y) , x − y ≥ δ x − y

2

∀x, y ∈ K.

b) đơn điệu trên K nếu
F (x) − F (y) , x − y ≥ 0 ∀x, y ∈ K.
c) đơn điệu chặt trên K nếu
F (x) − F (y) , x − y > 0 ∀x, y ∈ K, x = y.
d) giả đơn điệu mạnh trên K nếu tồn tại δ > 0 sao cho với mọi x, y ∈ K
F (x) , y − x ≥ 0 ⇒ F (y) , y − x ≥ δ y − x

2

.

e) giả đơn điệu trên K nếu với mọi x, y ∈ K
F (x) , y − x ≥ 0 ⇒ F (y) , y − x ≥ 0.
Ví dụ 1.4. a) Hàm F (x) = x, ∀x ∈ R là đơn điệu mạnh với δ = 21 .
b) Hàm F (x) = x3 , ∀x ∈ R là đơn điệu chặt.
c) Hàm F (x) = c, ∀x ∈ R là đơn điệu.
Theo định nghĩa trên các kéo theo (a) ⇒ (b), (a) ⇒ (c), (a) ⇒ (d), (c) ⇒
(e), (d) ⇒ (e) là hiển nhiên. Chú ý một toán tử giả đơn điệu mạnh có thể không
đơn điệu.
Ví dụ 1.5. Cho 0 < r < R, đặt K = B (r) : {x ∈ H : x ≤ r} và F được
cho bởi
F (x) , y − x := K (x) , y − x + (R − x ) G (x) , y − x ,

1.4. Ánh xạ hemi-liên tục
Định nghĩa 1.9. Giả sử K là một tập con lồi, đóng, khác rỗng trong không gian
Hilbert thực H và F : K → H là một ánh xạ. Khi đó F được gọi là hemi-liên
tục nếu với mọi x, y ∈ K và z ∈ H, hàm
λ → z, F (λx + (1 − λ) y)
từ [0, 1] vào R là hàm liên tục.
Ví dụ 1.6. Cho K = H = R2 và ánh xạ F : K → H xác định bởi F (x, y) =
(f1 (x, y) , 0) trong đó


 0, nếu x = 0 hoặc y ≤ 0,
y
f1 (x, y) =
nếu 0 < y ≤ x2 ,
x2 ,

 x2
nếu 0 < x2 ≤ y.
y ,
Dễ thấy f1 (x, y) liên tục khắp nơi trừ gốc tọa độ, tại đó nó liên tục theo bất
kỳ đường thẳng nào đi qua gốc tọa độ. Do đó F hemi-liên tục nhưng không liên
tục tại gốc tọa độ. Hơn nữa dễ thấy F là giả đơn điệu nhưng không đơn điệu. Để
thấy F không đơn điệu ta lấy u = (1, 2) và v = (2, 1) khi đó F (1, 2) = 12 , 0 ,
F (2, 1) = 14 , 0 và
F (1, 2)−F (2, 1) =

1
, 0 , (1, 2)−(2, 1) = (−1, 1) , (2, 1)−(1, 2) = (1, −1) .
4
12

Ví dụ 1.7. Trong R, xét tập K = [1; 5] ⊂ R và ánh xạ F : [1; 5] → R được xác
định bởi:
F (y) = y − 1 ∀y ∈ [1; 5] .
Khi đó, VIP(K, F ) là bài toán tìm x ∈ [1; 5] sao cho
x − 1, y − x ≥ 0 ∀y ∈ [1; 5] .

(1.2)

Ta chứng tỏ rằng: Sol(K, F) = {1}. Thật vậy, hiển nhiên x = 1 là một
nghiệm. Nếu 0 < x < 1 thì (1.2) chỉ thỏa mãn với y ≤ x. Ngược lại, nếu x > 1
thì (1.2) chỉ thỏa mãn với y ≥ x. Điều đó chứng tỏ x = 1 là nghiệm duy nhất.
Sau đây chúng ta sẽ trình bày mối quan hệ giữa VIP(K, F ) và nón pháp tuyến
của một tập lồi.
Mệnh đề 1.4. Cho K là một tập con lồi, đóng, khác rỗng của H và cho ánh xạ
F : K → H. Khi đó x là nghiệm của bất đẳng thức biến phân VIP(K, F ) khi và
chỉ khi −F (x) ∈ NK (x), trong đó NK (x) là nón pháp tuyến của K tại x.
Nói cách khác, x là nghiệm của bất đẳng thức biến phân VIP(K, F ) khi và
chỉ khi:
0 ∈ F (x) + NK (x).
13


Mệnh đề 1.5. Cho ánh xạ F : H → H. Véctơ x ∈ H là nghiệm của bất đẳng
thức biến phân VIP(K, F ) khi và chỉ khi F (x) = 0.
Chứng minh. Giả sử F (x) = 0 khi đó
F (x) , y − x = 0 ∀y ∈ K.
Suy ra x ∈ Sol(K, F).
Ngược lại, giả sử x ∈ Sol(K, F). Khi đó
F (x) , y − x ≥ 0 ∀y ∈ K.
Thay y = x − F (x) vào bất đẳng thức trên ta có:



Suy ra F (x) ∈ K ∗ .
Mặt khác, cũng vì K là nón và x ∈ K nên 2x ∈ K. Thay y trong bất đẳng
thức (1.3) bởi 2x ta được
(1.5)
F (x) , x ≥ 0.
Thay y trong bất đẳng thức (1.3) bởi 0 ta được
F (x) , −x ≥ 0.

(1.6)

Từ (1.5) và (1.6) ta kết luận: F (x) , x = 0, hay x là nghiệm của bài toán
NCP(K, F ).
Ngược lại, giả sử x ∈ K là nghiệm của bài toán NCP(K, F ). Theo định nghĩa
ta có:
F (x) ∈ K ∗ và F (x), x = 0.
Vì F (x) ∈ K ∗ nên F (x) , y ≥ 0 với mọi y ∈ K. Do đó
F (x) , y − x = F (x) , y − F (x), x ≥ 0 ∀y ∈ K.
Hay x là nghiệm của bài toán VIP(K, F ).
Bài toán tối ưu

Cho K ⊂ H là tập lồi, đóng, khác rỗng và f : K → R là một ánh xạ khả vi.
Bài toán tối ưu được phát biểu như sau:
Tìm x ∈ K sao cho f (x) = min {f (x) : x ∈ K} .

(1.7)

Mệnh đề 1.7. Nếu x ∈ K là nghiệm của bài toán tối ưu (1.7) thì x là nghiệm
của bài toán VIP(K, F ) với F = ∇f (đạo hàm của f ).

Khi đó bài toán VIP(K, F ) tương đương với bài toán điểm bất động (1.8), theo
nghĩa tập nghiệm của các bài toán này trùng nhau.
Chứng minh. Giả sử F (x) = x − T (x) với mọi x ∈ K và x ∈ K là nghiệm của
bài toán VIP(K, F ), tức là
F (x), x − x ≥ 0 ∀x ∈ K.
Do F (x) = x − T (x) nên
x − T (x), x − x ≥ 0 ∀x ∈ K.
Do T (x) ∈ K nên thay x ở trên bởi T (x) ta được
x − T (x), T (x) − x ≥ 0.
Hay
− x − T (x)

2

≥ 0.

Suy ra
x = T (x).
Ngược lại, giả sử x là nghiệm của bài toán điểm bất động (1.8). Khi đó
x = T (x).
16


Suy ra
F (x) = x − T (x) = 0
Hay
F (x), x − x = 0.
Suy ra điều phải chứng minh.
Mệnh đề 1.10. Cho K ⊂ H là một tập lồi, đóng, khác rỗng. Khi đó x ∈ K
là nghiệm của bài toán VIP(K, F ) khi và chỉ khi với mọi γ > 0, x là điểm bất



Trong trường hợp tập K không bị chặn, định lý về điểm bất động Brouwer
không áp dụng được. Khi đó, sự tồn tại nghiệm của bài toán VIP(K, F ) có thể
được thiết lập theo cách khác. Ký hiệu B (0, r) là hình cầu đóng tâm 0 bán kính
r > 0 trong không gian Hilbert H và đặt
K r = K ∩ B (0, r) .
Khi đó, K r bị chặn. Bài toán bất đẳng thức biến phân xác định trên K r , ký
hiệu là VIP(K r , F ) là bài toán
Tìm xr ∈ K r sao cho F (xr ), y − xr ≥ 0 ∀y ∈ K r .
Nếu K r = ∅ và K là tập con lồi đóng trong H thì K r lồi, compact, khác
rỗng. Hơn nữa, nếu F : K → H là ánh xạ liên tục thì theo Định lý 1.6, bài toán
VIP(K r , F ) luôn có nghiệm.
Định lí 1.7. Cho K ⊂ H là một tập lồi, đóng, khác rỗng và F : K → H là ánh
xạ liên tục. Khi đó, bài toán VIP(K, F ) có nghiệm khi và chỉ khi tồn tại r > 0
và xr là nghiệm của bài toán VIP(K r , F ) sao cho xr < r.
Chứng minh. Giả sử x là nghiệm của bài toán VIP(K, F ). Khi đó lấy r > 0 sao
cho x < r thì x là nghiệm của bài toán VIP(K r , F ).
Ngược lại, giả sử tồn tại r > 0 và xr là nghiệm của bài toán VIP(K r , F ) sao
cho xr < r. Lấy y ∈ K tùy ý. Vì xr < r nên có thể chọn λ > 0 đủ nhỏ sao
cho
ω = xr + λ(y − xr ) ∈ K r .
Do đó
0 ≤ F (xr ), ω − xr = λ F (xr ), y − xr .
Vì y ∈ K tùy ý nên xr là nghiệm của bài toán VIP(K, F ).
Định lí 1.8. Cho K là một tập lồi, đóng, khác rỗng trong H và F : K → H là
ánh xạ liên tục thỏa mãn
F (x) − F (x0 ), x − x0
→ ∞ khi x → ∞, x ∈ K, x0 ∈ K.
0

(1.11)

F (x2 ), y − x2 ≥ 0 ∀y ∈ K.

(1.12)

Thay y = x2 trong (1.11) và y = x1 trong (1.12) rồi cộng hai vế của hai bất
đẳng thức mới ta được:
F (x1 ) − F (x2 ), x2 − x1 ≥ 0
Hay
F (x1 ) − F (x2 ), x1 − x2 ≤ 0.
Điều này trái với định nghĩa về hàm đơn điệu chặt. Do đó x1 = x2 .
Nhận xét 1.4. Tính đơn điệu chặt không đảm bảo sự tồn tại nghiệm của bài toán
VIP(K, F ). Ví dụ, xét K = {x ∈ R : x ≥ 0} và F (x) = −e−x − 1. Khi đó F
đơn điệu chặt nhưng không tồn tại x ∈ K thỏa mãn F (x) ≥ 0. Do đó không
tồn tại x ∈ K sao cho bài toán VIP(K, F ) được thỏa mãn.
Định lí 1.10. Cho K là một tập con lồi, đóng, khác rỗng trong H và ánh xạ liên
tục F : K → H. Nếu F đơn điệu mạnh thì bài toán VIP(K, F ) tồn tại duy nhất
một nghiệm.
Chứng minh. Do F là ánh xạ đơn điệu mạnh nên với x0 ∈ K, tồn tại σ > 0 sao
cho
F (x) − F (x0 ), x − x0
≥ σ x − x0
∀x ∈ K.
0
x−x
19


Điều này kéo theo rằng F thỏa mãn điều kiện bức (1.9). Theo Định lý 1.8 thì

20