ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC

LÂM THỊ THOA

PHƯƠNG PHÁP CHIẾU GIẢI 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

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

Thái Nguyên - 2015


ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC

LÂM THỊ THOA

PHƯƠNG PHÁP CHIẾU GIẢI 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

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

60 46 01 12

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

NGƯỜI HƯỚNG DẪN KHOA HỌC

4

1.1

Tập lồi, hàm lồi, nón pháp tuyến và phép chiếu . . . . . . .

4

1.1.1

Tập lồi và hàm lồi

. . . . . . . . . . . . . . . . . .

4

1.1.2

Nón pháp tuyến . . . . . . . . . . . . . . . . . . . .

7

1.1.3

Phép chiếu . . . . . . . . . . . . . . . . . . . . . .

8

1.2


Phát biểu bài toán . . . . . . . . . . . . . . . . . . .

17

1.4.2

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

17

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

19


ii
2

Phương pháp chiếu giải 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

20

2.1

Phương pháp chiếu giải bài toán bất đẳng thức biến phân . .

21

2.2

Lời cảm ơn
Luận văn được hoàn thiện tại Đại học Khoa học - Đại học Thái Nguyên.
Tác giả xin bày tỏ lòng biết ơn sâu sắc tới PGS.TS. Phạm Ngọc Anh (Học
viện Bưu chính Viễn thông) đã trực tiếp hướng dẫn tận tình và động viên tác
giả trong suốt thời gian nghiên cứu và viết luận văn.
Trong quá trình học tập và nghiên cứu, thông qua các bài giảng, các buổi
hội thảo seninar, tác giả luôn nhận được sự quan tâm giúp đỡ cũng như những
ý kiến đóng góp quý báu của các thầy cô Trường Đại học Khoa học Thái
Nguyên, Học viện Bưu chính Viễn thông, các bạn học viên lớp cao học toán
K7Y. Tác giả xin chân thành cảm ơn!
Xin gửi tới lời cảm ơn sâu sắc tới Ban Lãnh đạo Trường Đại học Hải
Dương, các đồng nghiệp trong khoa Toán Kinh tế - Kỹ thuật đã luôn bên cạnh
động viên, tạo điều kiện thuận lợi cho tác giả học tập và nghiên cứu.
Tác giả cũng xin bày tỏ lòng biết ơn sâu sắc tới gia đình và người thân,
những người đã luôn khuyến khích và động viên tác giả trong suốt quá trình
nghiên cứu và làm luận văn.
Mặc dù đã có nhiều cố gắng nhưng luận văn khó tránh khỏi thiếu sót và
hạn chế, tác giả mong nhận được những ý kiến đóng góp quý báu của thầy cô
và bạn đọc để luận văn được hoàn thiện hơn.
Thái Nguyên, 2015

Lâm Thị Thoa
Học viên Cao học Toán K7D,
Trường ĐH Khoa học - ĐH Thái Nguyên


iv

Danh sách ký hiệu
không gian Hilbert thực

I

ánh xạ đồng nhất

domf

miền hữu dụng của f

epif

tập trên đồ thị hàm f

argmin{f (x) : x ∈ C}

tập các điểm cực tiểu của hàm f

∂f (x)

dưới vi phân của hàm lồi f tại x

δC

hàm chỉ trên C

NC (x)

nón pháp tuyến của điểm x trên tập C

dC (x)


Sol(f, C)

tập nghiệm bài toán cân bằng

V I(F, C)

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

Sol(F, C)

tập nghiệm bài toán bất dẳng thức biến phân

F ix

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

F ix(S)

tập điểm bất động của ánh xạ S


1

Mở đầu
Bài toán bất đẳng thức biến phân cổ điển là bài toán tìm một điểm x∗ ∈ C
sao cho
F x∗ , x − x∗ ≥ 0 ∀x ∈ C,
trong đó, C là một tập con, lồi, đóng, khác rỗng của một không gian Hilbert
thực H và một ánh xạ F : H → H, thường được goi là ánh xạ giá. Bài toán
này, kí hiệu bởi V I(F, C), là một bài toán cơ bản trong lí thuyết tối ưu. Bởi

