Tài liệu Tính tựa chuẩn tắc, tính giả chuẩn tắc và quy tắc nhân tử lagrange

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC DƯƠNG THỊ YẾN TÍNH TỰA CHUẨN TẮC, TÍNH GIẢ CHUẨN TẮC VÀ QUY TẮC NHÂN TỬ LAGRANGE CHUYÊN NGÀNH: TOÁN ỨNG DỤNG MÃ SỐ: 60.46.36 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 - 2011 Số hóa bởi 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 1 1 ĐIỀU KIỆN CẦN FRITZ JOHN 4 1.1 KẾT QUẢ BỔ TRỢ . . . . . . . . . . . . . . . . . . . . . 4 1.2 ĐIỀU KIỆN CẦN FRITZ JOHN . . . . . . . . . . . . . . 10 1.3 NHÂN TỬ LAGRANGE CÓ THÔNG TIN VÀ NHÂN TỬ LAGRANGE MẠNH . . . . . . . . . . . . . . . . . . . . . 17 2 TÍNH TỰA CHUẨN TẮC, TÍNH GIẢ CHUẨN TẮC VÀ CÁC ĐIỀU KIỆN CHÍNH QUY 29 2.1 TÍNH TỰA CHUẨN TẮC VÀ TÍNH GIẢ CHUẨN TẮC . 29 2.2 ĐIỀU KIỆN ĐỦ CHO TÍNH GIẢ CHUẨN TẮC . . . . . 35 2.3 ĐIỀU KIỆN CẦN VÀ ĐỦ CHO TÍNH TỰA CHUẨN TẮC 38 3 HÀM PHẠT CHÍNH XÁC 43 3.1 TÍNH GIẢ CHUẨN TẮC VÀ HÀM PHẠT CHÍNH XÁC 43 3.2 BIỂU DIỄN MỞ RỘNG CỦA TẬP RÀNG BUỘC 49 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên . . . http://www.lrc-tnu.edu.vn ii 3.3 CÁC VÍ DỤ . . . . . . . . . . . . . . . . . . . . . . . . . 50 Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . . 57 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 1 Mở đầu Lí thuyết các điều kiện tối ưu là một bộ phận quan trọng của lí thuyết các bài toán cực trị. Các quy tắc nhân tử Lagrange đã và đang thu hút được sự quan tâm nghiên cứu của nhiều tác giả. Thông thường người ta thiết lập các điều kiện cần tối ưu kiểu Fritz John và từ đó dẫn các điều kiện cần tối ưu kiểu Kuhn-Tucker với các điều kiện chính quy khác nhau. Các điều kiện cần tối ưu có thể dẫn bằng cách thiết lập các định lí luân phiên làm công cụ trên cơ sở sử dụng các định lí tách các tập lồi hoặc bằng phương pháp hàm phạt chính xác. Các nhân tử Lagrange với một vài tính chất phụ sẽ hữu ích trong nghiên cứu tính chất của nghiệm tối ưu. Năm 2002, D. P. Bertsekas và A. E. Ozdaglar [3] đã thiết lập quy tắc nhân tử Lagrange kiểu Fritz John, trong đó các nhân tử Lagrange có thêm một tính chất phụ (tính chất (CV)). Ba loại nhân tử Lagrange được nghiên cứu bao gồm các vectơ nhân tử Lagrange có thông tin, mạnh và tối thiểu. Các điều kiện chính quy tổng quát về tính tựa chuẩn tắc và tính giả chuẩn tắc của điểm chấp nhận được được đưa vào để đảm bảo sự khác 0 của nhân tử Lagrange ứng với hàm mục tiêu. Việc tiếp cận bằng phương pháp hàm phạt chính xác tỏ ra hiệu quả dưới các điều kiện về tính tựa chuẩn tắc và Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 2 tính giả chuẩn tắc. Luận văn trình bày các kết quả của Bertsekas và Ozdaglar [3] về lí thuyết các nhân tử Lagrange của bài toán tối ưu có các ràng buộc đẳng thức, bất đẳng thức và ràng buộc tập với các điều kiện chính quy tổng quát về tính tựa chuẩn tắc và tính giả chuẩn tắc của nghiệm tối ưu. Luận văn bao gồm phần mở đầu, ba chương, kết luận và danh mục các tài liệu tham khảo. Chương 1 trình bày điều kiện cần kiểu Fritz John với các nhân tử Lagrange có thêm tính chất (CV). Ba loại vectơ nhân tử Lagrange được nghiên cứu bao gồm các vectơ nhân tử Lagrange có thông tin, mạnh và tối thiểu. Mối quan hệ giữa các loại vectơ nhân tử Lagrange này được trình bày cho trường hợp nón tiếp tuyến lồi. Chương 2 trình bày các điều kiện chính quy tổng quát đảm bảo nhân tử Lagrange ứng với hàm mục tiêu khác 0. Đó là các điều kiện chính quy về tính tựa chuẩn tắc và tính giả chuẩn tắc của nghiệm. Chú ý rằng điều kiện giả chuẩn tắc mạnh hơn điều kiện tựa chuẩn tắc. Một trong các điều kiện chính quy (CQ1) -(CQ6) đúng thì điều kiện giả chuẩn tắc đúng. Chương 3 trình bày cách tiếp cận bằng phương pháp hàm phạt chính xác. Kết quả chỉ ra rằng điều kiện giả chuẩn tắc kéo theo sự thừa nhận một hàm phạt chính xác. Trong trường hợp nón pháp tuyến lồi thì điều kiện tựa chuẩn tắc cũng kéo theo sự thừa nhận một hàm phạt chính xác. Nếu tập ràng buộc là chính quy thì việc thừa nhận một hàm phạt chính xác kéo theo sự thừa nhận các nhân tử Lagrange. Nhân dịp này tôi xin bày tỏ lòng biết ơn sâu sắc tới thầy giáo PGS.TS Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 3 Đỗ Văn Lưu, người đã tận tình hướng dẫn, giúp đỡ tôi hoàn thành bản luận văn này. Tôi xin chân thành cảm ơn Ban chủ nhiệm khoa toá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 cùng các 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 và các thành viên trong lớp cao học toán K3 đã luôn quan tâm, động viên, giúp đỡ tôi trong suốt thời gian học tập và quá trình làm luận văn. Thái Nguyên, tháng 5 năm 2011 Dương thị Yến Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 4 Chương 1 ĐIỀU KIỆN CẦN FRITZ JOHN Chương 1 trình bày điều kiện cần Fritz John với các nhân tử Lagrange có thêm tính chất (CV). Các vectơ nhân tử Lagrange có thông tin, mạnh và tối thiểu được trình bày cùng với mối quan hệ của chúng. Các kết quả trong chương này là của Bertsekas-Ozdaglar [3]. 1.1 KẾT QUẢ BỔ TRỢ Xét bài toán tối ưu có dạng M inf (x), (1.1) x∈C trong đó, tập ràng buộc C bao gồm các ràng buộc đẳng thức, ràng buộc bất đẳng thức và ràng buộc tập trừu tượng. C = X ∩ {x|h1 (x) = 0, . . . , hm (x) = 0} ∩ {x|g1 (x) ≤ 0, . . . , gr (x) ≤ 0} (1.2) Giả sử f, hi , gj là các hàm trơn (khả vi liên tục) từ Rn vào R; X là tập đóng, khác rỗng trong Rn . Tất cả các vectơ được xem như các vectơ cột, dấu " ’ " kí hiệu phép chuyển vị, x0 y là kí hiệu tích vô hướng của hai vectơ Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 5 x và y. Ta dùng chuẩn Euclide 1 ||x|| = (x0 x) 2 . Nhắc lại: Vectơ y là tiếp tuyến của tập S ⊂ Rn tại x ∈ S nếu y = 0 hoặc tồn tại một dãy con {xk } ⊂ S sao cho xk 6= x với mọi k và xk → x, y (xk − x) → . ||xk − x|| ||y|| Một cách tương đương là: Tồn tại dãy con {xk } ⊂ S, với xk → x và dãy xk − x k k số dương {α } sao cho α → 0 và → y. αk Tập hợp tất cả các tiếp tuyến của S tại x được kí hiệu là TS (x) và được gọi là nón tiếp tuyến của S tại x. Nón cực của nón T được xác định bởi T ∗ = {z|z 0 y ≤ 0, y ∈ T }. Với nón T 6= ∅, ta luôn có T ⊂ (T ∗ )∗ . Dấu "=" xảy ra nếu T là tập lồi đóng. Với tập X đóng và điểm x ∈ X, ta kí hiệu nón pháp tuyến của X tại x là NX (x), NX (x) nhận được từ TX (x)∗ qua một phép lấy bao đóng: z ∈ NX (x) nếu tồn tại dãy con {xk } ⊂ X và {z k } sao cho xk → x, z k → z và z k ∈ TX (xk )∗ với mọi k. Một cách tương đương, đồ thị của NX (.), mà ta xem như một ánh xạ đa trị {(x, z)|z ∈ NX (x)}, là bao đóng của đồ thị của TX (.)∗ . Nói chung, ta có TX (x)∗ ⊂ NX (x), với bất kỳ x ∈ X. Tuy nhiên, NX (x) có thể không bằng TX (x)∗ , và có thể không lồi. Khi TX (x)∗ = NX (x), ta nói X là chính quy tại x. Hai tính chất quan trọng của tính chính quy là (xem [10]): (i) Nếu X là lồi thì chính quy tại mỗi x ∈ X; Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 6 (ii) Nếu X là chính quy tại x nào đó ∈ X thì TX (x) là lồi. Một điều kiện cần cổ điển để vectơ x∗ ∈ C là cực tiểu địa phương của f trên C là: 5f (x∗ )0 y ≥ 0, ∀y ∈ TC (x∗ ), (1.3) trong đó TC (x∗ ) là nón tiếp tuyến của C tại x∗ . Trong trường hợp C được biểu diễn bởi các ràng buộc đẳng thức và bất đẳng thức ta nhận được các nhân tử Lagrange. Ta nói rằng tập ràng buộc C (1.2) nhận các nhân tử Lagrange tại điểm x∗ ∈ C nếu với mọi hàm mục tiêu trơn f mà x∗ là cực tiểu địa phương của bài toán (1.1), tồn tại các vectơ λ∗ = (λ∗1 , . . . , λ∗m ) và µ∗ = (µ∗1 , . . . , µ∗r ) thỏa mãn các điều kiện sau: ∗ [∇f (x ) + m X i=1 λ∗i ∇hi (x∗ ) + r X µ∗j ∇gj (x∗ )]0 y ≥ 0, ∀y ∈ TX (x∗ ), (1.4) j=1 µ∗j ≥ 0, µ∗j = 0, ∀j = 1, . . . , r. (1.5) ∀j ∈ / A(x∗ ), (1.6) trong đó A(x∗ ) = {j|gj (x∗ ) = 0} là tập các chỉ số ràng buộc bất đẳng thức tích cực tại x∗ . Điều kiện (1.6) gọi là điều kiện bù (gọi tắt là (CS)). Cặp (λ∗ , µ∗ ) thoả mãn (1.4) - (1.6) gọi là vectơ nhân tử Lagrange tương ứng với f và x∗ . Tập hợp các vectơ nhân tử Lagrange tương ứng với f và x∗ là tập đóng và lồi (có thể là tập rỗng). Điều kiện (1.4) tương thích với tính chất đặc trưng cổ điển của nhân tử Lagrange: biểu hiện ở tính dừng của hàm Lagrange Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 7 tại x∗ . Khi X là tập lồi, (1.4) tương đương với ∗ [∇f (x ) + m X λ∗i ∇hi (x∗ ) + r X i=1 µ∗j ∇gj (x∗ )]0 (x − x∗ ) ≥ 0, ∀x ∈ X. (1.7) j=1 Bởi vì khi X là lồi, TX (x∗ ) là bao đóng của tập các phương chấp nhận được FX (x∗ ), các vectơ đó có dạng α(x − x∗ ) với α > 0 và x ∈ X. Nếu X = Rn thì (1.7) có dạng ∗ [5f (x ) + m X λ∗i ∗ 5 hi (x ) + i=1 r X µ∗j 5 gj (x∗ )] = 0, j=1 với điều kiện (1.5) và (1.6). Khi X = Rn , với hàm trơn f mà x∗ là cực tiểu địa phương của nó, tồn tại nhân tử Lagrange khi và chỉ khi 5f (x∗ )0 y ≥ 0, ∀y ∈ V (x∗ ), trong đó V (x∗ ) là nón các biến phân chấp nhận được cấp một tại x∗ , được cho bởi V (x∗ ) = {y| 5 hi (x∗ )0 y = 0, i = 1, . . . , m, 5gj (x∗ )0 y ≤ 0, j ∈ A(x∗ )}. Từ đó suy ra tập ràng buộc thừa nhận nhân tử Lagrange tại x∗ nếu TC (x∗ ) = V (x∗ ). Trong trường hợp này ta nói rằng x∗ là tựa chính quy hay tính tựa chính quy đúng tại x∗ . Bởi vì tính tựa chính quy là trừu tượng, cho nên ta cho các điều kiện thừa nhận các nhân tử Lagrange dễ kiểm chứng hơn. Các điều kiện như vậy được gọi là các điều kiện chính quy. Một số điều kiện chính quy thường dùng: (CQ1) X = Rn và x∗ là điểm chính quy theo nghĩa là gradients của ràng buộc bất đẳng thức 5hi (x∗ ), i = 1, . . . , m và gradients của ràng buộc bất đẳng thức tích cực 5gj (x∗ ), j ∈ A(x∗ ), là độc lập tuyến tính. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 8 (CQ2) X = Rn , các gradients của ràng buộc đẳng thức 5hi (x∗ ), i = 1, . . . , m là độc lập tuyến tính, và tồn tại y ∈ Rn sao cho 5hi (x∗ )0 y = 0, 5gj (x∗ )0 y ≤ 0, i = 1, . . . , m, ∀j ∈ A(x∗ ). Đây là điều kiện chính quy Mangasarian-Fromovitz. (CQ3) X = Rn , hàm hi là tuyến tính và gj là lõm. Tất cả điều kiện chính quy ở trên đều kéo theo điều kiện tựa chính quy TC (x∗ ) = V (x∗ ) và do đó kéo theo: tập ràng buộc thừa nhận các nhân tử Lagrange (xem [4]). Đó là cách tiếp cận cổ điển cho trường hợp X = Rn . Tuy nhiên, có cách tiếp cận khác để nhận được các nhân tử Lagrange dựa vào hàm phạt chính xác. Cụ thể, ta nói rằng tập ràng buộc C thừa nhận hàm phạt chính xác tại điểm chấp nhận được x∗ nếu với mọi hàm trơn f mà x∗ là cực tiểu địa phương chặt của f trên C, tồn tại số c > 0 sao cho x∗ cũng là cực tiểu địa phương của hàm FC (x) trên X, trong đó m r X X FC (x) = f (x) + c[ |hi (x)| + gj+ (x)], i=1 j=1 với gj+ (x) = max{0, gj (x)}. Lưu ý, việc thừa nhận nhân tử Lagrange, thừa nhận hàm phạt chính xác là tính chất của tập ràng buộc C không phụ thuộc vào hàm mục tiêu f của bài toán (1.1). Không mất tính chất tổng quát ta có thể giả sử x∗ là cực tiểu địa phương chặt bởi vì khi thay hàm mục tiêu f (x) bằng hàm f (x) + ||x − x∗ ||2 không làm ảnh hưởng đến nhân tử Lagrange của bài toán. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 9 Hai điểm quan trọng minh họa ý nghĩa của hàm phạt chính xác như là phương tiện thống nhất đảm bảo việc thừa nhận các nhân tử Lagrange là a) Nếu X là lồi và tập ràng buộc thừa nhận hàm phạt chính xác tại x∗ thì nó cũng thừa nhận các nhân tử Lagrange tại x∗ (xem [5]). b) Tất cả các điều kiện chính quy (CQ1) - (CQ3) ở trên kéo theo C thừa nhận hàm phạt chính xác ( xem [9], [11], [2]). Hình 1.1 tóm tắt mối quan hệ trên cho trường hợp X = Rn . Hai khái niệm tựa chính quy và thừa nhận hàm phạt chính xác có vẻ như không liên quan trực tiếp với nhau, nhưng thực ra chúng liên quan với nhau qua khái niệm tính giả chuẩn tắc của ràng buộc và tính tựa chuẩn tắc của ràng buộc. Khi X là tập con thực sự của Rn , Guignard [7] chỉ ra rằng tập ràng buộc thừa nhận nhân tử Lagrange tại x∗ nêú V (x∗ ) ∩ conv(TX (x∗ )) = conv(TC (x∗ )), (1.8) và nếu tổng vectơ V (x∗ )∗ + TX (x∗ )∗ là một tập đóng, trong đó conv(S) là bao đóng của bao lồi của tập S. Điều kiện Guignard tương đương với V (x∗ )∗ + TX (x∗ )∗ = TC (x∗ )∗ . Đặc biệt, khi X = Rn ta có TX (x∗ ) = Rn , TX (x∗ )∗ = {0}, và điều kiện (1.8) trở thành V (x∗ ) = conv(TC (x∗ )) [hoặc V (x∗ )∗ = TC (x∗ )∗ ]. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 10 Hình 1.1: Các đặc trưng của tập ràng buộc C kéo theo sự thừa nhận các nhân tử Lagrange trong trường hợp X = Rn 1.2 ĐIỀU KIỆN CẦN FRITZ JOHN Các điều kiện cần tối ưu Fritz John thường là điểm xuất phát trong việc phân tích các nhân tử Lagrange. Nhưng những điều kiện này không đủ để suy ra sự thừa nhận các nhân tử Lagrange dưới một điều kiện chính quy nào đó, chẳng hạn khi X = Rn và hàm ràng buộc hi và gj là tuyến tính. Định lí dưới đây xét trường hợp tập X không lồi. Định lí 1.1 Giả sử x∗ là cực tiểu địa phương của bài toán (1.1)-(1.2). Khi đó, tồn tại các số µ∗0 , λ∗1 , . . . , λ∗m và µ∗1 , . . . , µ∗r thoả mãn các điều kiện sau: m r P P ∗ ∗ ∗ ∗ (i) −[µ0 ∇f (x ) + λi ∇hi (x ) + µ∗j ∇gj (x∗ )] ∈ NX (x∗ ), i=1 (ii) µ∗j j=1 ≥ 0 với mọi j = 0, 1, . . . , r, (iii) µ∗0 , λ∗1 , . . . , λ∗m , µ∗1 , . . . , µ∗r không đồng thời bằng 0, Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 11 (iv) Nếu tập chỉ số I ∪ J 6= ∅ trong đó I = {i|λ∗i 6= 0}, J = {j 6= 0|µ∗j > 0}, thì tồn tại dãy {xk } ⊂ X hội tụ tới x∗ sao cho với mọi k, f (xk ) < f (x∗ ), λ∗i hi (xk ) > 0, ∀i ∈ I, µ∗j gj (xk ) > 0, ∀j ∈ J, (1.9) |hi (xk )| = o(w(xk )), ∀i 6∈ I, gj+ (xk ) = o(w(xk )), ∀j 6∈ J, (1.10) trong đó w(xk ) = min{min|hi (x)|, mingj+ (x)}. i∈I j∈J (1.11) Chứng minh Dùng hàm phạt bậc hai: Với mỗi k = 1, 2, . . . xét bài toán sau: m m kX + 1 kX 2 (hi (x)) + (gj (x))2 + ||x − x∗ ||2 , min F (x) ≡ f (x) + 2 i=1 2 j=1 2 k x ∈ X ∩ S, trong đó S = {x|||x − x∗ || ≤ ε}, và số ε > 0 sao cho f (x∗ ) ≤ f (x) với mọi x chấp nhận được và x ∈ S. Vì X ∩S là compact, theo định lí Weierstrass, ta có thể chọn một nghiệm tối ưu xk của bài toán trên. Với mọi k, ta có m r kX kX + k 2 1 k f (x ) + (hi (xk ))2 + (gj (x )) + ||x − x∗ ||2 2 i=1 2 j=1 2 k = F k (xk ) ≤ F k (x∗ ) = f (x∗ ), (1.12) và do f (xk ) bị chặn trên X ∩ S, ta nhận được lim |hi (xk )| = 0, i = 1, . . . , m, lim |gj+ (xk )| = 0, j = 1, . . . , r, k→∞ k→∞ Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 12 bởi vì nếu không, vế trái của (1.12) không bị chặn trên khi k → ∞. Vì thế, mọi điểm giới hạn x của {xk } là chấp nhận được, tức là x ∈ C. Hơn nữa, từ (1.12) ta có 1 f (xk ) + ||xk − x∗ ||2 ≤ f (x∗ ), 2 ∀k. Lấy giới hạn khi k → ∞ ta nhận được 1 f (x) + ||x − x∗ ||2 ≤ f (x∗ ). 2 Bởi vì x ∈ S và x chấp nhận được ta có f (x∗ ) ≤ f (x). Kết hợp với bất đẳng thức trên ta có ||x − x∗ || = 0 nên x = x∗ . Như vậy, dãy {xk } hội tụ tới x∗ và do đó xk là điểm trong của hình cầu đóng S với mọi k lớn hơn k. Với k ≥ k, theo điều kiện cần (1.3) ta có ∇F k (xk )0 y ≥ 0, ∀y ∈ TX (xk ). Một cách tương đương, −∇F k (xk ) ∈ TX (xk )∗ . Từ đó ta có k −[∇f (x ) + m X ξik ∇hi (xk ) + i=1 r X ζjk ∇gj (xk ) + (xk − x∗ )] ∈ TX (xk )∗ , (1.13) j=1 trong đó ξik = khi (xk ), ζjk = kgj+ (xk ). (1.14) Kí hiệu v u m r X X u k (ξik )2 + (ζjk )2 , σ = t1 + i=1 µk0 1 = k, σ λki ξik = k, σ i = 1, . . . , m, Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên (1.15) j=1 µkj ζjk = k, σ j = 1, . . . , r. http://www.lrc-tnu.edu.vn (1.16) 13 Chia (1.13) cho σ k ta được −[µk0 ∇f (xk ) + m X λki ∇hi (xk ) + i=1 r X µkj ∇gj (xk ) + j=1 1 k (x − x∗ )] ∈ TX (xk )∗ . k σ (1.17) Ta có (µk0 )2 + m X (λki )2 i=1 + r X (µkj )2 = 1, (1.18) j=1 dãy con {µk0 , λk1 , . . . , λkm , µk1 , . . . , µkr } là bị chặn và chứa một dãy con hội tụ tới {µ∗0 , λ∗1 , . . . , λ∗m , µ∗1 , . . . , µ∗r }. Từ (1.17) và tính chất của nón pháp tuyến NX (x∗ )[xk → x∗ , {xk } ⊂ X, z k → z ∗ và z k ∈ TX (xk )∗ (với mọi k) thì z ∗ ∈ NX (x∗ )], ta có µ∗0 , λ∗i , µ∗j phải thoả mãn điều kiện (i). Từ (1.14) và (1.16) ta suy ra µ∗0 , µ∗j thoả mãn (ii). Từ (1.18) ta thấy µ∗0 , λ∗i , µ∗j phải thoả mãn (iii). Cuối cùng, ta chỉ ra điều kiện (iv) thoả mãn: Giả sử I ∪ J 6= ∅. Chú ý rằng với mọi k đủ lớn trong tập chỉ số K của dãy con hội tụ, ta có λ∗i λki > 0 với mọi i ∈ I và µ∗j µkj > 0 với mọi j ∈ J. Vì thế, với mỗi k như vậy từ (1.14) và (1.16) ta có λ∗i hi (xk ) > 0 với mọi i ∈ I, và µ∗j gj (xk ) > 0 với mọi j ∈ J. Từ (1.12) ta có f (xk ) < f (x∗ ), với k đủ lớn. Hơn nữa, các điều kiện |hi (xk )| = o(ω(xk )), ∀i ∈ / I, gj+ (xk ) = o(ω(xk )), ∀j ∈ /J tương ứng với |λki | = o(min{min|λki |, minµkj }), i∈I Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên j∈J ∀i 6∈ I, http://www.lrc-tnu.edu.vn 14 và µkj = o(min{min|λki |, minµkj }), i∈I j∈J ∀j 6∈ J. Vì vậy điều kiện này đúng với mọi k ∈ K. Vậy điều kiện (iv) được chứng  minh. Nhận xét 1.1 Nếu X chính quy tại x∗ , tức là NX (x∗ ) = TX (x∗ )∗ , thì điều kiện (i) của Định lí 1.1 có dạng −[µ∗0 ∇f (x∗ ) + m X λ∗i ∇hi (x∗ ) i=1 + r X µ∗j ∇gj (x∗ )] ∈ TX (x∗ )∗ , j=1 hoặc [µ∗0 ∇f (x∗ ) + m X λ∗i ∇hi (x∗ ) + i=1 r X µ∗j ∇gj (x∗ )]0 y ≥ 0, ∀y ∈ TX (x∗ ). j=1 Hơn nữa, nếu µ∗o > 0 thì bằng cách chuẩn hoá ta có thể chọn µ∗o = 1, và khi đó điều kiện (i) của Định lí 1.1 tương đương với điều kiện (1.4). Vậy nếu X chính quy tại x∗ và µ∗o = 1 thì vectơ (λ∗ , µ∗ ) = {λ∗1 , . . . , λ∗m , µ∗1 , . . . , µ∗r } là vectơ nhân tử Lagrange, thoả mãn điều kiện (iv) của Định lí 1.1. Ta thấy điều kiện này mạnh hơn điều kiện (CS)(1.6). Ta gọi điều kiện (iv) là điều kiện (CV). Để minh họa cách sử dụng các điều kiện Fritz John tổng quát của Định lí 1.1 và điều kiện (CV), ta xét ví dụ sau Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 15 Ví dụ 1.1 Giả sử ta chuyển bài toán với ràng buộc đẳng thức min f (x), h(x)=0 thành bài toán với ràng buộc bất đẳng thức:    min f (x),     h(x) ≤ 0,      −h(x) ≤ 0. Điều kiện Fritz John khẳng định tồn tại các nhân tử không âm µ∗0 , λ+ , λ− không đồng thời bằng 0 sao cho µ∗0 ∇f (x∗ ) + λ+ ∇h(x∗ ) − λ− ∇h(x∗ ) = 0. (1.19) Điều kiện (CS) có dạng: λ+ h(x∗ ) = λ− h(x∗ ) = 0 µ∗0 = 0 và λ+ = λ− > 0. Tuy nhiên, các nhân tử này không thoả mãn điều kiện (CV) của Định lí 1.1. Nếu µ∗0 = 0 thì λ+ 6= 0 và λ− = 0 hoặc λ+ = 0 và λ− 6= 0. Giả sử ∇h(x∗ ) 6= 0, (1.19) sẽ không đúng. Vì vậy, µ∗0 > 0. Chia (1.19) cho µ∗0 ta nhận được ∇f (x∗ ) + λ∗ ∇h(x∗ ) = 0, với λ∗ = λ+ − λ− , µ∗0 với giả thiết ∇h(x∗ ) 6= 0. Nếu ta có thể lấy µ∗0 = 1 trong Định lí 1.1 cho các hàm trơn mà x∗ là cực tiểu địa phương, và X là chính quy tại x∗ thì tập ràng buộc C thừa Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 16 nhận các nhân tử Lagrange thoả mãn điều kiện (CV) mạnh hơn thay thế cho điều kiện (CS).Vectơ nhân tử Lagrange(λ∗ , µ∗ ) thỏa mãn (1.4) - (1.6) và điều kiện (CV) (Điều kiện (iv) của Định lí 1.1) được gọi là vectơ nhân tử Lagrange có thông tin. Vectơ nhân tử Lagrange được gọi là mạnh nếu thỏa mãn (1.4) - (1.6) và điều kiện sau (iv’) Nếu tập I ∪ J 6= ∅, trong đó I = {i|λ∗i 6= 0} và J = {j 6= 0|µ∗i > 0}, thì với mọi lân cận B của x∗ , tồn tại dãy {xk } ⊂ X hội tụ tới x∗ sao cho với mọi k, f (xk ) < f (x∗ ), λ∗i hi (xk ) > 0, ∀i ∈ I, gj (xk ) > 0, ∀j ∈ J. (1.20) Điều kiện này tương tự điều kiện (CV) nhưng yếu hơn. Các nhân tử Lagrange có thông tin là nhân tử Lagrange mạnh. Chiều ngược lại không đúng. Ta quan tâm đến việc loại bỏ các ràng buộc mà nhân tử Lagrange bằng 0, và các vectơ nhân tử Lagrange mà có số thành phần khác 0 tối thiểu (giá tối thiểu).Các vectơ nhân tử Lagrange đó được gọi là tối thiểu. Nó có giá I ∪ J không bao hàm thực sự trong giá của bất kì vectơ nhân tử Lagrange nào khác. Các nhân tử Lagrange tối thiểu không nhất thiết là nhân tử Lagrange thông tin. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 17 Hình 1.2: Mối quan hệ giữa các dạng khác nhau của nhân tử Lagrange khi giả thiết TX (x∗ ) lồi (chẳng hạn khi X chính quy tại x∗ ) 1.3 NHÂN TỬ LAGRANGE CÓ THÔNG TIN VÀ NHÂN TỬ LAGRANGE MẠNH Định lí sau chỉ ra mối quan hệ giữa các dạng khác nhau của nhân tử Lagrange (xem hình 1.2). Định lí 1.2 Giả sử x∗ là cực tiểu địa phương của bài toán (1.1)-(1.2). Giả sử nón tiếp tuyến TX (x∗ ) là lồi và tập các nhân tử Lagrange là khác rỗng. Khi đó, (a) Tập hợp các vectơ nhân tử Lagrange có thông tin là khác rỗng và vectơ nhân tử Lagrange có chuẩn nhỏ nhất là có thông tin. (b) Mọi vectơ nhân tử Lagrange tối thiểu là mạnh. Chứng minh (a) Ta tóm tắt bản chất của việc chứng minh trong bổ đề sau Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn