ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN CAO NGHI THỤC
MỘT SỐ THUẬT TOÁN D-GAP GIẢI BÀI
TOÁN CÂN BẰ NG VÀ BẤT ĐẲNG THỨC
BIẾN PHÂN

LUẬN VĂN THẠC SĨ TOÁN HỌC
1.2 Hàm liên tục trên không gian định chuẩn . . . . . . . . . . . 10
1.2.1 Tính liên tục của hàm trên không gian định chuẩn . . 10
1.2.2 Tính liên tục của hàm lồi trong không gian định chuẩn 11
1.2.3 Hàm nửa liên tục trong không gian định chuẩn . . . . 14
1.3 Tính đơn điệu của ánh xạ . . . . . . . . . . . . . . . . . . . . 15
1.4 Đạo hàm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.4.1 Đạo hàm theo hướng . . . . . . . . . . . . . . . . . . . 16
1.4.2 Đạo hàm Gâteaux và đạo hàm Fréchet . . . . . . . . . 17
2 Bài toán cân bằng và bất đẳng thức biến phân 20
2.1 Phát biểu bài toán . . . . . . . . . . . . . . . . . . . . . . . . 20
2.1.1 Bài toán cân bằng . . . . . . . . . . . . . . . . . . . . 20
MỤC LỤC 3
2.1.2 Bất đẳng thức biến phân . . . . . . . . . . . . . . . . 21
2.2 Hàm Gap của bài toán cân bằng . . . . . . . . . . . . . . . . 21
2.3 Bài toán cân bằng bổ trợ . . . . . . . . . . . . . . . . . . . . 23
2.4 Nghiệm của bài toán cân bằng và bất đẳng thức biến phân . 24
3 Một số thuật toán D-gap giải bài toán cân bằng và bất đẳng
thức biến phân 26
3.1 Hàm D-gap của bài toán cân bằng và bất đẳng thức biến phân 26
3.2 Thuật toán D-gap giải bài toán cân bằng và bất đẳng thức
biến phân . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.2.1 Thuật toán D-gap giải bài toán cân bằng . . . . . . . 34
3.2.2 Thuật toán D-gap giải bài toán bất đẳng thức biến phân 40
Kết luận 46
Tài liệu tham khảo 47
Lời nói đầu
Bài toán bất đẳng thức biến phân (Variational Inequality Problem) ra đời vào
thập niên 60 của thế kỷ XX với những đóng góp to lớn của G. Stampacchia,
J. L. Lions Đến nay, bài toán đã được phát triển thành nhiều dạng khác
nhau như bất đẳng thức biến phân vec tơ, bất đẳng thức biến phân suy rộng,

bằng và bất đẳng thức biến phân.
Chương 1
Các kiến thức cơ bản
1.1 Tập lồi và hàm lồi
1.1.1 Tập lồi trong không gian tuyến tính
Định nghĩa 1.1.1 Giả sử X là không gian tuyến tính. M ⊆ X được gọi là
tập lồi nếu ∀x, y ∈ S, ∀α ∈ [0, 1] : αx + (1 −α)y ∈ S.
Mệnh đề 1.1.2
(i) Giao họ bất kỳ các tập lồi là tập lồi.
(ii) Nếu C ⊆ X, D ⊆ X là hai tập lồi và α ∈ R thì
C + D := {c + d : c ∈ C, d ∈ D},
αC := {αx : x ∈ C}
cũng là tập lồi. Do đó C − D := C + (−1)D cũng là tập lồi.
Định nghĩa 1.1.3 Giả sử X là không gian tuyến tính. x ∈ X được gọi là tổ
hợp tuyến tính lồi của x
1
, x
2
, , x
m
∈ X nếu tồn tại α
1
, α
2
, , α
m
> 0 thỏa
mãn
m


α} là tập lồi , ∀α ∈ R.
(ii) f là hàm lồi chính thường khi và chỉ khi với bất kỳ x, y ∈ domf và
α ∈ [0, 1] ta có f [αx + (1 −α)y] ≤ αf(x) + (1 − α)f(y).
Định lý 1.1.10(Bất đẳng thức Jensen) Giả sử f là hàm chính thường trên
S. Khi đó, f là lồi trên S khi và chỉ khi ∀x
1
, x
2
, , x
m
∈ S, ∀α
1
, α
2
, , α
m
≥
0;
m

