ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC TRẦN PHƯƠNG HOA ĐIỀU KIỆN CẦN VÀ ĐỦ TỐI ƯU CHO BÀI TOÁN QUY HOẠCH PHI TUYẾN CHUYÊN NGÀNH: TOÁN ỨNG DỤNG Mà SỐ: 60.46.01 LUẬN VĂN THẠC SĨ TOÁN HỌC Người hướng dẫn khoa học: PGS TS ĐỖ VĂN LƯU THÁI NGUYÊN - 2010 Số hóa Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn i Mục lục Mục lục ii Mở đầu Chương MỘT SỐ ĐỊNH LÝ LUÂN PHIÊN 1.1 CÁC ĐỊNH LÝ FARKAS THUẦN NHẤT VÀ KHÔNG THUẦN 1.2 NHẤT MỘT SỐ ĐỊNH LÝ LUÂN PHIÊN KHÁC Chương ĐIỀU KIỆN TỐI ƯU KHI KHƠNG GIẢ THIẾT ĐIỀU KIỆN CHÍNH QUY 2.1 CÁC KHÁI NIỆM VÀ KẾT QUẢ BỔ TRỢ 2.2 CÁC ĐIỀU KIỆN CẦN VÀ ĐỦ TỐI ƯU KHI KHÔNG GIẢ THIẾT ĐIỀU KIỆN CHÍNH QUY Chương 19 ĐIỀU KIỆN TỐI ƯU KHI GIẢ THIẾT ĐIỀU KIỆN CHÍNH QUY 30 3.1 CÁC ĐIỀU KIỆN CHÍNH QUY MANGASARIAN - FROMOVITZ CẤP MỘT VÀ CẤP HAI 30 3.2 CÁC ĐIỀU KIỆN TỐI ƯU CẤP MỘT VÀ CẤP HAI 34 Số hóa Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn ii Kết luận 44 Tài liệu tham khảo 45 Số hóa Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Mở đầu Lý thuyết điều kiện tối ưu cho toán quy hoạch toán học phát triển từ giai đoạn sớm tốn học có nhiều ứng dụng kinh tế, kỹ thuật Để dẫn điều kiện cần tối ưu người ta thường sử dụng công cụ hữu hiệu định lý tách tập lồi không tương giao định lý luân phiên (Theorems of the alternative) tương thích hệ tuyến tính không Các định lý luân phiên tiếng định lý J.Farkas, P Gordan, T S Motzkin, (xem [5]) Trong tổng quan [6], G Still M Streng trình bày điều kiện cần đủ tối ưu cho điểm cực tiểu địa phương chặt cấp một, cấp hai cực tiểu lập tốn quy hoạch phi tuyến trơn với ràng buộc đẳng thức bất đẳng thức không gian hữu hạn chiều Giữa điều kiện cần điều kiện đủ tối ưu thường có sai khác (a gap), điều kiện đủ mạnh điều kiện cần Khi giả thiết điều kiện quy Mangasarian - Fromovitz cấp cấp hai khơng có sai khác điều kiện cần điều kiện đủ Luận văn tập trung trình bày điều kiện cần đủ cho điểm cực tiểu địa phương chặt cấp cấp hai dạng gốc đối ngẫu cho toán quy hoạch phi tuyến trơn có hữu hạn ràng buộc đẳng thức bất Số hóa Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn đẳng thức không gian hữu hạn chiều giả thiết khơng giả thiết điều kiện quy Mangasarian - Fromovitz cấp cấp hai Luận văn bao gồm phần mở đầu, ba chương, kết luận danh mục tài liệu tham khảo Chương trình bày số định lý luân phiên bao gồm định lý Farkas không nhất, định lý luân phiên ổn định định lý luân phiên đặc trưng cho tính bị chặn tập nhân tử Kuhn Tucker Chương trình bày điều kiện cần cho cực tiểu địa phương điều kiện đủ cho điểm cực tiểu địa phương chặt cấp cấp hai dạng gốc đối ngẫu cho toán quy hoạch tốn học trơn có hữu hạn ràng buộc đẳng thức bất đẳng thức không gian hữu hạn chiều khơng giả thiết điều kiện quy Chương trình bày điều kiện cần đủ cho điểm cực tiểu địa phương chặt cấp cấp hai dạng gốc đối ngẫu có điều kiện quy Kết với điều kiện quy Mangasarian - Fromovitz cấp cấp hai khơng có sai khác điều kiện cần điều kiện đủ tối ưu cấp cấp hai tương ứng, tức ta nhận điều kiện đặc trưng cho cực tiểu địa phương chặt cấp cấp hai Nhân dịp tơi 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 đỡ tơi hồn thành luận văn Tôi xin chân thành cảm ơn Ban chủ nhiệm khoa tốn, Phịng đào tạo sau đại học trường Đại học Khoa học - Đại học Thái Nguyên thầy cô giáo tham gia giảng dạy khoá học Xin chân thành cảm ơn gia đình, bạn bè đồng nghiệp thành viên Số hóa Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn lớp cao học toán K2 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 Thái Nguyên, tháng năm 2010 Trần Phương Hoa Số hóa Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn Chương MỘT SỐ ĐỊNH LÝ LUÂN PHIÊN Chương trình bày cách vắn tắt định lý luân phiên sử dụng để chứng minh điều kiện tối ưu gốc điều kiện tối ưu đối ngẫu tương đương Ta bắt đầu với định lý Farkas tiếng dạng dạng không Định lý Farkas ứng dụng chứng minh điều kiện tối ưu cấp dạng không để chứng minh điều kiện tối ưu cấp hai Các kết chương lấy [4] − [6] 1.1 CÁC ĐỊNH LÝ FARKAS THUẦN NHẤT VÀ KHÔNG THUẦN NHẤT Trước hết ta nhắc lại định lý Farkas [5] Định lý 1.1 ([5]) Cho ak1 , bk2 , ck3 ∈ Rn , k1 ∈ K1 , k2 ∈ K2 , k3 ∈ K3 với K1 , K2 , K3 tập số hữu hạn Giả sử K1 = ∅ Khi đó, hai khả (i) (ii) đúng: (i) Tồn ξ ∈ Rn thoả mãn ξ t ak1 < 0, k ∈ K1 , ξ t bk2 ≤ 0, k ∈ K2 , ξ t ck3 = 0, k ∈ K3 , Số hóa Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn ξ t chuyển vị vectơ ξ (ii) Tồn số µk1 ≥ 0, k1 ∈ K1 khơng đồng thời 0, µk2 ≥ 0, k2 ∈ K2 λk3 ∈ R, k3 ∈ K3 cho µk1 ak1 + k1 ∈K1 µk2 bk2 + k2 ∈K2 λk3 ck3 = k3 ∈K3 Định lý sau cho ta tổng qt hố định lý Farkas khơng Định lý 1.2 Giả sử ak1 , bk2 , ck3 ∈ Rn , k1 ∈ K1 , k2 ∈ K2 , k3 ∈ K3 với K1 , K2 , K3 tập số hữu hạn; αk1 , βk2 , γk3 ∈ R, k1 ∈ K1 , k2 ∈ K2 , k3 ∈ K3 Khi đó, hai khả (i) (ii) đúng: (i) Tồn ξ ∈ Rn thoả mãn ξ t ak1 < αk1 , k ∈ K1 , ξ t bk2 ≤ βk2 , k ∈ K2 , ξ t ck3 = γk3 , k ∈ K3 (ii) Tồn số µk1 ≥ 0, k1 ∈ K1 , µ0 ≥ 0, khơng đồng thời 0, µk2 ≥ 0, k2 ∈ K2 λk3 ∈ R, k3 ∈ K3 cho µk1 ak1 + k1 ∈K1 µk2 bk2 + k2 ∈K2 µk1 αk1 + k1 ∈K1 λk3 ck3 = 0, k3 ∈K3 λk3 γk3 = −µ0 ≤ µk2 βk2 + k2 ∈K2 k3 ∈K3 Chứng minh Đưa thêm biến ξn+1 , điều kiện (i) viết tương đương sau: Số hóa Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn (i’) Tồn nghiệm (ξ, ξn+1 ) hệ:     −ξn+1 < 0,       ξ t ak1 − ξn+1 αk1 < 0, k1 ∈ K1 ,    ξ t bk2 − ξn+1 βk2 ≤ 0,       ξ t ck3 − ξn+1 γk3 = 0, k2 ∈ K2 , k3 ∈ K3 Lưu ý tập số K1 tương ứng với bất đẳng thức chặt khác rỗng Từ định lý 1.1 ta suy ra: (ii’) Tồn số µk1 , k1 ∈ K1 , µ0 ≥ 0, khơng đồng thời 0, µk2 ≥ 0, k2 ∈ K2 λk3 ∈ R, k3 ∈ K3 cho         ck3 bk2 ak1  = + + λk3  µk2  µk1  µ0   + −1 −γk3 −βk2 −αk1 k3 ∈K3 k2 ∈K2 k1 ∈K1 Đẳng thức tương đương với (ii) 1.2 MỘT SỐ ĐỊNH LÝ LUÂN PHIÊN KHÁC Để đề cập điều kiện tối ưu mạnh ta cần dạng khác định lý luân phiên Định lý gọi định lý luân phiên ổn định Định lý 1.3 Cho bk2 , ck3 ∈ Rn , k2 ∈ K2 , k3 ∈ K3 với K2 , K3 tập số hữu hạn Khi đó, điều kiện (i) (ii) sau tương đương: (i) Không tồn vectơ ξ ∈ Rn , ξ = thoả mãn ξ t bk2 ≤ 0, k2 ∈ K2 , ξ t ck3 = 0, k3 ∈ K3 Số hóa Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn (ii) Với nón D= λk3 ck3 µk2 ≥ 0, k2 ∈ K2 , λk3 ∈ R, k3 ∈ K3 , µk2 bk2 + k2 ∈K2 k3 ∈K3 ta có ∈ int D Chứng minh Điều kiện (i) tương đương với: với d ∈ Rn cố định, không tồn ξ ∈ Rn thoả mãn    −ξ t d < 0,     ξ t bk2 ≤ 0, k2 ∈ K2 ,      ξ t ck = 0, k3 ∈ K3 Theo định lý 1.1, điều tương đương với: với d ∈ Rn cố định, tồn số µ0 > 0, µk2 ≥ 0, k2 ∈ K2 , λk3 ∈ R, k3 ∈ K3 cho −µ0 d + µk2 bk2 + k2 ∈K2 λk3 ck3 = k3 ∈K3 Chia hai vế cho µ0 , ta d ∈ D Vì d tuỳ ý, nên điều tương đương với D = Rn , D nón với điều kiện ∈ int D Dạng sau định lý luân phiên thích hợp để đặc trưng cho tính bị chặn tập nhân tử Kuhn - Tucker Định lý 1.4 ([4]) Cho a0 , ak1 , ck3 ∈ Rn , k1 ∈ K1 , k3 ∈ K3 với K1 , K3 tập số hữu hạn thoả mãn |K1 | + |K3 | ≥ 1, |K1 | ký hiệu số phần tử K1 , |K3 | ký hiệu số phần tử K3 Đặt Q= (µ, λ), µ ∈ R|K1 | , µ ≥ 0, λ ∈ R|K3 | a0 + µk1 ak1 + k1 ∈K1 Số hóa Trung tâm Học liệu - Đại học Thái Nguyên λk3 ck3 = k3 ∈K3 http://www.lrc-tnu.edu.vn 31 Định nghĩa 3.2 Giả sử x ∈ M với C x = {0} Ta nói điều kiện quy Mangasarian - Fromovitz cấp hai (SOMFCQ) thoả mãn x (i) ∇hi (x), i ∈ I độc lập tuyến tính; (ii) Với = x˜ ∈ C x ta có Cx,˜x = ∅, có nghĩa tồn vectơ ξ ∈ Rn cho x˜t ∇2 gj (x)˜ x + ∇gj (x)ξ < 0, j ∈ J∗∗ (x, x˜), x˜t ∇2 hi (x)˜ x + ∇hi (x)ξ = 0, i ∈ I Nhận xét 3.1 Sự kiện, MFCQ kéo theo SOMFCQ chứng minh sau: ∇hi (x), i ∈ I độc lập tuyến tính nên với x˜ ∈ C x tồn d ∈ Rn cho x˜t ∇2 hi (x)˜ x + ∇hi (x)d = 0, i ∈ I Khi đó, với vectơ ξ ∈ Rn thoả mãn điều kiện (ii) định nghĩa MFCQ, ta đặt ξ(t) = d + tξ ta có x˜t ∇2 gj (x)˜ x + ∇gj (x)ξ(t) < 0, j ∈ J∗∗ (x, x˜), x˜t ∇2 hi (x)˜ x + ∇hi (x)ξ(t) = 0, i ∈ I, với t > đủ lớn, có nghĩa ξ(t) vectơ thoả mãn điều kiện (ii) định nghĩa SOMFCQ Nhận xét 3.2 Điều kiện quy x ∈ M xem thông tin thêm liên quan đến cấu trúc tập chấp nhận x Chú ý, cách đưa vào MFCQ SOMFCQ hàm mục tiêu g0 hàm ràng buộc gj , j ∈ J khơng cịn xử lý giống Số hóa Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 32 Không có điều kiện quy, tập chấp nhận gồm điểm Chẳng hạn, tập chấp nhận M ⊂ R2 cho x21 + x22 ≤ Ví dụ sau cho ta thấy SOMFCQ thoả mãn MFCQ khơng thoả mãn Ví dụ 3.1 Xét tập chấp nhận M = (x1 , x2 ) ∈ R2 − x2 + x21 ≤ 0, x2 − 2x21 ≤ (xem ví dụ 2.1) Tại x = ta có C x = x˜ ∈ R2 x˜2 = , Cx = ∅, Cx,˜x = x˜˜ ∈ R2 2˜ x21 < x˜˜2 < 4˜ x21 = ∅, ∀0 = x˜ ∈ C x Như vậy, x = 0, SOMFCQ thoả mãn MFCQ không thoả mãn Nhận xét 3.3 Giả sử x¯ ∈ M ¯ ∈ Q0 với µ a) Giả sử MFCQ x¯ Nếu (¯ µ, λ) ¯ = điều x ¯ kiện Fritz - John định lý 2.4 ta phải có µ ¯0 > 0; có nghĩa ta giả sử điều kiện Kuhn - Tucker ∇g0 (¯ x) + ¯ i ∇hi (¯ λ x) = µ ¯j ∇gj (¯ x) + (3.1) i∈I j∈J∗ (¯ x) Để chứng minh điều này, ta giả sử µ ¯0 = Nếu ξ ∈ Rn thoả mãn điều kiện định nghĩa 3.1 ¯ i ∇hi (¯ λ x) ξ = µ ¯j ∇gj (¯ x) + 0= j∈J∗0 (¯ x) i∈I Số hóa Trung tâm Học liệu - Đại học Thái Nguyên µ ¯j ∇gj (¯ x)ξ < j∈J∗ (¯ x) http://www.lrc-tnu.edu.vn 33 Điều cho ta mâu thuẫn Bất đẳng thức vế phải suy µ ¯j khơng âm không đồng thời b) Giả sử x¯, với C x¯ = {0}, SOMFCQ thoả mãn Khi đó, điều kiện cấp hai định lý 2.4 x¯ (2.19) (2.20) giả sử µ ¯0 = 1, có nghĩa (2.19) thay (3.1) Để chứng minh điều này, ta giả sử µ ¯0 = Khi đó, lấy x˜ ∈ C x¯ , x˜ = 0, x) (2.19) (2.20) ta có C x¯ = {0} Theo nhận xét 2.7, tập số J∗0 (¯ (¯ x, x˜) thay J∗∗ Nhân (2.19) với ξ định nghĩa 3.2 cộng với (2.20) ta nhận ¯ i (˜ λ xt ∇2 hi (¯ x)˜ x +∇hi (¯ x)ξ) < µ ¯j (˜ xt ∇2 gj (¯ x)˜ x +∇gj (¯ x)ξ)+ 0≤ i∈I j∈J∗∗ (¯ x,˜ x) Điều cho ta mâu thuẫn Do nhận xét ta thấy với điều kiện MFCQ ta cần đưa vào tập nhân tử Kuhn - Tucker sau đây: Qx = (µ, λ) ∈ Qx | µ0 = µj ≥ 0, j ∈ J∗ (x), λi ∈ R, i ∈ I = ∇g0 (x) + µj ∇gj (x) + j∈J∗ (x) λi ∇hi (x) = i∈I Tính bị chặn tập Qx đặc trưng kết sau Gauvin [3] Định lý 3.1 ([3]) Giả sử x ∈ M Qx = ∅ Khi đó, Qx bị chặn ⇔ MFCQ x Số hóa Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 34 3.2 CÁC ĐIỀU KIỆN TỐI ƯU CẤP MỘT VÀ CẤP HAI Với điều kiện quy Mangasarian - Fromovitz cấp ta bỏ khác biệt điều kiện cần điều kiện đủ định lý chương Định lý 3.2 (Điều kiện cần đủ tối ưu) Giả sử x¯ ∈ M Khi đó, (i) Điều kiện cấp Giả sử điều kiện quy (MFCQ) x¯ Khi đó, x¯ cực tiểu địa phương chặt cấp toán (P) điều kiện đủ cấp định lý 2.3 2.5 (ii) Điều kiện cấp hai Giả sử C x¯ = {0} điều kiện quy (SOMFCQ) thoả mãn x¯ Khi đó, x¯ cực tiểu địa phương chặt cấp hai toán (P) điều kiện đủ cấp hai định lý 2.3 2.2 Chứng minh (i) Ta cần chứng minh chiều thuận chiều ngược lại suy từ định lý 2.3 2.5 Giả sử tồn vectơ x˜ ∈ C x¯ , x˜ = Theo MFCQ, tồn ξ ∈ Rn cho ∇gj (¯ x)ξ ≤ c < 0, j ∈ J∗ (¯ x), ∇hi (¯ x)ξ = 0, i ∈ I Do đó, với ε > cố định, ta có ∇gj (¯ x)(˜ x + εξ) ≤ εc, ∇hi (¯ x)(˜ x + εξ) = 0, Số hóa Trung tâm Học liệu - Đại học Thái Nguyên j ∈ J∗ (¯ x), (3.2a) i ∈ I, (3.2b) http://www.lrc-tnu.edu.vn 35 có nghĩa (˜ x + εξ) ∈ Cx¯ Ta giả sử x˜ + εξ ≥ Áp dụng bổ đề 2.1(c) ta suy tồn đường cong γε số Sε > cho γε (s) ∈ M, γε (0) = x¯, với ≤ s < Sε , γε (0) = x˜ + εξ Hơn nữa, sử dụng γ(s) = x¯ + s(˜ x + εξ) + o(s), ∇g0 (¯ x)˜ x ≤ 0, ta nhận g0 (γε (s)) − g0 (¯ x) = s∇g0 (¯ x)(˜ x + εξ) + o(s) ≤ sε|∇g0 (¯ x)ξ| + o(s) ≤ ε|∇g0 (¯ x)ξ| s(˜ x + εξ) + o(s) = ε|∇g0 (¯ x)ξ| γε (s) − x¯ + o(s) Điều với ε > Vì vậy, với ε → 0, ta có mâu thuẫn với định nghĩa (2.1) cực tiểu địa phương chặt cấp p = (ii) Ta chứng minh chiều thuận Theo giả thiết, tồn κ > lân cận U x¯ cho, với gˆ(x) := g0 (x) − κ x − x¯ gˆ(x) − gˆ(¯ x) = g0 (x) − g0 (¯ x) − κ x − x¯ ≥ 0, ta có ∀x ∈ M ∩ U Do , x¯ cực tiểu địa phương toán (P ) cực tiểu hàm gˆ tập chấp nhận (P ) Lưu ý rằng, ∇ˆ g (¯ x) = ∇g0 (¯ x), nên Số hóa Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 36 điều kiện cho (P ) (P ) trùng Theo định lý 2.4(ii), với ¯ i ∈ R, i ∈ I, ¯j ≥ 0, j ∈ J∗0 (¯ x), λ x˜ ∈ C x¯ , (2.19) thoả mãn với µ x˜t µ ¯0 ∇2 gˆ(¯ x) + i∈I j∈J∗ (¯ x) = x˜t ¯ i ∇2 hi (¯ λ x) x˜ − 2¯ µ0 κ˜ xt x˜ ≥ 0, µ ¯j ∇2 gj (¯ x) + j∈J∗0 (¯ x) ¯ i ∇2 hi (¯ λ x) x˜ µ ¯j ∇2 gj (¯ x) + (3.3) i∈I đó, ta sử dụng ∇2 gˆ(¯ x) = ∇2 g0 (¯ x) − 2κI Vì điều kiện quy SOMFCQ thoả mãn x¯, theo nhận xét 3.3 ta giả sử µ ¯0 = Khi (3.3) cho ta điều kiện cấp hai (2.21) Ngược lại, theo định lý 2.2, cần với giả thiết định lý x¯ cực tiểu địa phương cấp Để làm điều ta lấy x˜ ∈ C x¯ với x˜ = 0, vectơ ξ ∈ Cx,˜x (theo SOMFCQ tồn ξ) Khi đó, theo bổ đề 2.1(ii), có đường cong γ(s) = x¯ + s˜ x + s2 ξ + o(s2 ) S0 > 0, cho γ(s) ∈ M với ≤ s < S0 Sử dụng ∇g0 (¯ x)˜ x ≤ ta có: g0 (γ(s)) − g0 (¯ x) ≤ s2 (˜ xt ∇2 g0 (¯ x)˜ x + ∇g0 (¯ x)ξ) + o(s2 ) ≤ O( γ(s) − x˜ ); có nghĩa là, x¯ khơng thể cực tiểu địa phương cấp Điều kiện đủ tối ưu định lý 2.2 không đủ mạnh để đảm bảo điểm cực tiểu địa phương chặt cực tiểu địa phương lập Ví dụ sau minh hoạ điều Số hóa Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 37 Ví dụ 3.2 Xét toán tối ưu R: g0 (x) = x2 ,   x6 (1 + sin ), x g1 (x) =  0,  x=0 ≤  x=0 Ta có M= xx= ,k ∈ Z (4k − 1)π với x¯ = C x¯ = R, Cx¯ = ∅; Cx¯,˜x = ∅, ∪ {0}, ∀˜ x ∈ C x¯ Do đó, điều kiện quy (SOMFCQ) khơng thoả mãn x¯ Tuy nhiên, x¯ = điều kiện tối ưu cấp hai định lý 2.2 với cặp nhân tử (¯ µ0 , µ ¯1 ) với µ ¯0 > Do đó, x¯ cực tiểu địa phương chặt cấp hai Bởi tất điểm thuộc M \ {0} cực tiểu địa phương, x¯ cực tiểu lập Tuy nhiên điều kiện quy cấp hai định lý 2.2 với ¯ ∈ Q0 với µ x˜ ∈ C x¯ với (¯ µ, λ) ¯ = 0, điều kiện x ¯ quy (MFCQ) (SOMFCQ) thoả mãn x¯ cực tiểu cô lập Định lý 3.3 Giả sử x¯ ∈ M (i) (ii) đúng, (i) C x¯ = {0} MFCQ thoả mãn x¯; 0 (ii) C x¯ = {0}, Qx¯ = {0}, SOMFCQ thoả mãn x¯, với ¯ ∈ Q0 , (¯ ¯ = x˜ ∈ C x¯ , với (¯ µ, λ) x ¯ µ, λ) = 0, x˜t ¯ i ∇2 hi (¯ λ x) x˜ > µ ¯j ∇2 gj (¯ x) + j∈J∗0 (¯ x) Số hóa Trung tâm Học liệu - Đại học Thái Nguyên i∈I http://www.lrc-tnu.edu.vn 38 Khi đó, tồn lân cận U x¯ cho 0∈ / Dx0¯ , có nghĩa điều kiện Fritz - John không thoả mãn, với x ∈ U ∩ M \ {¯ x} (3.4) Đặc biệt, x¯ cực tiểu địa phương chặt cô lập cấp trường hợp (i) cực tiểu địa phương chặt cô lập cấp hai trường hợp (ii) Chứng minh Giả sử phát biểu (3.4) không Khi đó, tồn dãy xk ∈ M, k ∈ N, cho lim xk = x¯, vectơ nhân tử tương ứng (µk , λk ) ∈ Qxk , (µk , λk ) = k→∞ 0, cho µkj ∇gj (xk ) + ∇x Lk := µk0 ∇g0 (xk ) + λki ∇hi (xk ) = (3.5) i∈I j∈J∗ (xk ) Ta viết xk = x¯ + tk x˜k , x˜k = tk > Khi lim tk = 0, k→∞ Bằng cách chuyển sang dãy hội tụ, ta giả sử lim x˜k = x˜, k→∞ x˜ = Do tính liên tục, với tập số ràng buộc tích cực, ta có J∗ (xk ) ⊂ J∗ (¯ x), với k đủ lớn (3.6) Như vậy, với k đủ lớn (3.5) thay thể ∇x Lk = µk0 ∇g0 (xk ) + µkj ∇gj (xk ) + j∈J∗ (¯ x) Số hóa Trung tâm Học liệu - Đại học Thái Nguyên λki ∇hi (xk ) = 0, i∈I http://www.lrc-tnu.edu.vn 39 với µkj = k ∈ J∗ (¯ x) \ J∗ (xk ) (3.7) Như vậy, vectơ (µk , λk ) coi phần tử Qx¯ Trong (3.7), ta giả sử tính bị chặn cho vectơ (µk , λk ) giả sử (µk , λk ) = 1, k ∈ N, cách chuyển qua dãy hội tụ, ta có ¯ lim (µk , λk ) = (¯ µ, λ) k→∞ Trong (3.7) ta cho k → ∞ nhận ¯ i ∇hi (¯ λ x) = 0, µ ¯j ∇gj (¯ x) + ∇x L := µ ¯0 ∇g0 (¯ x) + (3.8) i∈I j∈J∗ (¯ x) ¯ ∈ Q0 Do điều kiện quy MFCQ (hoặc SOMFCQ có nghĩa (¯ µ, λ) x ¯ trường hợp (ii)), ta có µ ¯0 > (xem nhận xét 3.3) Bởi lim µkj = µ ¯j , k→∞ với số j cho µ ¯j > ta có gj (xk ) = gj (¯ x) = 0, với k đủ lớn Do đó, với j ∈ J∗ (¯ x) ta có gj (xk ) − gj (¯ x) = tk ∇gj (¯ x)˜ x + o(tk ) = 0, µ ¯j > 0, ≤ 0, µ ¯j = 0, hi (xk ) − hi (¯ x) = tk ∇hi (¯ x)˜ x + o(tk ) = 0, i ∈ I Do ∇gj (¯ x)˜ x ≤ 0, µ ¯j ∇gj (¯ x)˜ x = 0, ∇hi (¯ x)˜ x = 0, Số hóa Trung tâm Học liệu - Đại học Thái Nguyên j ∈ J∗ (¯ x), i ∈ I http://www.lrc-tnu.edu.vn (3.9a) (3.9b) 40 Hơn nữa, nhân (3.8) với x˜, µ ¯0 > 0, nên ta có ∇gj (¯ x)˜ x = x˜ ∈ C x¯ Điều cho ta mâu thuẫn trường hợp (i) (ii) Ta ý µkj ∇gj (¯ x)˜ x = 0, j ∈ J∗ (¯ x), (3.10) với k đủ lớn Thực tế, từ điều kiện: ∇gj (¯ x)˜ x < 0, với tk > 0, ta suy gj (xk ) − gj (¯ x) = tk ∇gj (¯ x)˜ x + o(tk ) < k → ∞, µkj = Bằng cách sử dụng (3.7), (3.8) ta có khai triển Taylor sau: ¯ i )∇hi (¯ (λki − λ x) (µkj − µ ¯j )∇gj (¯ x) + = ∇ x Lk − ∇ x L = j∈J∗0 (¯ x) i∈I µkj ∇2 gj (¯ x)˜ xk + + tk j∈J∗0 (¯ x) λki ∇2 hi (¯ x)˜ xk + o(tk ) i∈I Nhân với x˜t , sử dụng (3.9), (3.10) ∇g0 (¯ x)˜ x = ta nhận ¯ i ∇2 hi (¯ λ x) x˜ = o(tk ) k → ∞ µ ¯j ∇2 gj (¯ x) + tk x˜t j∈J∗0 (¯ x) i∈I Chia cho tk cho k → ∞ ta đến mâu thuẫn trường hợp (ii) Vì gradient ∇hi (¯ x), i ∈ I độc lập tuyến tính, tính liên tục ∇hi (x) nên tồn lân cận U x¯ cho ∀x ∈ U , gradient ∇hi (x), i ∈ I, độc lập tuyến tính Vì theo định lý 2.4, từ (3.4) suy U chứa điểm cực tiểu địa phương x = x¯ Bây ta xét điều kiện quy độc lập tuyến tính điểm x¯ ∈ M Số hóa Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 41 Định nghĩa 3.3 Ta nói điều kiện quy độc lập tuyến tính (LICQ) x ∈ M gradient ∇hi (x), i ∈ I, ∇gj (x), j ∈ J∗ (x) độc lập tuyến tính Nhận xét 3.4 Nếu x¯ ∈ M LICQ x¯ MFCQ thoả mãn Do đó, x cực tiểu địa phương toán (P ), nhân tử µ ¯0 hàm mục tiêu g0 xuất điều kiện tối ưu (định lý 2.4) chọn (nhận xét 3.3) Trong phần ta xét điểm tới hạn Định nghĩa 3.4 Điểm x¯ ∈ M gọi điểm tới hạn LICQ x¯ tồn ¯ i , i ∈ I cho nhân tử µ ¯j , j ∈ J∗ (¯ x); λ ¯ i ∇hi (¯ λ x) = µ ¯j ∇gj (¯ x) + ∇g0 (¯ x) + j∈J∗ (¯ x) (3.11) i∈I Nhận xét 3.5 Trong định nghĩa 3.4 nhân tử xác định (vì Qx¯ có phần tử) nhân tử tương ứng với ràng buộc bất đẳng thức khơng địi hỏi điều kiện không âm Ta gần điểm x¯, tập chấp nhận có cấu trúc tốt LICQ x¯ Giả sử x¯ ∈ M (không thiết điểm tới hạn) giả sử LICQ x¯ Khơng tính tổng qt ta giả sử I = 1, , q J∗ (¯ x) = q + 1, , p , p ≤ n Số hóa Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 42 Khi đó, tồn vectơ ξp+1 , , ξn ∈ Rn cho: ∇hi (¯ x), i = 1, , q, ∇gj (¯ x), j = q + 1, , p, ξkt , k = p + 1, , n , sở Rn Xét ánh xạ Φ : Rn → Rn xác định   hi (x), i = 1, , q     Φ : x → −gj (x), j = q + 1, , p    t ξk (x − x¯), k = p + 1, , n (3.12) Rõ ràng, Φ(¯ x) = ∇x Φ(¯ x) ánh xạ lên (chính quy) Do đó, tồn lân cận U x¯ cho tồn ánh xạ ngược khả vi Φ−1 U Hơn nữa, tồn lân cận V gốc cho Φ : U ∩ M → V ∩ ({0}q × Hp−q × Rn−p ), H = {x ∈ R | x ≥ 0} Bây ta xét trường hợp x¯ điểm tới hạn toán (P ) Trước hết ta làm rõ vai trò tham số Lagrange Đặt xˆ = Φ(x) gˆ0 = g0 Φ−1 Trong toạ độ mới, điểm Φ(¯ x) = điểm tới hạn gˆ0 ta có ∂ˆ g0 ¯i, (0) = −λ ∂ xˆi ∂ˆ g0 (0) = µ ¯j , ∂ xˆj ∂ˆ g0 (0) = 0, ∂ xˆk i = 1, , q, j = q + 1, , p, k = p + 1, , n Chú ý x ∈ M ∩ U ⇒ xˆ ∈ M := xˆ xˆi = 0, i = 1, , q; xˆj ≥ 0, j = q + 1, , p Ta giả sử µ ¯j = 0, ∀j = q + 1, , p, ma trận ∂ gˆ0 (0), ∂ xˆk ∂ xˆl Số hóa Trung tâm Học liệu - Đại học Thái Nguyên k, l = p + 1, , n http://www.lrc-tnu.edu.vn 43 quy Khi đó, khai triển Taylor gˆ0|M 0, mà với toạ độ xˆi xét số hạng không triệt tiêu đầu tiên, ta viết p gˆ0 (ˆ x) = µ ¯j xˆj + j=q+1 n xˆk k,l=p+1 xˆi = 0, xˆj ≥ 0, ∂ˆ g0 (0)ˆ xl + ρ(ˆ x), ∂ xˆk ∂ xˆl i = 1, , q, j = q + 1, , p, ρ(ˆ x) chứa tất số hạng khác khai triển Taylor Số µ ¯j âm (dương) gọi số tuyến tính LI (đối số tuyến tính LCI) x¯ Số hóa Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 44 Kết luận Luận văn trình bày điều kiện cần cho cực tiểu địa phương điều kiện đủ cho điểm cực tiểu địa phương chặt cấp cấp hai toán quy hoạch toán học phi tuyến trơn có hữu hạn ràng buộc đẳng thức bất đẳng thức khơng giả thiết điều kiện quy, điều kiện đặc trưng cho cực tiểu địa phương chặt cấp cấp hai giả thiết tương ứng điều kiện quy Mangasarian - Fromovitz cấp cấp hai Chú ý công cụ hữu hiệu định lý luân phiên Khi sử dụng định lý Farkas ta chứng minh điều kiện tối ưu cấp sử dụng định lý Farkas không ta chứng minh điều kiện tối ưu cấp hai Khi giả thiết điều kiện quy Mangasarian - Fromovitz cấp cấp hai khơng có sai khác điều kiện cần điều kiện đủ cho cực tiểu địa phương chặt cấp cấp hai tương ứng Lý thuyết điều kiện tối ưu cấp cấp hai cho điểm cực tiểu địa phương cực tiểu địa phương chặt toán quy hoạch tốn học trơn khơng trơn đề tài nhà tốn học quan tâm nghiên cứu Số hóa Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 45 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, Nhà xuất Khoa học Kĩ thuật Tiếng Anh [2] Ben Tal A (1980), Second - order and related extremality conditions in nonlinear progammming, Journal of Optimization Theory and Applications, Vol 31, pp 143 - 165 [3] Gauvin J (1977), A necessary and sufficient regularity condition to have bounded multipliers in nonlinear progammming, Mathematical Programming, Vol 12, pp 136 - 138 [4] Mangasarian O L (1981), A stable theorem of the alternative: An extension to the Gordon theorem, Linear Algebra and Its Applications, Vol 41, pp 209 - 223 [5] Mangasarian O L (1969), Nonlinear progammming, McGraw-Hill, New York [6] Still G and Streng M (1996), Otimality conditions in smooth nonlinear progammming, J Optim Theory Appl, Vol 90, pp 483 - 515 Số hóa Trung tâm Học liệu - Đại học Thái Nguyên http://www.lrc-tnu.edu.vn ... kiện cần điều kiện đủ tối ưu thường có sai khác (a gap), điều kiện đủ mạnh điều kiện cần Khi giả thiết điều kiện quy Mangasarian - Fromovitz cấp cấp hai khơng có sai khác điều kiện cần điều kiện. .. 1, 2} Cx¯,˜x = Cx¯ 2.2 CÁC ĐIỀU KIỆN CẦN VÀ ĐỦ TỐI ƯU KHI KHÔNG GIẢ THIẾT ĐIỀU KIỆN CHÍNH QUY Phần trình bày điều kiện cần đủ tối ưu khơng địi hỏi điều kiện quy cho ràng buộc bất đẳng thức phát... 3.2 CÁC ĐIỀU KIỆN TỐI ƯU CẤP MỘT VÀ CẤP HAI Với điều kiện quy Mangasarian - Fromovitz cấp ta bỏ khác biệt điều kiện cần điều kiện đủ định lý chương Định lý 3.2 (Điều kiện cần đủ tối ưu) Giả sử