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

MỞ ĐẦU 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. Bài toán cân bằng của song hàm f trên C được phát biểu như sau: tìm x ∗ ∈ C sao cho f ( x ∗ , y) ≥ 0 ∀y ∈ C. (EP( f , C )) Đ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 . . . 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 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 , áp dụng bài toán cân bằng vào thực tế . 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. Các phương pháp chính để giải bài toán cân bằng có thể kể đến như: phương pháp chiếu, phương pháp phân rã, phương pháp hiệu chỉnh Tikhonov, phương pháp điểm gần kề, phương pháp hàm đánh giá. Đặ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 và thu được các kết quả rất đáng khích lệ. Chúng tôi cho rằng việc mở rộng phương pháp này sang bài toán cân bằng là cần thiết. Đây là một trong những vấn đề sẽ được giải quyết trong luận án. 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, mô hình điều 1 khiển công suất của mạng viễn thông CDMA có thể dẫn đến 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. Theo hiểu biết của người viết, cho đến nay có rất ít phương pháp giải cho bài toán BEP( f , g, C ). Việc đề xuất các phương pháp mới, hiệu quả để giải bài toán câng bằng hai cấp cùng các trường hợp riêng của nó là rất cần thiết. Các vấn đề này sẽ được giải quyết trong luận án. 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 . . . . Bằng việc kết hợp hai bài toán nói trên, ta có thể 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. Trong chương cuối của luận án, chúng tôi sẽ xét bài 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 ánh xạ không giãn EP( f , C ) ∩ Fix ( T ). Trong luận án, chúng tôi sẽ tập trung nghiên cứu các nội dung sau: • Xây dựng phương pháp giải 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. • Xây dựng phương pháp giải 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 phương pháp 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. 2 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: • Chương 1. Một số kiến thức chuẩn bị. • 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. • Chương 3. Bài toán cân bằng hai cấp. • Chương 4. 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á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 tại Ba Vì, Hà Nội từ 2325/4/2015 • Hội thảo Tối ưu và tính toán khoa học lần thứ 16 tại Ba Vì, Hà Nội từ 1921/4/2018 • Hội nghị Toán ứng dụng và Tin học tại Đại học Bách Khoa Hà Nội từ 1213/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 vào ngày 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, ngày 27/09/2016 3 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 Cho H là không gian Hilbert thực được trang bị tích vô hướng ⟨., .⟩ và chuẩn tương ứng ∥.∥. Giả sử C ⊂ H là tập lồi, khác rỗng, x0 ∈ C. Tập { ⟨ ⟩ } 0 0 NC ( x ) := w ∈ H : w, y − x ≤ 0 ∀y ∈ C được gọi là nón pháp tuyến (ngoài) của C tại x0 . Dễ thấy NC ( x0 ) là một nón lồi, đóng, khác rỗng. Cho x ∈ H là điểm bất kì. Khi đó dC ( x ) := inf ∥y − x ∥ y∈C được gọi là khoảng cách từ x đến tập C. Giả sử tồn tại điểm x0 ∈ C thỏa mãn dC ( x ) = x − x0 , 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 các thuật 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 đó, • 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 y − x0 , x − x0 ≤ 0 ∀y ∈ C. • Á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. • Với mọi x ∈ H, x0 = PC ( x ) khi và chỉ khi x − x0 ∈ NC ( x0 ). Định nghĩa 1.2. Cho g : H → R ∪ {+∞}, x0 ∈ H. Nếu tập { ⟨ ⟩ 0 0 ∂g( x ) := w ∈ H : w, y − x ≤ g(y) − g( x0 ) ∀y ∈ H } khác rỗng thì g được gọi là khả dưới vi phân tại x0 , ∂g( x0 ) được gọi là dưới vi phân, mỗi vectơ w thuộc ∂g( x0 ) được gọi là dưới đạo hàm của g tại x0 . Hàm g được gọi là khả dưới vi phân trên tập C nếu nó khả dưới vi phân tại mọi điểm thuộc tập đó. 4 Định nghĩa 1.4. Song hàm f : C × C → R được gọi là 1. γ-đơn điệu mạnh trên C nếu tồn tại hằng số γ > 0 sao cho với mọi x, y ∈ C, f ( x, y) + f (y, x ) ≤ −γ∥ x − y∥2 ; 2. đơn điệu chặt trên C nếu với mọi x ̸= y ∈ C, ta có f ( x, y) + f (y, x ) < 0; 3. đơn điệu trên C nếu với mọi x, y ∈ C, ta có f ( x, y) + f (y, x ) ≤ 0; 4. γ-giả đơn điệu mạnh trên C nếu tồn tại hằng số γ > 0 sao cho với mọi x, y ∈ C, f ( x, y) ≥ 0 ⇒ f (y, x ) ≤ −γ∥ x − y∥2 ; 5. giả đơn điệu trên C nếu với mọi x, y ∈ C, ta có f ( x, y) ≥ 0 ⇒ f (y, x ) ≤ 0. 6. thỏa mãn điều kiện Lipschitz nếu tồn tại hai hằng số c1 , c2 > 0 sao cho f ( x, y) + f (y, z) ≥ f ( x, z) − c1 ∥ x − y∥2 − c1 ∥y − z∥2 . 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 Cho F : C → C là một ánh xạ, bài toán bất đẳng thức biến phân của ánh xạ F trên tập C được phát biểu dưới dạng tìm x ∗ ∈ C sao cho ⟨ Fx ∗ , y − x ∗ ⟩ ≥ 0 ∀y ∈ C. (VI( F, C )) Dễ thấy bài toán VI( F, C ) chính là trường hợp đặc biệt của EP( f , C ) bằng cách đặt f ( x, y) := ⟨ Fx, y − x ⟩. Có thể nói bài toán bất đẳng thức biến phân chính là trường hợp riêng quan trọng nhất của bài toán cân bằng. Bản thân bài toán VI( F, C ) cũng là một đề tài lý thú, thu hút được sự quan tâm nghiên cứu của đông đảo các nhà khoa học trong và ngoài nước. Rất nhiều phương pháp giải bài toán cân bằng được mở rộng trực tiếp từ các phương pháp tương ứng dành cho bài toán bất đẳng thức biến phân. Cần lưu ý rằng bản thân bài toán bất đẳng thức biến phân cũng bao hàm một loạt các bài toán khác như: bài toán bù phi tuyến, bài toán điểm bất động. 5 1.2.2 Bài toán cân bằng Nash trong trò chơi không hợp tác Lý thuyết trò chơi hiện đại được cho là “con đẻ” của nhà toán học John von Neumann và nhà kinh tế học Oskar Morgenstern. Đây là hai đồng tác giả của cuốn sách có tựa đề "Theory of Games and Economic Behaviour" được xuất bản năm 1944. Đến đầu những năm 1950, Nash đưa ra khái niệm “điểm cân bằng Nash” trong trò chơi không hợp tác. Cân bằng Nash đạt được khi không một người chơi nào có thể tăng được lợi ích bằng cách thay đổi chiến lược của mình trong khi các đối thủ khác vẫn giữ nguyên chiến lược của họ. Một cách tổng quát, giả sử có n người tham gia một trò chơi không hợp tác. Người chơi thứ i có tập chiến lược là Ci và có hàm lợi ích là f i : C → R với C = C1 × . . . Cn . Mục tiêu của mỗi người chơi là tìm kiếm một chiến lược cho riêng mình để tối đa hóa lợi ích f i . Điểm x ∗ ∈ C được gọi là điểm cân bằng Nash nếu với mọi y = (y1 , . . . , yn ) ∈ C, f i ( x1∗ , . . . , xn∗ ) ≥ f i ( x1∗ , . . . , xi∗−1 , yi , xi∗+1 , . . . , xn∗ ) ∀i = 1, . . . , n. Bằng cách đặt n f ( x, y) := ∑ [ fi (x1, . . . , xi , . . . , xn ) − fi (x1, . . . , yi , . . . , xn )] ∀ x, y ∈ C, (1.2) i =1 bài toán tìm điểm cân bằng Nash có thể đưa về bài toán cân bằng EP( f , C ). Song hàm f được định nghĩa ở trên gọi là song hàm Nikaido-Isoda. 1.2.3 Bài toán điểm yên ngựa Xét hai không gian Hilbert thực H1 , H2 . Giả sử C ⊂ H1 , D ⊂ H2 là hai tập lồi, đóng, khác rỗng, L : C × D → R là song hàm. Bài toán điểm yên ngựa (Saddle point problem) được phát biểu như sau tìm ( x ∗ , y∗ ) ∈ C × D sao cho L( x ∗ , y) ≤ L( x ∗ , y∗ ) ≤ L( x, y∗ ) (SP( L, C, D )) Bài toán trên có thể được đưa về bài toán EP( f , K ) với K = C × D, f (u, v) := L( x, y′ ) − L( x ′ , y) với mọi u = ( x ′ , y′ ), v = ( x, y) ∈ K. 1.3 Sự tồn tại và duy nhất nghiệm của bài toán cân bằng Trong mục này, chúng ta sẽ xét một số điều kiện đủ cho sự tồn tại và duy nhất nghiệm của bài toán cân bằng. Một số tính chất miêu tả cấu trúc của tập nghiệm 6 của EP( f , C ) cũng được trình bày. Định lý 1.8.1 Cho C ⊂ H là tập lồi, đóng, khác rỗng, f : C × C → R là song hàm cân bằng, giả đơn điệu, thỏa mãn điều kiện: với mọi x ∈ C, hàm số f (., x ) hê-mi liên tục và hàm số f ( x, .) lồi, nửa liên tục dưới trên C. Giả sử điều kiện bức sau được thỏa mãn: tồn tại một tập compắc B sao cho: ∀ x ∈ C \ B, ∃y ∈ C : f ( x, y) < 0. Khi đó, bài toán cân bằng EP( f , C ) có ít nhất một nghiệm. Mệnh đề 1.2.1 Giả sử song hàm f giả đơn điệu mạnh (hoặc đơn điệu chặt) trên C. Khi đó, bài toán EP( f , C ) có tối đa một nghiệm. Định lý 1.9.1 Cho C ⊂ H là tập lồi, đóng, khác rỗng, f : C × C → R là song hàm cân bằng, giả đơn điệu mạnh và thỏa mãn điều kiện: với mọi x ∈ C, hàm số f (., x ) hê-mi liên tục và hàm số f ( x, .) lồi, nửa liên tục dưới trên C và khả dưới vi phân tại một điểm nào đó thuộc H. Khi đó, bài toán cân bằng EP( f , C ) có đúng một nghiệm. Định lý 1.10.1 Cho C ⊂ H là tập lồi, đóng, khác rỗng, f : C × C → R là song hàm cân bằng, giả đơn điệu và thỏa mãn: với mọi x ∈ C, các hàm số f (., x ) nửa liên tục trên, f ( x, .) lồi trên C. Khi đó, (a) Sd = S, (b) S là tập lồi, đóng. 1 L.D. Muu, N.V. Quy (2015) On existence and solution methods for strongly pseudomonotone equilibrium problems. Vietnam J. Math. 43, 229 - 238. 7 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 Trong chương này, chúng tôi sẽ trình bày một số phương phân rã cho bài toán cân bằng. Đây được biết đến như là một phương pháp hiệu quả trong tối ưu để giải quyết các bài toán với hàm mục tiêu có dạng phức tạp, nhiều thành phần. Ý tưởng chính của phương pháp là tách hàm mục tiêu thành tổng hoặc hiệu của các hàm có dạng đơn giản hơn. Khi đó, thay vì phải xử lí trực tiếp hàm mục tiêu ban đầu, ta chỉ cần làm việc với các hàm thành phần, nhờ đó, ta có thể tận dụng được các tính chất và dạng đặc biệt của chúng. 2.1 Phân rã song hàm thành tổng của hai song hàm thành phần Cho C ⊂ H là tập lồi, đóng, có miền trong khác rỗng. Ta xét bài toán EP( f , C) với f := f 1 + f 2 , trong đó f i : C × C → R, i = 1, 2, là các song hàm thành phần. Ký hiệu lớp bài toán này là EPS ( f , C ). Định nghĩa 2.2. Song hàm f : C × C → R được gọi là thỏa mãn điều kiện Lipschitz kiểu mới nếu tồn tại hằng số Q > 0 sao cho với mọi x, y, z ∈ C, | f ( x, y) + f (y, z) − f ( x, z)| ≤ Q∥ x − y∥∥y − z∥. Định nghĩa 2.3. Song hàm f : C × C → R được gọi là liên tục τ-Hölder từng phần trên C nếu tồn tại các hằng số L > 0 và τ ∈ (0, 1] sao cho với mọi x, y, z ∈ C, ít nhất một trong hai điều kiện sau được thỏa mãn (a) | f ( x, y) − f (z, y)| ≤ L∥ x − z∥τ ; (b) | f ( x, y) − f ( x, z)| ≤ L∥y − z∥τ . 8 Giả thiết 2.1. Ta xét bài toán EPS ( f , C ) với các giả thiết sau: (A1) Với mọi x, hàm f (., x ) nửa liên tục trên trên C. (A2) Song hàm f là γ-giả đơn điệu mạnh trên C. (A3) Với mỗi x ∈ C, các hàm số f i ( x, .) nửa liên tục dưới, lồi, khả dưới vi phân trên C và f i ( x, x ) = 0, i = 1, 2. 2.1.1 Thuật toán phân rã tuần tự Thuật toán 2.1. Bước 0. Chọn x0 ∈ C và dãy số {λk } ⊂ (0, ∞). Đặt k = 0. Bước 1. Giả sử đã biết x k , tính: { } 1 k k k 2 y = argmin λk f 1 ( x , t) + ∥t − x ∥ : t ∈ C , 2 } { 1 k 2 k +1 k x = argmin λk f 2 (y , t) + ∥t − y ∥ : t ∈ C . 2 Nếu x k = yk = x k+1 , dừng thuật toán. Ngược lại, đi đến Bước 2. Bước 2. Cập nhật k := k + 1 quay trở lại Bước 1. Định lý 2.1. Cho f : C × C → R là song hàm được phân rã thành f := f 1 + f 2 . Giả sử các điều kiện của Giả thiết 2.1 được thỏa mãn, f 1 thỏa mãn điều kiện Lipschitz kiểu mới với hằng số Q, f 2 liên tục τ-Hölder từng phần trên C. Khi đó, với mọi x0 ∈ C, với mọi dãy {λk } thỏa mãn điều kiện ∞ (A4) ∑ ∞ λk = ∞, (A5) k =1 2 ∑ (λk ) 2−τ < ∞, k =1 dãy { x k } sinh ra bởi Thuật toán 2.1 hội tụ mạnh tới nghiệm duy nhất x ∗ của bài toán EPS ( f , C ). 2.1.2 Thuật toán phân rã song song Thuật toán 2.3. Bước 0. Chọn x0 ∈ C và dãy {λk } ⊂ (0, ∞). Đặt k = 0. Bước 1. Giả sử đã biết x k , tính } 1 k 2 y = argmin λk f 1 ( x , t) + ∥t − x ∥ : t ∈ C , 2 { k k 9 { } 1 zk = argmin λk f 2 ( x k , t) + ∥t − x k ∥2 : t ∈ C , 2 k k y +z x k +1 = . 2 Nếu x k = yk = zk , thì dừng thuật toán. Ngược lại, đi đến Bước 2. Bước 2. Cập nhật k := k + 1 và quay trở lại Bước 1. Định lý 2.2. Cho f : C × C → H, f = f 1 + f 2 . Giả sử các điều kiện trong Giả thiết 2.1 được thỏa mãn, f i liên tục τi -Hölder từng phần, i = 1, 2. Khi đó, với mọi x0 ∈ C và dãy 2 ∞ 2−τ < ∞, trong đó, τ = min{ τ , τ }, {λk } thỏa mãn điều kiện ∑∞ 1 2 k =1 λk = ∞, ∑k =1 ( λk ) dãy { x k } sinh ra bởi Thuật toán 2.3 hội tụ mạnh tới nghiệm duy nhất x ∗ của bài toán EP( f , C ). p Nhận xét 2.3. Thuật toán 2.3 có thể được mở rộng cho trường hợp f = ∑i=1 f i , p ≥ 2 như sau    x0 ∈ C,   (2.19) yik = argmin{λk f i ( x k , t) + 21 ∥t − x k ∥2 : t ∈ C }, i = 1, . . . , p,     x k +1 = 1 p y k . p ∑ i =1 i Với giả thiết tương tự như trong Định lý 2.2, ta có thể chứng minh { x k } sinh bởi (2.19) hội tụ mạnh tới nghiệm của EP( f , C ). 2.1.3 Trường hợp song hàm chứa nhiễu Giả sử f = f 1 + f 2 , trong đó song hàm f 1 được cho chính xác còn f 2 là song hàm chứa nhiễu, tức là, thay vì biết được f 2 , ta chỉ biết được phiên bản nhiễu gδ ( x, y) của nó, gδ ( x, y) thỏa mãn điều kiện | f 2 ( x, y) − gδ ( x, y)| ≤ δ∥ x − y∥α , ∀ x, y ∈ C với α ∈ (0, 2], δ > 0. Giả sử với mọi x ∈ C và δ > 0, hàm gδ ( x, .) lồi, nửa liên tục dưới. Cho {δk } là dãy số dương, giảm. Ký hiệu gk ( x, y) := gδk ( x, y). Định lý 2.3. Giả sử tất cả các điều kiện của Định lý 2.1 được thỏa mãn, limk→∞ δk = 0 và 2 2− µ ∑∞ k =1 λ k < ∞, với µ = min{τ, α}. Khi đó, dãy { x k } sinh bởi    x0 ∈ C,    { } 1 k k k 2 y = argmin λk f 1 ( x , t) + 2 ∥t − x ∥ : t ∈ C ,  { }     x k+1 = argmin λ g (yk , t) + 1 ∥t − yk ∥2 : t ∈ C , k k 2 hội tụ mạnh tới nghiệm x ∗ của bài toán EPS ( f , C ). 10 2.2 Phân rã song hàm thành hiệu của hai song hàm thành phần Trong mục này, ta xét bài toán EP( f , C ) với song hàm f được phân rã thành hiệu của hai song hàm thành phần: f := f 1 − f 2 với f i : H × H → R là các song hàm thỏa mãn điều kiện f i ( x, x ) = 0 với mọi x ∈ C, i = 1, 2. Ký hiệu lớp bài toán này là EPD ( f , C ). Giả thiết 2.2. Ta xét bài toán EPD ( f , C ) với các giả thiết sau. (B1) Tập nghiệm của bài toán EPD ( f , C ) khác rỗng. (B2) f 1 đơn điệu mạnh trên C. (B3) f 1 thỏa mãn điều kiện Lipschitz kiểu mới trên C. (B4) f 2 liên tục τ-Hölder từng phần trên C. (B5) Với mỗi x ∈ C, các hàm số f 1 ( x, .) và f 2 (., x ) nửa liên tục dưới, lồi và khả dưới vi phân trên C. Lưu ý rằng, với Giả thiết 2.2, song hàm f không nhất thiết phải lồi theo biến thứ nhất hoặc thứ hai. Ngoài ra, nó cũng không nhất thiết phải thỏa mãn bất cứ điều kiện nào về tính liên tục và đơn điệu trên C. Để giải bài toán EP( f , C ), chúng tôi đề xuất thuật toán phân rã sau. Thuật toán 2.4. Bước 0. Chọn x0 ∈ C và dãy {λk } ⊂ (0, ∞). Đặt k = 0. Bước 1. Giả sử đã biết x k , tính { } 1 k 2 y = argmin λk f 1 ( x , t) + ∥t − x ∥ : t ∈ C , 2 { } 1 k +1 k k 2 x = argmin λk f 2 (t, y ) + ∥t − y ∥ : t ∈ C . 2 k k Bước 2. Cập nhật k := k + 1 và quay lại Bước 1. Định lý 2.4. Cho f : C × C → R, f = f 1 − f 2 . Giả sử các điều kiện trong Giả thiết 2.2 được thỏa mãn. Khi đó, với mọi x0 ∈ C và với mọi dãy {λk } thỏa mãn hai điều kiện (A4), (A5), dãy { x k } sinh ra bởi Thuật toán 2.4 hội tụ mạnh tới nghiệm duy nhất của bài toán EPD ( f , C ). 11 Hệ quả 2.2. Giả sử các điều kiện (B1), (B2), (A4) và (A5) thỏa mãn. Ngoài ra, giả sử rằng (C1) Với mọi x ∈ H, f 1 ( x, .) nửa liên tục dưới, lồi và khả dưới vi phân trên C, (C2) Với mọi x ∈ C, f 2 (., x ) nửa liên tục dưới, lồi và khả dưới vi phân trên H, (C3) f 1 thỏa mãn điều kiện Lipschitz trên H, (C4) f 2 liên tục τ-Hölder từng phần trên H. Khi đó, dãy { x k } sinh ra bởi    x0 ∈ H,    { } 1 k k k 2 y = argmin λk f 1 ( x , t) + 2 ∥t − x ∥ : t ∈ C ,  } {     x k+1 = argmin λk f 2 (t, yk ) + 21 ∥t − yk ∥2 : t ∈ H . hội tụ mạnh tới nghiệm duy nhất của bài toán EPD ( f , C ). Giả sử tập dưới vi phân ∂ f 2 (., x )( x ) có thể tính được dễ dàng với mọi x ∈ C, đồng thời điều kiện sau được thỏa mãn (C4’) Tồn tại hằng số M > 0 sao cho với mọi x ∈ C và với mọi ξ ∈ ∂ f 2 (., x )( x ), ta có ∥ξ ∥ ≤ M. Khi đó, Thuật toán 2.4 có thể được cải tiến như sau:    x0 ∈ H,   yk = argmin{λk f 1 ( x k , t) + 12 ∥t − x k ∥2 : t ∈ C },     x k+1 ∈ yk − λ ∂ f (., yk )(yk ). k (2.40) 2 Hệ quả 2.3. Giả sử các điều kiện (B1), (B2), (C1)-(C3) và (C4’) được thỏa mãn, dãy {λk } thỏa mãn hai điều kiện ∞ ∞ k =1 k =1 ∑ λk = ∞, ∑ λ2k < ∞. Khi đó, dãy { x k } sinh ra bởi (2.40) hội tụ mạnh tới nghiệm duy nhất của bài toán EPD ( f , C ). 2.3 Phương pháp phân rã kết hợp ergodic Ta xét bài toán EP( f , C ) với song hàm f được phân rã thành tổng của hai song hàm thành phần f := f 1 + f 2 . Để giảm nhẹ điều kiện đặt lên song hàm f cũng như các song hàm thành phần, chúng tôi sẽ kết hợp thuật toán phân rã với phương pháp ergodic. 12 Giả thiết 2.3. Các thuật toán sẽ được đề xuất với các giả thiết sau: (D1) f giả đơn điệu trên C. Với mỗi y ∈ C, f (·, y) nửa liên tục trên yếu, lõm trên C. (D2) Với mỗi x ∈ C, f i ( x, x ) = 0, f i ( x, ·) nửa liên tục dưới, lồi và khả dưới vi phân trên C (i = 1, 2). (D3) Tập nghiệm của bài toán cân bằng EPS ( f , C ) khác rỗng. Điều kiện f giả đơn điệu và lõm theo biến thứ nhất trong (D1) có thể được thay thế bằng tính đơn điệu của f . 2.3.1 Phương pháp ergodic-phân rã tuần tự Thuật toán 2.5. Bước 0. Chọn x0 ∈ C, {λk } ⊂ (0, 1). Đặt k = 0, z0 = x0 , s0 = λ0 . Bước 1. Giả sử đã biết x k , tính: { } 1 yk = argmin λk f 1 ( x k , t) + ∥t − x k ∥2 : t ∈ C , 2 { } 1 k +1 k k 2 x = argmin λk f 2 (y , t) + ∥t − y ∥ : t ∈ C 2 ) ( λ λ k + 1 z k + k +1 x k +1 . s k +1 = s k + λ k +1 ; z k +1 = 1 − s k +1 s k +1 Bước 2. Cập nhật k := k + 1 và đi đến Bước 1. Định lý 2.5. Giả sử tất cả các điều kiện trong Giả thiết 2.5 thỏa mãn, f 1 , f 2 liên tục Hölder từng phần với các hằng số lần lượt là τ1 , τ2 . Đặt τ := min{τ1 , τ2 }. Khi đó, với mọi dãy {λk } thỏa mãn (A4), (A5), dãy {zk } sinh ra bởi Thuật toán 2.5 hội tụ yếu tới một nghiệm của bài toán EPS ( f , C ). 2.3.2 Phương pháp ergodic-phân rã song song Thuật toán 2.6. Bước 0. Chọn x0 ∈ C và dãy {λk } ⊂ (0, ∞). Đặt t0 = x0 , k = 0, s0 = λ0 . Bước 1. Giả sử đã biết x k , tính: { } 1 yk = argmin λk f 1 ( x k , t) + ∥t − x k ∥2 : t ∈ C , 2 { } 1 k k k 2 z = argmin λk f 2 ( x , t) + ∥t − x ∥ : t ∈ C , 2 13 x k +1 yk + zk = , 2 s k +1 = s k + λ k +1 ; t k +1 = ( λ 1 − k +1 s k +1 ) tk + λ k +1 k +1 x . s k +1 Bước 2. Cập nhật k := k + 1 và đi đến Bước 1. Định lý 2.6. Giả sử các điều kiện trong Giả thiết 2.3 được thỏa mãn, các song hàm f i liên tục τi -Hölder từng phần (i = 1, 2), đặt τ = min{τ1 , τ2 }. Khi đó, với mọi dãy {λk } thỏa mãn (A4), (A5), dãy {tk } sinh ra bởi Thuật toán 2.6 hội tụ yếu tới một nghiệm của bài toán EPS ( f , C ). Thử nghiệm số và ứng dụng Trong phần này, chúng tôi đã áp dụng các thuật toán phân rã vào mô hình cân bằng Nash của thị trường sản xuất điện. Các thuật toán được thử nghiệm trong cả hai trường hợp: song hàm được cho chính xác và song hàm chứa nhiễu. Phương pháp phân rã hiệu đã được thử nghiệm cho bài toán cân bằng không lồi. Ngoài ra, chúng tôi cũng tiến hành một vài so sánh sơ bộ các thuật toán mới với các thuật toán được đề xuất trước đó, bao gồm: Thuật toán Đạo hàm tăng cường, Thuật toán Đạo hàm tăng cường đối ngẫu và Thuật toán tìm kiếm theo tia kiểu Armijo. Kết quả cho thấy các thuật toán mới tỏ ra ưu thế hơn, đặc biệt trong các trường hợp song hàm f của bài toán cân bằng có dạng phức tạp, chứa nhiều thành phần. 14 Chương 3 Bài toán cân bằng hai cấp Cho C là tập lồi, đóng, khác rỗng trong không gian Hilbert thực H, f , g : C × C → R là các song hàm cân bằng trên C. Bài toán cân bằng hai cấp được phát biểu như sau: Tìm x ∗ ∈ Sol ( g, C ) : sao cho f ( x ∗ , y) ≥ 0 với mọi y ∈ Sol ( g, C ), trong đó Sol ( g, C ) := { x ∈ C : g( x, y) ≥ 0 ∀y ∈ C }. 3.1 (BEP( f , g, C )) Phương pháp chiếu dưới đạo hàm cho bài toán cân bằng hai cấp 3.1.1 Thuật toán và sự hội tụ Định nghĩa 3.1. • Ánh xạ A : C → C được gọi là para-đơn điệu nếu nó đơn điệu trên C và với mọi x, y ∈ C, ta có ⟨ A( x ) − A(y), x − y⟩ = 0 ⇔ A( x ) = A(y). • Song hàm g : C × C → R được gọi là para-(giả) đơn điệu nếu nó (giả) đơn điệu trên C và với mọi x ∗ ∈ Sol ( g, C ), y ∈ C, ta có g(y, x ∗ ) = 0 ⇒ y ∈ Sol ( g, C ). Mệnh đề 3.1. Cho A : C → C là ánh xạ para-đơn điệu. Với mọi x ∗ ∈ Sol ( A, C ), y ∈ C, ta có ⟨ A(y), y − x ∗ ⟩ = 0 ⇒ y ∈ Sol ( A, C ). Giả thiết 3.1. Ta xét bài toán BEP( f , g, C ) với các giả thiết sau. (E1) Song hàm f ρ-đơn điệu mạnh và g para-giả đơn điệu trên C. (E2) Với mỗi x ∈ C, các hàm số f ( x, .), g( x, .) lồi, khả dưới vi phân, hàm số f (., x ) hê-mi liên tục, hàm số g(., x ) nửa liên tục trên yếu và hàm số f ( x, .) nửa liên tục dưới yếu trên C. (E3) Sol ( g, C ) ̸= ∅. 15 (E4) Với mỗi x ∈ C, tồn tại hằng số L > 0 sao cho, với mỗi dãy bị chặn {tk } ⊂ C, ta có | g(tk+1 , x ) − g(tk , x )| ≤ L∥tk+1 − tk ∥ với mọi k ≥ 0. (E5) Các ánh xạ x 7→ ∂2 f ( x, x ) và x 7→ ∂2 g( x, x ) bị chặn trên mỗi tập bị chặn của C. Thuật toán 3.1. Bước 0. Chọn x0 ∈ C, µ ∈ (0, ∞) và các dãy {αk }, {λk } ⊂ (0, ∞). Đặt k = 0. Bước 1. Giả sử đã biết x k , tính: v k ∈ ∂2 g ( x k , x k ); w k ∈ ∂2 f ( x k , x k ); { } k k k k d = v + αk w ; ηk = max µ; ∥d ∥ ; ( ) λk k k +1 k x = PC x − d . ηk Bước 2. Cập nhật k := k + 1 và quay trở lại bước Bước 1. Định lý 3.1. Giả sử các điều kiện trong Giả thiết 3.1 thỏa mãn, ∑i∞=1 λi = ∞, ∑i∞=1 λ2i < ∞, ∑i∞=1 αi = ∞, ∑i∞=1 λi αi = ∞ và limi→∞ αi = 0. Khi đó, dãy { x k } sinh ra bởi Thuật toán 3.1 hội tụ mạnh tới nghiệm duy nhất x ∗ của bài toán BEP( f , g, C). 3.1.2 Áp dụng cho bài toán EP( f , Fix ( T )) Cho song hàm f : H × H → R và ánh xạ T : H → H với tập điểm bất động Fix ( T ) khác rỗng. Ta sẽ áp dụng Thuật toán 3.1 để giải bài toán Tìm x ∗ ∈ Fix ( T ) sao cho f ( x ∗ , y) ≥ 0 với mọi y ∈ Fix ( T ). (3.12) g( x, y) := ⟨ x − T ( x ), y − x ⟩ ∀ x, y ∈ H. (3.13) Đặt Mệnh đề 3.3. Giả sử T là ánh xạ không giãn và g là song hàm được cho bởi (3.13). Khi đó, (a) Fix ( T ) = Sol ( g, H ). (b) Song hàm g para-đơn điệu. Thuật toán 3.2. Bước 0. Chọn x0 ∈ H, µ ∈ (0, ∞) và các dãy {αk }, {λk } ⊂ (0, ∞). Đặt k = 0. Bước 1. Giả sử x k đã biết, tính: w k ∈ ∂2 f ( x k , x k ); d k = x k − T ( x k ) + α k w k ; { } λ k ηk = max µ; ∥d ∥ ; x k+1 = x k − k dk . ηk Bước 2. Cập nhật k := k + 1 và quay lại Bước 1. 16 Định lý 3.2. Giả sử song hàm f thỏa mãn tất cả các điều kiện trong Giả thiết 3.1, T là ánh xạ không giãn với tập điểm bất động Fix ( T ) ̸= ∅, ∑i∞=1 λi = ∞, ∑i∞=1 λ2i < ∞, ∑i∞=1 αi = ∞, ∑i∞=1 λi αi = ∞ và limi→∞ αi = 0. Khi đó, dãy { x k } sinh ra bởi Thuật toán 3.2 hội tụ mạnh tới nghiệm duy nhất x ∗ của bài toán (3.12). 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λ Ta nhắc lại khái niệm ánh xạ nghiệm. Cho song hàm cân bằng f : C × C → R, λ > 0, ánh xạ Uλ cho bởi } 1 Uλ : C → C, x 7→ argmin λ f ( x, y) + ∥ x − y∥2 : y ∈ C . 2 { được gọi là ánh xạ nghiệm của f trên C. Định nghĩa 3.3. Song hàm f : C × C → C được gọi là thỏa mãn điều kiện Lipschitz tăng cường nếu tồn tại các ánh xạ αi : C × C → C và β i : C → C, i = 1, . . . , p thỏa mãn, với mọi x, y, z ∈ C ta có p f ( x, y) + f (y, z) ≥ f ( x, z) + ∑ ⟨αi ( x, y), β i (y − z)⟩ , i =1 trong đó β i : C → C là các ánh xạ liên tục Ki -Lipschitz, αi : C × C → C, i = 1, . . . , p là các song hàm thỏa mãn tính chất αi ( x, y) + αi (y, x ) = 0, tồn tại Li > 0 sao cho ∥αi ( x, y)∥ ≤ Li ∥ x − y∥ với mọi x, y ∈ C, i = 1, . . . , p. Định lý 3.3. Cho f : C × C → R là song hàm thỏa mãn f ( x, .) nửa liên tục dưới, lồi, khả dưới vi phân với mọi x ∈ C, λ > 0. Giả sử f là γ-đơn điệu mạnh và thỏa mãn điều 2γ kiện Lipschitz tăng cường trên C. Khi đó, Uλ là ánh xạ co với mọi λ ∈ (0, M 2 ), trong đó p M = ∑ Ki Li , Ki , Li là các hệ số trong Định nghĩa 3.3. i =1 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 Cho T : C → C là ánh xạ không giãn với tập điểm bất động Fix ( T ) ̸= ∅, f : C × C → R là song hàm cân bằng. Xét bài toán cân bằng của song hàm f trên tập điểm bất động Fix ( T ) Tìm x ∗ ∈ Fix ( T ) sao cho f ( x ∗ , y) ≥ 0 ∀y ∈ Fix ( T ). 17 EP( f , Fix ( T )) Kí hiệu tập nghiệm của EP( f , Fix ( T )) bởi Sol ( f , Fix ( T )). Giả thiết 3.2. Ta xét bài toán với các điều kiện sau. (F1) Với mọi x ∈ C, hàm số f (., x ) nửa liên tục trên yếu, hàm số f ( x, .) nửa liên tục dưới, lồi, khả dưới vi phân trên C. (F2) Song hàm f là γ-đơn điệu mạnh và thỏa mãn điều kiện Lipschitz tăng cường trên C. (F3) Với mọi dãy bị chặn { x k }, {yk } ⊂ C, tồn tại hằng số Λ > 0 sao cho | f ( x k , yk )| ≤ Λ∥ x k − yk ∥. p Giả sử M = ∑ Ki Li , với Ki , Li và p là các hệ số trong Định nghĩa 3.3. Với các điều i =1 kiện trong Giả thiết 3.2, bài toán EP( f , Fix ( T )) có duy nhất một nghiệm x ∗ . Ta đề xuất thuật toán sau để tìm nghiệm này. Thuật toán 3.3. Bước 0. Chọn x0 ∈ C và dãy số {λk } ⊂ (0, ∞). Đặt k = 0. Bước 1. Giả sử đã biết x k , tính: x k+1 = Uλk+1 Tx k Bước 2. Cập nhật k := k + 1 quay trở lại Bước 1. Định lý 3.4. Cho T : C → C là ánh xạ không giãn với tập điểm bất động Fix ( T ) ̸= ∅ và f : C × C → R là song hàm thỏa mãn Giả thiết 3.2, {λk } ⊂ (0, ∞) là dãy số giảm thỏa mãn lim λk = 0, n→∞ ∞ ∑ λk = ∞ và k =1 | λ k − λ k +1 | = 0. k→∞ λ2k+1 lim { } Khi đó, dãy x k sinh ra bởi Thuật toán 3.3 hội tụ yếu tới nghiệm duy nhất của bài toán EP( f , Fix ( T )). Thử nghiệm số và ứng dụng Trong phần này, chúng tôi đã áp dụng bài toán cân bằng hai cấp vào mô hình Nash cho thị trường sản xuất điện có yếu tố bảo hộ doanh nghiệp. Mô hình 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 ẩn, và do đó, các phương 18 pháp truyền thống cho bài toán cân bằng không thể áp dụng. Bằng việc xây dựng một ánh xạ không giãn có tập điểm bất động trùng với tập ràng buộc, chúng tôi đã áp dụng thành công thuật toán chiếu dưới đạo hàm để giải bài toán nói trên. Ngoài ra, chúng tôi cũng tiến hành một vài so sánh sơ bộ thuật toán mới với Thuật toán kiểu dưới đạo được tác giả Iiduka đề xuất trước đó. Kết quả so sánh cho thấy, thuật toán mới tỏ ra ưu thế hơn, đặc biệt trong các bài toán có số chiều lớn. 19 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 Cho C ⊂ H là tập lồi, đóng, có miền trong khác rỗng, f i : C × C → R, i = 1, . . . , N, là các song hàm cân bằng trên C, S j , j = 1, . . . , M là các ánh xạ không giãn. Ta xét bài toán ∗ tìm x ∈ ( ) N ∩ Sol (C, f i ) ∩ ( M ) ∩ Fix (S j ) , j =1 i =1 (4.3) trong đó Sol ( f i , C ) là nghiệm của bài toán cân bằng cho song hàm f i trên C, Fix (S j ) là tập điểm bất động của ánh xạ S j . Giả thiết 4.1. Ta giả thiết với mọi i = 1, . . . , N, (G1) Song hàm f i giả đơn điệu trên C. (G2) Song hàm f i nửa liên tục trên yếu theo biến thứ nhất, f i ( xn , yn ) → 0 với mọi dãy { xn }, {yn } bị chặn thỏa mãn ∥ xn − yn ∥ → 0; (G3) Hàm số f i ( x, .) nửa liên tục dưới, lồi, khả dưới vi phân trên C với mọi x ∈ C. 4.1.1 Thuật toán Armijo lai ghép Để giải bài toán (4.3), ta đề xuất thuật toán sau. Thuật toán 4.1. β Bước 0. Chọn các số thực dương β > 0, σ ∈ (0, 2 ), γ ∈ (0, 1) và dãy {αn } ⊂ (0, 1) 20