i=1
α
i
= 1, f(
m

i=1
α
i
x

∗
).
fđược gọi là lồi chặt trên S nếu nó lồi chặt tại mọi x ∈ S.
(iii) Hàm f được gọi là lõm (concave) tại x
∗
∈ S nếu −f là lồi tại x
∗
∈ S.
(iv) Hàm f được gọi là lõm chặt (strictly concave) tại x
∗
∈ S nếu −f là lồi
chặt tại x
∗
∈ S.
(v) Hàm f được gọi là lồi mạnh (strongly convex) tại x
∗
∈ S nếu ∀x ∈
S, ∀α ∈ [0, 1], ∃ρ > 0 thỏa mãn
f[αx + (1 − αx
∗
)] ≤ αf(x) + (1 − α)f(x
∗
) −ρα(1 − α)x − x
∗

2
.
Hàm f được gọi là lồi mạnh trên S nếu nó lồi mạnh tại mọi x ∈ S.
Nhận xét Nếu f lồi chặt tại x
∗

Định nghĩa 1.1.14 Giả sử S ⊆ X là tập lồi và f : S −→ R ∪{+∞}.
(i) Hàm f được gọi là tựa lồi tại x
∗
∈ S nếu với mọi x ∈ S sao cho
f(x) ≤ f(x
∗
) và α ∈ [0, 1] ta có
f[αx + (1 − αx
∗
)] ≤ f(x
∗
).
f được gọi là tựa lồi trên S nếu nó tựa lồi tại mọi x ∈ S.
(ii) Hàm f được gọi là tựa lồi chặt (strictly quasiconvex) tại x
∗
∈ S nếu
∀x ∈ S sao cho f(x) < f(x
∗
) và α ∈ (0, 1) ta có,
f[αx + (1 − αx
∗
)] < f(x
∗
).
f được gọi là tựa lồi chặt trên S nếu nó tựa lồi chặt tại mọi x ∈ S.
(iii) Hàm f được gọi là tựa lõm (quasiconcave) tại x
∗
∈ S hoặc trên S nếu
−f là tựa lồi tại x
∗

f(x
n
) = a và ∀ε > 0, ∃δ > 0, x ∈ S ∩ B(x
∗
, δ) =⇒ f(x) > a − ε.
Ở đây B(x
∗
, δ) := {x ∈ X : x −x
∗
 < δ} là hình cầu mở tâm x
∗
, bán
kính δ. Lúc này ta viết
a = lim inf
x→x
∗
f(x).
(iii) Trong (ii) nếu ta thay f(x) > a −ε bởi f(x) < a + ε và tương ứng thay
điểm tụ nhỏ nhất bởi điểm tụ lớn nhất thì a được gọi là giới hạn trên
của f khi x dần đến điểm tụ x
∗
và ta có kí hiệu
a = lim sup
x→x
∗
f(x).
Nhận xét Nếu không tồn tại số thực a hữu hạn thỏa định nghĩa trên thì
ta nói lim inf
x→x
∗

2
) Với mọi dãy {x
n
} ⊂ S và x
n
→ x
∗
, lim
n→∞
f(x
n
) = f(x
∗
).
(ii) Hàm f được gọi là liên tục trên S nếu nó liên tục tại mọi điểm tụ của
S. Hay, hàm f được gọi là liên tục trên S nếu một bất kỳ trong ba
điều tương đương sau đây thỏa:
(β
1
) Với mọi α ∈ R, các tập mức dưới S
α
:= {x ∈ S : f (x) ≤ α} và
mức trên S
α
:= {x ∈ S : f(x) ≥ α} đều là tập đóng tương đối
trong S.
(β
2
) Với mọi α ∈ R, các tập mức sau đây đều là mở tương đối trong
S:

