ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
—————————

NGÔ THỊ THO

PHƯƠNG PHÁP CHIẾU GIẢI BÀI TOÁN
BẤT ĐẲNG THỨC BIẾN PHÂN GIẢ ĐƠN ĐIỆU MẠNH

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

Hà Nội - 2015


ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
—————————

NGÔ THỊ THO

PHƯƠNG PHÁP CHIẾU GIẢI BÀI TOÁN
BẤT ĐẲNG THỨC BIẾN PHÂN GIẢ ĐƠN ĐIỆU MẠNH

Chuyên ngành: Toán ứng dụng.
Mã số: 60460112.

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

NGƯỜI HƯỚNG DẪN KHOA HỌC:
GS.TSKH. LÊ DŨNG MƯU


8

9

1.2.1. Các khái niệm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2.2. Sự tồn tại nghiệm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

Chương 2. Phương pháp chiếu giải bài toán bất đẳng thức biến phân giả đơn
điệu mạnh . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.1. Phương pháp chiếu dưới đạo hàm tăng cường . . . . . . . . . . . . . . . . . . . .

13

2.2. Phương pháp chiếu cơ bản cải biên . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

16

Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

22

Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

23

1


LỜI CẢM ƠN


mình về bài toán bất đẳng thức biên phân, liên quan tới việc giải các bài toán biến
phân, bài toán điều kiển tối ưu và các bài toán biên có dạng của phương trình đạo
hàm riêng. Năm 1980, Kinderlehrer và Stampacchia cho xuất bản cuốn sách "An
Introduction to Variational Inequalities and Their Applications", giới thiệu bài toán
biến phân trong không gian vô hạn chiều và ứng dụng của nó. Năm 1984, cuốn
sách "Variational and Quasivariational Inequalities: Applications to Free Boundary
Problems" của C. Baiocci và A. Capelo đã á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 không có biên.
Hiện nay bài toán bất đẳng thức biến phân đã phát triển thành nhiều dạng khác
nhau,như là: bất đẳng thức biến phân vectơ, tựa bất đẳng thức biến phân, giả bất đẳng
thức 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 nhiều nhà toán học. Vì mô hình của nó
chứa nhiều bài toán quan trọng của một số lĩnh vực trong toán học cũng như thực tế
như tối ưu hóa, bài toán bù, lý thuyết trò chơi, cân bằng Nash, cân bằng mạng giao
thông, cân bằng di trú....
Một trong những hướng nghiên cứu quan trọng của bất đẳng thức biến phân là
việc xây dựng các phương pháp giải. Dựa trên tính chất của kiểu đơn điệu G. Cohen
đã nghiên cứu phương pháp nguyên lý bài toán phụ. Ngoài ra còn có phương pháp
hiệu chỉnh Tikhonov, phương pháp chiếu, phương pháp điểm trong. Những phương
pháp này khá hiệu quả, dễ thực hiện trên máy tính nhưng sự hội tụ của chúng chỉ
được đảm bảo trên cơ sở các giả thiết khác về tính chất đơn điệu.
Có nhiều phương pháp chiếu khác nhau, như là: phương pháp chiếu cơ bản,
phương pháp chiếu dưới đạo hàm, và phương pháp chiếu siêu phẳng. Mỗi phương
pháp giải quyết một lớp các bài toán bất đẳng thức biến phân nhất định. Do đó sự hội
tụ của thuật toán được đảm bảo.
Luận văn trình bày phương pháp chiếu dưới đạo hàm tăng cường và chiếu cơ bản
cải biên để giải bài toán bất đẳng thức biến phân giả đơn điệu mạnh. Các phương
pháp này tạo ra một dãy hội tụ của các điểm lặp dễ dàng tính được. Chúng đều hội tụ
3


