ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC SƯ PHẠM ——————–o0o——————– NGUYỄN THU MY BÀI TOÁN TỐI ƯU VỚI TẬP CHẤP NHẬN ĐƯỢC LỒI LUẬN VĂN THẠC SĨ TOÁN HỌC THÁI NGUYÊN - 2020 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC SƯ PHẠM ——————–o0o——————– NGUYỄN THU MY BÀI TOÁN TỐI ƯU VỚI TẬP CHẤP NHẬN ĐƯỢC LỒI Chuyên ngành: Giải Tích Mã số: 8460102 LUẬN VĂN THẠC SĨ TOÁN HỌC Người hướng dẫn khoa học GS.TS ĐỖ VĂN LƯU THÁI NGUYÊN - 2020 Lời cam đoan Tôi xin cam đoan cơng trình nghiên cứu khoa học độc lập riêng thân hướng dẫn khoa học GS TS Đỗ Văn Lưu Các nội dung nghiên cứu, kết luận văn trung thực chưa cơng bố hình thức trước Ngồi ra, luận văn tơi có sử dụng số kết tác giả khác có trích dẫn thích nguồn gốc Nếu phát gian lận xin chịu trách nhiệm nội dung luận văn Thái Nguyên, ngày 15 tháng năm 2020 Tác giả Nguyễn Thu My Xác nhận Xác nhận khoa chuyên môn người hướng dẫn GS TS Đỗ Văn Lưu i Lời cảm ơn Trong trình học tập nghiên cứu để hồn thành luận văn tơi nhận giúp đỡ nhiệt tình người hướng dẫn, GS TS Đỗ Văn Lưu Tôi muốn gửi lời cảm ơn mơn Giải tích, Khoa Tốn, tạo điều kiện thuận lợi, hướng dẫn, phản biện để tơi hồn thành tốt luận văn Do thời gian có hạn, thân tác giả cịn hạn chế nên luận văn có thiếu sót Tác giả mong muốn nhận ý kiến phản hồi, đóng góp xây dựng thầy cơ, bạn Tôi xin chân thành cảm ơn! Thái Nguyên, ngày 15 tháng năm 2020 Tác giả Nguyễn Thu My ii Mục lục Lời cam đoan i Lời cảm ơn ii Bảng ký hiệu v Mở đầu 1 Các kiến thức bổ trợ 1.1 Dưới vi phân suy rộng 1.2 Điều kiện quy 17 Đặc trưng nón pháp tuyến tập chấp nhận điều kiện tối ưu 20 2.1 Đặc trưng nón pháp tuyến tập chấp nhận 20 2.2 Điều kiện Karush-Kuhn-Tuker 24 2.2.1 Điều kiện Karush-Kuhn-Tucker qua Điều kiện Fritz John 24 2.2.2 Điều kiện Karush-Kuhn-Tucker không qua Điều kiện Fritz John 25 2.2.3 Tính bị chặn nhân tử Karush-Kuhn-Tucker 28 2.3 Đặc trưng tập nghiệm 29 2.3.1 Dưới vi phân suy rộng điểm tối ưu 29 2.3.2 Xấp xỉ tuyến tính 31 2.3.3 Ví dụ 32 iii Kết luận 34 Tài liệu tham khảo 36 iv Bảng ký hiệu co Ω bao lồi tập Ω int Ω phần tập Ω bd Ω biên tập Ω cl Ω bao đóng tập Ω cone(Ω) nón lồi sinh Ω DΩ (x) nón phương chấp nhận tập Ω x TΩ (x) nón tiếp tuyến tập Ω x NΩ (x) nón pháp tuyến tập Ω x ∅ tập rỗng h+ (x; d) đạo hàm theo phương Dini h x theo phương d h (x; d) đạo hàm theo phương h x theo phương d h◦ (x; d) đạo hàm suy rộng Clarke h x theo phương d ∂ ◦ h(x) vi phân Clarke h x (CQ) điều kiện quy (SCQ) điều kiện quy Slater (LICQ) điều kiện quy độc lập tuyến tính (GLCQ) điều kiện quy Lasserre suy rộng v Mở đầu Lý chọn đề tài Bài tốn tối ưu có hàm mục tiêu lồi và hàm ràng buộc bất đẳng thức lồi,các ràng buộc đẳng thức affine nhiều tác giả nghiên cứu thu nhiều kết đẹp Bài toán tối ưu với hàm ràng buộc không lồi, không khả vi, khơng Lipschitz địa phương, có tập chấp nhận tập lồi đề tài nhiều tác giả quan tâm nghiên cứu A Kabgani cộng [6] nghiên cứu tốn tối ưu khơng trơn có tập chấp nhận lồi Điều kiện Karush-Kuhn-Tuker với điều kiện quy thiết lập điều kiện tối ưu cho tốn tối ưu khơng trơn với tập chấp nhận tập lồi Đây vấn đề nghiên cứu có tính thời Chính vậy, tơi chọn đề tài: "Bài tốn tối ưu với tập chấp nhận lồi" Nội dung đề tài Luận văn trình bày kết nghiên cứu A.Kabgani, M Soleimanidamaneh, M.Zamani [6] cho toán tối ưu khơng trơn có tập chấp nhận lồi bao gồm: đặc trưng cho nón pháp tuyến tập chấp nhận được, điều kiện tối ưu qua vi phân suy rộng tính bị chặn tập nhân tử Karush-Kuhn-Tucker Luận văn bao gồm phần mở đầu, hai chương, kết luận danh mục tài liệu tham khảo Chương với tiêu đề "Các kiến thức bổ trợ" trình bày kết vi phân suy rộng điều kiện quy cho tốn tối ưu với tập chấp nhận lồi Chương với tiêu đề "Đặc trưng nón pháp tuyến tập chấp nhận điều kiện tối ưu" trình bày kết đặc trưng nón pháp tuyến tập chấp nhận được, điều kiện Karush-Kuhn-Tuker đặc trưng tập nghiệm Luận văn thực Trường Đại học Sư phạm - Đại học Thái Nguyên hoàn thành hướng dẫn GS.TS Đỗ Văn Lưu Tác giả xin bày tỏ lòng biết ơn chân thành sâu sắc tới thầy hướng dẫn khoa học mình, người đặt vấn đề nghiên cứu, dành nhiều thời gian hướng dẫn tận tình giải đáp thắc mắc tác giả suốt trình làm luận văn Tác giả học tập nhiều kiến thức chuyên ngành bổ ích cho cơng tác nghiên cứu thân Tác giả xin bày tỏ lòng cảm ơn sâu sắc tới thầy giáo, cô giáo tham gia giảng dạy lớp cao học Toán K26, nhà trường phịng chức trường, khoa Tốn, trường Đại học Sư phạm - Đại học Thái Nguyên quan tâm giúp đỡ tác giả suốt thời gian học tập trường Thái Nguyên, ngày 15 tháng năm 2020 Tác giả luận văn Nguyễn Thu My Chương Các kiến thức bổ trợ Chương trình bày số kiến thức vi phân suy rộng điều kiện quy Các kiến thức chương tham khảo [1, 2], [5, 6] 1.1 Dưới vi phân suy rộng Phần trình bày khái niệm vi phân suy rộng (convexificator), vi phân suy rộng quy cho hàm giá trị thực mở rộng V Jeyakumar D.T Luc [5] Giả sử X không gian Banach f : X → R hàm giá trị thực mở rộng, R := R ∪ {±∞} Khơng gian đối ngẫu X kí hiệu X ∗ X ∗ trang bị tô pô yếu∗ Bao lồi bao lồi đóng tập A X ∗ kí hiệu tương ứng co(A) co(A) Giả sử x ∈ X f hữu hạn Định nghĩa 1.1 Đạo hàm theo phương Dini f x theo phương v định nghĩa tương ứng f − (x, v) := lim inf f (x + tv) − f (x) , t f + (x, v) := lim sup f (x + tv) − f (xt) t t↓0 t↓0 Trong trường hợp f + (x; v) = f − (x; v), giá trị chung chúng ký hiệu f (x; v) gọi đạo hàm Dini f x theo phương Do đó, theo định nghĩa nón pháp tuyến tập lồi, ta có ∂ ∗ gi (x) ⊆ NK (x) Vậy cl cone(∪i∈I(x) ∂ ∗ gi (x)) ⊆ NK (x) (2.2) Đặt Γ(x) := ∪i∈I(x) ∂ ∗ gi (x) Để chứng minh chiều ngược lại, ta chứng minh Γ◦ (x) ⊆ TK (x) Lấy y ∈ int K Khi tồn > cho với d ∈ Rn với d ≤ 1, y + d ∈ K Do từ tính lồi K, với i ∈ I(x) d ∈ Rn với d ≤ 1, gi+ (x; d + y − x) ≤ Vì ζ, y − x ≤ − ζ, d , ∀d ∈ Rn ; d ≤ 1, ∀i ∈ I(x), ∀ζ ∈ ∂ ∗ gi (x) Đặt d = ζ ζ , ta ζ, y − x ≤ − ζ , ∀i ∈ I(x), ∀ζ ∈ ∂ ∗ gi (x) Do đó, ∈ / ∂ ∗ gi (x) tính đóng ∂ ∗ gi (x), ta có gi+ (x; y − x) = sup ζ, y − x ≤ − ζ∈∂ ∗ gi (x) inf ζ∈∂ ∗ gi (x) ζ < Vì vậy, gi+ (x; y − x) < 0, ∀y ∈ int K, ∀i ∈ I(x) (2.3) Cho d ∈ Γ◦ (x) y ∈ int K Từ (2.3) định nghĩa vi phân suy rộng quy trên, ta có gi+ (x; d + t(y − x)) ≤ gi+ (x; d) + tgi+ (x; y − x) < 0, ∀t > 0, ∀i ∈ I(x) Vì vậy, với λ đủ nhỏ, gi (x + λ(d + t(y − x))) ≤ với t > i ∈ I(x) Mặt khác, xét t > 0, với i ∈ / I(x), giả thiết nửa liên tục trên, ta có 22 gi (x + λ(d + t(y − x))) ≤ với λ đủ nhỏ Do d + t(y − x) ∈ DK (x) với t > Điều kéo theo d ∈ cl DK (x) = TK (x) Do đó, Γ◦ (x) ⊆ TK (x) Vì vậy, NK (x) = TK◦ (x) ⊆ Γ◦◦ (x) = cl cone(Γ(x)) Theo (2.2) suy NK (x) = cl cone(∪i∈I(x) ∂ ∗ gi (x.) Định lý chứng minh Nhận xét 2.1 Với giả thiết Định lý 2.2, cone (Γ(x)) đóng, định lý cone(∪i∈I(x) ∂ ∗ gi (x)) = cone(∪i∈I(x) co(∂ ∗ gi (x))), với d ∈ NK (x), λi co(∂ ∗ gi (x)), d∈ i∈I(x) / co(∂ ∗ gi (x)) với với λi ≥ 0, (i ∈ I(x)) Hơn nữa, theo (2.3), ∈ i ∈ I(x) Vì vậy, cone(Γ(x)) đóng miễn ∂ ∗ gi (x) bị chặn với i ∈ I(x) Để thuận tiện nhận kết sâu sắc hơn, số định lý ta sử dụng sở nón sinh vi phân suy rộng Cho trước nón C, tập B ⊆ C gọi sở C ∈ / B với c ∈ C\{0} có b ∈ B t > cho c = tb Giả sử giả thiết Định lý 2.2 cone(∂ ∗ gi (x)) đóng với i ∈ I(x) Từ (2.3), ta có ζ, y − x < 0, ∀y ∈ int K, ∀ζ ∈ cone(∂ ∗ gi (x))\{0}, ∀i ∈ I(x) (2.4) Vì vậy, cone(∂ ∗ gi (x)) nón nhọn đóng, có sở đóng lồi bị chặn Bi (xem Luc [4], Remark 1.6), vậy, cone(∪i∈I(x) ∂ ∗ gi (x)) = cone(∪i∈I(x) Bi ) Hệ 2.1 Giả sử giả thiết Định lý 2.2 Nếu cone(∂ ∗ gi (x)) đóng với i ∈ I(x), NK (x) = cone(∪i∈I(x) Bi ) 23 2.2 Điều kiện Karush-Kuhn-Tuker 2.2.1 Điều kiện Karush-Kuhn-Tucker qua Điều kiện Fritz John Ta nhắc lại khái niệm điểm Fritz John Karush-Kuhn-Tucker Định nghĩa 2.1 (i) Điểm x ∈ K gọi điểm Fritz John (FJ) (1.2) tồn λ0 , λ1 , · · · , λm ≥ không đồng thời 0, cho m ∗ λi co(∂ ∗ gi (x)), ∈ λ0 co(∂ f (x)) + (2.5) i=1 λi gi (x) = 0, ∀i ∈ I (2.6) (ii) Điểm x ∈ K điểm Karush-Kuhn-Tucker (KKT) (1.2) điểm FJ với λ0 = Định lí 2.3 Giả sử x ∈ K điểm FJ Nếu int K = ∅ (GLCQ) đúng, x điểm KKT Chứng minh Giả sử λ0 = (2.5) Ta có = m i=1 λi ζi , với ζi ∈ co(∂ ∗ gi (x)), i = 1, 2, · · · , m Do λi ζi , y − x , ∀y ∈ K, 0= i∈J J := {i ∈ I : λi > 0} ⊆ I(x) Với i ∈ I(x) y ∈ K, K lồi, gi+ (x; y − x) ≤ 0.Từ suy ζi ; y − x ≤ Như vậy, ζi , y − x = 0, ∀y ∈ K, ∀i ∈ J Bởi tồn xˆ ∈ int K, với v ∈ Rn t > đủ nhỏ ta có xˆ + tv ∈ K; đó, ζi , xˆ + tv − x = 0, ∀i ∈ J Vì vậy, ζi , xˆ − x + ζi , tv = 0.Từ suy ζi , v = 0, ∀i ∈ J 24 Do với v ∈ Rn i ∈ J, ζi , v = Do đó, ζi = với i ∈ J Vì vậy, ∈ co(∂ ∗ gi (x)) với i ∈ J Mặt khác, (GLCQ) int K = ∅, cách tương tự chứng minh định lý 2.2, ta suy (2.3), đó, 0∈ / co(∂ ∗ gi (x)) với i ∈ J Mâu thuẫn λ0 > khơng tính tổng quát lấy λ0 = 2.2.2 Điều kiện Karush-Kuhn-Tucker không qua Điều kiện Fritz John Nhiều tác giả nghiên cứu điều kiện Karush-Kuhn-Tucker cho nghiệm tối ưu (1.2) Họ thiết lập điều kiện Fritz John đưa vào điều kiện quy để nhận điều kiện Karush-Kuhn-Tucker Ta có sơ đồ sau: Cực tiểu ⇒ (FJ) ⇒ (KKT) Bây sử dụng đặc trưng NK (x), chứng minh Định lý 2.2, để nhận điều kiện Karus-Kuhn-Tucker mà khơng cần sử dụng điều kiện Fritz John Ta có sơ đồ đây: cực tiểu + (đặc trưng NK ) ⇒ (KKT) Định lí 2.4 Giả sử f có vi phân suy rộng quy ∂ ∗ f (x) x ∈ K Nếu x nghiệm tối ưu (1.2) ∈ cl (co(∂ ∗ f (x)) + NK (x)) Chứng minh Ta có sup η, d ≥ 0, ∀d ∈ DK (x) (2.7) η∈∂ ∗ f (x) Bằng chứng minh phản chứng ta giả sử f + (x; d) = sup η, d < với η∈∂ ∗ f (x) d ∈ DK (x) Điều kéo theo tồn t > thỏa mãn x + td ∈ K f (x + td) < f (x) Điều mâu thuẫn với tính tối ưu x Từ (2.7) ta có sup η, d ≥ 0, ∀d ∈ clDK (x) = TK (x) η∈∂ ∗ f (x) 25 Do sup η∈co(∂ ∗ f (x)) η, d + ITK (x) (d) ≥ 0, ∀d ∈ Rn , ITK (x) (.) hàm (ITK (x) (d)(bằng d ∈ TK (x) ∞ d ∈ / TK (x)) Theo Hiriart-Urruty Lemarecha ([4], Example V2.3.1), ITK (x) (d) = η, d với d Do sup η∈NK (x) sup η∈co(∂ ∗ f (x))+NK (x) η, d ≥ 0, ∀d ∈ Rn Từ đó, theo Hiriart-Urruty Lemarechal ([4], Theorem V2.3.1), ta có ∈ cl (co(∂ ∗ f (x)) + NK (x)), Vậy định lý chứng minh Hệ 2.2 Giả sử x ∈ K, int K = ∅, (GLCQ) đúng, f có vi phân / I(x) suy rộng quy ∂ ∗ f (x) bị chặn x Hơn nữa, giả sử gi với i ∈ nửa liên tục x Nếu x nghiệm tối ưu (1.2) cone(Γ(x)) đóng, tồn λi ≥ 0, i ∈ I(x) cho ∈ co(∂ ∗ f (x)) + λi co(∂ ∗ gi (x)) i∈I(x) Chứng minh Nó hệ Định lý 2.4 nhận xét 2.1 Định lý 2.4 Hệ 2.2 điều kiện cần tối ưu Trong Định lý 2.5, ta có điều kiện đủ tối ưu với hàm mục tiêu giả lồi tiệm cận Định nghĩa 2.2 Giả sử h : Ω ⊆ Rn → R ∪ {∞} có vi phân suy rộng quy x ∈ Ω Hàm h gọi giả lồi tiệm cận (asymptotic pseudoconvex) x với y ∈ Ω, ({ζk } ⊆ co(∂ ∗ h(x)), lim ζk , y − x ≥ 0) ⇒ h(y) ≥ h(x) k→∞ Hàm h gọi giả lồi tiệm cận Ω giả lồi tiệm cận điểm Ω 26 Định lí 2.5 Giả sử f giả lồi tiệm cận với vi phân suy rộng quy ∂ ∗ f (x) x ∈ K Nếu tồn λi ≥ 0, i ∈ I(x) cho ∈ co(∂ ∗ f (x)) + λi co(∂ ∗ gi (x)), (2.8) i∈I(x) x nghiệm tối ưu (1.2) Chứng minh Theo phần đầu chứng minh Định lý 2.2, (2.8) kéo theo ∈ co(∂ ∗ f (x)) + NK (x) Vì thế, −η ∈ NK (x) với η ∈ co(∂ ∗ f (x)) Từ ta nhận η, y − x ≥ 0, ∀y ∈ K Định lý chứng minh tính giả lồi có tiệm cận f x Hệ 2.3 Cho x ∈ K Giả sử gi với i ∈ / I(x) nửa liên tục x, int K = ∅ (GLCQ) x Hơn nữa, giả sử f có vi phân suy rộng quy ∂ ∗ f (x) bị chặn Nếu x nghiệm tối ưu (1.2) với i ∈ I(x), cone(∂ ∗ gi (x)) đóng, tồn λi ≥ 0, i ∈ I(x) cho ∈ co(∂ ∗ f (x)) + λi Bi , i∈I(x) Bi sở lồi compắc cone(∂ ∗ gi (x)) Nếu f giả lồi tiệm cận x, điều kiện điều kiện đủ tối ưu Chứng minh Áp dụng Hệ 2.1, Định lý 2.4 Định lý 2.5 Ta kết thúc phần với ví dụ Trong ví dụ sau, hàm ràng buộc g khơng Lipschitz địa phương tập chấp nhận đóng lồi Ví dụ 2.1 Xét tốn tối ưu f (x1 , x2 ), với ràng buộc g(x1 , x2 ) ≤ 0, 27 f (x1 , x2 ) = −x1 − x2  x1 + x2 , x1 , x2 ≤ 0, g(x1 , x2 ) =  |x | + |x |, trường hợp lại Đặt K = {(x1 , x2 ) : g(x1 , x2 ) ≤ 0} Ta thấy  v1 + v2 , v1 , v2 ≤ 0, + g ((0, 0); (v1 , v2 )) = +∞, trường hợp lại Hai tập hợp ∂ ∗ f (0, 0) = {(−1, −1)} ∂ ∗ g(0, 0) = {(1 + t, + 1t ) : t > 0} ∪ {(1, 1)} vi phân suy rộng quy f g x = (0, 0) Hơn nữa, (0, 0) ∈ / ∂ ∗ g(0, 0) Mặt khác, (1, 1) ∈ ∂ ∗ g(0, 0) Do đó, (0, 0) ∈ ∂ ∗ f (0, 0) + ∂ ∗ g(0, 0) Vì (0, 0) điểm Karush-Kuhn-Tucker nghiệm tối ưu 2.2.3 Tính bị chặn nhân tử Karush-Kuhn-Tucker Trong phần trình bày kết tính bị chặn tập nhân tử Karush-Kuhn-Tucker Khơng tính tổng qt, giả sử I(x) = {1, · · · , s} ⊆ I Đặt s M(x) := ∗ (λ1 , · · · , λs ) ≥ : ∈ co(∂ f (x)) + λi Bi , i=1 Bi sở com pắc lồi cone(∂ ∗ gi (x)) Định lí 2.6 Cho x ∈ K Giả sử int K = ∅ (GLCQ) x, hàm mục tiêu f có vi phân suy rộng quy ∂ ∗ f (x) bị chặn Khi M(x) tập bị chặn Chứng minh Bằng chứng minh phản chứng, khơng tính tổng qt, giả sử tồn dãy {(λk1 , · · · , λks )}k∈N ⊆ M(x) cho λk1 → ∞ với k → ∞ Với k ∈ N, tồn η k ∈ co(∂ ∗ f (x)) ζik ∈ Bi cho s k λki ζik , y − x , ∀y ∈ int K = η ,y − x + i=1 28 Chứng minh tương tự phần hai Định lý 2.2, ta có ηi , y − x < với i ∈ I(x) ηi ∈ ∂ ∗ gi (x) Do ta có ≤ η k , y − x + λk1 ζ1k , y − x Bởi co(∂ ∗ f (x)) B1 compact, phần sau ta giả sử η k → η ∈ co(∂ ∗ f (x)) ζ1k → ζ1 ∈ B1 với k → ∞ Vậy, k → ∞, ta nhận ηk , y − x 0≤ + ζ1k , y − x → + ζ1 , y − x < k λ1 Điều dẫn đến mẫu thuẫn Vậy định lý chứng minh 2.3 Đặc trưng tập nghiệm 2.3.1 Dưới vi phân suy rộng điểm tối ưu Trong phần này, ta đặt đặc trưng tập nghiệm tốn tối ưu (1.2) ngơn ngữ vi phân suy rộng sử dụng điều kiện KarushKuhn-Tucker thu phần 2.2 Giả sử tập nghiệm (1.2) S := {x ∈ K : f (x) ≤ f (y), ∀y ∈ K}, khác rỗng Ta thu số đặc trưng sau Mệnh đề 2.1 Cho x ∈ S Giả sử S tập lồi Khi ta có S ⊆ S1 := {x ∈ K : co(∂ ∗ f (x)) ∩ −NK (x) ⊆ −NK (x)}, S ⊆ S2 := {x ∈ K : co(∂ ∗ f (x)) ∩ −NK (x) ⊆ −NK (x)} Hơn nữa, với tập lồi A thỏa mãn S ⊆ A ⊆ K, ta có S ⊆ A1 := {x ∈ A : co(∂ ∗ f (x)) ∩ −NA (x) ⊆ −NA (x)}, S ⊆ A2 := {x ∈ A : co(∂ ∗ f (x)) ∩ −NA (x) ⊆ −NA (x)} Chứng minh Ta chứng minh bao hàm thức S ⊆ S1 Các bao hàm thức khác chứng minh tương tự Cho x ∈ S tùy ý Do tính lồi S, nên với 29 t > đủ nhỏ, x + t(x − x) ∈ S Điều kéo theo f + (x; x − x) = Do đó, η, x − x ≤ với η ∈ ∂ ∗ f (x) Vì vậy, η, x − x = với η ∈ co(∂ ∗ f (x)) ∩ −NK (x) Cho y ∈ K tùy ý Với η ∈ co(∂ ∗ f (x)) ∩ −NK (x), ta có η, y − x = η, y − x + η, x − x ≥ Vì vậy, η ∈ −NK (x) Định lý chứng minh Tính lồi S phần f tựa lồi Nếu f liên tục giả lồi tiệm cận, hàm hàm tựa lồi (Yang [8], Definition 3.1 3.2 Theorem 3.1) S lồi Mệnh đề sau cung cấp đặc trưng đầy đủ tập nghiệm S Mệnh đề 2.2 Cho x ∈ S Giả sử S lồi, co(∂ ∗ f (x)) + NK (x) đóng, f giả lồi tiệm cận có vi phân suy rộng quy trên K Khi đó, S = S3 = S4 = S5 , S3 :={x ∈ K : ∃ζ ∈ co(∂ ∗ f (x)), ζ, x − x = 0}, S4 :={x ∈ K : ∃ζ ∈ co(∂ ∗ f (x)), ζ, x − x ≥ 0}, S5 :={x ∈ K : ∃ζ ∈ co(∂ ∗ f (x)), cho ∀η ∈ ∂ ∗ f (x), η, x − x ≤ ζ, x − x } Chứng minh Hiển nhiên S3 ⊆ S4 Hơn nữa, từ tính giả lồi tiệm cận, ta có S4 ⊆ S Ta S ⊆ S3 , S ⊆ S5 , S5 ⊆ S4 S ⊆ S3 : Lấy x ∈ S Áp dụng định lý 2.4 tính đóng co(∂ ∗ f (x))+NK (x), tồn ζ ∈ co(∂ ∗ f (x)) ∩ −NK (x), tương tự chứng minh Mệnh đề 2.1 ta có, ζ, x − x = S ⊆ S5 : Lấy x ∈ S Tương tự tồn ζ ∈ co(∂ ∗ f (x)) thỏa mãn ζ, x − x = Vì S lồi x ∈ S, ta có f + (x; x − x) = Do với η ∈ ∂ ∗ f (x), η, x − x ≤ = ζ, x − x S5 ⊆ S4 : Lấy x ∈ S5 Do x ∈ S K lồi, f + (x; x − x) ≥ Vì thế, 30 x ∈ S5 , tồn ζ ∈ co(∂ ∗ f (x)) cho ≤ f + (x; x − x) = sup η, x − x ≤ ζ, x − x η∈∂ ∗ f (x) 2.3.2 Xấp xỉ tuyến tính Trong phần này, ta thu tốn bán vơ hạn tuyến tính để kiểm tra tính tối ưu nghiệm chấp nhận cho trước (1.2) Cho x nghiệm chấp nhận (1.2) Giả sử f có vi phân suy rộng quy x ∂ ∗ f (x) Cho η ∈ co(∂ ∗ f (x)) Xét toán quy hoạch bán vơ hạn tuyến tính sau: inf f (x) + η, x − x , x∈K1 (2.9) K1 = {x ∈ Rn : ζi , x − x ≤ 0, ∀i ∈ I(x), ∀ζi ∈ ∂ ∗ gi (x)} Định lý 2.7 2.8 nghiên cứu mối quan hệ tốn (1.2) (2.9) Định lí 2.7 Giả sử ∂ ∗ f (x) bị chặn, int K = ∅ (GLCQ) x Hơn nữa, giả sử gi với i ∈ / I(x) nửa liên tục x Nếu x nghiệm tối ưu (1.2) cone(Γ(x)) đóng, x nghiệm tối ưu (2.9) với η ∈ co(∂ ∗ f (x)) Chứng minh Từ Hệ 2.2, tồn λi ≥ 0, i ∈ I(x) cho ∈ co(∂ ∗ f (x)) + λi co(∂ ∗ gi (x)) i∈I(x) Vì vậy, ta có 0=η+ λi ζ i , i∈I(x) 31 (2.10) với η ∈ co(∂ ∗ f (x)) ζ i ∈ co(∂ ∗ gi (x)) Cho x điểm chấp nhận (2.9) tương ứng với η Theo (2.10), f (x) + η, x − x = f (x) − λi ζ i , x − x ≥ f (x) i∈I(x) Vì vậy, x nghiệm tối ưu (2.9) tương ứng với η Bây giờ, ta chứng minh phần ngược lại định lý 2.7 Định lí 2.8 Giả sử f giả lồi tiệm cận có vi phân suy rộng quy ∂ ∗ f x) x Nếu x nghiệm tối ưu (2.9) với η ∈ co(∂ ∗ f (x)), x nghiệm tối ưu (1.2) Chứng minh Cho x ∈ K tùy ý Do tính lồi K, với i ∈ I(x), gi+ (x; x−x) ≤ Do ta có (ζ, x − x) ≤ 0, ∀i ∈ I(x), ∀ζ ∈ ∂ ∗ gi (x) Vì x ∈ K1 Từ suy K ⊆ K1 , NK1 (x) ⊆ NK (x) Bởi x nghiệm (2.9) với η ∈ co(∂ ∗ f (x)), hàm mục tiêu f (x) + η, x − x tuyến tính theo x tập chấp nhận K1 lồi, ta có ∈ η + NK1 (x) Do đó, η, y − x ≥ 0, ∀y ∈ K Vậy ta có x nghiệm (1.2) giả thiết giả lồi tiệm cận f 2.3.3 Ví dụ Để minh họa cho kết quả, ta xét mơ hình cụ thể quy hoạch ngẫu nhiên với ràng buộc xác suất Giả sử A s × n ma trận C ⊆ Rn tập lồi Xét toán tối ưu sau: min{f (x) : x ∈ C, F (Ax) ≥ p}, p ∈ (0, 1) F (.) hàm phân phối xác suất 32 Ví dụ 2.2 Xét tốn f (x) : F (x) ≤ ,    −x + 3, x < 1,    f (x) = 1, x = 1,     −x + 2, x > hàm phân phối xác suất F cho    0, x ≤ 0,    F (x) = 21 x, ≤ x ≤ 1,     1, x > Hàm F không lồi khơng lõm cịn K= x : F (x) ≤ = (−∞, 1] tập lồi Cả F f khơng liên tục x = 1,cịn hai tập ∂ ∗ F (x) = [ 12 , ∞) ∂ ∗ f (x) = (−∞, −1] vi phân suy rộng quy hàm x Cho y ∈ K Cho {ηk }k∈N ⊆ ∂ ∗ f (x) cho lim ηk (y − x) ≥ Do k→∞ ηk ≤ −1, y ≤ x f (y) ≥ f (x) Vì vậy, f giả lồi tiệm cận x Hơn nữa, int K = ∅ Ta có F (x) = ∈ / ∂ ∗ F (x), điều kiện GLCQ x Như vậy, theo Định lý 2.2 NK (x) = cl cone(∂ ∗ F (x)) = [0, ∞) coi B = {1} sở lồi com pắc nón lồi đóng nhọn Bởi = η + λζ với η = −1 ∈ ∂ ∗ f (x), λ = 1, ζ = ∈ B, theo Định lý 2.5, x nghiệm tối ưu Chú ý hàm mục tiêu tựa lồi tập nghiệm S lồi Bây ta xét xˆ ∈ K, xˆ = x Ta có xˆ < và f khả vi x với 33 f (x) = −1 Vì thế, f (ˆ x)(ˆ x − x) = dẫn đến xˆ ∈ / S theo Mệnh đề 2.2 Do đó, S = {x} 34 Kết luận Luận văn trình trình bày số kết nghiên cứu A Kabgani cộng [6] nón pháp tuyến điều kiện tối ưu cho toán tối ưu với tập chấp nhận lồi Nội dung luận văn bao gồm: - Các kiến thức vi phân suy rộng; - Đặc trưng nón pháp tuyến tập chấp nhận toán tối ưu với ràng buộc bất đẳng thức khơng trơn có tập chấp nhận tập lồi; - Các điều kiện Karush-Kuhn-Tucker ngôn ngữ vi phân suy rộng ; - Đặc trưng tập nghiệm Bài tốn tối ưu khơng trơn với tập chấp nhận lồi đề tàicó tính thời sự, nhiều tác giả quan tâm nghiên cứu 35 Tài liệu tham khảo Tiếng Việt [1] Đỗ Văn Lưu, Phan Huy Khải (2000), Giải tích lồi, NXB Khoa học kĩ thuật, Hà Nội [2] Đỗ Văn Lưu (1999), Giải tích Lipschitz, NXB Khoa học Kĩ thuật, Hà Nội Tiếng Anh [3] F.H Clarke (1983), Optimization and Nonsmooth Analysis, Wiley Interscience, New York [4] JB Hiriart-Uruty, C Lemarecha (1993), Convex Analysis and Minimization algorithms I Springer, Berlin [5] V Jeyakumar, D.T Luc (1999), "Nonsmooth Calculus, minimality and monotonicity of convexificators", J Optim Theory Appl 101, 599 - 621 [6] A Kabgani,M Soleimani-damaneh,M Zamani (2017), "Optimality conditions in optimization problems with convex feasible set using convexificators",Math Meth Oper Res 86, 103-121 [7] R Schneider(1994), Convex bodies: the Brunn-Minkowski theory Cambridge University Press, Cambridge [8] X.Q Yang (2005), "Continuous generalized convex functions and their characterizations", Optimization 54, 495-506 36 ... thiết lập điều kiện tối ưu cho tốn tối ưu khơng trơn với tập chấp nhận tập lồi Đây vấn đề nghiên cứu có tính thời Chính vậy, tơi chọn đề tài: "Bài toán tối ưu với tập chấp nhận lồi" Nội dung đề... nón pháp tuyến tập chấp nhận toán tối ưu với tập chấp nhận tập lồi qua vi phân suy rộng, điều kiện cần Karush-Kuhn-Tuker đặc trưng tập nghiệm 2.1 Đặc trưng nón pháp tuyến tập chấp nhận Phần trình... tuyến điều kiện tối ưu cho toán tối ưu với tập chấp nhận lồi Nội dung luận văn bao gồm: - Các kiến thức vi phân suy rộng; - Đặc trưng nón pháp tuyến tập chấp nhận tốn tối ưu với ràng buộc bất