Tài liệu điều kiện tối ưu cho bài toán qui hoạch nửa vô hạn suy rộng

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC SƯ PHẠM ——————–o0o——————– HOÀNG TRI THỨC ĐIỀU KIỆN TỐI ƯU CHO BÀI TOÁN QUY HOẠCH NỬA VÔ HẠN SUY RỘNG LUẬN VĂN THẠC SĨ TOÁN HỌC Thái Nguyên, 4/2019 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC SƯ PHẠM ——————–o0o——————– HOÀNG TRI THỨC ĐIỀU KIỆN TỐI ƯU CHO BÀI TOÁN QUY HOẠCH NỬA VÔ HẠN SUY RỘNG LUẬN VĂN THẠC SĨ TOÁN HỌC Ngành: Toán giải tích Mã số: 8 46 01 02 NGƯỜI HƯỚNG DẪN KHOA HỌC PGS.TS. ĐỖ VĂN LƯU Thái Nguyên, 4/2019 i LỜI CAM ĐOAN Tôi xin cam đoan công trình trên là do tôi nghiên cứu dưới sự hướng dẫn của PGS. TS. Đỗ Văn Lưu. Các kết quả nêu trong luận văn nay là trung thực và chưa từng được công bố trong bất kỳ công trình khoa học nào khác. Ngoài ra, trong luận văn tôi còn sử dụng một số kết quả, nhận xét của các tác giả khác đều có trích dẫn và chú thích nguồn gốc. Nếu phát hiện bất kỳ sự gian lận nào tôi xin hoàn toàn chịu trách nhiệm về nội dung luận văn của mình. Thái Nguyên, ngày 08 tháng 4 năm 2019 Tác giả Hoàng Tri Thức XÁC NHẬN KHOA CHUYÊN MÔN XÁC NHẬN NGƯỜI HƯỚNG DẪN PGS.TS Đỗ Văn Lưu ii LỜI CÁM ƠN Luận văn này được thực hiện tại Trường Đại học sư phạm - Đại học Thái Nguyên và hoàn thành dưới sự hướng dẫn của PGS.TS. Đỗ Văn Lưu. Tác giả xin được bày tỏ lòng biết ơn chân thành và sâu sắc tới thầy hướng dẫn khoa học của mình, người đã đặt vấn đề nghiên cứu, dành nhiều thời gian hướng dẫn và tận tình giải đáp những thắc mắc của tác giả trong suốt quá trình làm luận văn. Tác giả cũng đã học tập được rất nhiều kiến thức chuyên ngành bổ ích cho công tác và nghiên cứu của bản thân. Tác giả xin bày tỏ lòng cảm ơn sâu sắc tới các thầy giáo, cô giáo đã tham gia giảng dạy lớp cao học Toán, nhà trường và các phòng chức năng của trường, khoa Toán, trường Đại học sư phạm - Đại học Thái Nguyên đã quan tâm và giúp đỡ tác giả trong suốt thời gian học tập tại trường. Xin chân thành cảm ơn anh chị em trong lớp cao học và bạn bè đồng nghiệp đã trao đổi, động viên và khích lệ tác giả trong quá trình học tập, nghiên cứu và làm luận văn. Thái Nguyên, ngày 08 tháng 4 năm 2019 Tác giả Hoàng Tri Thức iii Mục lục Lời cam đoan i Lời cám ơn ii Mục lục iii Bảng ký hiệu v Mở đầu 1 1 Điều kiện cần tối ưu cho bài toán quy hoạch nửa vô hạn suy rộng của Ruckmann - Shapiro 3 1.1. Phát biểu bài toán và điều kiện chính quy Mangasarian – Fromovitz. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2. Điều kiện cần tối ưu cấp 1 . . . . . . . . . . . . . . . . . . . . . 6 1.3. Các điều kiện cần cấp 1 dạng bao hàm thức tập hợp . . . . . . 11 1.4. Điều kiện tối ưu dựa trên phép tính hàm tựa khả vi . . . . . . . 14 2 Điều kiện cần và đủ tối ưu cho bài toán quy hoạch nửa vô hạn suy rộng của Stein – Still 16 2.1. Các kiến thức bổ trợ . . . . . . . . . . . . . . . . . . . . . . . . 16 2.2. Điều kiện chính quy Mangasarian-Fromovitz và điều kiện tối ưu 21 iv 2.3. Điều kiện cần tối ưu khi không giả thiết điều kiện chính quy Mangasarian-Fromovitz . . . . . . . . . . . . . . . . . . . . . . . 26 Kết luận 31 Tài liệu tham khảo 32 v Bảng ký hiệu ∇y g(x0 , y 0 ) gradient của g tại (x0 , y 0 ) theo y ∇g(x0 , y 0 ) 0 f+ (x, d) 0 gradient của g tại (x0 , y 0 ) theo (x, y) đạo hàm theo phương Dini trên của f tại x theo phương d f− (x, d) đạo hàm theo phương Dini dưới của f tại x theo phương d D+ f (x, d) đạo hàm theo phương Hadamard trên của f tại x theo phương d D− f (x, d) đạo hàm theo phương Hadamard dưới của f tại x theo phương d σ(d, E) hàm tựa của tập E (M F CQ) Điều kiện chính quy Mangasarian-Fromovitz (EM F CQ) Điều kiện chính quy Mangasarian-Fromovitz mở rộng v(x) hàm giá trị tối ưu (SIP ) bài toán quy hoạch nửa vô hạn (GSIP ) bài toán quy hoạch nửa vô hạn suy rộng 1 Mở đầu Bài toán quy hoạch nửa vô hạn suy rộng là một bài toán tối ưu có vô hạn ràng buộc bất đẳng thức, trong đó tập chỉ số của ràng buộc bất đẳng thức lại phụ thuộc vào tham số. Điều kiện tối ưu cho bài toán quy hoạch nửa vô hạn suy rộng đã và đang được nhiều tác giả quan tâm nghiên cứu. J. J. Ruckmann và A. Shapiro [11] đã dẫn điều kiện cần cấp một cho bài toán này với các hàm khả vi liên tục và tính bị chặn của tập chỉ số. G. Stein và G. Still [12] thiết lập các điều kiện cần tối ưu cho bài toán quy hoạch nửa vô hạn với điều kiện chính quy Mangasarian – Fromovitz qua đạo hàm theo phương Hadamard của hàm giá trị tối ưu. Đây là vấn đề thời sự được nhiều tác giả quan tâm nghiên cứu. Chính vì vậy, chúng tôi chọn đề tài: “Điều kiện tối ưu cho bài toán quy hoạch nửa vô hạn suy rộng”. Luận văn trình bày các điều kiện cần tối ưu cho bài toán quy hoạch nửa vô hạn suy rộng của J. J. Ruckmann và A. Shapiro đăng trong tạp chí J. Optim. Theory Appl., 101 (1999), 677-691, và các điều kiện cần và đủ tối ưu cho bài toán quy hoạch nửa vô hạn với điều kiện chính quy kiểu Mangasarian – Fromovitz của G. Stein và G. Still đăng trong tạp chí J. Optim. Theory Appl., 104 (2000), 443-458. Luận văn bao gồm phần mở đầu, hai chương, kết lận và danh mục các tài liệu tham khảo. Chương 1 với tiêu đề: "Điều kiện cần tối ưu cấp 1 cho bài toán quy hoạch nửa vô hạn suy rộng của Rockmann - Shapiro" trình bày điều kiện cần tối ưu 2 cho bài toán quy hoạch nửa vô hạn suy rộng với các hàm khả vi liên tục bằng cách sử dụng các cận của các đạo hàm theo phương Dini trên và dưới của hàm giá trị tối ưu. Trong trường hợp hàm giá trị tối ưu khả vi theo phương, chúng tôi trình bày điều kiện tối ưu cấp 1dựa trên tuyến tính hóa bài toán đang xét. Phần cuối chương trình bày các điều kiện cần và đủ cấp 1 bằng cách sử dụng phép toán của hàm tựa khả vi. Chương 2 với tiêu đề "Điều kiện cần và đủ tối ưu cho bài toán quy hoạch nửa vô hạn suy rộng của Stein – Still" trình bày các điều kiện tối ưu cấp 1 cho bài toán quy hoạch nửa vô hạn suy rộng với điều kiện chính quy MangasarianFromovitz mở rộng. Các điều kiện tối ưu đó là tổng quát hóa các điều kiện tối ưu cho bài toán quy hoạch nửa vô hạn thông thường. Chương 2 cũng trình bày các điều kiện cần tối ưu cấp 1 cho cực tiểu địa phương chặt cấp 1 khi không giả thiết điều kiện chính quy Mangasarian-Fromovitz cho bài toán cấp dưới. 3 Chương 1 Điều kiện cần tối ưu cho bài toán quy hoạch nửa vô hạn suy rộng của Ruckmann - Shapiro Chương 1 trình bày điều kiện cần tối ưu cấp 1 của J.J. Ruckmann A. Shapiro [11] cho bài toán quy hoạch nửa vô hạn suy rộng với các hàm khả vi liên tục bằng cách sử dụng cận của các đạo hàm theo phương Dini trên và dưới của hàm giá trị tối ưu. Trong trường hợp hàm giá trị tối ưu khả vi theo phương, chúng tôi trình bày điều kiện tối ưu cấp 1 dựa trên tuyến tính hóa của bài toán đang xét. Phần cuối chương trình bày các điều kiện cần và đủ cấp 1 bằng cách sử dụng phép toán của hàm tựa khả vi. 1.1. Phát biểu bài toán và điều kiện chính quy Mangasarian – Fromovitz. Xét bài toán tối ưu sau đây: min f (x), với ràng buộc x ∈ S. trong đó tập chấp nhận được được xác định như sau: S := {x ∈ Rn |g(x, y) ≤ 0, y ∈ Y (x)}, (1.1) 4 với Y (x) := {y ∈ Rk |hi (x, y) = 0, i = 1, ..., p, hj (x, y) ≤ 0, j = p + 1, ..., q}. Với mỗi y∈ Y (x) sẽ có tương ứng một ràng buộc bất đẳng thức của bài toán (1.1). Chúng tôi gọi bài toán như trên là bài toán quy hoạch nửa vô hạn suy rộng, trong đó sự khác nhau của nó với một bài toán quy hoạch nửa vô hạn thông thường là sự phụ thuộc x của tập chỉ số của ràng buộc bất đẳng thức Y(x). Trong những năm gần đây bài toán quy hoạch suy rộng nửa vô hạn đã trở thành một lĩnh vực được nhiều tác giả quan tâm nghiên cứu trong toán ứng dụng. Một số bài toán kỹ thuật được dẫn đến bài toán tối ưu loại này như: bài toán thiết kế, làm nóng hay làm lạnh tối thiểu theo thời gian một hình cầu và bài toán xấp xỉ Chebyshev ngược. Chúng tôi sẽ trình bày các điều kiện cần và điều kiện đủ tối ưu cấp 1 cho bài toán quy hoạch nửa vô hạn suy rộng. Chú ý rằng tập chấp nhận được có thể viết được dưới dạng tương đương sau: S = {x ∈ Rn |v(x) ≤ 0} trong đó, v(x) là hàm giá trị tối ưu: v(x) := sup g(x, y). (1.2) y∈Y (x) Chúng ta sử dụng ký hiệu và các thuật ngữ và các kỹ thuật sau đây trong cả chương này. Ký hiệu ∇y g(x0 , y 0 ) là gradient của g tại (x0 , y 0 ) theo biến y, ∇g(x0 , y 0 ) là gradient của g theo hai biến (x, y) taị (x0 , y 0 ),.... Với hàm giá trị thực f (x), ta ký hiệu f+0 (x, d) := lim sup[f (x + td) − f (x)]/t, f−0 (x, d) t→0+ := lim inf [f (x + td) − f (x)]/t. + t→0 là các đạo hàm theo phương trên và dưới. Hàm f được gọi là khả vi tại x theo phương d, nếu f+0 (x, d) = f−0 (x, d). 5 Với một tập Ξ ⊂ Rn , ta ký hiệu σ(., Ξ) là hàm tựa của Ξ σ(d, Ξ) := sup ξ T d, ξ∈Ξ và ký hiệu conv(Ξ) là bao lồi của Ξ. Bây giờ, ta đưa vào một số giả thiết cơ bản. Giả thiết A1 . f (x), g(x, y), hi (x, y), i = 1, 2..., q là các hàm giá trị thực khả vi liên tục. Bởi vì chúng ta đề cập đến điều kiện tối ưu cấp 1 nên ta tập trung vào tính khả vi cấp 1 của hàm giá trị tối ưu v(x). Đặc biệt, chúng ta sử dụng cận trên 0 0 v+ (x, d) và cận dưới v− (x, d) của hàm giá trị tối ưu. Trong chương này, ta giả sử x0 ∈ S một điểm chấp nhận được. Giả thiết A2 . Các tập Y (x) là bị chặn đều trong một lân cận x0 , tức là tồn tại lân cận N của x0 và tập bị chặn T ⊂ Rk sao cho Y (x) ⊂ T với mọi x ∈ N . Bởi vì hàm hi , i = 1, ..., q liên tục, ánh xạ đa trị x 7→ Y (x) có giá trị đóng. Theo giả thiết (A2 ) hàm giá trị tối ưu v(x) nửa liên tục trên tại x0 . Do đó, nếu v(x0 ) < 0 thì x0 là một điểm trong của S. Trong trường hợp này, nếu x0 là cực điểm địa phương của (1.1) thì điều kiện cần cấp 1 có dạng ∇f (x0 ) = 0. Do đó, ta giả sử v(x0 ) = 0. Bài toán cấp dưới. Theo giả thiết (A1 ) và (A2 ), các tập Y (x) là compact cho x gần x0 . Do đó, supremum vế phải của (1.2) nhận được. Bởi vì v(x0 ) = 0, ta có tập các ràng buộc tích cực Y (x0 ) := {y ∈ Y (x0 )|g(x0 , y) = 0} (1.3) khác rỗng. Rõ ràng, Y (x0 ) là tập các điểm cực đại toàn cục của bài toán cấp dưới sau đây: max g(x0 , y) với ràng buộc y ∈ Y (x0 ), Với bài toán này hàm, ta xét hàm Lagrange: 0 0 L(x , y, α) := g(x , y) − q X i=1 αi hi (x0 , y), (1.4) 6 trong đó α ∈ Rq . Điều kiện chính quy. Ta nói rằng điều kiện chính quy MangasarianFromovitz (MFCQ) là đúng tại y 0 ∈ Y (x0 ) nếu các điều kiện sau thỏa mãn: (i) (ii) Các vectơ ∇y hi (x0 , y 0 ), i = 1, ..., p độc lập tuyến tính; Tồn tại vectơ w ∈ Rk thỏa mãn wT ∇y hi (x0 , y 0 ) = 0 i = 1, ..., p wT ∇y hj (x0 , y 0 ) < 0 j ∈ {ν|hν (x0 , y 0 ) = 0, ν = p + 1, ..., q}. Theo [4], với y 0 ∈ Y0 (x0 ), tập các vectơ nhân tử Lagrange A(x0 , y 0 ) := {α ∈ Rq |∇y L(x0 , y 0 , α) = 0, αj ≥ 0, j = p + 1, ..., q, αj hj (x0 , y 0 ) = 0, j = p + 1, ..., q} khác rỗng và compact nếu điều kiện chính quy (MFCQ) đúng tại y 0 . Mệnh đề 1.1 Giả sử rằng các giả thiết (A1 ), (A2 ) đúng và (MFCQ) thỏa mãn mỗi điểm y ∈ Y0 (x0 ). Khi đó, với mọi d ∈ Rn , các bất đẳng thức sau đúng sup inf0 0 dT ∇x L(x0 , y, α) ≤ v− (x, d), y∈Y0 (x0 ) α∈A(x ,y) 0 v+ (x, d)) ≤ sup sup dT ∇x L(x0 , y, α). y∈Y0 (x0 ) α∈A(x0 ,y) (1.5) (1.6) Cận dưới (1.5) và cận trên (1.6) được dẫn trong [5]. 1.2. Điều kiện cần tối ưu cấp 1 Bằng cách sử dụng cận trên (1.6), định lý sau đây cho ta một điều kiện cần tối ưu Fritz John cấp 1. Định lý 1.1 Giả sử x0 là cực tiểu địa phương của (1.1) và điều kiện chính quy (MFCQ) đúng tại mọi điểm y ∈ Y0 (x0 ). Khi đó, tồn tại y l ∈ Y0 (x0 ), l = 1, ..., m, αl ∈ A(x0 , y l ), l = 1, ..., m, và các nhân tử λl ≥ 0, l = 0, ..., m sao m X cho λl > 0, và l=0 λ0 ∇f (x0 ) + m X l=1 λl ∇x L(x0 , y l , αl ) = 0. (1.7) 7 Chứng minh Bởi vì x0 là cực tiểu địa phương của (1.1) và v(x0 ) = 0, hàm số sau đây ψ(x) := max{f (x) − f (x0 ), v(x)} (1.8) đạt cực tiểu địa phương tại x0 với ψ(x0 ) = 0. Do x0 là cực tiểu địa phương, ta suy ra 0 ψ− (x0 , d) ≥ 0, với mọi d ∈ Rn . Hơn nữa, ta có 0 0 ψ− (x0 , d) = max{dT ∇f (x0 ), v− (x0 , d)}. Do (1.6) điều này kéo theo 0 ψ− (x0 , .) ≤ σ(., Ω), trong đó, σ(., Ω) là hàm tựa của tập Ω := conv({∇f (x0 ), ∇x L(x0 , y, α)|y ∈ Y0 (x0 ), α ∈ A(x0 , y)}). Vì vậy, σ(d, Ω) ≥ 0, với mọi d ∈ Rn . Bởi vì (MFCQ) đúng tại mọi y ∈ Y0 (x0 ), tập A(x0 , y) là compact. Như vậy, Ω cũng compact và vì vậy đóng. Theo Bổ đề Farkas, ta suy ra σ(d, Ω) ≥ 0, với mọi d ∈ Rn nếu và chỉ nếu 0 ∈ Ω. Chú ý rằng 0 ∈ / Ω kéo theo tồn tại d∗ ∈ Rn với ξ T d∗ < 0 với mọi ξ ∈ Ω. Điều này kéo theo (1.7) và chứng minh được hoàn thành.  Nhận xét 1.1 Chứng minh của Định lý 3.1 dựa vào ước lượng trên (1.6). Với mọi y ∈ Y0 (x0 ), nếu vectơ nhân tử Lagrange tương ứng là duy nhất (tức là, A(x0 , y) là tập một điểm), thì các cận dưới và trên trong (1.5) và (1.6) trùng nhau. Vì vậy, hàm giá trị tối ưu v(x) là khả vi theo phương tại x0 . Trong trường hợp này, điều kiện (1.7) là điều kiện cần cấp 1 tốt nhất. Nhận xét 1.2 Nếu A(x0 , y) không là tập một điểm với mỗi y ∈ Y0 (x0 ), thì cận (1.6) có thể cho một ước lượng trên rất khác, hàm giá trị tối ưu v(x) vẫn khả vi theo phương tại x0 , và 8 v 0 (x0 , d) = sup inf0 y∈Y0 (x0 ) α∈A(x ,y) dT ∇x L(x0 , y, α). (1.9) Nói riêng (1.9) đúng trong hai trường hợp này. Nhận xét 1.3 Trường hợp 1 xảy ra khi bài toán cấp dưới (1.4) là lồi (tức là g(x0 , .) lõm, hi (x0 , .), i = 1, ..., p tuyến tính và hj (x0 , .), j = p + 1, ..., q lồi. Vì vậy, Y0 (x0 ) là một tập lồi), và điều kiện Slater đúng (xem [6]). Chú ý rằng trong trường hợp lồi như vậy, tập A(x0 , y) ≡ A(x0 ) không phụ thuộc vào y ∈ Y0 (x0 ) và trùng với tập các nghiệm tối ưu của bài toán đối ngẫu với bài toán cấp dưới. Nhận xét 1.4 Trường hợp 2 xảy ra khi (MFCQ) đúng tại mọi y ∈ Y0 (x0 ) và dạng mạnh của điều kiện đủ cấp 2 thỏa mãn đảm bảo tính ổn định của Lipschitzian. Một câu hỏi hay là liệu với cách chọn bất kỳ các vectơ αl ∈ A(x0 , y l ), ta có thể tìm được các nhân tử λl sao cho các điều kiện tối ưu (1.7) tương ứng đúng hay không? Một phản ví dụ này được cho trong [7] trả lời là không. Dưới những giả thiết thêm về tính compact thì các nhân tử như vậy sẽ tồn tại. Định lý 1.2 Giả sử x0 ∈ S là cực tiểu địa phương của (1.1) và hàm giá trị tối ưu v(x) khả vi theo phương tại x0 và (1.9) đúng. Hơn nữa, với mỗi y ∈ Y0 (x0 ), ta chọn α(y) ∈ A(x0 , y) sao cho tập {∇x L(x0 , y, α(y)), y ∈ Y0 (x0 )} là compact. Khi đó, tồn tại y l ∈ Y0 (x0 ), l = 1, ..., m và các nhân tử λl ≥ 0, l = m X 0, ..., m sao cho λl ≥ 0, và l=0 λ0 ∇f (x0 ) + m X λl ∇x L(x0 , y l , α(y l )) = 0. (1.10) l=1 Chứng minh Do (1.9), với bất kỳ d ∈ Rn , ta nhận được 0 ≤ ψ 0 (x0 , d) = max{dT ∇f (x0 ), sup T ≤ sup{d ∇f (x 0 inf0 dT ∇x L(x0 , y, α)} y∈Y0 (x0 ) α∈A(x ,y) ), dT ∇x L(x0 , y, α(y)), y ∈ Y0 (x0 )}. Bởi vì, tập {∇x L(x0 , y, α(y)), y ∈ Y0 (x0 )} là compact, nên bao lồi của nó cũng compact, và vì vậy tập đó đóng. Một lý luận tương tự như trong chứng 9 minh Định lý 1.1 ta suy ra (1.10).  Ví dụ sau đây minh họa rằng trong Mệnh đề 1.2, giả thiết về tính compact của tập {∇x L(x0 , y, α(y)), y ∈ Y0 (x0 )} không thể bỏ được, mặc dù điều kiện (MFCQ) đúng tại mọi y ∈ Y (x0 ). Nguyên nhân là tập {∇x L(x0 , y, α(y)), y ∈ Y0 (x0 )} bị chặn nhưng không đóng. Ví dụ 1.1 Xét bài toán nửa vô hạn suy rộng sau: min f (x1 , x2 ) = −x1 , với ràng buộc x ∈ S, S := {x ∈ R2 |y2 ≤ 0, y ∈ Y (x)}, Y (x) := {y ∈ R2 |h1 (x, y) = y2 − x1 − x2 y1 ≤ 0, h2 (x, y) = y2 − y12 − x2 ≤ 0, h3 (x, y) = y1 ≤ 2, h4 (x, y) = −y1 ≤ 2, h5 (x, y) = y2 ≤ 4, h6 (x, y) = −y2 ≤ 4}. Hình 1.1: tập chấp nhận được S (1.11) 10 Ta có ( xem hình 1.1): 1 S = {x ∈ R2 |x2 ≤ −4} ∪ {x ∈ R2 | − 4 < x2 ≤ 0, x2 ≥ x1 } ∪ {x ∈ R2 |x2 ≥ 2 1 0, x2 ≤ − x1 } 2 và x0 = (0, 0) là cực tiểu địa phương của (1.11). Hơn nữa, ta có Y0 (x0 ) = {(y 1 , 0)| − 2 ≤ y1 ≤ 2}, {(µ, 1 − µ, 0, 0, 0, 0), µ ∈ [0, 1]}, với y1 = 0, 0 A(x , (y1 , 0)) = {(1, 0, 0, 0, 0, 0), với y ∈ [−2, 2]\{0}, y ∈ Y (x0 ), 1 0  {(µ, 1 − µ)} với y = (0, 0), α = (µ, 1 − µ, 0, 0, 0, 0), 0 ∇x L(x , y, α) = {(1, y ), với y = (y , 0), y 6= 0, α = (1, 0, 0, 0, 0, 0). 1 1 1 Dễ dàng thấy rằng chỉ với y 1 = (0, 0) và α(y 1 ) = (1, 0, 0, 0, 0, 0), tức là với µ = 1 và α(y 1 ) = (1, 0, 0, 0, 0, 0), y ∈ Y0 (x0 ), tồn tại một tổ hợp như trong (1.10) λ0 ∇f (x0 ) + λ1 ∇x L(x0 , y 1 , α)y 1 )) = λ0 −1 ! ! 1 + λ1 = 0. 0 0 Chú ý rằng (MFCQ) thỏa mãn với mọi y ∈ Y0 (x0 ) và v(.) là khả vi theo phương tại x0 với (1.9) đúng. Rõ ràng nếu tập Y0 (x0 ) của các ràng buộc tích cực là hữu hạn thì giả thiết của Định lý 1.2. Điều này kéo theo kết quả sau đây. Định lý 1.3 Giả sử x0 là cực tiểu địa phương cuả (1.1). Giả sử Y0 (x0 ) = {y 1 , ..., y m } là hữu hạn và v(.) khả vi theo phương và (1.9) đúng. Khi đó, Với bất kỳ cách chọn αl ∈ A(x0 , y l ), l = 1, ..., m, tồn tại các m X nhân tử λl ≥ 0, l = 0, 1, ..., m sao cho λl > 0, và (i) λ0 ∇f (x0 ) + m X l=0 λl ∇x L(x0 , y l , αl )) = 0. (1.12) l=1 (ii) Nếu Y0 (x0 ) = {y0 } là tập một điểm và tồn tại α1 , α2 ∈ A(x0 , y 0 ) 11 sao cho ∇x L(x0 , y 0 , α1 ) và ∇x L(x0 , y 0 , α2 ) là độc lập tuyến tính thì ∇f (x0 ) = 0. Chứng minh Khẳng định (i) được suy ra từ Định lý 1.2. Hơn nữa, nếu Y0 (x0 ) gồm một phần tử thì (1.12) đúng cho cả α1 và α2 . Bởi vì ∇x L(x0 , y 0 , α1 ) và ∇x L(x0 , y 0 , α2 ) độc lập tuyến tính, nên khác 0. Ta có nhân tử tương ứng của ∇f (x0 ) khác 0 trong cả hai trường hợp. Kết luận được suy ra từ (1.12).  Các Định lý 1.2 và 1.3 chỉ ra rằng có thể dẫn một họ các điều kiện cần cấp 1 có dạng (1.10), mỗi điều kiện cần đó với một cách chọn thích hợp các nhân tử của bài toán cấp dưới. 1.3. Các điều kiện cần cấp 1 dạng bao hàm thức tập hợp Mệnh đề 1.2 Giả sử hàm giá trị tối ưu v(.) khả vi theo phương tại x0 và công thức (1.9) đúng. Xét bài toán tuyến tính hóa của (1.1) tại x0 sau đây: min dT ∇f (x0 ) với d ∈ S 1 , (1.13) S 1 := {d ∈ Rn |v 0 (x0 , d) ≤ 0}. Khi đó, với điều kiện chính quy(1.14) dưới đây: {d ∈ Rn |v 0 (x0 , d) ≤ 0, } = cl{d ∈ Rn |v 0 (x0 , d) < 0}, (1.14) trong đó, cl là ký hiệu bao đóng tôpô , điều kiện cần tối ưu cấp 1 cho (1.1) có dạng sau: d0 = 0 là cực tiểu địa phương của (1.13). Chứng minh Chú ý rằng, theo (1.9) ta có S 1 = {d ∈ Rn | inf0 α∈A(x ,y) dT ∇x L(x0 , y, α) ≤ 0, ∀y ∈ Y0 (x0 )}..Một cách tiếp cận khác không đòi hỏi điều kiện chính quy là tuyến tính hóa hàm ψ trong (1.8), nghĩa là, nếu x0 là các cực tiểu địa phương của (1.1) thì ψ 0 (x0 , d) ≤ 0 với mọi d ∈ Rn . Bởi vì, ψ 0 (x0 , d) = max{dT ∇f (x0 ), v 0 (x0 , d)}, điều kiện này tương đương với tính chất: hoặc là giá trị tối ưu của bài toán 12 inf dT ∇f (x0 ) với ràng buộc d ∈ S 2 (1.15) bằng 0, trong đó S 2 := {d ∈ Rn |v 0 (x0 , d) < 0} {d ∈ Rn | 0 2 inf0 α∈A(x ,y) 0 dT ∇x L(x0 , y, α) < 0, ∀y ∈ Y0 (x0 )}, hoặc là S = Ø. Nếu v (x , .) liên tục thì các bài toán (1.13) và (1.15) tương đương nếu điều kiện chính quy (1.14) đúng. Sự khác nhau giữa các bài toán nửa vô hạn thông thường và suy rộng là các tập chấp nhận được S 1 và S 2 của các tuyến tính hóa của bài toán suy rông (1.1) không cần lồi. Để thấy rõ sự khác nhau, ta giả sử tập Y0 (x0 ) = {y 0 } là tập một điểm, còn tập A(x0 , y 0 ) không là tập một điểm. Khi đó S 1 là hợp của các nửa không gian S 1 = ∪α∈A(x0 ,y0 ) {d ∈ Rn |dT ∇x L(x0 , y 0 , α) ≤ 0}. Vì vậy, nếu d0 = 0 là cực tiểu địa phương của (1.13) thì d0 cũng là một cực tiểu địa phương của bài toán sau đây: min dT ∇f (x0 ), với ràng buộc {d ∈ Rn |dT ∇x L(x0 , y 0 , α) ≤ 0}, với mỗi α ∈ A(x0 , y 0 ). Do đó, ∇f (x0 ) và ∇x L(x0 , y 0 , α) phải là độc lập tuyến tính với mỗi α ∈ A(x0 , y 0 ). Ta suy ra hoặc là ∇f (x0 ) = 0 hoặc là ∇x L(x0 , y 0 , α) là nhân tử của ∇f (x0 ) với mỗi α ∈ A(x0 , y 0 ). Đây là cách khác để dẫn phát biểu (ii) của Định lý 1.3. Ví dụ 1.2 Xét tập chấp nhận được S := {x ∈ R2 |y2 ≤ 0, y ∈ Y (x)} của bài toán (1.1) với Y (x) := {y ∈ R2 |h1 (x, y) = y2 + εx1 − x2 ≤ 0, h2 (x, y) = y2 + y12 − x2 ≤ 0, h3 (x, y) = −y2 ≤ 4} và ε ∈ R. Rõ ràng, S là hợp của hai nửa không gian (hình 1.2) và có thể 13 viết như sau: S = {x ∈ R2 | min{x2 , x2 − εx1 } ≤ 0 = {x ∈ R2 |x2 ≤ 0} ∪ {x ∈ R2 |x2 − εx1 ≤ 0}. Với x0 = 0, ta nhận được Y0 (x0 ) = {y 0 }, y 0 = (0, 0), A(x0 , y 0 ) = (µ, 1 − µ, 0), µ ∈ [0, 1]}, ∇x L(x0 , y 0 , (µ, 1 − µ, 0)) = (−µε, 1), Hình 1.2: S là hợp của hai nửa không gian và tập chấp nhận được S 1 = {d ∈ R2 | inf (−µε, 1)d ≤ 0} µ∈[0,1] của bài toán tuyến tính hóa (1.13) tương ứng, trong đó ta có S = S 1 ( sau khi thay thế các tọa độ của d bằng x). Bây giờ, dễ thấy từ Hình 1.2 nếu ε 6= 0 và ∇f (x0 ) 6= 0, thì tồn tại d ∈ S với dT ∇f (0) < 0. Vì vậy x0 = 0 không thể là cực tiểu địa phương của (1.1). Điều này cũng không có gì ngạc nhiên do Mệnh đề 1.2(ii): Nếu ε 6= 0, µ1 , µ2 ∈ [0, 1], và µ1 6= µ2 , thì các vectơ ∇x L(x0 , y 0 , (µ1 , 1 − µ1 , 0)) = (−µ1 ε, 1), ∇x L(x0 , y 0 , (µ2 , 1 − µ2 , 0)) = (−µ2 ε, 1) là độc lập tuyến tính.