Luận án tiến sĩ toán học một số phương pháp giải bài toán chấp nhận tách suy rộn

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC SƯ PHẠM NGUYỄN THỊ THANH HUYỀN MỘT SỐ PHƯƠNG PHÁP GIẢI BÀI TOÁN CHẤP NHẬN TÁCH SUY RỘNG LIÊN QUAN ĐẾN BÀI TOÁN CÂN BẰNG LUẬN ÁN TIẾN SĨ TOÁN HỌC THÁI NGUYÊN–2020 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC SƯ PHẠM NGUYỄN THỊ THANH HUYỀN MỘT SỐ PHƯƠNG PHÁP GIẢI BÀI TOÁN CHẤP NHẬN TÁCH SUY RỘNG LIÊN QUAN ĐẾN BÀI TOÁN CÂN BẰNG Chuyên ngành: Toán Giải tích Mã số: 946 01 02 Người hướng dẫn khoa học: GS. LÊ DŨNG MƯU THÁI NGUYÊN–2020 i LỜI CAM ĐOAN Tôi xin cam đoan đây là công trình nghiên cứu của tôi, được hoàn thành dưới sự hướng dẫn của GS. Các kết quả viết chung với tác giả khác đã được sự nhất trí của đồng tác giả khi đưa vào luận án. Các kết quả nêu trong luận án là những kết quả mới và chưa từng được ai công bố trong các công trình nào khác.

Tác giả Nguyễn Thị Thanh Huyền ii LỜI CẢM ƠN Lời đầu tiên, tôi xin bày tỏ lòng biết ơn sâu sắc tới thầy tôi GS. Thầy đã tận tình hướng dẫn tôi từ khi tôi làm luận văn thạc sĩ và bây giờ là luận án tiến sĩ. Thầy đã tận tình chỉ dạy tôi phương pháp nghiên cứu, cách phát hiện và giải quyết vấn đề, đồng thời Thầy luôn động viên, khích lệ để tôi hoàn thành luận án này. Từ tận đáy lòng, tôi xin bày tỏ lòng biết ơn chân thành và sâu sắc nhất tới Thầy của tôi.

Tôi xin được trân trọng gửi lời cảm ơn tới Ban Giám hiệu Trường Đại học Sư phạm, Ban Chủ nhiệm Khoa Toán, cùng các thầy, các cô tham gia giảng dạy, tạo điều kiện thuận lợi để tôi học tập và nghiên cứu. Đồng thời tôi cũng chân thành cảm ơn các anh chị em nghiên cứu sinh, bạn bè đồng nghiệp tại xêmina nghiên cứu sinh khoa Toán Trường Đại học Sư phạm đã động viên, trao đổi và đóng góp những ý kiến quý báu cho tôi trong suốt quá trình học tập, nghiên cứu và hoàn thành luận án. Tôi xin cảm ơn Ban giám hiệu trường Đại học Khoa học, Đại học Thái Nguyên đã cho tôi cơ hội được đi học tập và nghiên cứu. Tôi xin cảm ơn Ban chủ nhiệm khoa Toán - Tin và các thầy cô Khoa Toán - Tin, đã tạo mọi điều kiện thu xếp công việc thuận lợi cho tôi trong suốt thời gian tôi đi làm nghiên cứu sinh.

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 Toán học, Đại học Thăng Long. Xêmina đã tạo cho tôi động lực 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. Phạm Kỳ Anh.

Thầy đã luôn động viên tôi, tạo điều kiện cho tôi báo cáo và chỉ dạy tôi nhiều kiến thức hữu ích. Tôi cũng xin gửi lời cảm ơn sâu sắc tới TS. Lê Hải Yến, người đã luôn quan tâm, chỉ bảo tôi trên con đường khoa học. Cuối cùng, tôi muốn bày tỏ lòng biết ơn sâu sắc tới những người thân iii trong gia đình, đặc biệt là bố mẹ hai bên, chồng và các con.

