TRƯỜNG ĐẠI HỌC HẢI PHÒNG
KHOA TOÁN

Phạm Thị Thanh Hà

PHƯƠNG PHÁP ĐẠO HÀM TĂNG CƯỜNG
MỞ RỘNG TÌM NGHIỆM CHUNG CỦA BÀI TOÁN
CÂN BẰNG VÀ BÀI TOÁN ĐIỂM BẤT ĐỘNG CỦA
ÁNH XẠ KHÔNG GIÃN

ĐỀ TÀI NGHIÊN CỨU KHOA HỌC

Người hướng dẫn khoa học:
TS. Đỗ Duy Thành

Hải Phòng - 2016


MỤC LỤC

Mục lục

1

Danh mục các ký hiệu và chữ viết tắt

2

Mở đầu

4


Dưới vi phân hàm lồi . . . . . . . . . . . . . . . . . . . . .

13

1.3

Phép chiếu và các tính chất . . . . . . . . . . . . . . . . . . . . .

15

1.4

Ánh xạ không giãn và các định lý điểm bất động . . . . . . . . .

15

1.5

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

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

16

1.5.1

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

16


2.3

Kết quả tính toán . . . . . . . . . . . . . . . . . . . . . . . . . . .

27

Kết luận

30
1


DANH MỤC CÁC KÝ HIỆU VÀ CHỮ
VIẾT TẮT
N

tập số tự nhiên

R

tập số thực

Rn

không gian Euclide thực n-chiều

H

không gian Hilbert thực


tập hợp A hợp với tập hợp B

A×B

tích Đề-Các của hai tập hợp A và B

argmin{f (x) : x ∈ C} tập các điểm cực tiểu của hàm f trên C
∂f (x)

dưới vi phân của f tại x

δC (·)

hàm chỉ trên C

P rC (x)

hình chiếu của x lên tập C

NC (x)

nón pháp tuyến ngoài của C tại x

xn → x

dãy {xn } hội tụ mạnh tới x

xn


này là sự khái quát hóa nhiều bài toán quen thuộc như bài toán tối ưu, bài toán
bất đẳng thức biến phân, bài toán điểm bất động, bài toán điểm cân bằng Nash,
bài toán điểm yên ngựa,...Tuy nhiên, Ky Fan [12] là người công bố kết quả đầu
tiên về sự tồn tại nghiệm của bài toán cân bằng. Từ đó đến nay đã có nhiều dạng
mở rộng đơn trị lẫn đa trị của kết quả này.
Một vấn đề được quan tâm trong 20 năm trở lại đây là xây dựng thuật toán
xấp xỉ nghiệm của bài toán cân bằng. Những công trình khai phá của W.Oettli
[7], A.Moudafi [19], I.V. Konnov [17], P.L. Combettes và S.A. Hirstoaga [11],...
đã tạo ra sự phát triển mạnh mẽ cả về số lượng và chất lượng của các nghiên cứu
về thuật toán xấp xỉ điểm cân bằng, trong đó phải kể đến các kết quả nghiên cứu
của một số tác giả người Việt Nam như L.D. Muu [21], P.K. Anh ([1, 2]), P.N.
Anh ([3, 5]),...
Một vấn đề cũng được quan tâm khá nhiều hiện nay là bài toán tìm điểm
chung của tập nghiệm của bài toán cân bằng và tập các điểm bất động của các
ánh xạ không giãn. Hầu hết các thuật toán để giải bài toán này đều dựa trên
tính về ánh xạ nghiệm được đề xuất bởi P.L. Combettes và S.A. Hirstoaga
Tr (x) =

z ∈ C : f (z, y) +

1
y − z, z − x ≥ 0, ∀y ∈ C ,
r

trong đó r > 0, song hàm f đơn điệu trên C, và x ∈ H. Khi đó, ta có
(i) Tr đơn trị;
(ii) F ix(Tr ) = Sol(C, f ).
4



y − uk , uk − xk ≥ 0, ∀y ∈ C,

rk




xk+1 = αk g(xk ) + (1 − αk )Suk , ∀k ≥ 0,

(1)

trong đó g : C → C là một ánh xạ co. Với các điều kiện cho trước của dãy các
tham số {αk } và {rk },
∞

∞

(i) αk ∈ [0, 1], lim αk = 0,
k→∞

αk = ∞,
k=1

|αk+1 − αk | < ∞;
k=1

∞

(ii) rk ∈ (0, ∞), lim inf rk > 0,
k→∞

