Luận văn Thạc sĩ Toán học: Về thuật toán chiếu giải bài toán chấp nhận được lồi

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:41

Thêm vào BST

Báo xấu

19
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Đề 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 thuật toán chiếu, 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. Mời các bạn tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Toán học: Về thuật toán chiếu giải bài toán chấp nhận được lồi

ĐẠ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 R+ Tập số thực không âm R ∪ {±∞} Tập số thực mở rộng C Tập số phức N Tập hợp số tự nhiên H Không gian Hilbert `2 Không gian các dãy số vô hạn kxk Chuẩn của véctơ x ∈ H |x| Giá trị tuyệt đối của x ∈ R (x(n) ) hay {xk } Dãy điểm trong H xk * 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 hx, yi 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 dC (x) Khoảng cách từ điểm x tới tập C 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 Lõi bên trong của S (= intaf f S S) r+ 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 PC Toán tử chiếu lên tập C 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 6= ∅. 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 h·, ·i : X × X → R (hoặc C) thỏa mãn với x, y, z ∈ X và λ ∈ R (hoặc C): (i) hx, xi ≥ 0, (ii) hx, xi = 0 ⇒ x = 0, (iii) hy, xi = hx, yi, (iv) hλx, yi = λhx, yi, (v) hx + y, zi = hx, zi + hy, zi. Mỗi tích vô hướng trên X tạo ra một chuẩn tương ứng p kxk = hx, xi 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 Pn Ví dụ 1.1. (i) Rn với tích vô hướng hx, yi = i=1 xi yi là không gian Hilbert trên R. (ii) Cn với tích vô hướng hu, vi = ni=1 = ui v i là không gian Hilbert trên P C, trong đó u = (u1 , u2 , . . . , un ), v = (v1 , v2 , . . . , vn ). (iii) `2 với tích vô hướng ∞ X ha, bi = aj bj j=1 là không gian Hilbert trên C (ở đây a = {aj }∞ ∞ j=1 , b = {bj }j=1 ). Sự kiện các chuỗi đối với ha, bi 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 k · k2 đã có trên `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 tích vô hướng Z ha, bi = fg (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 (hx, yi, λ ∈ R) với tích vô hướng h·, ·i và chuẩn k · k. Ký hiệu d là khoảng cách, nghĩa là p (∀x ∈ H) (∀y ∈ H) kxk = hx, xi và d(x, y) = kx − yk. Tập con C ⊂ H gọi là trực giao nếu x, y ∈ C, x 6= y ⇒ hx, yi = 0. C gọi là trực chuẩn nếu nó là tập con trực giao và có thêm kxk = 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/kxk : 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 | kxk ≤ 1}. Dãy {xk } trong H gọi là hội tụ yếu tới x0 , ký hiệu xk * x0 , nếu ha, xk i → ha, x0 i 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 kxk − x0 k → 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 đó |hx, yi| ≤ kxkkyk. Hơn nữa, |hx, yi| = kxkkyk ⇔ (∃α ∈ 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) kx + yk2 = kxk2 + 2hx, yi + kyk2 . (ii) Luật hình bình hành: kx + yk2 + kx − yk2 = 2(kxk2 + kyk2 ). (iii) Đồng nhất thức phân cực: kx + yk2 − kx − yk2 = 4hx, yi. (iv) Đồng nhất thức Apollonius: kx − yk2 = 2kz − xk2 + 2kz − yk2 − 4kz − (x + y)/2k2 . Chứng minh. (i) Kiểm tra dễ dàng. (ii) và (iii): Từ (i) suy ra kx − yk2 = kxk2 − 2hx, yi + kyk2 . 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) hx, yi ≤ 0 ⇔ (∀α ∈ R+ ) kxk ≤ kx − αyk ⇔ (∀α ∈ [0, 1]) kxk ≤ kx − αyk. (ii) x ⊥ y ⇔ (∀α ∈ R) kxk ≤ kx − αyk ⇔ (∀α ∈ [−1, 1]) kxk ≤ kx − αyk. Chứng minh. (i) Để ý rằng (∀α ∈ R) kx − αyk2 − kxk2 = α(αkyk2 − 2hx, yi). Từ đó trực tiếp suy ra có chiều thuận (⇒). Ngược lại, ∀α ∈ [0, 1], kxk ≤ kx−αk, từ đẳng thức trên suy ra hx, yi ≤ αkyk2 /2. Khi α ↓ 0, ta nhận được hx, yi ≤ 0. (ii) là hệ quả của (i), bởi vì x ⊥ y ⇔ [hx, yi ≤ 0 và hx, −yi ≤ 0]. Hệ quả 1.1. Giả sử x ∈ H, y ∈ H và α ∈ R. Khi đó, kαx + (1 − α)yk2 + α(1 − α)kx − yk2 = αkxk2 + (1 − α)kyk2 . Mệnh đề 1.1. (Tính lồi chặt). Nếu x, y ∈ H thì kx + yk = kxk + kyk kéo theo kyk · x = kxk · 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 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 L (X, Y ) = {T : X → Y | T tuyến tính và liên tục} và L (X) = L (X, X). Với chuẩn toán tử xác định bởi (∀T ∈ L (X, Y )) kT k = sup kT (B(0, 1))k = sup kT (x)k x∈X,kxk≤1 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 kTi xk < +∞. Khi đó, supi∈I kTi k < +∞. Đị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) = hx, ui. Hơn nữa, kf k = kuk. 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) hT x, yi = hx, T ∗ yi. 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 kxa − xk → 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 3 x và Vy 3 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 : hz − w, ui > 0} và {z ∈ H : hz − w, ui < 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 * 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 * x và kxn k → kxk]. 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 kT x − T yk ≤ kx − yk với mọi x, y ∈ D. Nếu kT x − T yk = kx − yk 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 kT x − T yk < kx − yk 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. • 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ì xn * x kéo theo x ∈ Fix T, xn − T xn → 0 trong đó các ký hiệu “→” và “*” 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 1 1 Id + N với ánh xạ không giãn N nào đó. 2 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) kT x − T yk2 ≤ hT x − T y, x − yi 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ì PC x được đặc trưng bởi PC x ∈ C và hy − PC x, x − PC xi ≤ 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 7→ inf c∈C kx − ck = kx − PC (x)k đượ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 kxn − xk ≤ αβ 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à (kxn − xk)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 kxpn − xk ≤ αβ 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}. Ta có đánh giá 1 np kxm − xk ≤ kxpn − xk ≤ α β p 1 np+r   β p α  p1 m = ≤  p−1  β  1 r 1 β p βp 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 kT x − f k < kx − f k. 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 κkx − T xk2 ≤ kx − f k2 − kT x − f k2 . 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 7→ 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. Ví dụ 1.2. Cho D là khoảng đối xứng lồi đóng trong R chứa [−1, +1]. Đặt ( 1 2 2 |x| nếu |x| ≤ 1, T : D → D : x 7→ 1 |x| − 2 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) hx − f, x − T xi ≥ kx − T xk2 và hx − T x, T x − f i ≥ 0. (iii) kx − f k2 − kRx − f k2 = 2αhx − f, x − T xi − α2 kx − T xk2 . (iv) R là (2 − α)/α - co: kx − f k2 − kRx − f k2 ≥ (2 − α)/αkx − Rxk2 = (2 − α)/αkx − T xk2 . 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ó kx − sk2 − kRx − sk2 ≥ (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 := Tn xn 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ó κkxn−1 − xn k2 ≤ kxn−1 − f k2 − kxn − f k2 . − xn k2 là hữu hạn. Từ P Cộng các bất đẳng thức này cho thấy rằng n kxn−1 đó 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 n x0 )n≥0 là chính qui tiệm cận với mọi x0 ∈ D. Mệnh đề sau chỉ ra các ánh xạ co (mạnh) đối với hợp và tổ hợp lồi. 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à N T i=1 Fix Ti 6= ∅. Khi đó TN (i) Fix(TN TN −1 . . . T1 ) = i=1 Fix Ti và TN TN −1 . . . T1 là ánh xạ co. (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à 6= {0}, D := H, N := 2 và T1 := T2 := − Id. Khi đó Fix T1 ∩ Fix T2 = {0} ⊆ và = 6 H ≡ Fix(T2 T1 ). 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. 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à N T i=1 Fix Ti 6= ∅. Hơn nữa, giả sử λ1 , . . . , λN > 0 với λ1 + · · · + λN = 1. Khi đó P N TN PN (i) Fix i=1 λi Ti = i=1 Fix Ti và i=1 λi Ti là ánh xạ co. PN (ii) Nếu mọi Ti là κt -co thì i=1 λi Ti là min{κ1 , . . . , κN }-co. Nhận xét P1.3. Khác vớiTnhận xét trước đây, có thể chứng minh rằng công N N thức Fix i=1 λi Ti = i=1 Fix Ti vẫn còn đúng ngay cả khi Ti không còn là á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 đó, P1 + P2 P1 + . . . + PN PN −1 . . . P1 T := N TN co chặt, Fix T = i=1 Si và dãy lặp (T n x0 ) là chính quy tiệm cận với mọi x0 . 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 kxn+1 − ck ≤ kxn − ck 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 {PC xn } 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 − PC xn → 0. Hơn nữa, nếu {xn } hội tụ tới x ∈ C nào đó thì kxn − xk ≤ 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, kxn − xk ≤ 2(1 − α)n/2 d(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 + tn T 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 n x0 ) 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 n x0 ) 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 n x0 ) 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 n x0 ) 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 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: N \ C := Ci 6= ∅. i=1 (n) Với mỗi i = 1, . . . , N (ta sẽ gọi i là chỉ số) và mỗi n ≥ 0, giả sử Ti :D→D là ánh xạ không giãn bền vững (firmly nonexpansive mapping) với (n) Fix Ti ⊇ Ci , (n) giả sử αi ∈ [0, 2] là các tham số nới lỏng (relaxation parameter) và (n) (n) (n) (n) Ri := (1 − αi ) Id +αi Ti (n) (n) là các ánh xạ nới lỏng tương ứng của Ti (nới lỏng dưới nếu αi ∈ [0, 1], nới (n) (n) lỏng trên nếu αi ∈ [1, 2]), giả sử (λi )Ni=1 ở trong [0, 1] là trọng số (weight),