ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC TRẦN XUÂN TRÌU MỘT SỐ PHƯƠNG PHÁP CHIẾU GIẢI HỆ BÀI TOÁN CÂN BẰNG HỖN HỢP TỔNG QUÁT LUẬN VĂN THẠC SĨ TỐN HỌC Chun ngành: Tốn ứng dụng Mã số: 46 01 12 NGƯỜI HƯỚNG DẪN KHOA HỌC TS Trương Minh Tuyên TS Phạm Hồng Trường Thái Nguyên – 2020 ii Lời cảm ơn Tôi xin bày tỏ lòng biết ơn sâu sắc đến TS Trương Minh Tun, người tân tình giúp đỡ tơi suốt q trình học tập, nghiên cứu để hồn thành luận văn Tôi xin chân thành cảm ơn Ban Giám hiệu, thầy giáo, giáo khoa Tốn–Tin, trường Đại học Khoa học, Đại học Thái Nguyên tận tình giúp đỡ tơi suốt q trình học tập nghiên cứu Trường Tôi xin chân thành cảm ơn đồng chí lãnh đạo phịng Giáo dục Đào tạo, Ban giám hiệu trường THCS Tân Lập huyện Vũ Thư, tỉnh Thái Bình tạo điều kiện giúp đỡ suốt thời gian học Nhân dịp này, xin gửi lời cảm ơn chân thành tới gia đình, người thân, bạn bè động viên, khích lệ, tạo điều kiện giúp đỡ tơi q trình học tập nghiên cứu iii Mục lục Lời cảm ơn ii Một số ký hiệu viết tắt iv Mở đầu Chương Kiến thức chuẩn bị 1.1 Không gian Banach phản xạ 1.2 Khoảng cách Bregman ánh xạ Bregman không giãn mạnh 1.2.1 Đạo hàm Gâteaux đạo hàm Fréchet 1.2.2 Hàm lồi khoảng cách Bregman 1.2.3 Hàm lồi hoàn toàn 1.2.4 Phép chiếu Bregman 1.2.5 Ánh xạ Bregman không giãn mạnh Chương Một số phương pháp chiếu giải hỗn hợp tổng quát 2.1 Bài toán cân hỗn hợp tổng quát 2.2 Phương pháp chiếu lai ghép 2.3 Phương pháp chiếu thu hẹp 3 4 12 17 20 hệ toán cân 21 21 24 31 Kết luận 38 Tài liệu tham khảo 39 iv Một số ký hiệu viết tắt X không gian Banach X∗ không gian đối ngẫu X R tập hợp số thực R + tập số thực không âm ∩ phép giao int M phần tập hợp M inf M cận tập hợp số M sup M cận tập hợp số M max M số lớn tập hợp số M M số nhỏ tập hợp số M argminx∈X F (x) tập điểm cực tiểu hàm F X ∅ tập rỗng dom(A) miền hữu hiệu toán tử (hàm số) A R(A) miền ảnh toán tử A A−1 toán tử ngược toán tử A I toán tử đồng lim sup xn giới hạn dãy số {xn } n→∞ lim inf xn giới hạn dãy số {xn } xn → x0 dãy {xn } hội tụ mạnh x0 xn dãy {xn } hội tụ yếu x0 n→∞ x0 F (T ) Fˆ (T ) tập điểm bất động tiệm cận ánh xạ T ∂f vi phân hàm lồi f f M tập điểm bất động ánh xạ T gradient hàm f bao đóng tập hợp M v projfC phép chiếu Bregman lên C Df (x, y) khoảng cách Bregman từ x đến y Mở đầu Bài toán tìm điểm bất động chung họ hữu hạn hay vô hạn ánh xạ không giãn không gian Hilbert hay không gian Banach trường hợp riêng tốn chấp nhận lồi: “Tìm phần tử thuộc giao khác rỗng họ hữu hạn hay vơ hạn tập lồi đóng {Ci }i∈I không gian Hilbert H hay không gian Banach X”, với I tập số Bài toán có nhiều ứng dụng quan trọng lĩnh vực khoa học khác như: Xử lí ảnh, khơi phục tín hiệu, vật lý, y học Khi Ci tập nghiệm toán cân (tổng qt), có nhiều phương pháp đề xuất dựa phương pháp lặp cổ điển tiếng Đó phương pháp lặp Kranoselskii, Mann, Ishikawa, Halpern, phương pháp xấp xỉ mềm hay phương pháp sử dụng siêu phẳng cắt Cho đến vấn đề nghiên cứu phương pháp xấp xỉ nghiệm hệ tốn cân khơng gian Hilbert hay Banach chủ đề thu hút quan tâm nhiều người làm tốn ngồi nước Bằng cách sử dụng công cụ khoảng cách Bregman thay cho khoảng cách thơng thường, người ta tìm nhiều phương pháp xấp xỉ nghiệm lớp tốn cân Ngồi ra, sử dụng khoảng cách Bregman người ta giải toán cân bằng, tốn liên quan khác khơng gian Banach phản xạ mà khơng địi hỏi thêm tính chất hình học khác khơng gian tính lồi hay trơn Năm 2016, T.M Tuyen [21] nghiên cứu đưa ba thuật toán chiếu cho tốn tìm nghiệm hệ tốn cân hỗn hợp tổng quát không gian Banach phản xạ Cụ thể hơn, T.M Tuyen giới thiệu chứng minh hội tụ mạnh ba phương pháp lặp song song dựa phương pháp chiếu lai ghép (hybrid projection method) phương pháp chiếu thu hẹp (shrinking projection method) Mục đích luận văn trình bày lại chi tiết kết T.M Tuyen báo [21] Theo đó, nội dung luận văn chia làm hai chương chính, đó: Chương Kiến thức chuẩn bị Trong chương này, luận văn đề cập đến số vấn đề không gian Banach phản xạ, đạo hàm Gâteaux, đạo hàm Fréchet, hàm lồi, vi phân hàm lồi, phép biến đổi Young-Fenchel, khoảng cách Bregman, phép chiếu Bregman tốn tử Bregman khơng giãn mạnh Chương Một số phương pháp chiếu giải hệ toán cân hỗn hợp tổng quát Nội dung chương kết T.M Tuyen phương pháp chiếu lai ghép hai phương pháp chiếu thu hẹp cho tốn tìm nghiệm hệ toán cân hỗn hợp tổng quát khơng gian Banach phản xạ Ngồi ra, số hệ định lý cho số toán liên quan giới thiệu Chương Kiến thức chuẩn bị Chương bao bồm hai mục Mục 1.1 trình bày số tính chất không gian phản xạ Mục 1.2 giới thiệu khoảng cách Bregman, phép chiếu Bregman tốn tử Bregman khơng giãn mạnh Nội dung chương tham khảo tài liệu [1, 13, 16, 19, 22] 1.1 Không gian Banach phản xạ Trước hết, mục nhắc lại khái niệm không gian Banach phản xạ Định nghĩa 1.1.1 Một không gian Banach X gọi không gian phản xạ, với phần tử x∗∗ không gian liên hợp thứ hai X ∗∗ X, tồn phần tử x thuộc X cho x, x∗ = x∗ , x∗∗ với x∗ ∈ X ∗ Chú ý 1.1.2 Trong luận văn, sử dụng ký hiệu x∗ , x để giá trị phiếm hàm x∗ ∈ X ∗ x ∈ X Mệnh đề 1.1.3 [1] Cho X không gian Banach Khi đó, khẳng định sau tương đương: i) X l�F ⊂ Cn nên ta có Df (xn , x0 ) ≤ Df (projfCn (x0 ), x0 ) = Df (x† , x0 ) Do vậy, theo Mệnh đề 1.2.28, ta thu {xn } hội tụ mạnh đến x† n → +∞ Ta suy điều phải chứng minh Chú ý 2.3.2 Nếu X không gian Banach phản xạ, trơn, lồi chặt f (x) = x thuật tốn (2.28) trở thành    C0 = X,    f  i   yn = ResΘi ,ϕi ,Ψi xn , i = 1, 2, , N, in ∈ argmaxi=1,2, ,N {φ(yni , xn )}, y n = ynin ,     Cn+1 = {z ∈ Cn : φ(z, y n ) ≤ φ(z, xn )},     x n+1 = ΠCn+1 (x0 ) (2.32) Tương tự Mục 2.2, có kết sau: Nếu Định lý 2.3.1, Ψi = với i = 1, 2, , N ta có hệ sau cho hệ tốn cân hỗn hợp 33 Hệ 2.3.3 Cho Ci , i = 1, 2, , N N tập lồi, đóng khác rỗng X Cho f : X −→ R hàm Legendre, bức, bị chặn, khả vi Fréchet lồi hoàn toàn tập bị chặn X Cho Θi : Ci × Ci −→ R thỏa mãn điều kiện C1)-C4) ϕi : Ci −→ R hàm lồi, nửa liên tục từ Ci vào R, với i = 1, 2, , N Giả sử F = ∩N i=1 M EP (Θi , ϕi ) = ∅ Khi với x0 ∈ X, dãy {xn } xác định    C0 = X,    f  i   yn = ResΘi ,ϕi xn , i = 1, 2, , N, (2.33) in ∈ argmaxi=1,2, ,N {Df (yni , xn )}, y n = ynin ,     Cn+1 = {z ∈ Cn : Df (z, y n ) ≤ Df (z, xn )},     x = projf (x ), n+1 Cn+1 hội tụ mạnh đến projfF (x0 ) n → +∞ Nếu Định lý 2.3.1, ϕi = với i = 1, 2, , N , ta có hệ cho hệ tốn cân tổng quát Hệ 2.3.4 Cho Ci , i = 1, 2, , N N tập lồi, đóng khác rỗng X Cho f : X −→ R hàm Legendre, bức, bị chặn, khả vi Fréchet lồi hoàn toàn tập bị chặn X Cho Θi : Ci × Ci −→ R thỏa mãn điều kiện C1)-C4) gọi Ψi : Ci −→ X ∗ ánh xạ đơn điệu, liên tục với i = 1, 2, , N Giả sử F = ∩N i=1 GEP (Θi , Ψi ) = ∅ Khi đó, với x0 ∈ X, dãy {xn } xác định    C0 = X,    f  i   yn = ResΘi ,Ψi xn , i = 1, 2, , N, in ∈ argmaxi=1,2, ,N {Df (yni , xn )}, y n = ynin ,     Cn+1 = {z ∈ Cn : Df (z, y n ) ≤ Df (z, xn )},     f x n+1 = projCn+1 (x0 ), (2.34) hội tụ mạnh đến projfF (x0 ) n → +∞ Nếu Định lý 2.3.1, ϕi = Ψi = với i = 1, 2, , N , ta có hệ sau cho hệ toán cân Hệ 2.3.5 Cho Ci , i = 1, 2, , N N tập lồi, đóng khác rỗng X Cho f : X −→ R hàm Legendre, bức, bị chặn, khả vi Fréchet 34 lồi hoàn toàn tập bị chặn X Cho Θi : Ci × Ci −→ R thỏa mãn điều kiện C1)-C4) với i = 1, 2, , N Giả sử F = ∩N i=1 EP (Θi ) = ∅ Khi đó, với x0 ∈ X, dãy {xn } xác định    C0 = X,    f  i   yn = ResΘi xn , i = 1, 2, , N, (2.35) in ∈ argmaxi=1,2, ,N {Df (yni , xn )}, y n = ynin ,     Cn+1 = {z ∈ Cn : Df (z, y n ) ≤ Df (z, xn )},     f x n+1 = projCn+1 (x0 ), hội tụ mạnh đến projfF (x0 ) n → +∞ Nếu Định lý 2.2.1, Θi = với i = 1, 2, , N ta có hệ cho hệ bất đẳng thức biến phân hỗn hợp Hệ 2.3.6 Cho Ci , i = 1, 2, , N N tập lồi, đóng khác rỗng X Cho f : X −→ R hàm Legendre, bức, bị chặn, khả vi Fréchet lồi hoàn toàn tập bị chặn X Cho ϕi : Ci −→ R hàm lồi, nửa liên tục từ Ci vào R Ψi : Ci −→ X ∗ hàm đơn điệu, liên tục, với i = 1, 2, , N Giả sử F = ∩N i=1 M V I(Ci , ϕi , Ψi ) = ∅ Khi đó, với x0 ∈ X, dãy {xn } xác định    C0 = X,    f  i   yn = Resϕi ,Ψi xn , i = 1, 2, , N, in ∈ argmaxi=1,2, ,N {Df (yni , xn )}, y n = ynin ,     Cn+1 = {z ∈ Cn : Df (z, y n ) ≤ Df (z, xn )},     f x n+1 = projCn+1 (x0 ), (2.36) hội tụ mạnh tới projfF (x0 ) n → +∞ Từ đặc trưng toán tử giải ResfΘi ,ϕi ,Ψi , ta có định lý phương pháp chiếu thu hẹp khác giải toán cân hỗn hợp Định lý 2.3.7 Với x0 ∈ X, dãy {xn } xác định    Q0 = X,    f  i   yn = ResΘi ,ϕi ,Ψi xn , i = 1, 2, , N, in ∈ argmaxi=1,2, ,N {Df (yni , xn )}, y n = ynin ,     Qn+1 = {z ∈ Qn : f (xn ) − f (y n ), z − y n ≤ 0},     f x n+1 = projQn+1 (x0 ), (2.37) ... Một số phương pháp chiếu giải hệ toán cân hỗn hợp tổng quát Nội dung chương kết T.M Tuyen phương pháp chiếu lai ghép hai phương pháp chiếu thu hẹp cho tốn tìm nghiệm hệ tốn cân hỗn hợp tổng quát. .. Phép chiếu Bregman 1.2.5 Ánh xạ Bregman không giãn mạnh Chương Một số phương pháp chiếu giải hỗn hợp tổng quát 2.1 Bài toán cân hỗn hợp tổng quát 2.2 Phương pháp chiếu. .. đối ngẫu X R tập hợp số thực R + tập số thực không âm ∩ phép giao int M phần tập hợp M inf M cận tập hợp số M sup M cận tập hợp số M max M số lớn tập hợp số M M số nhỏ tập hợp số M argminx∈X F