Luận án TS Toán học: Các tính chất chính quy của nghiệm bài toán tối ưu - Trần Trịnh Minh Sơn

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC ĐÀ LẠT TRẦN TRỊNH MINH SƠN CÁC TÍNH CHẤT CHÍNH QUY CỦA NGHIỆM BÀI TOÁN TỐI ƯU LUẬN ÁN TIẾN SĨ NGÀNH TOÁN HỌC LÂM ĐỒNG - 2016 ' $ BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC ĐÀ LẠT TRẦN TRỊNH MINH SƠN CÁC TÍNH CHẤT CHÍNH QUY CỦA NGHIỆM BÀI TOÁN TỐI ƯU Chuyên ngành: TOÁN GIẢI TÍCH Mã số: 62.01 LUẬN ÁN TIẾN SĨ NGÀNH TOÁN HỌC Người hướng dẫn khoa học: GS. PHAN QUỐC KHÁNH LÂM ĐỒNG - 2016 & % i LỜI CAM ĐOAN Các kết quả trình bày trong luận án 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. Phan Quốc Khánh. Các kết quả trong luận án là mới và chưa từng được công bố trong các công trình của người khác.

Các kết quả được công bố chung trong hai bài báo [KLS1, KLS2] đã được đồng tác giả cho phép sử dụng trong luận án. Tôi xin chịu trách nhiệm với những lời cam đoan của mình. Lâm Đồng, tháng 09 năm 2016 Tác giả luận án ii LỜI CẢM ƠN Luận án này được hoàn thành tại Trường Đại học Đà Lạt và Trường Đại học Quốc tế - Đại học Quốc gia TP.HCM dưới sự hướng dẫn tận tình và chu đáo của GS. Phan Quốc Khánh và sự quan tâm giúp đỡ của TS.

Tác giả xin bày tỏ lòng biết ơn sâu sắc tới các Thầy. Trong quá trình học tập và nghiên cứu, thông qua các bài giảng, hội nghị và seminar, tác giả luôn nhận được sự quan tâm giúp đỡ cũng như có được những ý kiến đóng góp quý báu của các Thầy Cô ở Khoa Toán - Tin học Trường Đại học Đà Lạt và Phòng bộ môn Tối ưu và Hệ thống Trường Đại học Khoa học Tự nhiên - ĐHQG TP. Tác giả xin chân thành cám ơn. Tác giả xin trân trọng cảm ơn Lãnh đạo Trường Đại học Đà Lạt, Phòng Quản lý Đào tạo, Phòng NCKH - HTQT, Phòng Quản lý Đào tạo - SĐH, Khoa Toán - Tin học, Trưởng ngành Toán Giải tích Trường Đại học Đà Lạt, Phòng Bộ môn Tối ưu và Hệ thống Trường Đại học Khoa học Tự nhiên TP.HCM, Phòng bộ môn Toán Trường Đại học Quốc tế - ĐH QG TP.HCM, Ban lãnh đạo Viện nghiên cứu cao cấp về Toán VIASM, Ban giám đốc Sở Giáo dục và Đào tạo tỉnh Lâm Đồng, Ban giám hiệu Trường THPT Chuyên Thăng Long Đà Lạt và Tổ Toán Trường THPT Chuyên Thăng Long Đà Lạt đã tạo mọi điều kiện thuận lợi cho tác giả trong thời gian làm nghiên cứu sinh.

