Thuật toán Gradient và phương pháp chỉnh lặp song song

Quỳnh Lưu
Quỳnh Lưu(11591 tài liệu)
(111 người theo dõi)
Lượt xem 200
5
Tải xuống 2,000₫
(Lịch sử tải xuống)
Số trang: 71 | Loại file: PDF
0

Gửi bình luận

Bình luận

Thông tin tài liệu

Ngày đăng: 15/03/2013, 10:11

Mô tả: Thuật toán Gradient và phương pháp chỉnh lặp song song Mục lục Mở đầu 1 1. Một số kiến thức chuẩn bị 3 1.1. ánh xạ không giãn . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2. ánh xạ hút và dãy đơn điệu Fejer . . . . . . . . . . . . . . . . . 6 1.3. Mô tả thuật toán tổng quát . . . . . . . . . . . . . . . . . . . . . . 14 1.4. Một số tính chất cơ bản . . . . . . . . . . . . . . . . . . . . . . . 15 2. Một số thuật toán chiếu 24 2.1. Xây dựng thuật toán . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.2. Một số kết quả hội tụ . . . . . . . . . . . . . . . . . . . . . . . . 27 2.3. Một số điều kiện đảm bảo sự hội tụ theo chuẩn và hội tụ tuyến tính 34 2.4. Một vài ví dụ về tính chính quy tuyến tính (bị chặn) . . . . . . . . 39 3. Thuật toán dưới gradient và phương pháp chỉnh lặp song song 41 3.1. Thuật toán dưới gradient . . . . . . . . . . . . . . . . . . . . . . . 41 3.1.1. Cơ sở . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 3.1.2. Các kết quả hội tụ . . . . . . . . . . . . . . . . . . . . . . 47 3.2. Phương pháp chỉnh lặp song song . . . . . . . . . . . . . . . . . . 50 i 3.2.1. Một số kết quả bổ trợ . . . . . . . . . . . . . . . . . . . . . 50 3.2.2. Một số ví dụ minh hoạ . . . . . . . . . . . . . . . . . . . . 51 3.3. Một vài thử nghiệm số . . . . . . . . . . . . . . . . . . . . . . . . 55 3.3.1. Bài toán với C i là hình cầu . . . . . . . . . . . . . . . . . . 55 3.3.2. Bài toán với C i là tập mức dưới của một hàm lồi . . . . . . 57 3.3.3. Phương pháp chỉnh lặp trong không gian vô hạn chiều . . . 61 Kết luận 62 Tài liệu tham khảo 63 Phụ lục 65 A Một số điểm lưu ý khi tính dưới vi phân 65 1.1. Một vài tính chất của dưới vi phân . . . . . . . . . . . . . . . . . 65 1.2. Một số ví dụ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 ii Lời cảm ơn Bản luận văn này được hoàn thành dưới sự hướng dẫn tận tâm và nhiệt tình của thầy- GS.TSKH. Phạm Kỳ Anh. Qua đây em xin bày tỏ lòng biết ơn chân thành và sâu sắc tới thầy. Cũng nhân dịp này, em xin gửi lời cảm ơn đến các anh nghiên cứu sinh Cao Văn Chung, Vũ Tiến Dũng cùng tập thể cán bộ, cộng tác viên, nhân viên của Trung tâm tính toán hiệu năng cao trường ĐH Khoa học Tự nhiên vì sự giúp đỡ tận tình và rất hiệu quả trong quá trình thực hiện luận văn. Em cũng xin gửi lời cảm ơn tới các thầy trong Bộ môn Toán học tính toán cùng toàn thể thầy giáo, cô giáo trong Khoa Toán-Cơ-Tin học trường ĐH Khoa học Tự nhiên-ĐH Quốc gia Hà Nội đã nhiệt tình giảng dạy, tạo điều kiện và giúp em thu được nhiều kiến thức bổ ích trong suốt quá trình học tập. Hà Nội, ngày 29 tháng 11 năm 2009 Học viên Vũ Anh Mỹ iii Mở đầu Nhiều vấn đề của khoa học và công nghệ đưa về bài toán tìm một điểm trong giao của một số tập lồi. Bài toán này được gọi là Bài toán chấp nhận lồi: Cho X là một không gian Hilbert và C 1 , C 2 , . . . , C N là các tập lồi đóng với giao là một tập C khác rỗng: C = C 1 . . . C N = . Tìm một điểm x C. Chúng ta xét hai trường hợp thường gặp sau: Các tập C i là đơn giản theo nghĩa các phép chiếu (trực giao) lên C i có thể tính toán được tường minh. C i trong trường hợp này có thể là siêu phẳng, nửa không gian, không gian con đóng hay một hình cầu. Không thể tính được phép chiếu lên C i , tuy nhiên có thể thay nó bằng phép chiếu lên một tập xấp xỉ nào đó của C i . C i trong trường hợp này có thể là tập mức dưới của một hàm lồi nào đó. Hướng tiếp cận thường dùng là sử dụng một thuật toán chiếu. Sử dụng các phép chiếu lên các tập C i hoặc tập xấp xỉ C i để xây dựng một dãy các phần tử hội tụ đến nghiệm của bài toán chấp nhận lồi. Một số ứng dụng của bài toán chấp nhận lồi có thể kể ra như sau: Bài toán xấp xỉ tốt nhất, trong đó mỗi tập C i là một không gian con đóng. Khôi phục ảnh (mô hình rời rạc): Mỗi tập C i là một nửa không gian hoặc một siêu phẳng, X là một không gian Euclid. Khôi phục ảnh (mô hình liên tục): X là không gian Hilbert vô hạn chiều. Các thuật toán dưới gradient: Một số tập C i thuộc loại thứ 2, tức là tập mức dưới của một hàm lồi. 1 Trong luận văn này chúng tôi nghiên cứu thuật toán chiếu tổng quát: x (n+1) = A (n) x (n) = N i=1 (n) i [(1 (n) i )I + (n) i P (n) i ] x (n) , (1.1) ở đây P (n) i là phép chiếu lên tập xấp xỉ C (n) i trong bước lặp thứ n, i , i tương ứng là các trọng và các tham số nới lỏng, và thuật toán chỉnh lặp song song giải hệ phương trình đặt không chỉnh A i (x) = 0, i = 1, . . . , N dạng: A i x (n) i + n N + n x (n) i = n x (n) , x (n+1) = 1 N N i=1 x (n) i . Trong đó n là tham số hiệu chỉnh, n là tham số song song hóa. Ngoài các phần Mở đầu, Kết luận và Tài liệu tham khảo, cấu trúc luận văn gồm 3 chương: Chương 1 mang tên "Một số kiến thức chuẩn bị", trình bày các khái niệm cơ bản, một số kết quả phụ trợ và thuật toán dạng tổng quát với các ánh xạ không giãn vững với các kết quả về tính hội tụ của thuật toán tổng quát. Chương 2 mang tên "Một số thuật toán chiếu", trình bày các thuật toán chiếu giải bài toán chấp nhận lồi và các kết quả hội tụ. Chương 3 mang tên "Thuật toán dưới gradient và phương pháp chỉnh lặp song song", trình bày bài toán chấp nhận lồi khi các tập lồi C i cho dưới dạng tập mức dưới của một phiếm hàm lồi, và thuật toán dưới gradient. Cuối chương này là một số ví dụ số minh họa thuật toán dưới gradient và phương pháp hiệu chỉnh song song áp dụng cho bài toán chấp nhận lồi cùng các thử nghiệm số cho các thuật toán trình bày trong Chương 2. 2 Chương 1. Một số kiến thức chuẩn bị 1.1. ánh xạ không giãn Định nghĩa 1. Cho X là một không gian Hilbert, một ánh xạ T : D D, trong đó D là một tập con lồi, đóng, khác rỗng của X gọi là không giãn nếu T x T y x y x, y D Nếu T x T y = x y x, y D, ta nói T là phép đẳng cự. Ngược lại, nếu T x T y < x y với mọi x, y khác nhau trong D ta nói T là ánh xạ không giãn chặt. Nếu T là ánh xạ không giãn thì tập điểm bất động của T, ký hiệu Fix T định nghĩa bởi: Fix T = {x D : x = T x} là tập lồi đóng. Mệnh đề 1 (Nguyên lý tính nửa đóng). Nếu D là một tập con lồi đóng của X, T : D X là ánh xạ không giãn, (x n ) là một dãy trong D và x D, khi đó nếu x n x và x n T x n 0 thì x Fix T. Chứng minh: Từ giả thiết x n x và ta có lim inf n x n x 0 > lim inf n x n x với mọi x 0 = x. Thật vậy, từ đẳng thức x n x 0 2 = x n x 2 + x x 0 2 + 2x n x, x x 0 3 và do giả thiết x n x, số hạng cuối tiến tới 0. Bây giờ giả sử x n x và x n T x n 0, do T không giãn ta có lim inf n x n x lim inf n T x n T x = lim inf n x n T x, từ bất đẳng thức chứng minh ở trên ta suy ra x = T x hay x Fix T. Định nghĩa 2. Nếu N là một ánh xạ không giãn thì ánh xạ trung bình (1 )I + N với [0, 1) cũng là ánh xạ không giãn. Một ánh xạ không giãn vững là một ánh xạ trung bình có dạng 1 2 I + 1 2 N với N là một ánh xạ không giãn. Tính vững có thể hiểu là ngoài tính không giãn T x T y x y, ánh xạ còn thỏa mãn bất đẳng thức chặt hơn là T x T y 2 + (Id T )x (Id T )y 2 x y 2 . Điều này tương đương với bất đẳng thức (ii) trong mệnh đề dưới đây. Mệnh đề 2. Nếu D là một tập con lồi đóng của X và T : D X là một ánh xạ, khi đó các mệnh đề sau tương đương: (i) T là ánh xạ không giãn vững. (ii) T x T y 2 T x T y, x y (T là 1ngược đơn điệu mạnh ). (iii) 2T I là ánh xạ không giãn. Định nghĩa 3. Một ánh xạ được gọi là không giãn vững nới lỏng nếu nó có thể biểu diễn được dưới dạng (1 )I + F với F là một ánh xạ không giãn vững nào đó. Hệ quả 1. Giả sử D là một tập con đóng của X và T : D X là một ánh xạ, khi đó T là ánh xạ được trung bình hóa khi và chỉ khi nó là ánh xạ không giãn vững nới lỏng. 4 Mệnh đề 3. Giả sử C là một tập con lồi đóng khác rỗng của X với phép chiếu tương ứng là P C . Khi đó: (i) Nếu x X thì P C x được đặc trưng bởi 2 tính chất: P C x C và C P C x, x P C x 0 (tiêu chuẩn Kolmogorov). (ii) P C là ánh xạ không giãn vững. Chứng minh: (i): Ta sẽ chứng minh x P C x = min{x z : z C} x P C x, P C x z 0 z C. Ta có x z 2 = x P C x + P C x z 2 = x P C x 2 + 2x P C x, P C x z + P C x z 2 x P C x 2 + 2x P C x, P C x z Như vậy, từ xP C x, P C xz 0 ta suy ra xP C x = min{xz : z C}. Ngược lại từ xP C x = min{x z : z C}. Chọn điểm z + (1)P C x C, > 0, ta có 0 x P C x 2 x (z + (1 )P C x) 2 = x P C x 2 x P C x (z P C x) 2 = 2x P C x (z P C x), (z P C x 0 x P C x (z P C x), z P C x Cho 0 0 x P C x, z P C x x P C x, P C x z 0 (ii): Để chứng minh P C là ánh xạ không giãn vững, dựa vào mệnh đề 2, ta chỉ cần chỉ ra P C x P C y, x y P C x P C y 2 . 5 Bất đẳng thức này tương đương với x y (P C x P C y), P C x P C y 0. Để chứng minh điều này, từ tiêu chuẩn Kolmogorov áp dụng cho P C y và P C x ta có x P C x, P C x P C y 0, P C y y, P C x P C y 0. Cộng từng vế ta có điều cần chứng minh. Định nghĩa 4. Hàm tương ứng d(ã, C) : X R : x inf cC xc = xP C x gọi là hàm khoảng cách tới tập C. Dễ thấy rằng với tập C lồi đóng thì d(ã, C) là hàm lồi và liên tục (và do đó là nửa liên tục dưới yếu). Định nghĩa 5. Một dãy (x n ) trong X được gọi là hội tụ tuyến tính tới giới hạn x với cấp nếu [0, 1) và tồn tại số 0 sao cho x n x n n Mệnh đề 4. Giả sử (x n ) là một dãy trong X, p là một số nguyên dương và x là một điểm trong X. Nếu (x pn ) n hội tụ tuyến tính tới x và (x n x) n là dãy giảm thì toàn bộ dãy (x n ) n cũng hội tụ tuyến tính tới x. 1.2. ánh xạ hút và dãy đơn điệu Fejer Định nghĩa 6. Giả sử D là một tập 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 T là ánh xạ hút đối với tập F nếu với mọi x D \ F, f F T x f < x f Ta nói T là hút mạnh đối với với tập F nếu tồn tại một số > 0 sao cho với mọi x D, f F x T x 2 x f 2 T x f 2 6 Khi cần nhấn mạnh ta nói T là hút đối với tập F. Bổ đề 1 (Dạng của một ánh xạ hút mạnh). Giả sử D là tập lồi đóng khác rỗng, T : D D là ánh xạ không giãn vững có điểm bất động, và (0, 2). Đặt R = (1 )I + T và cố định x D, f Fix T. Khi đó: (i) Fix R = Fix T. (ii) x f, x T x x T x 2 và x T x, T x f 0. (iii) x f 2 Rx f 2 = 2x f, x T x 2 x T x 2 . (iv) R là (2 )/-hút: x f 2 Rx f 2 (2 )/x Rx 2 = (2 )x T x 2 Chứng minh: (i) là hiển nhiên. (ii): Do T là ánh xạ không giãn vững, ta có T x f 2 T x f, x f T x x 2 + x f 2 + 2T x x, x f T x f, x f T x x 2 + x f 2 + 2T x x, x f T x x, x f + x f 2 T x x 2 x T x, x f = x T x, T x f + x T x 2 0 x T x, T x f. (iii): Bằng tính toán trực tiếp x f 2 Rx f 2 =x f 2 (1 )(x f) + (T x f) 2 =x f 2 [1 ) 2 x f 2 + 2 T x f 2 + 2(1 )x f, T x f] =2x f 2 2 x f 2 2 T x f 2 + 2 2 x f, T x f 2x f, T x f =2x f, x f (T x f) 2 [x f 2 + T x f 2 2x f, T x f] =2x f, x T x 2 x T x 2 . 7 . thuật toán dưới gradient. Cuối chương này là một số ví dụ số minh họa thuật toán dưới gradient và phương pháp hiệu chỉnh song song áp dụng cho bài toán. trong bước lặp thứ n, i , i tương ứng là các trọng và các tham số nới lỏng, và thuật toán chỉnh lặp song song giải hệ phương trình đặt không chỉnh A i

— Xem thêm —

Xem thêm: Thuật toán Gradient và phương pháp chỉnh lặp song song, Thuật toán Gradient và phương pháp chỉnh lặp song song, Thuật toán Gradient và phương pháp chỉnh lặp song song

Lên đầu trang

Tài liệu liên quan

Từ khóa liên quan

Đăng ký

Generate time = 0.149852991104 s. Memory usage = 17.56 MB