Ck = z ∈ H : w k − z ≤ x k − z ,





Dk = z ∈ H : xk − z, x − xk ≥ 0 ,






xk+1 = P rC ∩D (x),
k
k

trong đó {αk } ⊂ [a, 1] với a ∈ (0, 1) và {rk } ⊂ (0, ∞) thỏa mãn lim inf rk > 0.
k→∞

Khi đó, dãy {xk } hội tụ mạnh tới P rF ix(S)∩Sol(C,f ) (x).
Phương pháp đạo hàm tăng cường lần đầu tiên được G.M. Korpelevich [18]
đề xuất để giải bài toán tìm điểm yên ngựa sau đó được phát triển cho bài toán
bất đẳng thức biến phân. Phương pháp này sử dụng hai phép chiếu trong mỗi
bước lặp như sau:
x0 ∈ C, y k = P rC (xk − λk F (xk )) và xk+1 = P rC (xk − λk F (y k )).

(2)

Tiếp cận này cho phép giải bài toán bài toán bất đẳng thức biến phân V I(C, F )

với tập các điểm bất động của ánh xạ không giãn và thu được sự hội tụ yếu của
6


thuật toán. Xuất phát từ một điểm tùy ý x0 ∈ C, dãy lặp được định nghĩa như
sau:





y k = argmin λk f (xk , y) + 12 y − xk 2 : y ∈ C ,



tk = argmin λk f (y k , t) + 21 t − xk 2 : t ∈ C ,





xk+1 = αk x0 + (1 − αk )Sxk .

(3)

Dưới các điều kiện của tham số {λk } và {αk }, tác giả đã chứng minh các dãy
{xk }, {y k } và {tk } hội tụ yếu tới x ∈ F ix(S) ∩ Sol(C, f ) trong không gian Hilbert
thực.
Trên cơ sở tận dụng, kế thừa tối đa những kết quả nghiên cứu đã có trong
nước và trên thế giới về các phương pháp tìm điểm chung của tập nghiệm bài



Chương 1

Kiến thức cơ sở
1.1

Sự hội tụ mạnh và yếu trong không gian Hilbert
thực

Các khái niệm hội tụ mạnh và yếu là những khái niệm rất cơ bản trong không
gian Hilbert. Nó là cơ sở để xây dựng và chứng minh các định lý hội tụ của các
thuật toán sau này.
Định nghĩa 1.1. Dãy {xk } trong không gian Hilbert H gọi là hội tụ mạnh đến
x ∈ H nếu:
lim xk − x = 0.

k→∞

Ta ký hiệu: xk → x.
Định nghĩa 1.2. Dãy {xk } trong không gian Hilbert H gọi là hội tụ yếu đến
x ∈ H nếu:
lim xk , y = x, y ,

k→∞

Ta ký hiệu: xk

∀y ∈ H.


T : C → H, được gọi là nửa đóng (demiclosed) tại điểm p, nếu dãy xk ⊂ C, sao
cho xk

1.2
1.2.1

x và {T (xk )} → p, thì T (x) = p;

Hàm lồi và dưới vi phân hàm lồi
Tập lồi

Định nghĩa 1.4. Cho C là một tập con khác rỗng của một không gian Hilbert
thực H. C được gọi là tập lồi nếu với ∀x, y ∈ C và λ ∈ [0, 1], ta có
λx + (1 − λ)y ∈ C.
Định nghĩa 1.5. Tập con C trong không gian Hilbert H được gọi là nón nếu
λx ∈ C, ∀x ∈ C, λ > 0.
Tập con C trong không gian Hilbert H được gọi là nón lồi nếu nó vừa là nón vừa
là tập lồi, tức là
λx + µy ∈ C, ∀x, y ∈ C, λ, µ > 0.
Tập Rn+ là nón lồi trong Rn .

10


Định nghĩa 1.6. Cho không gian Hilbert thực H, C ⊆ H là một tập lồi và
x ∈ C, nón pháp tuyến ngoài của C tại x0 (hay còn gọi là nón lồi đóng), kí hiệu
là NC (x0 ) và được xác định bởi công thức
NC (x0 ) := {p ∈ H : p, x − x0 ≤ 0, ∀x ∈ C}.

1.2.2

