Tài liệu Một số phương pháp giải bài toán cân bằng có cấu trúc

BỘ GIÁO DỤC ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI ———————- TRỊNH NGỌC HẢI MỘT SỐ PHƯƠNG PHÁP GIẢI BÀI TOÁN CÂN BẰNG CÓ CẤU TRÚC LUẬN ÁN TIẾN SĨ TOÁN HỌC Hà Nội - 2018 BỘ GIÁO DỤC ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI ———————- TRỊNH NGỌC HẢI MỘT SỐ PHƯƠNG PHÁP GIẢI BÀI TOÁN CÂN BẰNG CÓ CẤU TRÚC Ngành: Toán học Mã số: 9460101 LUẬN ÁN TIẾN SĨ TOÁN HỌC CÁN BỘ HƯỚNG DẪN: TS. Lê Quang Thủy GS.TSKH. Phạm Kỳ Anh Hà Nội - 2018 LỜI CAM ĐOAN Tôi xin cam đoan những kết quả trình bày trong luận án này, dưới sự hướng dẫn của TS. Lê Quang Thủy và GS. TSKH. Phạm Kỳ Anh, là trung thực và chưa từng được công bố trong bất kỳ công trình của ai khác. Những kết quả viết chung với thầy hướng dẫn và các cộng sự đã được sự đồng ý của các đồng tác giả khi đưa vào luận án. Hà nội, ngày 02 tháng 10 năm 2018 Nghiên cứu sinh Thay mặt tập thể hướng dẫn TS. Lê Quang Thủy Trịnh Ngọc Hải 2 LỜI CẢM ƠN Trước hết, tôi xin bày tỏ lòng biết ơn chân thành và sâu sắc tới hai thầy hướng dẫn, TS. Lê Quang Thủy và đặc biệt GS. TSKH. Phạm Kỳ Anh. Tôi vô cùng biết ơn sự giúp đỡ tận tình, quý báu mà hai thầy đã dành cho tôi trong suốt thời gian làm nghiên cứu sinh. Hai thầy đã từng bước dẫn dắt, truyền cho tôi niềm đam mê nghiên cứu cùng nhiều kinh nghiệm, kỹ năng, kiến thức quý báu, đồng thời luôn động viên khích lệ để tôi vượt qua những thử thách trên bước đường làm khoa học. Tôi xin chân thành cảm ơn Viện Toán ứng dụng và Tin học, Viện Sau đại học, trường Đại học Bách Khoa Hà Nội đã tạo điều kiện cho tôi có nhiều thời gian tập trung nghiên cứu để hoàn thành luận án và khóa học nghiên cứu sinh. Công tác quản lý đào tạo và môi trường nghiên cứu của Trường đã góp phần không nhỏ để cho luận án này được hoàn thành đúng dự định. Tôi xin gửi lời cảm ơn sâu sắc tới các thầy, các anh chị và các bạn trong nhóm Xêmina liên cơ quan Đại học Khoa học Tự nhiên, Đại học Bách Khoa Hà Nội, Viện nghiên cứu cao cấp về Toán. Nhóm đã tạo cho tôi nhiều cảm hứng trong nghiên cứu khoa học và sự gắn bó với môi trường nghiên cứu. Đặc biệt, tôi xin gửi lời cám ơn chân thành tới GS. TSKH. Lê Dũng Mưu. Thầy đã giúp đỡ tôi rất nhiều về chuyên môn, gợi ý cho tôi những ý tưởng mới trong nghiên cứu. Bản luận án này sẽ không thể hoàn thành nếu không có sự thông cảm, chia sẻ và giúp đỡ của những người thân trong gia đình. Tôi xin bày tỏ lòng biết ơn sâu sắc tới bố mẹ, các anh chị em trong hai bên gia đình nội ngoại. Đặc biệt xin cảm ơn vợ và hai con gái yêu quý, những người đã vì tôi mà phải chịu nhiều thiệt thòi vất vả; đã luôn cảm thông và sẻ chia gánh nặng cùng tôi suốt những năm tháng qua để tôi có thể hoàn thành luận án này. 3 MỤC LỤC Trang Lời cam đoan 2 Lời cảm ơn 3 Mục lục 4 Bảng kí hiệu 6 Bảng các chữ viết tắt 7 Mở đầu 8 . Chương 1 Một số kiến thức chuẩn bị 1.1 Các khái niệm và kết quả cơ bản . . . . . . . . . . . . . . . . 1.2 Bài toán cân bằng và mối liên hệ với các bài toán khác . . . 1.2.1 Bài toán bất đẳng thức biến phân . . . . . . . . . . . . 1.2.2 Bài toán cân bằng Nash trong trò chơi không hợp tác 1.2.3 Bài toán điểm yên ngựa . . . . . . . . . . . . . . . . . 1.3 Sự tồn tại và duy nhất nghiệm của bài toán cân bằng . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chương 2 Bài toán cân bằng với song hàm phân rã thành tổng hoặc hiệu các song hàm thành phần 2.1 Phân rã song hàm thành tổng của hai song hàm thành phần . . . . 2.1.1 Thuật toán phân rã tuần tự . . . . . . . . . . . . . . . . . . . . 2.1.2 Thuật toán phân rã song song . . . . . . . . . . . . . . . . . . . 2.1.3 Trường hợp song hàm chứa nhiễu . . . . . . . . . . . . . . . . 2.1.4 Thử nghiệm số và ứng dụng . . . . . . . . . . . . . . . . . . . . 2.2 Phân rã song hàm thành hiệu của hai song hàm thành phần . . . . 2.2.1 Thuật toán và sự hội tụ . . . . . . . . . . . . . . . . . . . . . . . 2.2.2 Thử nghiệm số . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Phương pháp phân rã kết hợp ergodic . . . . . . . . . . . . . . . . . 2.3.1 Phương pháp ergodic-phân rã tuần tự . . . . . . . . . . . . . . 2.3.2 Phương pháp ergodic-phân rã song song . . . . . . . . . . . . 2.3.3 Thử nghiệm số . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 16 20 20 22 22 23 . . . . . . . . . . . . 27 28 31 35 37 39 46 47 51 55 55 60 63 Chương 3 Bài toán cân bằng hai cấp 67 3.1 Phương pháp chiếu dưới đạo hàm cho bài toán cân bằng hai cấp . . . 68 4 3.1.1 Thuật toán và sự hội tụ . . . . . . . . . . . . . . . . . . . . . . . 3.1.2 Áp dụng cho bài toán EP( f , Fix ( T )) . . . . . . . . . . . . . . . 3.1.3 Thử nghiệm số và ứng dụng . . . . . . . . . . . . . . . . . . . . 3.2 Phương pháp ánh xạ co cho bài toán EP( f , Fix ( T )) . . . . . . . . . . 3.2.1 Tính co của ánh xạ nghiệm Uλ . . . . . . . . . . . . . . . . . . 3.2.2 Thuật toán ánh xạ co cho bài toán cân bằng trên tập điểm bất động . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.3 Thử nghiệm số . . . . . . . . . . . . . . . . . . . . . . . . . . . Chương 4 Nghiệm chung của họ hữu hạn bài toán cân bằng và bài toán điểm bất động 4.1 Tìm nghiệm chung của họ hữu hạn các bài toán cân bằng và điểm bất động . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1.1 Thuật toán Armijo lai ghép . . . . . . . . . . . . . . . . . . . . 4.1.2 Thử nghiệm số . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Tìm nghiệm chung của họ hữu hạn các bài toán cân bằng và bài toán điểm bất động của nửa nhóm không giãn . . . . . . . . . . . . . . . 4.2.1 Thuật toán đạo hàm tăng cường lai ghép . . . . . . . . . . . . 4.2.2 Thử nghiệm số . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 75 76 82 82 . 87 . 92 96 . 97 . 97 . 109 . 113 . 114 . 118 Kết luận 121 Danh mục công trình khoa học của tác giả liên quan đến luận án 122 Tài liệu tham khảo 123 5 BẢNG KÍ HIỆU R R+ H ⟨ x, y⟩ ∥x∥ xn → x xn ⇀ x Rn l2 PC ( x ) NC ( x ) ∂g( x ) ∂2 f ( x, x ) S:C→H Fix (S) VI( A, C ) Sol ( A, C ) EP( f , C ) Sol ( f , C ) EPS ( f , C ) EPD ( f , C ) ∅ 2 Tập hợp các số thực Tập hợp các số thực không âm Không gian Hilbert thực Tích vô hướng của hai véc tơ x và y Chuẩn của vectơ x trong không gian Hilbert H Dãy { x n } hội tụ mạnh tới x Dãy { x n } hội tụ yếu tới x Không gian Hilbert thực n chiều với tích vô hướng ⟨ x, y⟩ := ∑in=1 xi yi , trong đó x = ( x1 , . . . , xn ) , y = (y1 , . . . , yn ) ∈ Rn Không gian Hilbert thực các dãy khả tổng bậc hai với tích vô hướng ⟨ x, y⟩ := ∑i∞=1 xi yi , trong đó x = ( x1 , x2 , . . .), y = (y1 , y2 , . . .) ∈ l 2 Phép chiếu vuông góc của x ∈ H lên tập C, tức PC ( x ) := argminy∈C ∥y − x ∥ Nón pháp tuyến ngoài của tập lồi C tại x, tức NC ( x ) := {w ∈ H : ⟨w, y − x ⟩ ≤ 0 ∀y ∈ C } Dưới vi phân của hàm g tại x, là tập ∂g( x ) := {w ∈ H : ⟨w, y − x ⟩ ≤ g(y) − g( x ) ∀y ∈ H } Dưới vi phân của hàm f ( x, .) tại x Ánh xạ S từ tập C vào H Tập điểm bất động của ánh xạ S Bài toán bất đẳng thức biến phân của toán tử A trên C Tập nghiệm của bất đẳng thức biến phân cho toán tử A trên C Bài toán cân bằng của song hàm f trên C Tập nghiệm của bài toán cân bằng cho song hàm f trên C Bài toán cân bằng với song hàm được phân rã thành tổng hai song hàm thành phần f = f 1 + f 2 Bài toán cân bằng với song hàm được phân rã thành hiệu hai song hàm thành phần f = f 1 − f 2 Tập rỗng Kết thúc chứng minh 6 BẢNG CÁC CHỮ VIẾT TẮT BEP CDMA DEP EP FP NCP OP SP VI Bài toán cân bằng hai cấp Mạng đa truy cập phân chia theo mã Bài toán cân bằng đối ngẫu Bài toán cân bằng Bài toán điểm bất động Bài toán bù phi tuyến Bài toán tối ưu Bài toán yên ngựa Bài toán bất đẳng thức biến phân 7 MỞ ĐẦU Cân bằng (equilibria) thường được hiểu như là một trạng thái đồng đều giữa các quá trình hoặc lực lượng đối lập. Trong Cơ học, hệ vật đạt được trạng thái cân bằng khi tổng các lực tác động vào hệ vật đó bằng 0. Trong Sinh học, một hệ sinh thái ở trạng thái cân bằng khi số loài thú mồi và săn mồi đạt được tỉ lệ tương đồng nhau. Cân bằng là một trạng thái rất quan trọng của vạn vật. Mọi sự tồn tại trong tự nhiên muốn bền vững, phải đạt được trạng thái này. Trong Toán học, mô hình cân bằng có thể được xem như mở rộng của mô hình tối ưu hóa với nhiều chủ thể tham gia. Mỗi chủ thể có mục tiêu khác nhau, thậm chí đối lập nhau. Do đó, rất khó tìm được một phương án tối ưu cho tất cả các chủ thể. Trong tình huống này, mô hình cân bằng tỏ ra phù hợp, để giải quyết các mâu thuẫn về lợi ích. Cho C là tập lồi, đóng, khác rỗng trong không gian Hilbert thực H, f : C × C → R là song hàm thỏa mãn tính chất cân bằng f ( x, x ) = 0 với mọi x ∈ C. Xét bài toán tìm x ∗ ∈ C sao cho f ( x ∗ , y) ≥ 0 ∀y ∈ C. (EP( f , C )) Bài toán EP( f , C ) được H. Nikaido và K. Isoda [60] đề xuất lần đầu vào năm 1955 nhằm tổng quát hóa bài toán cân bằng Nash. Năm 1972, nó tiếp tục được Ky Fan nghiên cứu dưới dạng bất đẳng thức minimax [31]. Tên gọi Bài toán cân bằng được GS. Lê Dũng Mưu và W. Oettli đưa ra vào năm 1992 [55]. Điểm lý thú của bài toán này là nó bao hàm một loạt các bài toán riêng lẻ khác nhau trong một thể thống nhất, chẳng hạn như bài toán tối ưu, bài toán cân bằng Nash, bài toán điểm bất động, bất đẳng thức biến phân, bài toán điểm yên ngựa . . . Ví dụ, khi chọn f ( x, y) := g(y) − g( x ), trong đó g : C → R, bài toán EP( f , C ) sẽ trở thành bài toán tối ưu tìm x ∗ ∈ C sao cho g( x ∗ ) ≤ g(y) ∀y ∈ C. (OP( g, C )) Trong trường hợp f ( x, y) := ⟨ Fx, y − x ⟩, với F : C → C là một ánh xạ, bài toán cân bằng sẽ trở thành bài toán bất đẳng thức biến phân tìm x ∗ ∈ C sao cho ⟨ Fx ∗ , y − x ∗ ⟩ ≥ 0 8 ∀y ∈ C. (VI( F, C )) Mặt khác, các phương pháp giải và kết quả nghiên cứu của từng bài toán riêng lẻ nói trên có thể được mở rộng và tổng quát hóa để áp dụng trở lại cho bài toán cân bằng. Các nghiên cứu về bài toán EP( f , C ) có thể tạm chia thành hai hướng: các nghiên cứu định tính bao gồm nghiên cứu sự tồn tại nghiệm, cấu trúc tập nghiệm, sự ổn định nghiệm [10, 12, 30, 45, 54] và các nghiên cứu định lượng, bao gồm đề xuất các giải thuật, nghiên cứu tốc độ hội tụ của các thuật toán [6,7,15,28,32,44,57, 65,70], áp dụng bài toán cân bằng vào thực tế [36,38,64]. Trong các hướng nghiên cứu trên, việc đề xuất các thuật giải cho bài toán cân bằng chiếm một tỉ trọng lớn. Hai phương pháp chính để giải bài toán cân bằng là phương pháp điểm gần kề [8] và phương pháp chiếu tổng quát [65]. Phương pháp điểm gần kề (PPM Proximal Point Method) bao gồm việc giải một bài toán cân bằng hiệu chỉnh tại f mỗi bước lặp. Giả sử tại bước lặp k, biết x k , ta tính xấp xỉ tiếp theo x k+1 = Jλ ( x k ), f trong đó, Jλ là giải thức của song hàm f với tham số λ > 0, được cho bởi: { } 1 f Jλ ( x ) = z ∈ H : f (z, y) + ⟨y − z, z − x ⟩ ≥ 0 ∀y ∈ C , x ∈ H. λ (0.1) Với giả thiết f đơn điệu, lồi và nửa liên tục dưới theo biến thứ hai, hê-mi liên tục f theo biến thứ nhất, ánh xạ Jλ là đơn trị và không giãn. Tuy nhiên, nếu f thuộc lớp hàm đơn điệu tổng quát hơn, chẳng hạn f là giả đơn điệu, thì bài toán cân f bằng trong (0.1) không còn đơn điệu mạnh, và do đó, Jλ , nói chung, là không đơn trị. Vì vậy, phương pháp PPM không thể áp dụng trong trường hợp này. Ngoài ra, thao tác giải bài toán cân bằng phụ tại mỗi bước lặp khiến cho phương pháp PPM khá phức tạp về mặt tính toán. Phương pháp chiếu tổng quát có thể khắc phục các nhược điểm này của PPM. Tại bước lặp k, giả sử biết x k , ta tính xấp xỉ f f tiếp theo x k+1 = Uλ ( x k ), trong đó, Uλ là ánh xạ nghiệm của song hàm f với tham số λ > 0, được cho bởi { } 1 f 2 (0.2) Uλ = argmin λ f ( x, y) + ∥y − x ∥ : y ∈ C . 2 Với giả thiết song hàm f lồi, nửa liên tục dưới theo biến thứ hai, bài toán tối ưu f f trong (0.2) là lồi mạnh, và do đó, Uλ đơn trị. Hơn nữa, việc tính Uλ đơn giản hơn f rất nhiều so với tính Jλ . Trong trường hợp f ( x, y) = ⟨ Fx, y − x ⟩, với F là ánh xạ trên C, phương pháp chiếu tổng quát cho bài toán cân bằng quay trở về phương pháp chiếu truyền thống cho bài toán bất đẳng thức biến phân, có dạng ( ) k +1 k k x = PC x − λFx , trong đó, PC là phép chiếu lên C. Đây có thể coi là phương pháp cơ bản và đơn giản nhất cho bài toán VI(F, C). Năm 2014, Phạm Duy Khánh và Phan Tú Vượng [43] đã chứng minh phương pháp này hội tụ tuyến tính tới nghiệm duy nhất của 9 bài toán VI(F, C) với giả thiết F giả đơn điệu mạnh và liên tục Lipschitz trên C. Trong luận án, chúng tôi sẽ mở rộng kết quả này cho bài toán cân bằng. Để giảm nhẹ điều kiện đặt lên song hàm f , các tác giả trong [65] đã đề xuất phương pháp đạo hàm tăng cường cho bài toán cân bằng:  { }  yk = argmin λ f ( x k , y) + 1 ∥y − x k ∥2 : y ∈ C 2 } {  x k+1 = argmin λ f (yk , y) + 1 ∥y − x k ∥2 : y ∈ C . 2 Phương pháp này được tổng quát hóa từ phương pháp tương ứng cho bài toán điểm yên ngựa [48]. Với giả thiết song hàm f giả đơn điệu, thỏa mãn điều kiện Lipschitz, thuật toán đạo hàm tăng cường hội tụ yếu tới nghiệm của bài toán EP( f , C ). Đặc điểm chung của các phương pháp giải xấp xỉ bài toán cân bằng là chúng sinh ra một dãy lặp hội tụ tới nghiệm của bài toán. Nói chung, trên mỗi bước lặp của thuật toán, ta cần giải một bài toán phụ. Chi phí tính toán để giải các bài toán phụ này là một trong những yếu tố chính ảnh hưởng đến tính hiệu quả và tốc độ của thuật toán. Một trong những ý tưởng để giảm chi phí tính toán cho các bài toán phụ là phân rã song hàm f ban đầu thành tổng hoặc hiệu các song hàm thành phần: f = f 1 ± f 2 . Khi đó, thay vì xử lí song hàm f , ta chỉ cần làm việc với từng song hàm thành phần. Ý tưởng này đặc biệt hữu ích khi song hàm f có dạng phức tạp, trong khi các song hàm thành phần có các dạng đơn giản hoặc đặc biệt. Phương pháp phân rã đã được áp dụng rộng rãi cho các bài toán tối ưu và bất đẳng thức biến phân [9, 37] và thu được các kết quả rất đáng khích lệ. Tuy nhiên, trong trường hợp của bài toán cân bằng, các kết quả thu được của phương pháp này vẫn còn rất hạn chế. Năm 2009, để giải bài toán cân bằng EP( f , C) với f = f 1 + f 2 , Moudafi [53] đã đề xuất phương pháp phân rã sau:  n n n n+1 theo công thức   Giả sử biết x , tính y , z và x   f1 n  n  y = Jrn ( x ), f  zn = Jrn2 ( x n ),     n n    x n +1 = y + z , 2 trong đó, rn > 0 thỏa mãn điều kiện ∞ ∞ n =0 n =0 ∑ rn = ∞, ∑ rn2 < ∞. Với giả thiết các song hàm f 1 , f 2 đơn điệu, tác giả đã chứng minh dãy ergodic của { x n } hội tụ yếu tới nghiệm của bài toán. Có thể thấy nhược điểm chính của phương pháp này là tại mỗi bước lặp, ta cần tính giải thức của hai song hàm f 1 và f 2 . Như đã phân tích ở trên, đây là các thao tác rất đắt về mặt tính toán, do đó, 10 ảnh hưởng nhiều đến tốc độ của thuật toán. Để khắc phụ nhược điểm này, chúng tôi sẽ đề xuất các phương pháp phân rã kiểu mới cho bài toán cân bằng. Khác với các thuật toán phân rã đã có trong [15, 53], tại mỗi bước lặp, thay vì phải tính giải thức của các song hàm thành phần, chúng tôi chỉ cần giải các bài toán quy hoạch lồi mạnh, có chi phí tính toán rẻ hơn rất nhiều. Hơn nữa, do không sử dụng giải thức của các song hàm thành phần, nên điều kiện đơn điệu đặt lên các song hàm này cũng được loại bỏ. Khi áp dụng bài toán cân bằng vào trong thực tế, ta có thể gặp tình huống tập ràng buộc của bài toán không được cho dưới dạng hiển. Chẳng hạn, trong [38–40], các tác giả nghiên cứu bài toán điều khiển công suất của mạng viễn thông CDMA. Mô hình này được miêu tả bởi bài toán cân bằng với tập ràng buộc cho bởi tập điểm bất động của ánh xạ không giãn T: tìm x ∗ ∈ Fix ( T ) sao cho f ( x ∗ , y) ≥ 0 ∀y ∈ Fix ( T ), (EP( f , Fix ( T ))) trong đó Fix ( T ) := {t ∈ C : T (t) = t}. Bài toán nói trên chính là một trường hợp riêng của bài toán cân bằng hai cấp, tức là bài toán cân bằng với tập ràng buộc là tập nghiệm của một bài toán cân bằng khác tìm x ∗ ∈ Sol ( g, C ) sao cho f ( x ∗ , y) ≥ 0 với Sol ( g, C ) := {t ∈ C : g(t, y) ≥ 0 ∀y ∈ Sol ( g, C ), (BEP( f , g, C )) ∀y ∈ C } , trong đó f , g là các song hàm cân bằng trên C. Mặc dù bài toán cân bằng hai cấp rất thú vị và có nhiều ứng dụng trong thực tế, việc giải nó còn gặp nhiều khó khăn. Một số trường hợp riêng của BEP( f , g, C) khi các bài toán cân bằng có dạng bất đẳng thức biến phân, đã được xét đến trong [4,5,50]. Năm 2014, PGS. Nguyễn Văn Quý [66] nghiên cứu bài toán: Tìm x ∗ ∈ S := Sol ( g, C ) ∩ Fix ( T ) sao cho f ( x∗ , y) ≥ 0 ∀y ∈ S, (BEP( f , g, T, C )) với T : C → C là ánh xạ giả co và đề xuất giải bài toán này bằng phương pháp điểm gần kề kết hợp với phép lặp Halpern:  g  uk = Jrk ( x k );      tính wk ∈ ∂ f ( x k , .)( x k );       ξ k = x k − ρwk ; x k +1 = αk ξk [ + (1 − α k ) (1 − t k )uk + tk T (uk ) ] , trong đó ρ > 0, {αk }, {tk }, {rk } ⊂ (0, ∞) là các dãy tham số. Với giả thiết song hàm f đơn điệu mạnh, song hàm g đơn điệu, vi phân đường chéo theo biến thứ hai của song hàm f liên tục Lipschitz trên C, PGS. Nguyễn Văn Quý đã chứng 11 minh dãy { x k } hội tụ mạnh tới nghiệm duy nhất của bài toán BEP( f , g, T, C). Tuy g nhiên, do phải tính giải thức Jrk tại mỗi bước lặp, phương pháp trên khá phức tạp về mặt tính toán. Dựa trên các ý tưởng từ bài báo [50,70], chúng tôi sẽ đề xuất một thuật toán mới, hiệu quả hơn để giải bài toán cân bằng hai cấp. Thay vì phải tính giải thức của các song hàm f và g, chúng tôi chỉ cần tính các vectơ dưới đạo hàm của chúng và thực hiện các phép chiếu lên tập ràng buộc C. Các thao tác này g có chi phí tính toán thấp hơn nhiều so với việc sử dụng ánh xạ Jλ . f Ánh xạ Uλ được định nghĩa trong (0.2) đóng vai trò là ánh xạ nghiệm của bài toán cân bằng, theo nghĩa, x ∗ là nghiệm của EP( f , C ) khi và chỉ khi nó là điểm bất động của ánh xạ này. Rất nhiều tác giả đã sử dụng nó để đề xuất các thuật toán cho bài toán cân bằng [2, 3, 36, 56, 64, 65]. Tuy nhiên, theo hiểu biết của tác giả, các nghiên cứu về ánh xạ này vẫn còn rất hạn chế. Trong trường hợp f f ( x, y) = ⟨ Fx, y − x ⟩ với F là ánh xạ trên C, Uλ có dạng GλF :C → C x 7→ PC ( x − λFx ) . Năm 2001, Yamada [82] đã chứng minh GλF là ánh xạ co với giả thiết F là đơn điệu mạnh và liên tục Lipschitz. Từ đây, nảy sinh câu hỏi: "Liệu kết quả này có thể mở f rộng cho trường hợp của bài toán cân bằng? Liệu Uλ có là ánh xạ co khi song hàm f thỏa mãn điều kiện đơn điệu mạnh và Lipschitz?" Câu trả lời sẽ được đưa f ra trong luận án. Cụ thể, chúng tôi sẽ chứng minh tính co của ánh xạ Uλ với các giả thiết song hàm f đơn điệu mạnh và thỏa mãn điều kiện Lipschitz kiểu mới và trên cơ sở đó, đề xuất thuật toán ánh xạ co cho bài toán EP( f , Fix ( T )). Ngoài ra, việc kết hợp bài toán cân bằng và bài toán điểm bất động cũng là một đề tài lý thú. Trong khi bài toán cân bằng mới chỉ được nghiên cứu tập trung trong khoảng 20 năm gần đây, bài toán điểm bất động đã có lịch sử phát triển trên 100 năm. Có rất nhiều phương pháp lặp đã được đề xuất để tìm điểm bất động của một hoặc một họ ánh xạ không giãn, ví dụ phương pháp lặp kiểu Halpern, phương pháp lặp kiểu Mann [17]. . . . Bằng việc kết hợp hai bài toán nói trên, ta tận dụng được các kĩ thuật đã có trong lý thuyết điểm bất động để đề xuất và chứng minh tính hội tụ của các thuật toán mới cho bài toán cân bằng. Một trong những chủ đề nhận được sự quan tâm của rất nhiều nhà khoa học là bài toán tìm nghiệm chung của bài toán cân bằng và điểm bất động [2, 3, 36, 69]. Trong luận án, chúng tôi nghiên cứu hai dạng mở rộng của bài toán này, đó là:  )  ( ∗ tìm x ∈ n ∩ Sol ( f i , C ) ∩  m ∩ j =1 i =1 12 Fix ( Tj ) (0.3) ( và tìm x ∗ ∈ n ∩ ) Sol ( f i , C ) i =1 ∩ ( ∩ ) Fix ( Ts ) , (0.4) s ≥0 trong đó, f i , i = 1, . . . , n là các song hàm cân bằng trên C, Tj , j = 1, . . . , m là các ánh xạ không giãn và { Ts }s≥0 là nửa nhóm không giãn trên C. Một số trường hợp riêng của hai bài toán (0.3), (0.4) đã được nhiều tác giả khác nhau nghiên cứu. Chẳng hạn, với m = n = 1, bài toán (0.3) trở thành tìm x ∗ ∈ Sol ( f , C ) ∩ Fix ( T ). Đây là bài toán đã được xét trong [3, 74]. Trong trường hợp các song hàm f i đồng nhất bằng 0, hai bài toán nói trên trở thành bài toán tìm điểm bất động chung của họ ánh xạ không giãn [1, 17, 72, 76]. Khó khăn chính khi đề xuất thuật toán cho hai bài toán (0.3) và (0.4) là tại mỗi bước lặp, ta cần giải nhiều bài toán phụ của các song hàm khác nhau, sau đó cần xử lý kết quả của các bài toán phụ này để xây dựng giá trị xấp xỉ tiếp theo. Để giải quyết vấn đề này, kĩ thuật chiếu song song tỏ ra đặc biệt có hiệu quả. Chúng tôi sẽ thực hiện các phép chiếu tổng quát tương ứng với từng song hàm, trong số các kết quả thu được, ta chọn phần tử cách xa giá trị xấp xỉ hiện tại nhất để làm cơ sở tính xấp xỉ tiếp theo. Kỹ thuật này đã được sử dụng trong các công trình của GS. Phạm Kỳ Anh và cộng sự [1,35,36]. Chúng tôi sẽ tập trung nghiên cứu các nội dung sau: • Xây dựng thuật toán cho bài toán cân bằng với song hàm được phân rã thành tổng hoặc hiệu các song hàm thành phần. • Xây dựng thuật toán cho bài toán cân bằng hai cấp cùng các trường hợp riêng của nó. • Xây dựng thuật toán tìm nghiệm chung của bài toán cân bằng và bài toán điểm bất động của các ánh xạ không giãn. Tất cả các thuật toán đề xuất trong luận án đều được chứng minh là hội tụ. Chúng tôi cũng tiến hành một vài thử nghiệm số để so sánh các thuật toán mới với các thuật toán đã có đồng thời áp dụng chúng vào một số mô hình thực tế. Ngoài phần mở đầu, kết luận, danh mục các công trình đã công bố của tác giả có liên quan đến luận án và danh mục tài liệu tham khảo, luận án gồm 4 chương. Các kết quả chính được tập trung trong các Chương 2, 3 và 4. Chương 1 trình bày một số kiến thức chuẩn bị và kết quả bổ trợ được sử dụng trong luận án. Cụ thể, chương này nhắc lại các khái niệm và kết quả cơ bản của giải tích lồi. Sau đó, các kết quả về sự tồn tại và duy nhất nghiệm cũng như cấu trúc tập nghiệm của bài toán cân bằng được trình bày một cách sơ lược. Để thấy được vai trò của bài toán cân bằng, chúng tôi trình bày mối liên hệ của bài toán này với một số bài toán quan trọng khác trong giải tích phi tuyến như: bài toán 13 bất đẳng thức biến phân, bài toán điểm bất động, bài toán cân bằng Nash, bài toán tối ưu,. . . Chương 2 đề cập tới bài toán cân bằng với song hàm được phân rã thành tổng hoặc hiệu các song hàm thành phần. Trong phần đầu, chúng tôi đề xuất hai thuật toán phân rã tuần tự và phân rã song song cho bài toán cân bằng giả đơn điệu mạnh. Tiếp theo, phương pháp phân rã hiệu được áp dụng để giải một lớp bài toán cân bằng không lồi và không đơn điệu. Trong phần cuối Chương 2, nhằm giảm nhẹ điều kiện đặt lên song hàm của bài toán, chúng tôi sẽ kết hợp phương pháp phân rã với kỹ thuật ergodic để giải một lớp bài toán cân bằng giả đơn điệu và không thỏa mãn điều kiện Lipschitz. Nhìn chung, các phương pháp phân rã tỏ ra đặc biệt hiệu quả khi song hàm gốc có dạng phức tạp, trong khi các song hàm thành phần có dạng đặc biệt hoặc đơn giản hơn. Điều này đã được kiểm chứng bằng một vài thử nghiệm số và so sánh sơ bộ ở cuối chương. Trong phần đầu tiên của Chương 3, chúng tôi sử dụng phương pháp chiếu dưới đạo hàm để giải bài toán cân bằng hai cấp với song hàm cấp trên đơn điệu mạnh và song hàm cấp dưới para-giả đơn điệu. Tại mỗi bước lặp, thay vì phải tính giải thức của các song hàm hoặc giải các bài toán quy hoạch lồi mạnh, thuật toán chỉ đòi hỏi tính các vectơ dưới đạo hàm và thực hiện một phép chiếu lên tập ràng buộc C. Điều này giúp cho phương pháp mới có chi phí tính toán thấp hơn nhiều so với các phương pháp khác. Tiếp theo, thuật toán kể trên được áp dụng cho bài toán cân bằng trên tập điểm bất động. Chúng tôi chỉ ra tập nghiệm của bài toán cân bằng với song hàm para-đơn điệu trùng với tập điểm bất động của ánh xạ không giãn. Bài toán này được nghiên cứu trong phần tiếp theo của chương ở một hướng tiếp cận khác. Chúng tôi chứng minh một điều kiện đủ cho tính co của ánh xạ nghiệm Uλ , trên cơ sở đó, đề xuất thuật toán ánh xạ co cho bài toán cân bằng trên tập điểm bất động của ánh xạ không giãn. Phần cuối chương trình bày một vài thử nghiệm số và so sánh với các thuật toán của các tác giả khác. Đặc biệt, chúng tôi sẽ áp dụng thuật toán của mình để giải bài toán cân bằng Nash cho thị trường sản xuất điện bán độc quyền. Khác với mô hình đã được xét trong các bài báo [64, 65], mô hình mới có thêm yếu tố bảo hộ doanh nghiệp. Điều này dẫn đến bài toán cân bằng với tập ràng buộc được cho dưới dạng tập điểm bất động của ánh xạ không giãn. Trong Chương 4, chúng tôi xét bài toán  )  ( m n ∩ ∩ ∩  Fix ( Tj ) , Sol ( f i , C ) tìm x ∗ ∈ j =1 i =1 ( và tìm x ∗ ∈ n ∩ ) Sol ( f i , C ) i =1 14 ∩ ( ∩ s ≥0 ) Fix ( Ts ) , trong đó, f i : C × C → R, i = 1, . . . , n là các song hàm cân bằng, Tj : C → C, j = 1, . . . , m là ánh xạ không giãn và { Ts }s>0 là nửa nhóm không giãn trên C. Để giải quyết bài các toán này, chúng tôi kết hợp phương pháp đạo hàm tăng cường và kỹ thuật tìm kiếm theo tia kiểu Armijo [65, 73] với các phương pháp lặp kiểu Mann và Halpern. Đây đều là các kỹ thuật quen thuộc của bài toán cân bằng và lý thuyết điểm bất động, nhưng đã được chúng tôi phát triển cho lớp bài toán tổng quát hơn. Ngoài ra, thuật toán dựa trên các kỹ thuật này chỉ sinh ra các dãy lặp hội tụ yếu tới nghiệm của bài toán. Trong các phương pháp được đề xuất, sử dụng thêm các phép chiếu lên nửa không gian chứa tập nghiệm, chúng tôi thu được các dãy lặp hội tụ mạnh tới hình chiếu của xuất phát điểm lên tập nghiệm. Các kết quả chính của luận án được công bố trong 7 bài báo trên các tạp chí thuộc danh mục ISI: Revista de la Real Academia de Ciencias Exactas, Físicas y Naturales. Serie A. Matemáticas, Numerical Algorithms, Optimization, Numerical Functional Analysis and Optimization, Journal of Optimization Theory and Applications, Journal of Fixed Point Theory and Applications, Miskolc Mathematical Notes và được báo cáo tại: • 7th International Conference on High Performance Scientific Computing, Hà Nội, 19-23/3/2018; • Hội thảo Tối ưu và tính toán khoa học lần thứ 13, Ba Vì, Hà Nội, 23-25/4/2015; • Hội thảo Tối ưu và tính toán khoa học lần thứ 16, Ba Vì, Hà Nội, 19-21/4/2018; • Hội nghị Toán ứng dụng và Tin học, Đại học Bách Khoa Hà Nội, 12-13/11/2016; • Hội nghị khoa học khoa Toán - Cơ - Tin học tại Đại học Khoa học Tự nhiên, Đại học Quốc Gia Hà Nội, 01/10/2016; • Xêmina "Bài toán cân bằng và các vấn đề liên quan", Viện Nghiên cứu Cao cấp về Toán, 27/09/2016; • Xêmina "Lý thuyết tối ưu và ứng dụng", Bộ môn Toán ứng dụng, Viện Toán ứng dụng và Tin học, Đại học Bách Khoa Hà Nội, 22/10/2015; • Xêmina "Bài toán cân bằng, bài toán điểm bất động và các vấn đề liên quan", Viện Toán ứng dụng và Tin học, Đại học Bách Khoa Hà Nội, 09/01/2018. 15 Chương 1 Một số kiến thức chuẩn bị Trong chương này, chúng tôi trình bày một số kiến thức cơ sở cần thiết cho các chương tiếp theo. Chương gồm ba phần. Phần đầu tiên trình bày một số khái niệm và kết quả cơ bản của giải tích lồi. Hai phần tiếp theo dành để giới thiệu bài toán cân bằng và các trường hợp riêng của nó cùng các điều kiện về sự tồn tại và duy nhất nghiệm của bài toán này. Nội dung của chương chủ yếu được tham khảo từ các tài liệu [8, 67, 78]. 1.1 Các khái niệm và kết quả cơ bản Một không gian vectơ thực H được trang bị tích vô hướng ⟨., .⟩ và đầy đủ đối với chuẩn √ ∥ x ∥ := ⟨ x, x ⟩ được gọi là không gian Hilbert thực. Từ đây đến hết luận án, ta luôn kí hiệu H là không gian Hilbert thực. Không gian Rn là một không gian Hilbert (hữu hạn chiều) với tích vô hướng n ∑ xi yi ⟨ x, y⟩ := i =1 và chuẩn ( ∥ x ∥ := )1/2 n ∑ xi2 i =1 với mọi x = ( x1 , . . . , xn ), y = (y1 , . . . , yn ) ∈ Rn . Không gian l 2 các dãy khả tổng bậc hai là một không gian Hilbert (vô hạn chiều) với tích vô hướng ⟨ x, y⟩ := ∞ ∑ xi yi i =1 16 và chuẩn ( ∞ )1/2 ∑ xi2 ∥ x ∥ := i =1 với mọi x = ( xi ), y = (yi ) ∈ Tập l2. Cho C ⊂ H là tập lồi, đóng, khác rỗng, x0 ∈ C. ⟨ NC ( x ) := {w ∈ H : w, y − x 0 0 ⟩ ≤ 0 ∀y ∈ C } được gọi là nón pháp tuyến (ngoài) của C tại x0 . Hiển nhiên NC ( x0 ) là một nón lồi, đóng khác rỗng. Giả sử x ∈ H. Khi đó dC ( x ) := inf ∥y − x ∥ y∈C được gọi là khoảng cách từ x đến tập C. Nếu tồn tại điểm x0 ∈ C thỏa mãn dC ( x ) = 0 x − x , ta gọi x0 là hình chiếu của x lên C, kí hiệu x0 = PC ( x ). Ánh xạ PC : H → C được gọi là phép chiếu (vuông góc) lên C. Ánh xạ này là công cụ sắc bén, đóng vai trò quan trọng trong việc xây dựng các thuật toán giải bài toán cân bằng và bất đẳng thức biến phân. Mệnh đề 1.1. Cho C ⊂ H là tập lồi, đóng, khác rỗng. Khi đó, (a) Với mọi x ∈ H, PC ( x ) luôn tồn tại duy nhất, đồng thời x0 = PC ( x ) khi và chỉ khi ⟨ ⟩ 0 0 y − x , x − x ≤ 0 ∀y ∈ C. (b) Ánh xạ PC có tính chất không giãn vững (hoặc 1-đơn điệu mạnh ngược), tức là, ∥ PC ( x ) − PC (y)∥2 ≤ ⟨ PC ( x ) − PC (y), x − y⟩ ∀ x, y ∈ H. (c) Với mọi x ∈ H, x0 = PC ( x ) khi và chỉ khi x − x0 ∈ NC ( x0 ). Định nghĩa 1.1. Cho f : H → R, x0 ∈ H. Khi đó, • Hàm f được gọi là hê-mi liên tục tại x0 nếu lim f (tz + (1 − t) x0 ) = f ( x0 ) t →0+ ∀z ∈ H. • Hàm f được gọi là nửa liên tục dưới tại x0 nếu ∀{ x k } ⊂ H, x k → x0 ⇒ lim inf f ( x k ) ≥ f ( x0 ). k→∞ • Hàm f được gọi là nửa liên tục dưới yếu tại x0 nếu ∀{ x k } ⊂ H, x k ⇀ x0 ⇒ lim inf f ( x k ) ≥ f ( x0 ). k→∞ • Hàm f được gọi là nửa liên tục dưới (tương ứng1 yếu) trên C nếu nó nửa liên tục dưới (t.ư. yếu) tại mọi điểm thuộc C. 1 Từ sau đây đến hết luận án, cụm từ "tương ứng" sẽ được viết tắt là "t.ư.". 17 • Hàm f được gọi là nửa liên tục trên (t.ư. yếu) nếu − f nửa liên tục dưới (t.ư. yếu). Hàm f được gọi là liên tục nếu nó vừa liên tục trên vừa liên tục dưới. Định nghĩa 1.2. Cho f : H → R ∪ {∞}, x0 ∈ H. Nếu tập { ⟨ ⟩ 0 0 ∂ f ( x ) := w ∈ H : w, y − x ≤ f (y) − f ( x0 ) ∀y ∈ H } khác rỗng thì f được gọi là khả dưới vi phân tại x0 , ∂ f ( x0 ) được gọi là dưới vi phân, mỗi vectơ w thuộc ∂ f ( x0 ) được gọi là dưới đạo hàm của f tại x0 . Hàm f được gọi là khả dưới vi phân trên một tập nếu nó khả dưới vi phân tại mọi điểm thuộc tập đó. Chú ý 1.1. Trong trường hợp f : C ⊂ H → R, bằng việc mở rộng hàm số này ra toàn bộ không gian   f ( x ) nếu x ∈ C, f¯( x ) :=  ∞ nếu x ∈ / C, ta có thể định nghĩa hàm f khả dưới vi phân trên C tương tự như trong Định nghĩa 1.2. Định nghĩa 1.3. Cho f : C → R ∪ {∞}, x0 ∈ C. Ta nói • f ( x ) đạt cực tiểu (t.ư. cực đại) địa phương tại x0 trên C nếu tồn tại lân cận U của x0 sao cho f ( x ) ≥ f ( x0 ) ∀ x ∈ U ∩ C (t.. f ( x ) ≤ f ( x0 ) ∀ x ∈ U ∩ C ) • f ( x ) đạt cực tiểu (t.ư. cực đại) toàn cục tại x0 trên C nếu f ( x ) ≥ f ( x0 ) ∀x ∈ C (t.. f ( x ) ≤ f ( x0 ) ∀ x ∈ C ) Định lý 1.1. [8, Mệnh đề 26.5] Cho C ⊂ H là tập lồi, đóng, có miền trong khác rỗng, f : C → R là hàm lồi, chính thường, nửa liên tục dưới và khả dưới vi phân trên C. Khi đó, x ∗ là điểm cực tiểu của f trên C khi và chỉ khi 0 ∈ ∂ f ( x ∗ ) + NC ( x ∗ ). Tiếp theo, chúng tôi trình bày một số bổ đề về dãy số, cần thiết cho việc chứng minh kết quả ở các chương tiếp theo. Bổ đề 1.1. [81, Bổ đề 2.5] Cho {αk }, { β k }, {λk } là các dãy số dương thỏa mãn αk+1 ≤ (1 − λk )αk + λk γk + β k ∀k ≥ 1. ∞ Giả sử λk ∈ (0, 1) với mọi k ≥ 1, ∑∞ k =1 λk = ∞, lim supk→∞ γk ≤ 0 và ∑k =1 β k < ∞. Khi đó limk→∞ αk = 0. 18 Bổ đề 1.2. [76] Giả sử { an } và {bn } là hai dãy số dương thỏa mãn điều kiện an+1 ≤ an + bn ∀n ∈ N, ∞ ∑ bn < ∞. n =1 Khi đó limn→∞ an tồn tại và hữu hạn. Bổ đề 1.3. [16] Cho { an } và {λn } là các dãy số dương thỏa mãn lim an = a ∈ R và n→∞ Khi đó, ta có ∞ ∑ λn = ∞. n =1 ∑nk=1 λk ak = a. lim n→∞ ∑n k =1 λ k Bổ đề 1.4. [49, Bổ đề 3.1] Cho {ζ k } ⊂ R là một dãy số thỏa mãn: tồn tại dãy con {ζ ki } ⊂ {ζ k } sao cho ζ ki < ζ ki +1 ∀i ≥ 0. Xét dãy chỉ số {τ (k )} cho bởi τ (k ) := max{i ≤ k : ζ i < ζ i+1 }. Khi đó {τ (k )} là một dãy không giảm, thỏa mãn limk→∞ τ (k ) = ∞, ζ τ (k) < ζ τ (k)+1 và ζ k ≤ ζ τ (k)+1 với mọi k ≥ 0. Bổ đề 1.5. [49, Bổ đề 2.1] Cho {λk }, {γk } ⊂ (0, ∞) là hai dãy số thỏa mãn ∞ ∑ k =0 λk = ∞, ∞ ∑ λ2k < ∞ và k =0 ∞ ∑ λk γk < ∞. k =0 Khi đó, • Tồn tại một dãy con {γki } ⊂ {γk } sao cho limi→∞ γki = 0. • Nếu tồn tại hằng số M > 0 sao cho γk+1 − γk ≤ Mλk với mọi k ≥ 0, thì limk→∞ γk = 0. Bổ đề 1.6. [80] Giả sử Br (0) ⊂ H là hình cầu đóng, tâm tại gốc tọa độ, bán kính r. Khi đó, với mọi hệ vectơ { x1 , x2 , . . . , x N } ⊂ Br (0) và các số thực dương λ1 , λ2 , . . . , λ N thỏa mãn ∑iN=1 λi = 1, tồn tại hàm lồi, tăng ngặt, liên tục g : [0, 2r ) → [0, ∞) thỏa mãn g(0) = 0, đồng thời với mọi i, j ∈ {1, 2, . . . , N }, i < j, ta có 2 N N 2 ∑ λk xk ≤ ∑ λk ∥ xk ∥ − λi λ j g(∥ xi − x j ∥). k =1 k =1 19