Luận văn Thạc sĩ Toán học: Điều kiện tối ưu cấp hai với các hàm lớp C1

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:47

Thêm vào BST

Báo xấu

24
lượt xem 7
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Luận văn trình bày các điều kiện tối ưu Karush – Kuhn – Tucker và Fritz John cấp 2 của Ginchev – Ivanov cho bài toán tối ưu với hữu hạn ràng buộc bất đẳng thức và ràng buộc tập với các hàm khả vi liên tục, và điều kiện tối ưu cấp 2 cho cực tiểu cô lập của Ivanov ([10], 2009) cho bài toán đó. Mời các bạn tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Toán học: Điều kiện tối ưu cấp hai với các hàm lớp C1

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC TRẦN THỊ MINH TÂM ĐIỀU KIỆN TỐI ƯU CẤP HAI VỚI CÁC HÀM LỚP C1 LUẬN VĂN THẠC SĨ TOÁN HỌC Thái Nguyên - 2016
ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC TRẦN THỊ MINH TÂM ĐIỀU KIỆN TỐI ƯU CẤP HAI VỚI CÁC HÀM LỚP C1 LUẬN VĂN THẠC SĨ TOÁN HỌC Chuyên ngành: TOÁN ỨNG DỤNG Mã số: 60 46 01 12 NGƯỜI HƯỚNG DẪN KHOA HỌC PGS.TS ĐỖ VĂN LƯU Thái Nguyên - 2016
i Mục lục Lời nói đầu 1 Chương 1. ĐIỀU KIỆN TỐI ƯU CẤP 2 CỦA GINCHEV - IVANOV 3 1.1 Điều kiện đủ tối ưu cho cực tiểu toàn cục . . . . . . . . . . 3 1.2 Điều kiện cần tối ưu cho cực tiểu địa phương . . . . . . . . 9 1.3 Điều kiện đủ tối ưu cho cực tiểu địa phương cô lập cấp 2 . 15 1.4 Điều kiện tối ưu cho cực tiểu địa phương parabolic . . . . 19 Chương 2. ĐIỀU KIỆN TỐI ƯU CẤP 2 CHO CỰC TIỂU CÔ LẬP CẤP 2 22 2.1 Các khái niệm và định nghĩa . . . . . . . . . . . . . . . . 22 2.2 Điều kiện cần cho cực tiểu địa phương cô lập cấp 2 . . . . 26 2.3 Cực tiểu cô lập và tính lồi suy rộng . . . . . . . . . . . . . 34 KẾT LUẬN 41 TÀI LIỆU THAM KHẢO 43
1 Lời nói đầu 1. Lý do chọn đề tài Điều kiện tối ưu Karush – Kuhn – Tucker (KKT) là công cụ hữu hiệu để giải các bài toán tối ưu phi tuyến. Các điều kiện cần cấp 1 cho phép ta tìm được tập các điểm dừng. Các điều kiện tối ưu cấp 2 cho phép loại bỏ các điểm dừng không là nghiệm và xác định liệu một điểm dừng có là nghiệm hay không. I. Ginchev và V. I. Ivanov ([6], 2008) đã thiết lập các điều kiện cần tối ưu KKT và Fritz John (FJ) cấp 2 cho bài toán tối ưu có ràng buộc bất đẳng thức và ràng buộc tập với các hàm lớp C1 , nhưng đạo hàm của chúng không Lipschitz địa phương. Các điều kiện đủ nhận được với hàm mục tiêu khả vi và giả lồi cấp 2. V. I. Ivanov ([10], 2009) tiếp tục nghiên cứu các điều kiện tối ưu cho cực tiểu cô lập của bài toán đó; các điều kiện đủ được dẫn với các giả thiết về tính lồi suy rộng. Điều kiện tối ưu cấp 2 là đề tài thời sự, được nhiều tác giả trong và ngoài nước quan tâm nghiên cứu. Chính vì vậy, tôi chọn đề tài “Điều kiện tối ưu cấp hai với các hàm lớp C1 ”. 2. Nội dung đề tài Luận văn trình bày các điều kiện tối ưu Karush – Kuhn – Tucker và Fritz John cấp 2 của Ginchev – Ivanov ([6], 2008) cho bài toán tối ưu với hữu hạn ràng buộc bất đẳng thức và ràng buộc tập với các hàm khả vi liên tục, và điều kiện tối ưu cấp 2 cho cực tiểu cô lập của Ivanov ([10], 2009) cho bài toán đó. Luận văn bao gồm phần mở đầu, hai chương, kết luận và danh mục các tài liệu tham khảo. CHƯƠNG I. ĐIỀU KIỆN TỐI ƯU CẤP 2 CỦA GINCHEV - IVANOV Trình bày các kết quả nghiên cứu của Ginchev - Ivanov ([6], 2008) về các điều kiện tối ưu Fritz John và KKT cấp 2 cho bài toán tối ưu có ràng
2 buộc bất đẳng thức và ràng buộc tập. Trong điều kiện cần, hàm mục tiêu và các hàm ràng buộc tích cực được giả thiết là khả vi liên tục, nhưng gradient của chúng không nhất thiết Lipschitz địa phương. Các điều kiện cần dạng hệ không tương thích và dạng đối ngẫu được trình bày. Trong điều kiện đủ, hàm mục tiêu khả vi và giả lồi cấp 2, các hàm ràng buộc khả vi và tựa lồi. Trong các điều kiện đủ cho cực tiểu địa phương cô lập ta giả thiết bài toán thuộc lớp C1,1 ; các điều kiện đủ cho cực tiểu parabolic cô lập cấp 2 của bài toán lớp C1 . CHƯƠNG II. ĐIỀU KIỆN TỐI ƯU CẤP 2 CHO CỰC TIỂU CÔ LẬP CẤP 2 Trình bày các kết quả nghiên cứu của Ivanov ([10], 2009) về các điều kiện tối ưu cấp 1 và cấp 2 cho cực tiểu cô lập cấp 2 của bài toán có ràng buộc bất đẳng thức và ràng buộc tập. Trong các điều kiện cần cho cực tiểu địa phương cô lập cấp 2, các hàm khả vi liên tục và khả vi theo phương cấp 2. Các điều kiện cần tối ưu cấp 2 dạng hệ không tương thích và dạng đối ngẫu, có và không có điều kiện chính quy cấp 2 được trình bày. Các điều kiện đủ tối ưu cho cực tiểu cô lập được trình bày với các giả thiết về tính lồi suy rộng. Luận văn này được thực hiện và hoàn thành tại Trường Đại học Khoa học - Đại học Thái Nguyên, dưới sự hướng dẫn của PGS. TS Đỗ Văn Lưu, Viện toán học - Viện Hàn Lâm Khoa học và Công nghệ Việt Nam. Tác giả xin bày tỏ lòng biết ơn sâu sắc tới thầy hướng dẫn khoa học của mình, thầy đã tận tâm và nhiệt tình chỉ bảo. Tác giả xin chân thành cảm ơn Ban giám hiệu, Ban chủ nhiệm khoa Toán - Tin, phòng Đào tạo Trường Đại học Khoa học - Đại học Thái Nguyên, cùng toàn thể cán bộ giảng dạy lớp cao học toán K8B đã nhiệt tình giảng dạy và giúp đỡ tác giả trong suốt quá trình học tập. Cuối cùng tác giả xin cảm ơn bố mẹ, gia đình, bạn bè và đồng nghiệp đã luôn bên cạnh động viên, giúp đỡ trong quá trình học tập và hoàn thành luận văn này. Tác giả Trần Thị Minh Tâm
3 Chương 1 ĐIỀU KIỆN TỐI ƯU CẤP 2 CỦA GINCHEV - IVANOV Chương 1 trình bày các điều kiện tối ưu Fritz John và Karush – Kuhn – Tucker cấp 2 của Ginchev - Ivanov [6] cho bài toán tối ưu có hữu hạn ràng buộc bất đẳng thức và ràng buộc tập. Trong điều kiện cần, hàm mục tiêu và các hàm ràng buộc tích cực được giả thiết thuộc lớp C1 , nhưng gradient của chúng không nhất thiết Lipschitz địa phương. Các điều kiện cần dạng hệ bất đẳng thức không tương thích và dạng đối ngẫu được trình bày. Trong điều kiện đủ, hàm mục tiêu được giả thiết khả vi và giả lồi cấp 2, các hàm ràng buộc khả vi và tựa lồi. Các điều kiện đủ cho cực tiểu parabolic cô lập cấp 2 của bài toán lớp C1 cũng được trình bày trong chương này. 1.1 Điều kiện đủ tối ưu cho cực tiểu toàn cục Trong chương này chúng ta trình bày điều kiện tối ưu KKT và FJ cho bài toán (P) sau: Minimize f0 (x) , fi (x) 6 0, i = 1, ..., m, x ∈ X, trong đó X ⊂ Rn và fi , i = 0, 1, ..., m là các hàm xác định trên X. Ký hiệu R ¯ = R ∪ {−∞} ∪ {+∞}. là tập các số thực và R
4 Hàm f : X → R trong đó X là tập mở, X ⊂ Rn , f khả vi tại điểm x ∈ X, 00 5 f (x) là đạo hàm của f tại x. Đạo hàm theo phương cấp 2 f (x, u) của f tại x ∈ X theo phương u ∈ Rn được xác định bởi công thức 00 2 f (x, u) = lim ( f (x + tu) − f (x) − t 5 f (x) u) . t→+0 t 2 00 Hàm f được gọi là khả vi theo phương cấp 2 trên X nếu đạo hàm f (x, u) tồn tại với mỗi x ∈ X và phương bất kỳ u ∈ Rn . Nhắc lại hàm f : X → R được gọi là tựa lồi tại x ∈ X (theo X) nếu y ∈ X, f (y) 6 f (x) ,t ∈ [0, 1] , (1 − t) x + ty ∈ X ⇒ f ((1 − t) x + ty) 6 f (x) . Nếu tập X là lồi thì hàm f được gọi là tựa lồi trên X nếu với mọi x, y ∈ X và t ∈ [0, 1] thì ta có f ((1 − t) x + ty) 6 max ( f (x) , f (y)) . Bổ đề 1.1.1. ([12]) Giả sử X là tập mở trong Rn và f là hàm thực xác định trên X khả vi và tựa lồi tại x ∈ X. Khi đó, y ∈ X, f (y) 6 f (x) =⇒ 5 f (x) (y − x) 6 0. Giả sử hàm f : X → R với X ⊂ Rn là tập mở, f khả vi tại x ∈ X. Khi đó, f được gọi là giả lồi tại x ∈ X nếu y ∈ X và f (y) < f (x) =⇒ 5 f (x) (y − x) < 0. Nếu f khả vi trên X thì f được gọi là giả lồi trên X nếu f là giả lồi tại mỗi x ∈ X. Xét hàm f : X → R, trong đó X là miền mở, f khả vi tại x ∈ X và khả vi theo phương cấp 2 tại x ∈ X theo mỗi phương y − x sao cho y ∈ X, f (y) < f (x) , 5 f (x) (y − x) = 0. Định nghĩa 1.1.2. Ta nói f là giả lồi cấp 2 (nói vắn tắt là 2-giả lồi) tại
5 x ∈ X nếu với mỗi y ∈ X, f (y) < f (x) ⇒ 5 f (x) (y − x) 6 0; 00 f (y) < f (x) , 5 f (x) (y − x) = 0 ⇒ f (x, y − x) < 0. Giả sử f khả vi trên X và khả vi theo phương cấp 2 tại mỗi x ∈ X theo mỗi phương y − x sao cho y ∈ X, f (y) < f (x) , 5 f (x) (y − x) = 0. Ta nói f là 2-giả lồi trên X nếu f là 2-giả lồi tại mỗi x ∈ X. Từ định nghĩa này ta suy ra mọi hàm giả lồi khả vi là 2-giả lồi. Điều ngược lại không đúng. Trong phần này ta giả sử fi , i = 0, ..., m là các hàm thực xác định trên không gian Euclid hữu hạn chiều Rn . Xét bài toán (P). Ký hiệu S là tập chấp nhận được S := {x ∈ X| fi (x) 6 0, i = 1, 2, ..., m} . Với mỗi điểm chấp nhận được x ∈ S ta kí hiệu I (x) là tập các chỉ số ràng buộc tích cực I (x) := {i ∈ {1, 2, ..., m} | fi (x) = 0} . Định nghĩa 1.1.3. Phương d được gọi là tới hạn tại điểm x ∈ S nếu 5 fi (x) d 6 0 với mọi i ∈ {0} ∪ I (x). Kết quả chính của phần này là định lý sau đây: Định lý 1.1.4. Giả sử ràng buộc tập X là mở, các hàm fi , i = 0, ..., m xác định trên X. Giả sử fi , (i ∈ {0} ∪ I(x)) ¯ khả vi tại điểm chấp nhận được x¯ và khả vi theo phương cấp 2 tại x¯ theo mọi phương tới hạn d ∈ Rn , f0 là 2-giả ¯ fi , (i ∈ I(x)) lồi tại x, ¯ Với mỗi phương tới hạn d ∈ Rn , tồn ¯ là tựa lồi tại x. tại các nhân tử Lagrange không âm λ1 , λ2 , ..., λm với λi fi (x) ¯ = 0, i = 1, ..., m, 5L (x) ¯ = 0, 00 trong đó L = f0 (x) + ∑m i=1 λi f i (x) là hàm Lagrange và L (x, ¯ d) > 0. Khi đó, x¯ là cực tiểu toàn cục của (P).
6 Chứng minh Để đơn giản kí hiệu, ta sẽ viết 5L (x)¯ = 5x L (x,¯ λ ). Giả sử ngược lại tồn tại x ∈ S với f0 (x) < f0 (x). ¯ Giả sử x − x¯ là một phương tới hạn. Do tính 2-giả lồi, ta có 5 f0 (x) ¯ (x − x) ¯ 6 0. Do tính tựa lồi và ¯ , i ∈ I (x) fi (x) 6 f (x) ¯ và do Bổ đề 1.1.1 ta có 5 fi (x) ¯ (x − x) ¯ 6 0 với mọi i ∈ I (x). ¯ Điều này suy ra x − x¯ là tới hạn. Sử dụng giả thiết của định lý suy ra tồn tại nhân tử không âm λ1 , λ2 , ..., λm với ¯ = 0, i = 1, ..., m và 5L (x) λi fi (x) ¯ (x − x) ¯ =0 sao cho 00 L (x, x − x) ¯ > 0. Do đó, λi = 0 với i ∈ ¯ Do x − x¯ là tới hạn, ta nhận được / I (x). 5L (x) ¯ (x − x) ¯ = 5 f0 (x) ¯ (x − x) ¯ + ∑ λi 5 fi (x) ¯ (x − x) ¯ 60 ¯ i∈I(x) Vì vậy, 5 f0 (x) ¯ (x − x) ¯ = 0 và λi 5 fi (x) ¯ (x − x) ¯ = 0 với mọi i ∈ I(x). ¯ Khi đó, 5 fi (x) ¯ (x − x) ¯ = 0 khi λi > 0. Do tính 2-giả lồi, ta suy ra 00 ¯ x − x) f0 (x, ¯ < 0. Do đó 00 00 ¯ x − x) L (x, ¯ < ∑ ¯ x − x) λi f (x, ¯ ¯ i∈I(x) fi (x¯ + t (x − x)) ¯ − fi (x) ¯ = ∑ λi lim 2 ¯ i >0 i∈I(x),λ t→+0 t /2 Do tính tựa lồi ta có fi (x¯ + t (x − x)) ¯ = 0, với mọi i ∈ I(x) ¯ 6 fi (x) ¯ và với 00 mọi t ∈ [0, 1] đủ nhỏ. Từ đấy ta suy ra L (x, x − x) ¯ < 0. Đây là một mâu thuẫn. Định lý 1.1.4 là một tổng quát hóa kết quả sau đây của Mangasarian [12, định lý 10.1.2], bởi vì lớp các hàm 2-giả lồi chứa lớp các hàm giả lồi khả vi.
7 Định lý 1.1.5. (Xem [12]). Giả sử tập ràng buộc X mở. Các hàm fi (i = 0, 1, ..., m) xác định trên X và x¯ là điểm chấp nhận được. Giả sử fi (i ∈ {0} ∪ I(x)) ¯ f0 giả lồi tại x¯ và fi (i ∈ I(x)) ¯ khả vi tại x, ¯ là tựa lồi tại x. ¯ Nếu tồn tại nhân tử Lagrange không âm λ1 , λ2 , ..., λm với ¯ = 0, i = 1, ..., m và 5L (x) λi fi (x) ¯ = 0, trong đó L = f0 (x) + ∑m i=1 λi f i (x) thì x¯ là cực tiểu toàn cục của (P). Ví dụ 1.1.6. Xét bài toán sau: ( x2 ,x>0 Minimize f0 (x) = , với ràng buộc f1 = −x 6 0. −x2 , x < 0 Trong bài toán này fi ∈ C1 , i = 0, 1. Hàm mục tiêu là 2-giả lồi tại x¯ = 0. Hàm ràng buộc là tuyến tính, cho nên tựa lồi. Hàm Lagrange là L (x) = f0 (x) − λ x. Điểm dừng duy nhất là x¯ = 0 với nhân tử Lagrange λ = 0. Ràng buộc là tích cực tại x¯ = 0. Các phương tới hạn là tất cả các phương d ∈ R sao cho d > 0. Dễ kiểm tra rằng 00 00 L (0, d) = f0 (0, d) = 2d 2 > 0. Khi đó, theo Định lý 1.1.4, x¯ = 0 là cực tiểu toàn cục. Bài toán này không thể giải được với các điều kiện đủ của Mangasarian [12, định lý 10.1.2], bởi vì f0 không giả lồi. Ví dụ 1.1.7. Xét bài toán sau Minimize f0 (x) = x3 , với ràng buộc f1 (x) = x 6 0. Hàm ràng buộc f1 = x là tựa lồi. Hàm mục tiêu f0 = x3 không là 2-giả lồi tại x¯ = 0, nhưng là tựa lồi. Hàm Lagrange là L (x, λ ) = x3 + λ x. Tập các phương tới hạn là {d ∈ R|d 6 0}. Điểm dừng duy nhất là x¯ = 0 với nhân 00 tử Lagrange λ = 0. Ta có L (0, 0) = 0, nhưng x¯ = 0 không là cực tiểu toàn cục.
8 Ta đưa vào các khái niệm sau đây: Định nghĩa 1.1.8. Giả sử X ⊂ Rn là một tập mở và hàm f : X → R là khả vi tại x ∈ X và khả vi theo phương cấp hai tại x ∈ X theo mọi phương y − x sao cho y ∈ X, f (y) < f (x) , 5 f (x) (y − x) = 0. Ta nói f là 2-giả lồi chặt tại x ∈ X nếu với mọi y ∈ X, y 6= x thì suy luận sau đúng: f (y) 6 f (x) =⇒ 5 f (x) (y − x) 6 0; 00 f (y) 6 f (x) , 5 f (x) (y − x) = 0 =⇒ f (x, y − x) < 0. Mỗi hàm 2-giả lồi chặt là 2-giả lồi Định lý 1.1.9. Nếu ta thêm vào giả thiết của Định lý 1.1.4 là f0 2-giả lồi chặt tại x¯ thì x¯ là cực tiểu toàn cục chặt. Chứng minh Ta có thể chứng minh định lý này tương tự Định lý 1.1.4. Định lý 1.1.10. Giả sử X ⊆ Rn mở, các hàm fi (i = 0, 1, ..., m) xác định trên X và x¯ là điểm chấp nhận được. Giả sử tất cả các hàm fi (i ∈ {0} ∪ I(x)) ¯ ¯ khả vi theo phương cấp 2 tại x¯ theo mỗi phương tới hạn d ∈ Rn khả vi tại x, ¯ Nếu với mỗi phương tới hạn d, tồn tại các nhân tử và 2-giả lồi chặt tại x. không âm λ0 , λ1 , ..., λm với λ = (λ0 , λ1 , ..., λm ) 6= 0 và 00 λi fi (x) ¯ = 0, i = 1, ..., m, 5L (x) ¯ = 0, L (x, ¯ d) > 0, trong đó L = ∑m i=0 λi f i (x) thì x¯ là cực tiểu toàn cục chặt của (P). Chứng minh Giả sử ngược lại tồn tại x ∈ S, x 6= x¯ với f0 (x) 6 f0 (x). ¯ Ta chứng minh định lý này tương tự Định lý 1.1.4. Do tính 2-giả lồi chặt ta nhận được 0 = 5L (x) ¯ (x − x) ¯ = ∑ λi 5 fi (x) ¯ (x − x) ¯ 6 0. ¯ i∈{0}∪I(x)
9 Do đó, λi 5 fi (x) ¯ = 0 với mọi i ∈ {0} ∪ I(x). ¯ (x − x) ¯ Với mọi i ∈ {0} ∪ I(x) ¯ với λi > 0, ta có 5 fi (x) ¯ (x − x) ¯ = 0. 00 ¯ x − x) Do tính 2-giả lồi chặt ta lại có fi (x, ¯ < 0. 00 Do λ 6= 0, ta suy ra L (x, ¯ x − x) ¯ < 0. Đây là một mâu thuẫn. 1.2 Điều kiện cần tối ưu cho cực tiểu địa phương Trong phần này ta trình bày điều kiện cần tối ưu cho bài toán (P) với các dữ liệu khả vi liên tục. Với các vectơ cố định x¯ ∈ Rn và d ∈ Rn , ta đặt ¯ d) := {i ∈ {0} ∪ I (x) I0 (x, ¯ | 5 fi (x) ¯ d = 0} . Định lý 1.2.1. (Điều kiện cần cấp 2) Giả sử X là tập mở trong Rn , các hàm fi (i = 0, 1, ..., m) xác định trên X. Giả sử x¯ là cực tiểu địa phương của (P), các hàm fi (i ∈ / I (x)) ¯ các hàm fi (i ∈ {0} ∪ I(x)) ¯ liên tục tại x, ¯ khả vi liên tục và các hàm fi (i ∈ I0 (x, ¯ d)) khả vi theo phương cấp 2 tại x¯ theo phương tới hạn bất kì d ∈ Rn . Khi đó, với mỗi phương tới hạn d ∈ Rn , không tồn tại z ∈ Rn là nghiệm của hệ 00 5 fi (x) ¯ z + fi (x, ¯ d) < 0, i ∈ I0 (x, ¯ d) . (1.1) Chứng minh Giả sử d là phương tới hạn cố định bất kì. Rõ ràng là trường hợp I0 (x, ¯ d) = 0/ không xẩy ra, vì x¯ là một điểm cực tiểu. Giả sử ngược lại tồn tại phương tới hạn d sao cho hệ (1.1) có nghiệm z ∈ Rn . Ta cố định i ∈ {0} ∪ I (x). ¯ Xét hàm một biến ϕi (t) = fi x¯ + td + 0, 5t 2 z . Bởi vì X là mở và x¯ là chấp nhận được, tồn tại δ > 0 sao cho ϕi xác định với 0 6 t < δ . Ta có 0 ϕi (t) = 5 fi x¯ + td + 0, 5t 2 z (d + tz) .
10 0 Do đó, ϕi (0) = 5 fi (x) ¯ d. Xét thương sau 0 2t −2 ϕi (t) − ϕi (0) − tϕi (0) = 2t −2 fi x¯ + td + 0, 5t 2 z − fi (x) ¯ − t 5 fi (x) ¯ d . Theo định lý giá trị trung bình tồn tại θi ∈ (0, 1) sao cho fi x¯ + td + 0, 5t 2 z = fi (x¯ + td) + 5 fi x¯ + td + 0, 5t 2 θi z 0, 5t 2 z . 00 Do fi ∈ C1 , tồn tại đạo hàm theo phương cấp 2, ϕi (0, 1) và 00 ¯ d) = lim 5 fi x¯ + td + 0, 5t 2 θi z z 5 fi (x) ¯ z + fi (x, t→+0 + lim 2t −2 ( fi (x¯ + td) − fi (x) ¯ − t 5 fi (x) ¯ d) t→+0 00 = ϕi (0, 1) . Bởi vì z là một nghiệm của hệ (1.1) với phương d, ta suy ra với mọi 0 i ∈ I0 (x, ¯ d), tồn tại εi > 0 sao cho ϕi (t) − ϕi (0) − tϕi (0) < 0, với mọi t ∈ (0, εi ), có nghĩa là fi x¯ + td + 0, 5t 2 z − fi (x) ¯ < 0, với mọi t ∈ (0, εi ) . (1.2) Xét các trường hợp sau: (1) Với mọi i ∈ {1, 2, ..., m} \ I (x) ¯ ta có fi (x) ¯ < 0. Vì vậy, do tính liên tục, tồn tại εi > 0 sao cho fi x¯ + td + 0, 5t 2 z < 0, với mọi t ∈ [0, εi ). 0 (2) Với mọi i ∈ I (x) ¯ \ I0 (x, ¯ d), ta có 5 fi (x) ¯ d = ϕi (0) < 0. Do đó, tồn tại εi > 0 sao cho ϕi (t) < ϕi (0), với mọi t ∈ (0, εi ). Vì vậy, ta có fi x¯ + td + 0, 5t 2 z < fi (x) ¯ = 0, với mọi t ∈ (0, εi ). ¯ d) \ {0}, do 5 fi (x) (3) Với mọi i ∈ I0 (x, ¯ d = 0, từ (1.2) suy ra tồn tại εi > 0 sao cho fi x¯ + td + 0, 5t 2 z < fi (x) ¯ = 0, với mọi t ∈ (0, εi ).
11 0 (4) Nếu 0 ∈ ¯ d) thì 5 f0 (x) / I0 (x, ¯ d < 0, nghĩa là ϕ0 (0) < 0. Do đó, với ε0 > 0 nào đó, ta có f0 x¯ + td + 0, 5t 2 z < f0 (x) ¯ với mọi t ∈ (0, ε0 ). (5) Nếu 0 ∈ I0 (x, ¯ d), thì 5 f0 (x) ¯ d = 0. Theo (2), tồn tại ε0 > 0 sao cho f0 x¯ + td + 0, 5t 2 z < f0 (x), ¯ với mọi t ∈ (0, ε0 ). Ta thấy rằng x¯ không là cực tiểu địa phương. Điều đó mâu thuẫn với giả thiết. Xét bài toán (P). Giả sử x¯ ∈ S. Nhắc lại [1]: nón tiếp tuyến Bouli- gand của S tại x¯ được định nghĩa như sau: n o T (S, x) n ¯ :={d ∈ R |∃ xk ⊂ S, lim xk = x, ¯ k→+∞ n o k k k ∃ t ⊂ (0, +∞) : d = lim t x − x¯ } k→+∞ Bao lồi đóng của T (S, x)¯ được ký hiệu bởi P (S, x) ¯ := cl (conv (T (S, x))) ¯ được gọi là nón giả tiếp tuyến của S tại x. ¯ Xét nón ¯ = {d ∈ Rn | 5 fi (x) L (x) ¯ d 6 0, i ∈ I (x)} ¯ . Định lý 1.2.2. (Điều kiện cần cấp hai đối ngẫu) Giả sử tất cả các giả thiết của Định lý 1.2.1 đúng. Khi đó, ứng với phương tới hạn bất kỳ d, tồn tại các nhân tử không âm λ0 , λ1 , ..., λm thỏa mãn λi fi (x) ¯ = 0, i = 1, 2, ..., m, 5L (x) ¯ = 0, λi 5 fi (x) ¯ d = 0, i ∈ {0} ∪ I(x), ¯ (1.3) 00 00 L (x, ¯ d) = ∑ λi fi (x, ¯ d) > 0. ¯ i∈{0}∪I(x) ¯ ⊆ P (S, x) Hơn nữa giả sử điều kiện chính quy Guignard L (x) ¯ đúng. Khi đó, ta có λ0 = 1. Chứng minh Xét ma trận A mà các hàng của nó là {5 fi (x) ¯ \ i ∈ I0 (x, ¯ d)} và vectơ b
12 n 00 o có các thành phần của nó là − fi (x, ¯ d) \ i ∈ I0 (x, ¯ d) . Với các khái niệm này, Định lý 1.2.2 khẳng định rằng hệ tuyến tính Az < b không có nghiệm. Điều này tương đương với việc nói rằng bài toán quy hoạch tuyến tính max {y|Az +~y 6 b} có giá trị tối ưu y¯ 6 0. Ở đây ~y là vectơ mà các thành phần của nó bằng y. Như vậy, bài toán quy hoạch đối ngẫu ( ) min bT λ |AT λ = 0, ∑ λi = 1, λi > 0 , i∈I0 (x,d) ¯ trong đó λ là vectơ có các thành phần là λi với i ∈ I0 (x, ¯ d), có một giá trị tối ưu không dương. Do đó, hệ AT λ = 0, bT λ 6 0, λ > 0, λ 6= 0 (1.4) có một nghiệm λ . Nếu ta xác định λi = 0, với i ∈ ({0} ∪ I (x))\I¯ 0 (x, ¯ d) hoặc / {0} ∪ I (x, i∈ ¯ d), thì từ (1.4) ta thấy rằng λ0 , λ1 , ..., λm thỏa mãn khẳng định của định lý. Ta thấy rằng các nhân tử Lagrange trong điều kiện cần cấp 2 phụ thuộc theo phương. Trong ví dụ sau đây, ta so sánh kết quả ở đây với Định lý 3.1 của Jeyakumar, Wang [11], trong đó các C1 hàm được sử dụng và các nhân tử không phụ thuộc vào phương. Định nghĩa sau đây được đưa vào trong [11]. Xét không gian M (Rn , Rn ) của các ma trận vuông cấp n × n. Giả sử f : Rn → Rn là khả vi liên tục và v ∈ Rn . Xét đạo hàm theo phương Dini trên của hàm v 5 f (1) (v 5 f ) (x + tu) − (v 5 f ) (x) (v 5 f )+ (x, u) := lim sup . t→0 t Định nghĩa 1.2.3. Ta nói rằng hàm f có Hessian xấp xỉ ∂∗2 f (x) tại x ∈ Rn nếu tồn tại một tập đóng bị chặn ∂∗2 f (x) ⊆ M (Rn , Rn ) và với mỗi v ∈ Rn , ta có (1) (v 5 f )+ (x, u) 6 max hMv, ui, ∀u ∈ Rn . M∈∂∗2 f (x)
13 Xét bài toán (P1 ) sau đây có ràng buộc đẳng thức và bất đẳng thức: Minimize f0 (x) , fi (x) 6 0, i = 1, 2, ..., m, h j (x) = 0, j = 1, 2, ..., q, trong đó fi , i = 0, 1, ..., m và h j , j = 1, 2, ..., q là C1 hàm trên Rn . Hàm Lagrange được cho bởi công thức m q L = f0 (x) + ∑ λi fi (x) + ∑ µ j h j (x) . i=1 j=1 Ký hiệu tập chấp nhận được là : C := x ∈ Rn | fi (x) 6 0, i = 1, 2, ..., m, h j (x) = 0, j = 1, 2, ..., q . Đặt ( ) m C (λ ) := x ∈ C| ∑ λi fi (x) = 0 . (1.5) i=1 Nón các phương chấp nhận được của tập C tại x ∈ C được định nghĩa như sau: F (C, x) := {u ∈ Rn |∃δ > 0, ∀α, 0 6 α 6 δ : x + αu ∈ C} . Ký hiệu Rm + là orthant dương của R m Định lý 1.2.4. ([11]) Giả sử bài toán (P1 ) có cực tiểu địa phương tại x.¯ Giả sử với mỗi λ ∈ Rm q 2 + và µ ∈ R , L (., λ , µ) có Hessian xấp xỉ ∂∗ L (x, ¯ λ , µ) tại ¯ Nếu điều kiện chính quy cấp 1 đúng tại x¯ thì tồn tại λi∗ > 0, λi∗ fi (x) x. ¯ =0 với i = 1, 2, ..., m, µ ∗ ∈ Rq , 5L (x, ¯ λ ∗ , µ ∗ ) = 0 và (∀u ∈ F (C (λ ∗ ) , x)) ¯ λ ∗ , µ ∗ ) : hMu, ui > 0. ∃M ∈ ∂∗2 L (x, ¯ ,
14 Ví dụ 1.2.5. Xét bài toán Minimize f0 = −x12 − x22 + x1 − x2 , p f1 = 1 + 2x2 − x1 − 1 6 0, f2 = x12 − x2 6 0. Ở đây f0 , f1 , f2 là các C1 hàm trong một lân cận x¯ = (0, 0). Điểm x¯ = (0, 0) không là tối ưu. Nếu ε > 0 đủ nhỏ tùy ý thì x (ε) = (ε, ε) là chấp nhận được và f0 (ε, ε) < f0 (0, 0). x¯ là một điểm dừng với λ = (λ1 , λ2 ) = (1, 0). Các phương tới hạn d = (u, u), với u > 0. Bởi vì d T 52 f0 + λ1 52 f1 + λ2 52 f2 d = −5u2 < 0, khi u 6= 0, theo Định lý 1.2.2, x¯ không là tối ưu. Mặt khác, F (C (1, 0) , x) ¯ = (0, 0). Do đó, Định lý 1.2.4 không thể loại bỏ x¯ không là tối ưu, bởi vì ∂∗2 L (x, ¯ λ ) và (0, 0)T 52 L (x, ¯ λ ) = 52 L (x, ¯ λ ) (0, 0) = 0. So sánh Định lý 1.2.2 với Định lý 3.2 của Hiriart - Urruty, Strodiot, Nguyễn [7], ta thấy rằng trong đó C1,1 hàm được sử dụng và các nhân tử không phụ thuộc vào phương. Ta đưa vào định nghĩa sau đây Định nghĩa 1.2.6. Giả sử f ∈ C1,1 (Rn ). Ma trận Hessian suy rộng của f tại x¯ , ký hiệu ∂ 2 f (x), ¯ là tập các ma trận được xác định là bao lồi của tập hợp sau: M|∃xi → x¯ với f khả vi 2 lần tại xi và 52 f (xi ) → M . Tập hợp ∂ 2 f (x) ¯ quy về 52 f (x) ¯ khi 5 f là khả vi chặt tại x. ¯ Xét tập C (λ ) xác định bởi (1.5) và nón tiếp tuyến Bouligand T (C (λ ) , x) ¯ của C (λ ). Khi đó, ta có định lý sau: Định lý 1.2.7. ([7]) Giả sử rằng bài toán (P1 ) với dữ liệu C1,1 có cực tiểu ¯ Nếu điều kiện chính quy cấp 1 đúng tại x¯ thì với mỗi nhân địa phương tại x. tử (λ , µ) ∈ Rm q + × R và với mỗi d ∈ T (C (λ ) , x), ¯ tồn tại ma trận 2 L (x, M ∈ ∂xx ¯ λ , µ) sao cho hMd, di > 0.
15 1.3 Điều kiện đủ tối ưu cho cực tiểu địa phương cô lập cấp 2 Trong phần này ta trình bày điều kiện đủ cho cực tiểu địa phương cô lập. Bổ đề 1.3.1. (Khai triển Taylor cấp 2) Giả sử f : X → R là hàm với miền xác định lồi, mở X. Giả sử rằng f là khả vi theo phương cấp 2 trên X. Khi đó, với mọi x, y ∈ X, tồn tại ξ ∈ [x, y) sao cho 1 00 f (ξ , y − x) 6 f (y) − f (x) − 5 f (x) (y − x) . (1.6) 2 Chứng minh Với mọi x, y ∈ X cố định, ta xét hàm một biến sau 1 ϕ (t) = f (x + t (y − x)) − f (x) − t 5 f (x) (y − x) + αt 2 2 trong đó α là hằng số. Do tính lồi của X cho nên hàm ϕ xác định trên [0, 1] và ϕ (0) = 0. Ta chọn α sao cho ϕ (1) = 0. Do đó, α = 2 (− f (y) + f (x) + 5 f (x) (y − x)). Theo định lý Weierstrass ϕ đạt giá trị cực đại toàn cục trên [0, 1] tại điểm θ nào đó. Nếu max {ϕ (t) | t ∈ [0, 1]} > 0 thì 0 < θ < 1. Do đó, 0 00 ϕ (θ ) = 0, ϕ (θ , 1) 6 0. Nếu max {ϕ (t) | t ∈ [0, 1]} = 0 thì không mất tính 0 chất tổng quát có thể giả sử θ = 0. Từ định nghĩa của ϕ, ta có ϕ (0) = 0. 00 Do tính chất cực đại, ta nhận được ϕ (θ , 1) 6 0. Trong cả hai trường hợp 00 ϕ (θ , 1) 6 0. Điều này kéo theo 00 f (ξ , y − x) + α 6 0, trong đó ξ = x + θ (y − x). Vì vậy (1.6) đúng. Bổ đề 1.3.2. (Xem [4, Bổ đề 1]) Giả sử ϕ : Rn → R là hàm C1,1 khả vi theo phương cấp 2; 5ϕ là Lipschitz với hằng số L trên x¯ + rclB, trong đó x¯ ∈ Rn , r > 0 và B := {x ∈ Rn | kxk< 1}. Khi đó, với u, v ∈ Rn và 0 < t < r, ta có