⇔ λx2 + µy 2 ≥ λ2 x2 + µ2 y 2 + 2λµxy
⇔ λx2 + µy 2 ≥ (λx + µy)2
⇔ λf (x) + µf (y) ≥ f (λx + µy).
Định nghĩa 1.8. Cho không gian Hilbert H, C ⊆ H. Hàm f : C → R ∪ {+∞}
được gọi là lồi chặt trên C, nếu với ∀x, y ∈ C, x = y; λ ∈ (0, 1), ta có
f (λx + (1 − λ)y) < λf (x) + (1 − λ)f (y).
Chú ý. Hàm lồi chặt là hàm lồi, nhưng điều ngược lại không đúng.
Ví dụ 1.2. Trong không gian Rn , xét hàm f (x) = x . Dễ thấy f(x) là hàm lồi.
Nếu trên Rn \{0} thì f (x) không lồi chặt.
Thật vậy, lấy x ∈ Rn \{0} và λ ∈ (0, 1), ta có
λx + (1 − λ)0 = λ x + (1 − λ) 0 .
Vậy f (x) = x không lồi chặt.
Định nghĩa 1.9. Cho không gian Hilbert H, C ⊆ H. Hàm f được gọi là lồi mạnh
trên C, nếu với ∀x, y ∈ C; λ ∈ (0, 1), ∃β > 0 sao cho
f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y) − λ(1 − λ)β x − y 2 .
Khi đó, β được gọi là hằng số lồi mạnh của f .
Ví dụ 1.3. Cho không gian Hilbert thực H. Với x ∈ H xét hàm f (x) =
ta thấy: Với ∀x, y ∈ C; λ ∈ (0, 1), ta có
λf (x) + (1 − λ)f (y) − f (λx + (1 − λ)y)
x
=λ
2

2

y
+ (1 − λ)
2

2

2
2
=λ

Vậy, hàm f (x) =

x
2

2

lồi mạnh với hệ số β = 1.

Định lý 1.3. (Định lý Moreau Rockafeller) Cho các hàm lồi chính thường f1 , f2 , ..., fm
trên Rn . Khi đó, với mọi x ∈ Rn
∂(f1 + f2 + ... + fm )(x) ⊇ ∂f1 (x) + ∂f2 (x) + ... + ∂fm (x).
Hơn nữa, nếu các hàm f1 (x), f2 (x), ..., fm (x) (có thể trừ một hàm) liên tục tại
một điểm x¯ ∈ ∩m
i=1 domfi , thì:
∂(f1 + f2 + ... + fm )(x) = ∂f1 (x) + ∂f2 (x) + ... + ∂fm (x).

1.2.3

Dưới vi phân hàm lồi

Định nghĩa 1.10. Cho không gian Hilbert H, C ⊆ H và hàm chính thường
f : C → R ∪ {+∞}. Một vectơ p ∈ C được gọi là dưới gradient của f tại x0 ∈ C
nếu
p, x − x0 + f (x0 ) ≤ f (x), ∀x ∈ C.
Tập tất cả các dưới gradient của f tại x0 được gọi là dưới vi phân của f tại x0 ,

Định lý 1.4. Cho C là một tập con lồi, đóng, khác rỗng trong không gian Hilbert
H và f : C → R là một khả dưới vi phân trên C. Điều kiện cần và đủ để điểm
x∗ ∈ C là cực tiểu của f trên C là
0 ∈ ∂f (x∗ ) + NC (x∗ ).
Trong đó ∂f (x∗ ) là kí hiệu dưới vi phân của hàm f tại x∗ , NC (x∗ ) là kí hiệu của
nón pháp tuyến ngoài của C tại x∗ .
Định nghĩa 1.11. Cho hàm số f xác định trên một tập mở C ⊂ R.
i) Hàm f được gọi là liên tục tại điểm x0 ∈ C nếu với ∀ > 0, ∃δ > 0 sao cho
f (x) − f (x0 )
0, ∃δ > 0 sao cho
f (x) ≥ f (x0 ) − (f (x) ≤ f (x0 ) + )
với ∀x ∈ C thỏa mãn x − x0 < δ. Nói cách khác, hàm f là nửa liên tục
dưới, (nửa liên tục trên) tại điểm x0 ∈ C nếu với mọi dãy {xk } ⊂ C hội tụ
đến x0 ∈ C và dãy {f (xk )} ⊂ R hội tụ, ta có
lim f (xk ) ≥ f (x0 ) ( lim f (xk ) ≤ f (x0 )).
k→∞

k→∞

14


1.3


≤ x−y

2

2

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

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

Ánh xạ không giãn và các định lý điểm bất
động