toán bất đẳng thức biến phân thường gặp trong thực tế cũng như trong các mô hình
toán học. Cuối chương phát biểu và chứng minh định lý về sự tồn tại và tính duy nhất
nghiệm của bài toán. Nội dung chủ yếu được trích dẫn từ tài liệu [1], [2], [3], [6],
[10].
Trong luận văn này, chúng ta sẽ làm việc trên không gian Hilbert thực trang bị
một tô pô yếu, với tích vô hướng ., . và chuẩn tương ứng của nó là ||.||.

5


1.1.

Kiến thức chuẩn bị

1.1.1.

Hội tụ mạnh và yếu trong không gian Hilbert

Định nghĩa 1.1.1. Giả sử H là không gian tuyến tính thực, với mọi x ∈ H xác định
một số gọi là chuẩn của x ( kí hiệu ||x||) thỏa mãn ba tiên đề sau:
1. Xác định dương: ∀x ∈ H

||x|| ≥ 0;

2. Thuần nhất dương: ∀x ∈ H; ∀λ ∈ R
3. Bất đẳng thức tam giác: ∀x, y ∈ H

||x|| = 0 ⇔ x = 0.
||λ x|| = |λ | ||x||.
||x + y|| ≤ ||x|| + ||y||.



1.1.2.

Toán tử chiếu

Định nghĩa 1.1.4. Giả sử C là một tập lồi, khác rỗng trong không gian Hilbert thực
H và x0 ∈ C.
1. Nón pháp tuyến (ngoài) của C tại x0 kí hiệu là NC (x0 ) được định nghĩa bởi:
NC (x0 ) := {ω ∈ H| ω T (x − x0 ) ≤ 0 ∀x ∈ C}.
Tập −NC (x0 ) được gọi là nón pháp tuyến (trong) của C tại x0 .
2. Nón pháp tuyến ε của C tại x0 được định nghĩa bởi:
NCε (x0 ) := {ω ∈ H| ω T (x − x0 ) ≤ ε

∀x ∈ C}.

Định nghĩa 1.1.5. Giả sử C = 0/ (không nhất thiết lồi) là một tập con của không gian
Hilbert H và y là một véc-tơ bất kỳ, khoảng cách từ y đến C được định nghĩa bởi
dC (y) := inf ||x − y||.
x∈C

Nếu tồn tại π ∈ C sao cho dC (y) := ||π − y||, thì ta nói π là hình chiếu (khoảng cách)
của y trên C, kí hiệu π = pC (y).
Mệnh đề 1.1.1. Cho C là một tập lồi đóng khác rỗng. Khi đó:
1. Với mọi y ∈ H, π ∈ C hai tính chất sau là tương đương:
a) π = pC (y),
b) y − π ∈ NC (π).
2. Với mọi y ∈ H, hình chiếu pC (y) của y trên C luôn tồn tại và duy nhất.
3. Nếu y ∈
/ C, thì pC (y) − y, x − pC (y) = 0 là siêu phẳng tựa của C tại pC (y)

Định nghĩa 1.1.7. Cho f : H → R, hàm f được gọi là nửa liên tục dưới tại x0 ∈ H
nếu
∀{xk } ⊂ H : xk → x0 ⇒ limk→∞ f (xk ) ≥ f (x0 ).
Hàm f được gọi là nửa liên tục dưới trên D ⊆ H nếu nó liên tục dưới tại mọi x ∈ D.
Hàm f là nửa liên tục trên nếu − f là nửa liên tục dưới. Nếu hàm f vừa liên tục trên
vừa liên tục dưới thì nó liên tục.

1.1.4.

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

Tính khả vi của hàm lồi đóng vai trò quan trọng trong các phương pháp tối ưu
hóa. Lớp các hàm lồi có những tính chất rất đẹp mà các lớp hàm khác không có. Giả
sử f : H → R là hàm lồi. Ta có các khái niệm sau
Định nghĩa 1.1.8. Vectơ ω ∈ H ∗ được gọi là dưới đạo hàm của f tại x0 ∈ H nếu:
ω, x − x0 ≤ f (x) − f (x0 ), ∀x ∈ H.
Tập hợp tất cả các dưới đạo hàm của hàm f tại x0 được gọi là dưới vi phân của hàm
f tại x0 , kí hiệu là
∂ f (x0 ) := {ω ∈ H ∗ : ω, x − x0 ≤ f (x) − f (x0 ), ∀x ∈ H}.
8