nào đó.
(iii) Hàm f liên tục Lipschitz quanh x
∗
nào đó.
(iv) int(epif)= ∅, ở đây int(·) là phần trong của (·).
(v) int(domf)= ∅ và f liên tục trong int(domf).
Chứng minh:
(ii)⇒ (i) Hiển nhiên.
(i)⇒ (ii) Giả sử f(x) ≤ M < +∞, ∀x ∈ U, với U là lân cận của x
∗
.
Không mất tính tổng quát, giả sử x
∗
= 0, f(x
∗
) = 0 và M > 0, ta sẽ
chứng minh f liên tục. Cho trước ε > 0, ε < M ta sẽ kiểm tra
| f(x) |≤ ε, ∀x ∈ V. (1.2)
Ở đây ta chọn V =
ε
M
U ∩ (−
ε
M
)U. Giả sử x ∈ V bất kỳ. Khi đó
Mx
ε
∈ U và do tính lồi ta có
f(x) ≤
ε

ta được
0 = f(0) ≤
1
1 +
ε
M
f(x) +
ε
M
1 +
ε
M
f(−
M
ε
x) ≤
1
1 +
ε
M
f(x) +
ε
1 +
ε
M
.
Do đó −ε ≤ f(x). Điều này cùng với (1.3) cho ta (1.2).
(i)⇒ (iv) Vì f (x) ≤ M, ∀x ∈ U, ta có
{(x, γ) ∈ S × R : x ∈ U, γ > M} ⊆ epi f
Vì tập ở vế trái là mở nên int(epif) = ∅.

Vì f lồi nên ta có:
f(x) ≤ γf( ˙x) + (1 − γ)f(y).
nên
f(x) − f( ˙x) ≤ (1 −γ)(f(y) − f( ˙x))
≤
x − ˙x
x − ˙x + ε
| f(y) − f( ˙x) | .
≤
x − ˙x
ε
| f(y) − f( ˙x) | .
≤
2l
ε
x − ˙x. (1.4)
(iii)⇒ (ii) Theo định nghĩa. 
1.2 Hàm liên tục trên không gian định chuẩn 14
1.2.3 Hàm nửa liên tục trong không gian định chuẩn
Định nghĩa 1.2.6 Giả sử S ⊆ X, x
∗
∈ S và là điểm tụ của S và f : S −→ R.
(i) Hàm f được gọi là nửa liên tục dưới (lower semi-continuous) tại x
∗
nếu
một bất kỳ trong hai điều tương đương sau thỏa.
(α
1
) ∀ε > 0, ∃δ > 0, x ∈ S ∩ B(x
∗

là mở tương đối trong S.
(β
3
) Trên đồ thị epif là đóng tương đối trong S ×R.
Định nghĩa 1.2.7 Giả sử S ⊆ X, x
∗
∈ S và là điểm tụ của S và f : S → R.
(i) Hàm f được gọi là nửa liên tục trên (upper semi-continuous) tại x
∗
nếu một bất kỳ trong hai điều tương đương sau thỏa.
(α
1
) ∀ε > 0, ∃δ > 0, x ∈ S ∩ B(x
∗
, δ) ⇒ f(x) < f(x
∗
) + ε.
(α
2
) Với mọi dãy {x
n
} ⊂ S, x
n
→ x
∗
ta có lim sup
n→∞
f(x
n
)  f(x

1.3 Tính đơn điệu của ánh xạ 15
Thí dụ 1.2.8 Xét hai hàm số f : R −→ R, g : R −→ R xác định như sau.
(a) Hàm
f(x) =

x nếu x = 2
x
2
nếu x = 2
là nửa liên tục dưới tại x
∗
= 2 và liên tục tại mọi x = 2. Do đó f nửa
liên tục dưới trên R.
(b) Hàm
g(x) =

x nếu x = 2
2x nếu x = 2
là nửa liên tục trên tại x
∗
= 2 và liên tục tại mọi x = 2. Do đó g nửa
liên tục trên trên R.
1.3 Tính đơn điệu của ánh xạ
Giả sử X là không gian định chuẩn, X
∗
là không gian liên hợp, tức là
không gian tất cả các phiếm hàm tuyến tính, liên tục trên X và ánh xạ
F : X −→ X
∗
.

+ λh) −f(x
∗
)) (1.5)
tồn tại thì f

