..
ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
NGUYỄN THÀNH TRUNG
XẤP XỈ NGHIỆM CỦA MỘT LỚP BÀI TOÁN
BẤT ĐẲNG THỨC BIẾN PHÂN BA CẤP
LUẬN VĂN THẠC SĨ TOÁN HỌC
Chuyên ngành: Toán ứng dụng
Mã số: 60 46 01 12
NGƯỜI HƯỚNG DẪN KHOA HỌC
TS. Trương Minh Tuyên
Thái Nguyên – 2017
ii
Lời cảm ơn
Luận văn này được thực hiện tại Trường Đại học Khoa học - Đại học Thái
Nguyên và hoàn thành dưới sự hướng dẫn của TS. Trương Minh Tuyên.
Qua thời gian nghiên cứu và học tập tại trường Đại học Khoa học, Đại học
Thái Nguyên tác giả đã học tập được rất nhiều kiến thức chuyên ngành phục vụ
cho công tác giảng dạy và nghiên cứu của bản thân.
Tác giả xin được bày tỏ lòng biết ơn chân thành tới thầy hướng dẫn TS.
Trương Minh Tuyên đã dành nhiều thời gian hướng dẫn và chỉ bảo tác giả trong
suốt quá trình làm luận văn.
Tác giả cũng xin bày tỏ lòng biết ơn tới các thầy cô trong Ban giám hiệu, các
thầy cô của khoa Toán - Tin và các phòng chức năng của 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.
Cuối cùng, tôi xin gửi lời cảm ơn tới các bạn trong lớp K9HY, bạn bè và
người thân trong gia đình đã động viên, giúp đỡ tôi trong suốt thời gian qua.
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ị
3
1.1. Một số đặc trưng của không gian Hilbert . . . . . . . . . . . . . .
3
1.2. Bài toán tìm điểm bất động của ánh xạ không giãn . . . . . . . . 10
1.3. Bài toán bất đẳng thức biến phân cổ điển . . . . . . . . . . . . . 15
1.4. Bài toán bất đẳng thức biến phân trong không gian Hilbert
. . . 18
1.5. Một số bổ đề bổ trợ . . . . . . . . . . . . . . . . . . . . . . . . . . 21
Chương 2 Xấp xỉ nghiệm của một lớp bất đẳng thức biến phân ba
cấp
23
2.1. Phát biểu bài toán . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.2. Thuật toán . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
Kết luận
Tài liệu tham khảo
49
50
iv
Một số ký hiệu và viết tắt
H
không gian Hilbert
X
không gian Banach
h., .i
tích vô hướng trên H
k.k
chuẩn trên H
∪
phép hợp
∩
phép giao
R+
tập các số thực không âm
I
toán tử đồng nhất
∅
tập rỗng
∀x
với mọi x
∃x
tồn tại x
αn & α0
dãy số thực {αn } hội tụ giảm về α0
xn −→ x0
dãy {xn } hội tụ mạnh về x0
xn * x0
dãy {xn } hội tụ yếu về x0
1
Mở đầu
Bài toán "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 P.và Stampacchia G. vào năm
1966 trong tài liệu [6]. 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à Stampacchia G. xuất bản năm 1980
[7].
Từ đó, bài toán bất đẳng thức biên phân được nghiên cứu và phát triển mạnh
mẽ, thu hút sự được sự quan tâm của nhiều người làm toán trong và ngoài nước.
Một trong những hướng nghiên cứu quan trọng của bài toán bất đẳng thức biến
phân là việc xây dựng các phương pháp giải. Có nhiều phương pháp giải đã được
đề suất như phương pháp gradient, gradient tăng cường hay phương pháp điểm
bất động ...
Bài toán bất đẳng thức biến phân có dạng: Tìm một phần tử x∗ ∈ C, sao cho
hF (x∗ ), x − x∗ i ≥ 0, ∀x ∈ C,
trong đó F là một ánh xạ liên tục từ không gian Hilbert H vào chính nó, C là
tập con lồi và đóng trong H. Bài toán này có ý nghĩa quan trọng trong việc giải
bài toán tối ưu lồi có ràng buộc và một trường hợp đặc biệt là bài toán chấp
nhận lồi nổi tiếng. Khi tập chấp nhận được C là tập nghiệm của một bài toán
khác (tập điểm bất động của ánh xạ không giãn, tập không điểm của toán tử
đơn điệu, tập nghiệm của một bất đẳng thức biến phân khác ...) thì bài toán
trên còn được gọi là bài toán bất đẳng thức biến phân hai cấp. Trong trường hợp
bấy kỳ ta có thể xem C là tập điểm bất động của phép chiếu mêtric PC từ H lên
C, do đó bài toán trên luôn có thể xem như bài toán bất đẳng thức biến phân
2
trên tập điểm bất động của một ánh xạ không giãn PC . Như vậy có thể nói bài
toán bất đẳng thức biến phân nói chung hay bài toán bất đẳng thức biến phân
hai cấp nói riêng đóng vai trò quan trọng trong lĩnh vực giải tích phi tuyến.
Trong những năm gần đây, bài toán bất đẳng thức biến phân ba cấp
V I(A2 , V I(C, A1 )) với C là tập nghiệm của một bài toán khác cũng là một
chủ đề quan trọng trong lĩnh vực tối ưu hóa. Lớp các bài toán này hiện đang thu
hút đông đảo người làm toán trong và ngoài nước quan tâm nghiên cứu.
Mục đích của luận văn là trình bày lại kết quả của Ceng L.C., Ansari Q.H.,
Petrusel A. và Yao J.C. trong tài liệu [4] về sự kết hợp các phương pháp lặp
Mann, phương pháp xấp xỉ gắn kết và phương pháp đường dốc nhất cho bài
toán bất đẳng thức biến phân ba cấp, với miền chấp nhận được là tập nghiệm
của bất đẳng thức biến phân trên tập điểm bất động của một ánh xạ không giãn.
Nội dung chính của luận văn được chia làm hai chương. Chương 1 trình bày
về một số tính chất đặc trưng của không gian Hilbert thực, bài toán tìm điểm
bất động của ánh xạ không giãn, bài toán bất đẳng thức biến phân cổ điển cùng
với các bài toán liên quan trong không gian hữu hạn chiều Rn , bài toán bất đẳng
thức biến phân trong không gian Hilbert và cuối cùng là một số bổ đề bổ trợ cần
sử dụng đến trong chứng minh các định lý được đề cập trong Chương 2 của luận
văn. Chương 2 của luận văn trình bày về một thuật toán của Ceng L.C., Ansari
Q.H., Petrusel A. và Yao J.C. trong tài liệu [4] cùng với đó là ba định lý (với các
giả thiết khác nhau đặt lên các dãy tham số) về sự hội tụ mạnh của thuật toán
về một nghiệm của bài toán bất đẳng thức biến phân ba cấp trong không gian
Hilbert.
3
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ểm bất động của ánh xạ không giãn. Mục 1.3 trình bày về bài
toán bất đẳng thức biến phân cổ điển trong không gian hữu hạn chiều Rn và
các bài toán liên quan, Mục 1.4 giới thiệu về bài toán bất đẳng thức biến phân
trong không gian Hilbert. Mục 1.5 trình bày một số bổ đề cần sử dụng đến 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 [2] và [3].
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à h., .i và chuẩn được kí hiệu là k.k.
Mệnh đề 1.1 (Bất đẳng thức Schwars). Trong không gian Hilbert thực H ta
luôn có bất đẳng thức sau:
|hx, yi| ≤ kxk.kyk,
với mọi x, y ∈ H.
Chứng minh. Nếu y = 0 thì bất đẳng thức cần chứng minh hiển nhiên đúng.
Nếu y 6= 0, thì từ tính chất của tích vô hướng, ta có
hx + ty, x + tyi ≥ 0,
4
với mọi t ∈ R. Suy ra
kyk2 t2 + 2hx, yit + kxk2 ≥ 0 ∀t ∈ R.
Điều này xảy ra khi và chỉ khi
|hx, yi|2 ≤ kxk2 .kyk2 .
Từ đó ta nhận được điều phải chứng minh.
Mệnh đề 1.2 (Đẳng thức hình bình hành). Trong không gian Hilbert thực H ta
luôn có đẳng thức sau:
kx + yk2 + kx − yk2 = 2(kxk2 + kyk2 ),
với mọi x, y ∈ H.
Chứng minh. Ta luôn có
kx + yk2 = kxk2 + 2hxx, yi + kyk2 ,
kx − yk2 = kxk2 − 2hxx, yi + kyk2 .
Cộng hai đẳng thức trên ta nhận được điều phải chứng minh.
Mệnh đề 1.3. Trong không gian Hilbert thực H ta luôn có đẳng thức sau
kx − yk2 + kx − zk2 = ky − zk2 + 2hx − y, x − zi,
với mọi x, y, z ∈ H.
Chứng minh. Thật vậy, ta có
ky − zk2 + 2hx − y, x − zi = hy, yi + hz, zi + 2hx, xi − 2hx, zi − 2hx, yi
= [hx, xi − 2hx, yi + hy, yi]
+ [hx, xi − 2hx, zi + hz, zi]
= kx − yk2 + kx − zk2 .
Vậy ta được điều phải chứng minh.
5
Mệnh đề 1.4. Cho H là một không gian Hilbert thực. Khi đó, với mọi x, y ∈ H
và mọi λ ∈ [0, 1], ta có
kλx + (1 − λ)yk2 = λkxk2 + (1 − λ)kyk2 − λ(1 − λ)kx − yk2 .
(1.1)
Chứng minh. Ta có
kλx + (1 − λ)yk2 = λ2 kxk2 + 2λ(1 − λ)hx, yi + (1 − λ)2 kyk2
= λkxk2 + (1 − λ)kyk2 − λ(1 − λ)(kxk2 − 2hx, yi + kyk2 )
= λkxk2 + (1 − λ)kyk2 − λ(1 − λ)kx − yk2 .
Ta được điều phải chứng minh.
Mệnh đề 1.5. Trong không gian Hilbert thực H, ta luôn có
kx + yk2 ≤ kxk2 + 2hy, x + yi
với mọi x, y ∈ H.
Chứng minh. Với mọi x, y ∈ H, ta có
kx + yk2 = kxk2 + 2hx, yi + kyk2
≤ kxk2 + 2hx, yi + 2kyk2
= kxk2 + 2hy, x + yi.
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ề phần tử x ∈ H, nếu
lim hxn , yi = hx, yi,
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ì
xn * x. Tuy nhiên, điều ngược lại không đúng. Chẳng hạn xét không gian
P∞
2
2
l2 = {xn } ⊂ R :
n=1 |xn | < ∞ và {en } ⊂ l , được cho bởi
en = (0, ..., 0,
1
, 0, ..., 0, ...),
vị trí thứ n
6
với mọi n ≥ 1. Khi đó, en * 0, khi n → ∞. Thật vậy, với mỗi y ∈ H, từ bất
đẳng thức Bessel, ta có
∞
X
|hen , yi|2 < kyk2 < ∞.
n=1
Suy ra limn→∞ hen , yi = 0, tức là en * 0. Tuy nhiên, {en } không hội tụ về 0, vì
ken k = 1 với mọi n ≥ 1.
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.6. 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 * x, khi n → ∞. Khi đó, với mọi y ∈ H và y 6= x,
ta có
lim inf kxn − xk < lim inf kxn − yk.
n→∞
n→∞
(1.2)
Chứng minh. Vì xn * x, nên {xn } bị chặn.
Ta có
kxn − yk2 = kxn − xk2 + kx − yk2 + 2hxn − x, x − yi
> kxn − xk2 + 2hxn − x, x − yi.
Vì x 6= y, nên
lim inf kxn − yk2 > lim inf kxn − xk2 + 2hxn − x, x − yi
n→∞
n→∞
= lim inf kxn − xk2 .
n→∞
Do đó, ta nhận được
lim inf kxn − xk < lim inf kxn − yk.
n→∞
n→∞
Mệnh đề được chứng minh.
Mệnh đề 1.7. Mọi không gian Hilbert thực H đều có tính chất Kadec-Klee, tức
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 * x và
kxn k → kxk, thì xn → x, khi n → ∞.
7
Chứng minh. Ta có
kxn − xk2 = kxn k2 − 2hxn , xi + kxk2
→ 0, n → ∞.
Suy ra xn → x, khi n → ∞. Mệnh đề được chứng minh.
Mệnh đề 1.8. Cho C là một tập con lồi và đóng của không gian Hilbert thực
H. Khi đó, với mỗi x ∈ H, tồn tại duy nhất phần tử PC x ∈ C sao cho
kx − PC xk ≤ kx − yk với mọi y ∈ C.
Chứng minh. Thật vậy, đặt d = inf kx − uk. Khi đó, tồn tại {un } ⊂ C sao cho
u∈C
kx − un k −→ d, n −→ ∞. Từ đó ta có
kun − um k2 = k(x − un ) − (x − um )k
2
2
2
= 2kx − un k + 2kx − um k − 4kx −
2
un + um 2
k
2
2
≤ 2(kx − un k + kx − um k ) − 4d2
−→ 0,
khi n, m −→ ∞. Do đó {un } là dãy Cauchy trong H. Suy ra tồn tại u = lim un ∈
n→∞
C. Do chuẩn là hàm số liên tục nên kx − uk = d. Giả sử tồn tại v ∈ C sao cho
kx − vk = d. Ta có
2
ku − vk = k(x − u) − (x − v)k
2
u+v 2
= 2(kx − uk + kx − vk ) − 4kx −
k
2
≤ 0.
2
2
Suy ra u = v. Vậy tồn tại duy nhất một phần tử PC x ∈ C sao cho kx − PC xk =
inf u∈C kx − uk.
Định nghĩa 1.1. Phép cho tương ứng mỗi phần tử x ∈ H một phần tử PC x ∈ C
xác định như trên được gọi là phép chiếu mêtric từ H lên C.
Ví dụ 1.1. Cho C = {x ∈ H : hx, ui = y}, với u 6= 0. Khi đó
PC x = x +
y − hx, ui
kuk
2
u.
8
Ví dụ 1.2. Cho C = {x ∈ H : kx − ak ≤ R}, trong đó a ∈ H là một phần tử
cho trước và R là một số dương. Khi đó, ta có:
x nếu kx − ak ≤ R,
PC x =
R
a +
(x − a) nếu kx − ak > R.
kx − ak
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.
Mệnh đề 1.9. Cho C là tập con lồi, đóng và khác rỗng của không gian Hilbert
H. Cho PC : H −→ C là một ánh xạ. Khi đó, các phát biểu sau là tương đương:
a) PC là phép chiếu mêtric từ H lên C;
b) hy − PC x, x − PC xi ≤ 0 với mọi x ∈ H và y ∈ C.
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à kx −
PC xk = inf u∈C kx − uk. Với mọi x ∈ H, y ∈ C và với mọi α ∈ (0, 1), đặt
yα = αy + (1 − α)PC x. Vì C lồi nên yα ∈ C và do đó
kx − PC xk ≤ kyα − xk.
Điều này tương đương với
2
kx − PC xk ≤ kα(y − PC x) − (x − PC x)k
2
2
2
= α2 ky − PC xk + kx − PC xk − 2αhy − PC x, x − PC xi.
Từ đó, ta nhận được
2
2hy − PC x, x − PC xi ≤ αky − PC xk .
Cho α −→ 0+ , ta được hy − PC x, x − PC xi ≤ 0.
Ngược lại, giả sử b) đúng. Với mọi x ∈ H và mọi y ∈ C, ta có
kx − PC xk2 = kx − y + y − PC xk2
= kx − yk2 + 2hx − y, y − PC xi + ky − PC xk2
= kx − yk2 + 2hx − PC x, y − PC xi − ky − PC xk2
≤ kx − yk2 .
Do đó, kx − PC xk = inf u∈C kx − uk, hay PC là phép chiếu mêtric từ H lên C.
9
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:
a) với mọi x, y ∈ H, ta có
kPC x − PC yk2 ≤ hx − y, PC x − PC yi;
b) với mọi x ∈ H và y ∈ C, ta có
kx − yk2 ≥ kx − PC xk2 + ky − PC xk2 .
Chứng minh. a) Với mọi x, y ∈ H, từ Mệnh đề 1.9, ta có
hx − PC x, PC y − PC xi ≤ 0,
hy − PC y, PC x − PC yi ≤ 0.
Cộng hai bất đẳng thức trên ta nhận được điều phải chứng minh.
b) Với mọi x ∈ H và y ∈ C, từ Mệnh đề 1.9, ta có
hx − PC x, y − PC xi ≤ 0.
Từ đó, ta có
kx − yk2 = k(x − PC x) − (y − PC x)k2
= kx − PC xk2 + ky − PC xk2 − 2hx − PC x, y − PC xi
≥ kx − PC xk2 + ky − PC xk2 .
Hệ quả được chứng minh.
Mệnh đề 1.10. Nếu C là một tập con lồi và đóng của không gian Hilbert H,
thì C là tập đóng yếu.
Chứng minh. Trước hết, ta chỉ ra tồn tại một phần tử v ∈ H, v 6= 0 sao cho
suphv, yi ≤ hv, xi − kvk2 .
y∈C
10
Vì x ∈
/ C, nên v = x − PC x 6= 0. Từ Mệnh đề 1.9, ta có
hv, y − PC xi ≤ 0,
với mọi y ∈ C. Suy ra
hv, y − x + x − PC xi ≤ 0,
với mọi y ∈ C. Điều này tương đương với
hv, yi ≤ hv, xi − kvk2 ,
với mọi y ∈ C. Do đó
suphv, yi ≤ hv, xi − kvk2 .
y∈C
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
đóng yếu. Khi đó, tồn tại dãy {xn } trong C thỏa mãn xn * x, nhưng x ∈
/ C. Vì
C là tập lồi và đóng, nên theo chứng minh trên, ta có
hv, zi < hv, xi − ε,
với ε = kvk2 /2 và mọi z ∈ C. Đặc biệt
hv, xn i < hv, xi − ε,
với mọi n. Cho n → ∞, ta nhận được
hv, xi ≤ hv, xi − ε,
đ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.11. Mọi tập con bị chặn của H đều là tập compact tương đối yếu.
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
với mọi x, y ∈ C, ta có
kT x − T yk ≤ kx − yk.
11
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 ) = {x ∈ C : T x = x}.
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.12. 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 ) 6= ∅.
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
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
xn → x, khi n → ∞. Vì {xn } ⊂ F ix(T ), nên
kT xn − xn k = 0,
với mọi n ≥ 1. Từ tính liên tục của chuẩn, cho n → ∞, ta nhận được kT x − xk =
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.4 và tính
không giãn của T ta có
kT z − zk2 = kλ(T z − x) + (1 − λ)(T z − y)k2
= λkT z − xk2 + k(1 − λ)(T z − y)k2 − λ(1 − λ)kx − yk2
= λkT z − T xk2 + (1 − λ)k(T z − T y)k2 − λ(1 − λ)kx − yk2
≤ λkz − xk2 + (1 − λ)k(z − y)k2 − λ(1 − λ)kx − yk2
= kλ(z − x) + (1 − λ)(z − y)k2 = 0.
Suy ra T z = z và do đó z ∈ F ix(T ). Vậy F ix(T ) là một tập lồi.
Mệnh đề 1.13 (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
đó, 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 xn * x ∈ C và xn − T xn → y, thì x − T x = y. Đặc biệt, nếu y = 0 thì
x ∈ F ix(T ).
12
Chứng minh. Giả sử x − T x 6= y. Vì xn * x, nên xn − y * x − y. Do x − y 6= T x,
nên từ Mệnh đề 1.6, ta có
lim inf kxn − xk < lim inf kxn − y − T xk
n→∞
n→∞
≤ lim inf (kxn − T xn − yk + kT xn − T xk)
n→∞
≤ lim inf kxn − xk.
n→∞
Suy ra mâu thuẫn. Do đó, x − T x = y. Đặc biệt, nếu y = 0 thì x = T x hay
x ∈ F ix(T ).
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ó với F ix(T ) 6= ∅. Tìm
phần tử x∗ ∈ F ix(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 đường dốc nhấ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ì,
(1.3)
xn+1 = αn xn + (1 − αn )T xn , n ≥ 0,
P∞
ở đây {αn } là một dãy số thực thỏa mãn α0 = 1, 0 < αn < 1, n ≥ 1, 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,
P∞
nếu dãy {αn } được chọn thỏa mãn n=1 αn (1 − αn ) = ∞, thì dãy {xn } xác định
bởi (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, Halpern B. [5] đã đề xuất phương pháp lặp
(
x0 ∈ C là một phần tử bất kì,
xn+1 = αn u + (1 − αn )T xn ,
n≥0
(1.4)
13
ở đâ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 A.[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 các kết quả sau:
(1) Dãy {xn } ⊂ C xác định bởi:
x0 ∈ C, xn =
1
εn
T xn +
f (xn ), ∀n ≥ 0,
1 + εn
1 + εn
(1.5)
hội tụ mạnh về nghiệm duy nhất của bất đẳng thức biến phân:
x ∈ F (T ) sao cho h(I − f )(x), x − xi ≤ 0, ∀x ∈ F (T ),
trong đó {εn } là một dãy số dương hội tụ về 0.
(2) Với mỗi phần tử ban đầu z0 ∈ C, xác định dãy {zn } ⊂ C bởi:
εn
1
T zn +
f (zn ), ∀n ≥ 0.
(1.6)
1 + εn
1 + εn
1
P∞
1
− = 0, thì {zn } hội tụ
Nếu limn→∞ εn = 0,
n=1 εn = +∞ và limn→∞
εn+1 εn
mạnh về nghiệm duy nhất của bất đẳng thức biến phân:
zn+1 =
x ∈ F (T ) sao cho h(I − f )(x), x − xi ≤ 0, ∀x ∈ F (T ),
ở đây, f : C → C là một ánh xạ co cho trước với hệ số co c ∈ [0, 1). Tức là
kf (x) − f (y)k ≤ ckx − yk ∀x, y ∈ C.
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.
Phương pháp đường dốc
Xét bài toán tối ưu không ràng buộc
min{f (x) : x ∈ Rn }.
14
Ta sẽ xây dựng một dãy điểm x0 , x1 , x2 , ... sao cho f (xk+1 < f (xk )) với mọi
k = 0, 1, 2, ..., dãy {xk } hội tụ tới x∗ khi k → ∞ và 5f (x∗ ) = 0. Giả sử ta có
điểm xk thuộc lân cận của x∗ , khi đó để giảm hàm mục tiêu ta sẽ dịch chuyển
từ xk theo hướng dk tạo với véctơ gradient 5f (xk ) một góc tù, tức là xác định
xk+1 = xk + αk dk ,
trong đó αk > 0 và h5f (xk ), dk i < 0.
Thật vậy, khai triển hàm f (x) thành chuỗi Taylor tại điểm xk , ta được
f (x) = f (xk ) + αh5f (xk ), di +
α2 2
h5 f (xk )d, di,
2
∂f (x) ∂f (x)
∂f (x) T
,
, ...,
) , 52 f (x) =
∂x1
∂x2
∂xn
và xk = xk + θ(x − xk ) với θ ∈ (0, 1). Do đó, nếu h5f (xk ), dk i
trong đó 5f (x)
=
(
∂ 2 f (x)
)n×n
∂xi ∂xj
< 0, thì với
(
α > 0 đủ nhỏ ta có f (x) < f (xk ).
Việc lựa chọn hướng dịch chuyển dk và độ dài bước αk khác nhau sẽ cho ta
các phương pháp gradient khác nhau. Nếu chọn dk = − 5 f (xk ) với mọi k, thì
phương pháp gradient như thế được gọi là phương pháp đường dốc nhất (Steepest
descent method). Đây là một phương pháp thông dụng để tìm cực tiểu, nó rất
đơn giản và có thể áp dụng cho nhiều lớp hàm khác nhau. Theo phương pháp
này, dãy lặp {xk } được xác định như sau:
xk+1 = xk − αk 5 f (xk ), αk > 0, k = 0, 1, 2, ...
(1.7)
Vấn đề đặt ra là, trong phương pháp lặp (1.7) αk > 0 được xác định như thế
nào. Dưới đây, chúng tôi giới thiệu qui tắc Armijo để xác định αk tại mỗi bước
lặp:
1. Chọn giá trị α tùy ý (như nhau với mọi bước lặp, chẳng hạn α = 1) và xác
định điểm x = xk − α 5 f (xk );
2. Tính f (x) = f [xk − α 5 f (xk )];
3. Kiểm tra bất đẳng thức
f (x) − f (xk ) ≤ εαh5f (xk ), dk i = −εαk 5 f (xk )k2 ,
(1.8)
với 0 < ε < 1 là hằng số cho trước tùy ý và như nhau ở mỗi bước lặp;
15
4. Nếu (1.8) thỏa mãn thì α là giá trị cần tìm. Nếu (1.8) không thỏa mãn, thì
ta giảm α, bằng cách nhân α với một số λ ∈ (0, 1), chẳng hạn thay α bởi
α/2, cho đến khi bất đẳng thức (1.8) được thỏa mãn.
Năm 2007, Alber [1] đã đề xuất phương pháp đường dốc cho bài toán tìm
điểm bất động của một ánh xạ không giãn T trên tập con lồi và đóng C của
không gian Banach E, ở dạng sau:
xn+1 = PC (xn − µn (xn − T xn )), x0 ∈ C,
(1.9)
trong đó PC là ánh xạ co rút không giãn từ E lên C và đã chứng minh được
P∞
rằng, nếu µn > 0 với mọi n và n=0 µ2n < ∞ và {xn } bị chặn thì:
i) Tồn tại một điểm tụ yếu của {xn };
ii) Mọi điểm tụ yếu của {xn } đều thuộc F ix(T );
iii) Nếu F ix(T ) = {x∗ }, thì {xn } hội tụ yếu về x∗ .
Nhận xét 1.1. Nếu C ≡ E, thì (1.9) trở thành
xn+1 = xn − µn (xn − T xn ), n ≥ 0.
Trong trường hợp này, thì dn := xn − T xn và theo phương pháp này thì phần tử
xn+1 sẽ gần tập điểm bất động của T hơn so với điểm xn . Thật vậy, lấy bất kỳ
p ∈ F ix(T ), khi đó ta có
kxn+1 − pk = kxn − µn (xn − T xn ) − pk
= (1 − µn )kxn − pk + µn kT xn − T pk
≤ kxn − pk.
1.3.
Bài toán bất đẳng thức biến phân cổ điển
Trong mục này, chúng tôi đề cập đến bài toán bất đẳng thức biến phân trên
không gian hữu hạn chiều Rn và một số bài toán liên quan.
Cho C là một tập con lồi và đóng của Rn và F : C −→ Rn là một ánh xạ
liên tục. Bài toán bất đẳng thức biến phân cổ điển của ánh xạ đơn trị được phát
16
biểu như sau:
Tìm x∗ ∈ C sao cho
hF x∗ , x − x∗ i ≥ 0, ∀x ∈ C.
(1.10)
Tập hợp những điểm x∗ ∈ C thỏa mãn (1.10) được gọi là tập nghiệm của bài
toán và ký hiệu là V I(F, C).
Sự tồn tại nghiệm của bài toán (1.10) được cho bởi định lý dưới đây:
Định lí 1.1. Cho C là một tập lồi và compact trong Rn và F : C −→ Rn là
một ánh xạ liên tục. Khi đó, bài toán (1.10) có ít nhất một nghiệm.
Chứng minh. Đặt PC là phép chiếu mêtric từ Rn lên C. Khi đó, PC (I − γF )
là một ánh xạ liên tục từ C vào chính nó, với I là ánh xạ đồng nhất trên Rn
và γ > 0. Theo nguyên lý điểm bất động Brouwer, tồn tại x∗ ∈ C sao cho
PC (x∗ − γF (x∗ )) = x∗ . Theo Mệnh đề 1.9, hF x∗ , x − x∗ i ≥ 0 với mọi x ∈ C hay
x∗ là nghiệm của bài toán (1.10).
Bất đẳng thức biến phân cổ điển (1.10) có mối quan hệ mật thiết với một số
bài toán khác như là: Hệ phương trình, bài toán tối ưu, bài toán bù và bài toán
điểm bất động.
Hệ phương trình
Nhiều vấn đề cân bằng kinh tế cổ điển đã được mô hình như một hệ phương
trình, vì điều kiện thanh toán bù trừ thị trường, nhất thiết phải có sự cân bằng
giữa cung và cầu. Bài toán bất đẳng thức biến phân có thể xem như một hệ
phương trình thông qua mệnh đề dưới đây:
Mệnh đề 1.14. Phần tử x∗ ∈ Rn là nghiệm của bài toán V I(F, Rn ) khi và chỉ
khi F x∗ = 0.
Chứng minh. Nếu F x∗ = 0, thì hiển nhiên x∗ là một nghiệm của bài toán
V I(F, Rn ).
Ngược lại, giả sử x∗ là một nghiệm của bài toán V I(F, Rn ), tức là
hF x∗ , x − x∗ i ≥ 0,
với mọi x ∈ Rn . Chọn x = x∗ − F x∗ , ta được −kF x∗ k2 = 0, suy ra F x∗ = 0.
- Xem thêm -