Những người đã luôn động viên, chia sẻ mọi khó khăn 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. Tác giả Nguyễn Thị Thanh Huyền iv Mục lục Lời cam đoan i Lời cảm ơn iii Mục lục iii Bảng ký hiệu v Bảng chữ viết tắt viii Mở đầu 1 Chương 1 Một số kiến thức chuẩn bị 12 1. Các khái niệm và kết quả cơ bản. Bài toán cân bằng và một số bài toán liên quan.

Bài toán chấp nhận tách. Một số phương pháp lặp cơ bản tìm điểm bất động. Các kết quả bổ trợ. 25 Chương 2 Thuật toán chiếu kết hợp phép lặp Mann-Krasnoselskii giải bài toán chấp nhận tách 26 2.

Mô tả bài toán và sự hội tụ. Ví dụ minh họa. 43 v Chương 3 Thuật toán dưới đạo hàm giải bài toán chấp nhận tách phi tuyến và ứng dụng cho mô hình cân bằng Nash có ràng buộc 44 3. Mô tả bài toán.

Thuật toán và sự hội tụ. Ví dụ minh họa. 68 Kết luận 69 Tài liệu tham khảo 72 vi vii Bảng ký hiệu R tập các số thực R++ tập các số thực dương Rn không gian véctơ Euclid thực n−chiều hx, yi tích vô hướng của hai véctơ x và y kxk chuẩn Euclid của véctơ x trong không gian Rn xn → x Dãy {xn } hội tụ mạnh tới x PC (x) Phép chiếu của điểm x lên tập C PC (x) = argminy∈C ky − xk NC (x) Nón pháp tuyến ngoài của tập lồi C tại x ∂f (x) Dưới vi phân của hàm f tại x ∂ ǫ f (x) ǫ-dưới vi phân của hàm f tại x ∂2 f (x, x) Dưới vi phân theo biến thứ hai của song hàm f (x, .) tại x ∂2ǫ f (x, x) ǫ-dưới vi phân theo biến thứ hai của song hàm f tại x argminC f Tập các điểm cực tiểu của hàm f trên tập C proxλg Ánh xạ gần kề của hàm lồi g với tham số λ > 0 AT ma trận chuyển vị của ma trận A EP (C, f ) Bài toán cân bằng của song hàm f trên tập C S(C, f ) Tập nghiệm của bài toán cân bằng song hàm f trên tập C ∅ Tập rỗng ✷ Kết thúc chứng minh viii Bảng chữ viết tắt (CFP) Bài toán chấp nhận lồi (EP) Bài toán cân bằng (SEO) Bài toán chấp nhận tách với C là tập nghiệm của bài toán EP và Q là tập nghiệm của bài toán tối ưu (SFP) Bài toán chấp nhận tách (NSEP) Bài toán chấp nhận tách phi tuyến 1 Mở đầu Một trong những lớp bài toán quan trọng thu hút được sự quan tâm nghiên cứu của nhiều nhà khoa học trong nước cũng như trên thế giới đó là bài toán cân bằng. Thuật ngữ cân bằng được sử dụng rộng rãi trong nhiều ngữ cảnh khoa học và kĩ thuật.

Trong Vật lý, trạng thái cân bằng của một hệ, theo thuật ngữ cơ học cổ điển, xảy ra khi hợp lực tác động lên hệ bằng không và trạng thái này được duy trì trong một khoảng thời gian dài. Trong Hóa học, vấn đề cân bằng cũng được đề cập trong các phản ứng hóa học. Trong Sinh học, cân bằng sinh thái là trạng thái ổn định tự nhiên của hệ sinh thái, hướng tới sự thích nghi cao nhất với điều kiện sống, trạng thái này thường xảy ra khi tương quan lực lượng giữa con mồi và thú săn mồi trong hệ sinh thái đó có tỉ lệ tương đồng với nhau. Trong kinh tế, sự cân bằng xảy ra, ví dụ như khi lượng cung bằng lượng cầu.