(x
∗
)(h) được gọi là đạo hàm theo hướng của f tại x
∗
theo hướng
h. Nếu với mọi h ∈ X giới hạn f

(x
∗
)(h) đều tồn tại thì f được gọi là khả
vi theo hướng tại x
∗
.
Định lý 1.4.2 Giả sử X là không gian vectơ, S ⊂ X là tập khác trống
và hàm f : S −→ R.
(i) Giả sử x
∗
là điểm cực tiểu của f trên S. Nếu hàm f có đạo hàm theo
hướng tại x
∗
theo mọi hướng x − x
∗
, với x ∈ S thì
f


λ
(f(x
∗
+ λ(x −x
∗
)) −f(x
∗
)).
Theo giả thiết x
∗
là điểm cực tiểu của f trên S, do đó với λ > 0 đủ
nhỏ ta được
f(x
∗
+ λ(x −x
∗
))  f(x
∗
).
Vậy
f

(x
∗
)(x −x
∗
)  0, ∀x ∈ S.
1.4 Đạo hàm 17
(ii) Vì f là hàm lồi nên ∀x ∈ S, ∀λ ∈ [0, 1] ta có
f(x

(x
∗
)(x −x
∗
).
Kết hợp (1.6) ta được
f(x
∗
)  f(x), ∀x ∈ S.
Như vậy x
∗
là điểm cực tiểu của f trên S. 
1.4.2 Đạo hàm Gâteaux và đạo hàm Fréchet
Định nghĩa 1.4.3 Giả sử (X,  · 
X
) và (Y,  · 
Y
) là các không gian định
chuẩn, S ⊂ X là tập mở khác trống và ánh xạ f : S → Y , x
∗
∈ S . Với mọi
h ∈ S nếu giới hạn
f

(x
∗
)(h) := lim
λ→0
1
λ

) : X → Y thỏa
lim
h
X
→0
f(x
∗
+ h) −f(x
∗
) −f

(x
∗
)(h)
Y
h
X
= 0 (1.8)
thì f

(x
∗
) được gọi là đạo hàm Fréchet của f tại x
∗
và ánh xạ f gọi là khả
vi Fréchet tại x
∗
.
Mối liên hệ giữa đạo hàm Fréchet và đạo hàm Gâteaux được thể hiện qua
định lý sau.

Định lý 1.4.7 Giả sử (X, ·) là không gian định chuẩn, S ⊂ X là tập lồi,
mở , khác trống và hàm f : S → R khả vi Fréchet tại mọi điểm x
∗
∈ S . Khi
đó hàm f là lồi khi và chỉ khi với mọi x, y ∈ S
f(y)  f(x) + f

(x)(x −x
∗
). (1.9)
Chứng minh.
(i) Giả sử f là hàm lồi. Khi đó với mọi x, y ∈ S và λ ∈ (0, 1]
f(x + λ(y −x)) = f(λy + (1 − λ)x)  λf(y) + (1 −λ)f(x).
Từ đó ta có
f(y)  f(x) +
1
λ
(f(x + λ(y −x)) − f(x)).
Vì f khả vi Fréchet tại x ∈ S nên
f

(x)(y −x) = lim
λ→0
+
1
λ
(f(x + λ(y −x)) − f(x)).
Do đó với mọi x, y ∈ S
f(y)  f(x) + f


f

(x
∗
)(h) = 0. (1.10)
Hệ thức (1.10) là điều kiện cần để x
∗
là điểm cực tiểu của hàm f. 
Chương 2
Bài toán cân bằng và bất
đẳng thức biến phân
2.1 Phát biểu bài toán
2.1.1 Bài toán cân bằng
Định nghĩa 2.1.1 Giả sử X là không gian định chuẩn, S ⊂ X là tập khác
trống. Hàm f : S ×S → R được gọi là hàm cân bằng (equilibrium function)
nếu
f(x, x) = 0, ∀x ∈ S.
Định nghĩa 2.1.2 Giả sử X là không gian định chuẩn, S ⊂ X là tập khác
trống và f : S × S → R là hàm cân bằng. Khi đó bài toán tìm x
∗
∈ S
sao cho
f(x
∗
, y)  0, ∀y ∈ S. (2.1)
được gọi là bài toán cân bằng (equilibrium problem) viết tắt (EP).
2.2 Hàm Gap của bài toán cân bằng 21
2.1.2 Bất đẳng thức biến phân
Định nghĩa 2.1.3 Giả sử X là tập lồi, đóng, khác trống trong R
n