Hàm f được gọi là khả dưới vi phân tại x0 nếu ∂ f (x0 ) = 0.
/
Định nghĩa 1.1.9. Cho ε > 0, một vectơ ω ∈ H ∗ được gọi là ε-dưới đạo hàm của f
tại x0 ∈ H nếu:
ω, x − x0 ≤ f (x) − f (x0 ) + ε, ∀x ∈ H.
Tập hợp tất cả các ε-dưới đạo hàm của hàm f tại x0 được gọi là ε-dưới vi phân của
hàm f tại x0 , kí hiệu là
∂ε f (x0 ) := {ω ∈ H ∗ : ω, x − x0 ≤ f (x) − f (x0 ) + ε, ∀x ∈ H}.


Các khái niệm

Định nghĩa 1.2.1. Cho K ⊂ H là một tập đóng, khác rỗng, F : K → H là một ánh xạ
đơn trị. Bài toán bất đẳng thức biên phân (đơn trị) là bài toán
Tìm x∗ ∈ K sao cho F(x∗ ), y − x∗ ≥ 0, ∀y ∈ K.
Tập nghiệm của bài toán kí hiệu là S(K, F).
9

(VIP)


Định nghĩa 1.2.2. Giả sử K ⊂ H là một tập lồi đóng, khác rỗng và toán tử F : K → H
được gọi là
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) giả đơn điệu mạnh trên K nếu tồn tại γ > 0 sao cho
F(x), y − x ≥ 0 ⇒ F(y), y − x ≥ γ||y − x||2

∀x, y ∈ K,

d) giả đơn điệu trên K nếu

thức biến phân (VIP). Tức là bài toán bất đẳng thức biến phân tương đương với bài
toán điểm bất động.

1.2.2.

Sự tồn tại nghiệm

Trong phần này, trình bày chứng minh theo tài liệu [9] rằng bài toán bất đẳng thức
biến phân giả đơn điệu mạnh luôn tồn tại một nghiệm và đó là nghiệm duy nhấtcủa
bái toán.
Bổ đề 1.2.1. Giả sử K là một tập lồi đóng, khác rỗng trong không gian Hilbert H.
Cho F : K → H là một toán tử sao cho F(∗), y − ∗ là nửa liên tục trên với mỗi
y ∈ K . Giả sử
∃ tập compăc W : ∀x ∈ K\W, ∃y ∈ K : F(x), y − x < 0.
Thì bài toán bất đẳng thức biến phân (VI) có một nghiệm.
Mệnh đề 1.2.3. Giả sử F là β − giả đơn điệu mạnh trên K. Nếu F(∗), y − ∗ là nửa
liên tục trên với mỗi y ∈ K thì bài toán bất đẳng thức biến phân (VI) có một nghiệm
duy nhất.

11


Chương 2

Phương pháp chiếu giải bài
toán bất đẳng thức biến phân
giả đơn điệu mạnh
Chương này, trình bày các thuật toán chiếu giải bài toán bất đẳng thức biến phân
giả đơn điệu mạnh V I(K, F). Phần đầu, trình bày thuật toán chiếu dưới đạo hàm tăng
cường (mỗi bước lặp có hai lần chiếu) với độ dài bước được lấy từ một khoảng đóng

∞

∑ λk = +∞,
k=0

lim λk = 0.

k→∞

