Báo cáo Một lớp các phương pháp đạo hàm tăng cường giải bài toán cân bằng không đơn điệu (Phần 1)

Nội dung text: Báo cáo Một lớp các phương pháp đạo hàm tăng cường giải bài toán cân bằng không đơn điệu (Phần 1)

1. BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM KỸ THUẬT THÀNH PHỐ HỒ CHÍ MINH CÔNG TRÌNH NGHIÊN CỨU KHOA HỌC CẤP TRƯỜNG MỘT LỚP CÁC PHƯƠNG PHÁP ĐẠO HÀM TĂNG CƯỜNG GIẢI BÀI TOÁN CÂN BẰNG KHÔNG ĐƠN ĐIỆU MÃ SỐ: T2015-42TÐ S K C0 0 5 2 8 6 Tp. Hồ Chí Minh, 2015
2. Đề tài cấp trường trọng điểm-T2015-42TĐ 2015 DANH SÁCH THÀNH VIÊN THAM GIA NGHIÊN CỨU THÀNH VIÊN: 1) Phan Tự Vượng-ĐH SPKT Tp HCM 1
3. Đề tài cấp trường trọng điểm-T2015-42TĐ 2015 Mục lục Danh mục bảng biểu Trang 3 Danh mục các chữ viết tắt Trang 4 Thông tin kết quả nghiên cứu bằng tiếng Việt và tiếng Anh Trang 5 Mở đầu Trang 9 Chương 1 Trang 11 Chương 2 Trang 14 Kết luận và kiến nghị Trang 20 Tài liệu tham khảo Trang 21 Phụ lục Trang 22 Bản sao thuyết minh đề tài đã được phê duyệt 2
4. Đề tài cấp trường trọng điểm-T2015-42TĐ 2015 Danh mục bảng biểu 3
5. Đề tài cấp trường trọng điểm-T2015-42TĐ 2015 Danh mục các chữ viết tắt 1) EP f, C : Bài toán cân bằng cho hàm số f trên tập lồi đóng và bị chặn C . 2) SE : Tập nghiệm của bài toán EP f, C . 3) DEP f, C : Bài toán cân bằng đối ngẫu của EP f, C . 4) SD : Tập nghiệm của bài toán DEP f, C . 5) VI C, F : Bài toán bất đẳng thức biến phân đối với ánh xạ F trên tập C. 4
6. Đề tài cấp trường trọng điểm-T2015-42TĐ 2015 TRƯỜNG ĐẠI HỌC SƯ PHẠM KỸ THUẬT CỘNG HOÀ XÃ HỘI CHỦ NGHĨA THÀNH PHỐ HỒ CHÍ MINH VIỆT NAM KHOA KHCB Độc lập - Tự do - Hạnh phúc Tp. HCM, Ngày 15 tháng 12 năm 2015 THÔNG TIN KẾT QUẢ NGHIÊN CỨU 1. Thông tin chung: - Tên đề tài: Một lớp các Phương pháp đạo hàm tăng cường giải bài toán cân bằng không đơn điệu - Mã số: T2015-42TĐ - Chủ nhiệm: Phan Tự Vượng - Cơ quan chủ trì: Đại học Sư phạm Kỹ thuật Tp Hồ Chí Minh - Thời gian thực hiện: Từ 1/2015 đến 12/2015 2. Mục tiêu: Nghiên cứu phương pháp đạo hàm tăng cường cho bài toán cân bằng không đơn điệu. Đề xuất và chứng minh sự hội tụ của các thuật toán, viết chương trình Matlab. 3. Tính mới và sáng tạo: Các kết quả thu được trong đề tài là hoàn toàn mới và đã được chấp nhận đăng ở tạp chí Quốc tế ISI (SCI) rất uy tín trong chuyên ngành Lý thuyết tối ưu. 5
7. Đề tài cấp trường trọng điểm-T2015-42TĐ 2015 4. Kết quả nghiên cứu: Đề xuất một lớp các phương pháp đạo hàm tăng cường cho bài toán cân bằng không đơn điệu trong không gian Hilbert thực. 5. Sản phẩm: Bài báo quốc tế đăng trên tạp chí ISI (SCI): Jean Jacques Strodiot, Phan Tu Vuong, Thi Thu Van Nguyen: A class of shrinking projection extragradient methods for solving non-monotone equilibrium problems in Hilbert spaces, Journal of Global Optimization, 2015, DOI 10.1007/s10898-015-0365-5 6. Hiệu quả, phương thức chuyển giao kết quả nghiên cứu và khả năng áp dụng: Các kết quả trình bày trong đề tài có thể sử dụng làm tài liệu tham khảo trong nghiên cứu cơ bản cho nghiên cứu sinh và học viên cao học. Trưởng Đơn vị Chủ nhiệm đề tài (ký, họ và tên) (ký, họ và tên) PGS. TS. Đỗ Quang Bình T.S. Phan Tự Vượng 6
8. Đề tài cấp trường trọng điểm-T2015-42TĐ 2015 INFORMATION ON RESEARCH RESULTS 1. General information: Project title: A class of Extragradient methods for solving nonmonotone equilibrium problems Code number: T2015-42TĐ Coordinator: Phan Tu Vuong Implementing institution: University of Technical Education HCMC Duration: from January 2015 to December 2015. 2. Objective(s): Extragradient-type methods for solving non-monotone equilibrium problem in a real Hilbert space. 3. Creativeness and innovativeness: The results obtained in this project are new and have been published in a very good International Optimization journal. 4. Research results: A new class of extragradient-type methods is introduced for solving an equilibrium problem in a real Hilbert space without any monotonicity assumption on the equilibrium function. The strategy is to replace the second projection step in the classical extragradient method by a projection onto shrinking convex subsets of the feasible set. Furthermore, to ensure a sufficient decrease on the equilibrium function, a general Armijo-type condition is imposed. This condition is shown to be satisfied for four different linesearches used in the literature. Then, the weak and strong convergence of the resulting algorithms is obtained under non-monotonicity assumptions. Finally, some numerical experiments are reported. 7
9. Đề tài cấp trường trọng điểm-T2015-42TĐ 2015 5. Products: ISI (SCI) paper: Jean Jacques Strodiot, Phan Tu Vuong, Thi Thu Van Nguyen: A class of shrinking projection extragradient methods for solving non-monotone equilibrium problems in Hilbert spaces, Journal of Global Optimization, 2015, DOI 10.1007/s10898-015-0365-5 6. Effects, transfer alternatives of reserach results and applicability: The results established in this project are references for PhD and Master students in the field of mathematics. 8
10. Đề tài cấp trường trọng điểm-T2015-42TĐ 2015 MỞ ĐẦU 1. TỔNG QUAN TÌNH HÌNH NGHIÊN CỨU THUỘC LĨNH VỰC CỦA ĐỀ TÀI Ở TRONG VÀ NGOÀI NƯỚC Bài toán cân bằng là mô hình toán học hữu ích giúp thống nhất một số khái niệm quan trọng trong toán học ứng dụng [1,2,3]. Tuy được phát biểu rất đơn giản nhưng bài toán cần bằng có thể bao trùm các bài toán sau dưới dạng đặc biệt: Bài toán tối ưu, bài toán bất đẳng thức biến phân, bài toán điểm bất động, bài toán bù tuyến tính, bài toán cân bằng Nash, xem [1,2,3]. Mô hình này có nhiều ứng dụng trong thực tiễn, đặc biệt là trong các bài toán kinh tế, ví dụ: bài toán mua bán điện cạnh tranh, bài toán ô nhiễm nguồn nước [1,6,7,8]. Sự tồn tại nghiệm, tính ổn định và các phương pháp giải bài toán cân bằng thu hút được sự quan tâm nghiên cứu của nhiều nhà toán học trên thế giới [1-11]. Cho đến nay, các phương pháp giải bài toán cân bằng đều cần dùng đến tính đơn điệu của hàm cân bằng (xem định nghĩa ở chương 1 và [1,4-11]). Thuật toán giải bài toán cân bằng không đơn điệu chưa được nghiên cứu nhiều. Hiện tại ở trong nước có một số nhóm nghiên cứu rất mạnh về các thuật toán giải bài toán cân bằng các kết quả của họ đã được đăng trên các tạp chí ISI có uy tín [4-11]. 2. TÍNH CẤP THIẾT CỦA ĐỀ TÀI Trong những năm gần đây, các phương pháp giải bài toán cân bằng là một chủ đề rất nóng, thu hút được sự quan tâm của nhiều nhà nghiên cứu trong nước và quốc tế. Tuy nhiên, cho tới nay các phương pháp giải bài toán cân bằng đều đòi hỏi tính đơn điệu của hàm cân bằng. Trong thực tế có những mô hình toán học mà hàm cân bằng không đơn điệu [1,11]. Vì vậy việc nghiên cứu phương pháp giải bài toán cân bằng không đơn điệu là rất quan trọng và cấp thiết. 9
11. Đề tài cấp trường trọng điểm-T2015-42TĐ 2015 3. MỤC TIÊU ĐỀ TÀI Nghiên cứu phương pháp đạo hàm tăng cường giải rất hiệu quả bài toán cân bằng đơn điệu và giả đơn điệu. Mục tiêu của đề tài là mở rộng và cải tiến phương pháp này để giải bài toán cân bằng không đơn điệu. 4. CÁCH TIẾP CẬN, PHƯƠNG PHÁP NGHIÊN CỨU 4.1. Cách tiếp cận Nghiên cứu lý thuyết thông qua các tài liệu chuyên ngành (sách, bài báo khoa học), các seminar học thuật. 4.2. Phương pháp nghiên cứu Các công cụ đã có trong lý thuyết tối ưu, cân bằng và thuật toán sẽ được sử dụng trong các nghiên cứu của đề tài. 5. ĐỐI TƯỢNG, PHẠM VI NGHIÊN CỨU 5.1. Đối tượng nghiên cứu Bài toán cân bằng không đơn điệu trong trong không gian Hilbert. 5.2. Phạm vi nghiên cứu Nghiên cứu các phương pháp đạo hàm tăng cường giải bài toán cân bằng không đơn điệu. Áp dụng các phương pháp này vào một số mô hình cụ thể, viết chương trình Matlab và trình bày kết quả số. 6. NỘI DUNG NGHIÊN CỨU Nội dung nghiên cứu được trình bày trong các chương tiếp theo và phụ lục đính kèm. 10
12. Đề tài cấp trường trọng điểm-T2015-42TĐ 2015 Chương 1: GIỚI THIỆU BÀI TOÁN CÂN BẰNG 1.1. Bài toán cân bằng: Cho C là tập lồi đóng trong không gian Hibert H , cho f: C C là hàm số hai biến thỏa f( x , x ) 0  x C và f(,) x là hàm lồi x C . Bài toán cân bằng đối với hàm f và tập C, ký hiệu là EP(f,C), là bài toán tìm x* C sao cho f( x *, y ) 0  y C . Tập nghiệm của bài toán này được ký hiệu là SE . Định nghĩa: Hàm f gọi là: a) Đơn điệu mạnh trên nếu tồn tại  0 sao cho fxy(,)(,),; fyx  xy 2  xyC b) Đơn điệu trên C nếu f( x , y ) f ( y , x ) 0  x , y C ; c) Giả đơn điệu trên C nếu f( x , y ) 0 f ( y , x ) 0  x , y C . Dễ thấy a))) b c , chiều ngược lại không đúng trong trường hợp tổng quát. Cho đến nay, tất cả các phương pháp giải bài toán cân bằng đều giả sử hàm cân bằng thỏa một trong các tính chất đơn điệu nêu trên. Trong nghiên cứu này chúng tôi sẽ đề xuất một lớp các thuật toán để giải bài toán cân bằng mà không dùng tính đơn điệu của hàm f. Chúng tôi chỉ dùng đến tính giải được của bài toán cân bằng đối ngẫu: Tương ứng với bài toán EP(f,C) ta xét bài toán đối ngẫu như sau: Tìm x* C sao cho f( y , x *) 0  y C . 11
13. Đề tài cấp trường trọng điểm-T2015-42TĐ 2015 Bài toán này và tập nghiệm của nó được ký hiệu lần lượt là DEP(f,C) và SD . Nếu f là hàm liên tục thì SSDE và nếu hàm f giả đơn điệu trên C thì SSED . Như vậy rõ ràng điều kiện SD  nhẹ hơn rất nhiều so với điều kiện hàm f giả đơn điệu trên C. Ta có thể dễ dàng xây dựng các hàm f có SD  nhưng không đơn điệu cũng như giả đơn điệu trên C [xem 10]. Trong thực tế, có những bài toán mà hàm cân bằng không đơn điệu như bài toán mua bán điện cạnh tranh và bài toán ô nhiễm môi trường sông [6,7,8]. Vì vậy, nghiên cứu này có thể áp dụng vào các mô hình thực tế nêu trên. 1.2. Phép chiếu mêtric: Cho C là tập lồi đóng khác rỗng trong không gian Hilbert thực H . Khi đó với mỗi vectơ x H , tồn tại duy nhất một vecto thuộc C , ký hiệu là PC () x sao cho x PC () x x y  y C . Ánh xạ PC (.) gọi là phép chiếu mêtric lên tập C . 1.3. Các trường hợp đặc biệt của bài toán cân bằng: Bài toán cân bằng tổng quát hóa rất nhiều bài toán quan trọng trong giải tích biến phân. Sau đây chúng ta chỉ trình bày một số trường hợp rất quan trọng. Người đọc có thể tham khảo thêm trong [1,2,3]. 1.3.1 Bài toán tối ưu: Xét bài toán min (x ), x C Xét hàm số f: C C xác định bởi f(,)()() x y y x . Hiển nhiên (x ) ( y )  y C f ( x , y ) 0  y C . Vậy bài toán tối ưu trên là một trường hợp riêng của bài toán EP(f,C). 12
14. Đề tài cấp trường trọng điểm-T2015-42TĐ 2015 1.3.2 Bài toán bất đẳng thức biến phân: Cho H là một không gian Hilbert và CH là một tập lồi đóng. Cho ánh xạ FCH: . Bài toán tìm x* C sao cho F( x ), y x 0  y C gọi là bất đẳng thức biến phân đối với F và C , ký hiệu VI(CF , ). Xét hàm số f: C C xác định bởi f( x , y ) F ( x ), y x Dễ thấy bài toán VI(CF , ) tương đương với bài toán EP(,) f C . 1.3.3 Bài toán điểm bất động Kakutani: C Cho FC: 2 , x được gọi là điểm bất động của F nếu x F() x . Giả sử với mọi x C , F() x lồi, compact, khác rỗng. Khi đó bài toán tìm một điểm bất động của F có thể mô tả dưới dạng bài toán cân bằng EP. Thật vậy, với mỗi x , y C ta đặt (x , y ) max x v , y x v F() x Hiển nhiên là nếu x F() x thì theo định nghĩa của ta có (x , y ) 0  y C . Ngược lại, giả sử x là nghiệm của bài toán (EP), tức là x C và (x , y ) 0  y C . Khi đó gọi y là hình chiếu của x lên tập lồi đóng F() x , ta có: x y, y x max x v , v x v F() x Do x là nghiệm của bài toán EP nên 2 0 (xy , ) max xvvx , xyyx , xy . v F() x Suy ra x y F() x . Vậy x là điểm bất động của F . 13
15. Đề tài cấp trường trọng điểm-T2015-42TĐ 2015 Chương 2 CÁC PHƯƠNG PHÁP ĐẠO HÀM TĂNG CƯỜNG GIẢI BÀI TOÁN CÂN BẰNG KHÔNG ĐƠN ĐIỆU 2.1 Thuật toán tổng quát: Trong phần này, chúng tôi trình bày một thuật toán rất tổng quát để xây dựng x dãy lặp k  hội tụ về nghiệm của bài toán cân bằng đang xét. Sau đó, chúng ta xét đến trường hợp cụ thể. Sự hội tụ của dãy lặp không phụ thuộc vào tính đơn điệu của hàm cân bằng. Chúng ta chỉ sử dụng giả thiết hàm cân bằng liên S tục và tập nghiệm của bài toán cân bằng đối ngẫu E khác rỗng. Thuật toán 1: x C c 0 Bước 0: Chọn 0 , . Đặt k=0. Bước 1: Giải bài toán lồi mạnh 1 2 min f ( x , y ) y x  y C k 2 k   y y x x thu được nghiệm k . Nếu k k thì dừng thuật toán, k là nghiệm. y x Nếu k k thì chuyển sang bước 2. (0,1) z(1 ) x y Bước 2: Tìm k và tính k k k k k sao cho c x y2 g, x z k k k k k k k 0 gk f z, z H trong đó  k và k 2 k k . Xét nửa không gian k xác định bởi H x H,, g x z k k k  k. x P x C Bước 3: Tính k1 C k , trong đó k là tập lồi đóng xác định bởi k CCHk k  i0  i . 14
16. Đề tài cấp trường trọng điểm-T2015-42TĐ 2015 Bước 4: Đặt k : k 1 và quay lại Bước 1. Định lý 2.1: x * x x x Giả sử là một điểm tụ yếu của dãy k và k là dãy con của k hội  j   x * x y x * tụ yếu về . Khi đó, nếu dãy k k hội tụ về 0 thì là nghiệm của bài j j toán cân bằng EP(f,C). Chứng minh: Xem phụ lục, Định lý 4.1 2.2 Một lớp các thuật toán tìm kiếm trên tia: Trong phần này, chúng ta trình bày các phương pháp khác nhau để tính điểm z k ở Bước 2 của thuật toán tổng quát 1. Sau đó, với mỗi phương pháp, ta chứng minh được các điều kiện ở Định lý 2.1 thỏa mãn. Phương pháp 1: Cho 0,1 và 0,1 , tìm số nguyên dương m nhỏ nhất sao cho g, x y x y 2 k, m k k k k , z: (1m ) x m y g f z, z trong đó k, m k k và k, m  2 k , m k , m . m ,z z g g Đặt k k, m và k k, m . Nhận xét 2.1: Phương pháp 1 được định nghĩa tốt và được sử dụng trong [4] để giải bài toán cân bằng giả đơn điệu. Mệnh đề 2.1: z, g Các điểm k k được tính trong phương pháp 1 thỏa mãn c x y2 g, x z k k k k k k k 15
17. Đề tài cấp trường trọng điểm-T2015-42TĐ 2015 với  0,c . Chứng minh: Xem phụ lục, Mệnh đề 5.1 Phương pháp 2: 0,1 , 0, 0,1 Cho  và , tìm số nguyên dương m nhỏ nhất sao cho 2m f ( z , y ) x y 2  k, m k k k , z: (1m ) x m y m ,z z g g trong đó k, m k k . Đặt k k, m và k k, m . Nhận xét 2.2: Phương pháp 2 được định nghĩa tốt và khi  0 phương pháp này được sử dụng trong [11] để giải bài toán cân bằng giả đơn điệu. Mệnh đề 2.2: z 2 Giả sử k được tính trong phương pháp 2. Khi đó với mọi k  k và gk f z, z k 2 k k ta có c x y2 g, x z k k k k k k k với c . Chứng minh: Xem phụ lục, Mệnh đề 5.2 Phương pháp 3: Cho 0,1 và 0,1 , tìm số nguyên dương m nhỏ nhất sao cho f z,, x f z y x y 2 k,, m k k m k k k , z: (1m ) x m y trong đó k, m k k . 16
18. Đề tài cấp trường trọng điểm-T2015-42TĐ 2015 m ,z z Đặt k k, m . Nhận xét 2.3: Phương pháp 3 được định nghĩa tốt và được sử dụng trong [9,11] để giải bài toán cân bằng và tựa cân bằng giả đơn điệu. Mệnh đề 2.3: z g f z, x Giả sử k được tính trong phương pháp 3 và k 2 k k . Khi đó gk f z, z g, x z f z , x 0 k 2 k k với  k k k k k k , hơn nữa ta có c x y2 g, x z k k k k k k k với c . Chứng minh: Xem phụ lục, Mệnh đề 5.3 Phương pháp 4: Cho 0,1 và 0,1 , tìm số nguyên dương m nhỏ nhất sao cho fzx,,, fzy fxy xy 2 k,, m k k m k k k k k , z: (1m ) x m y trong đó k, m k k . m ,z z Đặt k k, m . Nhận xét 2.4: Phương pháp 4 được định nghĩa tốt và được sử dụng trong [10] để giải bài toán tựa cân bằng giả đơn điệu. Mệnh đề 2.4: z g f z, x Giả sử k được tính trong phương pháp 3 và k 2 k k . Khi đó gk f z, z g, x z f z , x 0 k 2 k k với  k k k k k k , hơn nữa ta có c x y2 g, x z k k k k k k k 17
19. Đề tài cấp trường trọng điểm-T2015-42TĐ 2015 với c 1 . Chứng minh: Xem phụ lục, Mệnh đề 5.4 Mệnh đề 2.5: x * x x x Giả sử là một điểm tụ yếu của dãy k và k là dãy con của k hội  j   x * z, g tụ về với k k được tính như trong các phương pháp 1-4. Khi đó, x y 0 k k . j j Kết hợp Định lý 2.1 với Mệnh đề 2.5 ta có định lý hội tụ sau: Định lý 2.6: x x * Dãy k  tính bởi thuật toán 1 hội tụ yếu về là nghiệm của bài toán cân bằng EP(f,C). Chứng minh: Xem phụ lục, Định lý 5.1 x Để xây dựng dãy lặp k  hội tụ mạnh về nghiệm của bài toán cân bằng EP(f,C) chúng ta cần cải tiến thuật toán 1 như sau: Thuật toán 2: x C c 0 Bước 0: Chọn 0 , . Đặt k=0. Bước 1: Giải bài toán lồi mạnh 1 2 min f ( x , y ) y x  y C k 2 k   18
20. Đề tài cấp trường trọng điểm-T2015-42TĐ 2015 y y x x thu được nghiệm k . Nếu k k thì dừng thuật toán, k là nghiệm. y x Nếu k k thì chuyển sang bước 2. (0,1) z(1 ) x y Bước 2: Tìm k và tính k k k k k sao cho c x y2 g, x z k k k k k k k 0 gk f z, z H trong đó  k và k 2 k k . Xét nửa không gian k xác định bởi H x H,, g x z k k k  k. u P x C Bước 3: Tính k C k , trong đó k là tập lồi đóng xác định bởi k CCHk k  i0  i . x P x Bước 4: Tính k1 B D C 0 , với k  k  B x H, u x x x k k k  D x H, x x , x x 0 k k0 k  Bước 5: Đặt k : k 1 và quay lại Bước 1. Ta có định lý hội tụ sau cho Thuật toán 2. Định lý 2.7: x x * Dãy k  tính bởi thuật toán 2 hội tụ mạnh về là nghiệm của bài toán cân bằng EP(f,C). Chứng minh: Xem phụ lục, Định lý 5.2 2.3 Kết quả số cho các thuật toán: Chúng tôi áp dụng các thuật toán trên vào một số mô hình bài toán cân bằng trong thực tế, khi hàm cân bằng không đơn điệu. Các kết quả này được trình bày trong chương 6 của phụ lục đính kèm. 19
21. Đề tài cấp trường trọng điểm-T2015-42TĐ 2015 KẾT LUẬN VÀ KIẾN NGHỊ Trong đề tài này chúng tôi đã đề xuất các phương pháp đạo hàm tăng cường giải bài toán cân bằng không đơn điệu trong không gian Hilbert. Các kết quả trong đề tài đã được báo cáo tại hội nghị quốc tế về nghiên cứu và giảng dạy toán. Kết qủa của đề tài được đăng trên tạp chí quốc tế ISI(SCI) nổi tiếng trong chuyên nghành tối ưu. Các kết quả này có thể sử dụng làm tài liệu tham khảo trong nghiên cứu cơ bản cho nghiên cứu sinh và học viên cao học. Các kết qủa trình bày trong đề tài có thể mở rộng cho bài toán tựa cân bằng, đây sẽ là đề tài thú vị cho những ai quan tâm. 20