Định nghĩa 1.13. Cho C là một tập con lồi, đóng, khác rỗng của H. Ánh xạ
S : C → C được gọi là ánh xạ không giãn, nếu:
S(x) − S(y) ≤ x − y , ∀x, y ∈ C.
Định nghĩa 1.14. 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 S(x) = x. Kí hiệu F ix(S) là tập các
điểm bất động của S.
Định lý 1.5 ([9], [14], Browder-Gohde). Cho X là một không gian Banach lồi
đều, C là một tập con lồi, đóng, bị chặn của X. Khi đó, mọi ánh xạ không giãn
15


S : C → C có điểm bất động trong C và tập hợp các điểm bất động của S là lồi,
đóng và khác rỗng.
Hệ quả 1.1. Cho C là một tập con lồi, đóng, bị chặn của H. Khi đó mọi ánh
xạ không giãn S : C → C có điểm bất động trong C.
Định lý 1.6 ([16], Kirk). Cho X là một không gian Banach và C là một tập con
lồi, compact yếu, có cấu trúc chuẩn tắc trong X. Khi đó, mọi ánh xạ không giãn

(f ) tựa đơn điệu (quasimonotone) trên C, nếu
f (x, y) > 0 suy ra f (y, x) ≤ 0, ∀x, y ∈ C;
(g) liên tục kiểu Lipschitz (Lipschitz-type continuous) 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

1.5.2

2

− c2 y − z 2 , ∀x, y, z ∈ C.

Ví dụ thực tế

Ví dụ 1.5. (Bài toán cân bằng Nash)
i) Cho I = 1, 2, ...p, là tập chỉ số hữu hạn (tập p - người chơi).
ii) Ki là một tập lồi khác rỗng của Rni (tập các chiến lược của người chơi thứ
i)
iii) Cho trước hàm fi : K1 × K2 × ... × Kp → R (ta gọi là hàm tổn thất của
người chơi thứ i khi vi phạm chiến lược của người chơi với mọi i ∈ I).
Cho x = (x1 , x2 , ..., xp ), y = y1 , y2 , ..., yp ) ∈ K1 × K2 × ... × Kp . Ta định nghĩa
vecto x[yi ] ∈ K1 × K2 × ... × Kp như sau:


xj
∀j = i,
x[yi ] =

yi
∀j = i.

Theo cách đặt, ta có f (x∗ , y) ≤ 0, ∀yi ∈ Ki . Vậy x∗ ∈ K là nghiệm của (EP ).
Ngược lại, giả sử x∗ ∈ K là nghiệm của (EP ) nhưng lại không phải là nghiệm
của bài toán cân bằng Nash. Khi đó, ta có
f (x∗ , y) ≤ 0, ∀y ∈ K.
Theo cách đặt đó, ta có
p

(fi (x∗ [yi ]) − fi (x∗ )) ≤ 0, ∀y ∈ K.
i=1

Vì x∗ ∈ K không phải nghiệm của bài toán cân bằng Nash, nên ∃i0 ∈ I sao cho
fi0 (x∗ ) > fi0 (x∗ [yi ]),
18

∀j = i0 .


Lấy x∗ [yi ] = x∗ , ∀j = i0 , ta có
fi0 (x∗ ) = fi0 (x∗ [yi ]),

∀j = i0 .

Kết hợp 2 điều kiện trên, ta suy ra
p