Bước 1: Đặt k=0.
Bước 2: Tính
uk = PK (uk − λk F(uk )),
uk+1 = PK (uk − λk F(uk )).
Bước 3: Nếu uk = uk thì dừng lại. Ngược lại thì đặt k + 1 = k và quay lại bước 2.
Nếu thuật toán dừng ở bước thứ k, thì ta đặt uk = uk với mọi k ≥ k + 1. Vì thế,
Thuật toán 2.1.1 tạo ra một dãy lặp vô hạn.
Định lý 2.1.1. Cho K là một tập lồi, đóng, khác rỗng trong không gian Hilbert thực
H. Giả sử F : K → H là liên tục Lipschitz và giả đơn điệu mạnh trên K, thì dãy lặp
{uk } được tạo bởi Thuật toán 2.1.1 hội tụ mạnh tới nghiệm u∗ của bài toán. Hơn nữa,
tồn tại một chỉ số k0 ∈ N sao cho γλk < 1 với mọi k ≥ k0 và
||u

k+1

k

∗

∏ (1 − γλ j )||uk0 − u∗ ||,


1
(k + 1)2

∀k ∈ N.

∞

Từ đó ∑ λk < +∞, và dãy lặp {uk } được tạo bởi Thuật toán 2.1.1 được cho bởi
k=0

uk+1 = PK (uk − λk F(PK (uk − λk F(uk ))))
= uk − λk F(uk − λk F(uk ))
= uk − λk (uk − λk uk )
= (1 − λk + λk2 )uk .
Vì u0 = 1, ta có
k
k+1

u

=

∏

j=1

=

= ∏ 1−


j=1 ( j + 1)

=∏

∀k ∈ N.

Do đó, {uk } là dãy giảm và bị chặn dưới nên nó hội tụ.
k+2
1
= .
k→∞ 2(k + 1)
2

lim uk ≥ lim

k→∞

1
Ta được lim uk = u∗ với u∗ ≥ .Do vậy, dãy {uk } không hội tụ tới nghiệm duy nhất
k→∞
2
của bài toán VI(K, F).
Ví dụ 2.1.2. Cho K, F, u0 như trong Ví dụ 2.1.1 và λk = 1 với mọi k ∈ N. Do đó
k−1

∞

∑ λk = +∞. Tuy nhiên như đã tính toán ở trên uk = ∏ (1 − λ j + λ j2 ) = 1 với mọi
j=0


Dãy lặp

{uk }

F(u), v − u = 0 và F(v), v − u = 0.
được tạo bởi Thuật toán 2.1.1 được cho bởi



u0
= (u01 , u02 )T



 k+1
1
1 k
u1
= 1−
uk1 +
u
2
(k + 1)
k+1 2



1
1 k


1
1
+
(k + 1)2 (k + 1)4

k
0

1−

1−

j=0

1
1
+
.
2
( j + 1)
( j + 1)4

Khi đó
k
k

0

lim ||u || = ||u || lim


= µ||u0 || (µ ≥
).
2
Do đó, {uk } không hội tụ đến nghiệm duy nhất của bài toán VI(K, F).
Qua các ví dụ trên ta thấy rằng, nếu bỏ đi bất kỳ một trong ba đều kiện trên thì
dãy lặp {uk } đều không hội tụ tới nghiệm duy nhất của bài toán VI(F, K).
15


2.2.

Phương pháp chiếu cơ bản cải biên

