Header Page of 166 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC THĂNG LONG NGÔ THỊ NGỌC YẾN ĐIỀU KIỆN TỐI ƯU CHO BÀI TOÁN TỐI ƯU VÉC TƠ VỚI CÁC HÀM CÓ ĐẠO HÀM LIPSCHITZ ĐỊA PHƯƠNG LUẬN VĂN THẠC SĨ TOÁN HỌC HÀ NỘI - 2015 Footer Page of 166 Header Page of 166 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC THĂNG LONG NGÔ THỊ NGỌC YẾN ĐIỀU KIỆN TỐI ƯU CHO BÀI TOÁN TỐI ƯU VÉC TƠ VỚI CÁC HÀM CÓ ĐẠO HÀM LIPSCHITZ ĐỊA PHƯƠNG Chuyên ngành: Toán ứng dụng Mã số: 60 46 01 12 LUẬN VĂN THẠC SĨ TOÁN HỌC Hướng dẫn khoa học: PGS TS Đỗ Văn Lưu Hà Nội - 2015 Footer Page of 166 Thang Long University Libraty Header Page of 166 Mục lục Mở đầu Lý chọn đề tài Mục đích đề tài Nội dung đề tài Lời cam đoan Lời cảm ơn ĐIỀU KIỆN TỐI ƯU CHO BÀI TOÁN TỐI ƯU VÉC TƠ C 1,1 KHÔNG RÀNG BUỘC 1.1 Dưới vi phân cấp hàm lớp C 1,1 1.2 Hàm véc tơ C − lồi 1.3 Điều kiện tối ưu cho nghiệm lý tưởng 10 1.4 Điều kiện tối ưu cho nghiệm hữu hiệu 14 ĐIỀU KIỆN TỐI ƯU CHO BÀI TOÁN TỐI ƯU VÉC TƠ C 1,1 CÓ RÀNG BUỘC 21 2.1 Khái niệm bổ trợ 21 2.2 Bài toán với ràng buộc tập 22 2.3 Bài toán có ràng buộc đẳng thức bất đẳng thức 27 Kết luận 33 Footer Page of 166 Header Page of 166 Tài liệu tham khảo 34 Footer Page of 166 Thang Long University Libraty Header Page of 166 Mở đầu Lý chọn đề tài Lý thuyết điều kiện tối ưu phận quan trọng lý thuyết tối ưu hóa Nhiều toán tối ưu nảy sinh kinh tế, kỹ thuật có hàm liệu lớp C 1,1 , tức hàm có đạo hàm Lipschitz địa phương Hiriart - Urruty, Strodiot Hien Nguyen ([8], 1984) khai triển Taylor hàm C 1,1 qua ma trận Hessian suy rộng dẫn điều kiện tối ưu cấp cho toán tối ưu vô hướng với hàm C 1,1 A Guerraggio D.T Luc nghiên cứu toán tối ưu đa mục tiêu hay toán tối ưu véc tơ với hàm lớp C 1,1 dẫn điều kiện tối ưu cần đủ cho nghiệm hữu hiệu toán không ràng buộc ([5], 2001) có ràng buộc ([6], 2003) ngôn ngữ vi phân cấp hàm véc tơ Đây đề tài nhiều tác giả nước quan tâm nghiên cứu Chính chọn đề tài: Điều kiện tối ưu cho toán tối ưu véc tơ với hàm có đạo hàm Lipschitz địa phương Mục đích đề tài Luận văn trình bày kết nghiên cứu điều kiện tối ưu cấp Guerraggio – Luc cho toán tối ưu véc tơ lớp C 1,1 không ràng buộc (2001) có ràng buộc (2003) ngôn ngữ vi phân cấp Nội dung đề tài Chương Điều kiện tối ưu cho toán tối ưu véc tơ C 1,1 không ràng buộc Trình bày kết A Guerraggio D.T Luc ([5], 2001) điều kiện Footer Page of 166 Header Page of 166 cần đủ tối ưu cấp cho toán tối ưu véc tơ ràng buộc hàm mục tiêu lớp C 1,1 ngôn ngữ vi phân cấp với điều kiện đặc trưng cho hàm C − lồi C − đơn điệu Các ví dụ 1.2.1 1.2.2 tác giả Chương Điều kiện tối ưu cho toán tối ưu véc tơ C 1,1 có ràng buộc Trình bày kết A Guerraggio D.T Luc ([6], 2003) điều kiện tối ưu cấp cho toán tối ưu véc tơ C 1,1 có ràng buộc ngôn ngữ vi phân cấp hàm lớp C 1,1 Lời cam đoan Luận văn hoàn thành với học tập nghiên cứu sưu tầm tài liệu hướng dẫn PGS TS Đỗ Văn Lưu trình bày kết tối ưu Lời cảm ơn Nhân dịp xin bày tỏ lòng biết ơn sâu sắc tới thầy giáo PGS TS Đỗ Văn Lưu, người tận tình hướng dẫn, giúp đỡ hoàn thành luận văn Tôi xin chân thành cảm ơn Ban chủ nhiệm khoa Toán, phòng sau đại học trường Đại học Thăng Long thầy, cô giáo tham gia giảng dạy khóa học Xin chân thành cảm ơn gia đình, bạn bè đồng nghiệp thành viên lớp cao học Toán K1 quan tâm, động viên, giúp đỡ suốt thời gian học tập trình làm luận văn Do thời gian trình độ hạn chế nên luận văn không tránh khỏi thiếu sót Tôi mong nhận góp ý thầy cô để luận văn hoàn thiện Tôi xin chân thành cảm ơn! Hà Nội, tháng năm 2015 Người thực Ngô Thị Ngọc Yến Footer Page of 166 Thang Long University Libraty Header Page of 166 Chương ĐIỀU KIỆN TỐI ƯU CHO BÀI TOÁN TỐI ƯU VÉC TƠ C 1,1 KHÔNG RÀNG BUỘC Chương trình bày điều kiện cần đủ tối ưu cấp cho toán tối ưu véc tơ ràng buộc với hàm mục tiêu lớp C 1,1 ngôn ngữ vi phân cấp với điều kiện đặc trưng cho hàm C − lồi C − đơn điệu lớp C 1,1 Các kết trình bày chương Guerraggio - Luc ([5], 2001) 1.1 Dưới vi phân cấp hàm lớp C 1,1 Ta nói f hàm véc tơ lớp C 0,1 có nghĩa f hàm Lipschitz địa phương từ Rm vào Rn Theo định lý Rademacher, f khả vi hầu khắp nơi, tức trừ tập có độ đo Khi Jacobian suy rộng Clarke f điểm x◦ ∈ Rm , kí hiệu ∂f (x◦ ), tồn cho tập hợp ∂f (x◦ ) := cl conv{lim f (xi ) : xi → x◦ , f (xi ) tồn tại}, cl conv kí hiệu bao lồi đóng Bây giờ, ta giả sử f hàm véc tơ khả vi từ Rm vào Rn mà đạo hàm thuộc lớp C 0,1 Trong trường hợp này, ta nói f thuộc lớp C 1,1 Khi đó, Jacobian suy rộng Clarke f x◦ kí hiệu ∂ f (x◦ ) gọi vi phân cấp f x◦ , Footer Page of 166 Header Page of 166 nghĩa là, ∂ f (x◦ ) := cl conv{lim f (xi ) : xi → x◦ , f (xi ) tồn tại} Kí hiệu L(m,n) không gian tuyến tính gồm tất toán tử tuyến tính từ Rm vào Rn kí hiệu L(m,n) không gian tuyến tính gồm tất toán tử tuyến tính từ Rm vào L(m,m) Ta có ∂ f (x◦ ) tập không gian L(m,n) Do đó, phần tử ∂ f (x◦ ) hàm song tuyến tính Rm nhận giá trị Rn Trường hợp n = 1, thuật ngữ "Hessian suy rộng" dùng [8] để tập hợp ∂ f (x◦ ) Bằng cách xây dựng trên, vi phân cấp có tất tính chất Jacobian suy rộng Chẳng hạn, ∂ f (x◦ ) tập lồi khác rỗng compact không gian L(m,n) xem Rm×m×n ánh xạ đa trị x → ∂ f (x) nửa liên tục Chúng ta vài tính chất quan trọng sau: (a) Hợp với hàm tuyến tính: ∀ξ ∈ Rn , ta có ξ∂ f (x) = ∂ (ξf )(x) (1.1) (b) Định lý giá trị trung bình: Cho f hàm lớp C 0,1 a, b ∈ Rm Khi đó, f (b) − f (a) ∈ cl conv{∂f (x)(b − a) : x ∈ [a, b]}, [a, b] = conv{a, b}, conv kí hiệu bao lồi (c) Khai triển Taylor: Cho f ∈ C 1,1 a, b ∈ Rm Khi đó, f (b) − f (a) ∈ f (a)(b − a) + cl conv{∂ f (x)(b − a, b − a) : x ∈ [a, b]} 1.2 Hàm véc tơ C − lồi Cho f : Rm −→ Rn hàm véc tơ C nón lồi, đóng, nhọn có đỉnh gốc (C ∩ −C = {0}) int C = ∅ Thứ tự phận sinh C, kí hiệu ≥C , định nghĩa sau: a ≥C b ⇐⇒ a − b ∈ C Nhắc lại f C − lồi ∀x, y ∈ Rm ∀t ∈ [0, 1], ta có f (tx + (1 − t)y) ≤C tf (x) + (1 − t)f (y) (1.2) Footer Page of 166 Thang Long University Libraty Header Page of 166 Hàm C − lồi đóng vai trò quan trọng tối ưu véc tơ Trong mục ta sử dụng vi phân cấp để đặc trưng hàm C − lồi Nhắc lại ánh xạ đa trị F từ Rm vào L(n,m) C − đơn điệu ∀x, y ∈ Rm , ∀α ∈ F (x) ∀β ∈ F (y), ta có α(y − x) + β(x − y) ≤C Khi n = C nón số dương, định nghĩa quy định nghĩa thông thường ánh xạ đa trị đơn điệu từ Rm đến Rm Dưới số tính chất ánh xạ C − đơn điệu: (i) Nếu F C − đơn điệu tF C − đơn điệu, ∀t ≥ (ii) Nếu F1 F2 C − đơn điệu F3 ⊆ F1 F1 + F2 F3 C − đơn điệu (iii) F C − đơn điệu ξF đơn điệu ∀ξ ∈ C , C nón cực dương C, nghĩa C = {ξ ∈ Rn : ξ, v ≥ 0, ∀v ∈ C} (iv) Nếu f thuộc lớp C 0,1 f C − lồi ∂f C − đơn điệu Trong [10], Jacobian suy rộng sử dụng để mô tả đặc trưng hàm đơn trị Lipschitz địa phương, đơn điệu, từ Rm đến Rm Điều áp dụng cho ánh xạ đa trị C − đơn điệu, C − toán tử bán xác định dương Cho H ánh xạ đa trị từ Rm vào không gian L(m,n) Các phần tử H(x), x ∈ Rm , hàm song tuyến tính Rm nhận giá trị Rn Ta nói H C − bán xác định dương, ∀x ∈ Rm ∀φ ∈ H(x), ta có φ(u, u) ≥C Khi n = 1, C nón số dương H đơn trị, định nghĩa quy định nghĩa dạng song tuyến tính bán xác định dương Ánh xạ đa trị C − bán xác định dương có tính chất tương tự (i), (ii), (iii) Ta có đặc trưng ánh xạ Lipschitz địa phương C − đơn điệu Mệnh đề 1.2.1 Giả sử F hàm véc tơ Lipschitz địa phương từ Rm vào L(m,n) Khi đó, F C − đơn điệu Jacobian suy rộng ∂F ánh xạ đa trị C − bán xác định dương Footer Page of 166 Header Page 10 of 166 Chứng minh Trước hết giả sử ∂F C − bán xác định dương Khi đó, ∀x, y ∈ Rm , theo định lý giá trị trung bình (xem [1]), ta có F (x) − F (y) ∈ cl conv{∂F (z)(x − y) : z ∈ [x, y]} Do đó, F (x)(y − x) + F (y)(x − y) ∈ cl conv{−∂F (z)(x − y, x − y) : z ∈ [x, y]} Vì ∂F C − bán xác định dương C lồi đóng, vế bên phải thuộc −C Từ suy ra, F (x)(y − x) + F (y)(x − y) ≤C 0, F C − đơn điệu Ngược lại, cho F C − đơn điệu Giả sử x ∈ Rm điểm cho F (x) tồn Khi đó, ∀t ≥ ∀u ∈ Rm , ta có F (x + tu) − F (x) ∈ C Điều kéo theo F (x)(u, u) = lim [F (x + tu) − F (x)](u)/t ∈ C, t→+ C đóng Do đó, F (x)(u, u) ≥C 0, ∀u ∈ Rm với x F khả vi Do C đóng, bất đẳng thức cho giới hạn: lim F (xi ) xi → x F (xi ) tồn Do vậy, bất đẳng thức với tổ hợp lồi giới hạn đó, với giới hạn tổ hợp lồi Điều nghĩa ∂F C − bán xác định dương Ví dụ 1.2.1 Xét hàm f : R → R   x, f (x) = x  , x ≥ 0, x < Footer Page 10 of 166 Thang Long University Libraty Header Page 23 of 166 Chương ĐIỀU KIỆN TỐI ƯU CHO BÀI TOÁN TỐI ƯU VÉC TƠ C 1,1 CÓ RÀNG BUỘC Chương trình bày điều kiện cần đủ tối ưu cấp cho toán tối ưu véc tơ có ràng buộc với hàm lớp C 1,1 ngôn ngữ vi phân cấp Các kết trình bày chương Guerraggio - Luc ([6], 2003) 2.1 Khái niệm bổ trợ Giả sử f : Rn → Rm hàm véc tơ lớp C 0,1 , nghĩa f Lipschitz địa phương Theo định lý Rademacher (xem [4]), f khả vi hầu khắp nơi, tức trừ tập có độ đo không Jacobian suy rộng Clarke f điểm x◦ ∈ Rn , ký hiệu ∂f (x◦ ), tồn cho tập ∂f (x◦ ) := cl conv {lim ∇f (xi ) : xi → x◦ , ∇f (xi ) tồn tại}, cl conv{· · · } kí hiệu bao lồi đóng tập dấu ngoặc Bây giờ, giả sử f : Rn → Rm lớp C 1,1 , nghĩa là, ∇f lớp C 0,1 , Jacobian suy rộng Clarke ∇f x◦ , gọi vi phân cấp f x◦ : ∂ f (x◦ ) := cl conv {lim ∇2 f (xi ) : xi → x◦ , ∇2 f (xi ) tồn tại} Gọi L(n,m) không gian tuyến tính gồm tất toán tử tuyến tính từ Rn vào Rm gọi L(n,m) không gian tuyến tính tất toán tử tuyến tính 21 Footer Page 23 of 166 Header Page 24 of 166 từ Rn vào L(n,m) Ta có ∂ f (x◦ ) tập không gian hữu hạn chiều L(n,m) Do đó, phần tử ∂ f (x◦ ) xem hàm song tuyến tính từ Rn vào Rm Theo cách xây dựng, vi phân cấp có tất tính chất Jacobian suy rộng Ta liệt kê vài tính chất quan trọng vi phân cấp 2: (i) ∂ f (x◦ ) tập khác rỗng, lồi compact không gian L(m,n) (ii) Ánh xạ đa trị x → ∂ f (x) nửa liên tục (iii) Hợp thành với hàm tuyến tính: ∀ξ ∈ Rm , ta có ξ∂ f (x) = ∂ (ξf )(x) (iv) Định lý giá trị trung bình: Cho f lớp C 0,1 a, b ∈ Rn Khi đó, f (b) − f (a) ∈ cl conv {∂f (x)(b − a) : x ∈ [a, b]}, [a, b] = conv{a, b} (v) Khai triển Taylor: Cho f lớp C 1,1 a, b ∈ Rn Khi đó, f (b) − f (a) ∈ ∇f (a)(b − a) + cl conv{∂ f (x)(b − a, b − a) : x ∈ [a, b]} 2.2 Bài toán với ràng buộc tập Xét toán tối ưu đa mục tiêu sau (P ) M inD f (x), x ∈ S, D nón cone (int C) ∪ {0} nón C (lồi, đóng, nhọn với đỉnh Rn ), f hàm véc tơ Rn −→ Rm , S ⊆ Rn tập khác ∅ Bài toán (P ) có nghĩa tìm x◦ ∈ S cho f (x◦ ) − f (x) ∈ D\{0}, ∀x ∈ S Nếu D = C ta có nghiệm hữu hiệu (P ) Nếu D = (int C) ∪ {0} ta có nghiệm hữu hiệu yếu (P ) 22 Footer Page 24 of 166 Thang Long University Libraty Header Page 25 of 166 Nếu bao hàm thức ta thay S S ∩ U ta nhận khái niệm nghiệm hữu hiệu, hữu hiệu yếu địa phương (P ), U lân cận x◦ Ta xét toán (P ) với tập ràng buộc S cấu trúc đặc biệt Với x◦ ∈ S, nón tiếp tuyến Bouligand cấp nón tiếp tuyến cấp S x◦ định nghĩa sau: T1 (S, x◦ ) := {u ∈ Rn : ∃ti > 0, xi = x◦ + ti u + o(ti ) ∈ S}, T2 (S, x◦ ) := {(u, v) ∈ Rn × Rn : ∃ti > 0, xi = x◦ + ti u + (1/2)ti v + o(ti ) ∈ S}, o(ti )/ti → o(ti )/ti → 0, ti → 0+ Đặt Λ := {λ ∈ C : λ = 1}, với δ > 0, Sδ (x◦ ) := {t(x − x◦ ) : t ≥ 0, x ∈ S, x − x◦ ≤ δ} Phần bù tập A ⊂ Rn kí hiệu Ac Định lý 2.2.1 Giả sử f : Rn → Rm hàm lớp C 1,1 x◦ ∈ S nghiệm hữu hiệu yếu địa phương toán (P ) Khi đó, với (u, v) ∈ T2 (S, x◦ ) (i) Tồn λ ∈ Λ cho λ, ∇f (x◦ ) ≥ (ii) Khi ∇f (x◦ )(u) = 0, tồn λ ∈ Λ M ∈ ∂ f (x◦ ), cho λ , ∇f (x◦ )(v) + M (u, u) ≥ Chứng minh Lấy (u, v) ∈ T2 (S, x◦ ) Khi ∃ti > cho 2 {ti }∞ → xi = x◦ + ti u + (1/2)ti v + o(ti ) ∈ S Vì x◦ nghiệm hữu hiệu yếu địa phương, tồn i◦ ≥ thỏa mãn f (xi ) − f (x◦ ) ∈ (−int C)c , 23 Footer Page 25 of 166 ∀i ≥ i◦ (2.1) Header Page 26 of 166 Vì f hàm khả vi liên tục, ta có f (xi ) − f (x◦ ) = ∇f (x◦ )(xi − x◦ ) + o( xi − x◦ ) Do đó, từ (2.1) ta suy ∇f (x◦ )(u) ∈ (−int C)c Từ ta suy (i) Bây giờ, giả sử ∇f (x◦ )(u) = 0, áp dụng khai triển Taylor ta nhận f (xi ) − f (x◦ ) = ∇f (x◦ )(xi − x◦ ) + (1/2)Mi (xi − x◦ , xi − x◦ ), với Mi ∈ cl conv{∂ f (x) : x ∈ [x◦ , xi ]} Thay xi − x◦ = ti u + (1/2)ti v + o(ti ) vào đẳng thức trên, ta thu f (xi ) − f (x◦ ) = (1/2)ti (∇f (x◦ )(v) + Mi (u, u)) + o(ti ), o(ti )/ti → 0, i → ∞ Do từ (i) ta suy ∇f (x◦ )(v) + Mi (u, u) + o(ti )/ti ∈ (−int C)c Vì ánh xạ đa trị x → ∂ f (x) nửa liên tục lồi, giá trị compact, ta giả sử {Mi }1 ∞ hội tụ M◦ ∈ ∂ f (x◦ ) Khi đó, ta có ∇f (x◦ )(v) + M◦ (u, u) ∈ (−int C)c Điều tương đương với (ii) Suy điều phải chứng minh Khi C nón đa diện, ta suy kết Định lý 2.2.2 Giả sử C nón đa diện, f : Rn → Rm hàm lớp C 1,1 x◦ ∈ S nghiệm 24 Footer Page 26 of 166 Thang Long University Libraty Header Page 27 of 166 hữu hiệu yếu địa phương (P ) Khi đó, với (u, v) ∈ T2 (S, x◦ ), tồn λ ∈ Λ cho λ, ∇f (x◦ )(u) > 0, λ, ∇f (x◦ )(u) = 0, trường hợp thứ hai, tồn M ∈ ∂ f (x◦ ) cho λ, ∇f (x◦ )(v) + M (u, u) ≥ Chứng minh Lấy (u, v) ∈ T2 (S, x◦ ) chứng minh Khi đó, (2.1) thỏa mãn Vì nón C đa diện, tồn λ ∈ Λ cho λ, f (xi ) − f (x◦ ) ≥ 0, với số vô hạn i Nếu cần, ta xét dãy con, bất đẳng thức với i ≥ i◦ Áp dụng định lý giá trị trung bình, ta có λ, ∇f (x◦ )(u) ≥ Giả sử λ, ∇f (x◦ )(u) = Khai triển Taylor cho ta ≤ λ, f (xi ) − f (x◦ ) = (1/2)ti λ, ∇f (x◦ )(v) + Mi (u, u) + o(ti )/ti Vì vậy, λ, ∇f (x◦ )(v) + M (u, u) ≥ 0, với M ∈ ∂ f (x◦ ) Điều phải chứng minh Bây giờ, ta xét điều kiện đủ tối ưu Định lý 2.2.3 Giả sử f : Rn → Rm hàm lớp C 1,1 x◦ ∈ S Khi đó, điều kiện điều kiện đủ để x◦ nghiệm hữu hiệu địa phương (P ): (i) supλ∈Λ λ, ∇f (x◦ )(u) > 0, ∀u ∈ T1 (C, x◦ )\{0}; 25 Footer Page 27 of 166 Header Page 28 of 166 (ii) supλ∈Λ λ, ∇f (x◦ )(v) ≥ 0, ∀v ∈ Sδ (x◦ ), với δ > đó, inf λ∈Λ λ, M (u, u) > 0, ∀u ∈ T1 (S, x◦ )\{0}, M ∈ ∂ f (x◦ ) Chứng minh Giả sử ngược lại x◦ nghiệm hữu hiệu địa phương (P ) Khi đó, tồn xi ∈ S, xi → x◦ cho f (xi ) − f (x◦ ) ∈ −C (2.2) Ta giả sử (xi − x◦ )/ xi − x◦ → u, i → ∞ Khi đó, (2.2) cho ta ∇f (x◦ )(u) ∈ −C Điều mâu thuẫn với (i), nghĩa (i) điều kiện đủ Bây giờ, áp dụng khai triển Taylor ta nhận f (xi ) − f (x◦ ) = ∇f (x◦ )(xi − x◦ ) + (1/2)Mi (xi − x◦ , xi − x◦ ), (2.3) với Mi ∈ cl conv{∂ f (x) : x ∈ [x◦ , xi ]} Chú ý điều kiện thứ (ii) ∂ f (x◦ )(u, u) ⊆ int C Do tính nửa liên tục vi phân cấp 2, với i đủ lớn, cl conv{∂ f (x)(xi − x◦ , xi − x◦ ) : x ∈ [x◦ , xi ]} ⊆ int C (2.4) Hơn nữa, từ điều kiện thứ (ii) ta có ∇f (x◦ )(xi − x◦ ) ∈ (−int C)c , với i đủ lớn Từ (2.3) (2.4) suy f (xi ) − f (x◦ ) ∈ ∇f (x◦ )(xi − x◦ ) + Mi (xi − x◦ , xi − x◦ ) ⊆ (−int C)c + int C ⊆ (−C)c , với i đủ lớn Điều mâu thuẫn với (2.2) Ta suy điều phải chứng minh 26 Footer Page 28 of 166 Thang Long University Libraty Header Page 29 of 166 Định lý 2.2.4 Giả sử f : Rn → Rm hàm lớp C 1,1 Khi đó, điều kiện đủ để x◦ ∈ S nghiệm hữu hiệu yếu địa phương: ∃δ > cho với v ∈ Sδ (x◦ ), sup λ, ∇f (x◦ )(v) ≥ 0, λ∈Λ ∀M ∈ ∂ f (x), x − x◦ ≤ δ inf λ, M (v, v) ≥ 0, λ∈Λ Chứng minh Ta giả sử ngược lại x◦ nghiệm hữu hiệu yếu địa phương Khi đó, tồn xi ∈ S, xi → x◦ cho f (xi ) − f (x◦ ) ∈ −int C (2.5) Áp dụng khai triển Taylor, ta nhận f (xi ) − f (x◦ ) = ∇f (x◦ )(xi − x◦ ) + (1/2)Mi (xi − x◦ , xi − x◦ ), với Mi ∈ cl conv{∂ f (x) : x ∈ [x◦ , xi ]} Giả sử i◦ ≥ đủ lớn cho xi − x◦ ≤ δ Khi đó, từ điều kiện định lý suy ∇f (x◦ )(xi − x◦ ) ⊆ (−int C)c , Mi (xi − x◦ , xi − x◦ ) ⊆ C, ∀i ≥ i◦ Do đó, f (xi ) − f (x◦ ) ⊆ (−int C)c + C ⊆ (−int C)c Điều mâu thuẫn với (2.5) ta suy điều phải chứng minh 2.3 Bài toán có ràng buộc đẳng thức bất đẳng thức Trong phần này, ta xét toán S cho hệ đẳng thức bất đẳng thức Giả sử g h hai hàm số từ Rn vào Rk Rl Xét 27 Footer Page 29 of 166 Header Page 30 of 166 toán tối ưu có ràng buộc: (CP ) M inint C∪{0} f (x), g(x) ≤ h(x) = Với λ ∈ C , β ∈ Rk , β ≥ γ ∈ Rl , ta định nghĩa hàm Lagrange L(x, λ, β, γ) := λ, f (x) + β, g(x) + γ, h(x) , tập S◦ := {x ∈ Rn : gi (x) = βi > 0, gi (x) ≤ βi = h(x) = 0} Kí hiệu ∇L gradient L(x, λ, β, γ) theo biến x tương tự cho vi phân cấp ∂ L Định lý 2.3.1 Giả sử f, g, h lớp C 1,1 Nếu x◦ ∈ S nghiệm hữu hiệu yếu địa phương (CP ) tồn véc tơ khác không (λ◦ , β, γ) ∈ C × Rk+ × Rl cho ∇L(x◦ , λ◦ , β, γ) = Hơn nữa, C đa diện với (u, v) ∈ T2 (S◦ , x◦ ), tồn λ ∈ Λ cho ∇L(x◦ , λ, β, γ)(u) > 0, ∇L(x◦ , λ, β, γ)(u) = 0, trường hợp thứ hai, tồn M ∈ ∂ L(x◦ , λ, β, γ) cho ∇L(x◦ , λ, β, γ)(v) + M (u, u) ≥ Chứng minh Điều kiện tồn nhân tử (λ◦ , β, γ) biết Bây ta chứng minh điều kiện thứ hai với giả thiết C nón đa diện Lấy (u, v) ∈ T2 (S◦ , x◦ ) Giả sử xi = x◦ + ti u + (1/2)t2i v + o(t2i ) ∈ S◦ , với ti > đó, ti → 0, i → ∞ 28 Footer Page 30 of 166 Thang Long University Libraty Header Page 31 of 166 Vì x◦ nghiệm hữu hiệu yếu địa phương (CP ), tồn i◦ ≥ cho f (xi ) − f (x◦ ) ∈ (−int C)c , ∀i ≥ i◦ Hơn nữa, C nón đa diện, nên tồn λ ∈ Λ cho λ, f (xi ) − f (x◦ ) ≥ 0, với vô hạn i Bằng cách thay dãy cần thiết, ta giả sử bất đẳng thức với i ≥ i◦ Áp dụng khai triển Taylor cho L, tồn Mi ∈ cl conv{∂ L(x, λ, β, γ) : x ∈ [x◦ , xi ]} cho ≤ L(xi , λ, β, γ) − L(x◦ , λ, β, γ) = ∇L(x◦ , λ, β, γ)(xi − x◦ ) + (1/2)Mi (xi − x◦ , xi − x◦ ), ∀i ≥ i◦ Thay khai triển xi − x◦ = ti u + (1/2)t2i v + o(t2i ) vào hệ thức ta suy ≤ ti ∇L(x◦ , λ, β, γ)(u) + (t2i /2)[∇L(x◦ , λ, β, γ)(v) + Mi (u, u)] + o(t2i ), o(t2i )/t2i → 0, i → ∞ Chia bất đẳng thức cho ti qua giới hạn i → ∞, ta ∇L(x◦ , λ, β, γ)(u) ≥ Nếu ∇L(x◦ , λ, β, γ)(u) = 0, chia bất đẳng thức cho t2i qua giới hạn i → ∞, ta suy ∇L(x◦ , λ, β, γ)(v) + M◦ (u, u) ≥ 0, M◦ ma trận giới hạn dãy ma trận {Mi }∞ thuộc ∂ L(x◦ , λ, β, γ) ∂ L(x◦ ) nửa liên tục 29 Footer Page 31 of 166 Header Page 32 of 166 Định lý 2.3.2 Giả sử f, g, h hàm C 1,1 với u ∈ T1 (S, x◦ )\{0}, tồn (λ, β, γ) ∈ Λ × Rk+ × Rl cho ∇L(x◦ , λ, β, γ) = 0, inf M ∈∂ L(x◦ ,λ,β,γ) βg(x◦ ) = 0, M (u, u) > Khi đó, x◦ nghiệm hữu hiệu địa phương (CP ) Chứng minh Ta chứng minh phương pháp phản chứng, giả sử x◦ nghiệm địa phương (CP ) Khi đó, tồn xi ∈ S, xi → x◦ cho f (xi ) − f (x◦ ) ∈ −C Ta giả sử (xi − x◦ )/ xi − x◦ → u ∈ T1 (S, x◦ ) Ta có L(xi , λ, β, γ) − L(x◦ , λ, β, γ) ≤ 0, ∀i ≥ Hơn nữa, áp dụng khai triển Taylor cho L, ta nhận L(xi , λ, β, γ)−L(x◦ , λ, β, γ) = ∇L(x◦ , λ, β, γ)(xi −x◦ )+(1/2)Mi (xi −x◦ , xi −x◦ ), với Mi ∈ cl conv{∂ L(x, α, β, γ) : x ∈ [x◦ , xi ]} Do đó, Mi (xi − x◦ , xi − x◦ ) ≤ 0, chứng minh định lý trước Điều cho ta M◦ (u, u) ≤ 0, với M◦ ∈ ∂ L(x◦ , λ, β, γ) Điều trái với giả thiết Định lý 2.3.3 Giả sử f, g, h lớp hàm C 1,1 tồn δ > cho với v ∈ Sδ (x◦ ) có véc tơ (λ, β, γ) ∈ Λ × Rk+ × Rl cho ∇L(x◦ , λ, β, γ) = 0, βg(x◦ ) = 0, 30 Footer Page 32 of 166 Thang Long University Libraty Header Page 33 of 166 inf M ∈∂ L(x,λ,β,γ), x−x◦ ≤δ M (u, u) ≥ Khi đó, x◦ nghiệm hữu hiệu yếu địa phương (CP ) Chứng minh Cũng chứng minh định lý trước, x◦ không nghiệm hữu hiệu yếu địa phương tồn xi ∈ S, xi → x◦ cho f (xi ) − f (x◦ ) ∈ −int C Áp dụng công thức Taylor ta nhận > λ, f (xi ) − f (x◦ ) ≥ L(xi , λ, β, γ) − L(x◦ , λ, β, γ) ≥ ∇L(x◦ , λ, β, γ)(xi − x◦ ) + (1/2)Mi (xi − x◦ , xi − x◦ ), với Mi ∈ cl conv{∂ L(x, λ, β, γ) : x ∈ [x◦ , xi ]} Với i đủ lớn để xi − x◦ ≤ δ, ta suy L(xi , λ, β, γ) − L(x◦ , λ, β, γ) ≥ Đây mẫu thuẫn Ví dụ 2.3.1 Trong phần này, ta trình bày ví dụ để kết luận định lý 2.2.2 2.3.1 không nón C đa diện Cho f : R → R3 sau: f (t) := −(t + t2 cos t, t + t cos t, t sin t) Cho nón C C := {(x, y, z) ∈ R3 : x2 ≥ y + z , x ≥ 0} Ta xét toán mục tiêu đây: M inC f (t), t ∈ [0, ∞) Rõ ràng t = nghiệm hữu hiệu địa phương toán Ta có ∇f (0) = −(1, 2, 0) 31 Footer Page 33 of 166 ∇2 f (0) = −(2, 0, 2) Header Page 34 of 166 Phương trình λ, ∇f (0) = 0, λ ∈ Λ, nghiệm với λ = (2, −1, 31/2 )/81/2 λ = (2, −1, −31/2 )/81/2 Với giá trị λ véc tơ (u, v) = (1, 0) ∈ T2 (S, 0), ta có λ, ∇f (0)(v) + ∇2 f (0)(u, u) < Điều kết luận định lý 2.2.2 (định lý 2.3.1) không 32 Footer Page 34 of 166 Thang Long University Libraty Header Page 35 of 166 Kết luận Luận văn trình bày lý thuyết điều kiện tối ưu cấp Guerraggio - Luc cho nghiệm hữu hiệu toán tối ưu véc tơ lớp C 1,1 ràng buộc (2001) có ràng buộc (2003) ngôn ngữ vi phân cấp hàm lớp C 1,1 , bao gồm: - Khái niệm vi phân cấp cho hàm lớp C 1,1 tính chất; - Khai triển Taylor cho hàm lớp C 1,1 ; - Điều kiện đặc trưng cho hàm C − lồi C − đơn điệu cho ví dụ minh họa; - Điều kiện cần đủ tối ưu cấp cho toán tối ưu véc tơ ràng buộc với hàm mục tiêu lớp C 1,1 qua vi phân cấp 2; - Điều kiện cần đủ tối ưu cấp cho toán tối ưu véc tơ có ràng buộc với hàm lớp C 1,1 qua vi phân cấp Điều kiện tối ưu cấp cho toán tối ưu véc tơ đề tài nhiều tác giả quan tâm nghiên cứu 33 Footer Page 35 of 166 Header Page 36 of 166 Tài liệu tham khảo Tài liệu Tiếng Việt [1] Đỗ Văn Lưu (1999), Giải tích Lipschitz, NXB Khoa học Kỹ thuật, Hà Nội [2] Đỗ 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 Tài liệu Tiếng Anh [3] Aghezzaf, B., Hachimi, M (1999), Second-order optimality conditions in multiobjective optimization problems, Journal of Optimization Theory and Applications, vol 102, pp 37–50 [4] Clarke, F H (1983), Optimization and Nonsmooth Analysis, Wiley, New York [5] Guerraggio, A., Luc, D T (2001), Optimality conditions for C 1,1 vector optimization problems, Journal of Optimization Theory and Applications, vol 109, pp 615–629 [6] Guerraggio, A., Luc, D T (2003), Optimality conditions for C 1,1 constrained multiobjective problems, Journal of Optimization Theory and Applications, vol 116, pp 117–129 [7] Henig, M I (1982), Proper efficiency with respect to cones, Journal of Optimization Theory and Applications, vol 6, pp 387–407 [8] Hiriart-Urruty, J B., Strodiot, J J., Hien Nguyen, V (1984), Generalized Hessian matrix and second-order optimality conditions for problems with C 1,1 data, Applied Mathematics and Optimization, vol 11, pp 43–56 34 Footer Page 36 of 166 Thang Long University Libraty Header Page 37 of 166 [9] Luc, D T (1995), Taylor’s formula for C k,1 functions, SIAM Journal on Optimization, vol 5, pp 659–669 [10] Luc, D T., Schaible, S (1996), Generalized monotone nonsmooth maps, Journal of Convex Analysis, vol 3, pp 195–205 35 Footer Page 37 of 166 ... tài: Điều kiện tối ưu cho toán tối ưu véc tơ với hàm có đạo hàm Lipschitz địa phương Mục đích đề tài Luận văn trình bày kết nghiên cứu điều kiện tối ưu cấp Guerraggio – Luc cho toán tối ưu véc... LONG NGÔ THỊ NGỌC YẾN ĐIỀU KIỆN TỐI ƯU CHO BÀI TOÁN TỐI ƯU VÉC TƠ VỚI CÁC HÀM CÓ ĐẠO HÀM LIPSCHITZ ĐỊA PHƯƠNG Chuyên ngành: Toán ứng dụng Mã số: 60 46 01 12 LUẬN VĂN THẠC SĨ TOÁN HỌC Hướng dẫn khoa... Chương ĐIỀU KIỆN TỐI ƯU CHO BÀI TOÁN TỐI ƯU VÉC TƠ C 1,1 CÓ RÀNG BUỘC Chương trình bày điều kiện cần đủ tối ưu cấp cho toán tối ưu véc tơ có ràng buộc với hàm lớp C 1,1 ngôn ngữ vi phân cấp Các