Xin được cám ơn bạn bè, đồng nghiệp, anh chị em trong nhóm Tối ưu miền Nam và gia đình đã trao đổi, giúp đỡ, động viên và khích lệ tác giả trong suốt quá trình học tập, nghiên cứu và làm luận án. Lâm Đồng, tháng 09 năm 2016 iii Mục lục LỜI CAM ĐOAN i LỜI CẢM ƠN ii DANH SÁCH CÁC KÝ HIỆU v TÓM TẮT vii SUMMARY ix MỞ ĐẦU 1 1 KIẾN THỨC CHUẨN BỊ 9 1.1 Sự hội tụ của dãy tập và dãy ánh xạ đa trị .2 Hội tụ biến phân của dãy hàm và dãy song hàm có giá trị hữu hạn .3 Tính liên tục của ánh xạ đa trị .4 Tính lồi suy rộng theo nón của ánh xạ đa trị. 19 2 TÍNH XẤP XỈ CỦA BÀI TOÁN TỰA BẤT ĐẲNG THỨC BIẾN PHÂN ĐA TRỊ VÀ CÁC ÁP DỤNG 22 2.1 Hội tụ lopside của các song hàm có giá trị hữu hạn trên miền không chữ nhật .2 Tính xấp xỉ của bài toán tựa bất đẳng thức biến phân đa trị .3 Tính xấp xỉ của bài toán cân bằng Nash mở rộng .4 Tính xấp xỉ của nền kinh tế thuần túy trao đổi .5 Tính xấp xỉ của bài toán cân bằng giao thông. 39 iv 3 TÍNH ỔN ĐỊNH VÀ TÍNH ĐẶT CHỈNH LEVITIN-POLYAK CỦA TRÒ CHƠI ĐA MỤC TIÊU MỞ RỘNG CÓ THAM SỐ 47 3.1 Trò chơi đa mục tiêu mở rộng .2 Tính nửa liên tục dưới của ánh xạ nghiệm xấp xỉ .3 Tính đặt chỉnh Levitin-Polyak của trò chơi đa mục tiêu mở rộng có tham số.

54 4 CẬN SAI SỐ VÀ TÍNH ĐẶT CHỈNH CỦA MẠNG GIAO THÔNG 64 4.1 Tính duy nhất nghiệm và cận sai số của mạng giao thông .2 Nghiệm xấp xỉ của mạng giao thông .3 Tính đặt chỉnh của mạng giao thông có tham số. 80 5 TÍNH LIÊN THÔNG CỦA CÁC TẬP NGHIỆM XẤP XỈ CỦA BẤT ĐẲNG THỨC KY FAN ĐA TRỊ 86 5.1 Bất đẳng thức Ky Fan đa trị .2 Vô hướng hóa tuyến tính cho tập nghiệm yếu xấp xỉ .3 Tính nửa liên tục dưới và tính trù mật .4 Tính liên thông của tập nghiệm xấp xỉ và tập nghiệm yếu xấp xỉ. 97 KẾT LUẬN CHUNG 101 CÁC NGHIÊN CỨU TIẾP THEO 102 CÁC CÔNG TRÌNH LIÊN QUAN ĐẾN LUẬN ÁN 103 CÁC BÁO CÁO HỘI THẢO LIÊN QUAN ĐẾN LUẬN ÁN 104 TÀI LIỆU THAM KHẢO 105 v DANH SÁCH CÁC KÝ HIỆU N tập các số tự nhiên R tập các số thực R+ tập các số thực không âm n R không gian Euclide n chiều Bn không gian Banach n chiều ∗ X không gian đối ngẫu của không gian X ∗ ξ, x giá trị của ξ ∈ X tại x ∈ X 2 kết thúc chứng minh m n fv-biv(B × B ) tập các song hàm có giá trị hữu hạn ψ, φ các song hàm có giá trị hữu hạn h ν ν ν f → f hoặc f = h-limν f f hội tụ hypo đến f argminf tập các điểm cực tiểu của hàm f argmaxf tập các điểm cực đại của hàm f domf miền hữu hiệu của hàm số f epif trên đồ thị của hàm số f hypof dưới đồ thị của hàm số f ∂f(x) dưới vi phân của hàm lồi f tại điểm x a L (x) tập mức dưới điều chỉnh của f tại x f Na(x) toán tử nón pháp tuyến tương ứng với f tại x f infA cận dưới lớn nhất của tập số thực A supA cận trên nhỏ nhất của tập số thực A clA bao đóng của tập A intA phần trong của tập A convA bao lồi của tập A NA(x) nón pháp tuyến của tập A tại x d(x, A) khoảng cách từ điểm x đến tập A vi diam(A) đường kính của tập A ¯ B(a, r) hình cầu đóng tâm a bán kính r B(a, r) hình cầu mở tâm a bán kính r S(a, r) mặt cầu tâm a bán kính r ν n x ,x dãy số thực, hoặc dãy véctơ A:=B A được định nghĩa bằng B H(A, B) khoảng cách Hausdorff giữa hai tập hợp A và B C ∗ nón đối ngẫu của nón C ♯ C nón đối ngẫu chặt của nón C νP−K ν C −−−→C Các tập C hội tụ Painleve-Kuratowski đến tập C G:X⇒Y ánh xạ đa trị đi từ tập X và tập Y domG miền hữu hiệu của ánh xạ đa trị G gphG đồ thị của ánh xạ đa trị G −1 G :Y ⇒X ánh xạ ngược của G P:X×Y ⇒X phép chiếu từ X × Y vào X g ν ν G −→G Các ánh xạ G hội tụ graph đến ánh xạ G c ν ν G −→G Các ánh xạ G hội tụ liên tục đến ánh xạ G ν ν Limsupν G giới hạn trên của các ánh xạ đa trị G ν ν Liminfν G giới hạn dưới của các ánh xạ đa trị G ν ν Limν G giới hạn P -K của các ánh xạ đa trị G QVI(T, K) bài toán tựa bất đẳng thức biến phân Q tập nghiệm của QVI(T, K) TNP(T, K) bài toán mạng giao thông T tập các dòng cân bằng của TNP(T, K) GNEP(θ, X) bài toán cân bằng Nash mở rộng G tập các cân bằng Nash mở rộng của GNEP(θ, X) PEE(u, P × M) nền kinh tế thuần túy trao đổi P tập các điểm cân bằng cạnh tranh của PEE(u, P × M) MGG(f, G) trò chơi đa mục tiêu mở rộng M tập các dòng cân bằng Pareto-Nash yếu của MGG(f, G) KFI(F, A, B) bất đẳng thức Ky Fan đa trị K tập nghiệm của KFI(F, A, B) vii TÓM TẮT Luận án trình bày một số kết quả mới về các tính chất chính quy của nghiệm một số bài toán trong tối ưu hóa. Các tính chất ở đây là một số tính chất quan trọng có liên quan với nhau: tính xấp xỉ, tính ổn định nghiệm, tính đặt chỉnh, tính duy nhất nghiệm, tính chất liên thông của nghiệm và cận sai số của biến chấp nhận được.

