Luận án Phương pháp hàm phạt cho bài toán bất đẳng thức biến phân

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC VINH ĐẬU XUÂN LƯƠNG PHƯƠNG PHÁP HÀM PHẠT CHO BÀI TOÁN BẤT ĐẲNG THỨC BIẾN PHÂN LUẬN ÁN TIẾN SĨ TOÁN HỌC VINH - 2010 iBỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC VINH ĐẬU XUÂN LƯƠNG PHƯƠNG PHÁP HÀM PHẠT CHO BÀI TOÁN BẤT ĐẲNG THỨC BIẾN PHÂN LUẬN ÁN TIẾN SĨ TOÁN HỌC Chuyên ngành: Toán giải tích Mã số: 62 46 01 01 NGƯỜI HƯỚNG DẪN KHOA HỌC GS. TSKH. LÊ DŨNG MƯU PGS. TS. TRẦN VĂN ÂN VINH - 2010 MỤC LỤC Mục lục i Lời cam đoan iv Lời cảm ơn 1 Mở đầu 2 1 Lí do chọn đề tài . . . . . . . . . . . . . . . . . . . . . . 2 2 Mục đích nghiên cứu . . . . . . . . . . . . . . . . . . . . 5 3 Đối tượng nghiên cứu . . . . . . . . . . . . . . . . . . . . 6 4 Phạm vi nghiên cứu . . . . . . . . . . . . . . . . . . . . 6 5 Phương pháp nghiên cứu . . . . . . . . . . . . . . . . . . 6 6 Ý nghĩa khoa học và thực tiễn . . . . . . . . . . . . . . . 7 7 Tổng quan và cấu trúc luận án . . . . . . . . . . . . . . . 7 1 Hàm phạt cho bài toán bất đẳng thức biến phân 11 1.1 Các kết quả về sự tồn tại và tính duy nhất nghiệm của bài toán bất đẳng thức biến phân . . . . . . . . . . . . . 12 1.2 Phép chiếu và mối quan hệ với bất đẳng thức biến phân 13 1.3 Phương pháp chiếu . . . . . . . . . . . . . . . . . . . . . 17 1.4 Phương pháp hàm phạt . . . . . . . . . . . . . . . . . . 19 ii iii 1.5 Phương pháp kết hợp phạt-chiếu giải bài toán bất đẳng thức biến phân . . . . . . . . . . . . . . . . . . . . . . . 22 1.6 Ví dụ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 Kết luận Chương 1 . . . . . . . . . . . . . . . . . . . . . . . . 35 2 Hàm phạt cho bài toán bất đẳng thức biến phân vector yếu 36 2.1 Điều kiện đủ cho sự tồn tại nghiệm của bài toán bất đẳng thức biến phân vector yếu . . . . . . . . . . . . . . . . . 38 2.2 Bài toán phạt . . . . . . . . . . . . . . . . . . . . . . . . 39 2.3 Các định lý hội tụ . . . . . . . . . . . . . . . . . . . . . . 44 Kết luận Chương 2 . . . . . . . . . . . . . . . . . . . . . . . . 50 3 Hàm phạt cho bài toán tối ưu đa mục tiêu 51 3.1 Điều kiện đủ cho sự tồn tại nghiệm của bài toán tối ưu đa mục tiêu . . . . . . . . . . . . . . . . . . . . . . . . . 52 3.2 Bài toán phạt . . . . . . . . . . . . . . . . . . . . . . . . 54 3.3 Các định lý hội tụ . . . . . . . . . . . . . . . . . . . . . . 55 Kết luận Chương 3 . . . . . . . . . . . . . . . . . . . . . . . . 61 Kết luận và kiến nghị 62 1 Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 2 Kiến nghị . . . . . . . . . . . . . . . . . . . . . . . . . . 62 Danh mục công trình khoa học của nghiên cứu sinh liên quan đến luận án 63 Tài liệu tham khảo 63 iv LỜI CAM ĐOAN Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi, các kết quả trình bày trong luận án là hoàn toàn trung thực, được các đồng tác giả cho phép sử dụng và luận án hoàn toàn không trùng lặp với bất kì tài liệu nào khác. Đậu Xuân Lương 1LỜI CẢM ƠN Luận án được hoàn thành dưới sự hướng dẫn của GS. TSKH. Lê Dũng Mưu và PGS. TS Trần Văn Ân. Tác giả xin bày tỏ lòng biết ơn sâu sắc nhất tới các Thầy, những người đã tận tình hướng dẫn, giúp đỡ tác giả trong cả quá trình học tập, nghiên cứu và viết bản luận án này. Tác giả cũng xin chân thành cảm ơn Lãnh đạo trường Đại học Vinh, lãnh đạo khoa Toán học, Khoa Sau đại học – Trường Đại học Vinh; Lãnh đạo Viện Toán học, cùng tập thể GS và các Thầy, Cô của Trường Đại học Vinh và Viện Toán học đã động viên giúp đỡ tạo nhiều điều kiện thuận lợi trong thời gian tác giả học tập và nghiên cứu. Tác giả xin gửi lời cảm ơn tới các nhà khoa học và các Thầy, Cô thuộc Tổ Giải tích của Khoa Toán học – Trường Đại học Vinh đã dành thời gian đọc luận án và cho những ý kiến nhận xét quý báu. Tác giả xin gửi lời cảm ơn tới Trường Cao Đẳng Sư phạm Quảng Ninh và Khoa Tự nhiên thuộc Trường Cao Đẳng Sư phạm Quảng Ninh, người thân và bạn bè vì những góp ý, ủng hộ và động viên về tinh thần cũng như vật chất cho tác giả. Đậu Xuân Lương 2MỞ ĐẦU 1 Lí do chọn đề tài 1.1 Lý thuyết bất đẳng thức biến phân ra đời vào những năm 60 ([50, 20, 32]), là một công cụ mạnh và thống nhất để nghiên cứu các bài toán cân bằng. Cho đến nay, những bài toán được quy về các bài toán bất đẳng thức biến phân gồm có: bài toán cân bằng mạng giao thông (Traffic Network Equilibrium Problem) và bài toán gần với nó là bài toán cân bằng giá không gian (Spatial Price Equilibrium Problem) (tham khảo chẳng hạn [8, 47, 9, 42, 41]), các bài toán cân bằng tài chính (Financial Equilibrium Problem), cân bằng nhập cư (Migration Equilibrium Prob- lem), hệ thống môi trường (Environmental Network Problem) và mạng kiến thức (Knowledge Network Problem) ([11, 25, 26, 10, 40, 41, 29]). Phương pháp hàm phạt là một trong các phương pháp quan trọng để giải các bài toán bất đẳng thức biến phân (tham khảo chẳng hạn [38, 23, 39, 1, 51]). Nhờ vào phương pháp này, một bài toán với miền ràng buộc phức tạp có thể được chuyển về một dãy các bài toán không ràng buộc hoặc với ràng buộc đơn giản hơn. Trong khi đó, phương pháp chiếu là một lớp phương pháp đơn giản và hiệu quả, đặc biệt đối với các bài toán thỏa mãn điều kiện đơn điệu. Nhược điểm duy nhất của phương pháp này là ta phải tính hình chiếu của một điểm lên một miền lồi bất kỳ, và đó là một bài toán rất khó trong trường hợp tổng quát, khi mà miền đó không có hình dạng đặc biệt. Do đó, kết hợp phương pháp hàm phạt 3và phương pháp chiếu sẽ khắc phục được nhược điểm này của phương pháp chiếu. 1.2 Khái niệm bất đẳng thức biến phân vector được giới thiệu bởi Giannessi [16]. Từ đó tới nay, người ta đã tìm được nhiều ứng dụng của bài toán bất đẳng thức biến phân vector (Vector Variational Inequality Problem, viết tắt là VVIP) và bài toán bất đẳng thức biến phân vector yếu (Weak Vector Variational Inequality Problem, viết tắt là WVVIP) trong bài toán tối ưu đa mục tiêu (Multiobjective Optimization Problem, viết tắt là MOP) (tham khảo chẳng hạn [16, 2, 4, 53, 18], trong bài toán xấp xỉ vector (Vector Approximation Problem) ([54]), và trong bài toán cân bằng giao thông vector (Vector Traffic Equilibrium Problem) ([55]). Sự tồn tại nghiệm của bài toán bất đẳng thức biến phân vector yếu cũng được nghiên cứu trong nhiều công trình (tham khảo chẳng hạn [6, 4, 3, 31, 12]). Để có thể ứng dụng bài toán bất đẳng thức biến phân vector yếu vào thực tiễn, đòi hỏi phải có các thuật toán giải số hiệu quả cho bài toán này. Tuy nhiên, theo hiểu biết của chúng tôi, cho tới nay chỉ có một vài công trình nghiên cứu về các thuật toán để giải bài toán bất đẳng thức biến phân vector yếu ([18, 19]). Từ rất lâu, phương pháp hàm phạt đã được áp dụng để giải các bài toán tối ưu và các bài toán bất đẳng thức biến phân dạng thường, đưa một bài toán với miền ràng buộc phức tạp về một dãy các bài toán có ràng buộc đơn giản hơn hoặc không có ràng buộc. Tuy nhiên, cho tới nay chưa có bất cứ công trình nào nghiên cứu áp dụng phương pháp này cho bài toán bất đẳng thức biến phân vector yếu mà chúng tôi được biết. 1.3 Khái niệm nghiệm tối ưu Pareto (mà trong luận án này chúng tôi gọi là nghiệm Pareto) của bài toán tối ưu đa mục tiêu xuất hiện đầu tiên trong các công trình của Edgeworth [13] và Pareto [44]. Một điểm x được gọi là nghiệm Pareto của bài toán tối ưu đa mục tiêu với hàm mục tiêu f = (f1, . . . , fk) (k mục tiêu) nếu không có một điểm nào khác tốt hơn 4điểm đó, nghĩa là không tồn tại một điểm y 6= x sao cho fi(y) ≤ fi(x) với mọi i = 1, . . . , k, và fj(y) < fj(x) với một chỉ số j nào đó. Điểm x được gọi là nghiệm Pareto yếu của bài toán tối ưu đa mục tiêu nếu không có một điểm nào khác tốt hơn điểm đó xét trên tất cả các mục tiêu, nghĩa là không tồn tại y sao cho fi(y) < fi(x) với mọi i = 1, . . . , k. Bài toán tối ưu đa mục tiêu có ứng dụng rộng rãi trong rất nhiều lĩnh vực, trong cả khoa học và cuộc sống. Lý thuyết tối ưu đa mục tiêu được sử dụng trong bài toán xấp xỉ vector (Vector Approximation Problem), lý thuyết trò chơi (Game Theory), các bài toán quản lý và hoạch định tài nguyên (Resource Planning and Management), lý thuyết phúc lợi (Welfare Theory), các bài toán trong kỹ thuật như điều khiển phi cơ, các hệ thống cơ khí chính xác, .v.v.. (tham khảo chẳng hạn [48, 49, 33, 24]). Phương pháp hàm phạt áp dụng cho bài toán tối ưu đa mục tiêu đã được nghiên cứu trong một vài công trình gần đây (tham khảo [52, 21, 22, 34]). Trong [34], Liu và Feng nghiên cứu nghiệm Pareto yếu của bài toán MOP(D,f) sử dụng một hàm phạt mũ. Liu và Feng đã chứng minh rằng nếu x là một điểm giới hạn của một dãy các nghiệm Pareto yếu của các bài toán phạt và x chấp nhận được (nghĩa là x ∈ D), thì x là một nghiệm Pareto yếu của bài toán ban đầu. Như vậy, các định lý hội tụ của họ dựa trên giả thiết rằng điểm giới hạn x của dãy các nghiệm Pareto yếu của các bài toán phạt nằm trong miền ràng buộc D. Giả thiết này là một điểm bất lợi trong cách tiếp cận bài toán tối ưu đa mục tiêu với hàm phạt mũ của Liu và Feng. Từ đó nảy sinh yêu cầu phải có một mô hình hàm phạt cho các kết quả hội tụ tốt hơn, khắc phục được nhược điểm của mô hình đề xuất trong [34]. Với các lí do nêu trên, chúng tôi chọn đề tài “Phương pháp hàm phạt cho bài toán bất đẳng thức biến phân” làm đề tài luận án tiến sĩ. Đề tài tập trung nghiên cứu những vấn đề sau. (1) Kết hợp phương pháp hàm phạt và phương pháp chiếu để có một 5thuật toán hoàn chỉnh giải các bài toán bất đẳng thức biến phân dạng VIP(D,f), với D lồi đóng khác rỗng và f đơn điệu, liên tục Lipschitz. Bằng cách này, ta khắc phục được trở ngại lớn nhất của phương pháp chiếu là sự khó khăn khi tính toán hình chiếu của một điểm lên một miền lồi bất kỳ. (2) Áp dụng phương pháp hàm phạt để chuyển một bài toán bất đẳng thức biến phân vector yếu với ràng buộc trên một miền D lồi đóng bất kỳ về một dãy các bài toán bất đẳng thức biến phân vector yếu với miền ràng buộc K ⊃ D đơn giản hơn, gọi là các bài toán phạt. Ta có thể chọn K = Rk, nghĩa là các bài toán phạt sẽ không có ràng buộc. (3) Áp dụng phương pháp hàm phạt để chuyển một bài toán tối ưu đa mục tiêu với ràng buộc trên một miền D lồi đóng bất kỳ về một dãy các bài toán tối ưu đa mục tiêu với miền ràng buộc K ⊃ D đơn giản hơn, gọi là các bài toán phạt. Ta có thể chọn K = Rk, nghĩa là các bài toán phạt sẽ không có ràng buộc. Bằng cách sử dụng hàm phạt ngoài, chúng tôi thu được các kết quả hội tụ tốt hơn so với các kết quả nêu trong [34]. Ngoài ra, chúng tôi còn chỉ ra điều kiện đủ để các bài toán phạt đều có nghiệm Pareto yếu, đồng thời dãy các nghiệm đó có ít nhất một điểm giới hạn và đó chính là một nghiệm của bài toán ban đầu. 2 Mục đích nghiên cứu Luận án nhằm mục đích nghiên cứu áp dụng phương pháp hàm phạt cho bài toán bất đẳng thức biến phân, bài toán bất đẳng thức biến phân vector yếu và bài toán tối ưu đa mục tiêu, trong đó bài toán cuối cùng trong một số trường hợp đặc biệt là tương đương với bài toán bất đẳng thức biến phân vector yếu. Qua đó, luận án đưa ra những thuật toán mới cho các bài toán vừa nêu ở trên. 63 Đối tượng nghiên cứu Phương pháp hàm phạt, bài toán bất đẳng thức biến phân dạng thường và dạng vector yếu, bài toán tối ưu đa mục tiêu. 4 Phạm vi nghiên cứu Luận án nghiên cứu bài toán bất đẳng thức biến phân, bài toán bất đẳng thức biến phân vector yếu và bài toán tối ưu đa mục tiêu trong không gian Euclide hữu hạn chiều Rk. 5 Phương pháp nghiên cứu Chúng tôi sử dụng phương pháp nghiên cứu lí thuyết trong khi thực hiện đề tài. Trong chương thứ nhất, bằng việc kết hợp lợi thế của phương pháp hàm phạt và phương pháp chiếu, chúng tôi đã khắc phục được trở ngại lớn nhất của phương pháp chiếu là khó khăn trong việc tính hình chiếu của một điểm lên một miền lồi bất kỳ. Trong chương thứ hai, chúng tôi nghiên cứu phương pháp hàm phạt áp dụng cho bất đẳng thức biến phân vector yếu, sử dụng các kỹ thuật chứng minh truyền thống trong lý thuyết hàm phạt cho bài toán bất đẳng thức biến phân và cho bài toán tối ưu để chứng minh tính hội tụ của thuật toán. Điểm khác với các công trình nghiên cứu về bài toán bất đẳng thức biến phân (dạng thường) trước đó là chúng tôi đổi vị trí của tham số phạt khi xây dựng bài toán phạt. Nhờ đó tính hội tụ của thuật toán được chứng minh. Trong chương thứ ba, thay vì áp dụng hàm phạt mũ như trong [34], chúng tôi sử dụng hàm phạt ngoài và áp dụng kỹ thuật chứng minh trong [38], nhờ đó thu được các kết quả hội tụ tốt hơn các kết quả nêu trong [34]. 76 Ý nghĩa khoa học và thực tiễn Kết quả của luận án góp phần giải quyết vấn đề giải số các bài toán bất đẳng thức biến phân dạng thường và dạng vector yếu và bài toán tối ưu đa mục tiêu. Luận án là tài liệu tham khảo cho sinh viên, học viên cao học và nghiên cứu sinh chuyên ngành Toán giải tích. 7 Tổng quan và cấu trúc luận án 7.1 Tổng quan luận án Trong luận án này, chúng tôi nghiên cứu phương pháp hàm phạt cho bài toán bất đẳng thức biến phân (dạng thường), bài toán bất đẳng thức biến phân vector và bài toán liên quan với nó là bài toán tối ưu đa mục tiêu. Chương 1 nghiên cứu vấn đề kết hợp phương pháp hàm phạt và phương pháp chiếu để giải bài toán bất đẳng thức biến phân. Chúng tôi nhắc lại một số định nghĩa và kết quả cơ bản về sự tồn tại và duy nhất nghiệm của bài toán bất đẳng thức biến phân. Phương pháp chiếu và phương pháp hàm phạt cho bài toán bất đẳng thức biến phân được trình bày tương ứng trong các mục 1.3 và 1.4. Kết quả chính của chương này được trình bày trong mục 1.5. Trong mục này, chúng tôi đưa ra Thuật toán 3, kết hợp các phương pháp hàm phạt và phương pháp chiếu để giải bài toán bất đẳng thức biến phân. Thuật toán này trước hết chuyển một bài toán bất đẳng thức biến phân ràng buộc trên một miền lồi đóng D bất kỳ về một dãy các bài toán phạt với ràng buộc đơn giản hơn, sau đó giải mỗi bài toán phạt này bằng phương pháp chiếu. Vì các bài toán phạt có miền ràng buộc đơn giản, việc tính hình chiếu của một điểm bất kỳ lên 8miền ràng buộc đó trở nên dễ dàng hơn. Do đó phương pháp chiếu có thể giải các bài toán phạt một cách hiệu quả. Chúng tôi minh họa Thuật toán 3 trong ba ví dụ 1.6.1, 1.6.2, và 1.6.3, giải số bài toán bất đẳng thức biến phân trong trường hợp hai chiều và nhiều chiều, trong đó trường hợp nhiều chiều lấy theo mô hình Nash ([28]). Kết quả của Chương 1 được công bố trong [37]. Trong Chương 2, chúng tôi nghiên cứu phương pháp hàm phạt áp dụng cho bài toán bất đẳng thức biến phân vector yếu WVVIP(D,F ). Kết quả cơ bản về sự tồn tại nghiệm của bài toán bất đẳng thức biến phân vector yếu mà chúng tôi sử dụng trong chương này là Định lý 2.1.3 ([6]). Trong định lý này, tính chất cơ bản mà ánh xạ F cần phải thoả mãn là tính bức yếu trên D trong trường hợp miền D không bị chặn. Chúng tôi đưa ra khái niệm D-bức trên K. Với ánh xạ F thỏa mãn điều kiện D-bức trên K, sự tồn tại nghiệm của các bài toán phạt WVVIP(K,F (t)) với t > 0 được đảm bảo. Kết quả này được chứng minh trong Bổ đề 2.2.5. Trong mục 2.3, chúng tôi trình bày các định lý hội tụ cho mô hình hàm phạt. Trước hết, với Bổ đề 2.3.1, chúng tôi chứng minh rằng một điểm giới hạn bất kỳ của một dãy các nghiệm của bài toán phạt là một điểm chấp nhận được, nghĩa là nó thuộc vào miền ràng buộc của bài toán bất đẳng thức biến phân vector yếu ban đầu. Tiếp theo, với giả thiết về tính liên tục của ánh xạ F , trong Định lý 2.3.2 chúng tôi chứng minh rằng một điểm giới hạn bất kỳ của một dãy các nghiệm của các bài toán phạt WVVIP(K,F (t)) khi tham số phạt t tiến ra vô cùng sẽ là một nghiệm của bài toán ban đầu WVVIP(D,F ). Chúng tôi đưa ra một tính chất mạnh hơn tính chất D-bức trên K, đó là tính chất D-bức mạnh trên K của ánh xạ F : Rk → Rr×k. Định lý 2.3.4 chứng minh rằng nếu F là một ánh xạ liên tục, đơn điệu, thỏa mãn điều kiện D-bức mạnh trên K, thì (1) các bài toán phạt luôn có ít nhất một nghiệm; 9(2) một dãy nghiệm bất kỳ của các bài toán phạt luôn bị chặn và do đó có ít nhất một điểm giới hạn; (3) một điểm giới hạn bất kỳ của dãy các nghiệm của các bài toán phạt sẽ là nghiệm của bài toán ban đầu. Kết quả của Chương 2 được công bố trong [35]. Trong Chương 3, chúng tôi áp dụng phương pháp hàm phạt cho bài toán tối ưu đa mục tiêu MOP(D,f). Sử dụng các kết quả về sự tồn tại nghiệm Pareto yếu của bài toán tối ưu đa mục tiêu ([30]) và sự tồn tại nghiệm của bài toán bất đẳng thức biến phân vector yếu ([6]), trong Bổ đề 3.2.1 chúng tôi đưa ra điều kiện đủ cho sự tồn tại nghiệm của các bài toán phạt MOP(K,f (t)) với t > 0. Các kết quả chính về sự hội tụ của thuật toán phạt được trình bày trong mục 3.3. Bổ đề 3.3.1 chứng minh tính chấp nhận được của một điểm giới hạn của một dãy bất kỳ các nghiệm Pareto yếu của các bài toán phạt MOP(K,f (t)) khi t tiến ra vô cùng. Dựa vào bổ đề này, Định lý 3.3.2 chứng tỏ rằng một điểm giới hạn bất kỳ của một dãy các nghiệm Pareto yếu của các bài toán phạt MOP(K,f (t)) khi t tiến ra vô cùng là một nghiệm Pareto yếu của bài toán ban đầu MOP(D,f). Dùng kỹ thuật bao nghiệm Pareto yếu của các bài toán phạt bởi một hình cầu, trong Định lý 3.3.3 chúng tôi đưa ra một điều kiện đủ để (1) các bài toán phạt luôn có ít nhất một nghiệm; (2) một dãy nghiệm bất kỳ của các bài toán phạt luôn bị chặn và do đó có ít nhất một điểm giới hạn; (3) một điểm giới hạn bất kỳ của dãy các nghiệm của các bài toán phạt sẽ là nghiệm của bài toán ban đầu. Kết quả của Chương 3 được công bố trong [36]. 10 7.2 Cấu trúc luận án Nội dung chính của luận án được trình bày trong 3 chương. Ngoài ra, luận án có Lời cam đoan, Lời cảm ơn, Mục lục, phần Mở đầu, phần Kết luận và kiến nghị, Danh mục công trình khoa học của nghiên cứu sinh liên quan đến luận án, và Tài liệu tham khảo. Chương 1 trình bày về sự kết hợp giữa phương pháp hàm phạt và phương pháp chiếu để giải bài toán bất đẳng thức biến phân, bao gồm 6 mục. Mục 1.1 trình bày các kết quả cơ bản về sự tồn tại và duy nhất nghiệm của bài toán bất đẳng thức biến phân, Mục 1.2 trình bày phép chiếu và mối quan hệ với bài toán bất đẳng thức biến phân, Mục 1.3 trình bày về phương pháp chiếu, Mục 1.4 trình bày về phương pháp hàm phạt, Mục 1.5 trình bày về phương pháp kết hợp giải bài toán bất đẳng thức biến phân, Mục 1.6 trình bày các ví dụ. Chương 2 trình bày về phương pháp hàm phạt áp dụng cho bài toán bất đẳng thức biến phân vector yếu, bao gồm 3 mục. Mục 2.1 trình bày các kết quả cần dùng về sự tồn tại nghiệm của bài toán bất đẳng thức biến phân vector yếu, Mục 2.2 trình bày về bài toán phạt và điều kiện có nghiệm của bài toán phạt, Mục 2.3 trình bày các định lý hội tụ của phương pháp. Chương 3 trình bày về phương pháp hàm phạt áp dụng cho bài toán tối ưu đa mục tiêu, bao gồm 3 mục. Mục 3.1 trình bày các kết quả cần dùng về sự tồn tại nghiệm Pareto yếu của bài toán tối ưu đa mục tiêu, Mục 3.2 trình bày về bài toán phạt và điều kiện có nghiệm của bài toán phạt, Mục 3.3 trình bày các định lý hội tụ của phương pháp. 11 CHƯƠNG 1 HÀM PHẠT CHO BÀI TOÁN BẤT ĐẲNG THỨC BIẾN PHÂN Giả sử D ⊂ Rn là một tập lồi đóng khác rỗng và f : Rn → Rn là một ánh xạ bất kỳ. Ký hiệu 〈·, ·〉 là tích vô hướng trên Rn. Xét bài toán bất đẳng thức biến phân sau đây VIP(D,f) : Tìm x ∈ D, sao cho 〈f(x),y−x〉 ≥ 0, với mọi y ∈ D. Tập nghiệm của VIP(D,f) được kí hiệu là S. Tập D được gọi là miền ràng buộc của bài toán; f được gọi là ánh xạ giá của bài toán. Nếu f là gradient của một ánh xạ lồi g thì VIP(D,f) tương đương với bài toán tìm cực tiểu của g trên D. Tuy nhiên, không phải bài toán bất đẳng thức biến phân nào cũng tương đương với một bài toán quy hoạch lồi. Phương pháp chiếu (tham khảo [15], Chương 12) là một lớp phương pháp đơn giản và hiệu quả để giải các bài toán bất đẳng thức biến phân với giả thiết tối thiểu f giả đơn điệu và liên tục. Trở ngại chính trong phương pháp này là việc tính toán hình chiếu lên một tập lồi bất kỳ không hề đơn giản. Đó là một bài toán qui hoạch toàn phương với miền xác định lồi. Nếu D không có hình dạng đặc biệt thì việc xác định hình chiếu lên D là một bài toán khó giải. Trong khi đó, phương pháp hàm phạt (xem [38]) cho phép đưa bài toán 12 bất đẳng thức biến phân trên miền lồi đóng (bị chặn) bất kỳ về một dãy các bài toán bất đẳng thức biến phân trên một miền bất kỳ bao miền lồi ban đầu. Ý tưởng của chúng tôi là: đối với VIP(D,f) trong đó D là một miền lồi đóng bất kỳ, trước tiên dùng phương pháp hàm phạt để đưa nó về một dãy các bài toán trên một miền K bao D, sau đó dùng phương pháp chiếu để giải mỗi bài toán trên K. Miền K được xác định sao cho việc tính toán hình chiếu của một điểm lên K là dễ dàng. Trong trường hợp K là hình hộp, hình cầu hay không gian con, vì phép chiếu của một điểm lên K có công thức hiển đơn giản nên trở ngại chính của phương pháp chiếu được khắc phục. 1.1 Các kết quả về sự tồn tại và tính duy nhất nghiệm của bài toán bất đẳng thức biến phân Chúng tôi nhắc lại một vài định nghĩa và kết quả cần thiết. 1.1.1 Định lí. ([15], Hệ quả 2.2.5) (i) Nếu D là một tập lồi compắc khác rỗng và f liên tục trên D thì VIP(D,f) có ít nhất một nghiệm. (ii) Nếu f thỏa mãn điều kiện bức, nghĩa là lim x∈D,||x||→∞ 〈f(x)− f(x),x− x〉 ||x− x|| =∞ với x ∈ D nào đó, thì VIP(D,f) có ít nhất một nghiệm. 1.1.2 Định nghĩa. ([15], Định nghĩa 2.3.1) Ánh xạ f : D → Rn được gọi là 13 (i) đơn điệu trên D nếu 〈f(x)− f(y),x− y〉 ≥ 0, ∀x,y ∈ D; (ii) đơn điệu ngặt trên D nếu 〈f(x)− f(y),x− y〉 > 0, ∀x,y ∈ D và x 6= y; (iii) đơn điệu mạnh trên D nếu tồn tại hằng số α > 0 sao cho 〈f(x)− f(y),x− y〉 ≥ α||x− y||2, ∀x,y ∈ D; (iv) liên tục Lipschitz trên D nếu tồn tại hằng số L > 0 sao cho ||f(x)− f(y)|| ≤ L||x− y||, ∀x,y ∈ D; (v) giả đơn điệu trên D tương ứng với S nếu S 6= ∅ và ∀x ∈ S : 〈f(y),y − x〉 ≥ 0, ∀y ∈ D. Một thí dụ điển hình của ánh xạ đơn điệu (mạnh) là đạo hàm của một hàm lồi (mạnh). 1.1.3 Định lí. ([15], Định lý 2.3.3) (i) Nếu f đơn điệu ngặt trên D thì VIP(D,f) có nhiều nhất là một nghiệm. (ii) Nếu f đơn điệu mạnh trên D thì VIP(D,f) có nghiệm duy nhất. 1.2 Phép chiếu và mối quan hệ với bất đẳng thức biến phân 1.2.1 Định nghĩa. Giả sử D là một tập con lồi đóng khác rỗng của Rn. Với mọi vector x ∈ Rn, ta định nghĩa d(D,x) = inf y∈D ||x− y||. 14 Hàm d(D, .) được gọi là hàm khoảng cách tương ứng với chuẩn Euclide của x tới D. Nếu tồn tại y ∈ D sao cho d(D,x) = ||x− y|| thì y được gọi là hình chiếu vuông góc hay hình chiếu Euclide của x lên D (gọi tắt là hình chiếu của x lên D), và được ký hiệu bởi PD(x). Mệnh đề sau mô tả mối quan hệ giữa phép chiếu và tập nghiệm S của bài toán bất đẳng thức biến phân. 1.2.2 Mệnh đề ([15], Mục 12.1.1). Cho D ⊂ Rn là một tập con lồi đóng khác rỗng và f : Rn → Rn là một ánh xạ bất kỳ. Khi đó với ξ > 0 bất kỳ ta có x ∈ S⇐⇒fnatD (x) = 0, trong đó fnatD (x) ≡ x− PD(x− ξf(x)). 1.2.3 Nhận xét. Nếu D là một tập con lồi đóng khác rỗng thì hình chiếu của một điểm bất kỳ lên D luôn tồn tại và là duy nhất. Nếu K là một hình hộp, hình cầu, hay một không gian con thì tính hình chiếu của một điểm lên K rất dễ dàng. A. Hình chiếu của một điểm lên một hình hộp Giả sử rằng K = {x = (x1, x2, ..., xn)T ∈ Rn : ai ≤ xi ≤ bi, i = 1, 2, ..., n}, a = (a1, a2, ..., an) T ; b = (b1, b2, ..., bn) T ∈ Rn. Khi đó hình chiếu của x lên K được xác định như sau (PK(x))i =  ai, xi < ai, xi, xi ∈ [ai, bi], bi, xi > bi. (1.1) 15 B. Hình chiếu của một điểm lên một hình cầu Giả sử x = (x1, x2, ..., xn) T ∈ Rn, và C là một hình cầu bán kính R tâm A = (a1, a2, ..., an) T ∈ Rn, xác định bởi C = {z ∈ Rn : n∑ i=1 (zi − ai)2 ≤ R2}. Ta cần tìm hình chiếu y = PC(x) của x lên C. Nếu x ∈ C, ta có y ≡ x. Nếu x 6∈ C, hình chiếu của x lên C là giao điểm của đường thẳng nối x và tâm A của C, ký hiệu là ∆, với mặt cầu S = {z ∈ Rn : n∑ i=1 (zi − ai)2 = R2}. Ta có ∆ = {z ∈ Rn : zi = ai + t(xi − ai), i = 1, 2, . . . , n, t ∈ R}. Thay zi = ai + t(xi − ai) vào phương trình của S, ta thu được t2 n∑ i=1 (xi − ai)2 = R2. Do đó t = R /( n∑ i=1 (xi − ai)2 )1/2 . Vì vậy y có tọa độ như sau yi = ai + (xi − ai) R ( ∑n i=1(xi − ai)2)1/2 , i = 1, 2, . . . , n. C. Hình chiếu của một điểm lên một không gian con 16 Giả sử L ⊂ Rn là một không gian con k chiều với một cơ sở B = {η1,η2, . . . ,ηk}. Giả sử x ∈ Rn, và y = k∑ j=1 yjηj ∈ L, trong đó yj là các hệ số thực sao cho w = x− y thỏa mãn 〈w,ηj〉 = 0, với mọi j = 1, 2, . . . , k (ta sẽ tìm y thỏa mãn điều kiện này sau). Khi đó y là hình chiếu của x lên L. Thật vậy, vì w trực giao với mọi vector trong cơ sở của L nên nó cũng trực giao với mọi vector của L. Do đó, với z ∈ L, ||x− z||2 = 〈x− y + y − z,x− y + y − z〉 = 〈x− y,x− y〉+ 〈y − z,y − z〉+ 2〈w,y − z〉 = ||x− y||2 + ||y − z||2 ≥ ||x− y||2. Vì vậy y là hình chiếu của x lên L. Bây giờ ta tìm vector y như thế. Với mọi i = 1, 2, . . . , k, ta có 〈x− y,ηi〉 = 0. Nói cách khác, với mọi i = 1, 2, . . . , k ta có k∑ j=1 〈ηi,ηj〉yj = 〈x,ηi〉. (1.2) Với 1 ≤ i, j ≤ k đặt aij = 〈ηi,ηj〉, 17 và bi = 〈x,ηi〉. Khi đó từ (1.2) ta thu được một hệ tuyến tính k phương trình k ẩn Ay = b, trong đó A = (aij), và b = (b1, b2, . . . , bk) T . Hơn nữa theo định nghĩa, A là một ma trận xác định dương, nghĩa là det(A) 6= 0. Do đó hệ này có đúng một nghiệm. Vì y = k∑ j=1 yjηj, một khi ta biết yi, ta xác định được y. Nếu B được chọn là một cơ sở trực chuẩn của L, nghĩa là 〈ηi,ηj〉 = 0, i 6= j1, i = j, thì A là ma trận đơn vị. Do đó ta lập tức tính được yi = bi = 〈x,ηi〉, i = 1, 2, . . . , k. 1.3 Phương pháp chiếu Ta chỉ đề cập ở đây phương pháp chiếu hai lần, vì có thể sử dụng phương pháp này cho cả VIP(D,f) với f giả đơn điệu. Trong khi đó 18 phương pháp chiếu một lần có thể không hội tụ ngay cả khi f là đơn điệu. Hơn nữa, khi D có hình dạng đặc biệt thì khối lượng tính toán trong mỗi bước lặp là nhỏ nhất so với các phương pháp chiếu khác (vấn đề phân loại các phương pháp chiếu có thể tham khảo trong [15]). Thuật toán chiếu được mô tả dưới đây. Thuật toán 1. ([15], Mục 12.1.2) Dữ liệu: x(0) ∈ D và η > 0. Bước 0: Đặt k = 0. Bước 1: Nếu x(k) ∈ S, nghĩa là x(k) = PD(xk− ηf(x(k))), dừng và trả ra x(k) là một nghiệm. Bước 2: Tính x(k+1/2) = PD(x (k) − ηf(x(k))), x(k+1) = PD(x (k) − ηf(x(k+1/2))). Gán k := k + 1 và quay lại Bước 1. Trong Thuật toán 1 tham số η > 0 được gọi là độ dài bước. Sự thay đổi của η sẽ có ảnh hưởng tới tốc độ hội tụ của thuật toán. Sự hội tụ của Thuật toán 1 được đảm bảo bởi định lý sau. 1.3.1 Định lí. ([15], Bổ đề 12.1.10, Định lý 12.1.11) Cho D ⊂ Rn là một tập lồi đóng khác rỗng và f : D → Rn là một ánh xạ giả đơn điệu trên D tương ứng với S và liên tục Lipschitz trên D với hằng số L > 0. (i) Với mọi x ∈ S và với mọi k ∈ N, ta có ||x(k+1) − x||2 ≤ ||x(k) − x||2 − (1− η2L2)||x(k+1/2) − x(k)||2. (ii) Nếu 0 < η < 1/L thì dãy {x(k)} sinh bởi Thuật toán 1 hội tụ về một nghiệm của VIP(D,f). 19 1.4 Phương pháp hàm phạt Phương pháp hàm phạt được trình bày sau đây được đề xuất bởi L. D. Muu [38]. Cho D là một tập con lồi đóng khác rỗng của Rn, K là một tập con của Rn chứa D. Ta sẽ xây dựng một hàm lồi khả vi P : K → R thỏa mãn P (x) ≤ 0⇐⇒x ∈ D. (1.3) Hàm P thỏa mãn (1.3) được gọi là hàm phạt của D. Một hàm P thỏa mãn (1.3) còn được gọi là hàm thưởng-phạt, hay còn gọi là hàm phạt kiểu Lagrange. Khác với hàm phạt điểm ngoài thông thường đòi hỏi phải triệt tiêu trên miền ràng buộc D, hàm thưởng-phạt cho phép nhận giá trị âm tại các điểm thuộc D. Đối với một hàm phạt P thông thường, ta có P (x) = 0 với mọi x ∈ D. Điều này có nghĩa lượng phạt sẽ là 0 đối với mọi phương án thuộc D. Trong khi đó loại hàm thưởng-phạt lượng phạt sẽ khác nhau đối với mỗi phương án thuộc D. Nếu P (x) < 0, có nghĩa lượng phạt là âm (tức là thưởng). Nếu D = {x ∈ Rn : gi(x) ≤ 0 , i = 1, 2, ...,m}, trong đó gi : Rn → R là các hàm lồi khả vi thì hàm phạt P có thể lấy như sau P (x) := m∑ i=1 [max{0, gi(x)}]2. (1.4) Dễ thấy P thỏa mãn (1.3), hơn nữa P khả vi khi P được lấy theo (1.4). Thật vậy, xét hi(x) := [max{0, gi(x)}]2 = (α ◦ gi)(x), trong đó α(x) := [max{0, x}]2 = x2, x > 0,0, x ≤ 0. 20 Dễ thấy với x > 0 ta có α′(x) = 2x và với x < 0 ta có α′(x) = 0. Tại x = 0, đạo hàm bên phải của α bằng 0 lim ∆x→0+ α(0 + ∆x)− α(0) ∆x = lim ∆x→0+ (∆x)2 ∆x = 0, và bằng đạo hàm bên trái. Do đó α(x) khả vi trên R. Vì gi khả vi, hi là hàm hợp của hai hàm khả vi, cũng khả vi, với mọi i = 1, . . . ,m; nghĩa là P (x) khả vi trên Rn. Hoặc có thể lấy P (x) = max 1≤i≤m (gi(x)). (1.5) Trong trường hợp này, nếu m = 1 và g1 khả vi thì P ≡ g1 cũng khả vi. Bây giờ ta xây dựng các bài toán phạt sử dụng hàm phạt vừa định nghĩa ở trên. Với mỗi t > 0, đặt f (t) = tf +∇P . Dễ thấy rằng f (t) là đơn điệu với mọi t > 0 nếu f là đơn điệu. Ta xét bài toán bất đẳng thức biến phân ứng với tham số phạt t, ký hiệu VIP(K,f (t)) : Tìm x(t) ∈ K sao cho 〈f (t)(x(t)),x−x(t)〉 ≥ 0 , ∀x ∈ K, trong đó K ⊃ D là một tập lồi đóng bao D sao cho hình chiếu của một điểm bất kỳ của Rn lên K có thể được xác định dễ dàng, thậm chí là bởi một công thức hiển (ví dụ K là một hình hộp, một hình cầu hay một không gian con). Kí hiệu S(t) là tập nghiệm của VIP(K,f (t)) và đặt t∗ = sup{t ≥ 0 : S(t) ⊂ D}. 1.4.1 Bổ đề ([38]). Giả sử f là ánh xạ đơn điệu trên K, P là một hàm phạt lồi, khả vi, thỏa mãn (1.3) và bị chặn dưới. Khi đó (i) S(t) ∩D = ∅ nếu t > t∗, (ii) S(t) ⊂ D nếu 0 < t < t∗, 21 (iii) S(t∗) nằm trong tập nghiệm của bài toán ban đầu VIP(D,f) nếu 0 < t∗ <∞ và ánh xạ S(·) nửa liên tục dưới tại t∗, (iv) Nếu t∗ = ∞ thì bất kỳ dãy {x(k)} nào với x(k) ∈ S(tk) và với tk → t∗ có một điểm giới hạn và bất kỳ điểm giới hạn nào của {x(k)} đều là một nghiệm của VIP(D,f), (v) Nếu t∗ = 0 và S(0) 6= ∅ thì một điểm giới hạn bất kỳ của dãy {x(k)} với x(k) ∈ S(tk) và với tk → t∗ đều là một nghiệm của VIP(D,f). Hàm P cho bởi (1.4) bị chặn dưới bởi 0, do đó lập tức thỏa mãn các yêu cầu của bổ đề trên. Thuật toán 2. ([38]) Xây dựng một hàm phạt P thỏa mãn các điều kiện của Bổ đề 1.4.1. Lấy một số dương tùy ý t0 > 0. Đặt a = 0, b =∞ và chuyển sang Bước k với k = 0. Bước k (k = 0, 1, . . .): Giải bài toán VIP(K,f (tk)) thu được nghiệm x(k). a) Nếu x(k) ∈ D, đặt a := tk và tk+1 = (a+ b)/2, b <∞,2a, b =∞. Gán k := k + 1 và quay lại Bước k. b) Nếu x(k) /∈ D, đặt b := tk và tk+1 := (a + b)/2. Gán k := k + 1 và quay lại bước k. 1.4.2 Định lí ([38]). Giả sử f là ánh xạ đơn điệu trên K và {x(k)} là dãy thu được từ thuật toán trên. Với các giả thiết của Bổ đề 1.4.1, ta có 22 (i) Nếu x(k) ∈ D với k nào đó thì dãy {x(k)} có một dãy con hội tụ, trong đó tất cả các phần tử của dãy con đó là chấp nhận được (tức là thuộc D) và một điểm giới hạn bất kỳ của {x(k)} là nghiệm của bài toán ban đầu VIP(D,f). (ii) Trái lại, một điểm giới hạn bất kỳ của dãy {x(k)} là một nghiệm của bài toán ban đầu VIP(D,f). Chú ý rằng nếu P (x) ≡ 0 với mọi x ∈ D và x(k) là một nghiệm của VIP(K,f (tk)) thỏa mãn x(k) ∈ D, khi đó x(k) cũng là một nghiệm của bài toán ban đầu VIP(D,f). 1.5 Phương pháp kết hợp phạt-chiếu giải bài toán bất đẳng thức biến phân Trong phần này chúng tôi kết hợp phương pháp hàm phạt và phương pháp chiếu để giải bài toán bất đẳng thức biến phân, nhờ đó khắc phục được trở ngại cơ bản trong phương pháp chiếu là sự khó khăn khi phải tính hình chiếu của một điểm lên một miền lồi bất kỳ. Trong Thuật toán 2, tại bước lặp thứ k ta giải bài toán biến phân VIP(K,f (tk)). Vì miền ràng buộc của bài toán này có hình dạng đặc biệt, ta có thể giải nó bằng cách sử dụng các phương pháp chiếu, chẳng hạn, sử dụng phương pháp chiếu hai lần đã giới thiệu ở trên. Chọn các tham số tk một cách thích hợp ở mỗi bước, dãy nghiệm của các bài toán phạt VIP(K,f (tk)) sẽ hội tụ về một nghiệm của bài toán ban đầu VIP(D,f) khi tk → t∗. Đây là ý tưởng cơ bản của thuật toán mô tả dưới đây. Xét bài toán bất đẳng thức biến phân VIP(D,f) với D là tập con lồi đóng khác rỗng của Rn. Giả sử f là một ánh xạ liên tục và đơn điệu trên một miền lồi đóng K ⊃ D. Thuật toán kết hợp bao gồm hai bước chính 23 sau. Bước 1: Dùng phương pháp hàm phạt chuyển VIP(D,f) về một dãy bài toán trên miền K ⊃ D, VIP(K,f (t)), trong đó P là một hàm lồi khả vi trên K và thỏa mãn P (x) ≤ 0 khi và chỉ khi x ∈ D. Bước 2: Giải bài toán VIP(K,f (t)) bằng một trong các phương pháp chiếu [15]. Theo tính chất của hàm lồi, P khả vi nên cũng khả vi liên tục (xem Hệ quả 25.5.1, [45]), do đó ∇P cũng liên tục. Nếu ta giả sử thêm f và ∇P liên tục Lipschitz và f là đơn điệu, ta sẽ có f (t) := tf +∇P (t > 0) cũng đơn điệu và liên tục Lipschitz, cho nên ta có thể sử dụng phương pháp chiếu hai lần để giải VIP(K,f (t)). Thuật toán kết hợp được mô tả chi tiết dưới đây. Thuật toán 3 Xây dựng một tập lồi đóng K ⊃ D có hình dạng đặc biệt (chẳng hạn, hình hộp, hình cầu, hoặc không gian con) và một hàm phạt lồi P thỏa mãn các điều kiện trong Bổ đề 1.4.1. Lấy một số dương tùy ý t0 > 0. Chọn εk > 0, sao cho εk → 0 khi k →∞. Đặt a = 0, b =∞ và chuyển sang Bước k với k = 0. Bước k (k = 0, 1, . . .): • Bước k0: Chọn các hằng số λ > 0, η ∈ (0; 1/Ltk), trong đó Ltk là hằng số Lipschitz của f (tk). Đặt j := 0, chọn điểm xuất phát y0 ∈ K. • Bước k1: a) Nếu ||y(j) − PK(y(j) − λf (tk)(y(j)))|| ≤ εk, đặt x(k) := y(j). Xét hai trường hợp sau. 24 a1) Nếu x(k) ∈ D, đặt a := tk và tk+1 := (a+ b)/2, b <∞,2a, b =∞. Chuyển sang Bước k với k := k + 1. a2) Nếu x(k) /∈ D, đặt b := tk và tk := (a+b)/2. Đặt k := k+1 và quay lại Bước k. b) Nếu ||y(j) − PK(y(j) − λf (tk)(y(j)))|| > εk, chuyển sang Bước k2. • Bước k2: Tính y(j+1/2) := PK(y (j) − ηf (tk)(y(j))), y(j+1) := PK(y (j) − ηf (tk)(y(j+1/2))). Gán j := j + 1 và quay lại Bước k1. Trên đây PK(x) là hình chiếu của x lên K. Khi K có hình dạng đặc biệt, ta có thể tính PK(x) dễ dàng nhờ vào một công thức hiển (xem phần 1.2). Từ Định lý 1.3.1 và Định lý 1.4.2, vì εk → 0, ta có kết quả sau. 1.5.1 Định lí. Giả sử f là một ánh xạ đơn điệu trên miền lồi đóng K ⊃ D, P là một hàm phạt lồi khả vi của D. Hơn nữa giả sử P bị chặn dưới trên K, f và ∇P liên tục Lipschitz trên K. Gọi {x(k)} là dãy sinh bởi Thuật toán 3. Khi đó, một điểm giới hạn bất kỳ của {x(k)} là nghiệm của bài toán ban đầu VIP(D,f). Chứng minh. Không giảm tổng quát, vì nếu cần cho qua dãy con, ta có thể giả sử x (k) ∗ → x∗, 25 và x(k) → x¯, khi k → +∞. Theo Định lý 1.4.2 ta có x∗ là một nghiệm của bài toán ban đầu VIP(D,f). Mặt khác, theo phương pháp chiếu hai lần và do εk > 0 nên vòng lặp j sẽ kết thúc sau một số hữu hạn bước và tại bước lặp cuối cùng của vòng lặp j, ta có y(j) = x(k) thỏa mãn ‖x(k) − x(k)∗ ‖ ≤ εk. Qua giới hạn, do x (k) ∗ → x∗, x(k) → x¯, và εk → 0, ta được ‖x∗ − x¯‖ ≤ 0. Từ đó suy ra x¯ = x∗. Do x∗ là nghiệm của VIP(D,f), x¯ cũng là một nghiệm của VIP(D,f). 1.6 Ví dụ 1.6.1 Ví dụ. Xét D = {x ∈ Rn : g(x) ≤ 0} ∩K, trong đó K = {x = (x1, x2, . . . , xn)T ∈ Rn : 0 ≤ xi ≤ ai , i = 1, 2, . . . , n}, ai = 5 + i 3i− 1, g(x) = 1 n2 ∑ i exi − e 5 + n− 1 n2 . 26 Dễ thấy g(x) là một hàm lồi trên Rn. Chọn hàm P (x) ≡ g(x) trên Rn. Khi đó, P (x) ≤ 0, x ∈ D,P (x) > 0, x ∈ K \D. Ta sẽ bao D bởi K, do đó P là một hàm phạt của D. Hơn nữa, ∇P (x) = 1 n2 (ex1, ex2, . . . , exn)T . Do đó, ∇P (x) liên tục Lipschitz trên D với hằng số Lipschitz e6/n2. Ngoài ra, dễ thấy ∇P (x) còn đơn điệu mạnh với hằng số đơn điệu 1/n2. Do đó nếu f đơn điệu thì f (t) sẽ đơn điệu mạnh. Ánh xạ f được lấy theo mô hình Nash ([28]). f(x) = H(x)− p(σx)e− p′(σx)x, trong đó e = (1, . . . , 1)T ∈ Rn, σx = 〈x, e〉 = ∑ j xj, H(x) = (α1x1 + β1, . . . , αnxn + βn) T , với αi, βi, i = 1, . . . , n lấy ngẫu nhiên trong khoảng [0, 10]. Hàm p(t) được cho bởi p(t) = γ t+ 1 , trong đó γ lấy ngẫu nhiên trong khoảng [0, 15]. Ta có f chọn như trên là ánh xạ đơn điệu (tham khảo [28]). Ngoài ra, f liên tục Lipschitz với hằng số Lipschitz Ln = √ 2(α2 + 4n2γ2), trong đó α = max i αi. 27 Thật vậy, giả sử f = (f1, f2, . . . , fn), ta có fi(x) = αixi + βi − γ 1 + ∑ j xj + γxi (1 + ∑ j xj) 2 . Do đó fi(x)− fi(y) = αi(xi − yi) + γ ( 1 1 + ∑ j yj − 1 1 + ∑ j xj + xi (1 + ∑ j xj) 2 − yi (1 + ∑ j yj) 2 ) . Đặt N = 1 1 + ∑ j yj − 1 1 + ∑ j xj , Ni = xi (1 + ∑ j xj) 2 − yi (1 + ∑ j yj) 2 , và Mi = N +Ni. Ta có fi(x)− fi(y) = αi(xi − yi) + γMi. Do đó ( fi(x)− fi(y) )2 ≤ 2((αi(xi − yi))2 + (γMi)2). (1.6) Ta có M2i = (N +Ni) 2 ≤ 2(N2 +N2i ). (1.7) N2 = (∑ j(xj − yj) )2( (1 + ∑ j yj)(1 + ∑ j xj) )2 ≤ n ∑ j(xj − yj)2 1 = n‖x− y‖2. (1.8) Ta ước lượng N2i = ( xi (1 + ∑ j xj) 2 − yi (1 + ∑ j yj) 2 )2 . 28 Đặt ϕi(x) = xi (1 + ∑ r xr) 2 . Theo công thức số gia hữu hạn, tồn tại c ∈ [x,y] sao cho ϕi(x)− ϕi(y) = ∑ j ∂ϕi ∂xj (c)(xj − yj). Do đó N2i = ( ϕi(x)− ϕi(y) )2 = (∑ j ∂ϕi ∂xj (c)(xj − yj) )2 , trong đó ∂ϕi ∂xj (c) =  −2ci (1 + ∑ r cr) 3 =: Pi, j 6= i, 1 + ∑ r cr − 2ci (1 + ∑ r cr) 3 =: Qi, j = i. Ta suy ra N2i = ( Pi ∑ j 6=i (xj − yj) +Qi(xi − yi) )2 ≤ ( |Pi| ∑ j 6=i |xj − yj|+ |Qj||xi − yi| )2 . Hơn nữa, vì ci ≥ 0 ta có |Pi| = ∣∣∣ −2ci (1 + ∑ j cj) 3 ∣∣∣ = 2ci (1 + ∑ j cj) 3 ≤ 2ci (1 + ∑ j cj) 2 ≤ 2ci 2 ∑ j cj ≤ 1. 29 Bây giờ xét |Qi| = |1 +∑j cj − 2ci| (1 + ∑ j cj) 3 . Nếu ci ≤ 1, ta có |Qi| = (1− ci) + ∑ j 6=i cj (1 + ∑ j cj) 3 ≤ 1 + ∑ j cj (1 + ∑ j cj) 3 = 1 (1 + ∑ j cj) 2 ≤ 1. Nếu ci > 1, ta có (1 + ∑ j cj) 3 > (1 + ∑ j cj) 2 = 1 + 2 ∑ j cj + ( ∑ j cj) 2 ≥ 1 + 3 ∑ j cj = |1 + ∑ j cj|+ |2 ∑ j cj| ≥ |1 + ∑ j cj|+ |2ci| ≥ |1 + ∑ j cj − 2ci|. Do đó trong trường hợp này ta cũng có |Qi| ≤ 1. Tóm lại ta luôn có |Pi| ≤ 1, 30 và |Qi| ≤ 1. Do vậy, N2i ≤ (∑ j 6=i |xj − yj|+ |xi − yi| )2 = (∑ j |xj − yj| )2 ≤ n ∑ j |xj − yj|2 = n‖x− y‖2. (1.9) Kết hợp (1.6), (1.7), (1.8), và (1.9) ta có( fi(x)− fi(y) )2 ≤ 2(α2i (xi − yi)2 + γ2M2i ) ≤ 2(α2i (xi − yi)2 + 2γ2(N2 +N2i ) ≤ 2(α2i (xi − yi)2 + 2γ2(n‖x− y‖2 + n‖x− y‖2)) = 2 ( α2i (xi − yi)2 + 4nγ2‖x− y‖2 ) . Cuối cùng ta có ‖f(x)− f(y)‖2 = ∑ i ( fi(x)− fi(y) )2 ≤ 2 (∑ i α2i (xi − yi)2 + 4nγ2 ∑ i ‖x− y‖2 ) ≤ 2(α2‖x− y‖2 + 4n2γ2‖x− y‖2) = 2(α2 + 4n2γ2)‖x− y‖2, trong đó α = max i αi. Như vậy, ‖f(x)− f(y)‖ ≤ Ln‖x− y‖, 31 trong đó Ln = √ 2(α2 + 4n2γ2). Như vậy, ví dụ này thỏa mãn các giả thiết của Định lý 1.5.1. Do đó, dãy sinh bởi Thuật toán 3 có tính chất bất kỳ điểm giới hạn nào của dãy đó đều là một nghiệm của bài toán ban đầu. Chúng tôi đã cài đặt Thuật toán 3 dùng ngôn ngữ C và kết quả số được mô tả dưới đây. Sai số cho phép của thuật toán chiếu là ε = 10−6. Bảng I γ\n 5 10 20 5 [15 - 18] - 1s [15 - 28] - 1s [13 - 24] - 8s 10 [17 - 25] - 1s [15 - 25] - 3s [10 - 24] - 9s 15 [19 - 25] - 2s [14 - 24] - 5s [14 - 22] - 12s Bảng II γ\n 30 40 50 5 [13 - 15] - 10s [15 - 25] - 28s [10 - 24] - 70s 10 [15 - 22] - 50s [12 - 22] - 60s [13 - 21] - 210s 15 [17 - 22] - 90s [13 - 21] - 225s [13 - 20] - 420s Dữ liệu trong hai bảng trên được đọc như sau. Chẳng hạn lấy ô nằm ở hàng 3, cột 3, bảng 1, tương ứng với n = 10 và γ = 10 : thuật toán chạy mất 3 giây để đến được vòng lặp thứ 25 (giải hết bài toán phạt thứ 25), trong đó, các vòng lặp từ 15 đến 25 cho cùng một nghiệm xk (tính đến 6 chữ số thập phân). Ta xét hai ví dụ tiếp theo, trong đó hàm phạt P sẽ được lấy theo công thức (1.4). Xét D = {x = (x1, x2)T ∈ R2 : g1(x) ≤ 0, g2(x) ≤ 0}, 32 trong đó g1(x) = x2− x1− 1, g2(x) = −x2 + x21− 1 là các hàm lồi trên R2. Bây giờ ta xét hai ví dụ ứng với hai ánh xạ f khác nhau. 1.6.2 Ví dụ. Giả sử f(x) = ( x1 + x2 x2 + e x2 4 − 1 ) . Có thể nhận thấy (0, 0)T là một nghiệm của bài toán trên và là nghiệm duy nhất, do f đơn điệu mạnh. Ta lấy P theo (1.4). P (x) = [max{0, x2 − x1 − 1}]2 + [max{0,−x2 + x21 − 1}]2 =  0, x ∈ D, (x2 − x1 − 1)2, x ∈ (I), (x2 − x1 − 1)2 + (−x2 + x21 − 1)2, x ∈ (II), (−x2 + x21 − 1)2, x ∈ (III). Chú ý rằng D là miền nằm dưới đường thẳng x2 = x1 + 1 và nằm trên đường cong x2 = x 2 1 − 1, (I) là miền nằm trên cả đường thẳng và đường cong, (II) nằm trên đường thẳng và dưới đường cong, (III) nằm dưới cả đường thẳng và đường cong. Hai giao điểm của đường thẳng và đường cong là (−1, 0) và (2, 3). Do 33 đó có thể bao D bởi hình hộp K = {x = (x1, x2) ∈ R2 : −1 ≤ x1 ≤ 2, −1 ≤ x2 ≤ 3}. Không khó để thấy rằng f liên tục Lipschitz trên K với hằng số Lipschitz l = √ 4.4, do đó tf (t > 0) liên tục Lipschitz với hằng số Lipschitz lt = t √ 4.4. Hơn nữa, f đơn điệu mạnh trên K với hằng số đơn điệu α = 1 2 . Do đó tf (t > 0) có hằng số đơn điệu αt = t 2 . Ta có ∇P (x) =  0 0  , x ∈ D,−2(x2 − x1 − 1) 2(x2 − x1 − 1)  , x ∈ (I),−2(x2 − x1 − 1) + 4x1(−x2 + x21 − 1) 2(x2 − x1 − 1)− 2(−x2 + x21 − 1)  , x ∈ (II),4x1(−x2 + x21 − 1) −2(−x2 + x21 − 1)  , x ∈ (III) liên tục Lipschitz trên K với hằng số Lipschitz 69. Do đó f (t) liên tục Lipschitz trên K với hằng số Lipschitz Lt = 69 + t √ 4.4, 34 và có hằng số đơn điệu αt = t 2 . Trước hết, ta dùng phương pháp hàm phạt đưa bài toán trên về dãy các bài toán VIP(K,f (t)). Với mỗi t > 0, áp dụng phương pháp chiếu hai lần, ta chọn độ dài bước η thỏa mãn 0 < η < 1 Lt = 1 69 + t √ 4.4 . Do đó, có thể chọn η = 0.9t 69 + t √ 4.4 . Dùng Thuật toán 3, với độ chính xác (của thuật toán chiếu) 10−12, t0 = 1, ngay từ vòng lặp đầu tiên (của thuật toán phạt), với kết quả lấy đến 9 chữ số thập phân, ta được kết quả (0, 0)T . Có thể nhận thấy tk tiến ra ∞ nhanh chóng và kết quả ở mỗi bước lặp (của thuật toán phạt) đều cho ra nghiệm (0, 0)T (đúng đến 10 hoặc 11 chữ số thập phân). Chương trình chạy tới vòng lặp thứ 1000 chỉ sau 3 giây. Kết quả trên được giải thích như sau. Do ∇P ≡ 0 trên D (P chọn theo (1.4), nên nếu nghiệm của VIP(K,f (t)) nằm trong D thì đó cũng là nghiệm của bài toán ban đầu VIP(D,f). Trong trường hợp t∗ = ∞, vì t0 0, nên theo Bổ đề 1.4.1, S(t0) ⊂ D. Do đó, nghiệm của bài toán phạt ứng với t0 cũng chính là nghiệm của bài toán ban đầu. Điều đó giải thích tại sao nghiệm của bài toán ban đầu lại được tìm ra ngay sau bước lặp đầu tiên. 1.6.3 Ví dụ. Lấy f(x) = ( x1 + x2 + 10 x2 + e x2 + 10 ) . Chú ý rằng ở đây f không có nghiệm trên miền D. Tuy vậy, f vẫn đơn điệu mạnh và liên tục Lipschitz với cùng hằng số như ở ví dụ trước. Với 35 độ chính xác (của phương pháp chiếu) là 10−10, t0 = 1, x(0) = (1, 1)T , sau đây là kết quả của vòng lặp 24 đến vòng lặp 28. Bảng III Số bước lặp k x(k) tk 889881606 24 (−0.437337405102318,−0.808736590634006)T 0.0000001192 1779680342 25 (−0.437337404356388,−0.808736293018647)T 0.0000000596 3560253327 26 (−0.437337403855591,−0.808736144322769)T 0.0000000298 7128665016 27 (−0.437337403701826,−0.808736069890305)T 0.0000000149 14205655551 28 (−0.437337403325762,−0.808736032935760)T 0.0000000075 Cột đầu tiên cho biết số bước lặp mà thuật toán chiếu thực hiện để giải bài toán phạt. Có thể thấy là tk → 0, nghĩa là t∗ = 0. Trong trường hợp t∗ = 0, từ Bổ đề 1.4.1, nghiệm x(k) của bài toán phạt ứng với tk luôn nằm ngoài miền D và một điểm giới hạn bất kỳ của một dãy {x(k)} với x(k) ∈ S(tk) và tk → t∗ là một nghiệm của VIP(D,f). Có thể nhận thấy là nghiệm của những bước cuối cùng xấp xỉ thuộc miền D với sai số khoảng 10−8, nhưng vẫn nằm ngoài D. Điều này phù hợp với kết luận của Bổ đề 1.4.1. Kết luận Chương 1 Trong chương này, luận án đã giải quyết được những vấn đề sau. - Kết hợp phương pháp hàm phạt và phương pháp chiếu để đưa ra một thuật toán hoàn chỉnh giải bài toán bất đẳng thức biến phân VIP(D,f), với f là ánh xạ đơn điệu và liên tục Lipschitz, D là một miền lồi đóng khác rỗng của Rn. Với phương pháp này, trở ngại chính của phương pháp chiếu được khắc phục. - Áp dụng thuật toán này cho một số ví dụ cụ thể để minh họa các kết quả đã có trong phần lý thuyết. CHƯƠNG 2 HÀM PHẠT CHO BÀI TOÁN BẤT ĐẲNG THỨC BIẾN PHÂN VECTOR YẾU Phương pháp hàm phạt thường được sử dụng để đưa một bài toán có ràng buộc, gọi là bài toán ban đầu, về một dãy các bài toán không ràng buộc, gọi là các bài toán phạt, sao cho một dãy nghiệm của các bài toán phạt hội tụ về một nghiệm của bài toán ban đầu. Đã có nhiều nghiên cứu về cách thức áp dụng phương pháp hàm phạt để giải các bài toán bất đẳng thức biến phân (tham khảo chẳng hạn [38, 23, 39, 1, 51]). Tuy nhiên, theo hiểu biết của chúng tôi, cho tới nay chưa có công trình nghiên cứu nào về việc áp dụng phương pháp hàm phạt cho bài toán bất đẳng thức biến phân vector yếu. Trong chương này chúng tôi nghiên cứu mối quan hệ giữa tập nghiệm S(t) của bài toán phạt WVVIP(K,F (t)), khi t→ +∞, với tập nghiệm S của bài toán ban đầu WVVIP(D,F ). Chúng tôi chứng minh được rằng với một số giả thiết nhất định, các bài toán phạt luôn có ít nhất một nghiệm. Hơn nữa, một dãy nghiệm của các bài toán phạt luôn có ít nhất một điểm giới hạn và một điểm giới hạn bất kỳ của dãy này sẽ là nghiệm của bài toán ban đầu WVVIP(D,F ). Các ký hiệu, định nghĩa sau đây sẽ được sử dụng trong hai chương còn lại của luận án. Với x = (x1, . . . , xk) T ∈ Rk, 36 37 và y = (y1, . . . , yk) T ∈ Rk, ta dùng các ký hiệu sau x < y⇐⇒xi < yi, ∀i = 1, . . . , p, x 6< y⇐⇒∃i : xi ≥ yi. Tích vô hướng của x và y định nghĩa như sau 〈x,y〉 = k∑ i=1 xiyi. Với mỗi y = (y1, . . . , yk) T ∈ Rk, ký hiệu ‖y‖ là chuẩn Euclide của y, tức là ‖y‖ = √√√√ k∑ i=1 y2i . Ký hiệu Rk+ = {x = (x1, . . . , xk)T ∈ Rk : xi ≥ 0, i = 1, . . . , k}. Giả sử D là một tập con khác rỗng của Rk. Giả sử F : Rk → Rr×k là một ánh xạ liên tục với miền giá trị là một tập các ma trận thực kích thước r×k. Bài toán bất đẳng thức biến phân vector yếu với ràng buộc trên D được định nghĩa như sau WVVIP(D,F ) : Tìm x ∈ D sao cho F (x)(y − x) 6< 0,∀y ∈ D. Nếu D = Rk, WVVIP(D,F ) được gọi là một bài toán bất đẳng thức biến phân vector yếu không ràng buộc. Bài toán WVVIP(D,F ) dĩ nhiên là một trường hợp tổng quát của bài toán VIP(D,f) xét ở Chương 1 vì khi r = 1 nó trở thành bài toán bất 38 đẳng thức biến phân vô hướng. Hơn nữa bài toán bất đẳng thức biến phân vector yếu bao hàm nhiều bài toán quan trọng khác như một trường hợp riêng, trong đó có bài toán tối ưu vector lồi. Về bài toán bất đẳng thức biến phân vector yếu có thể tham khảo các tài liệu [16, 6, 4, 3, 31, 12, 17]. Gọi F i : Rk → Rk, i = 1, . . . , r là các ánh xạ thành phần của F , nghĩa là F i(x) là hàng thứ i của ma trận F (x). Ta có F (x)(y − x) = (〈F 1(x),y − x〉, . . . , 〈F r(x),y − x〉)T . Do đó x ∈ D là một nghiệm của WVVIP(D,F ) nếu và chỉ nếu với mọi y ∈ D ta có (〈F 1(x),y − x〉, . . . , 〈F r(x),y − x〉)T 6< 0, hay nói cách khác là tồn tại chỉ số i sao cho 〈F i(x),y − x〉 ≥ 0. 2.1 Điều kiện đủ cho sự tồn tại nghiệm của bài toán bất đẳng thức biến phân vector yếu Chúng tôi nhắc lại một điều kiện đủ cho sự tồn tại nghiệm của bài toán bất đẳng thức biến phân vector yếu được đưa ra trong [6]. Trước hết chúng ta cần một vài định nghĩa. 2.1.1 Định nghĩa ([6]). Ánh xạ F : Rk → Rr×k được gọi là đơn điệu trên Rk nếu với mọi x,y ∈ Rk ta có (F (y)− F (x))(y − x) ≥ 0, hay nói cách khác, các ánh xạ thành phần F i đều đơn điệu, nghĩa là 〈F i(y)− F i(x),y − x〉 ≥ 0, với mọi i = 1, . . . , r. 39 2.1.2 Định nghĩa ([6]). Ánh xạ F : Rk → Rr×k được gọi là thỏa mãn điều kiện bức yếu trên D ⊂ Rk nếu tồn tại s ∈ Rr+ và a ∈ D sao cho 〈sTF (y),y − a〉 → +∞ khi ‖y‖ → +∞, y ∈ D. Chen và Yang [6] đã đưa ra điều kiện đủ sau đây cho sự tồn tại nghiệm của WVVIP(D,F ). 2.1.3 Định lí ([6]). Giả sử D 6= ∅ là một tập con lồi đóng của Rk, và F : Rk → Rr×k là một ánh xạ liên tục và đơn điệu trên Rk. Giả sử rằng 1. D bị chặn, hoặc 2. F thỏa mãn điều kiện bức yếu trên D. Khi đó WVVIP(D,F ) có nghiệm. 2.2 Bài toán phạt Trong mục này ta xây dựng các bài toán phạt và thiết lập điều kiện đủ để các bài toán đó có nghiệm. Trước hết, ta có định nghĩa sau đây cho hàm phạt ngoài của một tập D ⊂ Rk. 2.2.1 Định nghĩa. Cho D là một tập con khác rỗng của Rk. Hàm P : Rk → R được gọi là một hàm phạt (ngoài) của D nếu nó thỏa mãnP (x) = 0, x ∈ D,P (x) > 0, x /∈ D. (2.1) Ta luôn chọn P sao cho P không những là hàm lồi mà còn khả vi. Ví dụ, nếu D được cho bởi D = {x ∈ Rk : gj(x) ≤ 0, j = 1, . . . ,m}, (2.2) 40 trong đó gj : Rk → R, j = 1, . . . ,m là các hàm liên tục, ta có thể lấy P (x) = m∑ j=1 [ max{0, gj(x)} ]2 . (2.3) Như đã chứng minh trong mục 1.4, P chọn như trên không những lồi và khả vi trên Rk, mà còn thỏa mãn (2.1). Do tính chất của hàm lồi (tham khảo [45], Hệ quả 25.5.1), nếu P là lồi và khả vi thì ∇P (x) liên tục trên Rk. Hơn nữa, 〈∇P (x),y − x〉 ≤ P (y)− P (x), với mọi x và y trong Rk. Ta định nghĩa bài toán phạt như sau. Đặt Qi := ∇P, và Q : Rk → Rr×k, với các hàm thành phần Qi : Rk → Rk, i = 1, . . . , r. Cố định một tập K ⊃ D. Với t > 0 ta xét bài toán phạt sau đây WVVIP(K,F (t)) : Tìm x(t) ∈ K sao cho (F (t)(x(t)))(y − x(t)) 6< 0, với mọi y ∈ K, trong đó F (t) := F + tQ. 2.2.2 Định nghĩa. Ánh xạ f : Rk → Rk được gọi là thỏa mãn điều kiện D-bức trên K nếu tồn tại a ∈ D sao cho 〈f(y),y − a〉 → +∞ khi ‖y‖ → +∞, y ∈ K. 2.2.3 Ví dụ. Ánh xạ F : R2 → R2 cho bởi F (y) = (y1 + y2, y2 + ey2/4 − 1)T , thỏa mãn điều kiện D-bức trên R2 với mọi tập con D chứa 41 gốc tọa độ (0, 0) của R2. Thật vậy, 〈F (y),y − 0〉 = (y1 + y2)y1 + (y2 + ey2/4 − 1)y2 = (y21 + y1y2 + y 2 2) + (e y2/4y2 − y2) → +∞, khi ‖y‖ → +∞. 2.2.4 Định nghĩa. Ánh xạ F : Rk → Rr×k được gọi là thỏa mãn điều kiện D-bức trên K nếu tồn tại s ∈ Rr+ và a ∈ D sao cho 〈sTF (y),y − a〉 → +∞ khi ‖y‖ → +∞, y ∈ K. Hiển nhiên khi r = 1 thì hai định nghĩa trên là như nhau vì ta có thể lấy s = 1. Bổ đề sau đây chỉ ra một điều kiện đủ để cả bài toán ban đầu và bài toán phạt có nghiệm. 2.2.5 Bổ đề. Giả sử D 6= ∅ là một tập con lồi đóng của Rk và F : Rk → Rr×k là một ánh xạ liên tục, đơn điệu và thỏa mãn điều kiện D-bức trên K. Khi đó WVVIP(D,F ) có nghiệm. Hơn nữa, với mọi t > 0, bài toán phạt WVVIP(K,F (t)) cũng có nghiệm. Chứng minh. Vì F thỏa mãn điều kiện D-bức trênK, nó cũng thỏa mãn điều kiện bức yếu trên D nếu D không bị chặn. Do đó theo Định lý 2.1.3, WVVIP(D,F ) có nghiệm. Bây giờ ta chứng minh rằng WVVIP(K,F (t)) cũng có nghiệm. Hiển nhiên F (t) là ánh xạ liên tục. Hơn nữa F (t) đơn điệu trên Rk. Ta cần chứng minh rằng với mọi x,y ∈ Rk, vector (F (t)(y)− F (t)(x))(y − x) có các tọa độ không âm. Thật vậy (F (t)(y)− F (t)(x))(y − x) = (F (y) + tQ(y)− F (x)− tQ(x))(y − x) = (F (y)− F (x))(y − x) + t(Q(y)−Q(x))(y − x). 42 Chú ý rằng số hạng thứ nhất luôn không âm, nghĩa là tất cả các tọa độ của nó đều không âm. Tọa độ thứ i của số hạng thứ hai được biến đổi như sau t〈Qi(y)−Qi(x),y − x〉 = −t〈∇P (y),x− y〉 − t〈∇P (x),y − x〉 ≥ −t(P (x)− P (y))− t(P (y)− P (x)) = 0. Chú ý rằng trong bất đẳng thức thứ hai ta sử dụng giả thiết P là hàm lồi. Do vậy tất cả các tọa độ của số hạng thứ hai đều không âm. Do đó F (t) đơn điệu trên Rk. Chúng ta còn phải chứng minh rằng F (t) thỏa mãn điều kiện bức yếu trên K. Thật vậy, tồn tại s ∈ Rr+ và a ∈ D sao cho 〈sTF (y),y − a〉 → +∞ khi ‖y‖ → +∞,y ∈ K. Ta có 〈sTF (t)(y),y − a〉 = 〈sT (F (y) + tQ(y)),y − a〉 = 〈sTF (y),y − a〉+ t〈sTQ(y),y − a〉. Xét số hạng thứ hai sau khi chia cho t. Vì Q(y)(y − a) = (〈Q1(y),y − a〉, . . . , 〈Qr(y),y − a〉), ta có 〈sTQ(y),y − a〉 = ∑ i si〈Qi(y),y − a〉 = ∑ i si〈∇P (y),y − a〉 ≥ ∑ i si(P (y)− P (a)) = ∑ i siP (y). 43 Tổng cuối cùng là không âm, vì si ≥ 0 và P (y) ≥ 0. Vì F thỏa mãn điều kiện D-bức trên K, ta có 〈sTF (y),y − a〉 → +∞ khi ‖y‖ → +∞,y ∈ K. Do vậy ta suy ra 〈sTF (t)(y),y − a〉 → +∞ khi ‖y‖ → +∞,y ∈ K. Do đó F (t) thỏa mãn điều kiện bức yếu trên K với mọi t > 0. Theo Định lý 2.1.3, bài toán phạt WVVIP(K,F (t)) có nghiệm. 2.2.6 Ví dụ. Ta lấy miền D như trong Ví dụ 1.6.2 D = {x = (x1, x2)T ∈ R2 : x2 − x1 − 1 ≤ 0,−x2 + x21 − 1 ≤ 0}, và K = R2. Hình 2.1: Miền ràng buộc D của WVVIP(D,F ) Lấy P theo (2.3). P (x) = [max{0, x2 − x1 − 1}]2 + [max{0,−x2 + x21 − 1}]2 =  0, x ∈ D, (x2 − x1 − 1)2, x ∈ (I), (x2 − x1 − 1)2 + (−x2 + x21 − 1)2, x ∈ (II), (−x2 + x21 − 1)2, x ∈ (III). 44 Ánh xạ F : R2 → R2×2 được cho bởi F (x) = ( x1 + x2 x2 + e x2/2 − 2 x1 + 2x2 x1 + 3x2 + e x2 − 1 ) . Khi đó với mọi x,y ∈ Rk ta có 〈F 1(y)− F 1(x),y − x〉 = (y1 − x1)2 + (y2 − x2)(y1 − x1) + (y2 − x2)2 + (ey2/2 − ex2/2)(y2 − x2) ≥ 0, và 〈F 2(y)− F 2(x),y − x〉 = (y1 − x1)2 + 3(y2 − x2)(y1 − x1) + 3(y2 − x2)2 + (ey2 − ex2/2)(y2 − x2) ≥ 0. Do đó F đơn điệu trên R2. Hơn nữa F thỏa mãn điều kiện D-bức trên K = R2. Thật vậy, chọn a = 0 ∈ D và s = (1, 1)T , ta có 〈sTF (y),y − a〉 = 〈F 1(y) + F 2(y),y〉 = 2y21 + 4y1y2 + 4y 2 2 + e y2/2y2 + e y2y2 − 3y2 → +∞, khi ‖y‖ → +∞. Như vậy các miền D, K = R2 và ánh xạ F định nghĩa như trên thỏa mãn tất cả các giả thiết của Bổ đề 2.2.5. Do đó, cả WVVIP(D,F ) và WVVIP(K,F (t)) (t > 0) tương ứng với D, K và F này đều có nghiệm. 2.3 Các định lý hội tụ Ký hiệu S và S(t) tương ứng là các tập nghiệm của WVVIP(D,F ) và WVVIP(K,F (t)). Giả sử {tn}n là một dãy số thực dương tăng đơn điệu tới +∞ khi n→ +∞. 45 2.3.1 Bổ đề. Giả sử x(n) ∈ S(tn) với mọi n ∈ N, {x(nm)}m là một dãy con hội tụ của {x(n)}n và limm→+∞ x(nm) = x. Khi đó x ∈ D. Chứng minh. Ta chứng minh bằng phản chứng. Giả sử x 6∈ D, ta có P (x) > 0 và do đó P (x) > ε với ε > 0 nào đó. Lấy y bất kỳ thuộc D. Vì x(nm) là một nghiệm của (WVVIP)tnm , tồn tại chỉ số inm sao cho 〈F (tnm)inm (x(nm)),y − x(nm)〉 ≥ 0. Vì inm ∈ {1, 2, . . . , r}, tồn tại một dãy vô hạn các chỉ số {inmk}k nhận cùng một giá trị, chẳng hạn inmk = 1, với mọi k ∈ N. Để đơn giản hóa ký hiệu ta giả sử inm = 1 với mọi m ∈ N. Do đó với mọi m ∈ N ta có 〈F (tnm)1 (x(nm)),y − x(nm)〉 ≥ 0. (2.4) Mặt khác vì P (x(nm))→ P (x) > ε, với mọi m đủ lớn ta có P (x(nm)) > ε. Do vậy 〈F (tnm)1 (x(nm)),y − x(nm)〉 = 〈F 1(x(nm)),y − x(nm)〉 + tnm〈∇P (x(nm)),y − x(nm)〉 ≤ 〈F 1(x(nm)),y − x(nm)〉 + tnm(P (y)− P (x(nm))) = 〈F 1(x(nm)),y − x(nm)〉 − tnmP (x(nm)) < 〈F 1(x(nm)),y − x(nm)〉 − εtnm → 〈F 1(x),y − x〉 −∞ = −∞, khi m→ +∞. Điều này mâu thuẫn với (2.4). Định lý sau đây chỉ ra rằng nếu một dãy các nghiệm của các bài toán phạt hội tụ về một điểm x thì x là một nghiệm của bài toán ban đầu 46 WVVIP(D,F ). Chú ý rằng nếu tồn tại n ∈ N sao cho x(n) ∈ S(tn)∩D thì dễ thấy x(n) cũng là một nghiệm của WVVIP(D,F ). 2.3.2 Định lí. Giả sử rằng x(n) ∈ S(tn) với mọi n ∈ N. Khi đó một điểm giới hạn bất kỳ của dãy {x(n)}n sẽ là một nghiệm của WVVIP(D,F ). Chứng minh. Giả sử x là một điểm giới hạn của dãy {x(n)}n. Gọi {x(nm)}m là dãy con của {x(n)}n hội tụ về x. Theo Bổ đề 2.3.1, ta có x ∈ D. Giả sử phản chứng rằng x không phải là nghiệm của WVVIP(D,F ). Khi đó tồn tại y ∈ D thỏa mãn 〈F i(x),y − x〉 < 0 với mọi i = 1, . . . , r. Vì x(nm) là một nghiệm của (WVVIP)tnm , với y nói trên, tồn tại một chỉ số inm thỏa mãn 〈F (tnm)inm (x(nm)),y − x(nm)〉 ≥ 0. Vì inm ∈ {1, 2, . . . , r}, tồn tại một dãy vô hạn các chỉ số {inmk}k nhận cùng một giá trị, chẳng hạn inmk = 1, với mọi k ∈ N. Để đơn giản hóa ký hiệu ta giả sử rằng dãy {inm}m tự nó thỏa mãn tính chất này, nghĩa là inm = 1 với mọi m ∈ N. Do vậy với mọi m ∈ N ta có 〈F (tnm)1 (x(nm)),y − x(nm)〉 ≥ 0. (2.5) Vì 〈F 1(x),y − x〉 < 0, ta suy ra rằng 〈F 1(x),y − x〉 < −ε, với ε > 0 nào đó. Sử dụng tính liên tục của F và giả thiết x(nm) → x, ta suy ra với mọi m đủ lớn〈 F 1(x (nm)),y − x(nm) 〉 < −ε. Do đó, sử dụng tính chất P (x(nm)) ≥ 0, 47 và tnm > 0, với mọi m ∈ N, với mọi m đủ lớn ta có 〈F (tnm)1 (x(nm)),y − x(nm)〉 = 〈 F 1(x (nm)),y − x(nm) 〉 + tnm 〈 ∇P (x(nm)),y − x(nm) 〉 ≤ 〈 F 1(x (nm)),y − x(nm) 〉 + tnm(P (y)− P (x(nm))) = 〈 F 1(x (nm)),y − x(nm) 〉 − tnmP (x(nm)) < −ε. Điều này mâu thuẫn với (2.5). 2.3.3 Định nghĩa. Ánh xạ F : Rk → Rr×k được gọi là thỏa mãn điều kiện D-bức mạnh trên K nếu tất cả các ánh xạ thành phần của nó thỏa mãn điều kiện D-bức trên K với cùng một vector a, nghĩa là tồn tại a ∈ D sao cho với mọi j = 1, . . . , r, 〈F j(y),y − a〉 → +∞, khi ‖y‖ → +∞,y ∈ K. Dễ thấy với ánh xạ F và các miền D và K = R2 định nghĩa trong Ví dụ 2.2.6 thì F thỏa mãn điều kiện D-bức mạnh trên K. Hiển nhiên nếu F thỏa mãn điều kiện D-bức mạnh trên K, thì F cũng thỏa mãn điều kiện D-bức trên K. Tuy nhiên, điều ngược lại không phải lúc nào cũng đúng. Ví dụ, xét miền D = {0}, K = R2, và F (x) = ( x1 + x2 x2/4 x1 x2 ) . 48 Chọn s = (1, 1)T . Vì 〈sTF (y),y − 0〉 = 〈F 1(y) + F 2(y),y〉 = 2y21 + y1y2 + 5 4 y22 → +∞, khi ‖y‖ → +∞, ta kết luận rằng F thỏa mãn điều kiện D-bức trên R2. Mặt khác, vì 〈F 1(y),y − 0〉 = (y1 + y2/2)2 = 0, với mọi y = (y1,−2y1)T , với y1 → +∞, ta suy ra F 1 thậm chí không thỏa mãn điều kiện D-bức trên R2. Do vậy F thỏa mãn điều kiện D-bức trên R2, nhưng không thỏa mãn điều kiện D-bức mạnh trên R2. 2.3.4 Định lí. Cho D 6= ∅ là một tập con lồi đóng của Rk và F : Rk → Rr×k là một ánh xạ liên tục, đơn điệu, đồng thời thỏa mãn điều kiện D-bức mạnh trên K. Giả sử x(n) ∈ S(tn) với mọi n ∈ N. Khi đó dãy {x(n)}n có ít nhất một điểm giới hạn và bất kỳ một điểm giới hạn nào của dãy này là một nghiệm của WVVIP(D,F ). Chứng minh. Chú ý rằng vì F cũng thỏa mãn điều kiện D-bức trên K, theo Bổ đề 2.2.5, S(tn) 6= ∅ với mọi n ∈ N, do đó dãy {x(n)}n nêu trong định lý được xác định đúng đắn. Ta sẽ chứng minh rằng dãy {x(n)}n bị chặn, nghĩa là tồn tại một hình cầu B nào đó với bán kính hữu hạn, có tâm là gốc tọa độ, sao cho x(n) ∈ B với mọi n ∈ N. Giả sử a là vector hằng trong Định nghĩa 2.3.3. Với mỗi t > 0, gọi B(t) là hình cầu đóng bé nhất, tâm tại gốc tạo độ 0, thỏa mãn tính chất sau: với mọi y /∈ B(t) và mọi j = 1, . . . , r, ta có 〈F (t)j (y),y − a〉 > 0, hay nói cách khác, 〈F j(y),y − a〉+ t〈∇P (y),y − a〉 > 0. 49 Vì mỗi F j thỏa mãn điều kiện D-bức trên K và 〈∇P (y),y − a〉 ≥ P (y)− P (a) = P (y) ≥ 0, ta suy ra với mọi t > 0, B(t) có bán kính hữu hạn. Ta sẽ chứng minh bằng phản chứng rằng S(t) ⊆ B(t) với mọi t > 0. Thật vậy, giả sử y ∈ S(t)\B(t), khi đó theo định nghĩa của B(t), với mọi j = 1, . . . , r ta có 〈F (t)j (y),y − a〉 > 0. Từ đó ta suy ra 〈F (t)j (y),a−y〉 < 0 với mọi j = 1, . . . , r. Điều này mâu thuẫn với giả thiết y ∈ S(t). Mặt khác ta sẽ chứng minh rằng nếu t′ > t, thì B(t′) ⊆ B(t). Thật vậy, với mọi y /∈ B(t), ta có 〈F j(y),y − a〉+ t〈∇P (y),y − a〉 > 0, kéo theo 〈F j(y),y − a〉+ t′〈∇P (y),y − a〉 > 0, (2.6) với mọi j = 1, . . . , r. Theo định nghĩa B(t′) là hình cầu nhỏ nhất thỏa mãn tính chất: với mọi y /∈ B(t′) bất đẳng thức (2.6) được thỏa mãn. Do đó B(t′) bị chứa trong B(t). Cuối cùng, vì {tn}n là dãy đơn điệu tăng ta có B(t1) ⊇ B(t2) ⊇ · · · ⊇ B(tn) ⊇ · · · Do đó, với mọi n ∈ N, x(n) ∈ S(tn) ⊆ B(tn) ⊆ B(t1). Vì B(t1) có bán kính hữu hạn, ta kết luận rằng dãy {x(n)}n bị chặn. Do vậy, theo nguyên lý Bolzano-Weierstrass dãy này có ít nhất một điểm giới hạn. Khẳng định rằng mỗi điểm giới hạn của {x(n)}n là một nghiệm của WVVIP(D,F ) được suy ra trực tiếp từ Định lý 2.3.2. 50 Kết luận Chương 2 Trong chương này, luận án đã giải quyết được những vấn đề sau. - Xây dựng mô hình bài toán phạt cho bài toán bất đẳng thức biến phân vector yếu và chứng minh rằng một điểm giới hạn bất kỳ của một dãy các nghiệm của các bài toán phạt chính là một nghiệm của bài toán ban đầu. - Chứng minh được rằng nếu miền D là lồi đóng, ánh xạ F đơn điệu và thỏa mãn tính chất bức, thì các bài toán phạt đều có nghiệm. Hơn nữa, bất kỳ dãy nghiệm nào của các bài toán phạt đều bị chặn, do đó có ít nhất một điểm giới hạn, và đó chính là một nghiệm của bài toán bất đẳng thức biến phân vector yếu ban đầu. CHƯƠNG 3 HÀM PHẠT CHO BÀI TOÁN TỐI ƯU ĐA MỤC TIÊU Phương pháp hàm phạt áp dụng cho bài toán tối ưu phi tuyến đã được nghiên cứu một cách khá kỹ lưỡng (tham khảo chẳng hạn [56, 14, 43, 7]). Phương pháp hàm phạt áp dụng cho bài toán tối ưu đa mục tiêu cũng đã được nghiên cứu trong một vài công trình gần đây (tham khảo [52, 21, 22, 34]). Trong [34], Liu và Feng đã chứng minh rằng nếu x là một điểm giới hạn của một dãy các nghiệm Pareto yếu của các bài toán phạt và x chấp nhận được (nghĩa là x ∈ D), thì x là một nghiệm Pareto yếu của bài toán ban đầu. Tính chấp nhận được của x là một giả thiết trong các kết quả của [34]. Trong chương này, chúng tôi sử dụng hàm phạt ngoài và chứng minh được các kết quả sau: (1) nếu x là một điểm giới hạn của một dãy các nghiệm Pareto yếu của các bài toán phạt thì x là chấp nhận được; (2) một điểm x như thế sẽ là một nghiệm của bài toán ban đầu; (3) với một số giả thiết đặt lên f , mọi bài toán phạt sẽ có ít nhất một nghiệm Pareto yếu và mỗi dãy nghiệm Pareto yếu của các bài toán phạt sẽ có ít nhất một điểm giới hạn, điểm giới hạn đó chính là một nghiệm của bài toán tối ưu đa mục tiêu ban đầu. 51 52 3.1 Điều kiện đủ cho sự tồn tại nghiệm của bài toán tối ưu đa mục tiêu Cho D là một tập con lồi đóng khác rỗng của Rk. Ta xét bài toán tối ưu đa mục tiêu với ràng buộc trên D sau đây MOP(D,f) : min x∈D f(x) = (f1(x), . . . , fr(x)), trong đó fi : Rk → R, i = 1, . . . , r là các ánh xạ xác định trên Rk. D được gọi là miền ràng buộc của MOP(D,f). Nếu x ∈ D thì x được gọi là một điểm chấp nhận được của MOP(D,f). Nếu D = Rk thì MOP(D,f) được gọi là bài toán tối ưu đa mục tiêu không ràng buộc. 3.1.1 Định nghĩa. Vector x ∈ D được gọi là một nghiệm Pareto yếu của MOP(D,f) nếu không tồn tại y ∈ D nào thỏa mãn f(y) < f(x). Do đó, x ∈ D là một nghiệm Pareto yếu MOP(D,f) nếu và chỉ nếu với mọi y ∈ D luôn tồn tại một chỉ số i sao cho fi(y) ≥ fi(x). Định lý sau đây thiết lập mối quan hệ giữa nghiệm Pareto yếu của một bài toán tối ưu đa mục tiêu và nghiệm của bài toán bất đẳng thức biến phân vector yếu tương ứng, dựa trên giả thiết về tính lồi và khả vi của hàm mục tiêu. 3.1.2 Định lí ([5]). Giả sử f là một ánh xạ lồi và khả vi, nghĩa là mỗi ánh xạ thành phần fi của f là lồi và khả vi. Khi đó x là một nghiệm Pareto yếu của MOP(D,f) nếu và chỉ nếu x là một nghiệm của WVVIP(D,f ′), trong đó f ′ là đạo hàm của f . Các kết quả sau đây về sự tồn tại nghiệm của bài toán tối ưu đa mục tiêu sẽ được sử dụng về sau trong chương này. 53 3.1.3 Định lí ([30]). Giả sử f lồi và khả vi. Hơn nữa giả sử rằng D không bị chặn và tồn tại a ∈ D sao cho lim ‖y‖→+∞, y∈D 〈∇fi(y),y − a〉 > 0, i = 1, . . . , r. Khi đó MOP(D,f) có một nghiệm Pareto yếu. Kết hợp Định lý 3.1.2, Định lý 3.1.3, và Định lý 2.1.3 ta thu được kết quả sau cho sự tồn tại nghiệm của bài toán tối ưu đa mục tiêu. 3.1.4 Hệ quả. Giả sử f lồi và khả vi. Giả sử thêm rằng một trong các điều kiện dưới đây thỏa mãn 1. D bị chặn, 2. D không bị chặn và ∇f thỏa mãn điều kiện bức yếu trên D, nghĩa là tồn tại một vector s ∈ Rr+ và một vector a ∈ D sao cho lim ‖y‖→+∞, y∈D r∑ i=1 si〈∇fi(y),y − a〉 = +∞, 3. D không bị chặn và tồn tại a ∈ D sao cho lim ‖y‖→+∞, y∈D 〈∇fi(y),y − a〉 > 0, i = 1, . . . , r. Khi đó MOP(D,f) có nghiệm Pareto yếu. Chứng minh. Do tính lồi của fi, ta có ∇fi liên tục và đơn điệu (Hệ quả 25.5.1, [45]). Gọi F : Rk → Rr×k là ánh xạ với các ánh xạ thành phần ∇fi, i = 1, . . . , r. Khi đó hiển nhiên F liên tục và đơn điệu. Nếu D bị chặn, theo Định lý 2.1.3, WVVIP(D,F ) có một nghiệm x. Sử dụng Định lý 3.1.2, ta suy ra rằng x cũng là một nghiệm Pareto yếu của MOP(D,f). 54 Giả sử rằng D không bị chặn. Nếu tính chất thứ hai thỏa mãn, ta có F thỏa mãn điều kiện bức yếu trên D. Do đó, theo Định lý 2.1.3, WVVIP(D,F ) có một nghiệm x. Sử dụng Định lý 3.1.2, ta suy ra x là một nghiệm Pareto yếu của MOP(D,f). Nếu tính chất thứ ba thỏa mãn, theo Định lý 3.1.3, MOP(D,f) có một nghiệm Pareto yếu. 3.2 Bài toán phạt Trong mục này ta sẽ xây dựng các bài toán phạt cho MOP(D,f). Cố định một tập K ⊃ D. Với t > 0 ta định nghĩa bài toán phạt như sau MOP(K,f (t)) : min x∈K f (t) = (f (t) 1 , . . . , f (t) r ), trong đó f (t) i = fi + tP , i = 1, . . . , r, với P là hàm phạt của D. Trong trường hợp miền K là Rk thì bài toán phạt không có ràng buộc nào. Tiếp theo ta nghiên cứu sự tồn tại nghiệm của các bài toán phạt MOP(K,f (t)). 3.2.1 Bổ đề. Giả sử f : Rk → Rr là lồi và khả vi. Hơn nữa giả thiết rằng một trong các điều kiện sau đây thỏa mãn 1. K bị chặn, 2. K không bị chặn và tồn tại các vector s ∈ Rr+ và a ∈ D sao cho lim ‖y‖→+∞, y∈K r∑ i=1 si〈∇fi(y),y − a〉 = +∞, 3. K không bị chặn và tồn tại a ∈ D sao cho lim ‖y‖→+∞, y∈K 〈∇fi(y),y − a〉 > 0, i = 1, . . . , r. Khi đó MOP(K,f (t)) có một nghiệm Pareto yếu. 55 Chứng minh. Hiển nhiên f (t) i = fi + tP lồi và khả vi. Nếu K bị chặn, theo Hệ quả 3.1.4, MOP(K,f (t)) có một nghiệm Pareto yếu. Giả sử rằng điều kiện thứ hai thỏa mãn. Ta có r∑ i=1 si〈∇f (t)i (y),y − a〉 = r∑ i=1 si〈∇fi(y),y − a〉+ t r∑ i=1 si〈∇P (y),y − a〉 ≥ r∑ i=1 si〈∇fi(y),y − a〉+ t(P (y)− P (a)) ≥ r∑ i=1 si〈∇fi(y),y − a〉 → +∞, khi ‖y‖ → +∞,y ∈ K. Trong bất đẳng thức thứ hai ta sử dụng tính chất P (y) ≥ 0 và P (a) = 0 vì a ∈ D. Do đó, theo Hệ quả 3.1.4 MOP(K,f (t)) có một nghiệm Pareto yếu. Giả sử điều kiện thứ ba thỏa mãn. Với mỗi i = 1, . . . , r ta có 〈∇f (t)i (y),y − a〉 = 〈∇fi(y),y − a〉+ t〈∇P (y),y − a〉 ≥ 〈∇fi(y),y − a〉+ t(P (y)− P (a)) ≥ 〈∇fi(y),y − a〉. Do đó lim ‖y‖→+∞, y∈K 〈∇f (t)i (y),y − a〉 > 0. Theo Hệ quả 3.1.4, ta kết luận rằng MOP(K,f (t)) có một nghiệm Pareto yếu. 3.3 Các định lý hội tụ Ký hiệu S và S(t) tương ứng là các tập nghiệm của MOP(D,f) và MOP(K,f (t)). Lấy {tn}n là một dãy các số thực dương tăng đơn điệu tới +∞ khi n→ +∞. 56 3.3.1 Bổ đề. Giả sử f liên tục và x(n) ∈ S(tn) với mọi n ∈ N. Giả sử rằng x là một điểm giới hạn của dãy { x(n) } n . Khi đó x ∈ D. Chứng minh. Ta chứng minh bổ đề này bằng phương pháp phản chứng. Giả sử x là giới hạn của dãy con { x(nm) } m của { x(n) } n và x /∈ D. Khi đó P (x) > 0 và do vậy P (x) > ε với ε > 0 nào đó. Lấy y ∈ D bất kỳ. Vì x(nm) ∈ S(tnm), tồn tại inm sao cho f (tnm) inm (y) ≥ f (tnm)inm (x(nm)). Vì inm ∈ {1, 2, . . . , r}, tồn tại một dãy vô hạn {inm`}` các chỉ số có cùng một giá trị, chẳng hạn inm` = 1, với mọi ` ∈ N. Để đơn giản ký hiệu, ta giả sử inm = 1 với mọi m ∈ N. Do đó với mọi m ∈ N f (tnm) 1 (y) ≥ f (tnm)1 (x(nm)). (3.1) Vì P (x(nm))→ P (x) > ε, với mọi m đủ lớn ta có P (x(nm)) > ε. Do vậy với m đủ lớn f (tnm) 1 (x (nm))− f (tnm)1 (y) = f1(x(nm))− f1(y) + tnm(P (x(nm))− P (y)) ≥ f1(x(nm))− f1(y) + tnmε → f1(x)− f1(y) +∞ = +∞, as m→ +∞. Điều này mâu thuẫn với (3.1). Chú ý rằng ở đây P (y) = 0 vì y ∈ D. Định lý sau đây chứng tỏ rằng nếu một dãy các nghiệm Pareto yếu của các bài toán phạt hội tụ tới một điểm x thì x là một nghiệm Pareto yếu của bài toán ban đầu. Để ý rằng nếu tồn tại n ∈ N sao cho x(n) ∈ S(tn) ∩D, dễ thấy x(n) cũng là một nghiệm của MOP(D,f). 3.3.2 Định lí. Giả sử rằng f liên tục và x(n) ∈ S(tn) với mọi n ∈ N. Khi đó một điểm giới hạn bất kỳ của dãy { x(n) } n sẽ là một nghiệm Pareto yếu của MOP(D,f). 57 Chứng minh. Ta giả sử rằng x là một điểm giới hạn của dãy { x(n) } n . Gọi { x(nm) } m là dãy con của { x(n) } n hội tụ tới x. Theo Bổ đề 3.3.1, x ∈ D. Giả sử phản chứng rằng x /∈ S. Khi đó tồn tại y ∈ D thỏa mãn fi(y) < fi(x), i = 1, . . . , r. Vì x(nm) ∈ S(tnm), tồn tại inm sao cho f (tnm) inm (y) ≥ f (tnm)inm ( x(nm) ) . Vì inm ∈ {1, 2, . . . , r}, tồn tại một dãy vô hạn các chỉ số { inm` } ` nhận cùng một giá trị, chẳng hạn inm` = 1, với mọi ` ∈ N. Để đơn giản ký hiêu, ta lại giả sử rằng chính dãy { inm } m thỏa mãn tính chất này, tức là inm = 1 với mọi m ∈ N. Do đó với mọi m ∈ N đủ lớn ta có f (tnm) 1 (y) ≥ f (tnm)1 ( x(nm) ) . (3.2) Vì f1(y) 0 nào đó. Vì x(nm) → x khi m→ +∞, với m đủ lớn ta có f1(y)− f1 ( x(nm) ) < −ε. Do vậy với m đủ lớn f (tnm) 1 (y)− f (tnm)1 ( x(nm) ) = f1(y)− f1 ( x(nm) ) + tnm ( P (y)− P(x(nm))) < −ε− tnmP ( x(nm) ) ≤ −ε. Điều này mâu thuẫn với (3.2). 3.3.3 Định lí. Giả sử f : Rk → Rr lồi và khả vi. Giả sử thêm rằng một trong các điều kiện sau đây thỏa mãn 1. K bị chặn, 58 2. K không bị chặn và tồn tại a ∈ D sao cho lim ‖y‖→+∞, y∈K 〈∇fi(y),y − a〉 > 0, i = 1, . . . , r. Giả sử x(n) ∈ S(tn) với mọi n ∈ N. Khi đó dãy { x(n) } n có ít nhất một điểm giới hạn và mỗi điểm giới hạn của dãy này là một nghiệm Pareto yếu của MOP(D,f). Chứng minh. Trước hết để ý rằng theo Bổ đề 3.2.1, ta có S(tn) 6= ∅. Do đó dãy { x(n) } n nêu trong định lý luôn tồn tại. Nếu K bị chặn thì dãy { x(n) } n ⊆ K cũng bị chặn. Do đó theo nguyên lý Bolzano-Weierstrass, dãy này sẽ có ít nhất một điểm giới hạn. Khẳng định rằng điểm giới hạn này là một nghiệm Pareto yếu của MOP(D,f) được suy ra trực tiếp từ Định lý 3.3.2. Bây giờ giả sử rằng K không bị chặn và tồn tại a ∈ D sao cho lim ‖y‖→+∞, y∈K 〈∇fi(y),y − a〉 > 0, i = 1, . . . , r. Ta chỉ cần chứng tỏ rằng dãy { x(n) } n bị chặn là đủ. Với t > 0, gọi B(t) là hình cầu đóng nhỏ nhất của Rk tâm tại gốc tọa độ sao cho với mọi y /∈ B(t) và với mọi i = 1, . . . , r, ta có〈∇f (t)i (y),y − a〉 > 0, hay nói cách khác〈∇fi(y),y − a)〉+ t〈∇P (y),y − a〉 > 0. Vì 〈∇fi(y),y − a)〉 > 0 khi ‖y‖ đủ lớn, và t 〈∇P (y),y − a〉 ≥ t(P (y)− P (a)) ≥ 0, 59 ta suy ra B(t) có bán kính hữu hạn. Tiếp theo, ta chứng minh rằng S(t) ⊆ B(t). Thật vậy, giả sử phản chứng rằng tồn tại y ∈ S(t)\B(t). Khi đó theo định nghĩa của B(t), với mọi i = 1, . . . , r ta có 〈∇f (t)i (y),y − a〉 > 0, hay nói một cách tương đương,〈∇f (t)i (y),a− y〉 < 0, i = 1, . . . , r. Do đó y không phải là một nghiệm của WVVIP(K, (f (t))′). Theo Định lý 3.1.2, ta suy ra rằng y /∈ S(t), mâu thuẫn. Do vậy S(t) ⊆ B(t). Mặt khác, với t′ > t, ta có B(t′) ⊆ B(t). Thật vậy, với mọi y /∈ B(t) và với mọi i = 1, . . . , r, ta có〈∇fi(y),y − a)〉+ t〈∇P (y),y − a〉 > 0, kéo theo 〈∇fi(y),y − a)〉+ t′〈∇P (y),y − a〉 > 0, (3.3) vì 〈∇P (y),y − a〉 ≥ P (y)− P (a) ≥ 0. Theo định nghĩa, B(t′) là hình cầu đóng nhỏ nhất sao cho với mọi y /∈ B(t′), bất đẳng thức (3.3) thỏa mãn với mọi i = 1, . . . , r. Do đó B(t′) là một tập con của B(t). Cuối cùng, vì {tn}n đơn điệu tăng, ta có B(t1) ⊇ B(t2) ⊇ · · · ⊇ B(tn) ⊇ · · · Do đó với mọi n ∈ N ta có x(n) ∈ S(tn) ⊆ B(tn) ⊆ B(t1). Vì bán kính của B(t1) là hữu hạn, ta kết luận rằng dãy { x(n) } n bị chặn. 60 3.3.4 Ví dụ. Xét D = {x = (x1, x2)T ∈ R2 : x2 − x1 − 1 ≤ 0,−x2 + x21 − 1 ≤ 0}. Hình 3.1: Miền ràng buộc D Lấy P theo (2.3) P (x) = [max{0, x2 − x1 − 1}]2 + [max{0,−x2 + x21 − 1}]2 =  0, x ∈ D, (x2 − x1 − 1)2, x ∈ (I), (x2 − x1 − 1)2 + (−x2 + x21 − 1)2, x ∈ (II), (−x2 + x21 − 1)2, x ∈ (III). Cho f(x) = (f1(x), f2(x)), trong đó f1(x) = x21 2 + x22 2 + x1x2 + 2e x2/2 − 2x2, f2(x) = e x1 + x21 − x1 + x22 2 + 1. Dễ thấy f định nghĩa như trên là lồi và khả vi trên R2. Lấy K = R2 và a = 0 ∈ D. Khi đó ta có 〈∇f1(y),y〉 = (y1 + y2)2 + y2ey2/2 − 2y2, 〈∇f2(y),y〉 = 2y21 + y22 + y1ey1 − y1, 61 hiển nhiên là các số dương khi ‖y‖ → +∞. Do đó, theo Định lý 3.3.3 một dãy bất kỳ các nghiệm Pareto yếu của các bài toán phạt MOP(K,f (tn)), n = 1, 2, . . . sẽ có ít nhất một điểm giới hạn và mọi điểm giới hạn của dãy đó là một nghiệm Pareto yếu của MOP(D,f). Kết luận Chương 3 Trong chương này, luận án đã giải quyết được những vấn đề sau. - Nghiên cứu mối quan hệ giữa tập các nghiệm Pareto yếu của bài toán tối ưu đa mục tiêu ban đầu và các tập nghiệm Pareto yếu của các bài toán phạt tương ứng. - Chứng minh được rằng nếu miền D là lồi đóng, ánh xạ f lồi, khả vi và thỏa mãn tính chất bức, thì các bài toán phạt đều có nghiệm Pareto yếu. Hơn nữa, bất kỳ dãy nghiệm Pareto yếu nào của các bài toán phạt đều bị chặn, do đó có ít nhất một điểm giới hạn và đó chính là một nghiệm Pareto yếu của bài toán tối ưu đa mục tiêu ban đầu. Định lý 3.3.2 chứng minh rằng một điểm giới hạn bất kỳ của dãy các nghiệm Pareto yếu của các bài toán phạt là một nghiệm Pareto yếu của bài toán ban đầu, chỉ cần giả thiết về tính liên tục của hàm mục tiêu f . Ta không yêu cầu f lồi hoặc khả vi trong định lý này. Tuy nhiên, Định lý 3.3.3 đòi hỏi những tính chất đó của f . Một vài công trình gần đây đã nghiên cứu nghiệm Pareto yếu của bài toán tối ưu đa mục tiêu với các giả thiết được giảm nhẹ cho f , chẳng hạn, khi f không lồi và không khả vi (tham khảo [27, 30, 46]). Dựa trên những kết quả này, ta cũng có thể giảm nhẹ các giả thiết đặt lên hàm f nêu trong Định lý 3.3.3. 62 KẾT LUẬN VÀ KIẾN NGHỊ 1 Kết luận Luận án nghiên cứu phương pháp hàm phạt áp dụng cho bài toán bất đẳng thức biến phân, bài toán bất đẳng thức biến phân vector yếu và bài toán tối ưu đa mục tiêu. Kết quả chính của luận án như sau. 1. Đưa ra thuật toán kết hợp hai phương pháp hàm phạt và phương pháp chiếu để giải bài toán bất đẳng thức biến phân. Thuật toán kết hợp đã khắc phục được nhược điểm cơ bản của phương pháp chiếu là sự khó khăn khi tính hình chiếu của một điểm lên một miền lồi bất kỳ và tận dụng được ưu điểm của thuật toán này là khối lượng tính toán nhỏ, thuật toán đơn giản. Thuật toán được minh họa bởi các ví dụ trong trường hợp hai chiều và nhiều chiều, kết quả giải số của các ví dụ được phân tích và so sánh. 2. Xây dựng mô hình hàm phạt để giải bài toán bất đẳng thức biến phân vector yếu. Chứng minh được các kết quả hội tụ cơ bản của phương pháp. 3. Nghiên cứu áp dụng phương pháp hàm phạt để tìm nghiệm Pareto yếu của bài toán tối ưu đa mục tiêu. Chứng minh được các kết quả hội tụ cơ bản của phương pháp. Cải tiến các kết quả nêu trong [34]. Kết quả chính của luận án được công bố trong [37], [35] và [36]. 2 Kiến nghị Thời gian tới, chúng tôi mong muốn tiếp tục nghiên cứu những vấn đề sau. 1. Nghiên cứu thêm về tính hiệu quả và tốc độ hội tụ của thuật toán 63 kết hợp phương pháp hàm phạt và phương pháp chiếu cho bài toán bất đẳng thức biến phân. 2. Giảm nhẹ các giả thiết nêu trong các điều kiện đủ đã thiết lập trong Chương 2 và Chương 3. Trước hết là nghiên cứu kỹ hơn các điều kiện đủ này trong trường hợp hàm mục tiêu là không trơn và không đơn điệu. 3. Nghiên cứu mở rộng phương pháp hàm phạt cho các dạng tổng quát hơn của bài toán bất đẳng thức biến phân vector. DANH MỤC CÔNG TRÌNH KHOA HỌC CỦA NGHIÊN CỨU SINH LIÊN QUAN ĐẾN LUẬN ÁN 1. Đậu Xuân Lương (2003), “Ánh xạ tự bức và ứng dụng vào bất đẳng thức biến phân,” Thông báo khoa học – Các ngành khoa học tự nhiên, Trường Đại học Vinh. 2. D. X. Luong and L. D. Muu (2010), “Combining the projection meth- ods and the penalty function method to solve the variational inequal- ities with monotone mappings”, Int. J. Optim. Theory Methods Appl., 2(2), pp. 124–137. 3. D. X. Luong (2010), “Penalty functions for the vector variational inequality problem”, submitted to Acta Mathematica Vietnamica for publication. 4. D. X. Luong and T. V. An (2010), “Penalty functions for the mul- tiobjective optimization problem”, J. Math. Sci. Adv. Appl., 6(1), pp. 177–192. TÀI LIỆU THAM KHẢO [1] Alber Y. I. (1995), “The penalty method for variational inequali- ties with nonsmooth unbounded operators in banach space”, Numer. Funct. Anal. Optim., 16(9&10), 1111–1125. [2] Chen G. Y. (1988), “Vector variational inequality and vector opti- mization”, Lecture Notes in Econom. and Math. Systems, 285, 408–416. [3] Chen G. Y. (1992), “Existence of solutions for a vector variational inequality: An extension of the Hartman-Stampacchia theorem”, J. Optim. Theory Appl., 74, 445–456. [4] Chen G. Y. and Craven B. D. (1990), “A vector variational inequality and optimization over an efficient set”, ZOR-Meth. Models Oper. Res., 34, 1–12. [5] Chen G. Y. and Craven B. D. (1994), “Existence and continuity of solutions for vector optimization”, J. Optim. Theory Appl., 81(3), 459–468. [6] Chen G. Y. and Yang X. Q. (1990), “The vector complementary prob- lem and its equivalences with the weak minimal element in ordered spaces”, J. Math. Anal. Appl., 153, 136–158. [7] Cominetti R. and Dussault J. P. (1994), “Stable exponential-penalty algorithm with superlinear convergence”, J. Optim. Theory Appl., 83(2), 285–309. 64 65 [8] Dafermos S. C. (1980), “Traffic equilibria and variational inequali- ties”, Transportation Science, 14(1), 42–54. [9] Dafermos S. C. (1990), “Exchange price equilibria and variational inequalities”, Math. Program., 46, 391–402. [10] Dafermos S. C. (1990), “Exchange price equilibria and variational inequalities”, Math. Program., 46(3), 391–402. [11] Dafermos S. C. and McKelvey S. C. (1992), “Partitionable variational inequalities with applications to network and economic equilibria”, J. Optim. Theory Appl., 73(2), 243–268. [12] Daniilidis A. and Hadjisavvas N. (1996), “Existence theorems for vec- tor variational inequalities”, Bull. Austral. Math. Soc., 54, 473–481. [13] Edgeworth F. Y. (1881), Mathematical Psychics, Kegan Paul, Lon- don, England. [14] Evans J. P. and Gould F. J. (1974), “An existence theorem for penalty function theory”, SIAM J. Control., 12, 505–516. [15] Facchiney F. and Pang J.-S. (2003), Finite Dimensional Variational Inequalities and Complementarity Problems, Springer Series in Op- erations Research and Financial Engineering. [16] Giannessi F. (1980), “Theorems of alternative, quadratic programs and complementary problems”, 151–186, in Variational inequality and complementary problems, edited by Cottle R. W., Giannessi F. and Eds J.-L. Lions, Wiley, New York. [17] Giannessi F. (2000), Vector Variational Inequalities and Vector Equilibria, Kluwer Academic Publishers. [18] Goh C. J. and Yang X. Q. (1999), “Vector equilibrium problem and vector optimization”, European J. Oper. Res., 116(3), 615–628. 66 [19] Goh C. J. and Yang X. Q. (2000), “Scalarization methods for vector variational inequality”, in Vector variational inequalities and vector equilibria, edited by Giannessi F., Kluwer Acadamic Publishers. [20] Hartman P. and Stampacchia G. (1966), “On some nonlinear elliptic differential functional equations”, Acta Mathematica, 115, 153–188. [21] Huang X. Q. and Yang X. Q. (2002), “Nonlinear Lagrangian for mul- tiobjective optimization and applications to duality and exact penal- ization”, SIAM J. Optim., 13(3), 675–692. [22] Huang X. Q., Yang X. Q. and Teo K. L. (2006), “Convergence analysis of a class of penalty methods for vector optimization problems with cone constraints”, J. Global Optim., 36(4), 637–652. [23] Ito K. and Kunisch K. (1990), “An augmented Lagrangian technique for variational inequalities”, Appl. Math. Optim., 21(1), 223–241. [24] Jahn J. (2004), Vector Optimization: Theory, Applications, and Extensions, Springer Verlag, New York. [25] Jofre A., Rockafellar R. T. and Wets R. J-B. (2005), “A varia- tional inequality scheme for determining an economic equilibrium”, in Variational Analysis and Applications, edited by Giannessi F. and Maugeri A., Kluwer Acadamic Publishers. [26] Jofré A., Rockafellar R. T. and Wets R. J-B. (2007), “Variational Inequalities and Economic Equilibrium”, Math. Oper. Res., 32(1), 32–50. [27] Kazmi K. R. (1996), “Existence of solutions for vector optimization”, Appl. Math. Lett., 9, 19–22. 67 [28] Konnov I. V. (2001), “Combined relaxation methods for variational inequalities”, Lecture Notes in Economics and mathematical Sys- tems, 495. [29] Konnov I. V. (2007), Equilibium Models and Variational Inequali- ties, Elsevier B. V., Amsterdam. [30] Lee G. M. and Kim D. S. (1994), “Existence of Solutions for vector optimization problems”, J. Optim. Theory Appl., 81(3), 459–468. [31] Lee G. M., Kim D. S., Lee B. S. and Cho S. J. (1993), “Generalized vector variational inequalities and fuzzy extensions”, Appl. Math. Lett., 6, 47–51. [32] Lions J. L. and Stampacchia G. (1967), “Variational inequalities”, Comm. Pure Appl. Math., 20, 493–519. [33] Liu G. P., Yang J. B. andWhidborne J. F. (2002),Multiobjective Op- timization and Control, Research Studies Press Ltd, Baldock United Kingdom. [34] Liu S. and Feng E. (2010), “The exponential penalty function method for multiobjective programming problems”, Optim. Methods Softw., 25(5), 667–675. [35] Luong D. X. (2010), “Penalty functions for the vector variational inequality problem”, Submitted to Acta Mathematica Vietnamica for publication. [36] Luong D. X. and An T. V. (2010), “Penalty functions for the mul- tiobjective optimization problem”, J. Math. Sci. Adv. Appl., 6(1), 177–192. [37] Luong D. X. and Muu L. D. (2010), “Combining the projection meth- ods and the penalty function method to solve the variational inequal- 68 ities with monotone mappings”, Int. J. Optim. Theory Methods Appl., 2(2), 124–137. [38] Muu L. D. (1989), “An augmented penalty function method for solv- ing a class of variational inequalities”, U.S.S.R. Comput. Math. and Math. Phys., 26(6), 117–122. [39] Muu L. D. (1992), “On a Lagrangian penalty function method for nonlinear programming problems”, Appl. Math. Optim., 25(1), 1–9. [40] Nagurney A. (1989), “Migration Equilibrium and Variational Inequal- ities”, Econom. Lett., 31(1), 109–112. [41] Nagurney A. (1999), Network Economics: A Variational Inequality Approach, Edition 2, Springer Series in Advances in Computational Economics. [42] Nagurney A. and Dafermos S. C. (1984), “General spatial economic equilibrium problem”, Oper. Res., 32, 1069–1086. [43] Nguyen V. H. and Strodiot J. J. (1979), “On the convergence rate for a penalty function method of exponential type”, J. Optim. Theory Appl., 27(4), 495–508. [44] Pareto V. (1906), Manual of Political Economy, Societa Editrice Libraria, Milano, Italy. [45] Rockafellar R. T. (1970), Convex Analysis, Princeton Univ. Press, Princeton, New Jersey. [46] Santos L. B., Ruiz-Garzon G., Rojas-Medar M. A. and Rufian-Lizana A. (2008), “Existence of weakly efficient solutions in nonsmooth vec- tor optimization”, Appl. Math. Comput., 200(2), 547–556. [47] Smith M. J. (1979), “The existence, uniqueness and stability of traffic equilibria”, Transportation Science, 13B, 295–304. 69 [48] Stadler W. (1979), “A survey of multicriteria optimization or the vector maximum problem, part I: 1776–1960”, J. Optim. Theory Appl., 29(1), 1–52. [49] Stadler W. (1988), Multicriteria Optimization in Engineering and in the Sciences, Springer Verlag, New York. [50] Stampacchia G. (1964), “Formes bilineares coercives sur les ensembles convexes”, Comptes Rendus Academie Sciences Paris, 258, 4413– 4416. [51] Tang Y. C. and Liu L. W. (2010), “The penalty method for a new system of generalized variational inequlities”, Int. J. Math. Math. Sci., 25(2010), 1–9. [52] White D. J. (2002), “Multiobjective programming and penalty func- tions”, J. Optim. Theory Appl., 13(3), 675–692. [53] Yang X. Q. (1993), “Vector complimentary and minimal element problems”, J. Optim. Theory Appl., 77, 483–495. [54] Yang X. Q. (1993), “Vector variational inequality and its duality”, Nonlinear Anal., 21(11), 869–877. [55] Yang X. Q. and Goh C. J. (1997), “On vector variational inequality: applications to vector traffic equilibria”, J. Optim. Theory Appl., 95, 431–443. [56] Zangwill W. I. (1969), Nonlinear Programming: A Unified Ap- proach, Prentice Hall, Englewood Cliffs, NJ.