Hiên - Vương - Strodiot trong bài báo "On extragradient - viscosity methods
for solving equilibrium and fixed point problems in a Hilbert space", Phan
Tu Vuong, Jean Jacques Strodiot and Van Hien Nguyen, Vol. 64, No. 2, pp.
429-451, Optimization, 2015.
Luận văn gồm hai chương:
Chương 1: Kiến thức chuẩn bị
Nội dung gồm các kiến thức cơ bản về tập lồi, hàm lồi, nón pháp tuyến và
phép chiếu trên một không gian Hilbert thực. Nhắc lại một số định nghĩa mở
rộng về tính đơn điệu của một ánh xạ F và một song hàm f . Phát biểu bài
toán và trình bày một số kết quả về sự tồn tại, tính duy nhất nghiệm của bài
toán bất đẳng thức biến phân, bài toán cân bằng.
Chương 2: Ứng dụng giải bài toán bất đẳng thức biến phân trên tập nghiệm
bài toán cân bằng.
Nội dung chương 2 trình bày phương pháp chiếu hai lần để giải bài toán
bất đẳng thức biến phân và bài toán cân bằng trong một không gian Hilbert


3
thực. Đặc biệt là ứng dụng phương pháp chiếu để giải 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.

Thái Nguyên, ngày 20 tháng 11 năm 2015
Lâm Thị Thoa
Email:


4

Chương 1


(iii) Hàm f được gọi là lồi mạnh trên C với hệ số β > 0, nếu
1
f (λx + (1 − λ)y) < λf (x) + (1 − λ)f (y) − βλ(1 − λ) x − y 2 , ∀x, y ∈ C,
2
∀λ ∈ (0, 1).
(iv) Hàm f được gọi là tựa lồi trên C, nếu
f (λx + (1 − λ)y) ≤ max{f (x), f (y)}, ∀x, y ∈ C, λ ∈ [0, 1].
(v) Hàm f được gọi hàm lõm trên C, nếu −f là hàm lồi trên C.
Ví dụ 1.1.1. Với mọi x ∈ H, hàm f xác định bởi f (x) =
là hàm lồi mạnh với hệ số β =

1
2

1
2

x 2 . Khi đó, f

trên H.

Giải. Với mọi x, y ∈ H, λ ∈ [0, 1], ta có
λf (x)+(1 − λ)f (y) − f (λx + (1 − λ)y) =
x
=λ

+ (1 − λ)

2
x

2
2

−λ

x
2

2

− λ(1 − λ) x, y

2

2


6
λ(1 − λ)
=
( x
2
λ(1 − λ)
=

2

2

+ y

Định nghĩa 1.1.2. Cho C là một tập con lồi, đóng, khác rỗng của H và một
ánh xạ F : C → R. Ánh xạ F được gọi là
a) nửa liên tục dưới tại x ∈ C nếu với mọi dãy {xk } ⊂ C hội tụ mạnh đến
x thì
lim inf F (xk ) ≥ F (x);
k→∞

b) nửa liên tục trên tại x ∈ C nếu với mọi dãy {xk } ⊂ C hội tụ mạnh đến
x thì
lim sup F (xk ) ≥ F (x);
k→∞

Ta nói F là nửa liên tục dưới (nửa liên tục trên) trên C nếu F nửa liên tục
dưới (nửa liên tục trên) tại mọi x ∈ C.

Ví dụ 1.1.2. Xét hàm một biến trên tập X = (−∞, 1]

 x2 nếu x < 1
f (x) =
 2 nếu x = 1
Dễ thấy epif ⊂ H là tập lồi. Do đó, f là hàm lồi trên X. Hàm f là liên tục
trên (−∞, 1). Tại x = 1, hàm f là nửa liên tục trên.


7
Định nghĩa 1.1.3. Cho C là một tập con, lồi và khác rỗng của H và hàm
f : C → R ∪ {+∞}. Một véctơ p ∈ C được gọi là dưới đạo hàm của hàm f
tại x0 ∈ C, nếu
p, x − x0 ≤ f (x) − f (x0 ), ∀x ∈ C.
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

= {w ∈ H : w, x − x0 ≤ δC (x), ∀x ∈ C}
= {w : w, x − x0 ≤ 0, ∀x ∈ C}
= NC (x0 ).
Nếu x ∈
/ C thì δC (x) = +∞ nên bất đẳng thức này luôn đúng. Vậy, dưới vi
phân của hàm chỉ của một tập lồi C khác ∅ tại một điểm x0 ∈ C chính là
nón pháp tuyến ngoài của C tại x0 .

1.1.3

Phép chiếu
Cho C là một tập con, lồi, đóng, khác rỗng của H. Phép chiếu metric

