ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC
——————–o0o——————–
NGUYỄN THỊ HỒNG VÂN
THUẬT TOÁN ĐIỂM GẦN KỀ VỚI DÃY SAI SỐ KHÔNG GIỚI NỘI TÌM KHÔNG ĐIỂM CỦA TOÁN TỬ ĐƠN ĐIỆU CỰC ĐẠI
LUẬN VĂN THẠC SĨ TOÁN HỌC
THÁI NGUYÊN - 2017
ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC
——————–o0o——————–
NGUYỄN THỊ HỒNG VÂN
THUẬT TOÁN ĐIỂM GẦN KỀ VỚI DÃY SAI SỐ KHÔNG GIỚI NỘI TÌM KHÔNG ĐIỂM CỦA TOÁN TỬ ĐƠN ĐIỆU CỰC ĐẠI
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
GIÁO VIÊN HƯỚNG DẪN GS. TS. NGUYỄN BƯỜNG
THÁI NGUYÊN - 2017
i
Mục lục
Bảng ký hiệu ii
Lời nói đầu 1
1 Một số bài toán liên quan
1.1 Không gian Hilbert . . . . . . . . . . . . . . . . . . . . . . 3 3
1.2 Bài toán cực tiểu phiếm hàm lồi trong không gian Hilbert . 10 . . . . . . . . . 13 1.3 Toán tử đơn điệu trong không gian Hilbert
1.4 Phương pháp điểm gần kề . . . . . . . . . . . . . . . . . . 18
2 Thuật toán điểm gần kề với dãy sai số không giới nội tìm
không điểm của toán tử đơn điệu cực đại 20 2.1 Thuật toán điểm gần kề . . . . . . . . . . . . . . . . . . . . 20
2.2 Thuật toán điểm gần kề mới . . . . . . . . . . . . . . . . . 25 2.3 So sánh hai thuật toán . . . . . . . . . . . . . . . . . . . . 27
3 Ứng dụng
30 3.1 Bài toán tối ưu . . . . . . . . . . . . . . . . . . . . . . . . 30
3.2 Bài toán bất đẳng thức biến phân . . . . . . . . . . . . . . 32
Kết luận 34
Tài liệu tham khảo 35
ii
Bảng ký hiệu
Trong toàn luận văn, ta dùng những ký hiệu với các ý nghĩa xác định
trong bảng dưới đây:
R tập số thực
Rn
không gian véc tơ n chiều tương ứng không gian Hilbert thực
toán tử đơn điệu trong không gian Hilbert miền xác định của toán tử A đồ thị của toán tử A miền hữu hiệu của hàm f tập trên đồ thị của hàm f tập tất cả không điểm của A, A−1(0) toán tử giải của toán tử T hình nón chuẩn tắc ứng với tập lồi C tập rỗng
H A dom A gra A domf epif zer(A) Jr,T NC ∅ (cid:104)x, y(cid:105) I
tích vô hướng của hai véc tơ x và y ánh xạ đơn vị
1
Lời nói đầu
Bài toán xác định không điểm của toán tử đơn điệu cực đại trong không
gian Hilbert có nhiều ý nghĩa quan trọng trong nhiều lĩnh vực khác nhau như: kinh tế, tối ưu hóa và các bài toán liên quan đến vật lý... Một trong
những phương pháp nổi bật để giải bài toán tìm không điểm của toán tử đơn điệu cực đại là phương pháp điểm gần kề được đề xuất nghiên cứu bởi Martinet cho cực tiểu phiếm hàm lồi trên Rn và sau này được mở rộng bởi Rockafellar.
xn+1 = Jγn(λnu + (1 − λn)(xn + en)), ∀n (cid:62) 0
Mới đây Boikanyo và Morosanu nghiên cứu sự hội tụ của thuật toán điểm gần kề với sai số cho toán tử đơn điệu cực đại A. Họ giả thiết tập không điểm của toán tử A là khác rỗng và dãy sai số (en) là giới nội. Trong đề tài luận văn này chúng tôi xét một dãy tạo bởi
và đưa ra điều kiện cần và đủ cho tập không điểm của A là khác rỗng. Chúng tôi cũng chỉ ra rằng dãy (xn) hội tụ mạnh đến phép chiếu của u lên A−1(0) không cần giả thiết tính giới nội của (en). Luận văn được trình bày thành 3 chương với nội dung chính sau:
I: Trong chương này trình bày một số kiến thức về khái niệm không gian Hilbert, một số ví dụ minh họa, bài toán cực tiểu phiếm hàm lồi
trong không gian Hilbert và thuật toán điểm gần kề cổ điển.
II: Trình bày hai thuật toán điểm gần kề và so sánh sự tối ưu của hai
thuật toán.
III: Trình bày về ứng dụng của thuật toán điểm gần kề trong bài toán
tối ưu và bài toán bất đẳng thức biến phân.
2
Luận văn này được hoàn thành tại Trường Đại học Khoa học - Đại học
Thái Nguyên dưới sự hướng dẫn tận tình của GS. TS. Nguyễn Bường, tác giả xin bày tỏ lòng biết ơn sâu sắc nhất tới thầy, người đã dành nhiều thời
gian và tâm huyết để hướng dẫn tận tình, giúp đỡ tác giả trong quá trình học tập, nghiên cứu và viết bản luận văn này.
Tác giả cũng xin chân thành cảm ơn Lãnh đạo Trường Đại học Khoa học - Đại học Thái Nguyên, Ban chủ nhiệm khoa Toán - Tin cùng toàn
thể các thầy cô trong và ngoài trường đã giảng dạy giúp tôi trau dồi thêm rất nhiều kiến thức phục vụ cho việc học tập và nghiên cứu của bản thân.
Đồng thời tác giả cũng xin gửi lời cảm ơn tới tập thể lớp cao học Toán
K9C (khóa 2015-2017) đã động viên và giúp đỡ tác giả rất nhiều trong quá trình học tập.
Cuối cùng tác giả xin gửi lời cảm ơn tới gia đình, bạn bè đã luôn động viên, giúp đỡ và tạo điều kiện tốt nhất cho tôi trong quá trình học tập,
nghiên cứu và làm luận văn. Xin chân thành cảm ơn!
Thái Nguyên, 29 tháng 9 năm 2017
Tác giả
Nguyễn Thị Hồng Vân
3
Chương 1
Một số bài toán liên quan
Chương này nhắc lại một số kiến thức về định nghĩa không gian Hilbert,
giải tích lồi và phương pháp điểm gần kề. Kiến thức chương này được tham khảo trong tài liệu [1], [2].
1.1 Không gian Hilbert
Định nghĩa 1.1.1 Một tập X được gọi là không gian tuyến tính trên R nếu với mỗi cặp (x, y) ∈ X × X, một phần tử của X, ta gọi là tổng của x và y, ký hiệu là x + y; với mỗi α ∈ R và x ∈ X, một phần tử của X gọi là tích của α và x, ký hiệu là αx thỏa mãn các điều kiện sau:
i. x + y = y + x với mọi x, y ∈ X (tính chất giao hoán).
ii. (x + y) + z = x + (y + z), với mọi x, y, z ∈ X (tính chất kết hợp).
iii. tồn tại phần tử không của X, ký hiệu 0, sao cho: x + 0 = 0 + x với
mọi x ∈ X.
x + (−x) = 0 với mọi x ∈ X.
iv. với mọi x ∈ X, tồn tại phần tử đối của x, ký hiệu là −x, sao cho
v. 1 · x = x · 1 = x, với mọi x ∈ X (1 là phần tử đơn vị).
vi. α(βx) = (αβ)x, với mọi α, β ∈ R, với mọi x ∈ X.
vii. (α + β)x = αx + βx, với mọi α, β ∈ R, với mọi x ∈ X.
viii. α(x + y) = αx + αy, với mọi α ∈ R, với mọi x, y ∈ X.
4
Định nghĩa 1.1.2 Cho H là một không gian tuyến tính trên trường số thực R. Tích vô hướng trên không gian H là một ánh xạ đi từ tích Descartes H × H vào R, ký hiệu là (cid:104)., .(cid:105), thỏa mãn các điều kiện sau:
i. (cid:104)x, y(cid:105) = (cid:104)y, x(cid:105) với mọi x, y ∈ H.
ii. (cid:104)x + y, z(cid:105) = (cid:104)x, z(cid:105) + (cid:104)y, z(cid:105) với mọi x, y, z ∈ H.
iii. (cid:104)αx, y(cid:105) = α(cid:104)x, y(cid:105) với mọi x, y ∈ H và mọi α ∈ R.
iv. (cid:104)x, x(cid:105) > 0 nếu x (cid:54)= 0 và (cid:104)x, x(cid:105) = 0 nếu x = 0.
Nhận xét 1.1.3 Từ Định nghĩa 1.1.2 ta suy ra
i. (cid:104)x, αy(cid:105) = α(cid:104)y, x(cid:105) với mọi x, y ∈ H và mọi α ∈ R.
ii. (cid:104)x, y + z(cid:105) = (cid:104)x, y(cid:105) + (cid:104)x, z(cid:105) với mọi x, y, z ∈ H.
Định nghĩa 1.1.4 Không gian tuyến tính H cùng với một tích vô hướng trên nó được gọi là một không gian tiền Hilbert.
Định lý 1.1.5 (bất đẳng thức Schwarz) Trong không gian tiền Hilbert H, với mọi x, y ∈ H ta luôn có bất đẳng thức sau:
|(cid:104)x, y(cid:105)|2 ≤ (cid:104)x, x(cid:105)(cid:104)y, y(cid:105).
(1.1)
0 ≤ (cid:104)x − αy, x − αy(cid:105) = (cid:104)x, x(cid:105) − 2α(cid:104)x, y(cid:105) + α2(cid:104)y, y(cid:105).
Chứng minh.Với mọi số thực α và với mọi x, y ∈ H ta có:
∆ = |(cid:104)x, y(cid:105)|2 − (cid:104)x, x(cid:105)(cid:104)y, y(cid:105) ≤ 0 với mọi x, y ∈ H.
Từ đây suy ra
|(cid:104)x, y(cid:105)|2 ≤ (cid:104)x, x(cid:105)(cid:104)y, y(cid:105) với mọi x, y ∈ H.
Hay
(cid:3)
Dấu đẳng thức trong bất đẳng thức (1.1) xảy ra khi và chỉ khi x và y
phụ thuộc tuyến tính.
5
Định lý 1.1.6 Không gian tiền Hilbert H là một không gian tuyến tính định chuẩn với chuẩn được xác định bởi
(cid:107)x(cid:107) =
(cid:104)x, x(cid:105)
(cid:113) (1.2) với mọi x ∈ H.
Chuẩn này được gọi là chuẩn cảm sinh từ tích vô hướng. Hàm số (cid:107)x(cid:107) = (cid:112)(cid:104)x, x(cid:105) với mọi x ∈ H là một chuẩn trên H. Chứng minh.Thật vậy, từ điều kiện (iv) của Định nghĩa 1.1.2 ta có (cid:107)x(cid:107) > 0 nếu x (cid:54)= 0 và (cid:107)x(cid:107) = 0 nếu x = 0 với x ∈ H. Từ điều kiện (i) và (iii) của Định nghĩa 1.1.2 ta suy ra (cid:107)αx(cid:107) = |α|.(cid:107)x(cid:107) với mọi α ∈ R và mọi x ∈ H. Từ bất đẳng thức Schwarz và cách định nghĩa chuẩn ta có:
|(cid:104)x, y(cid:105)| ≤ (cid:107)x(cid:107).(cid:107)y(cid:107) với mọi x, y ∈ H.
(1.3)
(cid:104)x + y, x + y(cid:105) = (cid:104)x, x(cid:105) + 2(cid:104)x, y(cid:105) + (cid:104)y, y(cid:105)
≤ (cid:107)x(cid:107)2 + 2(cid:107)x(cid:107).(cid:107)y(cid:107) + (cid:107)y(cid:107)2 = (cid:0)(cid:107)x(cid:107) + (cid:107)y(cid:107)(cid:1)2.
Từ đó với mọi x, y ∈ H ta có:
(cid:3) Suy ra (cid:107)x + y(cid:107) ≤ (cid:107)x(cid:107) + (cid:107)y(cid:107) với mọi x, y ∈ H.
Định nghĩa 1.1.7 Nếu H là một không gian tiền Hilbert thực và đầy đủ đối với chuẩn cảm sinh từ tích vô hướng xác định bởi (1.2) thì H được gọi là không gian Hilbert thực.
Ví dụ 1.1.8 Không gian
∞ (cid:88)
l2 =
x = {xn}n ∈ R :
|xn|2 < +∞
n=1
(cid:111) (cid:110)
∞ (cid:88)
(cid:104)x, y(cid:105) =
xnyn,
x = {xn}n∈N, y = {yn}n∈N ∈ l2
n=1
là không gian Hilbert với tích vô hướng
6
và chuẩn
∞ (cid:88)
(cid:107)x(cid:107) =
(cid:104)x, x(cid:105) =
|xn|2 =
|xn|2(cid:17) 1 2 .
n=1
n=1
(cid:113) (cid:16) ∞ (cid:88) (cid:118) (cid:117) (cid:117) (cid:116)
b
Ví dụ 1.1.9 Không gian L2[a, b] là không gian Hilbert với tích vô hướng:
(x, y) =
x(t)y(t)dt,
∀x, y ∈ L2 [a, b]
a
(cid:90)
2
|x(t)|2dt
.
(cid:107)x(cid:107) =
a
và chuẩn (cid:33) 1 (cid:32) b (cid:90)
Ví dụ 1.1.10 Gọi C[a, b] là tập tất cả các hàm giá trị thực liên tục trên khoảng đóng hữu hạn [a, b] ⊂ R. Trong C[a, b] xét tích vô hướng
(cid:104)x, y(cid:105) =
x(t)y(t).dt, x(t), y(t) ∈ C[a, b].
a
(cid:90) b
2
Không gian C[a, b] với chuẩn
(cid:107)x(cid:107) =
|x(t)|2dt
a
(cid:16) (cid:90) b (cid:17) 1
là không gian tiền Hilbert, nhưng không phải là không gian Hilbert.
(cid:104)xn, yn(cid:105) = (cid:104)x0, y0(cid:105).
lim n→∞
yn = y0 trong không gian Hilbert
xn = x0, lim n→∞
Định lý 1.1.11 Giả sử {xn}n∈N, {yn}n∈N là hai dãy lần lượt hội tụ mạnh đến x0, y0 trong không gian tiền Hilbert thực H. Khi đó,
Chứng minh. Giả sử lim n→∞ H. Ta sẽ chứng minh
(cid:104)xn, yn(cid:105) = (cid:104)x0, y0(cid:105)
lim n→∞
trong R.
7
|(cid:104)xn, yn(cid:105) − (cid:104)x0, y0(cid:105)| = |(cid:104)xn, yn(cid:105) + (cid:104)xn, y0(cid:105) − (cid:104)xn, y0(cid:105) − (cid:104)x0, y0(cid:105)|
≤ |(cid:104)xn, yn − y0(cid:105)| + |(cid:104)xn − x0, y0(cid:105)|
≤ (cid:107)xn(cid:107).(cid:107)yn − y0(cid:107) + (cid:107)xn − x0(cid:107).(cid:107)y0(cid:107).
Thật vậy,
(cid:104)xn, yn(cid:105) = (cid:104)x0, y0(cid:105).
lim n→∞
Vì dãy {xn}n∈N hội tụ trong H nên tồn tại một số M > 0 sao cho (cid:107)xn(cid:107) ≤ M với mọi n ∈ N. Do đó
(cid:3)
Nhận xét 1.1.12 Tích vô hướng là một phiếm hàm song tuyến tính liên tục trên H × H.
Định lý 1.1.13 Với mọi x, y thuộc không gian tiền Hilbert H, ta luôn có đẳng thức hình bình hành sau:
(cid:107)x + y(cid:107)2 + (cid:107)x − y(cid:107)2 = 2
(cid:107)x(cid:107)2 + (cid:107)y(cid:107)2(cid:17)
.
(cid:16)
(cid:107)x + y(cid:107)2 = (cid:104)x + y, x + y(cid:105) = (cid:107)x(cid:107)2 + (cid:107)y(cid:107)2 + 2(cid:104)x, y(cid:105)
Chứng minh. Với mọi x, y ∈ H, ta có
(cid:107)x − y(cid:107)2 = (cid:104)x − y, x − y(cid:105) = (cid:107)x(cid:107)2 + (cid:107)y(cid:107)2 − 2(cid:104)x, y(cid:105).
và
(cid:3) Cộng hai đẳng thức trên ta được đẳng thức cần chứng minh.
Áp dụng đẳng thức hình bình hành cho hai véc tơ x − y và x − z ta có
hệ quả sau.
Hệ quả 1.1.14 Cho H là một không gian tiền Hilbert và x, y, z ∈ H. Khi đó, ta có đẳng thức Apollonius:
(cid:107)x − y(cid:107)2 + (cid:107)x − z(cid:107)2(cid:17)
= 4
x −
2
+ (cid:107)y − z(cid:107)2.
y + z 2
(cid:16)
(cid:13) (cid:13) (cid:13) (cid:13) (cid:13) 2 (cid:13) (cid:13) (cid:13)
8
Nhận xét 1.1.15 (ý nghĩa của đẳng thức hình bình hành)
i. Đẳng thức trên nói lên một tính chất hình học: Tổng bình phương các cạnh của hình bình hành bằng tổng bình phương hai đường chéo.
ii. Từ định lý trên ta thấy, muốn đưa được tích vô hướng vào một không
gian định chuẩn thì không gian này phải thỏa mãn điều kiện hình bình hành. Ngược lại, nếu H là một không gian định chuẩn trong đó đẳng thức hình bình hành được thỏa mãn với mọi phần tử thuộc H thì trên H sẽ tồn tại một tích vô hướng (cid:104)., .(cid:105) sao cho chuẩn được xác định nhờ tích vô hướng. Điều này được thể hiện qua định lý sau.
Định lý 1.1.16 Giả sử (H, ||.||) là một không gian định chuẩn trên R trong đó đẳng thức hình bình hành nghiệm đúng với mọi x, y ∈ H. Nếu đặt
(cid:107)x + y(cid:107)2 − (cid:107)x − y(cid:107)2(cid:17)
,
(cid:104)x, y(cid:105) =
1 4
(cid:16) (1.4)
thì (cid:104)., .(cid:105) là một tích vô hướng trên H và ta có (cid:104)x, x(cid:105) = (cid:107)x(cid:107)2. Chứng minh. Ta chứng minh (cid:104)., .(cid:105) xác định như trên thỏa mãn các điều kiện trong định nghĩa về tích vô hướng. Thật vậy, các điều kiện (i) và (iv)
p(x, y) =
(cid:107)x + y(cid:107)2 − (cid:107)x − y(cid:107)2(cid:17)
.
1 4
trong Định nghĩa 1.1.2 hiển nhiên được thỏa mãn. Đặt (cid:16)
p(x, 0) = 0,
p(−x, y) = −p(x, y) ∀x, y ∈ H.
Để ý rằng, (cid:104)., .(cid:105) : H × H −→ R là một hàm liên tục và
4 (p(x, z) + p(y, z)) = (cid:107)x + z(cid:107)2 − (cid:107)x − z(cid:107)2 + (cid:107)y + z(cid:107)2 − (cid:107)y − z(cid:107)2
Với mọi x, y, z ∈ H ta có:
⇔ p(x, z) + p(y, z) = 2p
, z
.
(cid:19) (1.5) (cid:18)x + y 2
9
Trong đẳng thức (1.5) lấy y = 0 được
p(x, z) = 2p
, z
.
(cid:17) (1.6) (cid:16)x 2
2p
, z
= p(x + y, z).
Như vậy ta có: (cid:19)
(cid:18)x + y 2
2p(x, z) = p(2x, z),
∀x, y, z ∈ H.
Nghĩa là p(x, z) + p(y, z) = p(x + y, z). Vậy điều kiện (ii) trong Định nghĩa 1.1.2 được chứng minh. Thay thế x bằng 2x trong (1.6) ta được
p(nx, z) = np(x, z),
∀n ∈ N
Bằng quy nạp ta kiểm tra được
p(rx, z) = rp(x, z),
∀r ∈ Q và x, z ∈ H.
và bằng lập luận như trên ta có:
p(ax, z) = ap(x, z) ∀x, z ∈ H và a ∈ R.
Nhờ tính liên tục của chuẩn ||.|| suy ra hàm p(., z) liên tục, qua giới hạn ta có:
(cid:104)x, x(cid:105) = p(x, x) = (cid:107)x(cid:107)2 .
Vậy p(x, y) là một tích vô hướng trên H và hiển nhiên
(cid:3) Định lý được chứng minh.
n=1 trong không gian Hilbert H được
Định nghĩa 1.1.17 i. Dãy {xn}∞
(cid:104)xn, y(cid:105) = (cid:104)x, y(cid:105) với mọi y ∈ H.
lim n→∞
gọi là hội tụ yếu đến phần tử x ∈ H nếu
10
n=1 được gọi là hội tụ mạnh đến x ∈ H nếu
(cid:107)xn − x(cid:107) = 0.
lim n→∞
ii. Dãy {xn}∞
{xn} đến phần tử x ∈ H.
Ký hiệu xn (cid:42) x chỉ sự hội tụ yếu, xn → x chỉ sự hội tụ mạnh của dãy
Chú ý 1.1.18 i. Trong không gian Hilbert H, hội tụ mạnh kéo theo hội
tụ yếu, nhưng điều ngược lại không đúng.
ii. Mọi không gian Hilbert đều có tính chất Kadec–Klee, tức là nếu dãy {xn} trong không gian Hilbert H thỏa mãn các điều kiện (cid:107)xn(cid:107) → (cid:107)x(cid:107) và xn (cid:42) x, thì xn → x khi n → ∞.
(cid:107)xn − x0(cid:107)2 = (cid:104)xn − x0, xn − x0(cid:105)
= (cid:107)xn(cid:107)2 − (cid:104)x0, xn(cid:105) − (cid:104)xn, x0(cid:105) + (cid:107)x0(cid:107)2 .
Chứng minh. Thật vậy, trong không gian Hilbert nếu xn (cid:42) x0 và (cid:107)xn(cid:107) → (cid:107)x0(cid:107) thì xn → x0. Với mọi x, ta có:
(cid:107)xn(cid:107)2 = (cid:107)x0(cid:107)2,
(cid:104)xn, x0(cid:105) = (cid:107)x0(cid:107)2,
(cid:104)x0, xn(cid:105) = (cid:107)x0(cid:107)2.
lim x→∞
lim x→∞
lim x→∞
Từ giả thiết suy ra
(cid:107)xn − x0(cid:107)2 = (cid:107)x0(cid:107)2.
lim x→∞
Do đó
(cid:3)
1.2 Bài toán cực tiểu phiếm hàm lồi trong không gian Hilbert
∀x, y ∈ C, ∀λ ∈ [0, 1].
Định nghĩa 1.2.1 Một tập C ⊆ H được gọi là tập lồi nếu
11
∀x ∈ C, ∀λ > 0 ⇒ λx ∈ C.
Định nghĩa 1.2.2 i. một tập C ⊆ H được gọi là nón có đỉnh tại 0 nếu
ii. C được gọi là nón có đỉnh tại x0 nếu C − x0 là nón có đỉnh tại x0.
∀x, y ∈ C, ∀λ, µ > 0 ⇒ λx + µy ∈ C.
iii. Nón C có đỉnh tại x0 được gọi là nón lồi nếu C là tập lồi, nghĩa là
Cho C ⊂ H là tập lồi khác rỗng và ánh xạ f : C → R ∪ +∞. Ta có các
định nghĩa về hàm lồi như sau:
Định nghĩa 1.2.3 i. Trên đồ thị của hàm f, Kí hiệu là epif và được
epif := {(x, r) ∈ C × R : f (x) ≤ r}.
định nghĩa bởi công thức sau:
ii. Miền hữu hiệu của hàm f , kí hiệu là domf và được định nghĩa bởi
domf := {x ∈ C : f (x) < +∞}.
công thức sau:
Định nghĩa 1.2.4 Hàm f được gọi là chính phương nếu domf (cid:54)= 0 và f (x) > −∞ với mọi x ∈ C.
Định nghĩa 1.2.5 Hàm f : C → R được gọi là
f (λx + (1 − λ)y) ≤ λf (x) + f (λx + (1 − λ)f (y),
i. Lồi trên C nếu với mọi λ ∈ [0, 1], với mọi x, y ∈ C thì
f (λx + (1 − λ)y) ≤ λf (x) + f (λx + (1 − λ)f (y),
∀x, y ∈ C, x (cid:54)= y, ∀λ ∈ (0, 1).
ii. Lồi chặt trên C nếu
12
iii. Lồi mạnh trên C với hệ số α > 0 nếu với mọi x, y ∈ C, ∀λ ∈ (0, 1) ta
f (λx + (1 − λ)y) ≤ λf (x) + f (λx + (1 − λ)f (y)
−
λ(1 − λ)α (cid:107) x − y (cid:107)2 .
1 2
có:
iv. Lõm trên C nếu −f là hàm lõm trên C.
Định nghĩa 1.2.6 Giả sử f là hàm lồi trên H.
(cid:104)x∗, x − x(cid:105) ≤ f (x) − f (x), ∀x ∈ H.
i. Phiếm hàm x∗ ∈ H được gọi là dưới đạo hàm của hàm f tại x nếu
ii. Tập tất cả các dưới đạo hàm của f tại x được gọi là dưới vi phân của
∂f (x) := {x∗ ∈ H : (cid:104)x∗, x − x(cid:105) ≤ f (x) − f (x), ∀x ∈ H}.
hàm f tại x, kí hiệu là ∂f (x), một cách tương đương ta có:
iii. Hàm f được gọi là khả dưới vi phân tại x nếu ∂f (x) (cid:54)= 0.
Định nghĩa 1.2.7 Cho X, Y ∈ H và F : X → 2Y là ánh xạ từ X vào toàn bộ các tập con của Y (được kí hiệu là 2Y ). Khi đó ta nói F là ánh xạ đa trị từ X vào Y . Như vậy với mỗi x ∈ X, F (x) là một tập con của Y, (F (x) có thể là tập rỗng).
Định nghĩa 1.2.8 Ánh xạ đa trị F : H → 2H được gọi là:
i. Nửa liên tục trên tại x ∈ domF nếu với mọi tập mở V ⊂ F (x), tồn
F (x(cid:48)) ⊆ V, ∀x ∈ U.
tại lân cận mở U của x sao cho:
F (x) ⊆ V (cid:54)= 0, ∀x ∈ U ∩ domF.
ii. Nửa liên tục dưới tại x ∈ domF nếu với mọi tập mở V ⊂ H thỏa mãn
F nửa liên tục trên (nửa liên tục dưới) tại mọi điểm.
iii. Ánh xạ F được gọi là nửa liên tục trên (nửa liên tục dưới) trên H nếu
13
iv. F được gọi là liên tục tại x ∈ domF nếu F đồng thời nửa liên tục
trên và nửa liên tục dưới tại x.
v. Nếu trên F liên tục tại mọi điểm thuộc H thì F được gọi là liên tục
trên H.
1.3 Toán tử đơn điệu trong không gian Hilbert
Định nghĩa 1.3.1 Cho hai không gian tuyến tính X và Y . Một ánh xạ A : X → Y được gọi là ánh xạ tuyến tính hay toán tử tuyến tính nếu:
i. A(x1 + x2) = Ax1 + Ax2 với mọi x1, x2 ∈ X.
ii. A(αx) = αAx với mọi x ∈ X và mọi α ∈ R.
Chú ý 1.3.2 i. Điều kiện (i) và (ii) trong Định nghĩa 1.3.1 tương đương
A(α1x1 + α2x2 + ... + αkxk) = α1Ax1 + α2Ax2 + ... + αkAxk,
với:
với mọi xi ∈ X với mọi αi ∈ R, i = 1, . . . , k.
ii. Nếu Y ≡ X thì ta cũng nói A là toán tử trong X.
Ký hiệu R(A) là miền giá trị của toán tử A, tức là tập hợp các phần tử y ∈ Y sao cho y = Ax với một x ∈ X nào đó. Nếu y1, y2 ∈ R(A) thì α1y1 + α2y2 ∈ R(A) với mọi α1, α2 ∈ R nên R(A) là một không gian con của Y .
(cid:107)Ax(cid:107) ≤ K (cid:107)x(cid:107)
∀x ∈ X.
Định nghĩa 1.3.3 Một toán tử tuyến tính A từ X vào Y là liên tục khi và chỉ khi nó bị chặn (giới nội), nghĩa là tồn tại một hằng số dương K sao cho:
(cid:107)Ax(cid:107) ≤ K.
(cid:107)Ax(cid:107) (cid:107)x(cid:107)
= sup k(cid:54)=1
(cid:107)A(cid:107) = sup x(cid:54)=0
Định lý 1.3.4 Một toán tử tuyến tính A từ X vào Y được gọi là bị chặn (giới nội) nếu có một hằng số K > 0 sao cho:
14
S(a, r) = {x ∈ X : (cid:107)x − a(cid:107) = r}.
Ký hiệu mặt cầu tâm a bán kính r > 0 trong không gian X là S(a, r), nghĩa là
(cid:107)Ax(cid:107) ≤ (N + (cid:107)Ax0(cid:107))/α.
Hệ quả 1.3.5 Toán tử tuyến tính A bị chặn (liên tục) nếu tập các trị của nó trên một mặt cầu (tùy ý) bị chặn. Chứng minh. Thật vậy, giả sử (cid:107)Ax(cid:107) ≤ N với mọi x ∈ S(x0, α). Khi đó, với mọi x mà (cid:107)x(cid:107) = 1 thì αx + x0 ∈ S, cho nên A(αx + x0) ≤ N , và do đó (cid:107)Aαx + Ax0(cid:107) ≤ N hay α (cid:107)Ax(cid:107) ≤ N + (cid:107)Ax0(cid:107) . Từ đó suy ra
(cid:107)Ax(cid:107) ≤ K,
(cid:107)Ax(cid:107) (cid:107)x(cid:107)
= sup k(cid:54)=1
sup x(cid:54)=0
Vậy theo Định lý 1.3.4 ta có:
(cid:3) với K = (N + (cid:107)Ax0(cid:107))/α.
Ví dụ 1.3.6 Toán tử A : L2[0, 1] → L2[0, 1] xác định bởi
(Ax)(t) =
x(s)ds,
t ∈ [0, 1]
0
(cid:90) 1
t
2
là toán tử tuyến tính liên tục. Thật vậy, áp dụng Bất đẳng thức Bunhiacopxki ta có
1 (cid:90)
1 (cid:90)
≤
|x(s)| ds
x(s)ds
≤
|x(s)|2ds = (cid:107)x(cid:107)2,
(cid:90)
0
0
0
(cid:13) 2 (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) (cid:13) (cid:13)
2
t
1 (cid:90)
với mọi t ∈ [0, 1]. Suy ra, A bị chặn. Do đó
dt ≤ (cid:107)x(cid:107)2.
x(s)ds
(cid:90)
0
0
(cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12)
Suy ra, A bị chặn.
15
Dễ dàng thấy rằng, A là một toán tử tuyến tính. Do đó, A là toán tử tuyến (cid:3) tính liên tục.
k (cid:88)
Ví dụ 1.3.7 Cho X = Rk, Y = Rm, A(ξ1, ξ2, . . . , ξk) = (η1, η2, . . . , ηm) với
i = 1, 2, 3, . . . , m,
ηi =
aijξj
j=1
(1.7)
trong đó aij là những hằng số. Ma trận
a11 ... am1
. . . a1k ... . . . · · · amk
k (cid:88)
x =
ξjej
j=1
là ma trận của toán tử A. Thật vậy, (1.7) là dạng tổng quát của toán tử tuyến tính từ Rk vào Rm. Cho A là toán tử tuyến tính bất kì từ Rk vào Rm. Gọi e1, e2, . . . , ek và f1, f2, . . . , fk là các cơ sở của Rk và Rm sao cho với mọi x = (ξ1, ξ2, . . . , ξk)T ∈ Rk, y = (η1, η2, . . . , ηm)T ∈ Rm:
m (cid:88)
y =
ηifi,
i=1
và
e1 = (1, 0, . . . , 0)T , e2 = (0, 1, . . . , 0)T , . . . , ek = (0, 0, . . . , 1)T ,
f1 = (1, 0, . . . , 0)T , f2 = (0, 1, . . . , 0)T , . . . , fm = (0, 0, . . . , 1)T .
với
k (cid:88)
Ax =
ξj(Aej).
j=1
Vì A là toán tử tuyến tính nên
16
Ax = (η1, η2, . . . , ηm),
Aej = (a1j, a2j, . . . , amj)
Đặt
(cid:3) ta có (1.7).
Cho H là một không gian Hilbert thực, C là một tập con của H.
Định nghĩa 1.3.8 Cho C là một tập con lồi đóng, khác rỗng của không gian Hilbert thực H, A : C → H là một ánh xạ. Ánh xạ A được gọi là:
(cid:107)A(x) − A(y)(cid:107) ≤ L (cid:107)x − y(cid:107)
∀x, y ∈ C.
i. L-liên tục Lipschitz trên C, nếu tồn tại hằng số L > 0 sao cho
Nếu 0 < L < 1 thì A là ánh xạ co, nếu L = 1 thì A là ánh xạ không giãn.
ii. bị chặn trên C, nếu với mỗi tập con khác rỗng, bị chặn B của C, tồn
∀x, y ∈ B.
(cid:104)A(x) − A(y), x − y(cid:105) ≤ kB (cid:107)x − y(cid:107)
tại hằng số dương kB chỉ phụ thuộc vào tập B sao cho
iii. bị chặn Lipschitz trên C nếu với mỗi tập con bị chặn B của C, A là
ánh xạ liên tục Lipschitz trên B.
Định nghĩa 1.3.9 Cho C là một tập con lồi đóng, khác rỗng của không gian Hilbert thực H, A : C → H là một ánh xạ. Ánh xạ A được gọi là:
(cid:104)A(x) − A(y), x − y(cid:105) ≥ 0 ∀x, y ∈ C.
i. Đơn điệu trên C nếu
(cid:104)A(x) − A(y), x − y(cid:105) ≥ η (cid:107)x − y(cid:107)2
∀x, y ∈ C.
ii. η-đơn điệu mạnh trên C nếu tồn tại một hằng số η dương sao cho
17
iii. Hemi-liên tục (hemicontinuous) trên C nếu A(x + ty) (cid:42) Ax khi t → 0 với mọi x, y ∈ C và demi-liên tục (demicontinuous) trên C nếu từ xn → x suy ra Axn (cid:42) Ax khi n → ∞.
= +∞,
x ∈ C.
lim (cid:107)x(cid:107)→+∞
(cid:104)Ax, x(cid:105) (cid:107)x(cid:107)
iv. Bức trên C nếu
Sau đây là một kết quả của lý thuyết toán tử đơn điệu được dùng trong
Chương 2.
∀x ∈ X
(cid:104)A(x) − f, x − x0(cid:105) ≥ 0,
Bổ đề 1.3.10 Cho X là không gian Banach thực, X ∗ là không gian đối ngẫu của X, f ∈ X ∗ và A : X → X ∗ là một toán tử hemi-liên tục. Khi đó nếu tồn tại x0 ∈ X thỏa mãn bất đẳng thức:
∀x ∈ X.
(cid:104)A(x0) − f, x − x0(cid:105) ≥ 0,
thì x0 là nghiệm của phương trình A(x) = f . Nếu A là một toán tử đơn điệu trên X thì điều kiện trên tương đương với
Bổ đề 1.3.10 gọi là bổ đề Minty, tên một nhà toán học Mỹ, người đã
chứng minh kết quả trên trong trường hợp không gian Hilbert. Sau này chính ông và Browder đã chứng minh một cách độc lập cho không gian
Banach.
Với toán tử r : X → Y từ không gian Banach X vào không gian Banach Y , ta sẽ viết r(x) = o((cid:107)x(cid:107)) với x → θX, nếu r(x)/(cid:107)x(cid:107) → 0 khi x → θX. Kí hiệu L(X, Y ) là tập tất cả các toán tử tuyến tính liên tục T : X → Y .
A(x + h) = A(x) + T h + o((cid:107)h(cid:107)),
Định lý 1.3.11 Cho A : X → Y là một toán tử từ không gian Banach X vào không gian Banach Y . Toán tử A được gọi là khả vi Fréchet tại điểm x ∈ X, nếu tồn tại T ∈ L(X, Y ) sao cho
18
với mọi h thuộc một lân cận của điểm θ. Nếu tồn tại, thì T được gọi là đạo hàm Fréchet của A tại x và ta viết A(cid:48)(x) = T .
1.4 Phương pháp điểm gần kề
(cid:104)y2 − y1, x2 − x1(cid:105) ≥ 0,
Cho H là không gian Hilbert thực với vô hướng (cid:104)., .(cid:105) và chuẩn (cid:107).(cid:107). Chúng tôi kí hiệu hội tụ yếu trong H bởi (cid:42) và hội tụ mạnh bởi →. Một toán tử A : D(A) ⊆ H ⇒ H được gọi là đơn điệu nếu đồ thị của nó là một tập đơn điệu của H × H, tức là
với mọi x1, x2 ∈ D(A) và với mọi y1 ∈ Ax1 và y2 ∈ Ax2. A là toán tử đơn điệu cực đại nếu A là đơn điệu và đồ thị của A không nằm thực sự trong đồ thị của một toán tử đơn điệu bất kì khác. Chúng ta biết rằng trong không gian Hilbert thực điều này tương tự với toán tử (I + A), có R(I + A) = H.
Cho D ⊂ H là khác rỗng. A một toán tử T : D −→ H được gọi là
(cid:107)T (x) − T (y)(cid:107) (cid:54)(cid:107) x − y (cid:107),
không giãn nếu
với mọi x, y ∈ D. Đối với một toán tử đơn điệu cực đại A và với mỗi t > 0, toán tử Jt : H −→ H được xác định bởi Jt := (I + tA)−1(x) là đơn trị và không giãn trên H. Nó được gọi là toán tử giải của A. Xét bài toán đa trị sau:
(1.8)
Tìm ∈ D(A) sao cho 0 ∈ A(x).
xn+1 = Jγn(xn + en),
Một trong những phương pháp lặp hữu hiệu để giải (1.8) là thuật toán điểm gần kề. Thuật toán điểm gần kề xây dựng một dãy lặp (xn) như sau:
với mọi n (cid:62) 0, khi đó x0 ∈ H là điểm xuất phát cho trước (γn) ⊂ (0, +∞) và (en) là dãy sai số tính toán, thường được giới thiệu như là sai số thực nghiệm.
19
xn+1 = Jγn(λnu + (1 − λn)(xn + en)), ∀n (cid:62) 0.
Năm 2013, Boikanyo và Morosanu xét một dãy tạo bởi thuật toán sau:
Ở đây xo, u ∈ H, λn ∈ (0, 1), và γn ∈ (0, ∞), với mọi n ≥ 0. Họ chỉ ra rằng nếu A−1 (cid:54)= ∅ và λn −→ 1, γn −→ ∞ và (en) là giới nội, dãy (xn) hội tụ mạnh đến một phần tử của A−1(0), nó gần nhất đến điểm u. Kết luận: Chương 1 trình bày sơ lược về không gian tiền Hilbert, Không gian Hilbert đồng thời đưa ra một số ví dụ minh họa. Phát biểu bài toán
cực tiểu phiếm hàm lồi. Toán tử đơn điệu trong không gian Hilbert. Phương
pháp điểm gần kề cũng được trình bày trong chương này làm cơ sở cho việc nghiên cứu chương 2.
20
Chương 2
Thuật toán điểm gần kề với dãy sai
số không giới nội tìm không điểm
của toán tử đơn điệu cực đại
Chương này là nội dung chính của luận văn trình bày thuật toán điểm
gần kề với dãy sai số không giới nội tìm không điểm của toán tử đơn điệu cực đại. Mục 2.1 là Thuật toán điểm gần kề. Thuật toán điểm gần kề mới
được trình bày trong mục 2.2. So sánh hai thuật toán được trình bày trong mục 2.3. Những kiến thức chương này được tham khảo trong các tài liệu
[3]-[9].
2.1 Thuật toán điểm gần kề
Trong mục này, chúng tôi đưa ra điều kiện cần và đủ cho không điểm
của A là khác rỗng.
Bổ đề 2.1.1 Cho A : D(A) ⊆ H ⇒ H là một toán tử đơn điệu cực đại với A−1(0) = F (cid:54)= ∅ và cho bất kì u ∈ H, (I + tA)−1u → PF u khi t → +∞, ở đây, PF u là hình chiếu của u trên F.
(2.1)
xn+1 = Jγn(λnu + (1 − λn)(xn + en)),
Định lý 2.1.2 Cho A : D(A) ⊆ H ⇒ H là một toán tử đơn điệu cực đại. Với mọi x0, u ∈ H cố định, xét dãy (xn) xác định bởi
21
với mọi n (cid:62) 0. Trong đó λn ∈ (0, 1) và γn ∈ (0, +∞) với mọi n ≥ 0. Khi đó A−1(0) (cid:54)= ∅ khi và chỉ khi tồn tại dãy (λn) ⊂ (0, 1) và (γn) ⊂ (0, +∞) , với λn → 1 và γn → +∞ khi n → +∞, sao cho dãy ((1 − λn)en) giới nội và lim infn→∞((cid:107) xn+1 (cid:107) +(1 − λn) (cid:107) xn (cid:107)) < ∞ hay lim infn→∞((cid:107) xn+1 (cid:107) +(1 − λn) (cid:107) xn+1 − xn (cid:107)) < ∞.
Chứng minh. Giả sử A−1(0) (cid:54)= ∅ và cho p ∈ A−1(0). Từ (2.1) và toán
(cid:107) xm+1 − p (cid:107) =(cid:107) Jγm(λmu + (1 − λm)(xm + em)) − Jγm(p) (cid:107)
≤(cid:107) (λmu + (1 − λm)(xm + em) − p (cid:107)
(2.2)
≤ λm (cid:107) u − p (cid:107) +(1 − λm) (cid:107) em (cid:107)
+ (1 − λm) (cid:107) xm − p (cid:107) .
tử giải là không giãn, với mọi m ≥ 0, ta có:
(cid:107) xm+1 − p (cid:107) ≤ λn (cid:107) u − p (cid:107)
+ (1 − λn) (cid:107) en (cid:107) +(1 − λn) (cid:107) xn − p (cid:107)
≤ λn (cid:107) u − p (cid:107) (1 − λn) (cid:107) en (cid:107) +(1 − λn)
+
Từ bất đẳng thức trên, với mọi n ≥ 0, ta thu được:
(cid:104) λn−1 (cid:107) u − p (cid:107) +(1 − λn−1) (cid:107) en−1 (cid:107)
=
(cid:107) u − p (cid:107)
+
+ (1 − λn−1) (cid:107) xn−1 − p (cid:107) (cid:105) (cid:104) λn + λn−1(1 − λn) (cid:104) (1 − λn) (cid:107) en (cid:107)
(cid:105)
+ (1 − λn)(1 − λn−1) (cid:107) en−1 (cid:107)
+ (1 − λn)(1 − λn−1) (cid:107) xn−1 − p (cid:107)
≤
≤ .... (cid:104) λn + λn−1(1 − λn) + λn−2(1 − λn−1)(1 − λn)
+ ....
(cid:105)
22
(cid:107) u − p (cid:107)
+
(cid:105) + λ0(1 − λ1)...(1 − λn)
(2.3)
+ ....
(cid:104) (1 − λn) (cid:107) en (cid:107) +(1 − λn)(1 − λn−1) (cid:107) en−1 (cid:107)
+ (1 − λn)(1 − λn−1...(1 − λ0 (cid:107) e0 (cid:107)
+ (1 − λn)(1 − λn−1...(1 − λ0) (cid:107) x0 − p (cid:107) .
(cid:105)
(cid:107) xn+1 − p (cid:107) (cid:54)
1 + α + α2 + ... + αn(cid:105) (cid:104) (cid:104)
(cid:107) u − p (cid:107) M + M α + M α2 + ... + M αn(cid:105)
+
(2.4)
+
+ (cid:107) x0 − p (cid:107) .
+ αn (cid:107) x0 − p (cid:107) M 1 − α
Vì λn → 1 và (1 − λn)en giới nội, nên tồn tại 0 < α < 1 và M > 0 sao cho với mọi n ∈ N , ta có 1 − λn (cid:54) α và (1 − λn) (cid:107) en (cid:107)(cid:54) M . Vì vậy từ (2.3), ta có:
(cid:54) (cid:107) u − p (cid:107) 1 − α
((cid:107) xn+1 (cid:107) +(1 − λn) (cid:107) xn (cid:107)) < ∞.
lim inf n→∞
Bất đẳng thức này chỉ ra rằng (xn) giới nội và do đó
∈ A(xn+1),
λnu + (1 − λn)(xn + en) − xn+1 γn
Ngược lại, giả thiết lim infn→∞((cid:107) xn+1 (cid:107) +(1 − λn) (cid:107) xn (cid:107)) < ∞. Khi đó tồn tại một dãy (n(k)) của N sao cho (cid:107) xn(k)+1 (cid:107) +(1 − λn(k)) (cid:107) xn(k) (cid:107) giới nội. Vì thế tồn tại một dãy (m(l)) của (n(k)) như vậy xm(l)+1 (cid:42) p khi l → ∞ với p ∈ H. Tương tự ((1 − λm(l))xm(l)) là dãy giới nội. Bây giờ cho mỗi x ∈ D(A) và y ∈ A(x), vì
nên ta thu được:
y−
, x−xm(l)+1
λm(l)u + (1 − λm(l))(xm(l) + em(l)) − xm(l)+1 γm(l)
(cid:68) (cid:69) (cid:62) 0. (2.5)
23
→ 0,
λm(l)u + (1 − λm(l))(xm(l) + em(l)) − xm(l)+1 γm(l)
vì (1−λm(l))xm(l) và xm(l)+1 là giới nội nên λn → 1, γn → ∞ và ((1−λn)en) giới nội, dẫn đến:
(cid:104)y, x − p(cid:105) (cid:62) 0.
khi l → ∞. Bây giờ, cho l → ∞ trong biểu thức (2.5), ta thu được:
Do đó, do tính cực đại của A, ta suy ra p ∈ D(A) và 0 ∈ A(p). Định lý (cid:3) được chứng minh hoàn thành.
Nhận xét 2.1.3 Từ chứng minh Định lý 2.1.2 chỉ ra rằng A−1(0) (cid:54)= ∅ khi và chỉ khi (xn) giới nội.
Hệ quả 2.1.4 Cho A : D(A) ⊆ H ⇒ H là một toán tử đơn điệu cực đại. Với mọi x0, u ∈ H cố định, cho dãy (xn) được xác định bởi (2.1), trong đó λn ∈ (0, 1) và γn ∈ (0, +∞) với mọi n (cid:62) 0. Giả sử tồn tại hai dãy (λn) ⊂ (0, 1) và (γn) ⊂ (0, +∞) với λn → 1 và γn → +∞ khi n → +∞, sao cho dãy ((1 − λn)en) giới nội. Khi đó A−1(0) (cid:54)= ∅ nếu lim infx→∞ (cid:107) xn (cid:107)< ∞ và dãy (xn+1 − xn) giới nội.
Chứng minh. Chứng minh của Hệ quả 2.1.4 được sinh ra từ Định lý
((cid:107) xn+1 (cid:107) +(1 − λn) (cid:107) xn+1 − xn (cid:107)) < ∞.
lim inf n→∞
2.1.2, và trong trường hợp này, ta có điều kiện
(cid:3)
Định lý sau mở rộng kết quả trước đó của Boikanyo và Morosanu. chú ý
rằng, kết quả của Boikanyo và Morosanu thu được với giả thiết tập không điểm của A là khác rỗng và dãy sai số (en) là giới nội.
Định lý 2.1.5 Giả sử A : D(A) ⊆ H ⇒ H là toán tử đơn điệu cực đại. Với mọi x0, u ∈ H, cho dãy (xn) được xác định bởi (2.1), ở đây λn ∈ (0, 1) và γn ∈ (0, +∞) với mọi n (cid:62) 0. Nếu λn → 1, γn → +∞ và
24
((1 − λn)en) → 0 khi n → +∞ thì (xn) hội tụ mạnh đến PF u, phép chiếu metric của u lên F := A−1(0), khi và chỉ khi
((cid:107) xn+1 (cid:107) +(1 − λn) (cid:107) xn (cid:107)< ∞.
lim inf n→∞
(cid:107) xn+1 − PF u (cid:107) (cid:54)(cid:107) xn+1 − Jγnu (cid:107) + (cid:107) Jγnu − PF u (cid:107)
=(cid:107) Jγn(γnu + (1 − λn)(xn + en)) − Jγnu (cid:107)
+ (cid:107) Jγnu − PF u (cid:107)
(2.6)
≤ (1 − λn) (cid:107) xn − u + en (cid:107) + (cid:107) Jγnu − PF u (cid:107) ≤ (1 − λn) (cid:107) xn − u (cid:107) +(1 − λn) (cid:107) en (cid:107)
+ (cid:107) Jγnu − PF u (cid:107) .
Chứng minh. Chúng ta biết từ Định lý 2.1.2 và Nhận xét 2.1.3 cho thấy A−1(0) (cid:54)= ∅ và dãy (xn) giới nội. Hơn nữa, từ (2.1), ta có:
Khi đó bất đẳng thức thứ hai suy ra từ toán tử giải là không giãn. Kết quả được suy ra ngay bằng cách sử dụng Bổ đề 2.1.1 và cho n → +∞ trong (cid:3) bất đẳng thức trên.
,
λn := 1 −
1 (n + 1)((cid:107) en (cid:107) +1)
Nhận xét 2.1.6 Cho mỗi dãy (en) trong H (không nhất thiết phải giới nội), tồn tại dãy (λn) trong (0, 1) như vậy λn → 1 và ((1 − λn)en → 0 khi n → +∞ . Ta xét ví dụ:
với mọi n (cid:62) 0. Vì với mọi toán tử đơn điệu cực đại A : D(A) ⊆ H ⇒ H trong không gian Hilbert thực H với A−1(0) (cid:54)= ∅, suy ra tương tự dãy hội tụ mạnh mẽ trong phép chiếu metric của u lên A−1(0), khi đó γn ∈ (0, +∞) với mọi n (cid:62) 0 và γn → +∞ khi n → +∞.
1 −
u +
.
(xn + en)
xn+1 = Jγn
1 (n + 1)((cid:107) en (cid:107) +1)
1 (n + 1)((cid:107) en (cid:107) +1)
(cid:16)(cid:16) (cid:17) (cid:17)
25
Từ ví dụ sau chỉ ra rằng, nếu A−1(0) = ∅, thì dãy (xn) không giới nội.
(2.7)
λnu + (1 − λn)(xn + en) = xn+1 − γne−xn+1.
Ví dụ 2.1.1 Cho H = R và A : H → H được định nghĩa bởi Ax = −e−x. Rõ ràng, A là đơn điệu cực đại và A−1(0) (cid:54)= ∅. Cho mỗi x0, u ∈ H cho dãy (xn) được sinh ra bởi (2.1). Suy ra
Nếu cho hai dãy (λn) và (γn) với λn → 1 γn → ∞ và (1 − λn)en → 0, dãy (xn) giới nội, từ (2.7), suy ra được: lim supn→∞ γne−xn+1 ≤| u | +supn(cid:62)0 | xn |< +∞. Để tạo ra γn → ∞, ta cần phải có limn→∞e−xn+1 = 0 và vì xn+1 → ∞, điều này là mâu thuẫn. Vì thế (xn) là không giới nội.
2.2 Thuật toán điểm gần kề mới
Trong mục này chúng tôi giới thiệu một thuật toán mới và cho thấy dãy (yn) hội tụ mạnh mẽ lên PF u. Đầu tiên chúng tôi đưa ra điều kiện cần và đủ cho tập không điểm của A là khác rỗng.
(2.8)
yn+1 = Jγn(λnu + (1 − λn)(y0 + en)),
Định lý 2.2.1 Cho A : D(A) ⊆ H ⇒ H là đơn điệu cực đại. Với mọi điểm cố định y0, u ∈ H, cho dãy (yn) xác định bởi
với mọi n (cid:62) 0, trong đó λn ∈ (0, 1) và γn ∈ (0, +∞) với mọi n (cid:62) 0. Khi đó A−1(0) (cid:54)= ∅ khi và chỉ khi tồn tại hai dãy (λn) ⊂ (0, 1) và (γn) ⊂ (0, +∞) với λn → 1 và γn → +∞ khi n → +∞, sao cho dãy ((1 − λn)en) giới nội và lim infn→∞ (cid:107) yn (cid:107)< ∞.
(cid:107) ym+1 − p (cid:107) =(cid:107) Jγm(λmu + (1 − λm)(y0 + em)) − Jγm(p) (cid:107) ≤(cid:107) λmu + (1 − λm)(y0 + em) − p (cid:107)
(2.9)
≤ λm (cid:107) u − p (cid:107) +(1 − λm) (cid:107) em (cid:107)
+ (1 − λm) (cid:107) y0 − p (cid:107) .
Chứng minh. Giả sử A−1(0) (cid:54)= ∅ và cho p ∈ A−1(0). Từ (2.8) và thực tế là toán tử giải là không giãn, với mọi m (cid:62) 0 ta có:
26
(cid:107)yn(cid:107) < ∞.
lim inf n→∞
Bất đẳng thức cho thấy dãy (yn) giới nội vì
inf (cid:107) yn (cid:107)< ∞. Khi đó tồn tại dãy con (n(k)) của N như vậy (yn(k)) giới nội. Vì thế tồn tại một dãy con (m(l)) của (n(k)) như vậy ym(l) (cid:42) p khi l → ∞, cho một số p ∈ H. Bây giờ cho mỗi số x ∈ D(A) và y ∈ A(x), khi đó
∈ A(yn+1),
λnu + (1 − λn)(y0 + en) − yn+1 γn
Ngược lại, giả thiết lim x→∞
ta được
y−
, x−ym(l)
λm(l)−1u + (1 − λm(l−1))(y0 + em(l)−1) − ym(l) γm(l)−1
(cid:68) (cid:69) (cid:62) 0. (2.10)
→ 0,
λm(l)−1u + (1 − λm(l−1))(y0 + em(l)−1) − ym(l) γm(l)−1
Khi đó λn → 1, γn → +∞ và ((1 − λn)en) giới nội , suy ra
(cid:104)y, x − p(cid:105) (cid:62) 0.
khi l → ∞. Lúc này l → ∞ trong (2.10), ta được:
Vì thế từ giá trị lớn nhất của A, ta có kết luận p ∈ D(A) và 0 ∈ A(p). (cid:3)
Nhận xét 2.2.2 Từ chứng minh ở Định lý 2.2.1 cho thấy A−1(0) (cid:54)= ∅, khi và chỉ khi (yn) giới nội.
Định lý 2.2.3 Cho A : D(A) ⊆ H ⇒ H là một toán tử đơn điệu cực đại, với mọi y0, u ∈ H cho dãy (yn) xác định bởi (2.8), trong đó λn ∈ (0, 1) và γn ∈ (0, +∞) với mọi n (cid:62) 0. Nếu λn → 1, γn → +∞ và ((1 − λn)en) → 0 khi n → +∞ thì (yn) hội tụ mạnh đến PF u, hình chiếu của của u trên F : A−1(0), khi và chỉ khi limn→∞ (cid:107) yn (cid:107)< ∞.
27
Chứng minh. Chứng minh được thực hiện như chứng minh Định lý 2.1.5 (cid:3) và vì thế chúng tôi bỏ qua chứng minh điều này.
2.3 So sánh hai thuật toán
Dựa vào các định lý chúng tôi sẽ so sánh hai thuật toán (2.1) và (2.8).
Định lý 2.3.1 Cho (xn) và (yn) được sinh ra tương ứng bởi (2.1) và (2.8), nếu 1 > λn ≥ α > 0, cho một số α > 0 và tất cả n ≥ 0, khi đó (xn) giới nội khi và chỉ khi (yn) giới nội.
(2.11)
(cid:107) yn+1 − xn+1 (cid:107)≤ (1 − λn) (cid:107) y0 − xn (cid:107)
Chứng minh. Giả thiết (xn) giới nội. Với mọi n ≥ 0,
(cid:107) ym+1 − xm+1 (cid:107) ≤ (1 − λm) (cid:107) y0 − xm (cid:107)
≤ (1 − λm) (cid:107) y0 − ym (cid:107) +(1 − λm) (cid:107) ym − xm (cid:107)
≤ (1 − λm)M + (1 − λm) (cid:107) ym − xm (cid:107) .
và dẫn đến (yn) giới nội. Ngược lại, giả thiết (yn) giới nội. Khi đó tồn tại β ∈ (0, 1) và M > 0 như vậy (cid:107) y0 − yn (cid:107)≤ M và 1 − λn < β với nọi n ≥ 0. Vì vậy, với mọi m ≥ 0, ta có:
(cid:107) yn+1 − xn+1 (cid:107) ≤ (1 − λn)M + (1 − λn) (cid:107) yn − xn (cid:107)
≤ (1 − λn)M + (1 − λn)(1 − λn−1)M
+ (1 − λn)(1 − λn−1) (cid:107) yn−1 − xn−1 (cid:107)
M
Sử dụng bất đẳng thức trên, bằng phương pháp quy nạp toán học, với mọi n ≥ 0, ta được
+ (1 − λn)(1 − λn−1) (cid:107) yn−1 − xn−1 (cid:107)
≤ ....
(cid:104) = (1 − λn) (cid:105) 1 + (1 − λn−1)
(cid:104) 1 + (1 − λn−1) ≤ (1 − λn)
28
+ (1 − λn−1)(1 − λn−2) + ...
+ (1 − λn)(1 − λn−1)...(1 − λ0) (cid:107) y0 − x0 (cid:107)
(2.12)
≤ (1 − λn)(1 + β + β2 + ...)M
+ βn+1 (cid:107) y0 − x0 (cid:107)
≤ (1 − λn)
+ βn+1 (cid:107) y0 − x0 (cid:107) .
1 1 − β
(cid:105) M + (1 − λn−1)(1 − λn−2)...(1 − λ0)
(cid:3) Từ bất đẳng thức này cho thấy (xn) giới nội.
Định lý 2.3.2 Cho (xn) và (yn) được xác định bởi (2.1) và (2.8), tương ứng. Nếu λn → 1, khi n → +∞ thì (xn) hội tụ mạnh đến PF u khi và chỉ khi (yn) hội tụ mạnh đến PF u.
Chứng minh. Nếu (xn) hội tụ mạnh đến PF u, khi đó từ (2.11) ta thấy (yn) hội tụ mạnh đến PF u. Ngược lại, nếu (yn) hội tụ mạnh đến PF u, lúc này n → +∞ trong (2.12), (cid:3) ta có kết luận (xn) hội tụ mạnh đến PF u.
Từ ví dụ sau cho thấy tốc độ hội tụ của hai thuật toán là không thể so sánh được và vì vậy tùy thuộc vào bài toán đem xét, ta có thể chỉ ra cái
1 − 1
| xn+1 − 1 |=
n − xn n2 1 + n
này thuận tiện hơn cái kia. Ví dụ 2.3.1 Cho A : R −→ R định nghĩa bởi Ax = x − 1. Rõ ràng 1 A−1(0) = {1}. Cho λn = 1 − n2 ,γn = n và en = n. Bằng cách lấy x0 = y0 = u = 0, ta có:
.
| yn+1 − 1 |=
1 − 1 n 1 + n
và
Vì vậy | xn+1 − 1 |(cid:54)| yn+1 − 1 |. Mặt khác, bằng cách lấy x0 = y0 = 2 và
29
u = 0, ta có:
1 − 1
| xn+1 − 1 |=
n − xn n2 1 + n
1 − 1
n − 2 n2
.
| yn+1 − 1 |=
1 + n
và
n2 . Ta có | yn+1 − 1 |(cid:54)| xn+1 − 1 | với mọi n (cid:62) N0.
n2 < 2
Từ đó xn → 1 khi n → +∞, khi đó tồn tại một số No ∈ N như vậy với mọi n (cid:62) N0, xn
Kết luận: Trong chương 2 chúng tôi trình bày hai thuật toán điểm gần
kề và so sánh sự hội tụ của hai thuật toán.
30
Chương 3
Ứng dụng
Trong chương này chúng tôi trình bày về ứng dụng của thuật toán điểm
gần kề cho bài toán tối ưu và bài toán bất đẳng thức biến phân.
3.1 Bài toán tối ưu
Cho H là một không gian Hilbert thực và f : H −→ (−∞, +∞) là một hàm lồi chính phương và nửa liên tục dưới. Chúng ta biết [4] A = ∂f là toán tử đơn điệu cực đại trong H và tập không điểm của A trùng với tập các điểm cực tiểu của f . Khi đó các Định lý 2.1.5 và 2.2.3 cho ta lược đồ xấp xỉ tìm một điểm cực tiểu của f .
Định lý 3.1.1 Cho H là một không gian Hilbert thực và f : H −→ (−∞, +∞) là một hàm lồi chính phương và nửa liên tục dưới. Với mọi x0, u ∈ H, cho dãy (xn) xác định bởi (2.1) với A = ∂f , trong đó λn ∈ (0, 1) và γn ∈ (0, +∞) với mọi n ≥ 0. Nếu λn → 1 và γn → +∞ và ((1 − λn)en) → 0 khi n → +∞, thì (xn) hội tụ mạnh mẽ đến PF u, hình chiếu của u trên F := ∂f −1(0) = argminf , khi và chỉ khi (xn) giới nội.
Chứng minh. Khi đó A = ∂f là một toán tử đơn điệu cực đại, điều này (cid:3) được chướng minh từ Định lý 2.1.5.
Định lý 3.1.2 Cho H là một không gian Hilbert thực và f : H −→ (−∞, +∞) là một hàm lồi chính phương và nửa liên tục dưới. Cho y0, u ∈ H, ε > 0 và dãy (yn) xác định bởi (2.8) với A = ∂f , trong đó λn ∈ (0, 1)
31
w0 = y0
wn = λnu + (1 − λn)(w0 + en) − γnzn,
và γn ∈ (0, +∞) với mọi n ≥ 0. Cho dãy w được tạo bởi:
trong đó zn thỏa mãn
,
zn ∈ ∂f (yn + 1) ∩ B
u − PF u,
ε 4γn
(cid:18) (cid:19)
(cid:107) wn − PF u (cid:107)≤ ε,
với mọi n ≥ 0. Nếu F := ∂f −1(0) = argminf (cid:54)= ∅, λn → 1 và γn → +∞ và γn → +∞ và ((1−λn)en) → 0 khi n → +∞, thì tồn tại một số N0 ∈ N sao cho
với mọi n (cid:62) N0.
λnu + (1 − λn)(y0 + en) ∈ yn+1 + γn∂f (yn+1).
Chứng minh. Theo định nghĩa của yn, ta có:
λnu + (1 − λn)(y0 − +en) = yn+1 + γnξn.
Vì thế, tồn tại ξn ∈ ∂f (yn+1) như vậy:
(3.1)
γnξn = u − PF u.
lim n→∞
Cho n −→ ∞ trong đẳng thức trên, thu được:
Vì thế, tồn tại một số N1 ∈ N sao cho với mọi n (cid:62) N1, ta có:
.
γnξn ∈ γn∂f (yn+1) ∩ B
u − PF u,
ε 4
(cid:17) (cid:16)
Mặt khác, từ giả thiết ta có:
.
γnzn ∈ γn∂f (yn+1) ∩ B
u − PF u,
ε 4
(cid:16) (cid:17)
32
(cid:107) yn+1 − PF u (cid:107)<
ε 2
Từ đó tồn tại một số N0 ≥ N1 sao cho với mọi n ≥ N0
.
(cid:107) γnzn − γnξn (cid:107)<
ε 2
và
(cid:107) ωn − PF u (cid:107) ≤(cid:107) ωn − yn+1 (cid:107) + (cid:107) yn+1 − PF u (cid:107)
=(cid:107) γnzn − γnξn (cid:107) + (cid:107) yn+1 − PF u (cid:107)
<
+
= ε.
ε 2
ε 2
Với mọi n ≥ N0, ta có:
(cid:3)
3.2 Bài toán bất đẳng thức biến phân
(3.2)
ND(z) := w ∈ H : (cid:104)w, z − u(cid:105) ≥ 0, ∀u ∈ D
Cho D là tập lồi đóng khác rỗng trong không gian Hilbert thực H và cho A0 : D −→ H là một ánh xạ liên tục đơn điệu đơn trị. Kí hiệu ND(z) là hình nón chuẩn tắc D tại z:
và cho A : H ⇒ H được định nghĩa bởi
A0(z) + ND(z) nếu
A(z) :=
(3.3)
z ∈ D, nếu z /∈ D.
∅
(cid:40)
Tính đơn điệu cực đại của ánh xạ đa trị A đã được xác định bởi Rockafellar [4]. Mối quan hệ 0 ∈ A(z) suy ra −A0(z) ∈ ND(z), hay được gọi là bất đẳng thức biến phân:
Tìm z ∈ D như vậy (cid:104)z − u, A0(z)(cid:105) ≤ 0 với mọi u ∈ D.
V I(A0, D) := {z ∈ D : (cid:104)z − u, A0(z)(cid:105) (cid:54) 0, ∀u ∈ D}.
Ta định nghĩa V I(A0, D) như sau:
33
z ∈ D, −A0(z) ∈ Do và (cid:104)z, A0(z)(cid:105) = 0.
Nếu D là hình nón, thì điều kiện này có thể viết dưới dạng
Bài toán tìm điểm z là một ví dụ quan trọng của bài toán bù trong quy hoạch tuyến tính. Khi đó Định lý 2.1.5 và 2.2.3 đưa ra lược đồ xấp xỉ tìm nghiệm của bất đẳng thức biến phân với ánh xạ A0 đơn trị đơn điệu và hắt liên tục A0 : D −→ H.
Định lý 3.2.1 Cho H là một không gian thực, D lồi đóng khác rỗng của H, A0 : D −→ H là ánh xạ đơn trị đơn điệu và ND(z) là nón pháp tuyến của D tại z. Với mọi x0, u ∈ H, cho dãy (xn) xác định bởi (2.1), với A được xác định bởi (3.3), khi đó λn ∈ (0, 1) và γn ∈ (0, +∞) với mọi n (cid:62) 0. Nếu λn → 1, γn → +∞, và ((1 − λn)en) → 0 khi n → +∞, thì V I(A0, D) (cid:54)= ∅ khi và chỉ khi (xn) giới nội và trong trường hợp này, (xn) hội tụ mạnh đến một thành phần của V I(A0, D), đó là hình chiếu của u trên A−1(0).
Chứng minh. Vì chúng ta đã biết A là một toán tử đơn điệu cực đại và V I(A0, D) = A−1(0), thì phần kết luận này được rút ra từ Định lý 2.1.4. (cid:3)
Nhận xét 3.2.2 Tương tự, nếu (yn) được sinh ra bởi (2.8) với A định nghĩa bởi (3.3), thì V I(A0, D) (cid:54)= ∅ khi và chỉ khi (yn) giới nội và trong trường hợp này, (yn) hội tụ mạnh mẽ đến PF u, hình chiếu của u trên F := A−1(0), đó là phần tử của V I(A0, D).
34
Kết luận
Đề tài này chúng tôi nghiên cứu hai thuật toán điểm gần kề với dãy sai số không giới nội cho toán tử đơn điệu cực đại A trong không gian Hilbert thực H. Trong mỗi trường hợp chúng tôi đưa ra điều kiện cần và đủ để tập không điểm của A là khác rỗng và đã chứng minh sự hội tụ mạnh mẽ của thuật toán điểm gần kề với tập không điểm của A trong trường hợp này, không giả thiết tính giới nội của dãy sai số cụ thể:
(1) Giới thiệu khái niệm và một số tính chất cơ bản của không gian Hilbert
thực và toán tử đơn điệu cực đại.
(2) Trình bày phương pháp điểm gần kề.
(3) Ứng dụng vào bài toán tối ưu và bài toán bất đẳng thức biến phân.
35
Tài liệu tham khảo
Tiếng Việt
[1] Đỗ Văn Lưu, Phan Huy Khải (2000), Giải tích lồi, NXB Khoa học và
Kỹ thuật Hà Nội.
[2] Hoàng Tụy (2003), Hàm thực và Giải tích hàm, NXB Đại học Quốc
gia Hà Nội.
Tiếng Anh
[3] Rouhani B. D. , Moradi S. (2017), "Strong convergence of two proximal point algorithms with possible unbounded error sequences", J. Otim
Theory Applications 172(1), 222-235 .
[4] Bnouhachem A. , Noor M. A. (2006), "Inexact proximal point method
for general variational inequalities", Journal of Mathematics Analysis
and Applications 324, 1195-1212.
[5] Rokafellar R. T. (1976), "Monotone Operators and the Proximal Point
Algorithm", SIAM Journal on Control and Optimization 14, 877-898.
[6] Eckstein J. (1988), "The Lions-Mercier splitting algorithm and the
alternating direction method are instances of the proximal point al-
gorithm", Report LIDS-P-1769, Laboratory for Information and De- cision Sciences.
[7] Brézis H. (1973), "Opérateurs Maximaux Monotones et Semi-Groupes de Contractions dans les Espaces de Hilbert", Amsterdam: North -
Holland.
36
[8] He B. S. (1999), "Inexact implicit methods for monotone general vari-
ational inequalities", Math. Programming 86 113-123.
[9] Gol’shtein E. G. , Tret’yakov N. V. (1979), "Modified Lagrangians in convex programming and their generalizations", Math. Programming
Stud. 10 86-97.
