ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
————————————
PHẠM THỊ GIANG
VỀ THUẬT TOÁN CHIẾU GIẢI BÀI TOÁN CHẤP NHẬN ĐƯỢC LỒI
Chuyên ngành: Toán ứng dụng
Mã số: 60 46 01 12
LUẬN VĂN THẠC SĨ TOÁN HỌC
NGƯỜI HƯỚNG DẪN KHOA HỌC
GS.TS. TRẦN VŨ THIỆU
Thái Nguyên - 2017
1
Mục lục
Danh mục các ký hiệu 2
MỞ ĐẦU 4
Chương 1. Kiến thức chuẩn bị 6
1.1 Không gian Hilbert thực . . . . . . . . . . . . . . . . . . . . . . 6
1.1.1 Khái niệm cơ bản . . . . . . . . . . . . . . . . . . . . . . 6
1.1.2 Đồng nhất thức và bất đẳng thức cơ bản . . . . . . . . . 8
1.1.3 Toán tử tuyến tính và phiếm hàm . . . . . . . . . . . . . 9
1.1.4 Tôpô mạnh và tôpô yếu . . . . . . . . . . . . . . . . . . 9
1.2 Ánh xạ không giãn và toán tử chiếu . . . . . . . . . . . . . . . . 11
1.3 Ánh xạ co và dãy đơn điệu Fejér . . . . . . . . . . . . . . . . . . 14
Chương 2. Thuật toán giải bài toán chấp nhận được lồi 19
2.1 Mô tả sơ đồ thuật toán . . . . . . . . . . . . . . . . . . . . . . . 19
2.2 Tính chất cơ bản của thuật toán . . . . . . . . . . . . . . . . . . 21
2.3 Kết quả hội tụ . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.4 Thuật toán chiếu . . . . . . . . . . . . . . . . . . . . . . . . . . 29
KẾT LUẬN 39
TÀI LIỆU THAM KHẢO 40
2
Danh mục các ký hiệu
R Tập số thực
Tập số thực không âm
Tập số thực mở rộng
R+ R ∪ {±∞} C Tập số phức
N Tập hợp số tự nhiên
Không gian Hilbert H
Không gian các dãy số vô hạn (cid:96)2
(cid:107)x(cid:107)
Chuẩn của véctơ x ∈ H Giá trị tuyệt đối của x ∈ R |x|
Dãy điểm trong H (x(n)) hay {xk}
xk (cid:42) x0 xk hội tụ yếu tới x0
xk → x0 xk hội tụ mạnh (hội tụ theo chuẩn) tới x0
(cid:104)x, y(cid:105) tích vô hướng của hai véctơ x, y ∈ H
[x, y] Đoạn thẳng nối x và y
x ≤ y Véctơ x nhỏ hơn hay bằng véctơ y (xi ≤ yi, ∀i = 1, . . . , n)
x ≥ y Véctơ x lớn hơn hay bằng véctơ y (xi ≥ yi, ∀i = 1, . . . , n)
conv{x1, . . . , xk} Bao lồi của các điểm x1, . . . , xk
x ∈ X x là một phần tử của tập X
x /∈ X x không là phần tử của tập X
∅ Tập hợp rỗng
Khoảng cách từ điểm x tới tập C dC(x)
A + B Tổng véctơ của hai tập A và B
3
A − B Hiệu véctơ của hai tập A và B
A ∪ B Hợp của hai tập A và B
A ∩ B Giao của hai tập A và B
A × B Tích Đề các của hai tập A và B
A ⊂ B A là tập con của B
A ⊆ B A là tập con (có thể bằng) của B
intY S Phần trong của S đối với Y (S, Y là tập con tùy ý của H)
int S Phần trong của S (=intH S)
S Bao đóng của tập S
conv S Bao lồi của tập S
convS Bao lồi đóng của tập S
affS Bao afin đóng của tập S
span S Không gian con tuyến tính nhỏ nhất của H chứa S
icr S
r+ Lõi bên trong của S (= intaf f S S) Phần dương của số r ∈ R = max{r, 0}
lim Giới hạn trên (của dãy số thực)
lim Giới hạn dưới (của dãy số thực)
∀x Với mọi x
∃x Tồn tại x
Id Toán tử đồng nhất trong H
Toán tử chiếu lên tập C PC
Fix T Tập điểm bất động của toán tử T
4
MỞ ĐẦU
Trong toán học và vật lý học hiện đại (ví dụ, chụp X quang điện toán hóa), ta thường gặp bài toán sau đây với tên gọi là bài toán chấp nhận được lồi (convex feasibility problem), phát biểu toán học chính xác của bài toán như sau: Cho H là một không gian Hilbert và C1, C2, . . . , CN là các tập lồi đóng trong H với giao C = C1 ∩ C2 ∩ . . . ∩ CN (cid:54)= ∅. Hãy tìm một điểm x ∈ C?
Có hai loại bài toán chính thường gặp:
1. Các tập Ci đơn giản, theo nghĩa có thể tính được hình chiếu (ánh xạ điểm gần nhất) trên Ci. Chẳng hạn, khi Ci là một siêu phẳng hay nửa không gian.
2. Không thể tính trực tiếp hình chiếu trên Ci, tuy nhiên có thể mô tả hình chiếu trên tập xấp xỉ nào đó rộng hơn Ci. Thường, Ci là tập mức dưới của một hàm lồi nào đó.
Tiếp cận hay được sử dụng để giải bài toán chấp nhận được lồi là thuật toán chiếu. Ý tưởng của thuật toán là: chiếu trên từng tập Ci (hoặc trên tập xấp xỉ của nó) để tạo ra dãy các điểm mà chúng hội tụ tới nghiệm của bài toán chấp nhận được lồi. Đó cũng là cách tiếp cận được phân tích, nghiên cứu và trình bày trong tài liệu tham khảo [3].
Đề tài luận văn “Về thuật toán chiếu giải bài toán chấp nhận được lồi” nhằm mục đích tìm hiểu và giới thiệu nội dung bài báo [3], trong đó trình bày nghiên cứu cải tiến, hợp nhất và điểm lại các kết quả nghiên cứu trước đó về các thuật toán chiếu.
Luận văn đề cập tới bài toán chấp nhận được lồi trong không gian Hilbert
và thuật toán chiếu giải bài toán. Luận văn gồm hai chương:
Chương 1. “Kiến thức chuẩn bị”. Chương này nhắc lại một số kiến thức cơ bản về không gian Hilbert, ánh xạ không giãn, toán tử chiếu và một số kiến thức liên quan. Tài liệu chính được sử dụng [1] - [4]. Trong chương có một số tiểu mục sau:
1.1. Không gian Hilbert thực: nhắc lại các khái niệm và sự kiện cơ bản (luật
hình bình hành, toán tử tuyến tính, sự hội tụ mạnh, hội tụ yếu, ...).
1.2. Ánh xạ không giãn và toán tử chiếu: Các khái niệm và tính chất (ánh
xạ không giãn bền vững, ánh xạ trung bình, nguyên lý bán đóng, ...).
5
1.3. Ánh xạ co và dãy đơn điệu Fejér: Tính chất cơ bản của toán tử dùng
trong sơ đồ lặp và của dãy lặp nhận được.
Chương 2. “Thuật toán giải bài toán chấp nhận được lồi”. Chương này đề cập tới các thuật toán (bao gồm thuật toán chiếu) giải bài toán chấp nhận được lồi. Tài liệu chính được sử dụng [3], [5], [6]. Chương 2 có một số tiểu mục sau:
2.1. Mô tả sơ đồ thuật toán: chính quy tiệm cận, nới lỏng, kỳ dị, trọng số,... 2.2. Tính chất cơ bản của thuật toán: Các tính chất, ví dụ và nhận xét. 2.2. Các kết quả hội tụ: Định lý lưỡng phân I và sự hội tụ theo tôpô yếu. 2.3. Thuật toán chiếu: Nguyên mẫu của thuật toán chiếu hội tụ, hội tụ tuyến
tính, định lý lưỡng phân II và sự hội tụ theo tôpô yếu,...
Do thời gian có hạn nên luận văn này chủ yếu chỉ dừng lại ở việc tìm hiểu, tập hợp tài liệu, sắp xếp và trình bày các kết quả nghiên cứu đã có theo chủ đề đặt ra. Trong quá trình viết luận văn cũng như trong soạn thảo văn bản chắc chắn không tránh khỏi có những sai sót nhất định. Tác giả luận văn rất mong nhận được sự góp ý của các thầy cô và các bạn đồng nghiệp để luận văn được hoàn thiện hơn.
Nhân dịp này, tác giả xin bày tỏ lòng biết ơn sâu sắc tới thầy hướng dẫn GS.TS. Trần Vũ Thiệu đã tận tình giúp đỡ trong suốt quá trình làm luận văn. Tác giả cũng xin chân thành cảm ơn các GS, PGS, TS của Khoa Toán-Tin, Trường Đại học Khoa học Thái Nguyên và của Viện Toán học, Viện Công nghệ thông tin thuộc Viện Hàn lâm Khoa học và Công nghệ Việt Nam đã giảng dạy và tạo mọi điều kiện thuận lợi trong quá trình tác giả học tập và nghiên cứu.
Thái Nguyên, tháng 5 năm 2017 Tác giả luận văn
Phạm Thị Giang
6
Chương 1
Kiến thức chuẩn bị
Chương này nhắc lại một số kiến thức cơ bản về không gian Hilbert: Các đồng nhất thức, bất đẳng thức hữu ích, ánh xạ không giãn, nguyên lý bán đóng, toán tử chiếu, ánh xạ co (co mạnh) và một số kiến thức liên quan. Nội dung của chương được tham khảo chủ yếu từ các tài liệu [1] - [4].
1.1 Không gian Hilbert thực
1.1.1 Khái niệm cơ bản
Định nghĩa 1.1. Không gian tiền Hilbert (pre-Hilbert space) là một không gian véctơ X trên R (hoặc C) cùng với tích vô hướng (inner product) xác định bởi (cid:104)·, ·(cid:105) : X × X → R (hoặc C) thỏa mãn với x, y, z ∈ X và λ ∈ R (hoặc C):
(i) (cid:104)x, x(cid:105) ≥ 0,
(ii) (cid:104)x, x(cid:105) = 0 ⇒ x = 0,
(iii) (cid:104)y, x(cid:105) = (cid:104)x, y(cid:105),
(iv) (cid:104)λx, y(cid:105) = λ(cid:104)x, y(cid:105),
(v) (cid:104)x + y, z(cid:105) = (cid:104)x, z(cid:105) + (cid:104)y, z(cid:105).
Mỗi tích vô hướng trên X tạo ra một chuẩn tương ứng
(cid:107)x(cid:107) = (cid:112)(cid:104)x, x(cid:105) với mọi x ∈ X.
Nếu X là không gian đủ theo chuẩn vừa xây dựng (nói cách khác, nếu X là không gian đủ theo metric sinh ra từ chuẩn này, hay X là không gian Banach với chuẩn đó) thì X được gọi là một không gian Hilbert.
7
i=1 xiyi là không gian Hilbert
Ví dụ 1.1. (i) Rn với tích vô hướng (cid:104)x, y(cid:105) = (cid:80)n trên R.
i=1 = uivi là không gian Hilbert trên
(ii) Cn với tích vô hướng (cid:104)u, v(cid:105) = (cid:80)n
C, trong đó u = (u1, u2, . . . , un), v = (v1, v2, . . . , vn).
∞ (cid:88)
(iii) (cid:96)2 với tích vô hướng
j=1
j=1, b = {bj}∞
(cid:104)a, b(cid:105) = ajbj
là không gian Hilbert trên C (ở đây a = {aj}∞ j=1). Sự kiện các chuỗi đối với (cid:104)a, b(cid:105) luôn hội tụ là hệ quả của bất đẳng thức H¨older với p = q = 2. Ở đây dễ kiểm tra lại các tính chất mà tích vô hướng cần phải thỏa mãn. Chuẩn sinh ra từ tích vô hướng là chuẩn (cid:107) · (cid:107)2 đã có trên (cid:96)2.
(iv) L2[0, 1], L2[a, b] và L2[R] tất cả đều là các không gian Hilbert đối với
(cid:90)
tích vô hướng
(cid:104)a, b(cid:105) = f g
(tích phân được lấy trên miền thích hợp).
Cho H là một không gian Hilbert thực ((cid:104)x, y(cid:105), λ ∈ R) với tích vô hướng (cid:104)·, ·(cid:105)
và chuẩn (cid:107) · (cid:107). Ký hiệu d là khoảng cách, nghĩa là
(∀x ∈ H) (∀y ∈ H) (cid:107)x(cid:107) = (cid:112)(cid:104)x, x(cid:105) và d(x, y) = (cid:107)x − y(cid:107).
Tập con C ⊂ H gọi là trực giao nếu x, y ∈ C, x (cid:54)= y ⇒ (cid:104)x, y(cid:105) = 0. C gọi là trực chuẩn nếu nó là tập con trực giao và có thêm (cid:107)x(cid:107) = 1 với mỗi x ∈ C. Để ý rằng các định nghĩa này áp dụng cho mọi tập con C có hữu hạn hay vô số phần tử. Cũng cần chú ý là nếu C là tập con trực giao thì {x/(cid:107)x(cid:107) : x ∈ C\{0}} là tập con trực chuẩn.
Tập trực chuẩn C ⊂ H gọi là một cơ sở trực chuẩn của H nếu spanC = H (tức là không gian con tuyến tính đóng nhỏ nhất của H chứa C trùng với H). Không gian H là tách được nếu H có một cơ sở trực chuẩn đếm được. Ký hiệu toán tử đồng nhất trên H là Id.
Hình cầu đơn vị đóng của H ký hiệu là B(0, 1) = {x ∈ H | (cid:107)x(cid:107) ≤ 1}.
Dãy {xk} trong H gọi là hội tụ yếu tới x0, ký hiệu xk (cid:42) x0, nếu (cid:104)a, xk(cid:105) → (cid:104)a, x0(cid:105) với mỗi a ∈ H. Dãy {xk} trong H gọi là hội tụ mạnh tới x0, ký hiệu xk → x0, nếu (cid:107)xk − x0(cid:107) → 0 (còn gọi hội tụ theo tích vô hướng và hội tụ theo chuẩn).
8
1.1.2 Đồng nhất thức và bất đẳng thức cơ bản
Bất đẳng thức Cauchy - Schwarz. Giả sử x, y ∈ H. Khi đó
|(cid:104)x, y(cid:105)| ≤ (cid:107)x(cid:107)(cid:107)y(cid:107).
Hơn nữa, |(cid:104)x, y(cid:105)| = (cid:107)x(cid:107)(cid:107)y(cid:107) ⇔ (∃α ∈ R+) x = αy hay y = αx.
Bổ đề 1.1. Giả sử x, y và z ∈ H. Khi đó, các điều sau là đúng:
(i) (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.
(ii) Luật hình bình hành: (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).
(iii) Đồng nhất thức phân cực: (cid:107)x + y(cid:107)2 − (cid:107)x − y(cid:107)2 = 4(cid:104)x, y(cid:105).
(iv) Đồng nhất thức Apollonius:
(cid:107)x − y(cid:107)2 = 2(cid:107)z − x(cid:107)2 + 2(cid:107)z − y(cid:107)2 − 4(cid:107)z − (x + y)/2(cid:107)2.
Chứng minh. (i) Kiểm tra dễ dàng. (ii) và (iii): Từ (i) suy ra
(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.
Lần lượt cộng và trừ (i) với đồng nhất thức này, ta nhận được (ii) và (iii). (iv) Áp dụng (i) đối với (z − x)/2 và (z − y)/2.
Bổ đề 1.2. Giả sử x và y ∈ H. Khi đó, các điều sau là đúng:
(i) (cid:104)x, y(cid:105) ≤ 0 ⇔ (∀α ∈ R+) (cid:107)x(cid:107) ≤ (cid:107)x − αy(cid:107) ⇔ (∀α ∈ [0, 1]) (cid:107)x(cid:107) ≤ (cid:107)x − αy(cid:107).
(ii) x ⊥ y ⇔ (∀α ∈ R) (cid:107)x(cid:107) ≤ (cid:107)x − αy(cid:107) ⇔ (∀α ∈ [−1, 1]) (cid:107)x(cid:107) ≤ (cid:107)x − αy(cid:107).
Chứng minh. (i) Để ý rằng
(∀α ∈ R) (cid:107)x − αy(cid:107)2 − (cid:107)x(cid:107)2 = α(α(cid:107)y(cid:107)2 − 2(cid:104)x, y(cid:105)).
Từ đó trực tiếp suy ra có chiều thuận (⇒). Ngược lại, ∀α ∈ [0, 1], (cid:107)x(cid:107) ≤ (cid:107)x−α(cid:107), từ đẳng thức trên suy ra (cid:104)x, y(cid:105) ≤ α(cid:107)y(cid:107)2/2. Khi α ↓ 0, ta nhận được (cid:104)x, y(cid:105) ≤ 0.
(ii) là hệ quả của (i), bởi vì x ⊥ y ⇔ [(cid:104)x, y(cid:105) ≤ 0 và (cid:104)x, −y(cid:105) ≤ 0].
Hệ quả 1.1. Giả sử x ∈ H, y ∈ H và α ∈ R. Khi đó,
(cid:107)αx + (1 − α)y(cid:107)2 + α(1 − α)(cid:107)x − y(cid:107)2 = α(cid:107)x(cid:107)2 + (1 − α)(cid:107)y(cid:107)2.
Mệnh đề 1.1. (Tính lồi chặt). Nếu x, y ∈ H thì
(cid:107)x + y(cid:107) = (cid:107)x(cid:107) + (cid:107)y(cid:107) kéo theo (cid:107)y(cid:107) · x = (cid:107)x(cid:107) · y.
Chứng minh. Suy ra từ luật bình hành.
9
1.1.3 Toán tử tuyến tính và phiếm hàm
L (X, Y ) = {T : X → Y | T tuyến tính và liên tục}
Cho X và Y là hai không gian tuyến tính định chuẩn thực. Ta nhắc lại, toán tử T : X → Y là tuyến tính nếu T [αx + βy] = αT x + βT y, ∀x, y ∈ X, ∀α, β ∈ R. Toán tử tuyến tính T là liên tục tại một điểm thuộc X khi và chỉ khi T liên tục Lipschitz. Đặt
và L (X) = L (X, X). Với chuẩn toán tử xác định bởi
x∈X,(cid:107)x(cid:107)≤1
(∀T ∈ L (X, Y )) (cid:107)T (cid:107) = sup (cid:107)T (B(0, 1))(cid:107) = sup (cid:107)T (x)(cid:107)
thì L (X, Y ) là không gian tuyến tính định chuẩn và đó là không gian Banach nếu Y là không gian Banach.
Định lý Banach - Steinhaus (Tính bị chặn đều). Giả sử X là một không gian Banach thực, Y là một không gian tuyến tính định chuẩn thực và (Ti)i∈I là một họ các toán tử bị chặn theo từng điểm, nghĩa là (∀x ∈ X) sup (cid:107)Tix(cid:107) < +∞. Khi đó, supi∈I (cid:107)Ti(cid:107) < +∞.
Định lý biểu diễn Riesz - Fréchet sau cho thấy có thể đồng nhất mỗi phiếm hàm tuyến tính liên tục trong không gian Hilbert thực H với một véctơ trong H. Định lý Riesz - Fréchet. Giả sử f ∈ L (H, R). Khi đó, tồn tại duy nhất véctơ u ∈ H sao cho (x ∈ H) f (x) = (cid:104)x, u(cid:105). Hơn nữa, (cid:107)f (cid:107) = (cid:107)u(cid:107).
Cho K là không gian Hilbert thực và T : H → K liên hợp (adjoint) của T
là toán tử duy nhất T ∗ ∈ L (K, H) thỏa mãn
(∀x ∈ H) (∀y ∈ K) (cid:104)T x, y(cid:105) = (cid:104)x, T ∗y(cid:105).
1.1.4 Tôpô mạnh và tôpô yếu
Tôpô metric của (H, d), tức là tôpô nhận họ tất cả các hình cầu mở làm cơ sở lân cận, được gọi là tôpô mạnh (strong topology) hay tôpô theo chuẩn (norm topology) của H. Như vậy, lưới (xa)a∈A trong H hội tụ mạnh (converges strongly) tới điểm x nếu (cid:107)xa − x(cid:107) → 0, ký hiệu xa → x.
Khi sử dụng mà không nói gì thêm, các khái niệm tôpô trong H (đóng, mở, lân cận, liên tục, compac, hội tụ, ....) sẽ luôn được hiểu theo nghĩa tôpô mạnh.
Một khái niệm tôpô rất quan trọng khác (tôpô yếu) cũng được đề cập tới.
10
Định nghĩa 1.2. Tôpô yếu (weak topology) của H được tạo nên bởi cơ sở lân cận gồm họ tất cả các tương giao hữu hạn các nửa không gian mở của H.
Ta ký hiệu không gian tôpô nhận được là Hyếu. Ta nhắc lại, không gian tô pô X là không gian Hausdorff nếu với hai điểm khác biệt bất kỳ x và y trong X đều tồn tại các tập mở Vx (cid:51) x và Vy (cid:51) y sao cho Vx ∩ Vy = ∅. Ta có
Bổ đề 1.3. Hyếu là không gian Hausdorff.
Chứng minh. Giả sử x và y là hai điểm khác biệt trong H. Đặt u = x − y và w = (x + y)/2. Khi đó {z ∈ H : (cid:104)z − w, u(cid:105) > 0} và {z ∈ H : (cid:104)z − w, u(cid:105) < 0} lần lượt là hai lân cận yếu (nửa không gian mở) rời nhau của x và y.
Về hình học, có thể giải thích sự hội tụ mạnh và yếu của lưới (xa)a∈A trong H tới x ∈ H như sau: xa → x (hội tụ mạnh) có nghĩa là d{x}(xa) → 0 (khoảng cách từ xa tới x dần tới 0); trong khi đó xa (cid:42) x (hội tụ yếu) có nghĩa là dC(xa) → 0 (khoảng cách từ xa tới C dần tới 0) đối với mọi siêu phẳng đóng C chứa x.
Tính chất đặc trưng của không gian Hilbert vô hạn chiều H là: hình cầu
đơn vị đóng trong H không là tập compac.
Mệnh đề 1.2. Các điều sau là tương đương
(i) H là hữu hạn chiều.
(ii) Hình cầu đơn vị đóng B(0, 1) của H là compac.
(iii) Tôpô yếu của H trùng với tôpô mạnh của H.
(iv) Tôpô yếu của H metric hóa được.
Ta nhắc lại, không gian tôpô X gọi là metric hóa được nếu tôpô của nó trùng với tôpô metric (tôpô nhận họ tất cả các hình cầu mở làm cơ sở lân cận).
Mệnh đề sau cho thấy khi nào tôpô yếu của H metric hóa được.
Mệnh đề 1.3. Tôpô yếu của hình cầu đơn vị đóng B(0, 1) của H metric hóa được khi và chỉ khi H là tách (tức H có một cơ sở trực chuẩn đếm được).
Điều khác biệt đáng chú ý là mọi hình cầu đơn vị đóng là compac yếu. Tính
chất sâu sắc và cơ bản này được biết với tên gọi định lý Banach - Alaoglu.
Mệnh đề 1.4. (Định lý Banach - Alaoglu). Hình cầu đơn vị đóng của H là compac yếu (compac trong tôpô yếu).
11
Bổ đề 1.4. Giả sử C là một tập con của H. Khi đó C là tập compac yếu khi và chỉ khi C đóng yếu và bị chặn.
Mệnh đề sau đây nêu tính chất đặc trưng của dãy hội tụ mạnh.
Mệnh đề 1.5. Giả sử (xn)n∈N là một dãy trong H và x ∈ H. Khi đó, xn → x ⇔ [xn (cid:42) x và (cid:107)xn(cid:107) → (cid:107)x(cid:107)].
1.2 Ánh xạ không giãn và toán tử chiếu
• Ánh xạ không giãn. Ánh xạ T : D → H, trong đó D là một tập con lồi
đóng khác rỗng của H, được gọi là không giãn (nonexpansive) nếu
(cid:107)T x − T y(cid:107) ≤ (cid:107)x − y(cid:107) với mọi x, y ∈ D.
Nếu (cid:107)T x − T y(cid:107) = (cid:107)x − y(cid:107) với mọi x, y ∈ D thì ta nói T là một ánh xạ đẳng cự (isometry). Trái lại nếu (cid:107)T x − T y(cid:107) < (cid:107)x − y(cid:107) với mọi x, y ∈ D thì ta nói T là một ánh xạ không giãn chặt (strictly nonexpansive mapping). Nếu T là một ánh xạ không giãn thì tập tất cả các điểm bất động Fix T được xác định bởi
Fix T = {x ∈ D : x = T x}
luôn là tập lồi đóng.
(cid:27)
• Nguyên lý bán đóng (demiclosedness principle). Nếu D là tập con lồi đóng của H, T : D → H là ánh xạ không giãn, (xn) là một dãy trong D và x ∈ D, thì
kéo theo x ∈ Fix T, xn (cid:42) x xn − T xn → 0
trong đó các ký hiệu “→” và “(cid:42)” lần lượt chỉ sự hội tụ theo chuẩn và hội tụ yếu.
Rõ ràng là ánh xạ đồng nhất Id là không giãn và dễ thấy rằng tổ hợp lồi của các ánh xạ không giãn cũng là không giãn. Nói riêng, nếu N là ánh xạ không giãn thì (1 − α) Id +αN cũng là ánh xạ không giãn với mọi α ∈ [0, 1).
Các ánh xạ này được gọi là ánh xạ trung bình (averaged mappings). Ánh xạ không giãn bền vững (firmly nonexpansive) là ánh xạ không giãn có thể viết dưới dạng
Id + N với ánh xạ không giãn N nào đó. 1 2 1 2
12
Mệnh đề 1.6. Nếu D là một tập con lồi đóng của H và T : D → H là một ánh xạ, thì các điều kiện sau là tương đương:
(i) T là ánh xạ không giãn bền vững.
(ii) (cid:107)T x − T y(cid:107)2 ≤ (cid:104)T x − T y, x − y(cid:105) với mọi x, y ∈ D.
(iii) 2T − Id là ánh xạ không giãn.
Một ánh xạ được gọi là không giãn bền vững nới lỏng (relaxed firmly non-
expansive) có thể biểu diễn nó dưới dạng
(1 − α) Id +αF với ánh xạ không giãn bền vững F nào đó.
Hệ quả 1.2. Cho D là một tập con lồi đóng của H và T : D → H là một ánh xạ. Khi đó T là ánh xạ trung bình khi và chỉ khi T là ánh xạ không giãn bền vững nới lỏng.
• Toán tử chiếu. Cho tập con lồi đóng khác rỗng C của H, ánh xạ đưa mỗi điểm tới điểm gần nó nhất trong C (theo chuẩn cảm sinh bởi tích vô hướng của H) được gọi là phép chiếu lên C và ký hiệu là PC.
Mệnh đề 1.7. Giả sử C là một tập con lồi đóng khác rỗng của H với phép chiếu PC. Khi đó,
(i) PC là ánh xạ không giãn bền vững.
(ii) Nếu x ∈ H thì PCx được đặc trưng bởi
PCx ∈ C và (cid:104)y − PCx, x − PCx(cid:105) ≤ 0, ∀y ∈ C.
Như vậy, có thể thấy các quan hệ sau đây giữa các loại toán tử nêu trên. chiếu ⇓ không giãn bền vững ⇓ không giãn bền vững nới lỏng = trung bình ⇓ đẳng cự ⇒ không giãn ⇐ không giãn chặt
Hàm liên kết d(·, C) : H → R : x (cid:55)→ infc∈C (cid:107)x − c(cid:107) = (cid:107)x − PC(x)(cid:107) được gọi là hàm khoảng cách (distance function) tới C. Có thể chứng minh được rằng d(·, C) là hàm lồi và liên tục (do đó nửa liên tục dưới).
13
Chất lượng hội tụ của thuật toán sẽ được bàn tới theo ngôn từ hội tụ tuyến tính (linear convergence): dãy (xn) trong H được gọi là hội tụ tuyến tính tới giới hạn x (với tốc độ β) nếu β ∈ [0, 1) và tồn tại α ≥ 0 sao cho
(cid:107)xn − x(cid:107) ≤ αβn với mọi n.
Mệnh đề 1.8. Giả sử (xn) là một dãy trong H, p là một số nguyên dương và x là một điểm trong H. Nếu (xpn)n hội tụ tuyến tính tới x và ((cid:107)xn − x(cid:107))n giảm. Khi đó toàn bộ dãy (xn)n hội tụ tuyến tính tới x.
Chứng minh. Tồn tại α ≥ 0 và β ∈ [0, 1) sao cho
(cid:107)xpn − x(cid:107) ≤ αβn với mọi n.
Bây giờ cố định một số nguyên dương tùy ý m và chia cho p dư r, tức là
m = p × n + r, trong đó r ∈ {0, 1, . . . , p − 1}.
(cid:16)
(cid:17)np
1 p
Ta có đánh giá
β
(cid:17)np+r
1 p
(cid:16)
(cid:17)m
1 p
(cid:107)xm − x(cid:107) ≤ (cid:107)xpn − x(cid:107) ≤ α (cid:16)
(cid:17)r ≤
(cid:16)
1 p
1 p
β = β (cid:16) α (cid:17)p−1 β β
và từ đây suy ra kết quả.
Cuối cùng chúng ta nhắc lại một số ký hiệu sau đây: Nếu S và Y là các tập con bất kỳ của H, thì các ký hiệu span S, convS, S, intY S, icr S và int S lần lượt là không gian con tuyến tính nhỏ nhất của H chứa S, bao lồi đóng của S, bao đóng của S, phần trong của S đối với Y , lõi bên trong (intrinsic core) của S (= intaffS, trong đó affS là bao afin đóng của S) và phần trong của S (= intH S).
S được gọi là một nón nếu nó lồi, khác rỗng và đóng đối với phép nhân với số không âm. Nếu S là giao của một số hữu hạn các nửa không gian (đóng) thì S là một tập lồi đa diện (polyhedron).
Nếu r là một số thực thì r+ := max{r, 0} được gọi là phần dương của r. Với các dãy số thực, thì ký hiệu lim (lim) là giới hạn trên (giới hạn dưới). Đôi khi ta còn dùng các lượng tử ∀ (với mọi) và ∃ (tồn tại) để câu được ngắn gọn.
14
1.3 Ánh xạ co và dãy đơn điệu Fejér
Mục này bàn tới hai khái niệm quan trọng. Khái niệm thứ nhất tổng quát ý tưởng các ánh xạ không giãn trung bình (tương ứng, ánh xạ không giãn chặt).
Định nghĩa 1.3. Giả sử D là một tập con lồi đóng khác rỗng, T : D → D là ánh xạ không giãn, và F là một tập con lồi đóng khác rỗng của D. Ta nói rằng T co đối với F (attracting w.r.t.) nếu với mọi x ∈ D\F, f ∈ F
(cid:107)T x − f (cid:107) < (cid:107)x − f (cid:107).
Nói cách khác, mọi điểm trong F hút mọi điểm ngoài F . Biến thể mạnh
hơn và định lượng hơn như sau.
Ta nói rằng T co mạnh đối với F nếu có κ > 0 sao cho với mọi x ∈ D, f ∈ F
κ(cid:107)x − T x(cid:107)2 ≤ (cid:107)x − f (cid:107)2 − (cid:107)T x − f (cid:107)2.
Nếu muốn nhấn mạnh rõ hơn, ta có thể chọn cách nói rằng T là κ - co đối với F . Trong một số tình huống F là tập Fix T (tập điểm bất động của T ); trong trường hợp này ta chỉ đơn giản muốn nói về ánh xạ co, co mạnh hay κ - co.
Nhận xét 1.1. Định nghĩa trên khá tổng quát. Như sẽ thấy, lớp các ánh xạ co mạnh chứa như trường hợp riêng tất cả các ánh xạ không giãn trung bình và do đó chứa tất cả các phép chiếu nới lỏng - những ánh xạ chính mà ta quan tâm.
Ánh xạ x (cid:55)→ 1 − ln(1 + er) là ví dụ đầu tiên về ánh xạ không giãn chặt nhưng không là ánh xạ trung bình, do đó lớp ánh xạ co thực sự rộng hơn lớp ánh xạ co mạnh. Cuối cùng không lớp nào chứa lớp đẳng cự với điểm bất động.
Các mệnh đề ngăn chặn riêng được minh họa bởỉ ví dụ sau đây.
(cid:40) 1
Ví dụ 1.2. Cho D là khoảng đối xứng lồi đóng trong R chứa [−1, +1]. Đặt
2|x|2 |x| − 1 2
nếu |x| ≤ 1, T : D → D : x (cid:55)→ nếu trái lại.
Khi đó:
• T là ánh xạ không giãn và Fix T = {0}. • T không là ánh xạ không giãn chặt.
15
• T là ánh xạ co. • T là ánh xạ co mạnh khi và chỉ khi D là compac.
Bổ đề 1.5. (Nguyên mẫu của ánh xạ co mạnh). Giả sử D là một tập con lồi đóng khác rỗng, T : D → D là ánh xạ không giãn bền vững có điểm bất động và α ∈ (0, 2). Giả sử R := (1 − α) Id +αT và cố định x ∈ D, f ∈ F ixT . Khi đó
(i) Fix R = Fix T.
(ii) (cid:104)x − f, x − T x(cid:105) ≥ (cid:107)x − T x(cid:107)2 và (cid:104)x − T x, T x − f (cid:105) ≥ 0.
(iii) (cid:107)x − f (cid:107)2 − (cid:107)Rx − f (cid:107)2 = 2α(cid:104)x − f, x − T x(cid:105) − α2(cid:107)x − T x(cid:107)2.
(iv) R là (2 − α)/α - co:
(cid:107)x − f (cid:107)2 − (cid:107)Rx − f (cid:107)2 ≥ (2 − α)/α(cid:107)x − Rx(cid:107)2 = (2 − α)/α(cid:107)x − T x(cid:107)2.
Chú ý rằng (i) và (iii) thực ra đúng đối với ánh xạ không giãn T . Tuy nhiên điều này sẽ không cần đến về sau. Do phép chiếu là ánh xạ không giãn bền vững, cho nên ta trực tiếp nhận được hệ quả sau.
Hệ quả 1.3. Nếu P là phép chiếu lên một tập lồi đóng khác rỗng S nào đó và α ∈ (0, 2) thì R := (1 − α) Id +αP là (2 − α)/α-co đối với S và với x ∈ H, s ∈ S ta có (cid:107)x − s(cid:107)2 − (cid:107)Rx − s(cid:107)2 ≥ (2 − α)αd2(x, S).
Định nghĩa 1.4. Giả sử {xn} là một dãy trong H. Ta nói {xn} là chính quy tiệm cận (asymptotically regular) nếu xn − xn+1 → 0.
Ví dụ 1.3. Giả sử D là một tập lồi đóng khác rỗng, F là tập con lồi đóng khác rỗng của D và (Tn)n≥0 là một dãy tự ánh xạ không giãn của D, trong đó mỗi Tn là κ-co đối với F và limnκn > 0. Hơn nữa giả sử dãy (xn) được xác định bởi
x0 ∈ D tùy ý, xn+1 := Tnxn với mọi n ≥ 0.
Khi đó (xn) là chính qui tiệm cận.
Chứng minh. Cố định f ∈ F và chọn 0 < κ < limnκn. Khi đó, với mọi n đủ lớn ta có
n (cid:107)xn−1 − xn(cid:107)2 là hữu hạn. Từ
κ(cid:107)xn−1 − xn(cid:107)2 ≤ (cid:107)xn−1 − f (cid:107)2 − (cid:107)xn − f (cid:107)2.
Cộng các bất đẳng thức này cho thấy rằng (cid:80) đó suy ra điều cần chứng minh.
16
Hệ quả 1.4. Giả sử D là tập lồi đóng khác rỗng và T : D → D là ánh xạ co mạnh với các điểm bất động. Khi đó, dãy lặp (T nx0)n≥0 là chính qui tiệm cận với mọi x0 ∈ D.
i=1 Fix Ti (cid:54)= ∅. Khi đó
Mệnh đề sau chỉ ra các ánh xạ co (mạnh) đối với hợp và tổ hợp lồi.
i=1 Fix Ti và TN TN −1 . . . T1 là ánh xạ co.
Mệnh đề 1.9. Giả sử D là một tập lồi đóng khác rỗng, T1, . . . , Tn : D → D là các ánh xạ co và (cid:84)N (i) Fix(TN TN −1 . . . T1) = (cid:84)N
(ii) Nếu mọi Ti là κi-co thì TN TN −1 . . . T1 là min{κ1, . . . , κN }/2N −1-co.
Nhận xét 1.2. Giả sử H ⊇ và (cid:54)= {0}, D := H, N := 2 và T1 := T2 := − Id. Khi đó
Fix T1 ∩ Fix T2 = {0} ⊆ và (cid:54)= H ≡ Fix(T2T1).
i=1 Fix Ti
(cid:17)
Do đó công thức về các tập điểm bất động cho ở (i) của mệnh đề vừa nêu nói chung không đúng đối với các ánh xạ không giãn.
i=1 Fix Ti và (cid:80)N
i=1 λiTi là ánh xạ co.
i=1 λiTi
Mệnh đề 1.10. Giả sử D là một tập lồi khác rỗng, T1, . . . , TN : D → D là các ánh xạ co và (cid:84)N (cid:54)= ∅. Hơn nữa, giả sử λ1, . . . , λN > 0 với λ1 + · · · + λN = 1. Khi đó (cid:16)(cid:80)N = (cid:84)N (i) Fix
i=1 λiTi là min{κ1, . . . , κN }-co.
(cid:17)
(cid:16)(cid:80)N
(ii) Nếu mọi Ti là κt-co thì (cid:80)N
i=1 λiTi
= (cid:84)N Nhận xét 1.3. Khác với nhận xét trước đây, có thể chứng minh rằng công i=1 Fix Ti vẫn còn đúng ngay cả khi Ti không còn là thức Fix
ánh xạ co.
Ví dụ 1.4. Giả sử S1, . . . , SN là các tập lồi đóng khác rỗng với các phép chiếu P1, . . . , PN và với giao khác rỗng. Khi đó,
T := P1 + P2P1 + . . . + PN PN −1 . . . P1 N
i=1 Si và dãy lặp (T nx0) là chính quy tiệm cận với mọi x0.
co chặt, Fix T = (cid:84)N
Khái niệm thứ hai về các tính chất lặp căn bản của các ánh xạ không giãn.
Định nghĩa 1.5. Giả sử C là một tập lồi đóng khác rỗng và {xn} là một dãy trong H. {xn} là dãy đơn điệu Fejér với C nếu
(cid:107)xn+1 − c(cid:107) ≤ (cid:107)xn − c(cid:107) với mọi c ∈ C và mọi n ≥ 0.
17
Định lý 1.1. (Tính chất cơ bản của dãy đơn điệu Fejér). Giả sử {xn}n≥0 là một dãy đơn điện Fejér đối với C. Khi đó,
(i) {xn} bị chặn và d(xn+1, C) ≤ d(xn, C).
(ii) {xn} có nhiều nhất một điểm tụ yếu trong C. Do đó {xn} hội tụ yếu về một điểm nào đó trong C khi và chỉ khi mọi điểm tụ yếu của {xn} nằm trong C.
(iii) Nếu phần trong của C khác rỗng, thì {xn} hội tụ theo chuẩn.
(iv) Dãy {PCxn} hội tụ theo chuẩn.
(v) Các điều sau đây là tương đương:
(a) {xn} hội tụ theo chuẩn về một điểm nào đó trong C.
(b) {xn} có các điểm tụ theo chuẩn, tất cả đều nằm trong C.
(c) {xn} có các điểm tụ theo chuẩn, trong đó có một điểm nằm trong C.
(d) d(xn, C) → 0.
(e) xn − PCxn → 0.
Hơn nữa, nếu {xn} hội tụ tới x ∈ C nào đó thì (cid:107)xn − x(cid:107) ≤ 2d(xn, C) với mọi n ≥ 0.
(vi) Nếu có hằng số α > 0 sao cho αd2(xn, C) ≤ d2(xn, C) − d2(xn+1, C) với mọi n, thì {xn} hội tụ tuyến tính tới điểm x nào đó trong C. Nói chính xác hơn,
(cid:107)xn − x(cid:107) ≤ 2(1 − α)n/2d(x0, C) với mọi n ≥ 0.
Nhận xét 1.4. Như chúng ta biết, khái niệm đơn diệu Fejér đã được Motzkin và Schoenberg đưa ra năm 1954.
Ví dụ 1.5. (Phép lặp Krasnoselski/Mann). Giả sử C là một tập lồi đóng khác rỗng, T : C → C là một ánh xạ không giãn có điểm bất động và dãy (xn) cho bởi
x0 ∈ C, xn+1 := (1 − tn)xn + tnT xn
với mọi n ≥ 0 và một dãy (tn)n≥0 nào đó trong [0, 1]. Khi đó (xn) là dãy đơn điệu Fejér đối với Fix T.
18
Nhận xét 1.5. Trước đó phép lặp Krasnoselski/Mann đã được nghiên cứu trong không gian Hilbert. Khi đó một số tác giả đã sử dụng một cách không tường minh các tính chất của dãy đơn điệu Fejér. Tuy nhiên nhiều tiến bộ to lớn đã thu được và ngày nay phép lặp này đang được nghiên cứu trong các không gian định chuẩn và các không gian tổng quát hơn.
Ví dụ 1.6. (Ví dụ 1.4 tiếp). Dãy (T nx0) hội tụ yếu tới một điểm bất động nào đó của T với mọi x0.
Chứng minh. Dãy (T nx0) là chính quy tiệm cận (Ví dụ 1.4) và đơn điệu Fejér đối với Fix T (Ví dụ 1.5). Theo nguyên lý bán đóng, mọi điểm giới hạn yếu của (T nx0) nằm trong Fix T . Kết luận được suy ra từ Định lý 1.1(ii).
Nhận xét 1.6. Mặt khác, người ta có thể dùng các kết quả của Baillon, Bruck và Reich về các ánh xạ trung bình để chứng minh ví dụ trên. Thực ra, người ta còn có thể chỉ ra rằng (T nx0) hội tụ theo chuẩn mỗi khi S1, . . . , SN là các không gian con afin đóng.
Nhận xét 1.7. Để kết thúc mục này chúng tôi nhắc lại phương pháp Halpern (1967) tạo ra dãy hội tụ theo chuẩn tới điểm bất động của T gần với điểm xuất phát nhất.
Kết luận chương. Chương này đã điểm lại một số khái niệm và kiến thức cần thiết về không gian Hilbert, khái niệm dãy hội tụ yếu và hội tụ mạnh, các đồng nhất thức, bất đẳng thức hữu ích. Trình bày các khái niệm và kết quả về ánh xạ không giãn, ánh xạ không giãn bền vững và toán tử chiếu, ánh xạ co, ánh xạ co mạnh cùng các tính chất và một số kiến thức liên quan: nguyên lý bán đóng, dãy đơn điệu Fejér và các tính chất.
Các khái niệm và kết quả trình bày ở chương này sẽ được sử dụng ở chương
sau, khi xét tới các thuật toán và dãy các điểm lặp sinh ra bởi thuật toán.
19
Chương 2
Thuật toán giải bài toán chấp nhận
được lồi
Chương này trình bày khái niệm thuật toán (sơ đồ lặp) nêu ra ở [3] cùng với các khái niệm có liên quan, nêu các tính chất cơ bản và các kết quả hội tụ của thuật toán lặp này. Nội dung chương này được viết dựa chủ yếu trên các tài liệu tham khảo [3], [5] và [6].
2.1 Mô tả sơ đồ thuật toán
N (cid:92)
Cho D ⊂ H là một tập lồi đóng khác rỗng trong không gian Hilbert thực H và C1, . . . , CN là một số hữu hạn tập con lồi đóng của D với giao khác rỗng:
i=1
C := Ci (cid:54)= ∅.
: D → D
Với mỗi i = 1, . . . , N (ta sẽ gọi i là chỉ số) và mỗi n ≥ 0, giả sử T (n) i là ánh xạ không giãn bền vững (firmly nonexpansive mapping) với
i ⊇ Ci,
Fix T (n)
i ∈ [0, 2] là các tham số nới lỏng (relaxation parameter) và
giả sử α(n)
i
i T (n)
i
:= (1 − α(n) ) Id +α(n) R(n) i
(nới lỏng dưới nếu α(n)
i ∈ [1, 2]), giả sử (λ(n)
i
là các ánh xạ nới lỏng tương ứng của T (n) i ∈ [0, 1], nới i lỏng trên nếu α(n) )N i=1 ở trong [0, 1] là trọng số (weight),
20
i = 1 và sau cùng giả sử rằng
i=1 λN
N (cid:88)
nghĩa là (cid:80)N
i R(n) λ(n)
i
i=1
A(n) :=
là trung bình trọng số tương ứng của các ánh xạ nới lỏng.
Xét thuật toán (algorithm) nêu ra ở [3], xác định bởi dãy lặp:
x(0) ∈ D tùy ý , x(n+1) := A(n)x(n) với mọi n ≥ 0
với giả thiết rằng dãy (x(n)) nằm trong D. Với mỗi n ta định nghĩa tập chỉ số tích cực (active index)
i > 0}
I (n) := {i ∈ {1, . . . , N } : λ(n)
N (cid:88)
và nói i là tích cực tại n hay n là tích cực đối với i nếu λ(n) i > 0, tức là i ∈ I (n). Ta luôn giả thiết rằng mỗi chỉ số được chọn vô số lần, tức i là tích cực tại vô số n (đôi khi ta gọi đó là điều khiển lặp - repetitive control). Để giảm nhẹ cách trình bày, ta ký hiệu ngắn gọn
j ] với mọi chỉ số i và mọi n ≥ 0.
i α(n)
i
j=1
:= λ(n) [2 − µ(n) i λ(n) j αn
i
Để thuận tiện, ta đưa thêm vào một số khái niệm. Ta nói thuật toán là chính quy tiệm cận (asymptotically regular) nếu mọi dãy sinh ra bởi thuật toán là chính quy tiệm cận (xem Định nghĩa 1.4). Ta nói thuật toán là không bị nới lỏng (unrelaxed) nếu α(n) i = 1 với mọi n và mọi chỉ số i là tích cực tại n bất kỳ; để ý rằng trong trường hợp này thuật toán rút gọn thành tích các ánh xạ không giãn bền vững. Ta nói thuật toán là kỳ dị (singular) nếu I (n) gồm duy nhất một phần tử với mọi n. Thuật toán kỳ dị còn được gọi là phương pháp tác dụng dòng (row - action method). Cuối cùng, ta nói thuật toán được gán trọng số (weighted) nếu I (n) = {1, . . . , N } với mọi n; ngoài ra trong các tài liệu ta còn gặp thuật toán song song (parallel) hay thuật toán đồng thời (simultaneous).
Nhận xét 2.1. Thuật toán nêu trên đây là sự tổng quát trực tiếp của thuật toán Flam - Zowe ([6] 1990), ở đó các tác giả xét H hữu hạn chiều và T (n) là phép chiếu trên siêu phẳng chứa Ci. Thuật toán đó sẽ được đề cập ở Mục 2.4.
21
2.2 Tính chất cơ bản của thuật toán
Các tính chất quan trọng của thuật toán được nêu ở bổ đề và hai hệ quả
sau.
(cid:88)
Bổ đề 2.1. (i) Nếu x ∈ D và n ≥ 0 thì
i λ(n) λ(n)
j α(n)
i α(n)
j (cid:107)T (n)
i x(n) − T (n)
j x(n)(cid:107)2
(cid:88)
i (cid:107)x(n) − x(cid:107)2 − (cid:107)x(n+1) − x(cid:107)2 = i α(n)
λ(n) i i x(n), T (n) i x(n) − x(cid:105) (cid:88) i
(cid:88) (cid:2)2 − (cid:3)(cid:107)x(n) − T (n) + 2 i α(n)
λ(n) i j α(n)
λ(n) i i x(n)(cid:107)2. i j + 2 i∈I (n) Ci và n ≥ 0 thì (cid:88) (ii) Nếu x ∈ (cid:84) i (cid:107)x(n) − T (n)
µ(n) i x(n)(cid:107)2. i (cid:84) (cid:107)x(n) − x(cid:107)2 − (cid:107)x(n+1) − x(cid:107)2 ≥ i∈I (j) Ci và m ≥ n ≥ 0 thì m−1
(cid:88) (cid:88) (iii) Nếu x ∈ (cid:84)m−1
j=n i (cid:107)x(j) − T (j)
µ(j) i x(j)(cid:107)2. j=n i (cid:107)x(n) − x(cid:107)2 − (cid:107)x(m) − x(cid:107)2 ≥ Nói riêng, đánh giá này đúng mỗi khi x ∈ C. +∞
(cid:88) (cid:88) (iv) Dãy (x(n)) là đơn điệu Fejér đối với C và do đó bị chặn. Đồng thời i (cid:107)x(j) − T (j)
µ(j) i x(j)(cid:107)2. j=0 i +∞ > (cid:88) (v) Nếu n ≥ 0 thì i α(n)
λ(n) i (cid:107)x(n) − T (n) i x(n)(cid:107). i (cid:107)x(n+1) − x(n)(cid:107) ≤ Chứng minh. (i) Ta bỏ qua các tính toán sơ cấp. Dễ dàng thấy (i) ⇒ (ii) ⇒
(iii) ⇒ (iv) (dùng Bổ đề 1.5(ii)). (v) suy trực tiếp từ định nghĩa của thuật
toán. Hệ quả 2.1. (Điều kiện đủ của hội tụ theo chuẩn). 22 (i) Nếu phần trong của C khác rỗng thì dãy (x(n)) hội tụ theo chuẩn tới một điểm nào đó trong D. (ii) Nếu dãy (x(n)) có dãy con (x(n(cid:48))) với d(x(n(cid:48)), C) → 0 thì toàn bộ dãy (x(n)) hội tụ theo chuẩn tới một điểm nào đó trong C. Chứng minh. Hệ quả suy ra từ Bổ đề 2.1(iv) và Định lý 1.1. i > 0 với mọi chỉ số i hoặc i < 0 với mọi chỉ số i. (cid:80) i > ε với mỗi chỉ số
i : i tích cực tại n (cid:107)x(n) − Tix(n)(cid:107)2 Nhận xét 2.2. Nếu phần trong của C là rỗng thì sự hội tụ chỉ có thể là hội
tụ yếu. Genel và Lindenstrauss (1975) đưa ra ví dụ về tự ánh xạ không giãn
bền vững T của một tập lồi đóng khác rỗng nào đó trong (cid:96)2 sao cho dãy lặp
(T nx0) hội tụ yếu nhưng không hội tụ theo chuẩn với điểm xuất phát x0 nào
đó. (Phương pháp hội tụ theo chuẩn được nói tới ở Nhận xét 1.7.) Do dãy
(T nx0) là đơn điệu Fejer đối với Fix T (Ví dụ 1.5) nên ta kết luận rằng Fix T
có phần trong rỗng và sự hội tụ theo chuẩn của thuật toán cần có thêm một
số giả thiết. (cid:88) n i : i tích cực tại n Hệ quả 2.2. (Thuật toán chính quy tiệm cận). Thuật toán là chính quy tiệm
cận mỗi khi
(i) lim n : n tích cực đối với i µ(n)
(ii) lim n : n tích cực đối với i α(n)
Chứng minh. (i) Tồn tại ε > 0 sao cho với mọi n đủ lớn µ(n)
i là tích cực tại n. Bổ đề 2.1(iv) kéo theo (cid:80)
n
là hữu hạn. Ngược lại,
(cid:88) (cid:107)x(n) − Tix(n)(cid:107)2 → 0. (cid:88) i (cid:107)x(n) − Tix(n)(cid:107)2. n i : i tích cực tại n Mặt khác, theo Bổ đề 2.1(v),
(cid:88) (cid:107)x(n+1) − x(n)(cid:107) ≤ λ(n)
i α(n) Do vậy (x(n)) là chính quy tiệm cận. (ii) Theo Bổ đề 1.5(iv) và Mệnh đề 1.10, mọi A(n) là κn-co đối với C, trong đó
: i tích cực tại n }. Giả thiết đảm bảo limnκn > 0, )/α(n)
i κn := min{(2 − α(n)
i
do đó kết luận suy ra từ Ví dụ 1.3. Ví dụ đơn giản sau đây cho thấy rằng thuật toán không nhất thiết là chính quy tiệm cận. 23 i i :≡ P{0} = 0; α(n) Ví dụ 2.1. Giả sử H := R, N := 1, T (n)
:≡ 2. Khi đó
x(n) = (−1)nx(0); do đó dãy (x(n)) không là chính quy tiệm cận đối với x(0) (cid:54)= 0. Ít ra thuật toán cần phải hội tụ yếu về một điểm nào đó; tuy nhiên như Ví dụ 2.1 cho thấy cần phải có thêm các giả thiết. 1 Định nghĩa 2.1. Ta nói thuật toán là hội tụ (focusing) nếu với mọi chỉ số i
và mọi dãy con (x(nk))k của thuật toán thì
x(nk) − T (nk) kéo theo x ∈ Ci. x(nk) (cid:42) x
x(nk) → 0
i tích cực tại nk Nhờ nguyên lý bán đóng, ta trực tiếp nhận được ví dụ thứ nhất. 1 Ví dụ 2.2. Với N := 1, T (n) :≡ T và C1 :≡ Fix T . Khi đó thuật toán hội tụ. Nhận xét 2.3. Khái niệm thuật toán hội tụ rất quan trọng và có thể xem như
sự mở rộng của nguyên lý bán đóng đối với các ánh xạ không giãn bền vững. Định lý 2.1. (Lưỡng phân I - dichotomy I). Giả thiết thuật toán hội tụ. Nếu i > 0 với mọi chỉ số i, lim n : n tích cực đối với i µ(n) thì dãy (x(n)) hoặc hội tụ theo chuẩn tới một điểm nào đó trong C hoặc không
có điểm tụ theo chuẩn nào đó. Chứng minh. Do tính đơn điệu Fejér của (x(n)) và Định lý 1.1(v), chỉ cần chỉ
ra rằng điểm tụ theo chuẩn bất kỳ của (x(n)) nằm trong C. Giả sử trái lại rằng
định lý không đúng. Khi đó, tồn tại dãy con (x(nk))k hội tụ tới điểm nào đó
x /∈ C. Ta ký hiệu I1 := {i ∈ {1, . . . , N } : x ∈ Ci} và I2 := {i ∈ {1, . . . , N } : x /∈ Ci}; khi đó I2 khác rỗng. Ta giả thiết (sau khi chuyển qua dãy con nếu cần) rằng i∈I1 I (nk) ∪ I (nk+1) ∪ . . . ∪ I (nk+1−1) = {1, . . . , N }. Bây giờ lấy mk ∈ {nk, . . . , nk+1 − 1} nhỏ nhất sao cho I (mk) ∩ I2 (cid:54)= ∅. Do đó
với nk ≤ m ≤ mk ta có I (m) ⊆ I1. Vì x ∈ (cid:84)
Ci nên theo Bổ đề 2.1(iii),
(cid:107)x(nk) − x(cid:107) ≥ (cid:107)x(mk) − x(cid:107), điều này kéo theo x(mk) → x. (2.1) 24 Sau khi chuyển qua dãy con khác nếu cần, ta có thể giả thiết rằng tồn tại chỉ
số i sao cho (2.2) i ∈ I (mk) ∩ I2 với mọi k. k µ(mk) i i (cid:107)x(mk) − T (mk) x(mk)(cid:107)2. Theo (b) và giả i Theo Bổ đề 2.1(iv), +∞ > (cid:80)
thiết về (µ(n)
), ta kết luận rằng i (2.3) x(mk) − T (mk) x(mk) → 0. Do thuật toán hội tụ nên (2.1), (2.2) và (2.3) kéo theo x ∈ Ci, điều này trái
với i ∈ I2 và định lý được chứng minh. Nhận xét 2.4. Biến thể hữu hạn chiều của định lý trên là khá mới và được
bàn luận (dưới dạng này hay dạng khác) bởi nhiều tác giả khác. Đáng tiếc
là do các ánh xạ không giãn bền vững nói chung không liên tục yếu, cho nên
chứng minh không thực hiện được trong tôpô yếu. Hệ quả 2.3. Giả sử H là hữu hạn chiều và thuật toán hội tụ. Nếu i > 0 lim n : n tích cực đối với i µ(n) với mọi chỉ số i thì dãy (x(n)) hội tụ theo chuẩn tới một điểm nào đó trong C. Chứng minh. Dãy (x(n)) bị chặn (Bổ đề 2.1(iv))) và do đó thuật toán có điểm
tụ theo chuẩn. Sau đó áp dụng Định lý 2.1. Nhận xét 2.5. (Đảm bảo điều kiện "liminf"). Cách đơn giản để đảm bảo i > 0 lim n : n tích cực đối với i µ(n) i ≤ 2 − ε
i ≥ ε3. Hơn i với mọi n đủ lớn tích cực đối với i, bởi vì khi đó µ(n) với một chỉ số i nào đó là giả thiết rằng tồn tại ε > 0 sao cho ε ≤ α(n)
và ε ≤ λ(n)
nữa, giả thiết này tương đương với (Hệ quả 2.2) i > 0 và lim n : n tích cực đối với i µ(n) i < 2. lim n : n tích cực đối với i µ(n) Flam và Zowe đã sử dụng rất kết quả giả thiết này, xem thêm Ví dụ 2.8. i :≡ Ti, Ci := Fix Ti và tồn tại ε > 0 sao cho ε ≤ α(n) Ví dụ 2.3. Giả sử H là hữu hạn chiều và thuật toán là chính quy. Hơn nữa
giả sử rằng T (n)
i ≤ 2 − ε
với mọi n và mọi chỉ số i. Khi đó dãy (x(n)) hội tụ theo chuẩn tới một điểm
nào đó trong C. 25 Chứng minh. Từ nguyên lý bán đóng suy ra rằng thuật toán là hội tụ. Theo
Nhận xét 2.5 lim n : n tích cực đối với i µ(n)
i > 0 với mọi chỉ số i. Kết luận được
suy từ Hệ quả 2.3. i ) hội tụ tích cực theo Định nghĩa 2.2. Cho một thuật toán, ta nói rằng (T (n)
từng điểm (converges actively pointwise) tới Ti với chỉ số i nào đó nếu i d = Tid với mọi d ∈ D. i lim n : n tích cực đối với i T (n) i Mệnh đề 2.1. (Nguyên mẫu của thuật toán hội tụ). Giả sử T1, . . . , TN : D →
D là các ánh xạ không giãn bền vững và Ci := Fix Ti với mọi chỉ số i. Nếu T (n)
hội tụ tích cực theo từng điểm tới Ti với mọi chỉ số i thì thuật toán là hội tụ. i Chứng minh. Cố định chỉ số i và dãy con (x(nk)) của (x(n)) với x(nk) (cid:42) x ∈
D, x(nk) − T (nk)x(nk)
→ 0 và i là chỉ số tích cực tại mọi nk. Ta cần chỉ ra rằng
x ∈ Ci. Cố định một u bất kỳ thuộc H. Do T (nk) PD không giãn nên i i (cid:104)(x(nk) − u) − (T (nk) x(nk) − T (nk) PDu), x(nk) − u(cid:105) ≥ 0 với mọi k. i Cho k → +∞, khi đó theo giả thiết về T (n) và (x(nk)) ta kết luận rằng (cid:104)TiPDu − u, x − u(cid:105) ≥ 0. Do u được chọn tùy ý nên ta có thể chọn u = x + tv với v là véctơ tùy ý và
t ≥ 0. Khi đó (cid:104)TiPD(x + tv) − (x + tv), v(cid:105) ≤ 0; do đó cho t → 0 ta nhận được (cid:104)TiPDx − x, v(cid:105) ≤ 0. Với v = x − TiPDx ta được x = TiPDx. Nhưng x ∈ D nên PDx = x và vì thế x ∈ Fix Ti = Ci. Nhận xét 2.6. Mệnh đề 2.1 cho một giải thích khác của sự kiện là các Ví dụ
2.2 và 2.3 là hội tụ. Định nghĩa 2.3. (Điều khiển). Ta nói thuật toán là tuần hoàn (cyclic) nếu I (n−1) = {u mod N } với n ≥ 1, trong đó ta dùng {1, 2, . . . , N } làm phần dư. Nếu có số nguyên dương p sao
cho i ∈ I (n) ∪ I (n+1) ∪ . . . ∪ I (n+p−1) với mọi chỉ số i và mọi n ≥ 0, 26 thì ta nói về thuật toán đứt đoạn (intermittent) hoặc p-đứt đoạn hoặc điều
khiển đứt đoạn (intermittent control). Ta gọi một thuật toán hầu tuần hoàn
(almost cyclic) nếu nó là đứt đoạn và kỳ dị. Ta nói về điều khiển khối và thuật
toán khối nếu hai điều kiện dưới đây là đúng: m = ∅ 1. Có phân hoạch J1 ∩ . . . ∩ JM = {1, . . . , N } với Jm (cid:54)= ∅ và Jm ∩ J (cid:48) với mọi m, m(cid:48) ∈ {1, . . . , M } và m (cid:54)= m(cid:48). 2. Có số nguyên dương p sao cho với mọi n ≥ 0 và mọi m ∈ {1, . . . , M }, I (n(cid:48)) = Jm với n(cid:48) ∈ {n, n + 1, . . . , n + p − 1}. Cuối cùng nếu ta muốn nhấn mạnh rằng các chỉ số tích cực không nhất thiết
theo một dạng điều khiển nào đó, thì ta nói điều khiển ngẫu nhiên (random
control) và thuật toán ngẫu nhiên (radom algorithm). Rõ ràng là Nhận xét 2.7. Gần đây các thuật toán khối nhận được nhiều sự chú ý trong
cách chữa bệnh bằng bức xạ. Định lý 2.2. (Kết quả tôpô yếu). (i) Giả sử thuật toán là hội tụ và đứt đoạn. Nếu i > 0 với mọi chỉ số i lim n : n tích cực đối với i µ(n) thì dãy (x(n)) là chính quy tiệm cận và hội tụ yếu tới điểm nào đó trong
C. (ii) Giả sử thuật toán hội tụ và p-đứt đoạn đối với số nguyên dương p nào đó. Đặt i : np ≤ j ≤ (n + 1)p − 1 và i tích cực tại j} với mọi n ≥ 0. νn = min{µj (nk+1)p−1
(cid:88) (cid:88) Nếu (cid:80)
n νn = +∞ thì dãy (x(n)) có điểm tụ yếu duy nhất trong C. Chính
xác hơn, có dãy con (xnkp) hội tụ yếu tới điểm tụ yếu duy nhất này của
(x(n)) trong C thỏa mãn i x(j)(cid:107) → 0. j = nkp i ∈ I (j) (cid:107)x(j) − T (j) điều này kéo theo x(nkp+rk) − x(nkp+sk) → 0 27 với mọi dãy (rk), (sk) trong {0, . . . , p − 1}. Nói riêng, điều này xảy ra mỗi
khi i > 0 với mọi chỉ số i. n µ(n) lim n : n tích cực đối với i µ(n) (iii) Giả sử thuật toán hội tụ và dãy (x(n)) hội tụ yếu nếu về một điểm x nào
i = +∞ với chỉ số i nào đó thì x ∈ Ci. Hệ quả là, nếu i = +∞ với mọi chỉ số i thì x ∈ C. đó. Nếu (cid:80)
(cid:80)
n µ(n) Chứng minh. (i) (x(n)) là chính quy tiệm cận (Hệ quả 2.2(i)). Giả sử trái lại
rằng (x(n)) không hội tụ yếu về điểm nào đó trong C. Khi đó theo tính đơn
điệu Fejér của (x(n)) và Định lý 1.1(ii), tồn tại chỉ số i và dãy con (x(nk))k hội
tụ yếu về điểm nào đó x /∈ Ci. Do thuật toán là đứt đoạn nên ta nhận được
mk với nk ≤ mk ≤ nk + p − 1 và i ∈ I (mk) với mọi k ≥ 0. Vì thuật toán là chính quy tiệm cận, nên ta có x(nk) − x(mk) → 0 và do đó (x(nk)) hội tụ yếu tới x. Do thuật toán là hội tụ nên ta kết luận rằng x(mk)(cid:107) > 0. limk(cid:107)x(mk) − T (mk) i i i
Mặt khác, theo Bổ đề 2.1(iv), +∞ > (cid:80)
mâu thuẫn với giả thiết về (µ(n) n µ(mk)
). Vậy kết luận (i) đúng. i (cid:107)x(mk) − T (mk) x(mk)(cid:107). Điều này (n+1)p−1
(cid:88) (cid:88) (ii) Tạm thời cố định c ∈ C. Khi đó, theo Bổ đề 2.1(iii) và định nghĩa νn, i x(j)(cid:107)2 j=np i∈I (j) (cid:107)x(j) − T (j) (cid:107)x(np) − c(cid:107)2 − (cid:107)x((n+1)p) − c(cid:107)2 ≥ νn (nk+1)p−1
(cid:88) (cid:88) với mọi n ≥ 0. Cộng theo n và chú ý tới giả thiết về (νn), ta được dãy con
(x(nkp))k thỏa mãn i x(j)(cid:107) → 0, j = nkp i ∈ I (j) (cid:107)x(j) − T (j) (2.4) Theo Bổ để 2.1(v) ta lại có x(nkp+rk) − x(nkp+sk) → 0 (2.5) với mọi dãy (rk), (sk) trong {0, 1, . . . , p − 1}. Sau khi chuyển qua dãy con nếu
cần, ta có thể giả thiết rằng (x(nkp))k hội tụ yếu tới x ∈ D nào đó. 28 Ta sẽ chứng minh x ∈ C. Thật vậy, xét một chỉ số i bất kỳ. Do thuật toán là đứt đoạn nên có một dãy (rk) trong {0, 1, . . . , p − 1} thỏa mãn x(nkp+rk) (cid:42) x (2.6) (điều này suy ra từ (2.5) với sk ≡ 0) và (2.7) i ∈ I (nkp+rk) với mọi k. Theo (2.4) i (2.8) x(nkp+rk) − T (nkp+rk) x(nkp+rk) → 0. n µ(n) i (cid:107)x(n) − T (n) i x(n)(cid:107)2. Do giả thiết (cid:80) Do thuật toán là hội tụ (2.6), (2.7) và (2.8) kéo theo x ∈ Ci. Do i tùy ý nên
x ∈ C. Theo Định lý 1.1(ii), x là điểm tụ yếu duy nhất của x(n) trong C. Kết
thúc chứng minh phần (ii). i = +∞ nên (iii) Theo Bổ đề 2.1(iv), +∞ > (cid:80)
n µ(n) i x(n)(cid:107)) n : n tích cực đối với i lim((cid:107)x(n) − T (n) phải bằng 0. Do thuật toán là hội tụ nên ta thấy rằng x ∈ Ci và toàn bộ định
lý được chứng minh. i i i > Nhận xét 2.8. (i) là kết quả cơ bản về hội tụ yếu của các tác giả [3]. (ii) là
kết quả mở rộng ý tưởng đã có trước đó. Đó là một kết quả về sự tồn tại điểm
tụ yếu duy nhất của (x(n)) trong C; tuy nhiên giả thiết trước đó hơi khác đôi
chút: tham số nới lỏng ít tổng quát hơn nhưng trọng số điều khiển tổng quát
hơn. (iii) cũng là mở rộng các kết quả đã có của nhiều tác giả khác. Hệ quả 2.4. Giả sử T1, . . . , TN : D → D là các ánh xạ không giãn bền vững,
Ci := Fix Ti và (T (n)
) hội tụ tích cực theo từng điểm tới Ti. Hơn nữa, giả sử
tồn tại ε > 0 sao cho ε ≤ α(n)
i ≤ 2 − ε và ε ≤ λ(n)
với mọi n ≥ 0 và mọi chỉ số
i tích cực tại n. Nếu thuật toán là đứt đoạn thì dãy (x(n)) hội tụ yếu tới một
điểm nào đó trong C.
Chứng minh. Thuật toán là hội tụ (Mệnh đề 2.1) và lim n : n tích cực đối với i µ(n)
0 với mọi chỉ số i (Nhận xét 2.5). Kết luận suy ra từ Định lý 2.2(i). i ≡ Ti thì Hệ quả 2.4 cho kết quả đối với hữu hạn tập. Nhận xét 2.9. Trường hợp riêng của định lý Browder: Nếu thuật toán là hầu
tuần hoàn và T (n) 29 n µ(n) Hệ quả 2.5. Giả sử thuật toán là hội tụ và phần trong của C khác rỗng. Nếu
(cid:80)
i = +∞ với mọi chỉ số i thì dãy (x(n)) hội tụ theo chuẩn tới một điểm nào đó trong C. Chứng minh. Trực tiếp suy ra từ Hệ quả 2.1(i) và Định lý 2.2(ii). Hệ quả 2.6. Giả sử H hữu hạn chiều và thuật toán là hội tụ và p-đứt đoạn.
Nếu (cid:80)
n νn → +∞ (trong đó νn được xác đinh như ở Định lý 2.2(ii)) thì dãy
(x(n)) hội tụ theo chuẩn tới một điểm nào đó trong C. n µ(n) Chứng minh. Theo Định lý 2.2(ii), (x(n)) có điểm tụ yếu x ∈ C. Do H hữu hạn
chiều nên x là điểm tụ theo chuẩn của (x(n)). Từ đó áp dụng Hệ quả 2.1(ii). (cid:88) Nhận xét 2.10. (Đảm bảo điều kiện “tổng phân kỳ”). Một cách đảm bảo cho
(cid:80)
i = +∞ với một chỉ số i nào đó là giả thiết rằng tồn tại ε > 0 sao cho i ≤ 2 − ε với mọi n và n ε ≤ α(n) λ(n)
i = +∞. (cid:88) Điều này tương ứng (trong trường hợp mọi Ti là phép chiếu) với kết quả của
Flam và Zower (xem thêm Ví dụ 2.8(ii)). Cách khác là giả thiết rằng thuật
toán là kỳ dị và i n:n tích cực đối với i (2 − α(n) ) = +∞, α(n)
i n µ(n) i bởi vì lúc đó tổng trên đây bằng (cid:80) . i Từ đây trở về sau ta dành riêng xét tình huống sau đây. i Đặt vấn đề. Ta giữ lại các giả thiết ở Chương 2, trong đó ta đã định nghĩa
thuật toán. Ở đây ta giả thiết thêm rằng T (n)
là phép chiếu trên tập lồi đóng
khác rỗng C(n)
nào đó chứa Ci. i ⊇ Ci với mọi chỉ số i và mọi m ≥ 0. i và T (n) T (n)
i := P (n)
i := PC (n) Ta còn giả thiết rằng D := H, điều này là có thể vì phép chiếu được xác định
khắp mọi nơi. Ta ký hiệu ngắn gọn Pi = PCi với mọi chỉ số i ∈ {1, . . . , N } 30 và gọi thuật toán trong cách đặt này là thuật toán chiếu (projection algorithm).
Ta nói thuật toán chiếu có các tập hằng (constant sets) nếu C(n)
i ≡ Ci với mọi
n ≥ 0 và mọi chỉ số i. Nhận xét 2.11. Về mặt hình thức thuật toán chiếu là sự mở rộng đôi chút
của thuật toán Flam và Zower [6] (tuy nhiên, do ta cho phép các không gian
Hilbert vô hạn chiều và giả thiết các siêu phẳng ít hạn chế hơn, cho nên ta sẽ
nhận được các kết quả thực chất tổng quát hơn. Đương nhiên, tất cả các kết quả trình bày ở các mục trước đây có thể áp
dụng được cho thuật toán chiếu. Tuy nhiên, trước khi có thể làm điều đó ta
cần phải hiểu rõ hơn ý nghĩa của thuật toán chiếu hội tụ. Nguyên mẫu đầu
tiên của thuật toán chiếu hội tụ được diễn đạt theo ngôn từ của sự hội tụ tập
theo nghĩa của Mosco. Bổ đề 2.2. Giả sử (Sn) là một dãy các tập hợp lồi đóng và có tập hợp lồi đóng
S nào đó với S ⊆ Sn với mọi n. Khi đó các điều kiện sau là tương đương: (i) PSn → Ps từng điểm theo chuẩn. (ii) Sn → S theo nghĩa Mosco, nghĩa là hai điều kiện sau được thỏa mãn: (a) Với mọi s ∈ S tồn tại dãy (sn) hội tụ theo chuẩn về s, sn ∈ Sn, ∀n. (b) Nếu (snk)k là dãy hội tụ yếu với snk ∈ Snk với mọi k, thì giới hạn yếu của dãy nằm trong S. → 0, thì giới hạn yếu của dãy (iii) Nếu (xnk)k là dãy hội tụ yếu với xnk − Psnk nằm trong S. (cid:92) Hơn nữa, nếu một (do đó mỗi) trong các điều kiện trên được thỏa mãn
thì n S = Sn. i Chứng minh. (i) ⇔ (ii): Đây là trường hợp không gian Hilbert của Tkusada
(Định lý 3.2 [10]). Chứng minh (ii) ⇔ (iii) và phần “Hơn nữa” khá dễ dàng nên
bị bỏ qua. (cid:92) Định lý 2.3. (Nguyên mẫu thứ nhất của thuật toán chiếu hội tụ). Nếu (P (n)
)
hội tụ tích cực từng điểm tới Pi với mọi chỉ số i, thì thuật toán chiếu hội tụ và n : n tích cực đối với i với mọi chỉ số i. Ci = C(n)
i 31 i Chứng minh. Áp dụng Bổ đề 2.2 cho (C(n) ) n : n tích cực đối với i đối với mọi i. i i n C(n)
) ⊇ (C(2) và (C(n) )n giảm, nghĩa là Ví dụ 2.4. Giả sử Ci = (cid:84) i i ) ⊇ . . . ⊇ (C(n) ) ⊇ . . . (C(1)
i với mọi n ≥ 0 và mọi chỉ số i. Khi đó thuật toán chiếu là hội tụ. Hơn nữa, nếu
thuật toán chiếu là đứt đoạn và lim n : n tích cực đối với i µ(n)
i > 0 với mọi chỉ số
i thì dãy (x(n)) là chính quy tiệm cận và hội tụ yếu tới điểm nào đó trong C. Chứng minh. Mosco đã chứng minh rằng một dãy giảm dần các tập lồi đóng
hội tụ tới giao của chúng. Từ Định lý 2.3 và Bổ đề 2.2 suy ra thuật toán chiếu
là hội tụ. Kết luận bây giờ được suy ra từ Định lý 2.2(i). Nhận xét 2.12. Ballon đã thu được Ví dụ 2.4 với thuật toán là hầu tuần hoàn
(tức đứt đoạn và kỳ dị) và không bị nới lỏng (tức α(n)
i = 1 với mọi n và mọi
chỉ số i là tích cực tại n bất kỳ). Ví dụ 2.5. (Phép chiếu ngẫu nhiên). Giả sử thuật toán chiếu là kỳ dị (tức I (n)
gồm duy nhất một phần tử với mọi n), không bị nới lỏng và có các tập hằng
số. Nếu đối với chỉ số j nào đó, tập Cj là compac bị chặn thì dãy (x(n)) hội tụ
theo chuẩn tới điểm nào đó trong C. Nói riêng, điều này đúng nếu H là hữu
hạn chiều. Chứng minh. Ví dụ 2.4 cho thấy rằng thuật toán hội tụ. Cũng vậy, µ(n)
i = 1
với mọi n ≥ 0 và mọi chỉ số i tích cực tại n. Dãy (x(n)) n : n tích cực đối với j nằm
trong Cj và vì thế phải có một điểm tụ theo chuẩn. Do đó theo Định lý 2.1,
toàn bộ dãy (x(n)) hội tụ theo chuẩn tới điểm nào đó trong C. i Để phát biểu nguyên mẫu thứ hai của thuật toán chiếu hội tụ (cũng như
các kết quả hội tụ theo chuẩn và hội tụ tuyến tính trong các tiết sau) ta cần
thêm một số định nghĩa. Định nghĩa 2.4. Ta nói thuật toán chiếu là hội tụ tuyến tính (linearly focus-
ing) nếu có số β > 0 sao cho βd(x(n), Ci) ≤ d(x(n), C(n)
) với mọi n đủ lớn và
mọi chỉ số i tích cực tại n. Ta nói phép chiếu hội tụ mạnh (strongly focusing) nếu x(nk) (cid:42) x, i ) → 0, i tích cực tại nk kéo theo d(x(nk), Ci) → 0 với mọi chỉ số i d(x(nk), C(nk)
và mọi dãy con (x(nk))k của (x(n)). 32 Theo Định nghĩa 2.1 và tính nửa liên tục dưới yếu của d(·, Ci), ta nhận được hội tụ tuyến tính ⇒ hội tụ mạnh ⇒ hội tụ. Hệ quả 2.7. (Nguyên mẫu thứ hai của thuật toán chiếu hội tụ). Mọi thuật
toán chiếu hội tụ tuyến tính là hội tụ. Nhận xét 2.13. Flam và Zowe [6] đã dùng các thuật toán chiếu hội tụ tuyến
tính trong không gian Euclide rất có kết quả (xem thêm Ví dụ 2.8). Hệ quả 2.8. (Nguyên mẫu của thuật toán chiếu hội tụ tuyến tính). Nếu thuật
toán chiếu có các tập hằng thì thuật toán hội tụ tuyến tính. i Hệ quả 2.9. (Nguyên mẫu của thuật toán chiếu hội tụ mạnh). Giả sử thuật
toán chiếu hội tụ. Nếu các số hạng của dãy (x(n)) tạo nên một tập compac
tương đối thì thuật toán chiếu hội tụ mạnh. Nói riêng, điều này xảy ra khi H
hữu hạn chiều hoặc phần trong của C khác rỗng. Chứng minh. Giả sử không đúng. Khi đó ta có ε > 0, x ∈ H, một chỉ số i và
một dãy con (x(nk))k với x(nk) (cid:42) x, x(nk) − P (nk)
x(nk) → 0, i tích cực tại nk,
nhưng (cid:107)x(nk) − Pix(nk)(cid:107) ≥ ε với mọi k. Do thuật toán hội tụ nên x ∈ Ci. Sau
khi chuyển qua dãy con nếu cần, ta có thể giả thiết (do giả thiết compac) rằng
x(nk) → x. Nhưng khi đó x(nk) − Pix(nk) → x − Pix = 0, ta gặp mâu thuẫn.
Vậy thuật toán chiếu hội tụ mạnh. Nếu H hữu hạn chiều thì các số hạng của
(x(n)) tạo nên tập compac tương đối do (x(n)) bị chặn (Bổ đề 2.1(iv)). Cuối
cùng, nếu int C (cid:54)= ∅ thì (x(n)) hội tụ theo chuẩn (Hệ quả 2.1(i)). 1 1 Hai nguyên mẫu của Thuật toán chiếu hội tụ (Định lý 2.3 và Hệ quả 2.7) 1 := [0, 1/(n + 1)] và
các tập lồi compac
theo nghĩa Mosco (Ví dụ 2.4 và Hệ quả 2.9). Tuy 1 là không bị nới lỏng, như được minh họa ở hai ví dụ sau.
Ví dụ 2.6. Giả sử H := R, N := 1, C := C1 := {0}, C(n)
x(0) = 2. Khi đó thuật toán chiếu hội tụ mạnh và dãy C(n)
giảm dần hội tụ tới C(n)
nhiên thuật toán chiếu không hội tụ tuyến tính. Thực vậy, với n ≥ 1 ta có 1 1 x(n) = = và → 0. 1
n 1
n + 1 d(x(n), C(n)
)
D(x(n), C1) Ví dụ 2.7. Giả sử H := R, N := 1, C := C1 := {0}, C(n)
:= (−1)n[0, 1] và
x(0) ∈ H tùy ý. Khi đó thuật toán chiếu hội tụ tuyến tính, bởi vì x(n) ≡ 0 ∈ C
với mọi n ≥ 2. Tuy nhiên dãy C(n)
các tập lồi compac không hội tụ tới C1 theo
nghĩa Mosco. 33 Sau khi đã cảm nhận được khái niệm thuật toán chiếu hội tụ tuyến tính,
chúng ta cung cấp tài liệu về sự ích lợi của khái niệm này thông qua kết quả
lưỡng phân của Aharoni và Censor. i (cid:80) i∈I λ(m) i Định lý 2.4. (Lưỡng phân II). Giả thiết thuật toán chiếu hội tụ tuyến tính và
có số ε > 0 thỏa mãn ε ≤ α(n)
i ≤ 2 − ε với mọi n lớn và mọi chỉ số i tích cực
tại n. Khi đó, dãy (x(n)) hoặc hội tụ theo chuẩn hoặc không có điểm tụ nào
theo chuẩn. i i∈I
(cid:88) Chứng minh. Giả sử trái lại rằng (x(n)) có ít nhất hai điểm tụ theo chuẩn,
chẳng hạn y và z. Lấy β > 0 thỏa mãn biểu diễn (x(m), ci) ≤ d(X (m), C(m)
)
với mọi m lớn và mọi chỉ số i tích cực tại m. Cố định c ∈ C. Do y /∈ C
(trái lại, hóa ra dãy (x(n)) hội tụ theo chuẩn bởi Hệ quả 2.1(ii)), tập chỉ số
I = {i ∈ {1, . . . , N } : y /∈ Ci} là khác rỗng. Ký hiệu B := y + rBH, trong đó
r := (1/2) min({(cid:107)y − z(cid:107)} ∪ {d(y, Ci) : i ∈ I}).
Khẳng định 1: ∃γ1 > 0 sao cho (x(m) ∈ B và m đủ lớn) ⇒ (cid:107)x(m) − c(cid:107) −
(cid:107)x(m+1) − c(cid:107) ≥ γ1
. Mặt khác, theo Bổ đề 2.1(ii), định nghĩa của β
và (cid:107)y − x(m)(cid:107) ≥ d(y, Ci) − d(x(m), Ci) ta có
(cid:88) (cid:107)x(m) − c(cid:107)2 − (cid:107)x(m+1) − c(cid:107)2 ≥ d2(x(m), C(m) ) µ(m)
i i i∈I ε2β2d2(x(m), C(m) ) ≥ λ(m)
i i∈I ≥ ε2β2r2 (cid:88) . λ(m)
i Mặt khác, (cid:80) i (cid:107)x(m)−c(cid:107)2−(cid:107)x(m+1)−c(cid:107)2 = ((cid:107)x(m)−c(cid:107)−(cid:107)x(m+1)−c(cid:107))×((cid:107)x(m)−c(cid:107)+(cid:107)x(m+1)−c(cid:107)) i (xem Mệnh đề 1.6(i), Mệnh đề 1.6(iii) và Hệ quả (cid:88) (cid:88) và chuẩn của thừa số sau cũng nhiều nhất bằng 2(r + (cid:107)y − c(cid:107)). Gộp tất cả lại
γ1 = ε2β2r2/(2(r + (cid:107)y − c(cid:107))) làm việc và khẳng định 1 được kiểm tra.
Khẳng định 2: ∃γ2 > 0 sao cho (x(m) ∈ B và m đủ lớn) ⇒ (cid:107)x(m+1) − y(cid:107) −
i∈I λ(m)
(cid:107)x(m) − y(cid:107) ≥ γ2
. Với mỗi i ∈ {1, . . . , N }\I, y là là điểm bất động
của ánh xạ không giãn R(m)
1.2). Ta có đánh giá i (R(j)
λ(j) i x(j) − y) + i (R(j)
λ(j) i x(j) − y) i ∈ I i ∈ {1, ... , N } \ I (cid:13)
(cid:13)
(cid:13)
(cid:13)
(cid:13)
(cid:13) (cid:13)
(cid:13)
(cid:13)
(cid:13)
(cid:13)
(cid:13) (cid:107)x(j+1) − y(cid:107) = 34 (cid:88) (cid:88) i x(j) − y|| i ∈ I (cid:88) i ∈ {1, ... , N } \ I
≤ (cid:107)x(j) − y(cid:107) + i {||R(j)
λ(j) i x(j) − x(j)|| + ||x(j) − y||} i ∈ I
(cid:88) ||R(j) ||x(j) − y|| + ≤ λ(j)
i λ(j)
i i {α(j)
λ(j) i i x(j)|| + ||x(j) − y||} i ∈ I
(cid:88) ||x(j) − P (j) ≤ (cid:107)x(j) − y(cid:107) + i ∈ I
(cid:88) ≤ (cid:107)x(j) − y(cid:107) + λ(j)
i {2d(x(j), Ci) + r} i ∈ I ≤ (cid:107)x(j) − y(cid:107) + λ(j)
i {2(d(y, Ci) + ||x(j) − y||) + r}. Do đó γ2 = 2 max{d(y, Ci) : i ∈ I} + 3r làm việc và khẳng định 2 được kiểm
tra. Phần chứng minh còn lại được thực hiện nhanh chóng. Đặt δ := r (< r) γ1
γ1 + γ2 m−1
(cid:88) (cid:88) và tìm n lớn sao cho (cid:107)x(n) − y(cid:107) < d; do đó (x(n)) ∈ B. Bây giờ z là một điểm
tụ theo chuẩn khác của (x(n)) và có khoảng cách dương tới B, vì thế có số m
nhỏ nhất > n với x(m) ∈ B. Theo tính đơn điệu Fejér của (x(n)) và Khẳng định
1 ta có j=n i∈I m−1
(cid:88) (cid:88) (cid:107)y − c(cid:107) ≤ (cid:107)x(m) − c(cid:107) ≤ (cid:107)x(n) − x(cid:107) − γ1 λ(j)
i j=n i∈I ; < δ + (cid:107)y − c(cid:107)γ1 λ(j)
i m−1
(cid:88) (cid:88) do đó j=n i∈I . λ(j)
i < δ
γ1 m−1
(cid:88) (cid:88) Tuy nhiên theo Khẳng định, j=n i∈I δ = r. (cid:107)x(m) − y(cid:107) ≤ (cid:107)x(n) − y(cid:107) + γ2 λ(j)
i < δ + γ2
γ1 điều này mâu thuẫn với y /∈ B. Vì thế dãy (x(n)) có nhiều nhất một điểm tụ
theo chuẩn. Nhận xét 2.14. Như Ví dụ 2.1 đã minh họa, cần phải có thêm một số giả
thiết để đảm bảo có nhiều nhất một điểm tụ theo chuẩn. 35 n µ(n)
i = +∞ với mọi chỉ số i thì x ∈ C. Hệ quả 2.10. Giả sử thuật toán chiếu hội tụ tuyến tính và có số ε > 0 sao
cho ε ≤ α(n)
i ≤ 2 − ε với mọi n lớn và mọi chỉ số i tích cực tại n. Giả thiết
thêm rằng H hữu hạn chiều hoặc int C (cid:54)= ∅. Khi đó dãy x(n) hội tụ theo chuẩn
tới điểm x nào đó. Nếu (cid:80)
i = +∞ với chỉ số i nào đó thì x ∈ Ci. Hệ quả
là nếu (cid:80)
n µ(n) Chứng minh. Theo Hệ quả 2.1.(i), nếu int C (cid:54)= ∅ thì (x(n)) hội tụ theo chuẩn.
Nếu H hữu hạn chiều thì (x(n)) có điểm tụ theo chuẩn; do đó theo Định lý
2.4, dãy (x(n)) cũng hội tụ theo chuẩn. Từ đó kết quả được suy ra từ Định lý
2.2.(iii). i > 0 với mọi chỉ số i thì x ∈ C. Suy ra ngay hai ví dụ sau đây. n µ(n) i = +∞ với mọi chỉ số i thì x ∈ C. Ví dụ 2.8. Giả sử H là hữu hạn chiều, thuật toán chiếu hội tụ tuyến tính và
có số ε > 0 sao cho ε ≤ α(n)
i ≤ 2 − ε với mọi n lớn và mọi chỉ số i tích cực tại
n. Khi đó dãy (x(n)) hội tụ theo chuẩn tới điểm x nào đó.
(i) Nếu lim n : n tích cực đối với i µ(n)
(ii) Nếu int C (cid:54)= ∅ và (cid:80) i∈I Ci, trong đó (cid:88) Ví dụ 2.9. Giả sử H là hữu hạn chiều, thuật toán chiếu có các tập hằng (và
do đó hội tụ tuyến tính theo Hệ quả 2.8) và có số ε > 0 sao cho ε ≤ α(n)
i ≡
α(n) ≤ 2 − ε với mọi n lớn và mọi chỉ số i tích cực tại n. Khi đó dãy (x(n)) hội
tụ theo chuẩn và giới hạn của dãy nằm trong (cid:84) n i = +∞ tương đương với (cid:80) I :≡ {i ∈ {1, . . . , N } : µ(n)
i = +∞}. i = +∞ ở Ví dụ 2.9 thì ta 2 Nhận xét 2.15. Với giả thiết về tham số nới lỏng trong các ví dụ trên đây, điều
i > 0 tương đương với lim n : n tích cực đối với i λ(n)
kiện lim n : n tích cực đối với i µ(n)
i >
0 (xem Nhận xét 2.5) và điều kiện (cid:80)
n λ(n)
n µ(n)
i =
+∞ (xem Nhận xét 2.10) với mọi chỉ số i. 1 1
:≡ 3/2 và λ(n)
(cid:18)
(cid:19) (cid:19) (cid:18) Ví dụ 2.8(i) được suy ra không chỉ từ Hệ quả 2.10, mà còn từ Định lý 2.1.
Ví dụ sau cho thấy rằng nếu bỏ giả thiết (cid:80)
n µ(n)
không thể hy vọng giới hạn của (x(n)) nằm trong Ci.
Ví dụ 2.10. Giả sử H := R, N := 2, C1 := C(n)
[0, +∞). Giả sử x(0) > 0, α(n) :≡ (−∞, 0] và C2 := C(n)
:≡
1 < 3/2 với mọi n. Khi đó :≡ α(n)
2 . . . 1 − x(0), x(n) = 1 − λ(n−1)
1 λ(0)
1 3
2 3
2 36 (cid:88) và vì thế n i x(n) ⇔ µ(n)
i = +∞. lim
n x(n) ∈ C1 ⇔ lim
n i → αi và λ(n(cid:48))
α(n(cid:48)) i → λi Định lý 2.5. Cho một thuật toán chiếu, giả sử P (n)
hội tụ tích cực theo từng
điểm tới Pi với mọi chỉ số i. Hơn nữa, giả sử có dãy con nào đó (n(cid:48)) của (n)
sao cho với mọi chỉ số i với αi ∈ [0, 2] và λi ∈ [0, 1]. Nếu phần trong của C khác rỗng thì dãy (x(n)) hội
tụ theo chuẩn tới một điểm nào đó trong C. Chứng minh. Theo Hệ quả 2.1(i), (x(n)) hội tụ theo chuẩn tới điểm x nào đó.
Ta phải chỉ ra x ∈ C. Thật vậy, trước hết ta khẳng định x(n(cid:48)) → Pix với mọi chỉ số i. P (n(cid:48))
i i i i x(n(cid:48)) − P (n(cid:48)) x(n(cid:48)) − P (n(cid:48)) i i ) kéo theo P (n(cid:48)) N
(cid:88) x(cid:107) ≤ (cid:107)x(n(cid:48)) − x(cid:107) nên ta có P (n(cid:48))
Vì (cid:107)P (n(cid:48))
x → 0. Do
i
λ(n(cid:48))
i → λi > 0 nên ta thấy rằng i là chỉ số tích cực tại n(cid:48) với mọi n(cid:48) đủ lớn.
Giả thiết về (P (n)
x → Pix. Từ đó suy ra điều khẳng định. Bây
giờ i i P (n(cid:48)) i i = 1 x(n+1) = ((1 − α(n(cid:48)) )x(n(cid:48)) + α(n(cid:48)) x(n(cid:48))); λ(n(cid:48))
i N
(cid:88) bằng cách lấy giới hạn theo dãy con (x(n(cid:48))) và từ điều vừa khẳng định, ta có i = 1 x = λi((1 − αi)x + αiPix) N
(cid:88) hay
i = 1 x = Pix. λjαj λiαi
N
(cid:80)
j=1 Mệnh đề 1.10 kéo theo x ∈ C và chứng minh được hoàn thành. i → λi với λi > 0 nào đó Ví dụ 2.11. Giả sử H là hữu hạn chiều, thuật toán chiếu có các tập hằng và
các tham số nới lỏng chỉ phụ thuộc vào n, chẳng hạn α(n)
i ≡ α(n) với mọi chỉ
số i và mọi n. Giả sử thêm rằng có dãy con (n(cid:48)) của (n) sao cho với mọi chỉ số
i, λ(n(cid:48)) 37 i ≤ 2 − ε với mọi n lớn thì dãy (x(n)) hội tụ (i) Nếu có ε > 0 sao cho ε ≤ α(n) theo chuẩn tới điểm nào đó trong C. (ii) Nếu phần trong của C và có dãy con (n(cid:48)(cid:48)) của (n(cid:48)) thỏa mãn α(n(cid:48)(cid:48)) → 2 n µ(n) i = +∞ với mọi chỉ số thì dãy (x(n)) hội tụ theo chuẩn tới điểm nào đó trong C. Chứng minh. (i) Giả thiết về trọng số kéo theo (cid:80)
i. Như vậy (i) suy ra từ Ví dụ 2.9. (ii) suy ra trực tiếp từ Định lý 2.5. Nhận xét 2.16. Để ý là Định lý 2.5 làm việc tốt đặc biệt khi α(n)
i ≡ 2. Vì
trong trường hợp này µ(n)
i ≡ 0 nên không có kết quả nào trước đây được áp
dụng. Nếu bỏ giả thiết int C (cid:54)= ∅ thì kết luận của Định lý 2.5 không còn đúng
(xem Ví dụ 2.1). Định nghĩa 2.5. (Điều khiển). Ta nói thuật toán chiếu xét các tập xa nhất
nếu mỗi n, ít nhất một chỉ số xa nhất là tích cực, tức là I (n)
xa := {i : d(x(n), Ci) = max{d(x(n), Cj) : j = 1, . . . , N }} ∩ I (n) (cid:54)= ∅. Theo Censor, ta nói về điều khiển tập xa nhất nếu thuật toán chiếu là chính quy và xét các tập xa nhất. Rõ ràng là Định lý 2.6. (Kết quả tôpô yếu). Giả sử thuật toán chiếu hội tụ mạnh và xét
các tập từ xa. Hơn nữa, giả sử rằng (i(n)) là dãy chỉ số tích cực xa nhất, tức là
i(n) ∈ I (n) xa với mọi n.
n µ(n) i(n) = +∞ thì có dãy con (x(nk))k của (x(n)) sao cho (i) Nếu (cid:80) max{d(x(nk), Cj) : j = 1, . . . , N } → 0, và (x(nk))k hội tụ yếu tới điểm tụ yếu duy nhất của (x(n)) trong C. i(n) > 0 thì (x(n)) hội tụ yếu tới một điểm nào đó trong C và (ii) Nếu limµ(n) n µ(n) i(n)d(x(n), C(n) max{d(x(n), Cj) : j = 1, . . . , N } → 0. i(n)) hội tụ. Do
i(n)) = 0. Như vậy, ta có thể trích ra dãy con (x(nk))k và cố Chứng minh. (i) Theo Bổ đề 2.1(iv), các chuỗi (cid:80)
đó limnd(x(n), C(n) 38 i(n)) → 0, i(nk) ≡ i và (x(nk)) hội tụ yếu. Do định chỉ số i thỏa mãn d(x(n), C(n)
thuật toán hội tụ mạnh và xét các tập xa nhất, nên ta kết luận rằng max{d(x(nk), Cj) : j = 1, . . . , N } → 0. Theo tính nửa liên tục dưới yếu của d(·, cj) với mọi chỉ số j, giới hạn yếu của
x(nk) nằm trong C. Theo Định lý 2.6(ii), (x(n)) có nhiều nhất một điểm tụ yếu
trong C. Do đó (i) đúng; (ii) được chứng minh tương tự. Nhận xét 2.17. Điều khiển tập xa nhất là khái niệm cũ và thành công. Từ
năm 1954 nhiều tác giả (Agmon, Motzkin và Schoenberg) đã nghiên cứu các
thuật toán chiếu giải hệ bất phương trình tuyến tính nhờ dùng điều khiển tập
xa nhất. Bregman đã xét tình huống khi có tập hợp tùy ý của tương giao các
tập hợp lồi đóng. Kết luận chương. Chương này đã đề cập tới sơ đồ thuật toán, bao gồm
thuật toán chiếu giải bài toán chấp nhận được lồi. Trình bày chi tiết khái niệm
sơ đồ lặp của thuật toán nêu ở tài liệu tham khảo [3], cùng với các khái niệm có
liên quan (thuật toán chính quy tiệm cận, thuật toán không bị nới lỏng, thuật
toán kỳ dị, thuật toán trọng số, ...). Nêu các tính chất cơ bản của thuật toán,
khái niệm thuật toán hội tụ và kết quả hội tụ (định lý lưỡng phân I và II). Với
thuật toán chiếu trình bày các kết quả về sự hội tụ tuyến tính của thuật toán. 39 Luận văn này đề cập tới bài toán chấp nhận được lồi và các thuật toán tìm
nghiệm của bài toán trong không gian Hilbert. Đây là lớp bài toán có ứng dụng
quan trọng trong thực tiễn và được nhiều tác giả quan tâm nghiên cứu trong
nhiều năm gần đây. Luận văn đã trình bày một số nội dung cụ thể sau. 1. Một số khái niệm và kiến thức cơ bản về không gian Hilbert, sự hội tụ
yếu và hội tụ mạnh, toán tử tuyến tính, ánh xạ không giãn (ánh xạ không giãn
bền vững, ánh xạ trung bình, nguyên lý bán đóng), toán tử chiếu, ánh xạ co,
ánh xạ co mạnh, dãy đơn điệu Fejér: Tính chất và một số kết quả có liên quan. 2. Thuật toán giải bài toán chấp nhận được lồi: sơ đồ thuật toán, các dạng
thuật toán (chính quy tiệm cận, nới lỏng, kỳ dị, trọng số, thuật toán chiếu,...);
tính chất cơ bản của thuật toán, các ví dụ và nhận xét. Các kết quả về sự hội
tụ: Định lý lưỡng phân I, sự hội tụ trong tôpô yếu. Nguyên mẫu của thuật toán
chiếu hội tụ, sự hội tụ tuyến tính, định lý lưỡng phân II và sự hội tụ theo tôpô
yếu. Nội dung trình bày trong luận văn xem như là một số kiến thức đã tìm hiểu
bước đầu của tác giả về bài toán chấp nhận được lồi và các thuật toán giải bài
toán. Các kiến thức này tạo cơ sở để sau này tác giả sẽ tìm hiểu thêm các bài
toán và thuật toán khác trong lĩnh vực toán giải tích và toán ứng dụng. 40 Tiếng Việt [1] Phạm Kỳ Anh, Trần Đức Long (2001), Giáo trình hàm thực và giải tích hàm, Nhà xuất bản Đại học Quốc gia Hà Nội. [2] Lê Dũng Mưu, Nguyễn Hiền và Nguyễn Hữu Điển (2014), Giáo trình giải tích lồi và ứng dụng, Nhà xuất bản Đại học Quốc gia Hà Nội. Tiếng Anh [3] H. H. Bauschke, J. M. Borwein (1996), “On projection algorithms for solv-
ing convex feasibility problems”, SIAM REVIEW, 38(3), 367-426, Septem-
ber. [4] H. H. Bauschke, P. L. Combettes (2010), Convex Analysis and Mono-tone Operator Theory in Hilbert Spaces, Springer. [5] F. E. Browder (1967), “Convergence theorems for sequences of nonlinear operators in Banach spaces”, Math. Z., 100, 201-225 . [6] S. D.Flam, J. Zowe (1990), “Relaxed outer projections, weighted averages and convex feasibility”, BTT, 30, 289-300.2.3 Kết quả hội tụ
2.4 Thuật toán chiếu
KẾT LUẬN
Tài liệu tham khảo
