ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC
ĐINH THỊ TRANG
THUẬT TOÁN LAI GHÉP GIẢI BÀI TOÁN CHẤP NHẬN TÁCH NHIỀU TẬP
LUẬN VĂN THẠC SĨ TOÁN HỌC
Chuyên ngành: Toán ứng dụng Mã số: 8 46 01 12
NGƯỜI HƯỚNG DẪN KHOA HỌC GS.TS. Nguyễn Bường
Thái
Nguyên
–
2021
ii
Lời cảm ơn
Luận văn này được hoàn thành dưới sự hướng dẫn của GS.TS. Nguyễn Bường
(Viện Công nghệ Thông tin-Viện Hàn lâm Khoa học và Công nghệ Việt Nam).
Tác giả xin được bày tỏ lòng biết ơn chân thành và sâu sắc tới thầy hướng dẫn
khoa học của mình, người đã đặt vấn đề nghiên cứu, dành nhiều thời gian hướng
dẫn và tận tình giải đáp những thắc mắc của tác giả trong suốt quá trình làm
luận văn.
Tác giả cũng đã học tập được rất nhiều kiến thức chuyên ngành bổ ích cho
công tác và nghiên cứu của bản thân. Tác giả xin bày tỏ lòng cảm ơn sâu sắc tới
các thầy giáo, cô giáo đã tham gia giảng dạy lớp cao học Toán, nhà trường và
các phòng chức năng của trường, khoa Toán - Tin, trường Đại học Khoa học -
Đại học Thái Nguyên đã quan tâm và giúp đỡ tác giả trong suốt thời gian học
tập tại trường.
Xin chân thành cảm ơn anh chị em trong lớp cao học và bạn bè đồng nghiệp
đã trao đổi, động viên và khích lệ tác giả trong quá trình học tập, nghiên cứu và
làm luận văn.
iii
Mục lục
Lời cảm ơn ii
Một số ký hiệu và viết tắt iv
Mở đầu 1
Chương 1 Một số kiến thức chuẩn bị 2
1.1. Một số đặc trưng của không gian Hilbert . . . . . . . . . . . . . . 2
1.2. Bài toán tìm điểm bất động của ánh xạ không giãn . . . . . . . . 9
1.3. Bất đẳng thức biến phân trong không gian Hilbert . . . . . . . . . 12
1.3.1. Một số vấn đề sơ lược về bất đẳng thức biến phân . . . . . 12
1.3.2. Bất đẳng thức biến phân trên tập điểm bất động của ánh
xạ không giãn . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.4. Một số bổ đề bổ trợ . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
Chương 2 Một số thuật toán lai ghép giải bài toán chấp nhận tách
nhiều tập 22
2.1. Phát biểu bài toán và một số cải tiến của phương pháp CQ . . . . 22
2.2. Thuật toán và sự hội tụ . . . . . . . . . . . . . . . . . . . . . . . . 26
Kết luận 34
Tài liệu tham khảo 35
iv
Một số ký hiệu và viết tắt
H
X
không gian Hilbert
(cid:104)., .(cid:105)
không gian Banach
(cid:107).(cid:107)
tích vô hướng trên H
∪
chuẩn trên H
∩
phép hợp
phép giao
I
tập các số thực không âm R+
∅
toán tử đồng nhất
∀x
tập rỗng
∃x
với mọi x
xn → x0
tồn tại x
xn (cid:42) x0
dãy {xn} hội tụ mạnh về x0
F ix(T )
dãy {xn} hội tụ yếu về x0
tập điểm bất động của ánh xạ T
1
Mở đầu
“Bất đẳng thức biến phân” được nảy sinh trong quá trình nghiên cứu và giải
các bài toán thực tế như bài toán cân bằng trong kinh tế, tài chính, bài toán
mạng giao thông, lý thuyết trò chơi, phương trình vật lý toán ... Bài toán này
được giới thiệu lần đầu tiên bởi Hartman và Stampacchia vào năm 1966 trong tài
liệu [5]. Bài toán bất đẳng thức biến phân trong không gian hữu hạn chiều, cũng
như vô hạn chiều cùng với các ứng dụng của nó được giới thiệu khá chi tiết trong
cuốn sách “An Introduction to Variational Inequalities and Their Applications”
của D. Kinderlehrer và G. Stampacchia xuất bản năm 1980 [7].
Bất đẳng thức biến phan trên tập nghiệm của một bài toán khác thường được
gọi là bất đẳng thức biến phân hai cấp. Gần đây đã có nhiều người làm toán
trong và ngoài nước quan tâm đến bất đẳng thức biến phân trên tập nghiệm của
bài toán chấp nhận tách (đa tập), do lớp bài toán này có thể áp dụng để giải
một số lớp bài toán khác, đặc biệt là các bài toán liên quan đến xử lý tín hiệu,
xử lý hình ảnh trong Y học.
Mục đích của luận văn là trình bày lại các kết quả của Wang và các cộng sự
trong tài liệu [14] về một phương pháp lặp xoay vòng tìm nghiệm của bất đẳng
thức biến phân trên tập nghiệm của bài toán chấp nhận tách đa tập trong không
gian Hilbert.
Nội dung chính của luận văn được cấu trúc thành hai chương, trong đó:
Chương 1 trình bày một số kiến thức chuẩn bị về không gian Hilbert, ánh xạ
không giãn và bất đẳng thức biến phân. Chương 2 trình bày lại chi tiết các kết
quả của Wang và các cộng sự về phương pháp lặp kiểu đường dốc nhất kết hợp
với phương pháp CQ xấp xỉ nghiệm của bất đẳng thức biến phân trên tập nghiệm
của bài toán chấp nhận tách đa tập trong không gian Hilbert.
2
Chương 1
Một số kiến thức chuẩn bị
Chương này bao gồm năm mục chính. Mục 1.1 đề cập đến một số đặc trưng
cơ bản của không gian Hilbert thực. Mục 1.2 giới thiệu sơ lược một số kết quả
về bài toán tìm điển bất động của ánh xạ không giãn. Mục 1.4 và 1.4 đề cập đến
bài toán bất đẳng thức biến phân cổ điển và bài toán bất đẳng thức biến phân
trong không gian Hilbert. Mục 1.5 giới thiệu một số bổ đề bổ trợ cần sử dụng
trong Chương 2 của luận văn. Nội dung của chương này phần lớn được tham
khảo từ các tài liệu [1], [2] và [7].
1.1. Một số đặc trưng của không gian Hilbert
Ta luôn giả thiết H là không gian Hilbert thực với tích vô hướng được kí hiệu
là (cid:104)., .(cid:105) và chuẩn được kí hiệu là (cid:107).(cid:107).
(cid:107)x − y(cid:107)2 + (cid:107)x − z(cid:107)2 = (cid:107)y − z(cid:107)2 + 2(cid:104)x − y, x − z(cid:105),
Mệnh đề 1.1. Trong không gian Hilbert thực H ta luôn có đẳng thức sau
với mọi x, y, z ∈ H.
(cid:107)y − z(cid:107)2 + 2(cid:104)x − y, x − z(cid:105) = (cid:104)y, y(cid:105) + (cid:104)z, z(cid:105) + 2(cid:104)x, x(cid:105) − 2(cid:104)x, z(cid:105) − 2(cid:104)x, y(cid:105)
= [(cid:104)x, x(cid:105) − 2(cid:104)x, y(cid:105) + (cid:104)y, y(cid:105)]
+ [(cid:104)x, x(cid:105) − 2(cid:104)x, z(cid:105) + (cid:104)z, z(cid:105)]
= (cid:107)x − y(cid:107)2 + (cid:107)x − z(cid:107)2.
Chứng minh. Thật vậy, ta có
Vậy ta được điều phải chứng minh.
3
Mệnh đề 1.2. Cho H là một không gian Hilbert thực. Khi đó, với mọi x, y ∈ H
(cid:107)λx + (1 − λ)y(cid:107)2 = λ(cid:107)x(cid:107)2 + (1 − λ)(cid:107)y(cid:107)2 − λ(1 − λ)(cid:107)x − y(cid:107)2.
và mọi λ ∈ [0, 1], ta có
(1.1)
(cid:107)λx + (1 − λ)y(cid:107)2 = λ2(cid:107)x(cid:107)2 + 2λ(1 − λ)(cid:104)x, y(cid:105) + (1 − λ)2(cid:107)y(cid:107)2
= λ(cid:107)x(cid:107)2 + (1 − λ)(cid:107)y(cid:107)2 − λ(1 − λ)((cid:107)x(cid:107)2 − 2(cid:104)x, y(cid:105) + (cid:107)y(cid:107)2)
= λ(cid:107)x(cid:107)2 + (1 − λ)(cid:107)y(cid:107)2 − λ(1 − λ)(cid:107)x − y(cid:107)2.
Chứng minh. Ta có
Ta được điều phải chứng minh.
(cid:107)x + y(cid:107)2 ≤ (cid:107)x(cid:107)2 + 2(cid:104)y, x + y(cid:105)
Mệnh đề 1.3. Trong không gian Hilbert thực H, ta luôn có
với mọi x, y ∈ H.
(cid:107)x + y(cid:107)2 = (cid:107)x(cid:107)2 + 2(cid:104)x, y(cid:105) + (cid:107)y(cid:107)2
≤ (cid:107)x(cid:107)2 + 2(cid:104)x, y(cid:105) + 2(cid:107)y(cid:107)2
= (cid:107)x(cid:107)2 + 2(cid:104)y, x + y(cid:105).
Chứng minh. Với mọi x, y ∈ H, ta có
Mệnh đề được chứng minh.
Nhắc lại rằng, dãy {xn} trong không gian Hilbert H được gọi là hội tụ yếu về
(cid:104)xn, y(cid:105) = (cid:104)x, y(cid:105),
lim n→∞
phần tử x ∈ H, nếu
xn (cid:42) x. Tuy nhiên, điều ngược lại không đúng. Chẳng hạn xét không gian n=1 |xn|2 < ∞(cid:9) và {en} ⊂ l2, được cho bởi l2 = (cid:8){xn} ⊂ R : (cid:80)∞
, 0, ..., 0, ...),
en = (0, ..., 0,
1 vị trí thứ n
với mọi y ∈ H. Từ tính liên tục của tích vô hướng, suy ra nếu xn → x, thì
4
với mọi n ≥ 1. Khi đó, en (cid:42) 0, khi n → ∞. Thật vậy, với mỗi y ∈ H, từ bất đẳng
∞ (cid:88)
|(cid:104)en, y(cid:105)|2 < (cid:107)y(cid:107)2 < ∞.
n=1
thức Bessel, ta có
(cid:107)en(cid:107) = 1 với mọi n ≥ 1.
Suy ra limn→∞(cid:104)en, y(cid:105) = 0, tức là en (cid:42) 0. Tuy nhiên, {en} không hội tụ về 0, vì
Ta biết rằng mọi không gian Hilbert H đều thỏa mãn điều kiện của Opial,
tính chất này được thể hiện trong mệnh đề dưới đây:
Mệnh đề 1.4. Cho H là một không gian Hilbert thực và {xn} ⊂ H là một dãy
bất kỳ thỏa mãn điều kiện xn (cid:42) x, khi n → ∞. Khi đó, với mọi y ∈ H và y (cid:54)= x,
ta có
(cid:107)xn − y(cid:107).
lim inf n→∞
(cid:107)xn − x(cid:107) < lim inf n→∞
(1.2)
Chứng minh. Vì xn (cid:42) x, nên {xn} bị chặn.
(cid:107)xn − y(cid:107)2 = (cid:107)xn − x(cid:107)2 + (cid:107)x − y(cid:107)2 + 2(cid:104)xn − x, x − y(cid:105)
> (cid:107)xn − x(cid:107)2 + 2(cid:104)xn − x, x − y(cid:105).
Ta có
(cid:107)xn − x(cid:107)2 + 2(cid:104)xn − x, x − y(cid:105)
lim inf n→∞
(cid:107)xn − y(cid:107)2 > lim inf n→∞
(cid:107)xn − x(cid:107)2.
= lim inf n→∞
Vì x (cid:54)= y, nên
(cid:107)xn − y(cid:107).
lim inf n→∞
(cid:107)xn − x(cid:107) < lim inf n→∞
Do đó, ta nhận được
Mệnh đề được chứng minh.
Mệnh đề 1.5. Mọi không gian Hilbert thực H đều có tính chất Kadec-Klee, tức
(cid:107)xn(cid:107) → (cid:107)x(cid:107), thì xn → x, khi n → ∞.
là nếu {xn} ⊂ H là một dãy bất kỳ trong H thỏa mãn các điều kiện xn (cid:42) x và
(cid:107)xn − x(cid:107)2 = (cid:107)xn(cid:107)2 − 2(cid:104)xn, x(cid:105) + (cid:107)x(cid:107)2
Chứng minh. Ta có
5
→ 0, n → ∞.
Suy ra xn → x, khi n → ∞. Mệnh đề được chứng minh.
H. Khi đó, tồn tại duy nhất phần tử x∗ ∈ C sao cho
(cid:107)x∗(cid:107) ≤ (cid:107)x(cid:107) với mọi x ∈ C.
(cid:107)x(cid:107). Khi đó, tồn tại {xn} ⊂ C sao cho
Mệnh đề 1.6. Cho C là một tập con lồi và đóng của không gian Hilbert thực
(cid:107)xn(cid:107) −→ d, n −→ ∞.
Chứng minh. Thật vậy, đặt d = inf x∈C
(cid:107)
(cid:107)xn − xm(cid:107)2 = 2((cid:107)xn(cid:107)2 + (cid:107)xm(cid:107)2) − 4(cid:107)
xn + xm 2
≤ ((cid:107)xn(cid:107)2 + (cid:107)xm(cid:107)2) − 4d2 −→ 0,
xn ∈
Từ đẳng thức hình bình hành, ta có
khi n, m −→ ∞. Do đó {xn} là dãy Cauchy trong H. Suy ra tồn tại x∗ = lim n→∞ C (do {xn} ⊂ C và C là tập đóng). Do chuẩn là hàm số liên tục nên (cid:107)x∗(cid:107) = d.
Tiếp theo ta chỉ ra tính duy nhất. Giả sử tồn tại y∗ ∈ C sao cho (cid:107)y∗(cid:107) = d. Ta
(cid:107)x∗ − y∗(cid:107)2 = 2((cid:107)x∗(cid:107)2 + (cid:107)y∗(cid:107)2) − 4(cid:107)
(cid:107)2
x∗ + y∗ 2
≤ 2(d2 + d2) − 4d2
= 0.
có
infx∈C (cid:107)x(cid:107).
Suy ra x∗ = y∗. Vậy tồn tại duy nhất một phần tử x∗ ∈ C sao cho (cid:107)x∗(cid:107) =
Từ Mệnh đề 1.6, ta có mệnh đề dưới đây:
H. Khi đó, với mỗi x ∈ H, tồn tại duy nhất phần tử PCx ∈ C sao cho
(cid:107)x − PC(x)(cid:107) ≤ (cid:107)x − y(cid:107) với mọi y ∈ C.
Mệnh đề 1.7. Cho C là một tập con lồi và đóng của không gian Hilbert thực
Chứng minh. Vì C là tập lồi, đóng và khác rỗng nên x − C cũng là tập lồi, đóng
và khác rỗng. Do đó, theo Mệnh đề 1.6, tồn tại duy nhất một phần tử PC ∈ C
(cid:107)x − PC(x)(cid:107) ≤ (cid:107)x − y(cid:107) với mọi y ∈ C.
sao cho
6
Định nghĩa 1.1. Phép cho tương ứng mỗi phần tử x ∈ H một phần tử PCx ∈ C
xác định như trên được gọi là phép chiếu mêtric từ H lên C.
u.
PCx = x +
y − (cid:104)x, u(cid:105) (cid:107)u(cid:107)2
Ví dụ 1.1. Cho C = {x ∈ H : (cid:104)x, u(cid:105) = y}, với u (cid:54)= 0. Khi đó
Ví dụ 1.2. Cho C = {x ∈ H : (cid:107)x − a(cid:107) ≤ R}, trong đó a ∈ H là một phần tử cho
x nếu (cid:107)x − a(cid:107) ≤ R,
trước và R là một số dương. Khi đó, ta có:
PCx =
a +
(x − a) nếu (cid:107)x − a(cid:107) > R.
R (cid:107)x − a(cid:107)
Mệnh đề dưới đây cho ta một điều kiện cần và đủ để ánh xạ PC : H −→ C là
một phép chiếu mêtric.
H. Cho PC : H −→ C là một ánh xạ. Khi đó, các phát biểu sau là tương đương:
Mệnh đề 1.8. Cho C là tập con lồi, đóng và khác rỗng của không gian Hilbert
a) PC là phép chiếu mêtric từ H lên C;
b) (cid:104)y − PCx, x − PCx(cid:105) ≤ 0 với mọi x ∈ H và y ∈ C;
PCx(cid:107) = infu∈C (cid:107)x − u(cid:107). Với mọi x ∈ H, y ∈ C và với mọi α ∈ (0, 1), đặt yα =
αy + (1 − α)PCx. Vì C lồi nên yα ∈ C và do đó
(cid:107)x − PCx(cid:107) ≤ (cid:107)yα − x(cid:107).
Chứng minh. Thật vậy, giả sử PC là phép chiếu mêtric từ H lên C, tức là (cid:107)x −
(cid:107)x − PCx(cid:107)2 ≤ (cid:107)α(y − PCx) − (x − PCx)(cid:107)2
= α2(cid:107)y − PCx(cid:107)2 + (cid:107)x − PCx(cid:107)2 − 2α(cid:104)y − PCx, x − PCx(cid:105).
Điều này tương đương với
2(cid:104)y − PCx, x − PCx(cid:105) ≤ α(cid:107)y − PCx(cid:107)2.
Từ đó, ta nhận được
7
Cho α −→ 0+, ta được (cid:104)y − PCx, x − PCx(cid:105) ≤ 0.
(cid:107)x − PCx(cid:107)2 = (cid:107)x − y + y − PCx(cid:107)2
= (cid:107)x − y(cid:107)2 + 2(cid:104)x − y, y − PCx(cid:105) + (cid:107)y − PCx(cid:107)2
= (cid:107)x − y(cid:107)2 + 2(cid:104)x − PCx, y − PCx(cid:105) − (cid:107)y − PCx(cid:107)2
≤ (cid:107)x − y(cid:107)2.
Ngược lại, giả sử b) đúng. Với mọi x ∈ H và mọi y ∈ C, ta có
Do đó, (cid:107)x − PCx(cid:107) = infu∈C (cid:107)x − u(cid:107), hay PC là phép chiếu mêtric từ H lên C.
Từ mệnh đề trên, ta có hệ quả dưới đây:
Hệ quả 1.1. Cho C là một tập con lồi đóng của không gian Hilbert H và PC là
phép chiếu mêtric từ H lên C. Khi đó, ta có các khẳng định sau:
(cid:107)PCx − PCy(cid:107)2 ≤ (cid:104)x − y, PCx − PCy(cid:105);
a) với mọi x, y ∈ H, ta có
(cid:107)x − y(cid:107)2 ≥ (cid:107)x − PCx(cid:107)2 + (cid:107)y − PCx(cid:107)2.
b) với mọi x ∈ H và y ∈ C, ta có
(cid:104)x − PCx, PCy − PCx(cid:105) ≤ 0,
(cid:104)y − PCy, PCx − PCy(cid:105) ≤ 0.
Chứng minh. a) Với mọi x, y ∈ H, từ Mệnh đề 1.8, ta có
Cộng hai bất đẳng thức trên ta nhận được điều phải chứng minh.
(cid:104)x − PCx, y − PCx(cid:105) ≤ 0.
b) Với mọi x ∈ H và y ∈ C, từ Mệnh đề 1.8, ta có
(cid:107)x − y(cid:107)2 = (cid:107)(x − PCx) − (y − PCx)(cid:107)2
= (cid:107)x − PCx(cid:107)2 + (cid:107)y − PCx(cid:107)2 − 2(cid:104)x − PCx, y − PCx(cid:105)
≥ (cid:107)x − PCx(cid:107)2 + (cid:107)y − PCx(cid:107)2.
Từ đó, ta có
Hệ quả được chứng minh.
8
C là tập đóng yếu.
Mệnh đề 1.9. Nếu C là một tập con lồi và đóng của không gian Hilbert H, thì
(cid:104)v, y(cid:105) ≤ (cid:104)v, x(cid:105) − (cid:107)v(cid:107)2.
sup y∈C
Chứng minh. Trước hết, ta chỉ ra tồn tại một phần tử v ∈ H, v (cid:54)= 0 sao cho
(cid:104)v, y − PCx(cid:105) ≤ 0,
Vì x /∈ C, nên v = x − PCx (cid:54)= 0. Từ Mệnh đề 1.8, ta có
(cid:104)v, y − x + x − PCx(cid:105) ≤ 0,
với mọi y ∈ C. Suy ra
(cid:104)v, y(cid:105) ≤ (cid:104)v, x(cid:105) − (cid:107)v(cid:107)2,
với mọi y ∈ C. Điều này tương đương với
(cid:104)v, y(cid:105) ≤ (cid:104)v, x(cid:105) − (cid:107)v(cid:107)2.
sup y∈C
với mọi y ∈ C. Do đó
Bây giờ ta chỉ ra C là tập đóng yếu. Giả sử ngược lại rằng C không là tập
C là tập lồi và đóng, nên theo chứng minh trên, ta có
(cid:104)v, z(cid:105) < (cid:104)v, x(cid:105) − ε,
đóng yếu. Khi đó, tồn tại dãy {xn} trong C thỏa mãn xn (cid:42) x, nhưng x /∈ C. Vì
(cid:104)v, xn(cid:105) < (cid:104)v, x(cid:105) − ε,
với ε = (cid:107)v(cid:107)2/2 và mọi z ∈ C. Đặc biệt
(cid:104)v, x(cid:105) ≤ (cid:104)v, x(cid:105) − ε,
với mọi n. Cho n → ∞, ta nhận được
điều này là vô lý. Do đó, C là tập đóng yếu.
Chú ý 1.1. Nếu C là tập đóng yếu trong H thì hiển nhiên C là tập đóng.
Từ định lý Banach-Alaoglu, ta có mệnh đề dưới đây:
Mệnh đề 1.10. Mọi tập con bị chặn của H đều là tập compact tương đối yếu.
9
1.2. Bài toán tìm điểm bất động của ánh xạ không giãn
Định nghĩa 1.2. Cho C là một tập con lồi, đóng và khác rỗng của không gian
Hilbert thực H. Ánh xạ T : C −→ H được gọi là một ánh xạ không giãn, nếu
(cid:107)T x − T y(cid:107) ≤ (cid:107)x − y(cid:107).
với mọi x, y ∈ C, ta có
{x ∈ C : T x = x}.
Ta ký hiệu tập điểm bất động của ánh xạ không giãn T là F ix(T ), tức là F ix(T ) =
Mệnh đề dưới đây cho ta mô tả về tính chất của tập điểm bất động F ix(T ).
Mệnh đề 1.11. Cho C là một tập con lồi, đóng và khác rỗng của không gian
Hilbert thực H và T : C −→ H là một ánh xạ không giãn. Khi đó, F ix(T ) là một
tập lồi và đóng trong H.
Chứng minh. Giả sử F ix(T ) (cid:54)= ∅.
Trước hết, ta chỉ ra F ix(T ) là tập đóng. Thật vậy, vì T là ánh xạ không giãn
xn → x, khi n → ∞. Vì {xn} ⊂ F ix(T ), nên
(cid:107)T xn − xn(cid:107) = 0,
nên T liên tục trên C. Giả sử {xn} là một dãy bất kỳ trong F ix(T ) thỏa mãn
với mọi n ≥ 1. Từ tính liên tục của chuẩn, cho n → ∞, ta nhận được (cid:107)T x−x(cid:107) = 0,
tức là x ∈ F ix(T ). Do đó, F ix(T ) là tập đóng.
Tiếp theo, ta chỉ ra tính lồi của F ix(T ). Giả sử x, y ∈ F ix(T ), tức là T x = x
và T y = y. Với λ ∈ [0, 1], đặt z = λx + (1 − λ)y. Khi đó, từ Mệnh đề 1.2 và tính
(cid:107)T z − z(cid:107)2 = (cid:107)λ(T z − x) + (1 − λ)(T z − y)(cid:107)2
= λ(cid:107)T z − x(cid:107)2 + (cid:107)(1 − λ)(T z − y)(cid:107)2 − λ(1 − λ)(cid:107)x − y(cid:107)2
= λ(cid:107)T z − T x(cid:107)2 + (1 − λ)(cid:107)(T z − T y)(cid:107)2 − λ(1 − λ)(cid:107)x − y(cid:107)2
≤ λ(cid:107)z − x(cid:107)2 + (1 − λ)(cid:107)(z − y)(cid:107)2 − λ(1 − λ)(cid:107)x − y(cid:107)2
= (cid:107)λ(z − x) + (1 − λ)(z − y)(cid:107)2 = 0.
không giãn của T ta có
Suy ra T z = z và do đó z ∈ F ix(T ). Vậy F ix(T ) là một tập lồi.
10
Mệnh đề 1.12 (Nguyên lý nửa đóng). Cho C là tập con lồi, đóng và khác rỗng
của không gian Hilbert thực H và T : C −→ C là một ánh xạ không giãn. Khi đó,
xn (cid:42) x ∈ C và xn − T xn → y, thì x − T x = y. Đặc biệt, nếu y = 0 thì x ∈ F ix(T ).
nếu T có điểm bất động thì T là nửa đóng, tức là với mọi dãy {xn} ⊂ C thỏa mãn
Chứng minh. Giả sử x − T x (cid:54)= y. Vì xn (cid:42) x, nên xn − y (cid:42) x − y. Do x − y (cid:54)= T x,
(cid:107)xn − y − T x(cid:107)
lim inf n→∞
(cid:107)xn − x(cid:107) < lim inf n→∞
((cid:107)xn − T xn − y(cid:107) + (cid:107)T xn − T x(cid:107))
≤ lim inf n→∞
(cid:107)xn − x(cid:107).
≤ lim inf n→∞
nên từ Mệnh đề 1.4, ta có
x ∈ F ix(T ).
Suy ra mâu thuẫn. Do đó, x − T x = y. Đặc biệt, nếu y = 0 thì x = T x hay
Bài toán. Cho T : C −→ C là một ánh xạ không giãn từ tập con lồi, đóng và
khác rỗng C của không gian Hilbert H vào chính nó là một ánh xạ không giãn
với F (T ) (cid:54)= ∅. Tìm phần tử x∗ ∈ F (T ).
Đã có nhiều phương pháp nổi tiếng được đề xuất để giải bài toán trên, như
phương pháp lặp Mann, phương pháp lặp Ishikawa, phương pháp lặp Halpern,
phương pháp xấp xỉ mềm, phương pháp sử dụng siêu phẳng cắt ...
Chú ý 1.2. Nếu T là ánh xạ co trên C, thì dãy lặp Picard xác định bởi x0 ∈ C
và xn+1 = T (xn) hội tụ mạnh về điểm bất động duy nhất của T . Tuy nhiên điều
này không còn đúng đối với lớp ánh xạ không giãn.
Phương pháp lặp Mann
Năm 1953, W. R. Mann [8] đã nghiên cứu và đề xuất phương pháp lặp sau:
x0 ∈ C là một phần tử bất kì,
n ≥ 0,
xn+1 = αnxn + (1 − αn)T xn,
(1.3)
n=1 αn(1 − αn) = ∞, thì dãy {xn} xác định bởi
ở đây {αn} là một dãy số thực thỏa mãn α0 = 1, 0 < αn < 1, n ≥ 1, (cid:80)∞ n=0 αn = ∞. Dãy lặp (1.3) được gọi là dãy lặp Mann. Mann W. R. đã chứng minh rằng, nếu dãy {αn} được chọn thỏa mãn (cid:80)∞
11
(1.3) sẽ hội tụ yếu tới một điểm bất động của ánh xạ T . Chú ý rằng nếu H là
không gian Hilbert vô hạn chiều thì dãy lặp (1.3) chỉ cho sự hội tụ yếu.
Phương pháp lặp Halpern
Năm 1967, B. Halpern [4] đã đề xuất phương pháp lặp
x0 ∈ C là một phần tử bất kì,
n ≥ 0
xn+1 = αnu + (1 − αn)T xn,
(1.4)
ở đây u ∈ C và {αn} ⊂ (0, 1). Dãy lặp (1.4) được gọi là dãy lặp Halpern. Ông
đã chứng minh sự hội tụ mạnh của dãy lặp (1.4) về điểm bất động của ánh xạ
không giãn T với điều kiện αn = n−α, α ∈ (0, 1).
Phương pháp lặp xấp xỉ mềm
Năm 2000, Moudafi [9] đã đề xuất phương pháp xấp xỉ mềm, để tìm điểm bất
động của ánh xạ không giãn trong không gian Hilbert và đã chứng minh được
(1) Dãy {xn} ⊂ C xác định bởi:
các kết quả sau:
x0 ∈ C, xn =
T xn +
f (xn), ∀n ≥ 0,
1 1 + εn
εn 1 + εn
(1.5)
x ∈ F (T ) sao cho (cid:104)(I − f )(x), x − x(cid:105) ≤ 0, ∀x ∈ F (T ),
hội tụ mạnh về nghiệm duy nhất của bất đẳng thức biến phân:
(2) Với mỗi phần tử ban đầu z0 ∈ C, xác định dãy {zn} ⊂ C bởi:
trong đó {εn} là một dãy số dương hội tụ về 0.
zn+1 =
T zn +
f (zn), ∀n ≥ 0.
1 1 + εn
εn 1 + εn
−
= 0, thì {zn} hội tụ
(1.6)
n=1 εn = ∞ và limn→∞
1 εn+1
1 εn mạnh về nghiệm duy nhất của bất đẳng thức biến phân:
x ∈ F (T ) sao cho (cid:104)(I − f )(x), x − x(cid:105) ≤ 0, ∀x ∈ F (T ),
Nếu limn→∞ εn = 0, (cid:80)∞ (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12)
(cid:107)f (x) − f (y)(cid:107) ≤ c(cid:107)x − y(cid:107) ∀x, y ∈ C.
ở đây, f : C → C là một ánh xạ co cho trước với hệ số co c ∈ [0, 1). Tức là
Chú ý 1.3. Khi f (x) = u với mọi x ∈ C, thì phương pháp xấp xỉ mềm của
Moudafi trở về phương pháp lặp của Halpern.
12
1.3. Bất đẳng thức biến phân trong không gian Hilbert
1.3.1. Một số vấn đề sơ lược về bất đẳng thức biến phân
Trong mục trên chúng ta vừa trình bày sự tồn tại nghiệm của bất đẳng thức biến phân cổ điển trong không gian Rn. Các kết quả trên đã được nghiên cứu
và mở rộng trong không gian Hilbert. Dưới đây, chúng tôi sẽ trình bày một số
phương pháp tìm nghiệm cho bài toán bất đảng thức biến phân trong không gian
Hilbert.
Cho C là một tập con lồi và đóng của không gian Hilbert H và A : C −→ H
là một ánh xạ liên tục. Bài toán bất đẳng thức biến phân được phát biểu như
sau:
(cid:104)Ax∗, x − x∗(cid:105) ≥ 0 với mọi x ∈ C.
Tìm x∗ ∈ C sao cho
(1.7)
Tập hợp những điểm x∗ ∈ C thỏa mãn (1.7) được gọi là tập nghiệm của bài toán
và ký hiệu là V I(A, C).
Trước hết chúng ta nhắc lại một số khái niệm sau.
Cho H là một không gian Hilbert thực, C là một tập lồi đóng khác rỗng của H
và A : C −→ H là một ánh xạ từ C vào H.
(cid:104)Ax − Ay, x − y(cid:105) ≥ 0.
a) Ánh xạ A được gọi là đơn điệu trên C nếu, với mọi x, y ∈ C ta có:
(cid:104)Ay, x − y(cid:105) ≥ 0 suy ra (cid:104)Ax, x − y(cid:105) ≥ 0.
b) Ánh xạ A được gọi là giả đơn điệu trên C nếu, với mọi x, y ∈ C ta có:
α > 0 sao cho với mọi x, y ∈ C ta có:
(cid:104)Ax − Ay, x − y(cid:105) ≥ α(cid:107)x − y(cid:107)2.
c) Ánh xạ A được gọi là α−đơn điệu mạnh trên C, nếu tồn tại một hằng số
d) Ánh xạ A được gọi là α-ngược đơn điệu mạnh trên C, nếu tồn tại một hằng
(cid:104)Ax − Ay, x − y(cid:105) ≥ α(cid:107)Ax − Ay(cid:107)2.
số α > 0 sao cho với mọi x, y ∈ C ta có:
13
e) Ánh xạ A được gọi là h-liên tục trên C nếu A(x + ty) (cid:42) A(x) khi t −→ 0+
sao cho với mọi x, y ∈ C.
L > 0 sao cho với mọi x, y ∈ C ta có:
(cid:107)Ax − Ay(cid:107) ≥ L(cid:107)x − y(cid:107).
f) Ánh xạ A được gọi là L-liên tục Lipschitz trên C, nếu tồn tại một hằng số
Nhận xét 1.1. Dễ dàng thấy rằng, nếu ánh xạ A là α-ngược đơn điệu mạnh
L =
thì ánh xạ A là một ánh xạ đơn điệu và liên tục Lipschitz với hằng số Lipschitz
1 α
.
Mệnh đề dưới đây cho ta biết về một trường hợp tồn tại nghiệm của bài toán
bất đẳng thức biến phân.
Mệnh đề 1.13. Cho C là một tập con lồi, đóng, khác rỗng và bị chặn của không
V I(C, A) (cid:54)= ∅.
gian Hilbert H và cho A : C −→ H là một toán tử đơn điệu, h-liên tục. Khi đó,
Mệnh đề 1.14. Cho C là một tập con lồi, đóng và khác rỗng của không gian
x∗ ∈ V I(C, A) khi và chỉ khi x∗ ∈ C và
(cid:104)Ay, y − x∗(cid:105) ≥ 0, ∀y ∈ C.
Hilbert H và cho A : C −→ H là một toán tử đơn điệu, h-liên tục. Khi đó,
Chứng minh. Giả sử x∗ ∈ V I(C, A), tức là (cid:104)Ax∗, y − x∗(cid:105) ≥ 0 với mọi y ∈ C. Khi
(cid:104)Ay, y − x∗(cid:105) = (cid:104)Ay − Ax∗, y − x∗(cid:105) + (cid:104)Ax∗, y − x∗(cid:105) ≥ 0
đó, từ tính đơn điệu của A, ta có
với mọi y ∈ C.
(cid:104)Ay, y − x∗(cid:105) ≥ 0, ∀y ∈ C.
Ngược lại, giả sử x∗ ∈ C thỏa mãn
Vì C là tập lồi, nên yt = ty + (1 − t)x∗ ∈ C với mọi y ∈ C và mọi t ∈ (0, 1). Do đó,
(cid:104)Ayt, t(y − x∗)(cid:105) ≥ 0, ∀t ∈ (0, 1).
từ bất đẳng thức trên, ta có
14
(cid:104)Ayt, y − x∗(cid:105) ≥ 0, ∀t ∈ (0, 1).
tương đương với
(cid:104)Ax∗, y − x∗(cid:105) ≥, ∀y ∈ C.
Từ tính h-liên tục của A, cho t → 0+, ta nhận được
Mệnh đề được chứng minh.
Mệnh đề 1.15. Cho C là một tập con lồi, đóng và khác rỗng của không gian
x∗ ∈ V I(C, A) khi và chỉ khi x∗ = PC(x∗ − λAx∗) với mọi λ > 0.
Hilbert H và cho A : C −→ H là một toán tử đơn điệu, h-liên tục. Khi đó,
Chứng minh. Suy ra trực tiếp từ Mệnh đề 1.8.
1.3.2. Bất đẳng thức biến phân trên tập điểm bất động của ánh xạ
không giãn
Một lớp bất đẳng thức biến phân hai cấp quan trọng và có nhiều ứng dụng
trong các lĩnh vực khác nhau của toán học, vật lý, y học hay kinh tế ... là bài
toán bất đẳng thức biến phân trên tập điểm bất động của ánh xạ không giãn.
T : H −→ H là một ánh xạ không giãn. Tìm phần tử x∗ ∈ V I(F ix(T ), A), tức là
x∗ thỏa mãn
(cid:104)Ax∗, v − x∗(cid:105) ≥ 0, ∀v ∈ F ix(T ).
Bài toán 1.1. Cho A : H −→ H là một toán tử đơn điệu, liên tục và cho
Năm 2001, Yamada [10] đã đề xuất phương pháp đường dốc nhất để giải Bài
toán 1.1 cho trường hợp A là toán tử Lipschitz và đơn điệu mạnh. Kết quả của
Yamada được cho bởi định lý dưới đây:
Định lý 1.1. [10] Cho T : H −→ H là một ánh xạ không giãn với F ix(T ) (cid:54)= ∅.
Giả sử ánh xạ A : H −→ H là L-Lipchitz và η-đơn điệu mạnh trên T (H). Khi đó
2η L2 ) và dãy {λn} ⊂ (0, 1] thỏa mãn các điều kiện:
với u0 ∈ H, µ ∈ (0,
(L1) limn→∞ λn = 0,
n=1λn = ∞,
(L2) Σ∞
15
= 0,
λn − λn+1 λ2 n+1
(L3) limn→∞
thì dãy {un} xác định bởi
un+1 := T (λn+1)un := T un − λn+1µA(T un)
(1.8)
hội tụ mạnh về nghiệm duy nhất u∗ của VIP(F ix(T ), A).
Hơn nữa, Yamada cũng đã mở rộng kết quả trên cho trường hợp tập điểm
bất động F ix(T ) của ánh xạ không giãn T được thay bằng tập điểm bất động
chung của một họ hữu hạn ánh xạ không giãn. Kết quả này được thể hiện trong
định lý dưới đây:
F := ∩N
i=1F ix(Ti) (cid:54)= ∅ và
Định lý 1.2. [10] Cho Ti : H −→ H (i = 1, ..., N ) là các ánh xạ không giãn với
∆ := ∪N
i=1Ti(H). Khi đó, với bất kì u0 ∈ H, bất kì µ ∈ (0,
(1.9) F = F ix(TN ...T1) = F ix(T1TN ...T3T2) = ... = F ix(TN −1TN −2...T1TN ).
{λn} ⊂ [0, 1] thỏa mãn
Giả sử rằng một ánh xạ F : H −→ H là L-Lipchitz và η-đơn điệu mạnh trên 2η L2 ) và bất kì dãy
(B1) limn→∞ λn = 0,
n=1λn = ∞,
(B2) Σ∞
n=1 | λn − λn+N |< ∞.
(B3) Σ∞
Dãy {un} xác định bởi
un+1 := T (λn+1)
[n+1] (un) := T[n+1](un) − λn+1µF (T[n+1](un)),
(1.10)
[i] = {i − kN |k = 0, 1, 2, ...} ∩ {1, 2, ..., N }
hội tụ mạnh về nghiệm duy nhất của VIP(F, F), tức là u∗ ∈ F sao cho (cid:104)v − u∗, F (u∗)(cid:105) ≥ 0 với mọi v ∈ F, trong đó [.] là modulo N xác định bởi
16
1.4. Một số bổ đề bổ trợ
Bổ đề 1.1 (xem [10]). Cho C là một tập con khác rỗng của không gian Hilbert
thực H. Giả sử λ ∈ (0, 1) và µ > 0. Cho F : C −→ H là một ánh xạ k-Lipschitzian
và η-đơn điệu mạnh trên C và cho T : C −→ C là một ánh xạ không giãn. Xác
Gx = (I − λµF )T x, ∀x ∈ C.
định ánh xạ G : C −→ H bởi
(cid:107)Gx − Gy(cid:107) ≤ (1 − λτ )(cid:107)x − y(cid:107), ∀x, y ∈ C,
Khi đó, G là một ánh xạ co nếu µ < 2η/k2. Chính xác hơn, với µ ∈ (0, 2η/k2), thì
trong đó τ = 1 − (cid:112)1 − µ(2η − µk2).
(cid:107)(I − µF )x − (I − µF )y(cid:107)2
= (cid:107)(x − y) − µ(F x − F y)(cid:107)2
= (cid:107)x − y(cid:107)2 − 2µ(cid:104)x − y, F x − F y(cid:105) + µ2(cid:107)F x − F y(cid:107)2
≤ (1 − 2µη + µ2k2)(cid:107)x − y(cid:107)2
= [1 − µ(2η − µk2)](cid:107)x − y(cid:107)2.
Chứng minh. Trước hết, với mọi x, y ∈ C, ta có
(cid:107)(I − λµF )T x − (I − λµF )T y(cid:107)
= (cid:107)(1 − λ)(T x − T y) − λ(I − µF )T x − (I − µF )T y)(cid:107)
Do đó, từ tính không giãn của T , ta có
≤ (1 − λ)(cid:107)x − y(cid:107) + λ
1 − µ(2η − µk2)(cid:107)x − y(cid:107)
= (1 − λτ )(cid:107)x − y(cid:107),
(cid:112)
với τ = (cid:112)1 − µ(2η − µk2). Bổ đề được chứng minh.
Bổ đề 1.2. Cho {an} là một dãy số các số thực không âm thỏa mãn tính chất
an+1 ≤ (1 − sn)an + sntn + vn, ∀n ≥ 0
(1.11)
trong đó {sn}, {sn} và {vn} thỏa mãn các điều kiện
17
n=0(1 − sn) = 0;
n=0 sn = ∞ hoặc (cid:81)∞
i) (cid:80)∞
ii) lim supn→∞ tn ≤ 0;
n=0 σn < ∞.
iii) vn ≥ 0, ∀n ≥ 0 và (cid:80)∞
Khi đó {an} hội tụ đến 0 khi n → ∞.
∞ (cid:88)
vn < ε, ∀n ≥ N.
tn < ε,
n=N
Chứng minh. Với ε > 0 bất kỳ (cho trước), lấy số tự nhiên N đủ lớn sao cho
Từ (1.11), bằng quy nạp toán học, ta chỉ ra được
n (cid:89)
∞ (cid:88)
1 −
ε +
vn, ∀n > N.
an+1 ≤
aN +
(1 − sk)
(1 − sk)
n=N
k=N
k=N
(cid:19) (cid:18) (cid:19) (cid:18) n (cid:89)
Từ các điều kiện i)-iii) và đánh giá trên, ta nhận được lim supn→∞ an ≤ 2ε. Vì ε > 0 là bất kỳ nên lim supn→∞ an ≤ 0. Do đó limn→∞ an = 0.
Bổ đề 1.3. Giả sử {xn}, {yn} là các dãy trong không gian Banach E và {αn} là
(cid:107)wn − zn(cid:107).
(cid:107)wn − zn(cid:107) hoặc d = lim inf n→∞
d = lim sup n→∞
dãy trong [0; 1] với lim supn αn < 1. Đặt
((cid:107)wn+1 − wn(cid:107) − (cid:107)zn+1 − zn(cid:107)) ≤ 0
lim sup n→∞
Giả sử rằng zn+1 = αnwn + (1 − αn)zn với mọi n ∈ N,
|(cid:107)wn+k − zn(cid:107) − (1 + αn + αn+1 + ... + αn+k−1)d| = 0
lim inf n→∞
và d < ∞. Khi đó
với mọi k ∈ N.
(cid:107)wn+1 − zn+1(cid:107) − (cid:107)wn − zn(cid:107) ≤ (cid:107)wn+1 − wn(cid:107) + (cid:107)wn − zn+1(cid:107) − (cid:107)wn − zn(cid:107)
= (cid:107)wn+1 − wn(cid:107) − (cid:107)zn+1 − zn(cid:107),
Chứng minh. Từ
18
((cid:107)wn+j − zn+j(cid:107) − (cid:107)wn − zn(cid:107))
lim sup n→∞
j−1 (cid:88)
((cid:107)wn+i+1 − zn+i+1(cid:107) − (cid:107)wn+i − zn+i(cid:107))
= lim sup n→∞
i=0 j−1 (cid:88)
((cid:107)wn+i+1 − wn+i(cid:107) − (cid:107)zn+i=1 − zn+i(cid:107))
≤ lim sup n→∞
i=0
j−1 (cid:88)
≤
((cid:107)wn+i+1 − wn+i(cid:107) − (cid:107)zn+i=1 − zn+i(cid:107)) ≤ 0
lim sup n→∞
i=0
αn)/2, 0 < a < 1. Cố định k, l ∈ N và ε >
ta có
0. Do vậy tồn tại m(cid:48) ≥ l sao cho a ≤ 1 − αn, (cid:107)wn+1 − wn(cid:107) − (cid:107)zn+1 − zn(cid:107) và (cid:107)wn+j − zn+j(cid:107) − (cid:107)wn − zn(cid:107) ≤ ε/2 với mọi n ≥ m(cid:48) và j = 1, 2, · · · , k.
với j ∈ N. Đặt a = (1 − lim sup n→∞
(cid:107)wm+k − zm+k(cid:107) ≥ d −
ε 2
Trong trường hợp d = lim supn (cid:107)wn − zn(cid:107), chọn m ≤ m(cid:48) thỏa mãn
≥ d − (cid:15)
(cid:107)wm+j − zm+j(cid:107) ≥ (cid:107)wm+k − zm+k(cid:107) −
ε 2
và (cid:107)wn − zn(cid:107) ≤ d + ε với mọi n ≥ m. Khi đó, ta có
với j = 0, 1, ..., k − 1.
(cid:107)wm − zm(cid:107) ≤ d +
ε 2
Trong trường hợp d = lim infn (cid:107)wn − zn(cid:107), chọn m ≥ m(cid:48) thỏa mãn
≤ d + ε
(cid:107)wm+j − zm+j(cid:107) ≤ (cid:107)wm+k − zm+k(cid:107) +
ε 2
và (cid:107)wn − zn(cid:107) ≥ d − ε với mọi n ≥ m. Ta có
với j = 1, ..., k.
(cid:107)wn+1 − wn(cid:107) − (cid:107)zn+1 − zn(cid:107) ≤ ε với mọi n ≥ m và
d − ε ≤ (cid:107)wm+j − zm+j(cid:107) ≤ d + ε
Trong cả hai trường hợp trên, lấy m thỏa mãn m ≥ l, a ≤ 1 − αn ≤ 1,
với j = 0, 1, ..., k.
19
Tiếp theo, ta chỉ ra
−
ε
(cid:107)wm+j − zm+j(cid:107) ≥ (1 + αm+j + αm+j+1 + ... + αm+k−1)d (k − j)(2k + 1) ak−j
(1.12)
với j = 0, 1, ..., k − 1.
d − ε ≤ (cid:107)wm+k − zm+k(cid:107)
= (cid:107)wm+k − αm+k−1wm+k−1 − (1 − αm+k−1)zm+k−1(cid:107)
≤ αm+k−1(cid:107)wm+k − wm+k−1(cid:107) + (1 − αm+k−1)(cid:107)wm+k − zm+k−1(cid:107)
≤ αm+k−1(cid:107)zm+k − zm+k−1(cid:107) + ε + (1 − αm+k−1)(cid:107)wm+k − zm+k−1(cid:107)
= α2
m+k−1(cid:107)wm+k−1 − zm+k−1(cid:107) + ε + (1 − αm+k−1)(cid:107)wm+k − zm+k−1(cid:107)
≤ α2
m+k−1d + 2ε + (1 − αm+k−1)(cid:107)wm+k − zm+k−1(cid:107),
Từ
(1 − α2
m+k−1)d − 3ε
(cid:107)wm+k − zm+k−1(cid:107) ≥
1 − αm+k−1
ε.
≥ (1 + αm+k−1)d −
2k + 1 a
ta có
Do đó (1.12) đúng với j = k − 1. Giả sử (1.12) đúng với j ∈ {1, 2, ..., k − 1} nào
k−1 (cid:88)
(1 +
ε
αm+i)d −
(k − i)(2k + 1) ak−j
i=j
≤ (cid:107)wm+k − zm+j(cid:107)
= (cid:107)wm+k − αm+j−1wm+j−1 − (1 − αm+j−1)zm+j−1(cid:107)
≤ αm+j−1(cid:107)wm+k − wm+j−1(cid:107) + (1 − αm+j−1)(cid:107)wm+k − zm+j−1(cid:107)
k−1 (cid:88)
≤ αm+j−1
(cid:107)wm+i+1 − wm+i(cid:107) + (1 − αm+j−1)(cid:107)wm+k − zm+j−1(cid:107)
i=j−1
k−1 (cid:88)
≤ αm+j−1
((cid:107)zm+i+1 − zm+i(cid:107) + ε) + (1 − αm+j−1)(cid:107)wm+k − zm+j−1(cid:107)
i=j−1
k−1 (cid:88)
≤ αm+j−1
(cid:107)zm+i+1 − zm+i(cid:107) + kε + (1 − αm+j−1)(cid:107)wm+k − zm+j−1(cid:107)
i=j−1
đó. Khi đó, từ
20
k−1 (cid:88)
= αm+j−1
αm+i(cid:107)zm+i+1 − zm+i(cid:107) + kε + (1 − αm+j−1)(cid:107)wm+k − zm+j−1(cid:107)
i=j−1
k−1 (cid:88)
≤ αm+j−1
αm+i(d + ε) + kε + (1 − αm+j−1)(cid:107)wm+k − zm+j−1(cid:107)
i=j−1
k−1 (cid:88)
≤ αm+j−1
αm+id + 2kε + (1 − αm+j−1)(cid:107)wm+k − zm+j−1(cid:107),
i=j−1
1 +
αm+i
αm+i − αm+j−1
k−1 (cid:80) i=j−1
k−1 (cid:80) i=j
d
(cid:107)wm+k − zm+j−1(cid:107) ≥
1 − αm+j−1
−
ε
(k − j)(2k + 1)/ak−j + 2k 1 − αm+j−1
k−1 (cid:88)
≥ (1 +
ε.
αm+i)d −
(k − j + 1)(2k + 1) ak−j+1
i=j−1
ta nhận được
Do đó 1.12 đúng với j = j − 1. Như vậy 1.12 đúng với mọi j = 0, 1, ..., k − 1. Đặc
ε.
biệt, ta có
(cid:107)wm+k − zm(cid:107) ≥ (1 + αm + αm+1 + ... + αm+k−1)d −
k(2k + 1) ak
(1.13)
k−1 (cid:88)
(cid:107)zm+i+1 − zm+i(cid:107)
(cid:107)wm+k − zm(cid:107) ≤ (cid:107)wm+k − zm+k(cid:107) +
i=0 k−1 (cid:88)
αm+i(cid:107)wm+i − zm+i(cid:107)
= (cid:107)wm+k − zm+k(cid:107) +
i=0
k−1 (cid:88)
≤ d + ε +
αm+i(d + ε)
i=0
k−1 (cid:88)
≤ d +
Mặt khác, ta lại có
αm+id + (k + 1)ε.
i=0
(1.14)
ε.
|(cid:107)wm+k − zm(cid:107) − (1 + αm + αm+1 + ... + αm+k−1)d| ≤
k(2k + 1) ak
Từ (1.13) và (1.14), ta có
Từ l ∈ N và ε > 0 tùy ý, ta có điều phải chứng minh.
21
E sao cho
zn+1 = αnωn + (1 − αn)zn, ∀n ≥ 0,
Bổ đề 1.4. [13]. Giả sử {zn}, {ωn} là các dãy bị chặn trong không gian Banach
αn < 1.
0 < lim inf n→∞
αn ≤ lim sup n→∞
trong đó {αn} là một dãy trong [0,1] sao cho
((cid:107)ωn+1 − ωn(cid:107) − (cid:107)zn+1 − zn(cid:107)) ≤ 0.
lim sup n→∞
(cid:107)ωn − zn(cid:107) = 0.
Giả sử rằng
Khi đó lim sup n→∞
αn > 0, M = 2 sup{(cid:107)zn(cid:107) + (cid:107)wn(cid:107) : n ∈ N} < ∞ và (cid:107)wn − zn(cid:107) < ∞. Giả sử d > 0 và cố định k ∈ N với (1 + ka)d > M. Theo
d = lim sup n→∞ Bổ đề 1.3, ta có
|(cid:107)wn+k − zn(cid:107) − (1 + αn + αn+1 + ... + αn+k−1)d| = 0.
lim inf n→∞
Chứng minh. Đặt a = lim inf n→∞
((cid:107)wni+k − zni(cid:107) − (1 + αni + αni+1 + ... + αni+k−1)d) = 0
lim i→∞
Do đó, tồn tại một dãy con {ni} của dãy {n} trong N sao cho
αni+j với mọi j ∈ {0, 2, ..., k − 1}. Ta có
1}. Đặt βj = lim i→∞
M < (1 + ka)d
≤ (1 + β0 + β1 + ... + βk−1)d
(1 + αni + αni+1 + ... + αni+k−1)d
= lim i→∞
(cid:107)wni+k − zni(cid:107)
= lim i→∞
(cid:107)wn+k − zn(cid:107) ≤ M.
≤ lim sup n→∞
và tồn tại các giới hạn của các dãy {(cid:107)wni+k −zni(cid:107)}, {αni+j} với mọi j ∈ {0, 1, ..., k −
Điều này là mâu thuẫn. Vậy d = 0.
22
Chương 2
Một số thuật toán lai ghép giải bài toán chấp nhận tách nhiều tập
Nội dung chính của chương này là trình bày lại kết quả của Wang và các cộng
sự trong tài liệu [14] về một phương pháp lặp xoay vòng tìm nghiệm của bất
đẳng thức biến phân trên tập nghiệm của bài toán chấp nhận tách đa tập trong
không gian Hilbert.
2.1. Phát biểu bài toán và một số cải tiến của phương pháp
CQ
Cho C và Q là các tập con lồi, đóng và khác rỗng của các không gian Hilbert H1 và H2, tương ứng. Cho A : H1 −→ H2 là một toán tử tuyến bị chặn A∗ : H2 → H1
là toán tử liên hợp của A. Bài toán chấp nhận tách (SFP) trong không gian
Hilbert được phát biểu như sau:
Tìm một phần tử x∗ ∈ Γ = C ∩ A−1(Q) (cid:54)= ∅. (SFP)
Dạng tổng quát của Bài toán (SFP) là bài toán (MSSFP), bài toán này được
phát biểu như sau: Cho Ci, i = 1, 2, ..., t và Qj, j = 1, 2, ..., r là các tập con lồi và
đóng của H1 và H2, tương ứng.
i=1Ci ∩ A−1(∩r
j=1Qj) (cid:54)= ∅.
Tìm một phần tử x∗ ∈ Γ = ∩t (MSSFP)
Một trong những phương pháp cơ bản để giải bài toán (SFP) là phương pháp
CQ. Với phương pháp CQ, Bài toán (SFP) được đưa về bài toán tìm một điểm
23
bất động của ánh xạ PC (cid:0)I − γA∗(I − PQ)A(cid:1), trong đó γ > 0, PC và PQ lần lượt là
0,
(cid:18) (cid:19) Ta biết rằng nếu γ ∈ (cid:1)A là một ánh xạ không (cid:0)I −γA∗(I −PQ , thì PC các phép chiếu mêtric từ E lên C và từ F lên Q, tương ứng. 2 (cid:107)A(cid:107)2
giãn. Do đó, người ta có thể vận dụng các phương pháp tìm điểm bất động của
ánh xạ không giãn (phương pháp lặp Mann, phương pháp lặp Halpern, phương
pháp xấp xỉ gắn kết) để tìm nghiệm của Bài toán (SFP).
Xu [12] đã đưa ra và chứng minh các kết quả dưới đây. Trước hết ông chỉ ra
sự hội tụ yếu của phương pháp CQ về một nghiệm của Bài toán (SFP).
0,
2 (cid:107)A(cid:107)2
xn+1 = PC
(cid:18) (cid:19) Định lý 2.1. [12] Nếu γ ∈ thì dãy {xn} xác định bởi x1 ∈ H1 và
(cid:0)I − γA∗(I − PQ)A(cid:1)xn
hội tụ yếu về một nghiệm của bài toán (SFP).
Sự hội tụ của phương pháp lặp Mann và phương pháp lặp được cho bởi định
lý dưới đây:
Định lý 2.2. [12] Cho dãy {αn} ⊂ [0, 4/(2 + γ(cid:107)A(cid:107)2)] thỏa mãn điều kiện
4
∞ (cid:88)
= ∞.
αn
2 + γ(cid:107)A(cid:107)2 − αn
n=1
(cid:19) (cid:18)
0,
2 (cid:107)T (cid:107)2
xn+1 = (1 − αn)xn + αnPC
(cid:18) (cid:19) Nếu γ ∈ thì dãy {xn} xác định bởi x1 ∈ H1 và
(cid:0)I − γA∗(I − PQ)A(cid:1)xn,
hội tụ yếu về một nghiệm của bài toán (SFP).
Năm 2006, Xu [11] đã đưa ra các thuật toán mở rộng của phương pháp CQ
r (cid:88)
p(x) =
βj(cid:107)Ax − PQj (Ax)(cid:107)2,
1 2
j=1
dưới đây cho Bài toán (MSSFP). Đặt
trong đó βj > 0 với mọi j = 1, 2, . . . , r. Trước hết, Xu [11] đã chứng minh kết quả
dưới đây:
Mệnh đề 2.1. Giả sử tập nghiệm của Bài toán (MSSFP) khác rỗng. Khi đó, ta
có các khẳng định sau:
24
r (cid:88)
(cid:53)p(x) =
i) Hàm p(x) là lồi, khả vi với đạo hàm được xác định bởi
βjA∗(I − PQj )Ax,
j=1
(2.1)
j=1 βj.
và (cid:53)p(x) là ánh xạ Lipschitz với hằng số L = (cid:107)A(cid:107)2 (cid:80)r
ii) Phần tử x∗ là một nghiệm của Bài toán (MSSFP) nếu nó là điểm bất động
i=1 với Ti = PCi(I − γ (cid:53) p),
γ > 0, i = 1, 2, . . . , t.
chung của các ánh xạ không giãn trung bình {Ti}t
Tiếp đó, ông chứng minh sự hội tụ của phương pháp lặp Picard cho Bài toán
(MSSFP).
0,
2 L
(cid:18) (cid:19) với βj > 0 với mọi j = 1, 2, . . . , r và L =
j=1 βj, thì dãy {xn} xác định bởi x1 ∈ H1 và
r (cid:88)
r (cid:88)
βjA∗(I − PQj )A)xn
xn+1 = PCN (I − γ
βjA∗(I − PQj )A . . . PC1(I − γ
j=1
j=1
Định lý 2.3. [11] Nếu γ ∈ (cid:107)A(cid:107)2 (cid:80)r
hội tụ yếu về một nghiệm của Bài toán (MSSFP).
Xu cũng đã xây dựng và chứng minh sự hội tụ của phương pháp lặp song
song và phương pháp lặp xoay vòng cho Bài toán (MSSFP) ở dạng dưới đây:
0,
(cid:19) (cid:18) với βj > 0 với mọi j = 1, 2, . . . , r, L =
2 L j=1 βj và λi > 0 thỏa mãn (cid:80)t
i=1 λi = 1, thì dãy {xn} xác định bởi x1 ∈ H1
Định lý 2.4. [11] Nếu γ ∈ (cid:107)A(cid:107)2 (cid:80)r
t (cid:88)
r (cid:88)
xn+1 =
λiPCi(I − γ
βjA∗(I − PQj )A)xn
i=1
j=1
và
hội tụ yếu về một nghiệm của Bài toán (MSSFP).
0,
2 L
(cid:18) (cid:19) với βj > 0 với mọi j = 1, 2, . . . , r và L =
j=1 βj, thì dãy {xn} xác định bởi x1 ∈ H1 và
r (cid:88)
βjA∗(I − PQj )A)xn
xn+1 = PC[n+1](I − γ
j=1
Định lý 2.5. [11] Nếu γ ∈ (cid:107)T (cid:107)2 (cid:80)r
hội tụ yếu về một nghiệm của Bài toán (MSSFP).
25
Từ các kết quả trong [11, 3, 6], ta có các kết quả dưới đây.
Bổ đề 2.1. [11, 3, 6] Giả sử rằng Bài toán (MSSFP) có tập nghiệm khác rỗng.
U = T1 . . . Tt là trung bình; tổ hợp lồi S =
αiTi là trung bình, trong đó αi >
:= PCi(I − γ∇q), i = 1, 2, . . . , t, trong đó 0 < γ < 2/L. Khi đó ánh xạ t (cid:80) i=1
0,
αi = 1; T[n+1] = Tn mod t cũng là trung bình, trong đó hàm mod lấy giá trị
t (cid:80) i=1
Đặt Ti
trên tập {1, 2, . . . , t}.
Bổ đề 2.2. [11] Ký hiệu các toán tử trung bình U, S, T[n+1] trong Bổ đề 2.1 là T.
Vơi các điểm khởi đầu x0, y0 và z0 bất kỳ trong H, n ≥ 0, dãy {xn}, {yn} và {zn}
được sinh bởi
xn+1 = T xn,
(2.2)
yn+1 = (1 − an)T yn,
(2.3)
zn+1 = (1 − bn)zn + bnT zn,
(2.4)
trong đó {an} và {bn} là các dãy số thực trong (0, 1). Khi đó, ta có các khẳng
định sau:
i) Dãy {xn} xác định bởi (2.2) hội tụ yếu tới một nghiệm của Bài toán
(MSSFP);
n=1 bn(1 − bn) = ∞, thì dãy {zn} xác định bởi (2.4) hội tụ yếu tới một
ii) Nếu (cid:80)∞
nghiệm của Bài toán (MSSFP);
iii) Nếu các điều kiện sau được thỏa mãn
n=1 an = ∞;
a) limn→∞ an = 0; b) (cid:80)∞
n=1 |an+1 − an| < ∞ hoặc limn→∞ an+1/an = 1,
c) (cid:80)∞
thì dãy {yn} xác định bởi (2.3) hội tụ mạnh về nghiệm chuẩn tắc của Bài
toán (MSSFP).
f : H × H → H là một ánh xạ tổ hợp được xác định bởi
f (x1, x2) = (1 − αn)x1 + αnx2, n ≥ 0,
Định nghĩa 2.1. Cho các toán tử trung bình U, S, T[n+1] trong Bổ đề 2.2 và
26
Y := Sf (U, T[n+1]), Z := T[n+1]f (U, S). Khi đó đặt B : H → H là toán tử trung
với mọi (x1, x2) ∈ H × H và αn ∈ [0, 1]. Ta đặt các ánh xạ X := U f (S, T[n+1]),
bình được xác định bởi B := anX + bnY + cnZ, n ≥ 0 với an, bn, cn là các dãy trong R thỏa mãn an + bn + cn = 1.
2.2. Thuật toán và sự hội tụ
Trong mục này chúng tôi trình bày lại một vài thuật toán lai ghép hội tụ
mạnh để giải bài toán chấp nhận tách đa tập, chính xác hơn là tìm nghiệm của
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 (MSSFP) từ tài
liệu [14]. Trước hết, chúng ta có kết quả sau.
k-Lipschitz và η-đơn điệu mạnh. Ký hiệu các toán tử trung bình U, S hoặc T[n+1]
Định lý 2.6. Giả sử rằng H là không gian Hilbert thực và F : H −→ H là ánh xạ
được xác định trong Bổ đề 2.1 là Tα. Với mọi x0 ∈ H, dãy {xn}n(cid:62)0 được sinh bởi
xn+1 = (I − λnµF )Tαxn, n ≥ 0,
(2.5)
λn = 0,
trong đó λn ∈ (0, 1) thoả mãn
(P1) lim n→∞
λn = ∞ và γ ∈ (0, 2/L).
∞ (cid:80) n=0
(P2)
Khi đó dãy {xn} xác định bởi (2.5) hội tụ mạnh tới một nghiệm của Bài toán
(cid:104)F x∗, x − x∗(cid:105) ≥ 0, với mọi x ∈ Γ.
(MSSFP), đồng thời là nghiệm duy nhất của bài toán bất đẳng thức biến phân
(2.6)
Chứng minh. Đầu tiên ta chứng minh rằng dãy {xn} bị chặn. Vì Tα là ánh xạ
(cid:107)xn+1 − p(cid:107) = (cid:107)(I − λnµF )(Tαxn − p) + λnF p(cid:107)
≤ (1 − λnτ )(cid:107)xn − p(cid:107) +
µ τ
(cid:107)F p(cid:107) (cid:111)
không giãn và Tαp = p, nên từ Bổ đề 1.1 và (2.5), với p ∈ Γ ta có
(cid:107)F p(cid:107)
.
≤ max
(cid:107)x0 − p(cid:107),
µ τ
(cid:110)
Từ đó ta suy ra dãy {xn} bị chặn.
27
(cid:107)xn+1 − xn(cid:107) = (cid:107)(I − λnµF )Tα(xn − xn−1) + (λn−1 − λn)µF Tαxn−1(cid:107)
Tiếp theo ta có
(2.7) (cid:54) (1 − λnτ )(cid:107)xn − xn−1(cid:107)+ | λn−1 − λn | (cid:107)µF Tαxn−1(cid:107).
Từ các điều kiện (P1), (P2) và Bổ đề 1.4 ta có
(cid:107)xn+1 − xn(cid:107) = 0.
lim n→∞
(2.8)
||xn − un|| ≤ (cid:107)xn − xn+1(cid:107) + (cid:107)xn+1 − un(cid:107)
≤ (cid:107)xn − xn+1(cid:107) + λnµ(cid:107)F un(cid:107).
Đặt un = Tαxn ta thu được
Từ điều kiện (P1) và (2.8) ta nhận được
(cid:107)xn − un(cid:107) = 0.
lim n→∞
(2.9)
Vì dãy {xn} bị chặn, nên tồn tại một dãy con xni (cid:42) x∗ khi i → ∞. Một cách tổng quát ta giả sử rằng xn (cid:42) x∗ khi i → ∞, kết hợp với Mệnh đề 1.12 ta có xn (cid:42) x∗ ∈ F ix(Tα).
Mặt khác, từ các Bổ đề 2.1 và 2.2 ta biết rằng un (cid:42) x khi n → ∞ và x ∈ Γ.
Do đó
(cid:104)F x∗, un − x∗(cid:105) ≥ 0, x∗ ∈ Γ.
lim n→∞
(2.10)
(cid:107)xn+1 − x∗(cid:107)2 = (cid:107)(I − λnµF )(un − x∗) − λnµF x∗(cid:107)2
= (cid:107)(I − λnµF )(un − x∗)(cid:107)2 + λ2
nµ2(cid:107)F x∗(cid:107)2
− 2λnµ (cid:104)(I − λnµF )(un − x∗), F x∗(cid:105)
≤ (1 − λnτ )(cid:107)xn − x∗(cid:107) − 2λnµ (cid:104)un − x∗, F x∗(cid:105)
+ λ2
nµ2(cid:107)F un − F x∗(cid:107)(cid:107)F x∗(cid:107)
nµ2(cid:107)F x∗(cid:107)2 + 2λ2 = (1 − σn)(cid:107)xn − x∗(cid:107) + σnδn,
Cuối cùng ta sẽ chứng minh xn (cid:42) x∗ theo chuẩn. Thật vậy, ta có
σn = λnτ,
trong đó
28
(cid:104)un − x∗, F x∗(cid:105) +
δn =
λnµ2 τ
−2µ τ
(cid:0)(cid:107)F x∗(cid:107)2 + 2(cid:107)F un − F x∗(cid:107)(cid:107)F x∗(cid:107)(cid:1).
σn ≤ 0. Do đó, từ Bổ đề 1.2 ta suy ra rằng
σn = ∞ và lim n→∞
∞ (cid:80) n=0 xn → x∗ khi n → ∞,
Rõ ràng rằng
Nhận xét 2.1. Khi ta thay F = I trong Định lý 2.6, thuật toán (2.5) trở thành
(2.3) và hội tụ mạnh tới nghiệm có chuẩn nhỏ nhất của Bài toán (MSSFP).
Định lý 2.7. Giả sử rằng H là không gian Hilbert thực và F : H −→ H là ánh
xạ k-Lipschitz và η-đơn điệu mạnh. Gọi Ω là tập con lồi, đóng, khác rỗng của H1
và giả sử Ω ∩ Γ (cid:54)= ∅. Với mọi x0 ∈ H1, dãy lặp {xn} được sinh bởi
x0 ∈ Ω, y0
n = xn, n ≥ 0,
n , i = 1, 2, . . . , t,
n = Tiyi−1 yi
αiTiyi
xn+1 = PΩ
(2.11)
n)(cid:3),
n + (1 − εn)
t (cid:80) i=1
i sao cho
αi = 1, λn ∈ (0, 1], εn ∈ [0, 1],
(cid:2)(I − λnµF )(εnT[n+1]yt
t (cid:80) i=1
Ti = PCi(I − γF ), i = 1, 2, . . . , t, Tnmodt = PCn mod t(I − γF ) và γ ∈ (0, 2/L). Khi
trong đó αi > 0 với mọi
đó dãy {xn} được xác định bởi (2.11) hội thụ mạnh tới một phần tử trong Ω ∩ Γ,
(cid:104)F x∗, x − x∗(cid:105) ≥ 0, với mọi x ∈ Ω ∩ Γ.
dồng thời là nghiệm duy nhất của bài toán bất đẳng thức biến phân
(2.12)
Chứng minh. Đặt F = Ω∩Γ. Ta biết rằng PF x hoàn toàn xác định với mọi x ∈ H, vì F là tập con lồi và đóng của H1. Chúng ta chỉ ra rằng tồn tại duy nhất x∗ ∈ F
sao cho
x∗ = PF (I − µF )x∗
(2.13)
Từ Bổ đề 1.1 ta biết rằng I − µF là ánh xạ co và do đó PF (I − µF ) cũng là ánh
αiTiyi
xạ co trên H. Khi đó nguyên lý ánh xạ co Banach ta suy ra (2.13).
n + (1 − εn)
n, khi đó với mọi p ∈ F và n ≥ 0 thì
t (cid:80) i=1
(cid:107)y1
n − p(cid:107) = (cid:107)xk − p(cid:107),
n − T1p(cid:107) ≤ (cid:107)y0
n − p(cid:107) = (cid:107)T1y0
Ta viết un = εnT[n+1]yt
(cid:107)yi
n − p(cid:107) = (cid:107)Tiyi−1
n − Tip(cid:107) ≤ (cid:107)yi
n − p(cid:107)
và do đó
29
≤ . . . ≤ (cid:107)y0
n − p(cid:107) = (cid:107)xk − p(cid:107), i = 1, 2, . . . , t.
(2.14)
t (cid:88)
αiTiyt
(cid:107)un − p(cid:107)2 = εn(cid:107)T[n+1]yt
n − p(cid:107)2
n − p(cid:107)2 + (1 − εn)(cid:107)
i=1
t (cid:88)
αiTiyt
− εn(1 − εn)(cid:107)T[n+1]yt
n(cid:107)2
n −
≤ εn(cid:107)yt
i=1 n − p(cid:107)2
n − p(cid:107)2 + (1 − εn)(cid:107)yt
≤ (cid:107)xn − p(cid:107)2,
Từ Bổ đề 2.1 và (2.14) ta có
(cid:107)un − p(cid:107) ≤ (cid:107)xn − p(cid:107), với mọi n ≥ 0.
với mọi n ≥ 0. Do đó ta có
Phần còn lại của định lý được lập luận giống như chúng minh của Định lý 2.5.
Tương tự như trên, ta có định lý dưới đây.
Định lý 2.8. Giả sử rằng H là không gian Hilbert thực và F : H −→ H là ánh
H1. Với mọi x0 ∈ H1, dãy lặp được sinh bởi
xạ k-Lipschitz và η-đơn điệu mạnh. Gọi Ω là tập con lồi, đóng, khác rỗng của
x0 ∈ Ω,
αiTixn, n ≥ 0,
y0 n = εnT[n+1]xn + (1 − εn)
t (cid:80) i=1
n = Tiyi−1 yi
(2.15)
n , i = 1, 2, . . . , t, (cid:3), (cid:2)(I − λnµF )yt
xn+1 = PΩ
n
i sao cho
αi = 1, λn ∈ (0, 1], εn ∈ [0, 1],
t (cid:80) i=1
Ti = PCi(I − γF ), i = 1, 2, . . . , t, Tn mod t = PCn mod t(I − γF ) và γ ∈ (0, 2/L).
trong đó αi > 0 với mọi
Ω ∩ Γ nghiệm duy nhất của bài toán bất đẳng thức biến phân (2.12).
Khi đó dãy {xn} được xác định bởi (2.15) hội thụ mạnh tới một phần tử trong
Tiếp theo, ta có kết quả sau.
30
Định lý 2.9. Giả sử rằng H là không gian Hilbert thực và F : H −→ H là ánh
H1. Cho g : H1 → H1 là ánh xạ κ co với κ ∈ (0, k). Với mọi điểm x0 ∈ Ω, dãy lặp
{xn} được sinh bởi
xạ k-Lipschitz và η-đơn điệu mạnh. Cho Ω là tập con lồi, đóng, khác rỗng của
xn+1 = (1 − ωn)xn + ωnPΩ[λnµg(xn) + (I − λnµF )Bxn], n ≥ 0.
(2.16)
λn = 0,
λn = ∞,
trong đó {ωn} và {λn} là hai dãy trong đoạn [0, 1] thoả mãn điều kiện
∞ (cid:80) n=1
ωn,
(C1) lim n→∞
(C2) 0 < lim n→∞
với B được xác định như trong Định nghĩa 2.1. Khi đó dãy {xn} được xác định
bởi (2.16) hội thụ mạnh tới một phần tử trong Ω ∩ Γ, đồng thời là nghiệm duy
(cid:104)gx∗ − F x∗, x − x∗(cid:105) ≤ 0, với mọi x ∈ Ω ∩ Γ.
nhất của bài toán bất đẳng thức biến phân
(2.17)
Nếu g = 0 thì dãy {xn} hội tụ mạnh tới nghiệm của bài toán bất đẳng thức biến
phân (2.12).
Chứng minh. Đầu tiên ta sẽ chứng minh dãy {xn} bị chặn. Thật vậy, với z ∈ Γ,
(cid:107)Bxn − z(cid:107) ≤ (cid:107)xn − z(cid:107), với mọi n ≥ 0.
từ Định nghĩa 2.1 ta có
(cid:107)xn+1 − z(cid:107) ≤ (1 − ωn)(cid:107)xn − z(cid:107) + ωn(cid:107)λnµ(g(xn) − g(z))+
= (1 − ωnλn(τ − µκ))(cid:107)xn − z(cid:107) +
+ λnµ(g(z) − F (z)) + (I − λnµF )(B(xn) − z)(cid:107) µ(cid:107)g(z) − F (z)(cid:107) τ − µκ
}.
Hơn nữa từ (2.16) ta suy ra
µ(cid:107)g(z) − F (z)(cid:107) τ − µκ
(cid:54) max{(cid:107)xn − z(cid:107),
}.
(cid:107)xn − z(cid:107) ≤ max{(cid:107)x0 − z(cid:107),
µ(cid:107)g(z) − F (z)(cid:107) τ − µκ
Bằng quy nạp có thể thấy với mọi n ≥ 0 ta có:
31
Do đó {xn} bị chặn. Vì vậy ta suy ra được g(xn) cũng bị chặn.
Tiếp theo chúng ta chỉ ra rằng
(cid:107)xn+1 − xn(cid:107) = 0.
lim n→∞
(2.18)
Đặt W = 2PΩ − I, ta thấy rằng W là không giãn. Từ Định nghĩa 2.1 ta thấy tồn
tại một hằng số dương t ∈ (0, 1) sao cho B = (1 − t)I + tV , trong đó V là ánh xạ
không giãn. Khi đó ta có thể viết lại (2.16) như sau:
xn+1 = (cid:0)1 −
un,
ωn(1 + t) 2
ωn(1 + t 2
(2.19) (cid:1)xn +
,
un =
tV xn + (cid:98)zn + W ˜zn 1 + t
trong đó
(cid:98)zn = λnµg(xn) − λnµF Bxn, ˜zn = λnµg(xn) + (I − λnµF )Bxn.
< 1
Từ đó theo giả thiết (C1) và t ∈ (0, 1) ta suy ra rằng
≤ lim n→∞
ωn(1 + t) 2
ωn(1 + t) 2
0 < lim n→∞
(2.20)
(cid:107)(cid:98)zn+1 − (cid:98)zn(cid:107) ≤| λn+1 − λn | µ((cid:107)g(xn+1)(cid:107) + (cid:107)F Bxn+1(cid:107))
Do đó từ (2.1) và Định nghĩa 2.1 ta có
+ λnµ(κ + k)(cid:107)xn+1 − xn(cid:107),
(2.21)
(cid:107)˜zn+1 − ˜zn(cid:107) ≤| λn+1 − λn | µ((cid:107)g(xn+1)(cid:107) + (cid:107)F Bxn+1(cid:107))
và
+ (1 + λnµ(κ + k))(cid:107)xn+1 − xn(cid:107).
(2.22)
)(cid:107)xn+1 + xn(cid:107)
(cid:107)un+1 − un(cid:107) ≤ (1 +
λnµ(κ + k) 1 + t
+
| λn+1 − λn | µ((cid:107)g(xn+1)(cid:107) + (cid:107)F Bxn+1(cid:107)),
2 1 + t
Từ (2.21) và (2.17) ta thu được
(cid:107)un+1 − un(cid:107) − (cid:107)xn+1 − xn(cid:107) ≤
(cid:107)xn+1 + xn(cid:107)
λnµ(κ + k) 1 + t
có nghĩa là
32
+
| λn+1 − λn | µ((cid:107)g(xn+1)(cid:107) + (cid:107)F Bxn+1(cid:107)).
2 1 + t
Từ giả thiết (C1) ta dễ dàng nhận được
((cid:107)un+1 − un(cid:107) − (cid:107)xn+1 − xn(cid:107)) ≤ 0.
lim n→∞
(2.23)
Theo (C1) và (2.23) ta có dãy {un} bị chặn. Do đó từ (2.20), (2.23) và Bổ đề 1.4
(cid:107)un − xn(cid:107) = 0.
lim n→∞
ta thu được
Khi đó
(cid:107)un − xn(cid:107) = 0.
lim n→∞
(cid:107)xn+1 − xn(cid:107) = lim n→∞
ωn(1 + t) 2
(2.24)
(cid:107)xn − vn(cid:107) ≤ (cid:107)xn+1 − xn(cid:107) + (1 − ωn)|xn − vn(cid:107)
+ ωn(cid:107)λnµg(xn) − λnµF Bxn(cid:107).
Đặt vn = Bxn ta suy ra
(cid:107)xn − vn(cid:107) ≤
(cid:107)xn+1 − xn(cid:107) + λnµ(cid:107)g(xn) − F Bxn(cid:107).
1 ω n
Vì vậy ta có
Từ (2.24) và giả thiết (C1) ta có thể đưa ra
(cid:107)xn − vn(cid:107) = 0.
lim n→∞
(2.25)
Vì {xn} bị chặc nên tồn tại một dãy con của {xn} là {xni} sao cho xni (cid:42) x∗ khi i → ∞. Do đó chúng ta có thể giả sử rằng xn (cid:42) x∗ khi n → ∞. Từ (2.25) và Mệnh đề 1.12 ta có xn (cid:42) x∗ ∈ F ix(B).
Vì xn (cid:42) x∗ ∈ F ix(B) nên ta suy ra vn (cid:42) ˜x ∈ F ix(B). Do vậy
(cid:104)(g − F B)x∗, vn − x∗(cid:105) ≤ (cid:104)(g − F B)x∗, ˜x − x∗(cid:105) ≤ 0.
lim n→∞
(2.26)
(cid:107)xn+1 − x∗(cid:107) ≤ (1 − ωn)(cid:107)xn − x∗(cid:107)2 + ωn(cid:107)Bxn − x∗(cid:107)2 + ωnλ2
nµ2(cid:107)g(xn) − F Bxn(cid:107)2
+ 2ωnλnµ (cid:104)g(xn) − F Bxn, Bxn − x∗(cid:105) .
≤ (1 − ωn)(cid:107)xn − x∗(cid:107)2 + ωn(cid:107)Bxn − x∗(cid:107)2 + ωnλ2
nµ2(cid:107)g(xn) − F Bxn(cid:107)2
Cuối cùng, từ (2.16) ta có
33
+ 2ωnλnµ(cid:107)g(xn) − g(x∗)(cid:107)(cid:107)Bxn − x∗(cid:107)
− 2ωnλnµ(cid:107)F Bxn − F Bx∗(cid:107)(cid:107)Bxn − x∗(cid:107)
+ 2ωnλnµ (cid:104)g(x∗) − F Bx∗, Bxn − x∗(cid:105)
= (1 − σn)(cid:107)xn − x∗(cid:107)2 + σnδn,
δn =
(cid:107)g(xn) − F Bxn(cid:107)2 +
(cid:104)(g − F B)x∗, Bxn − x∗(cid:105) .
σn = 2ωnλnµ(k − κ), λnµ 2(L − κ)
1 k − κ
trong đó
δn ≤ 0. Áp dụng
σn = ∞ và lim n→∞
∞ (cid:80) n=1
Từ điều kiện (C1) và (2.26) rõ ràng rằng
Bổ đề 1.2 ta thu được (cid:107)xn − x∗(cid:107) → 0. Do đó ta có điều phải chứng minh.
Tương tự như Đinh lý 2.9 một thuật toán khác và sự hội tụ của nó cũng được
phát biểu trong định lý dưới đây.
Định lý 2.10. Giả sử rằng H là không gian Hilbert thực và F : H −→ H là ánh
xạ k-Lipschitz và η-đơn điệu mạnh. Gọi Ω là tập con lồi, đóng, khác rỗng của H.
Cho g : H1 → H1 là ánh xạ κ-co với κ ∈ (0, k). Với mọi điểm x0 ∈ Ω, dãy lặp được
sinh bởi
xn+1 = (1 − ωn)xn + ωnPΩ[λnµg(xn) + B(I − λnµF )xn], n ≥ 0.
(2.27)
λn = 0,
λn = ∞,
trong đó {ωn} và {λn} là hai dãy trong đoạn [0, 1] thoả mãn các điều kiện
∞ (cid:80) n=1
ωn,
(C1) lim n→∞
(C2) 0 < lim n→∞
với B được xác định như trong Định nghĩa 2.1. Khi đó dãy {xn} được xác định
bởi (2.27) hội thụ mạnh tới một phần tử trong Ω ∩ Γ, đồng thời là nghiệm duy
{xn} hội tụ mạnh tới nghiệm của bài toán bất đẳng thức biến phân (2.6).
nhất của bài toán bất đẳng thức biến phân (2.17). Đặc biệt, nếu g = 0 thì dãy
34
Kết luận
Luận văn đã trình bày lại một cách khá chi tiết và hệ thống về các
• Một số tính chất đặc trưng của không gian Hilbert, ánh xạ không giãn
vấn đề sau:
và bài toán tìm điểm bất động của ánh xạ không giãn trong không gian
• Bất đẳng thức biến phân và bất đẳng thức biến phân trên tập điểm bất
Hilbert;
• Các kết quả của Yang và các cộng sự cho bài toán bất đẳng thức biến phân
động (chung) của các ánh xạ không giãn trên không gian Hilbert;
trên tập nghiệm của bài toán chấp nhận tách đa tập trong không gian
Hilbert từ tài liệu [14].
35
Tài liệu tham khảo
[1] Agarwal R. P., O’Regan D., Sahu D. R. (2009), Fixed Point Theory for
Lipschitzian-type Mappings with Applications, Springer.
[2] Bauschke H.H., Combettes P.L. (2010), Convex Analysis and Monotone Op-
erator Theory in Hilbert spaces, Springer.
[3] Gou Y., Yu Y., Chen R. (2011), “Strong convergence theorem of the CQ
algorithm for the multiple-set feasibility problem”, International Conference
on future Computer sciences and application, pp. 61–64.
[4] Halpern B.(1967), "Fixed points of nonexpanding maps", Bull. Math. Soc.,
73, pp. 957–961.
[5] Hartman P., Stampacchia G. (1966), “On some nonlinear elliptic differential
functional equations” Acta Math., 115, pp. 271–310.
[6] He H., Liu S., Noor M. A. (2010), “Some Krasnosel’ski-Man algorithms and
the multiple-set split feasibility problem”, Fixed point theory and applica-
tions, DOI:10.1155/2010/513956.
[7] Kinderlehrer D., Stampacchia G. (1980), An introduction to variational in-
equalities and their applications, Academic Press, New York.
[8] Mann W. R. (1953), “Mean value methods in iteration”, Proc. Amer. Math.
Soc., 4, pp. 506-510.
[9] Moudafi A. (2000), “Vicosity approximation methods for fixed point prob-
lems”, J. Math. Anal. Appl., 241, pp. 45-55.
[10] Yamada I. (2001), “The hybrid steepest descent method for the variational
inequality problem over the intersection of fixed point sets of nonexpansive
36
mappings”, Inherently Parallel Algorithms in Feasibility and Optimization
and their Applications, 8, pp. 473-504.
[11] Xu H.K. (2006), “A variable Krasnosel’skii-Mann algorithm and the
multiple-set split feasibility problem”, Inverse Problems, 22, pp. 2021–2034.
[12] Xu H.K. (2010), “Iterative methods for the split feasibility problem in infinite
dimensional Hilbert spaces”, Inverse Problems, 26, 105018.
[13] Suzuki T. (2007), “A sufficient and necessary condition for Halpern-type
strong convergence to fixed points of nonexpansive mappings”, Proc. Amer.
Math. Soc., 135(1), pp. 99–106.
[14] Wang P., Zhou J., Wang R., Chen J. (2017), “Some explicit and strong
convergence hybrid algorithms for solving the multiple-sets split feasibility
problem”, International Journal of Discrete Mathematics, 2, pp. 80–87.