hay còn gọi là phép chiếu trực giao của một điểm x ∈ H lên C, kí hiệu
P rC (x), được xác dịnh bởi
P rC (x) = argmin{ x − y : y ∈ C}.
Theo định nghĩa, hình chiếu vuông góc P rC (x) của x trên C là nghiệm
của bài toán quy hoạch toàn phương lồi mạnh, có dạng:


1

2
min
x−y :y ∈C .
2

Ví dụ 1.1.4. Cho C = {(x1 , x2 ) ∈ R2 : x21 + x22 ≤ 1, x1 ≥ 0, x2 ≥ 0}. Hãy
xác định phép chiếu P rC (x) với mọi x ∈ R2 .
Giải.







{x}

với x ∈ C

{(min{1, x1 }, 0)}

với x1 ≥ 0, x2 < 0

{(0, min{1, x2 })}

với x1 ≤ 0, x2 > 0

{(0, 0)}


x1

,

x21 + x22

với x1 ≤ 0, x2 ≤ 0



ii) x − P rC (x), y − P rC (x) ≤ 0, ∀x ∈ H, y ∈ C;
iii) P rC (x) − P rC (y) ≤ x − y , ∀x, y ∈ H;
iv) P rC (x) − P rC (y)
v) P rC (x)−P rC (y)
vi) P rC (x) − y

1.2

2

2

2

≤ P rC (x) − P rC (y), x − y , ∀x, y ∈ H;

≤ x−y 2 − P rC (x)−x+y−P rC (y) 2 , ∀x, y ∈ H;

≤ x−y

2

− P rC (x) − x 2 , ∀x ∈ H, y ∈ C.

Hàm đơn điệu
Để thấy được tính đơn điệu suy rộng của bài toán cân bằng và bài toán

bất đẳng thức biến phân, trong mục này ta sẽ nhắc lại định nghĩa của ánh xạ
đơn điệu F trong bài toán bất đẳng thức biến phân V I(F, C) và song hàm
đơn điệu của bài toán cân bằng EP (f, C).

trên C và F không đơn điệu trên C.

Giải. Giả sử F (x), y − x ≥ 0. Từ x ∈ C hay x

≤ α < β suy ra

x, y − x ≥ 0. Khi đó, ta có
F (y), y − x = (β − y ) y, y − x
≥ (β − y )( y, y − x − x, y − x )
≥ (β − α) y − x

2

= γ y − x 2.
Như vậy, F là giả đơn điệu mạnh với hằng số γ > 0 trên C. Nhưng F lại
không đơn điệu mạnh, thậm chí F không đơn điệu trên C. Thật vậy, chọn hai


12
phần tử trong C là x =

β
2 , 0, 0, . . . , 0

∈ C và y = (α, 0, 0, . . . , 0). Khi đó,

ta có


3


+ β x − Sx 2 , ∀(x, x∗ ) ∈ C × F ix(S).

Định nghĩa 1.2.2. Cho S : C → C là một ánh xạ không giãn. Một điểm
x ∈ C được gọi là điểm bất động của ánh xạ S, nếu Sx = x. Kí hiệu F ix(S)
là tập các điểm bất động của S
Định lí 1.2.1. Giả sử tồn tại β ∈ [0, 1) sao cho ánh xạ S : H → H là β−
giả co chặt và nửa đóng tại 0. Nếu S là giả co chặt thì tập điểm bất động tại
F ix(S) là tập đóng và lồi.
Ta nhắc lại một vài định nghĩa về tính đơn điệu của một song hàm f cho
bài toán cân bằng.


13
Định nghĩa 1.2.3. Song hàm f : C × C → R còn được gọi là
i) γ− đơn điệu mạnh trên C, nếu tồn tại hằng số γ > 0 sao cho
f (x, y) + f (y, x) ≤ −γ x − y 2 , ∀x, y ∈ C;
ii) đơn điệu chặt trên C, nếu bất kì x, y ∈ C và x = y sao cho
f (x, y) + f (y, x) < 0;
iii) đơn điệu trên C, nếu
f (x, y) + f (y, x) ≤ 0, ∀x, y ∈ C;
iv) tựa đơn điệu mạnh trên C, nếu
f (x, y) > 0 ⇒ f (y, x) ≤ 0, ∀x, y ∈ C;
v) giả đơn điệu trên C, nếu
f (x, y) ≥ 0 ⇒ f (y, x) ≤ 0, ∀x, y ∈ C;
vi) giả đơn điệu chặt trên C, nếu bất kì x, y ∈ C và x = y
f (x, y) ≥ 0 ⇒ f (y, x) < 0;
vii) liên tục kiểu Lipschitz trên C với hằng số c1 > 0 và c2 > 0, nếu
f (x, y) + f (y, z) ≥ f (x, z) − c1 x − y