(fi (x∗ [yi ]) − f (x∗ ) < 0,

∀y ∈ K

i=1


Xây dựng dãy lặp

Trong thời gian gần đây, các thuật toán lặp để tìm điểm chung của tập
nghiệm bài toán cân bằng và tập điểm bất động của ánh xạ không giãn trong
không gian Hilbert thực đã được nghiên cứu và mở rộng bởi nhiều tác giả (xem
[4, 5, 6, 10, 15, 22, 24, 25, 26, 28]). Trong [22], S. Sun đã giới thiệu phương pháp
chính quy thay phiên (the alternative regularization method). Dãy lặp được xây
dựng như sau:



x0 , u ∈ C,




1
f (uk , y) +
y − uk , uk − xk ≥ 0, ∀y ∈ C,

rk




xk+1 = βk g(xk ) + (1 − βk )S(αk u + (1 − αk )uk ), ∀k ≥ 0,

(2.1)



(iii) lim

20


∞

(iv) rk ∈ (0, ∞), lim inf rk > 0,
k→∞

|rn+1 − rk | < ∞.
k=1

thì các dãy {xk } và {uk } hội tụ mạnh tới z = P rF ix(S)∩Sol(C,f ) g(z). Tuy nhiên,
trong các thuật toán trên tại mỗi bước lặp thứ k đòi hỏi phải giải bài toán cân
bằng phụ xấp xỉ với song hàm đơn điệu trên C. Đây là cách làm khá phức tạp
và khó khăn khi chạy thuật toán trên máy tính. Để tránh được điều đó, chúng
tôi đã kết hợp giữa phương pháp đạo hàm tăng cường được giới thiệu bởi P.N.
Anh [4] với phương pháp chính quy hóa tương đối của S. Sun [22], đưa ra một kỹ
thuật lặp mới để tìm điểm chung của tập nghiệm bài toán cân bằng giả đơn điệu
EP (C, f ) và tập điểm bất động của ánh xạ không giãn trong một không gian
Hilbert thực. Khi đó, tại mỗi bước lặp thứ k chúng tôi chỉ cần giải hai bài toán
lồi mạnh với phương pháp giải tương đối đơn giản và thu được nghiệm chính xác.
Cho trước x1 , t ∈ H. Dãy {xk } được xác định như sau.




y k = argmin{λk f (xk , y) + 21 y − xk 2 : y ∈ C}


(i) αk ⊂ (0, 1),
∞
k=1 |βk |

(ii)

∞
k=1 αk

= ∞;

< ∞ hoặc lim sup
k→∞

βk
≤ 0.
αk

Khi đó, lim ak = 0.
k→∞

Bổ đề 2.2 ([13]). Cho C là một tập con lồi, đóng, khác rỗng của một không gian
Hillbert thực H. Nếu F ix(S) = ∅ thì (I − S) nửa đóng, tức là, bất kỳ {xk } ⊂ C
hội tụ yếu đến x¯ ∈ C và dãy {(I − S)(xk )} hội tụ mạnh tới y¯ thì (I − S)¯
x = y¯,
với I là toán tử đơn vị của H.
Bổ đề 2.3 ([4]). Cho 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. Cho f : C × C → R là một song hàm giả đơn điệu, liên tục kiểu
Lipschitz với hằng số c1 , c2 > 0. Với mỗi x ∈ C, cho f (x, .) lồi, khả dưới vi phân

ii) βk ⊂ (0, 1),

∞
k=0 βk

= ∞,

lim αk = 0;

k→∞

lim βk = 0;

k→∞

αk
= 0;
k→∞ βk

iii) lim

iv) λk ⊂ [a, b],

a, b ∈ (0,

1
), trong đó L = max{2c1 , 2c2 }.
L

Khi đó các dãy {xk }, {y k }, {tk } cùng hội tụ mạnh đến x∗ với điều kiện

2

+ 2βk g(x∗ ) − x∗

+ (1 − βk )(1 − αk ) tk − x∗
≤ 2βk δ 2 xk − x∗

2

+ (1 − βk )(1 − αk ) xk − x∗

2

+ (1 − βk )αk (u − x∗ )

2

2

+ (1 − βk )αk (u − x∗ )

2

2

− (1 − 2λk c1 ) xk − y k

2

2

2

+ 2βk g(x∗ ) − x∗

2

2

2

(2.3)

+ (1 − βk )αk u − x∗

2

− (1 − 2λk c1 )(1 − βk )(1 − αk ) xk − y k 2 .

(2.4)

Từ giả thiết (iv) và (2.4), ta có
(1 − αk )(1 − βk )(1 − 2bc1 ) xk − y k

2

≤ (1 − αk )(1 − βk )(1 − 2λk c1 ) xk − y k
≤ xk − x∗

2



≤

1 − αk (1 − βk ) + βk (1 − 2δ 2 )
23

xk − x∗

2


2
g(x∗ ) − x∗
2
1 − 2δ
+αk (1 − βk ) u − x∗ 2 .
+βk (1 − 2δ 2 )

2

Từ đó, dẫn đến:
xk+1 − x∗

2

max { xk − x∗ 2 ,

≤

2

Từ x − t

k

k

≤ x −y

k

k→∞
k

k

+ y − t , ta được
lim xk − tk = 0.

k→∞

Bước 2. Chứng minh lim tk − S(tk ) = 0.
k→∞

k

Đặt u = αk t + (1 − αk )tk . Khi đó, ta có:
xk+1 − xk = βk g(xk ) + (1 − βk )S(uk ) − xk
= βk (g(xk ) − xk ) + (1 − βk )(tk − xk )
+(1 − βk )(S(uk ) − S(tk ) + S(tk ) − tk ).
Điều này dẫn tới