Trạng thái cân bằng là trạng thái mà con người và vạn vật đều có xu hướng tiến đến. Bài toán cân bằng, còn được gọi là bất đẳng thức Ky Fan, được nghiên cứu trong luận án này có thể phát biểu một cách đơn giản như sau: Cho C là một tập lồi, đóng, khác rỗng trong không gian Rn và f : C × C → R là một song hàm thỏa mãn f (x, x) = 0, với mọi x ∈ C (song hàm có tính chất này thường được gọi là song hàm cân bằng). EP(C, f ) Bất đẳng thức trên được H. Isoda [81] sử dụng lần đầu tiên vào năm 1955 trong khi nghiên cứu trò chơi không hợp tác.

Năm 1972, Ky Fan [62] gọi là bất đẳng thức minimax và ông đã đưa ra các 2 kết quả về sự tồn tại nghiệm của bài toán này. Thuật ngữ bài toán cân bằng được sử dụng lần đầu tiên bởi L. Bài toán cân bằng bao hàm nhiều lớp bài toán quen thuộc như 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 Kakutani, bài toán cân bằng Nash trong lý thuyết trò chơi không hợp tác, bài toán cân bằng véctơ, bài toán cân bằng tập. Các bài toán này, một số được trình bày bởi L.

Oettli [77], sau đó được E. Oettli giới thiệu thêm trong công trình [21] năm 1994, gần đây được giới thiệu khá đầy đủ trong cuốn sách chuyên khảo của G. Bigi và các cộng sự [26]. Ngoài ra, bài toán cân bằng còn được mở rộng sang các bài toán cân bằng véctơ, bài toán cân bằng tập bởi nhiều tác giả trong các tài liệu [42, 49, 70, 73, 87] và cuốn chuyên khảo [55].

Trong vài chục năm trở lại đây, bài toán cân bằng được nghiên cứu cả về tính chất định tính và phương pháp giải. Về tính chất định tính, sự tồn tại nghiệm của bài toán cân bằng được khảo sát trong các công trình [23, 24, 25, 41, 52, 53, 57] và các tài liệu tham khảo trong đó. Sự ổn định nghiệm, cấu trúc của tập nghiệm được nghiên cứu trong các tài liệu [11, 12, 13, 76]. Hướng nghiên cứu về phương pháp giải có thể nói là được quan tâm nhiều hơn, chẳng hạn trong [6, 7, 8, 9, 16, 35, 38, 39, 40, 41, 52, 53, 57, 63, 64, 65, 78, 79, 83, 88, 89, 92].

Dễ thấy rằng nếu ta định nghĩa ánh xạ S bằng cách, với mỗi x ∈ C, đặt S(x) := argmin{f (x, y) : y ∈ C} thì từ điều kiện f (x, x) = 0 với mọi x ∈ C, ta có mọi điểm bất động của ánh xạ S đều là nghiệm của bài toán cân bằng. Ngược lại với các giả thiết thông thường là f (x, .) lồi, khả dưới vi phân, thỏa mãn một tính chất chính quy nào đó, thì mọi điểm bất động của ánh xạ S đều là nghiệm của bài toán cân bằng. Qua đây ta thấy việc tìm nghiệm của bài toán cân bằng có thể quy về việc tìm điểm bất động. Tuy nhiên việc tìm điểm bất động của một ánh xạ, ngay trong trường hợp điểm bất 3 động theo định lý Brouwer đã có từ hơn một thế kỷ, nhưng cho đến nay vẫn chưa có thuật toán hiệu quả cho bài toán này.

Hơn nữa, như đã nêu, bài toán cân bằng bao hàm nhiều bài toán quan trọng, khó giải như là những trường hợp riêng, nên không hy vọng có một thuật toán hiệu quả để giải bài toán cân bằng tổng quát. Vì thế người ta đã nghiên cứu các phương pháp giải bài toán cân bằng với những giả thiết nhất định. Các giả thiết này có thể là một tính chất đơn điệu nào đó như tính giả đơn điệu, đơn điệu, đơn điệu chặt, đơn điệu mạnh và tính lồi, khả dưới vi phân theo biến thứ hai của song hàm f .