Thuật toán 2.2.1. Cho trước u0 ∈ K và {λk } ⊂ (0, +∞).
Bước 1: Đặt k=0.
Bước 2: Tính u k = PK (uk − λk F(uk )), nếu u k = uk thì dừng lại. Nếu không thì
chuyển sang bước tiếp theo.
Bước 3: Đặt uk+1 = u k , sau đó quay lại bước 2.
Nếu thuật toán chấm dứt ở bước thứ k, thì ta đặt uk = uk với mọi k ≥ k + 1. Như
vậy, đối với một dãy các độ dài bước thay đổi {λk } ⊂ (0, +∞), Thuật toán 2.2.1 tạo
ra cho mỗi điểm ban đầu u0 ∈ K một dãy lặp vô hạn {uk }.
Mệnh đề 2.2.1. Cho K là một tập lồi, đóng, khác rỗng trong không gian Hilbert
thực H và ánh xạ F : K → H là giả đơn điệu mạnh trên K với mô-đun γ và liên tục
Lipschitz trên K với hằng số L. Cho {uk } là dãy lặp được tạo ra bởi Thuật toán 2.2.1
và u∗ là nghiệm duy nhất của bài toán VI(K, F) thì
[1 + λk (2γ − λk L2 )] ||uk+1 − u∗ ||2 ≤ ||uk − u∗ ||2 , ∀k ∈ N.
Bài toán VI(K, F) luôn có duy nhất một nghiệm, và dãy lặp được tạo bởi Thuật
toán 2.2.1, với độ dài bước được chọn từ một khoảng đóng của các số thực dương,
hội tụ tuyến tính tới nghiệm duy nhất đó. Cụ thể, ta có định lý sau:
Định lý 2.2.1. Cho K là một tập lồi, đóng, khác rỗng trong không gian Hilbert thực


1
1 + a(2γ − bL2 )

∈ (0, 1).

Chú ý 2.2.1 Khi a = b = λ , độ dài bước là cố định. Do đó phương pháp chiếu cơ
bản cải biên trở thành phương pháp chiếu cơ bản và µ trở thành
µ=

1
1 + λ (2γ − λ L2 )

.

2γ
. Các ước tính sai số là chặt chẽ khi µ là nhỏ nhất. Xét
L2
2γ
µ như một hàm của λ ∈ 0, 2 , ta tìm được giá trị nhỏ nhất của µ là
L
L
γ
µ ∗ :=
tại điểm λ∗ := 2 .
L
L2 + γ 2

Ta có λ ∈ 0,


.
2
2 + γ2


L
γ


 1+

2
tL
Vậy suy ra
min µ(a, b) : 0 < a ≤ b


i=1

∑ |ui |2 < +∞}. Định nghĩa u, v = ∑ ui vi và ||u|| =

u, u là tích vô hướng và

chuẩn của hai vectơ u, v trên H, với u = (u1 , u2 , · · · , ui , · · · ),v = (v1 , v2 , · · · , vi , · · · ) ∈ H
β
bất kỳ. Cho α, β ∈ R sao cho β > α > > 0. Đặt
2
Kα = {u ∈ H : ||u|| ≤ α},

Fβ (u) = (β − ||u||)u,

trong đó α, β là các tham số. Dễ thấy S(Kα , Fβ ) = {0}. Hàm Fβ là liên tục Lipschitz
và giả đơn điệu mạnh trên Kα . Thật vậy, với u, v ∈ Kα bất kỳ,
||Fβ (u) − Fβ (v)|| = ||(β − ||u||)u − (β − ||v||)v||
= ||β (u − v) − ||u||(u − v) − (||u|| − ||v||)v||
≤ β ||u − v|| + ||u|| ||u − v|| + | ||u|| − ||v|| | ||v||
≤ β ||u − v|| + α ||u − v|| + α||u − v||
= (β + 2α)||u − v||.
Do đó Fβ là liên tục Lipschitz trên Kα với hằng số Lipschitz L := β + 2α. Cho u, v ∈
Kα sao cho Fβ (u), v − u ≥ 0. Theo giả thiết ||u|| ≤ α < β . Suy ra u, v − u ≥ 0.
Do đó
Fβ (v), v − u = (β − ||v||) v, v − u
≥ (β − ||v||)

v, v − u − u, v − u



Lấy u0 ∈ Kα bất kỳ, và λ ∈ 0,

||uk+1 − 0|| ≤

µ
µ k+1 1
||u − u0 || và ||uk+1 − 0|| ≤
||uk+1 − uk ||
1−µ
1−µ

với mọi k ∈ N, trong đó
µ=

1
1 + λ [2(β − α) − λ (β + 2α)2 ]