β
2

∈ C2 vào bất đẳng thức trên, ta nhận được

β
− ≤ −β. Điều này là mâu thuẫn. Như vậy, f không đơn điệu mạnh trên C2 .
2
Ví dụ 1.2.3. Xét song hàm f : R × R → R xác định bởi

 x(y − x) nếu x, y ∈ [0, +∞)
f (x, y) =
0
nếu x, y ∈
/ [0, +∞) hoặc y ∈
/ [0, +∞).
Khi đó, f đơn điệu trên C := R. Nhưng, f không đơn điệu chặt trên C.


15
Giải. Để chứng minh f là đơn điệu trên C, ta xét các trường hợp sau:
Trường hợp 1: Với x, y ∈ [0, +∞), ta có f (x, y) + f (y, x) = 0 ≤ 0.
Trường hợp 2: Với x ∈
/ [0, +∞) hoặc y ∈
/ [0, +∞), ta có f (x, y) + f (y, x) =
−(x − y)2 ≤ 0. Như vậy, f là đơn điệu trên C.
Mặt khác, f là không đơn điệu chặt trên C. Vì với mọi x = 0 và x, y ∈
[0, +∞), f (x, y) + f (y, x) = 0.
Ví dụ 1.2.4. Xét song hàm f : R × R → R xác định bởi
f (x, y) = x2 (y − x).


1.3.2

Sự tồn tại nghiệm của bài toán bất đẳng thức biến phân
Sự tồn tại nghiệm của bài toán V I(F, C) được thể hiện trong các định

lý sau:
Định lí 1.3.1. Cho C là một tập con lồi, compact và khác rỗng của một không
gian Hilbert thực H và một ánh xạ liên tục F : C → H. Khi đó, bài toán bất
đẳng thức biến phân V I(F, C) có nghiệm.
Định lí 1.3.2. Cho C là một tập con lồi, đóng và khác rỗng của một không
gian Hilbert thực H và một ánh xạ liên tục F : C → H. Khi đó, bài toán bất
đẳng thức biến phân V I(F, C) có nghiệm khi và chỉ khi tồn tại R > 0 sao
cho bài toán bất đẳng thức biến phân V I(F, C ∩ B(0, R)) có một nghiệm xR
thỏa mãn xR < R.
Hệ quả 1.3.1. Cho C là một tập lồi, đóng và khác rỗng của một không gian
H và một ánh xạ liên tục F : C → H thỏa mãn điều kiện bức hay tồn tại
x0 ∈ C sao cho
F (x) − F (x0 ), x − x0
x − x0

→ +∞ khi x → +∞, x ∈ C.

Khi đó, bài toán bất đẳng thức biến phân V I(F, C) có nghiệm.


17

1.4


Định lí 1.4.1. Cho C là một tập lồi, đóng khác rỗng của H và song hàm cân
bằng f : C × C → R có các tính chất: f (x, .) là hàm tựa lồi nửa liên tục


18
dưới trên C, ∀x ∈ C; f (., y) là hàm tựa lõm, nửa liên tục trên trên C. Giả sử
một trong hai điều kiện dưới đây đúng
i) Tồn tại một tập hữu hạn N ⊆ C sao cho tập
C N :=

x ∈ C| min f (x, y) ≥ 0
y∈N

là compact.
ii) Tồn tại một tập hữu hạn M ⊆ C sao cho tập
DM :=

x ∈ C| max f (x, y) ≤ 0
x∈M

là compact.
Khi đó, bài toán EP (f, C) có nghiệm.
Hệ quả 1.4.1. Cho C là một tập con, lồi, đóng, khác rỗng của H và f :
C × C → R ∪ {+∞} là một song hàm sao cho f (., y) là nửa liên tục trên
với mỗi y ∈ C và f (x, .) là hàm tựa lồi x ∈ C. Giả sử rằng ít nhất một trong
các giả thiết sau được thỏa mãn:
i) C là tập compact,
ii) Điều kiện bức: Tồn tại một tập con compact, khác rỗng W của C sao
cho với mọi x ∈ C\W , tồn tại y ∈ W để f (x, y) < 0.
Khi đó, bài toán cân bằng EP (f, C) sẽ có nghiệm.