Các bài toán chúng tôi xét không phải là bài toán cực tiểu, mô hình chính nhất trong tối ưu hóa, mà là một số mô hình khác có ý nghĩa thực tế cao và cũng thường gọi là các bài toán liên quan đến tối ưu: từ bất đẳng thức Ky Fan (còn được gọi là bài toán cân bằng), tựa bất đẳng thức biến phân là các mô hình tổng quát hơn bài toán cực tiểu đến các bài toán rất thực tiễn là trò chơi không hợp tác (cũng còn được gọi là bài toán cân bằng Nash), bài toán mạng giao thông và nền kinh tế thuần túy trao đổi. Luận án có 5 chương. Chương 1 trình bày một số định nghĩa và kiến thức chuẩn bị phục vụ cho các chương sau. Chương 2 nghiên cứu về tính xấp xỉ của bài toán tựa bất đẳng thức biến phân đa trị và áp dụng cho các bài toán thực tiễn: bài toán cân bằng Nash mở rộng, nền kinh tế thuần túy trao đổi và bài toán mạng giao thông.

Chương này đưa ra định nghĩa về các song hàm có giá trị hữu hạn trên miền không chữ nhật cho các bài toán trên, chứng minh xấp xỉ theo nghĩa hội tụ lopside của các song hàm tương ứng các bài toán xấp xỉ đến song hàm của bài toán gốc và thiết lập hội tụ theo nghĩa Painlevé-Kuratowski cho các tập nghiệm tương ứng. Chương 3 nghiên cứu trò chơi đa mục tiêu mở rộng trong không gian véctơ tôpô. viii Điều kiện đủ cho tính nửa liên tục dưới của tập các điểm cân bằng Pareto-Nash yếu xấp xỉ và điều kiện đủ cho tính đặt chỉnh Levitin-Polyak được chứng minh dưới giả thiết compắc. Trong trường hợp trò chơi được xét trong không gian mêtric, tính đặt chỉnh Levitin-Polyak được thiết lập dựa vào các độ đo không compắc.

Chương 4 gồm hai mảng kết quả. Đầu tiên chúng tôi thiết lập các điều kiện đủ về tính duy nhất nghiệm và các cận sai số cho các dòng chấp nhận được của mạng giao thông bằng cách sử dụng hàm đánh giá cho tựa bất đẳng thức biến phân đa trị tương ứng.