Tài liệu điều kiện cực trị và ổn định trong tối ưu véctơ với thứ tự suy rộng [tt]

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2 NGUYỄN VĂN TUYÊN ĐIỀU KIỆN CỰC TRỊ VÀ ỔN ĐỊNH TRONG TỐI ƯU VÉCTƠ VỚI THỨ TỰ SUY RỘNG TÓM TẮT LUẬN ÁN TIẾN SĨ TOÁN HỌC HÀ NỘI - 2016 Công trình được hoàn thành tại Trường Đại học Sư phạm Hà Nội 2. Người hướng dẫn khoa học: PGS. TS Nguyễn Quang Huy Phản biện: ................................................................... ................................................................... Phản biện: ................................................................ ................................................................ Phản biện: .................................................................. .................................................................. Luận án sẽ được bảo vệ trước Hội đồng cấp Trường chấm luận án tiến sĩ họp tại : ............................................................................................................................... vào hồi ...... giờ ngày ...... tháng ...... năm 20... Có thể tìm hiểu luận án tại: • Thư viện Quốc gia Việt Nam • Thư viện Trường Đại học Sư phạm Hà Nội 2 Mở đầu Tối ưu véctơ (Vector optimization) hay còn gọi là Tối ưu đa mục tiêu (Multicriteria optimization) được hình thành từ những ý tưởng về cân bằng kinh tế, lý thuyết giá trị của F. Edgeworth (1881) và V. Pareto (1906). Từ những năm 1950 trở lại đây, sau những công trình về điều kiện cần và đủ cho tối ưu của H. W. Kuhn và A. W. Tucker năm 1951, về giá trị cân bằng và tối ưu Pareto của G. Debreu năm 1954, lý thuyết tối ưu véctơ mới thực sự được công nhận là một ngành toán học quan trọng và có nhiều ứng dụng trong thực tế. Lúc đầu người ta mới nghiên cứu những bài toán có liên quan tới ánh xạ đơn trị từ không gian Euclide này sang không gian Euclide khác mà thứ tự trong nó được sinh ra bởi nón orthant dương. Sau đó người ta mở rộng cho các bài toán trong không gian có số chiều vô hạn với nón lồi bất kì. Để mở rộng phạm vi áp dụng của các khái niệm nghiệm cổ điển của các bài toán quy hoạch toán học và bài toán tối ưu véctơ, A. Y. Kruger và B.S. Mordukhovich (xem [48, Subsection 5.5.18] và các tài liệu trích dẫn được trích dẫn trong đó) đã đề xuất khái niệm nghiệm tối ưu theo thứ tự suy rộng (hay nghiệm (f ; Θ)-tối ưu địa phương), ở đó f : X → Z là một ánh xạ đơn trị giữa các không gian Banach và tập sinh thứ tự Θ là một tập bất kì chứa gốc. Một điểm x̄ ∈ X được gọi là một nghiệm (f ; Θ)-tối ưu địa phương nếu tồn tại một lân cận U của x̄ và một dãy {zk } với kzk k → 0 khi k → ∞ thỏa mãn: f (x) ∈ / f (x̄) − Θ − zk với mọi x ∈ U và k ∈ N. Nếu Θ là một nón lồi có phần trong tương đối khác rỗng, thì khái niệm nghiệm tối ưu trên bao phủ các khái niệm nghiệm cổ điển trong tối ưu véctơ như nghiệm Pareto, nghiệm Pareto tương đối (hay nghiệm tối ưu theo nghĩa Slater) (xem [48, 65]). Cần nhấn mạnh rằng, tập sinh thứ tự Θ không nhất thiết là tập lồi hay là nón. Điều này đáp ứng đòi hỏi ngày càng tăng trong thực tế và cả trong lý thuyết áp dụng của tối ưu véctơ; đặc biệt là trong các mô hình kinh tế (xem [60]). Ngoài khía cạnh mở rộng phạm vi áp dụng của các khái niệm nghiệm, nghiệm tối ưu theo thứ tự suy rộng còn là một công cụ hữu ích để nghiên cứu các bài toán minimax (minimax problem) trên một tập compact (xem [48, Example 5.54]). Việc 1 xem nghiệm của một bài toán minimax như là nghiệm của một bài toán tối ưu véctơ theo thứ tự suy rộng giúp chúng ta thuận lợi hơn khi nghiên cứu các điều kiện cần tối ưu cho các bài toán này (xem [48, Subsections 5.3.1, 5.5.19]). Với những ý nghĩa kể trên, việc nghiên cứu các tính chất định tính của nghiệm tối ưu theo thứ tự suy rộng của các bài toán tối ưu véctơ có một ý nghĩa rất quan trọng. Tuy nhiên, theo hiểu biết của chúng tôi mới chỉ có một vài nghiên cứu về các điều kiện cần cực trị (xem [9, 48] và các tài liệu được trích dẫn trong đó) và độ nhạy nghiệm (xem [32]). Luận án này trình bày các kết quả mới về sự tồn tại nghiệm, các tính chất tôpô của tập nghiệm, các điều kiện cực trị và tính ổn định của các bài toán tối ưu véctơ với thứ tự suy rộng. Luận án bao gồm phần mở đầu, 3 chương, phần kết luận, và danh mục tài liệu tham khảo. Chương 1 khảo sát khái niệm tối ưu theo thứ tự suy rộng. Mục 1.1 phân tích khái niệm nghiệm của bài toán tối ưu véctơ theo thứ tự suy rộng. Mục 1.2 trình bày một số kết quả về sự tồn tại nghiệm tối ưu theo thứ tự suy rộng. Mục 1.3 khảo sát một số tính chất tôpô (tính đóng và tính liên thông) của tập nghiệm của bài toán tối ưu véctơ theo thứ tự suy rộng. Chương 2 nghiên cứu các điều kiện tối ưu cho bài toán tối ưu véctơ với thứ tự suy rộng. Mục 2.1 nhắc lại một số kiến thức cơ sở của giải tích biến phân. Các kiến thức này là cơ sở để đưa ra các điều kiện tối ưu trong các mục tiếp theo của chương này. Trong Mục 2.2, bằng cách tiếp cận trên không gian ảnh chúng tôi đã đạt được một số điều kiện cần, điều kiện đủ cho một điểm hữu hiệu suy rộng. Các kết quả về điều kiện cần có thể coi là trường hợp đặc biệt của các kết quả trong [9, 48]. Tuy nhiên kết quả về điều kiện đủ là mới. Trong mục cuối của chương này, chúng tôi trình bày một số điều kiện đủ cho điểm là nghiệm tối ưu theo thứ tự suy rộng dưới các giả thiết về tính lồi. Chương 3 trình bày các kết quả nghiên cứu về tính ổn định của bài toán tối ưu véctơ sử dụng khái niệm nghiệm Pareto tương đối. Trong Mục 3.1, chúng tôi trình bày một số tính chất của tập điểm hữu hiệu Pareto tương đối. Mục 3.2 trình bày các kết quả về sự hội tụ trên theo nghĩa Kuratowski-Painlevé của tập điểm hữu hiệu Pareto tương đối. Mục 3.3 trình bày các kết quả về sự hội tụ dưới theo nghĩa Kuratowski-Painlevé của tập điểm hữu hiệu Pareto tương đối. Trong mục cuối chúng tôi thiết lập một số điều kiện đủ cho tính nửa liên tục dưới của ánh xạ điểm hữu hiệu Pareto tương đối. Việc đánh số của các chương, mục, định lý, ... trong bản tóm tắt này được giữ nguyên như ở trong luận án. 2 Chương 1 Tính chất tôpô của tập nghiệm trong tối ưu véctơ với thứ tự suy rộng Mục đích của chương này là trình bày một số đặc trưng của nghiệm tối ưu theo thứ tự suy rộng. Chương này được viết trên cơ sở các bài báo [2, 3]. 1.1. Một số tính chất cơ bản Cho Z là một không gian Banach. Với mỗi tập A ⊂ Z, chúng ta sẽ sử dụng các kí hiệu sau trong toàn bộ luận án: int A, cl A, bd (A), Ac , aff (A), conv (A) và cone (A) là phần trong, bao đóng, biên, phần bù, bao aphin, bao lồi, và bao nón của A trong Z. Bên cạnh đó, l(A) được kí hiệu là tập hợp A ∩ (−A). Định nghĩa 1.1. Cho A là một tập con khác rỗng trong Z và Θ ⊂ Z là một tập chứa 0Z . Một điểm z̄ ∈ A được gọi là một điểm hữu hiệu suy rộng (generalized efficient point) của A tương ứng với Θ, nếu tồn tại một dãy {zk } ⊂ Z với kzk k → 0 khi k → ∞ thỏa mãn A ∩ (z̄ − Θ − zk ) = ∅ ∀k ∈ N. (1.1) Tập hợp tất cả các điểm hữu hiệu suy rộng của A tương ứng với Θ được kí hiệu là GMin (A | Θ). Định lý 1.1. Cho A là một tập con khác rỗng trong Z và Θ ⊂ Z chứa 0Z . Khi đó GMin (A | Θ) = A ∩ bd (A + Θ). (1.2) Hơn nữa, GMin (A | Θ) là đóng nếu A đóng trong Z. Tiếp theo, chúng ta thiết lập một số quan hệ giữa các điểm hữu hiệu suy rộng và các điểm tựa của tập A. Nhắc lại rằng, z̄ ∈ cl A được gọi là một điểm tựa (supporting point) của A nếu tồn tại z ∗ ∈ Z ∗ \ {0} thỏa mãn hz ∗ , z̄i = sup{hz ∗ , zi | z ∈ A}. 3 Khi đó, z ∗ được gọi là một hàm tựa (supporting functional) của A tại z̄. Kí hiệu Θ∗ là tập cực (polar set) của Θ: Θ∗ = {z ∗ ∈ Z ∗ | hz ∗ , θi ≤ 0 ∀ θ ∈ Θ}. Mệnh đề 1.1. Cho A là một tập con khác rỗng trong không gian Banach Z và Θ ⊂ Z chứa 0Z . Nếu z̄ ∈ A là một điểm tựa của A tương ứng với hàm tựa z ∗ ∈ Θ∗ , thì z̄ ∈ GMin (A | Θ). Do đó, ta có [ {A0 (z ∗ ) | z ∗ ∈ Θ∗ , z ∗ 6= 0} ⊂ GMin (A | Θ), ở đó A0 (z ∗ ) = {z0 ∈ A | hz ∗ , z0 i = suphz ∗ , zi, z ∈ A}. Mệnh đề 1.2. Cho A là một tập con khác rỗng trong không gian Banach Z, và Θ ⊂ Z chứa 0Z . Giả sử rằng, A + Θ là một tập lồi và có phần trong khác rỗng. Khi đó, [ GMin (A | Θ) = {A0 (z ∗ ) | z ∗ ∈ Θ∗ , z ∗ 6= 0}. Mệnh đề 1.3. Cho A là một tập con khác rỗng trong Z và Θ ⊂ Z là một tập e ⊃ Θ, thì chứa 0Z . Nếu Θ e ⊂ GMin (A | Θ). GMin (A | Θ) (1.3) Mệnh đề 1.4. Cho A là một tập con khác rỗng trong Z và Θ ⊂ Z là một tập chứa 0Z thỏa mãn Θ + Θ = Θ. Khi đó GMin (A | Θ) = A ∩ GMin (A + Θ | Θ). (1.4) Định nghĩa 1.2. Giả sử Θ là một nón lồi với riΘ 6= ∅. Một điểm z̄ ∈ A được gọi là một điểm hữu hiệu Pareto tương đối/điểm hữu hiệu Slater (relative Pareto efficient point/Slater efficient point) của A tương ứng với Θ, nếu A ∩ (z̄ − ri Θ) = ∅. (1.5) Tập hợp tất cả các điểm hữu hiệu tương đối của A tương ứng với Θ được kí hiệu bởi RMin (A | Θ). Nếu Θ là một nón lồi trong Z, thì Θ sinh ra một quan hệ thứ tự trên Z như sau: z1 , z2 ∈ Z, z2 ≥ z1 nếu z2 − z1 ∈ Θ. Ta viết x > y nếu x ≥ y và không có y ≥ x, hoặc là, x ∈ y + Θ \ l(Θ). Một nón Θ được gọi là nhọn nếu l(Θ) = {0Z }. 4 Định nghĩa 1.3. Cho Θ là một nón lồi trong Z, A ⊂ Z là một tập con khác rỗng. a) Một điểm z̄ ∈ A được gọi là điểm hữu hiệu Pareto yếu/điểm hữu hiệu yếu (weak Pareto efficient point/weak efficient point) của A tương ứng với Θ, nếu A ∩ (z̄ − int Θ) = ∅ và int Θ 6= ∅. Tập hợp tất cả các điểm hữu hiệu Pareto yếu của A tương ứng với Θ được kí hiệu là WMin (A | Θ). b) Một điểm z̄ ∈ A được gọi là một điểm hữu hiệu Pareto/điểm hữu hiệu (Pareto efficient point/efficient point) của A tương ứng với Θ, nếu (z̄ ≥ y, với y ∈ A nào đó ) ⇒ (y ≥ z̄). Tập hợp tất cả các điểm hữu hiệu Pareto của A tương ứng với Θ được kí hiệu bởi Min (A | Θ). Mệnh đề 1.5. Nếu Θ là một nón lồi thì các phát biểu sau đây đúng (i) Nếu int Θ 6= ∅, thì GMin (A | Θ) ⊂ WMin (A | Θ). (ii) Nếu int Θ 6= ∅, thì WMin (A | Θ) ⊂ RMin (A | Θ). (iii) Nếu ri Θ 6= ∅, thì RMin (A | Θ) ⊂ GMin (A | Θ). Vì vậy, nếu Θ là một nón lồi với phần trong khác rỗng, thì WMin (A | Θ) = RMin (A | Θ) = GMin (A | Θ). (1.6) Mệnh đề 1.6. (xem [39, Proposition 2.3]) Một điểm z̄ ∈ Min (A | Θ) khi và chỉ khi A ∩ (z̄ − Θ) ⊂ z̄ + l(Θ), hoặc là, không có y ∈ A nào thỏa mãn z̄ > y. Đặc biệt, khi Θ là một nón nhọn, z̄ ∈ Min (A | Θ) khi và chỉ khi A ∩ (z̄ − Θ) = {z̄}. Mệnh đề 1.7. Giả sử Θ ⊂ Z là một nón lồi thỏa mãn Θ \ l(Θ) khác rỗng và A là một tập con khác rỗng trong Z. Nếu z̄ là một điểm hữu hiệu Pareto của A tương ứng với Θ, thì z̄ là một điểm hữu hiệu suy rộng của A tương ứng với Θ, hay là Min (A | Θ) ⊂ GMin (A | Θ). 1.2. Sự tồn tại nghiệm tối ưu theo thứ tự suy rộng 1.2.1. Sự tồn tại của các điểm hữu hiệu suy rộng (1.7) Giả sử Θ là một nón lồi Z. Một lưới {xα | α ∈ I} trong Z được gọi là giảm (tương ứng với Θ) nếu xα > xβ với mỗi α, β ∈ I, β > α. Với mỗi x ∈ Z, đặt Ax := A ∩ (x − Θ). Tập Ax được gọi là một lát cắt của A tại x. 5 Định nghĩa 1.4. (xem [39, Definition 3.2, p. 46]) Một tập A ⊂ Z được gọi là Θ-đầy đủ (Θ-complete) nếu không có phủ nào có dạng {(xα − cl Θ)c | α ∈ I} với {xα } là một lưới giảm trong A. Định nghĩa 1.5. Một nón lồi Θ trong Z được gọi là nón đúng (correct cone) nếu cl Θ + Θ \ l(Θ) ⊂ Θ, hay là cl Θ + Θ \ l(Θ) ⊂ Θ \ l(Θ). Mệnh đề 1.8. (xem [39, Theorem 3.3]) Giả sử rằng Θ là một nón lồi đúng và A là một tập con khác rỗng trong Z. Khi đó, Min (A | Θ) khác rỗng khi và chỉ khi A có lát cắt Θ-đầy đủ. Định lý 1.2. Giả sử rằng Θ là một nón lồi đúng thỏa mãn Θ \ l(Θ) khác rỗng và A là một tập con khác rỗng trong Z. Nếu A có lát cắt Θ-đầy đủ, thì GMin (A | Θ) khác rỗng. Định lý 1.3. Giả sử rằng A là một tập con khác rỗng trong Z và Θ ⊂ Z là một e := cl conv cone Θ thỏa mãn tập bất kì chứa 0Z . Nếu nón lồi đóng Θ e \ l(Θ) e 6= ∅, Θ (1.8) e và A có lát cắt Θ-đầy đủ, thì GMin (A | Θ) 6= ∅. 1.2.2. Áp dụng cho bài toán tối ưu véctơ Giả sử rằng X và Z là hai không gian Banach và Θ ⊂ Z là một tập chứa gốc. Cho F là một ánh xạ đa trị từ X tới Z. Định nghĩa 1.6. (xem [39, 40]) Giả sử rằng Ω là một tập con của dom F và Θ ⊂ Z là một tập chứa 0Z . (i) F được gọi là Θ-liên tục trên (upper Θ-continuous) tại x̄ ∈ Ω nếu với mỗi lân cận V của F (x̄) trong Z, tồn tại một lân cận U của x̄ trong X sao cho F (x) ⊂ V + Θ ∀x ∈ U ∩ dom F. Ta nói rằng F là Θ-liên tục trên trên tập Ω nếu nó là Θ-liên tục trên tại mọi điểm thuộc Ω. 6 (ii) F được gọi là Θ-nửa liên tục trên (upper Θ-semicontinuous) tại x̄ ∈ Ω nếu với mỗi lân cận V của 0Z , tồn tại một lân cận U của x̄ trong X sao cho F (x) ⊂ V + F (x̄) + Θ ∀x ∈ U ∩ dom F. Nếu điều này đúng với mọi x ∈ Ω, thì ta nói rằng F là Θ-nửa liên tục trên trên tập Ω. (iii) F là Θ-liên tục dưới (lower Θ-continuous) tại x̄ nếu với mỗi y ∈ F (x̄) và với mỗi lân cận V của y trong Z, tồn tại một lân cận U của x̄ trong X sao cho F (x) ∩ (V + Θ) 6= ∅ với mỗi x ∈ U ∩ dom F. Ta nói rằng F là Θ-liên tục dưới trên tập Ω nếu nó là Θ-liên tục dưới tại mọi điểm thuộc Ω. (iv) F được gọi là Θ-liên tục (Θ-continuous) tại x̄ nếu nó là Θ-liên tục trên và Θ-liên tục dưới tại điểm này. Định nghĩa 1.7. Cho F : X ⇒ Z là một ánh xạ đa trị giữa các không gian Banach, Θ ⊂ Z là một tập chứa gốc, và tập ràng buộc Ω ⊂ X. Ta nói rằng cặp (x̄, z̄) ∈ gph F là một nghiệm tối ưu địa phương theo thứ tự suy rộng (locally generalized optimal solution) của F tương ứng với tập sinh thứ tự Θ trên Ω, nếu z̄ ∈ GMin (F (Ω ∩ U ) | Θ), với U là một lân cận nào đó của x̄. Mệnh đề 1.9. Giả sử rằng Θ là một nón lồi đúng với Θ \ l(Θ) khác rỗng, Ω ⊂ X là một tập compact khác rỗng và F là Θ-nửa liên tục trên trên Ω với F (x) + Θ đóng và Θ-đầy đủ với mọi x ∈ Ω. Khi đó, GS (Ω, F ) khác rỗng. Mệnh đề 1.10. Giả sử rằng Ω ⊂ Z là một tập compact, F là nửa liên tục trên e := cl conv cone Θ thỏa mãn điều trên tập Ω và Θ ⊂ Z là một tập chứa gốc. Nếu Θ kiện (1.8), thì GS (Ω, F ) khác rỗng. 1.3. Một số tính chất tôpô của tập nghiệm 1.3.1. Tính đóng Giả sử rằng X, Z là hai không gian Banach. Cho f : X → Z là một ánh xạ đơn trị, Ω là một tập con khác rỗng trong X, và Θ ⊂ Z là một tập chứa 0Z . Xét bài toán tối ưu véctơ (VOP) min f (x) với ràng buộc x ∈ Ω. 7 Định lý 1.4. Giả sử rằng Θ là một tập con của Z chứa 0Z . Nếu Ω là đóng, f là Θ-liên tục trên Ω và điều kiện sau được thỏa mãn Θ + Θ = Θ, (1.9) thì GS (Ω, f ) là một tập đóng. Định lý 1.5. Giả sử Θ là một tập con của Z với 0Z ∈ Θ. Nếu Ω là một tập đóng và f liên tục trên A, thì GS (Ω, f ) đóng. 1.3.2. Tính liên thông Cho A là một tập con khác rỗng trong không gian Banach Z, B ⊂ A. Trong mục này, chúng ta giả sử rằng Θ là một nón lồi. Định nghĩa 1.8. (xem [39, Definition 4.1, p. 54]) Ta nói rằng tính chất trội (the domination property), kí hiệu là (DP ), đúng cho cặp (A, B) ⊂ Z × Z, nếu A ⊂ B + Θ. (1.10) Định nghĩa 1.9. (xem [11]) Ta nói rằng tính chất bao hàm (the containment property), kí hiệu là (CP ), đúng cho (A, B) ⊂ Z × Z, nếu với mỗi W ∈ N (0Z ), tồn tại V ∈ N (0Z ) sao cho [A \ (B + W )] + V ⊂ B + Θ. (1.11) Mệnh đề 1.11. Cho A là một tập con khác rỗng trong không gian Banach Z, Θ là một nón lồi với Θ \ l(Θ) 6= ∅. Nếu (CP ) đúng cho (A, Min (A | Θ)), thì Min (A | Θ) ⊂ GMin (A | Θ) ⊂ cl Min (A | Θ). (1.12) Một tập A ⊂ Z tương ứng được gọi là Θ-lồi (Θ-convex), Θ-đóng (Θ-closed) nếu tập A + Θ tương ứng là lồi, đóng. Đặt Θ+i = {z ∗ ∈ Z ∗ | hz ∗ , θi > 0 ∀ θ ∈ Θ \ {0}} . Định lý 1.6. Cho A là một tập compact yếu, Θ-lồi trong không gian Banach Z. Giả sử Θ là một nón nhọn thỏa mãn Θ+i 6= ∅. Nếu (CP ) đúng cho (A, Min (A | Θ)), thì tập GMin (A | Θ) liên thông tương ứng với tôpô yếu σ(Z, Z ∗ ). Mệnh đề 1.12. (xem [38, Theorem 4.1]) Cho Rm là không gian Euclide m-chiều. Giả sử Θ là một nón lồi, đóng, nhọn và A là một tập khác rỗng, Θ-đóng, Θ-lồi trong Rm . Khi đó, tập Min (A | Θ) co rút được. Định lý 1.7. Giả sử rằng Θ là một nón lồi, đóng, nhọn và A là một tập lồi, khác rỗng, Θ-đóng trong Rm . Nếu Min (A | Θ) khác rỗng, thì tập GMin (A | Θ) là liên thông cung. 8 Chương 2 Điều kiện tối ưu cho bài toán tối ưu véctơ với thứ tự suy rộng Trong chương này, chúng tôi sẽ thiết lập một số điều kiện tối ưu cho bài toán tối ưu véctơ với thứ tự suy rộng. Chương này được viết trên cơ sở các bài báo [1, 2]. 2.1. Một số kiến thức chuẩn bị Giả sử X là không gian Banach với chuẩn k · k. Không gian đối ngẫu của X được kí hiệu bởi X ∗ . Tôpô yếu∗ trong X ∗ được kí hiệu bởi w∗ . Nếu A : X → Y là toán tử tuyến tính liên tục giữa các không gian Banach, thì A∗ kí hiệu toán tử liên hợp của nó. Cho F : X ⇒ X ∗ ánh xạ đa trị giữa X và X ∗ . Giới hạn trên theo dãy theo nghĩa Painlevé-Kuratowski tại x̄ của F đối với tôpô chuẩn của X và tôpô yếu* của X ∗ được xác định bởi w∗ Lim sup F (x) = {x∗ ∈ X ∗ |∃ xk → x̄, x∗k −→ x∗ , x∗k ∈ F (xk ) ∀k ∈ N}. (2.1) x→x̄ Định nghĩa 2.1. Cho Ω ⊂ X, x̄ ∈ Ω, và ε > 0. (i) Tập các ε-véctơ pháp tuyến Fréchet của Ω tại x̄ được xác định bởi ( ) ∗ hx , x − x̄i N̂ε (x̄; Ω) := x∗ ∈ X ∗ | lim sup 6ε , k x − x̄ k Ω x→x̄ (2.2) Ω ở đó kí hiệu x − → x̄ có nghĩa là x → x̄ và x ∈ Ω. Ta gọi hình nón lồi đóng N̂ (x̄; Ω) := N̂0 (x̄; Ω) là nón pháp tuyến Fréchet của Ω tại x̄. (ii) Nón pháp tuyến Mordukhovich hay nón pháp tuyến qua giới hạn của Ω tại x̄ 9 là tập hợp bε (x, Ω). N (x̄, Ω) = Lim sup N (2.3) x→x̄ ε↓0 Không gian Banach X được gọi là không gian Asplund nếu mọi hàm lồi liên tục ϕ : Ω → R xác định trên một tập lồi mở Ω ⊂ X đều khả vi Fréchet trên một tập điểm trù mật trong Ω; xem [47, Definition 2.17, p. 196]. Định nghĩa 2.2. Cho f : X → R là hàm nhận giá trị trong tập số thực suy rộng, hữu hạn tại x̄. Với mỗi ε > 0, đặt   ∗ f (x) − f (x̄) − hx , x − x̄i ∂ˆε f (x̄) := x∗ ∈ X ∗ | lim inf > −ε . (2.4) x→x̄ kx − x̄k Các phần tử của tập hợp ở vế phải công thức này được gọi là các ε-dưới gradient Fréchet của f tại x̄, còn bản thân tập hợp đó được gọi là ε-dưới vi phân Fréchet ˆ (x̄) := ∂ˆ0 f (x̄) được gọi là dưới vi phân Fréchet của f tại của f tại x̄. Tập hợp ∂f x̄. Định nghĩa 2.3. Tập hợp ∂f (x̄) := Limsup ∂ˆε f (x) f x→ − x̄ (2.5) ε↓0 được gọi là dưới vi phân Mordukhovich, hay dưới vi phân qua giới hạn, của f tại x̄. Tập hợp (2.6) ∂ ∞ f (x̄) := Limsup λ∂ˆε f (x) f x→ − x̄ ε,λ↓0 được gọi là dưới vi phân qua giới hạn suy biến của f tại x̄. Định nghĩa 2.4. Tập Ω ⊂ X được gọi là compact pháp tuyến theo dãy (SNC) tại Ω x̄ nếu với mọi dãy εk ↓ 0, xk − → x̄ và x∗k ∈ N̂εk (xk , Ω) có     ∗ ∗ ω ∗ xk −→ 0 khi k → 0 =⇒ kxk k → 0 khi k → 0 , ở đó ta có thể bỏ qua εk nếu X là không gian Asplund và Ω là đóng địa phương tại x̄. Định nghĩa 2.6. Ánh xạ đa trị F : X ⇒ Y được gọi là compact pháp tuyến theo dãy (SNC) tại (x̄, ȳ) ∈ gphF nếu đồ thị của nó có thuộc tính đó. Ta nói 10 F là compact pháp tuyến một phần theo dãy (PSNC) tại (x̄, ȳ) nếu với mọi dãy (εk , xk , yk , x∗k , yk∗ ) ∈ [0, ∞) × (gphF ) × X ∗ × Y ∗ thoả mãn εk ↓ 0, (xk , yk ) → (x̄, ȳ), (x∗k , −yk∗ ) ∈ N̂εk ((xk , yk ); gphF ), ω∗ x∗k −→ 0 và kyk∗ k → 0, ta có kx∗k k → 0 khi k → ∞. Định nghĩa 2.8. Cho ánh xạ đa trị F : X ⇒ Y với domF 6= ∅. (i) Lấy (x, y) ∈ X × Y và ε ≥ 0, tập các ε-đối đạo hàm của F tại (x, y) là ánh xạ b ε∗ F (x, y) : Y ∗ ⇒ X ∗ được xác định bởi đa trị D n o ∗ ∗ ∗ ∗ ∗ ∗ b b Dε F (x, y)(y ) := x ∈ X |(x , −y ) ∈ Nε ((x, y); gphF ) . (2.7) b ∗ F := D b 0∗ là đối đạo hàm Fréchet của F tại (x, y). Ta gọi ánh xạ đa trị D (ii) Đối đạo hàm Mordukhovich , hay đối đạo hàm qua giới hạn, của F tại (x̄, ȳ) ∈ ∗ gphF là ánh xạ đa trị DN F (x̄, ȳ) : Y ∗ ⇒ X ∗ được xác định bởi ∗ DN F (x̄, ȳ)(y ∗ ) := {x∗ ∈ X ∗ |(x∗ , −y ∗ ) ∈ N ((x̄, ȳ); gphF )} . (2.8) ∗ (iii) Đối đạo hàm hỗn hợp của F tại (x̄, ȳ) ∈ gphF là ánh xạ đa trị DM F (x̄, ȳ) : ∗ ∗ Y ⇒ X được xác định bởi ∗ DM F (x̄, ȳ)(y ∗ ) := Lim sup D̂ε∗ F (x, y)(y ∗ ). (2.9) (x,y)→(x̄,ȳ) ω∗ y∗ − →x∗ ε↓0 Định nghĩa 2.10. (xem [47, Definition 2.1]) Cho Ω1 , Ω2 là các tập con khác rỗng trong không gian Banach Z và z̄ ∈ Ω1 ∩ Ω2 . Chúng ta nói rằng z̄ là một điểm cực trị địa phương của hệ {Ω1 , Ω2 } nếu tồn tại một lân cận U của x̄ và một dãy {ak } thỏa mãn ak → 0 khi k → ∞ và Ω1 ∩ (Ω2 − ak ) ∩ U = ∅ ∀k ∈ N. (2.10) Khi đó {Ω1 , Ω2 , z̄} được gọi là một hệ cực trị trong Z. Định lý 2.3. (Nguyên lý cực trị, xem [47, Theorem 2.20]) Nếu z̄ là một điểm cực trị của các tập đóng {Ω1 , Ω2 } trong không gian Asplund Z, thì nó thỏa mãn các quan hệ sau: với mỗi  > 0, tồn tại xi ∈ Z và x∗i ∈ Z ∗ thỏa mãn xi ∈ Ωi ∩ (z̄ + B), x∗i ∈ N̂ (xi , Ωi ) với i = 1, 2, kx∗1 + x∗2 k ≤ , và 1 −  ≤ kx∗1 k + kx∗2 k ≤ 1 + . 11 2.2. Các điều kiện tối ưu cho điểm hữu hiệu suy rộng Định lý 2.4. (Điều kiện cần) Cho Z là một không gian Asplund, A ⊂ Z là một tập con đóng khác rỗng và Θ ⊂ Z là một tập con đóng và chứa gốc. Giả sử rằng, A là SNC tại z̄ hoặc Θ là SNC tại 0. Nếu z̄ ∈ GMin (A | Θ), thì tồn tại z ∗ ∈ Z ∗ thỏa mãn 0 6= z ∗ ∈ N (z̄; A) ∩ N (0; Θ). (2.11) Hệ quả 2.1. Cho Z là một không gian Asplund và ∅ 6= A ⊂ Z, 0Z ∈ Θ ⊂ Z, z̄ ∈ GMin (A | Θ). Giả sử rằng A + Θ và Θ là các tập đóng, A + Θ là SNC tại z̄ hoặc Θ là SNC tại 0Z , và điều kiện sau Θ+Θ=Θ (2.12) nghiệm đúng. Khi đó, tồn tại z ∗ ∈ Z ∗ thỏa mãn 0 6= z ∗ ∈ N (z̄; A + Θ) ∩ N (0; Θ). (2.13) Định lý 2.5. (Điều kiện cần và đủ) Cho Z là một không gian Asplund, ∅ 6= A ⊂ Z, 0Z ∈ Θ ⊂ Z và z̄ ∈ A. Giả sử rằng A + Θ là một tập đóng trong Z và hoặc A + Θ là SNC tại z̄, hoặc dim Z < ∞. Khi đó, z̄ ∈ GMin (A | Θ) khi và chỉ khi tồn tại z ∗ ∈ Z ∗ thỏa mãn 0 6= z ∗ ∈ N (z̄; A + Θ) ∩ N (0; Θ). (2.14) Định lý 2.6. (Điều kiện đủ dưới giả thiết về tính lồi) Cho Z là một không gian Banach, ∅ 6= A ⊂ Z, 0Z ∈ Θ ⊂ Z. Giả sử rằng A, Θ là các tập lồi và int Θ 6= ∅. Nếu tồn tại z ∗ ∈ Z ∗ thỏa mãn 0 6= z ∗ ∈ N (z̄; A) ∩ N (0, Θ), (2.15) thì z̄ ∈ GMin (A | Θ). 2.3. Các điều kiện tối ưu cho bài toán tối ưu véctơ với thứ tự suy rộng Mục này trình bày một số điều kiện đủ tối ưu theo thứ tự suy rộng. Như trong lý thuyết tối ưu véctơ cổ điển, ý tưởng xây dựng điều kiện đủ ở đây vẫn là sử dụng tính lồi, hoặc tính lồi địa phương, của tập hợp và của hàm véctơ theo thứ tự bộ phận. 12 2.3.1. Điều kiện cần cực trị Trước hết chúng ta trình bày một kết quả cơ bản trong [48] về các điều kiện cần cực trị cho nghiệm tối ưu theo thứ tự suy rộng với ràng buộc hình học. Định lý 2.8. (Điều kiện cần, xem [48, Theorem 5.59, p. 74]) Cho f : X → Z là một ánh xạ giữa các không gian Asplund, và các tập hợp Ω ⊂ X, Θ ⊂ Z sao cho x̄ ∈ Ω, 0Z ∈ Θ. Giả sử x̄ là một điểm (f, Θ)-tối ưu địa phương trên tập ràng buộc Ω. Khi đó, ta có các khẳng định sau: (i) Giả sử rằng tập hợp ε(f, Ω, Θ) := {(x, z) ∈ X × Z | z ∈ f (x) + Θ, x ∈ Ω} là đóng địa phương tại (x̄, z̄) với z̄ := f (x̄), và dim Z < ∞. Khi ấy, tồn tại z ∗ ∈ Z ∗ thỏa mãn (0, z ∗ ) ∈ N ((x̄, z̄); ε(f, Ω, Θ)), z ∗ = 6 0. (2.16) ∗ Điều này kéo theo z ∗ ∈ N (0; Θ); và nó cũng kéo theo 0 ∈ DN fΩ (x̄)(z ∗ ) nếu như hạn chế fΩ của f trên Ω là liên tục trong một lân cận của x̄, Ω là đóng địa phương tại x̄, và Θ là đóng địa phương tại 0. Thêm vào đó, nếu fΩ Lipschitz địa phương tại x̄, thì (2.16) tương đương với 0 ∈ ∂hz ∗ , fΩ i(x̄), z ∗ ∈ N (0; Θ) \ {0}. (2.17) (ii) Giả sử fΩ liên tục trong một lân cận của x̄, Ω là đóng địa phương tại x̄, và Θ là đóng địa phương tại 0, và một trong hai điều kiện sau được thỏa mãn: (a) Θ là SNC tại 0,
−1 (b) fΩ là PSNC tại (z̄, x̄). Khi đó, tồn tại z ∗ ∈ Z ∗ thỏa mãn ∗ 0 6= z ∗ ∈ N (0; Θ) ∩ ker DN fΩ (x̄). (2.18) Điều kiện (2.18) này tương đương với (2.17) và (2.16), nếu như ánh xạ fΩ là Lipschitz địa phương tại x̄ và chính quy đối đạo hàm mạnh tại điểm này. 2.3.2. Điều kiện đủ tối ưu cho nghiệm toàn cục Định lý 2.9. Cho f : X → Z là một ánh xạ giữa các không gian Banach, cho Ω ⊂ X, và cho tập hợp Θ ⊂ Z với 0Z ∈ Θ. Giả sử rằng Θ là lồi, có phần trong khác rỗng, và tập ε(f, Ω, Θ) := {(x, z) ∈ X × Z | z ∈ f (x) + Θ, x ∈ Ω} 13 là lồi. Khi đó, nếu tại x̄ ∈ Ω và tồn tại z ∗ ∈ Z ∗ thỏa mãn (0, z ∗ ) ∈ N ((x̄, z̄); ε(f, Ω, Θ)), z ∗ 6= 0, (2.19) với z̄ := f (x̄), thì x̄ là nghiệm (f, Θ)-tối ưu toàn cục trên Ω. Định lý 2.10. Cho f : X → Z là một ánh xạ giữa các không gian Banach, Ω ⊂ X là tập lồi, và cho tập hợp Θ ⊂ Z với 0 ∈ Θ. Giả sử rằng Θ là một nón lồi với intΘ 6= ∅, và ánh xạ f là Θ-lồi trên Ω, tức là
(1 − λ)f (x) + λf (x0 ) ∈ f (1 − λ)x + λx0 + Θ, ∀x, x0 ∈ Ω, ∀λ ∈ (0, 1). Khi đó, nếu x̄ ∈ Ω và tồn tại z ∗ ∈ Z ∗ thỏa mãn điều kiện (0, z ∗ ) ∈ N ((x̄, z̄); ε(f, Ω, Θ)), z ∗ 6= 0 với z̄ := f (x̄), thì x̄ là nghiệm (f, Θ)-tối ưu toàn cục trên Ω. 2.3.3. Điều kiện đủ tối ưu cho nghiệm địa phương Định lý 2.11. Cho f : X → Z là một ánh xạ giữa các không gian Banach, Ω ⊂ X, Θ ⊂ Z, 0 ∈ Θ và x̄ ∈ Ω. Giả sử Θ là một tập lồi, có phần trong khác rỗng. Nếu tồn tại δ ∈ (0, +∞] sao cho tập ε(f, Ωx̄,δ , Θ) := {(x, z) ∈ X × Z | z ∈ f (x) + Θ, x ∈ Ωx̄,δ }, với z̄ := f (x̄) và Ωx̄,δ := {x ∈ Ω | kx− x̄k ≤ δ)}, là lồi. Khi đó, nếu tồn tại z ∗ ∈ Z ∗ thỏa mãn (0, z ∗ ) ∈ N ((x̄, z̄); ε(f, Ω, Θ)), z ∗ 6= 0, (2.20) thì x̄ là nghiệm (f, Θ)-tối ưu địa phương trên Ω. Định nghĩa 2.12. Cho f : X → Z là một ánh xạ giữa các không gian Banach, Ω ⊂ X , Θ ⊂ Z sao cho 0Z ∈ Θ. Giả sử Ω là một tập lồi địa phương tại x̄. Ta nói ánh xạ f là Θ-lồi địa phương tại x̄ nếu tồn tại một lân cận lồi U của x̄ thỏa mãn
(1 − λ)f (x) + λf (x0 ) ∈ f (1 − λ)x + λx0 + Θ, ∀x, x0 ∈ U ∩ Ω, ∀λ ∈ (0, 1). Định lý 2.12. Cho f : X → Z là một ánh xạ giữa các không gian Banach, và các tập hợp Ω ⊂ X, Θ ⊂ Z sao cho 0Z ∈ Θ. Giả sử rằng Ω là một tập lồi địa phương tại x̄ ∈ Ω, Θ là một nón lồi với intΘ 6= ∅, và ánh xạ f là Θ-lồi địa phương tại x̄. Khi đó, nếu tồn tại z ∗ ∈ Z ∗ thỏa mãn (0, z ∗ ) ∈ N ((x̄, z̄); ε(f, Ω, Θ)), z ∗ 6= 0 với z̄ := f (x̄), thì điểm x̄ là nghiệm (f, Θ)-tối ưu địa phương trên Ω. 14 Chương 3 Tính ổn định nghiệm của bài toán tối ưu véctơ Chương này trình bày một số kết quả về tính ổn định của bài toán tối ưu véctơ sử dụng khái niệm nghiệm Pareto tương đối như là một trường hợp riêng của nghiệm tối ưu theo thứ tự suy rộng. Chương này được viết trên cơ sở bài báo [4]. 3.1. Về khái niệm điểm hữu hiệu Pareto tương đối Định nghĩa 3.1. (xem [2]) Cho Z là một không gian Banach, A ⊂ Z là một tập con khác rỗng, và C là một nón lồi trong Z. Ta nói rằng (i) z̄ là một điểm hữu hiệu Pareto tương đối (relative efficient point) của A tương ứng với C nếu A ∩ (z̄ − ri C) = ∅ và ri C 6= ∅, (3.1) (ii) z̄ là một điểm hữu hiệu Pareto giả tương đối (pseudo/intrinsic relative efficient point) của A tương ứng với C nếu A ∩ (z̄ − pri C) = ∅ và pri C 6= ∅, (3.2) (iii) z̄ là một điểm hữu hiệu Pareto tựa tương đối (quasi relative efficient point) của A tương ứng với C nếu A ∩ (z̄ − qri C) = ∅ và qri C 6= ∅. (3.3) Định nghĩa 3.2. (xem [46]) Một tập lồi khác rỗng A ⊂ Z được gọi là tròn nếu biên của A không chứa một đoạn thẳng. Mệnh đề 3.1. Giả sử rằng Z là một không gian Banach và C là một nón lồi với ri C 6= ∅ và 0 ∈ / ri C. Nếu A là một tập tròn, thì RMin (A | C) = Min (A | C). 15 (3.4) Cho A là một tập con khác rỗng trong không gian Banach Z và B ⊂ A. Giả sử rằng C ⊂ Z là một nón lồi. Để cho ngắn gọn, ta viết Min A và RMin A tương ứng thay cho Min (A | C) và RMin (A | C). Khái niệm sau là một dạng yếu hơn của tính chất bao hàm cho cặp (A, B). Định nghĩa 3.3. Ta nói rằng tính chất bao hàm tương đối (the relative containment property), kí hiệu là (RCP ), đúng cho cặp (A, B) ⊂ Z × Z nếu với mỗi W ∈ N (0Z ) tồn tại V ∈ N (0Z ) sao cho [A \ (B + W )] + [V ∩ aff (C)] ⊂ B + C. (3.5) Mệnh đề sau cho ta một đặc trưng của tính (RCP ) khi ri C 6= ∅. Mệnh đề 3.2. Nếu ri C 6= ∅, thì các khẳng định sau là tương đương (i) (RCP ) đúng cho (A, B); (ii) Với mỗi W ∈ N (0Z ) tồn tại W0 ∈ N (0Z ) sao cho với mọi y ∈ A \ (B + W ) tồn tại ηy ∈ B và cy ∈ C thỏa mãn y = ηy + cy , (cy + W0 ) ∩ aff (C) ⊂ C. Mệnh đề sau khẳng định rằng nếu (RCP ) được thỏa mãn thì tập điểm hữu hiệu Pareto tương đối sẽ trù mật của trong tập điểm hữu hiệu Pareto. Mệnh đề 3.3. Cho A là một tập con khác rỗng trong Z và C ⊂ Z là một nón lồi với ri C 6= ∅. Nếu (RCP ) đúng cho (A, Min A), thì Min A ⊂ RMin A ⊂ cl Min A. Bổ đề 3.1. Giả sử rằng A là một tập đa diện trong Rm được xác định bởi A = {z ∈ Rm | hai , zi ≤ bi , i = 1, 2, ..., N }, (3.6) với ai ∈ Rm và bi ∈ R với mọi i ∈ I =: {1, 2, ..., N }. Cho C ⊂ Z là một nón lồi đóng nhọn. Khi đó, RMin A khác rỗng khi và chỉ khi Rec (A) ∩ (−ri C) = ∅, ở đó Rec (A) là nón lùi xa của A và được xác định bởi Rec (A) = {z ∈ Rm | hai , zi ≤ 0, i ∈ I}. Định lý 3.1. Nếu A là một tập đa diện được cho bởi (3.6) và C ⊂ Rm là một nón lồi đóng nhọn, thì RMin A đóng. 16 3.2. Sự hội tụ trên của tập điểm hữu hiệu Pareto tương đối Cho Z là một không gian Banach, {An } là một dãy tập con trong Z và A ⊂ Z là một tập con khác rỗng. Chúng ta nhắc lại một số khái niệm hội tụ của dãy tập hợp. • Sự hội tụ theo nghĩa Kuratowski-Painlevé: Giới hạn dưới và giới hạn trên theo nghĩa Kuratowski-Painlevé của dãy {An } được định nghĩa tương ứng như sau: Lim inf An := {z ∈ Z , | z = lim zn , zn ∈ An với mọi n đủ lớn}, n→∞ Lim sup An := {z ∈ Z , | z = lim zk , zk ∈ Ank với {Ank } ⊂ {An } nào đó}. n→∞ Nếu Lim sup An ⊂ A ⊂ Lim inf An , thì ta nói {An } hội tụ đến A theo nghĩa K → A. Khi các giới hạn được xét theo tôpô Kuratowski-Painlevé và kí hiệu là An − yếu trên Z, thì ta kí hiệu giới hạn dưới và giới hạn trên tương ứng bởi w−Lim inf An và w − Lim sup An . Nếu w − Lim sup An ⊂ A ⊂ Lim inf An , thì ta nói rằng {An } M hội tụ đến A theo nghĩa Mosco và kí hiệu An −→ A. Cho x ∈ Z và A, B là các tập con khác rỗng trong Z. Định nghĩa d(x, A) = inf d(x, a) (d(x, ∅) = ∞); a∈A e(A, B) = sup d(a, B) (e(∅, B) = 0, e(∅, ∅) = 0, e(A, ∅) = ∞); a∈A h(A, B) = max{e(A, B), e(B, A)}; eρ (A, B) = e(A ∩ Bρ , B) Bρ = B(0, ρ); hρ (A, B) = max{eρ (A, B), eρ (B, A)}. • Sự hội tụ theo nghĩa Wijsman: Ta nói rằng {An } tội tụ đến A theo nghĩa Wijsman nếu lim d(An , x) = d(A, x) ∀x ∈ Z, n→∞ ở đó d(A, x) = inf d(a, x). a∈A • Sự hội tụ theo nghĩa Hausdorff: Ta nói rằng dãy {An } ⊂ Z hội tụ đến A theo nghĩa Hausdorff nếu lim h(An , A) = 0. n→∞ 17 Điều kiện lim e(An , A) = 0 được gọi là hội tụ trên theo nghĩa Hausdorff và n→∞ lim e(A, An ) = 0 được gọi là hội tụ dưới theo nghĩa Hausdorff. n→∞ • Sự hội tụ theo nghĩa Attouch-Wets: Ta nói rằng dãy {An } ⊂ Z hội tụ đến A theo nghĩa Attouch-Wets nếu lim hρ (An , A) = 0 n→∞ với mọi ρ > 0. Chúng ta có thể chia sự hội tụ này thành hai phần: hội tụ trên và hội tụ dưới theo nghĩa Attouch-Wets tương ứng như sau: lim eρ (An , A) = 0, n→∞ và lim eρ (A, An ) = 0. n→∞ Sonntag và Zălinescu [58] đã chỉ ra rằng sự hội tụ trên theo nghĩa của AttouchWets tương đương với lim inf d(An , B) ≥ d(A, B), n→∞ với mỗi tập bị chặn B, ở đó d(A, B) := inf inf d(a, b). a∈A b∈B Bổ đề 3.2. Giả sử Z là một không gian Banach và C ⊂ Z là một tập lồi có phần trong tương đối khác rỗng. Khi đó, z ∈ ri C khi và chỉ khi với mọi y ∈ C, tồn tại µ > 1 sao cho (1 − µ)y + µz ∈ C. Cho {Cn } và C là các nón lồi trong Z. Để cho ngắn gọn, ta viết RMin A, RMin An , Min A, Min An , WMin A và WMin An tương ứng thay cho RMin (A | C), RMin (An | Cn ), Min (A | C), Min (An | Cn ), WMin (A | C) và WMin (An | Cn ). Định lý 3.2. Cho (Cn ) và C là các nón lồi trong Z với phần trong tương đối khác rỗng. Nếu K (i) An − → A, (ii) Lim sup Cnc ⊂ (ri C)c , thì Lim sup RMin An ⊂ RMin A. 18