(ii) x
∗
= arg min
x∈S
sup
y∈S
(−f(x, y)) và min
x∈S
sup
y∈S
(−f(x, y)) = 0;
(iii) x
∗
= arg min
y∈S
f(x
∗
, y).
Định nghĩa 2.2.3 Từ bổ đề trên ta nhận thấy (EP) nhận hàm
g(x) = sup
y∈S
[−f(x, y)] (2.3)
làm hàm gap.
Như vậy việc giải (EP) tương đương tìm cực tiểu hàm gap trên S.
2.2 Hàm Gap của bài toán cân bằng 22
Mệnh đề 2.2.4 Giả sử
(i) ∀x ∈ S, f(x, ·) là hàm lồi chặt trên S;
(ii) ∀y ∈ S, f(·, y) là khả vi và f
x
liên tục trên S × S;

luôn thỏa. Chẳng hạn, trường hợp bài toán (VI), f(x, y) = F(x), y −x là
tuyến tính và không thỏa tính lồi chặt. Để tránh giả thiết về tính lồi chặt,
Fukushima[3, 18 ] và Zhu-Marcotte[20, 21] đã chính quy hóa bài toán (VI)
bằng việc thêm hàm H và sử dụng hàm gap (2.3) cho bài toán chính quy.
Định nghĩa 2.2.6 Giả sử S ⊆ X. Hàm p : X → R được gọi là hàm
gap cho bài toán (VI) nếu và chỉ nếu
(i) p(x)  0, ∀x ∈ S.
(ii) p(x) = 0 và x ∈ S khi và chỉ khi x là nghiệm của (VI).
2.3 Bài toán cân bằng bổ trợ 23
2.3 Bài toán cân bằng bổ trợ
Bài toán bổ trợ đã được Cohen[2] sử dụng trong việc giải quyết các bài toán
tối ưu. Sau đó Mastroeni G[17] cũng sử dụng nó vào bài toán cân bằng. Ý
tưởng của việc áp dụng là cộng thêm hàm chính quy vào bài toán gốc mà
không làm thay đổi nghiệm của bài toán ban đầu song việc giải bài toán mới
này lại thuận tiện hơn.
Định nghĩa 2.3.1 Giả sử H : R
n
× R
n
→ R thỏa các điều kiện sau:
(H1) H khả vi liên tục;
(H2) H(x, y)  0 và H(x, y) = 0 khi và chỉ khi x = y;
(H3) ∀x ∈ R
n
, H(x, ·) là lồi mạnh với modulus λ;
(H4) ∀x, y ∈ R
n
, H
x
(x, y) + H

Chứng minh.
"khi". Theo (H2), H(x, ·) đạt cực tiểu tại y = x. Vì (H3) và (H1) thỏa
nên,∀z ∈ R
n
, ta có
H
y
(x, x), z −x ≥ 0 (2.5)
Chọn t = 2x −z ∈ R
n
ta thấy H
y
(x, x), z −x ≤ 0. Kết hợp (2.5) ta được
H
y
(x, x), z −x = 0, ∀z ∈ R
n
. Vì vậy H
y
(x, x) = 0.
"Chỉ khi". Từ (H1) và (H3) ta được:
H(x, x) −H(x, y) ≥ H
y
(x, y), x − y + λx − y
2
. (2.6)
Giả sử H
y
(x, y) = 0. Vì H(x, x) = 0, (2.6)
−H(x, y) ≥ λx −y

∗
, x
∗
) + αH
y
(x
∗
, x
∗
), y −x
∗
 ≥ 0.
Theo mệnh đề 2.4.1, H
y
(x
∗
, x
∗
) = 0 và do đó, ∀y ∈ S,
f
y
(x
∗
, x
∗
), y −x
∗
 ≥ 0,
Dựa vào tính lồi của hàm f(x
∗