Theo Chú ý 2.2.1 giá trị nhỏ nhất của µ là µ∗ =
λ = λ∗ =

.

β + 2α
(β − α)2 + (β + 2α)2 ]

tại điểm

β −α
.



Hệ quả 2.2.2. Cho {λk } như trong Định lý 2.2.2. Cho F là đơn điệu mạnh trên K với
mô-đun γ và liên tục Lipschitz trên K với một hằng số L. Thì dãy {uk } bất kỳ được
tạo ra từ Thuật toán 2.2.1 hội tụ theo chuẩn tới nghiệm duy nhất của bài toán VI(K,
F) và tồn tại một chỉ số k0 ∈ N sao cho
1

||uk+1 − u∗ || ≤

||uk0 − u∗ ||,

∏ki=k0 [1 + λi (2γ − λi L2 ]
đúng với mỗi k ≥ k0 .
Ví dụ 2.2.2. Cho H = l2 , α, β ∈ R sao cho β > α >
Kα = {u ∈ H : ||u|| ≤ α},

β
> 0. Đặt
2

Fβ (u) = (β − ||u||)u,

∞
1
, ∀k ∈ N. Khi đó ∑ λk = +∞, lim λk = 0.
k→∞
k+1
k=0
k

1
,
(k + 2)2

∀k ∈ N.

∞

Từ đó lim λk = 0 và ∑ λk < +∞, cả hai điều kiện (2.4) và (2.5) đều bị lược bỏ. Dãy
k→∞

lặp

uk

k=0

được tạo bởi Thuật toán 2.2.1 với u0 = 1 được cho bởi
uk+1 = PK (uk − λk F(uk )) = uk − λk uk = (1 − λk )uk .

20


Do đó,
k

k

uk+1 = ∏(1 − λi )


Vậy lim uk =

∞

điều kiện ∑ λk = +∞, lim λk = 0 và λk = 1, ∀k ∈ N. Khi đó dãy lặp {uk } trở thành
k=0

k→∞

uk+1 = PK (uk − λk F(uk )) = uk − λk uk = (1 − λk )uk .
Để chứng minh {uk } hội tụ tuyến tính đến 0, ta cần chứng minh:
||uk+1 − 0||
lim
= µ, với µ ∈ (0, 1).
k→∞ ||uk − 0||
Vì lim λk = 0 và uk = 0 với mọi k ∈ N, ta có
k→∞

||uk+1 − 0||
= lim |1 − λk | = 1.
k→∞ ||uk − 0||
k→∞
lim

Vậy {uk } không hội tụ tuyến tính tới nghiệm duy nhất của bài toán VI(K, F).
Ví dụ trên cho thấy rằng dãy {uk } được xét trong Định lý 2.2.2 có thể không hội
tụ tuyến tính tới nghiệm duy nhất của bài toán VI(K, F). Mặt khác, trong một so sánh
với dãy lặp được tạo Định lý 2.2.1, công thức lặp trong Định lý 2.2.2 có tốc độ hội
tụ chậm hơn. Như vậy, bên cạnh những ưu điểm nêu trên, thì phương pháp chiếu cải
biên không có hằng số tiên nghiệm cũng có những nhược điểm về tốc độ hội tụ.

6. Igor Konnov (2001), Combined Relaxation Methods for Variational Inequalities,
Springer.
7. Pham Duy Khanh (2012), ”A new extragradient method for strongly pseudomonotone variational inequalities”, Submitted.
8. Pham Duy Khanh, Phan Tu Vuong (2014), ”Modified projection method for strongly
pseudomonotone variational inequalities”, Journal of Global Optimization,58,
no 2, 341 - 350.
9. Phung M. Duc, Le D. Muu, and Nguyen V. Quy (2014), ”Solution - existence and
algorithms with their convergence rate for strongly pseudomonotone equilibrium problems”, Pracific Journal Mathematics, Pacific J. Mathematics, To
appear.

23