Tài liệu điều kiện tối ưu và điều kiện chính quy ràng buộc cho bài toán tối ưu với ràng buộc cân bằng

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ĐỊCH XUÂN LUYẾN ĐIỀU KIỆN TỐI ƯU VÀ ĐIỀU KIỆN CHÍNH QUY RÀNG BUỘC CHO BÀI TOÁN TỐI ƯU VỚI RÀNG BUỘC CÂN BẰNG THÁI NGUYÊN - 2015 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ĐỊCH XUÂN LUYẾN ĐIỀU KIỆN TỐI ƯU VÀ ĐIỀU KIỆN CHÍNH QUY RÀNG BUỘC CHO BÀI TOÁN TỐI ƯU VỚI RÀNG BUỘC CÂN BẰ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 NGƯỜI HƯỚNG DẪN: PGS.TS. ĐỖ VĂN LƯU THÁI NGUYÊN - 2015 iii Mục lục Mở đầu 1 1 Điều kiện cần và đủ tối ưu cho bài toán quy hoạch toán học với ràng buộc cân bằng của J.J. Ye 3 1.1. Điều kiện điểm dừng và điều kiện điểm chính quy . . . . . 3 1.1.1. Điểm dừng và điều kiện chính quy . . . . . . . . . . 4 1.1.2. Điều kiện dừng đối ngẫu . . . . . . . . . . . . . . . 5 1.2. Điều kiện cần và đủ tối ưu . . . . . . . . . . . . . . . . . . 9 2 Điều kiện tối ưu và điều kiện chính quy cho bài toán quy hoạch toán học với ràng buộc cân bằng của C. Kanzow và A. Schwartz 20 2.1. Các khái niệm và định nghĩa . . . . . . . . . . . . . . . . . 20 2.2. Điều kiện Fritz John . . . . . . . . . . . . . . . . . . . . . 22 Kết luận 30 Tài liệu tham khảo 31 1 Mở đầu 1. Lý do chọn đề tài Các bài toán quy hoạch toán học với ràng buộc cân bằng (hay còn gọi là ràng buộc bù) là một lớp bài toán tối ưu khó. Các điều kiện KuhnTucker cho các bài toán này phải được thiết lập với các điều kiện chính quy thích hợp với kiểu ràng buộc này. Nhiều công trình đã nghiên cứu về các điều kiện Fritz John, các điều kiện chính quy và các điều kiện Kuhn-Tucker cho lớp bài toán này. J.J. Ye ([11], 2005) đã thiết lập các điều kiện Fritz John cho bài toán tối ưu khả vi với ràng buộc cân bằng. Các điều kiện chính quy thích hợp được đưa vào [11] để dẫn điều kiện Kuhn-Tucker. C. Kanzow và A. Schwartz ([4], 2010) đã sử dụng cách tiếp cận Fritz John để dẫn các điều kiện tối ưu cần và đủ cho bài toán quy hoạch toán học khả vi với ràng buộc cân bằng. Đây là đề tài đã và đang đượ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ác giả đã chọn đề tài: "Điều kiện tối ưu và điều kiện chính quy ràng buộc cho bài toán tối ưu với ràng buộc cân bằng". 2. Mục đích của đề tài Luận văn trình bày các kết quả nghiên cứu về điều kiện tối ưu và các điều kiện chính quy cho bài toán tối ưu khả vi với ràng buộc cân bằng của Ye [11] và Kanzow - Schwartz [4] đăng trên tạp chí J. Math. Anal. Appl. vol 307 (2005) và SIAM J. Optim. vol 20 (2010). 3. Nội dung của luận vă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 1: Điều kiện cần và đủ tối ưu cho bài toán quy hoạch toán 2 học với ràng buộc cân bằng của J.J. Ye Trình bày các kết quả của J.J. Ye ([11],2005) về các loại điểm dừng thích hợp cho bài toán tối ưu với ràng buộc cân bằng. Chương 1 trình bày định lý về điều kiện M-dừng kiểu Fritz John, định lý về điều kiện M-dừng Kuhn-Tucker cho bài toán quy hoạch toán học khả vi với ràng buộc cân bằng. Điều kiện M-dừng đủ với các giả thiết về tính lồi suy rộng cũng được trình bày trong chương 1. Chương 2: Điều kiện tối ưu và điều kiện chính quy cho bài toán quy hoạch toán học với ràng buộc cân bằng của C. Kanzow và Schwartz Trình bày các kết quả về điều kiện tối ưu và các điều kiện chính quy thích hợp cho bài toán quy hoạch toán học khả vi với ràng buộc cân bằng MPEC của Kanzow - Schwartz ([4],2010). Chương 2 trình bày điều kiện cần Fritz John của Kanzow- Schwartz và các điều kiện chính quy cho MPEC. Điều kiện đủ để MPEC là M-dừng được trình bày với các điều kiện chính quy thích hợp. Nhân dịp này tác giả xin được gửi lời cảm ơn đến tập thể các thầy cô giáo đã truyền đạt những tri thức quý giá trong thời gian tác giả học tập tại trường. Đặc biệt tác giả xin bày tỏ lòng biết ơn sâu sắc đối với thầy giáo PGS.TS. Đỗ Văn Lưu đã hướng dẫn, giúp đỡ tận tình và đầy trách nhiệm để tác giả hoàn thành luận văn này. Cuối cùng tác giả xin được cảm ơn Sở giáo dục - Đào tạo tỉnh Thái Nguyên, trường THPT Yên Ninh, gia đình, bạn bè, đồng nghiệp đã động viên, ủng hộ và tạo mọi điều kiện cho tác giả trong suốt thời gian nghiên cứu và học tập. Thái Nguyên, tháng 11 năm 2015. Học viên Địch Xuân Luyến 3 Chương 1 Điều kiện cần và đủ tối ưu cho bài toán quy hoạch toán học với ràng buộc cân bằng của J.J. Ye Chương 1 trình bày các kết quả của J.J. Ye ([11],2005) về các loại điểm dừng, điều kiện M-dừng Fritz John, điều kiện M-dừng Kuhn-Tucker cho bài toán quy hoạch toán học với ràng buộc cân bằng khả vi. Với các giả thiết về tính suy rộng, điều kiện M- dừng Kuhn-Tucker trở thành điều kiện M-dừng đủ. 1.1. Điều kiện điểm dừng và điều kiện điểm chính quy Xét bài toán với ràng buộc cân bằng (MPEC): (MPEC) min f (z) g(z) ≤ 0, h(z) = 0, G(z) ≥ 0, H(z) = 0, (1.1) G(z)T H(z) = 0, trong đó f : Rn → R, G : Rn → Rm , H : Rn → Rm , g : Rn → Rp , h : Rn → Rq kí hiệu phép chuyển vị. Để nghiên cứu bài toán (MPEC) người ta nghiên cứu dạng không đối xứng của bài toán tối ưu với ràng 4 buộc cân bằng(OPCC): (OPPC) min f (x, y) g(x, y) ≤ 0, h(x, y) = 0, G(x, y) ≥ 0, y ≥ 0, (1.2) G(x, y)T y = 0. Bài toán này là trường hợp đặc biệt quan trọng nhất (trong đó Ω = Rm + ) của bài toán tối ưu với ràng buộc bất đẳng thức biến phân (OPVIC): (OPVIC) min f (x, y) g(x, y) ≤ 0, y ∈ Ω, (1.3) h(x, y) = 0, hG(x, y), y − y 0 i ≤ 0, ∀y 0 ∈ Ω, trong đó f : Rn+m → R, G : Rn+m → Rm , g : Rn+m → Rp , h : Rn+m → Rq và Ω là tập con lồi đóng của Rm . Với một vectơ d ∈ Rn và tập chỉ số I ⊆ {1, 2, ..., n}, di là thành phần thứ i của d và dI là vectơ con gồm các thành phần di với i ∈ I.ha, bi hoặc aT b là tích vô hướng của vectơ a và b. 1.1.1. Điểm dừng và điều kiện chính quy Với vectơ chấp nhận được z ∗ của MPEC, ta định nghĩa các tập sau đây: Ig := {i : gi (z ∗ ) = 0} α := α(z ∗ ) := {i : Gi (z ∗ ) = 0, Hi (z ∗ ) > 0}, β := β(z ∗ ) := {i : Gi (z ∗ ) = 0, Hi (z ∗ ) = 0}, γ := γ(z ∗ ) := {i : Gi (z ∗ ) > 0, Hi (z ∗ ) = 0}. Tập β là một tập suy biến. Nếu β là tập rỗng, thì vectơ z ∗ được gọi là thỏa mãn điều kiện bù chặt. Ở đây ta xét trường hợp β 6= ∅. Ta xác định tập các phân hoạch của β bởi P (β) := {(β1 , β2 ) : β1 ∪ β2 = β, β1 ∩ β2 = ∅}. 5 Mỗi phân hoạch (β1 , β2 ) ∈ P (β) được ghép với bài toán MPEC: (MPEC)(β1 , β2 ) min f (z) g(z) ≤ 0, h(z) = 0, Gi (z) = 0, i ∈ α ∪ β2 , Hi (z) = 0, i ∈ γ ∪ β1 , Gi (z) ≥ 0, i ∈ β1 , Hi (z) ≥ 0, i ∈ β2 . (1.4) Rõ ràng z ∗ là nghiệm tối ưu địa phương của MPEC nếu và chỉ nếu nó là nghiệm tối ưu của M P EC(β1 , β2 ) với mọi phân hoạch (β1 , β2 ) ∈ P (β). Trước hết ta nhắc lại khái niệm nón tiếp tuyến. Định nghĩa 1.1 (Nón tuyến tính) Giả sử Z là tập chấp nhận được của MPEC và z ∗ ∈ Z. Nón tiếp tuyến của Z tại z ∗ là nón đóng được xác định bởi T (z ∗ ) := {d ∈ Rn : ∃tn ↓ 0, dn → d sao cho z ∗ + tn dn ∈ Z, ∀n}. (1.5) Khái niệm sau đây về điều kiện điểm dừng của MPEC được đựa vào trong [8]. Nó khác với điều kiện B-dừng [9] được xác định bởi lin ∗ ∇f (z ∗ )T d ≥ 0, ∀d ∈ TM P EC (z ) (1.6) lin ∗ trong đó TM P EC (z ) là nón tuyến tính hóa MPEC được định nghĩa dưới đây. Định nghĩa 1.2 (Điểm B-dừng) Một điểm chấp nhận được z ∗ của MPEC được gọi là điểm dừng Boligand (B-dừng) nếu ∇f (z ∗ )T d ≥ 0, ∀d ∈ T (z ∗ ). 1.1.2. (1.7) Điều kiện dừng đối ngẫu Không giống với quy hoạch phi tuyến thông thường chỉ có một điều kiện dừng đối ngẫu, tức là điều kiện Karush-Kuhn-Tucker MPEC, có một số khái niệm dừng. Bây giờ ra tóm tắt và trình bày mối liên hệ giữa các khái niệm đó. 6 Định nghĩa 1.3 (Điểm W-dừng). Một điểm chấp nhận được z ∗ của MPEC được gọi là dừng yếu nếu tồn tại λ = (λg , λh , λG , λH ) ∈ Rp+q+2m sao cho điều kiện sau đúng: ∗ 0 = ∇f (z ) + X ∇λgi gi (z ∗ ) − λhi ∇hi (z ∗ ) i=1 i∈Ig m X + q X (1.8) ∗ H ∗ [λG i ∇Gi (z ) + λi ∇Hi (z )], i=1 λgIg ≥ 0, λG γ = 0, λH α = 0. (1.9) Dễ thấy rằng điều kiện W-dừng là điều kiện KKT cho bài toán MPEC chặt sau: (TMPEC) min f (z) g(z) ≤ 0, h(z) = 0, Gi (z) = 0, i ∈ α, Hi (z) = 0, i ∈ γ, Gi (z) = 0, Hi (z) = 0, i ∈ β. Định nghĩa 1.4 (Điểm C-dừng) Điểm chấp nhận được z ∗ của MPEC được gọi là điểm dừng Clarke nếu tồn tại λ = (λg , λh , λG , λH ) ∈ Rp+q+2m sao cho (1.8) - (1.9) và điều kiện sau đúng: ∀i ∈ β, H λG i λi ≥ 0. (1.10) Theo [9. Bổ đề 1] điều kiện C-dừng là điều kiện KKT không trơn khi sử dụng grandient suy rộng Clarke [4] bằng cách phát biểu lại MPEC như một bài toán quy hoạch phi tuyến không trơn: min f (z) g(z) ≤ 0, h(z) = 0, Gi (z) = 0, i ∈ α, Hi (z) = 0, i ∈ γ, (1.11) min{Gi (z), Hi (z)} = 0, i ∈ β. Định nghĩa 1.5 (Điểm A-dừng). Một điểm chấp nhận được z ∗ của MPEC được gọi là điểm dừng luân 7 phiên nếu tồn tại λ = (λg , λh , λG , λH ) ∈ Rp+q+2m sao cho (1.8) - (1.9) và điều kiện sau đúng: ∀i ∈ β, λG i ≥ 0, hoặc λH i ≥ 0. (1.12) Khái niệm điểm A-dừng được đưa vào bởi Flegel và Kanzow. Thực ra điều kiện A-dừng là điều kiện KKT cho M P EC(β1 , β2 ) với một phân hoạch (β1 , β2 ) ∈ P (β). Định nghĩa 1.6 (Điểm M-dừng) Điểm chấp nhận được z∗ của MPEC được gọi là Mordukhovich-dừng nếu tồn tại λ = (λg , λh , λG , λH ) ∈ Rp+q+2m sao cho (1.8) - (1.9) và điều kiện sau đây đúng: ∀i ∈ β, H G H hoặc λG i > 0, λi > 0 hoặc λi λi = 0. (1.13) Định nghĩa 1.7 (Điểm S-dừng). Một điểm chấp nhận được z ∗ của MPEC được gọi là dừng mạnh nếu tồn tại λ = (λg , λh , λG , λH ) ∈ Rp+q+2m sao cho (1.8) - (1.9) và điều kiện sau đúng: ∀i ∈ β, λG i ≥ 0, λH i ≥ 0. Điều kiện S-dừng là điều kiện KKT cho MPEC nới lỏng: (RMPEC) min f (z) g(z) ≤ 0, h(z) = 0, Gi (z) = 0, i ∈ α, Hi (z) = 0, i ∈ γ, Gi (z) ≥ 0, Hi (z) ≥ 0, i ∈ β. (1.14) 8 Biểu đồ sau đây tóm tắt mối quan hệ giữa các khái niệm điểm dừng đối ngẫu trên: Điểm S -dừng ⇓ Điểm M-dừng ⇓ ⇓ Điểm C-dừng Điểm A-dừng ⇓ ⇓ Điểm W-dừng Định nghĩa 1.8 (MPEC LICQ). Giả sử z ∗ là điểm chấp nhận được của MPEC, trong đó tất cả các hàm khả vi liên tục tại z ∗ . Ta nói rằng điều kiện chính quy độc lập tuyến tính MPEC thỏa mãn tại z ∗ nếu các vectơ gradient của các ràng buộc của R MPEC: ∇gi (z ∗ ), ∀i ∈ Ig , ∇hi (z ∗ ), ∀i = 1, 2, 3, . . . , q, ∇Gi (z ∗ ), ∀i ∈ α ∪ β, ∇Hi (z ∗ ), ∀i ∈ γ ∪ β là độc lập tuyến tính. MPEC LICQ là điều kiện rất mạnh. Đó là điều kiện chính quy độc lập tuyến tính cho MPEC nới lỏng. Vì vậy, nó là điều kiện chính quy để điều kiện S-dừng, đúng tại một nghiệm tối ưu địa phương. Định nghĩa 1.9 ( MPEC LICQ bộ phận). Giả sử z ∗ là điểm chấp nhận được của MPEC. Điều kiện chính quy độc lập tuyến tính MPEC bộ phận đúng tại z ∗ nếu với mọi vectơ 9 λ = (λg , λh , λG , λH ) ∈ Rp+q+2m 0= X λgi ∇gi (z ∗ ) + q X λhi ∇hi (z ∗ ) i=1 i∈Ig − m X ∗ [λG i ∇Gi (z ) i=1 ∗ + λH i ∇Hi (z )], H λG γ = 0, λα = 0, kéo theo H λG β = 0, λβ = 0, 1.2. Điều kiện cần và đủ tối ưu Trước hết ta nhắc lại một số kiến thức về nón và dưới vi phân giới hạn của Mordukhovich: Định nghĩa 1.10 (i) Giả sử C ⊆ Rn là tập khác rỗng. Nón cực của C được định nghĩa như sau: C 0 := {s ∈ Rn | sT d ≤ 0, ∀d ∈ C}. (ii) Giả sử C ⊆ Rn là tập đóng khác rỗng. Nón tiếp tuyến Bouligand của C tại x∗ được định nghĩa bởi xk − x∗ → d} tk = {d ∈ Rn | ∃{xk } → d, {tk } ↓ 0 : x∗ + tk dk ∈ C ∀k ∈ N}. TC (x∗ ) := {d ∈ Rn | ∃{xk } →C x∗ , {tk } ↓ 0 : trong đó {xk } →C x∗ kí hiệu dãy {xk } hội tụ đến x∗ và x∗ ∈ C, ∀k ∈ N. (iii) Giả sử C ⊆ Rn là tập đóng khác rỗng và x∗ ∈ C. Nón pháp tuyến Fr’echet của C tại x∗ được định nghĩa bởi NCF (x∗ ) := TC (x∗ )0 . 10 (iv) Giả sử C ⊆ Rn là tập đóng khác rỗng và x∗ ∈ C. Nón pháp tuyến giới hạn C tại x∗ được định nghĩa bởi NC (x∗ ) := {d ∈ Rn | ∃{xk } →C x∗ , dk ∈ NCF (xk ) : dk → d}. Các dưới vi phân sau đây có quan hệ với các nón đã định nghĩa trên. Định nghĩa 1.11 Giả sử f : Rn → R liên tục (i) Dưới vi phân của f tại x∗ được định nghĩa như sau: ∂ F f (x∗ ) := {s ∈ Rn | lim∗ inf x→x f (x) − f (x∗ ) − sT (x − x∗ ) ≥ 0}. kx − x∗ k (ii) Dưới vi phân giới hạn của f tại x∗ được định nghĩa như sau: ∂f (x∗ ) := {s ∈ Rn | ∃{xk } → x∗ , sk ∈ ∂ F f (xK ) : sk → s}. Ta trình bày điều kiện M-dừng, kiểu Fritz John cho MPEC, bằng cách phát biểu lại MPEC dạng OPVIC như sau: (P) min f (z) g(z) ≤ 0, (x, u, w) ∈ Ω, h(H(z), G(z) − x, h(z)), (x, y, w) − (x0 , y 0 , w0 )i ≤ 0, ∀(x0 , y 0 , z) ∈ Ω, m q trong đó Ω = Rm + ×R ×R . Một điều kiện M-dừng kiểu Fritz John có thể phát biểu như sau: Định lý 1.1 (Điều kiện M-dừng kiểu Fritz John). Giả sử z ∗ là nghiệm địa phương của MPEC trong đó tất cả các hàm khả vi liên tục tại z ∗ . Khi đó, tồn tạị r ≥ 0, λ = (λg , λh , λG , λH ) ∈ Rp+q+2m , 11 không đồng thời bằng 0, sao cho ∗ 0 = r∇f (z ) + X λgi ∇gi (z ∗ ) i∈Ig − m X + q X λhi ∇hi (z ∗ ) i=1 ∗ H ∗ [λG i ∇Gi (z ) + λi ∇Hi (z )], (1.15) i=1 H λgIg ≥ 0, λG γ = 0, λα ≥ 0, G H hoặc λgi > 0, λH i > 0, hoặc λi λi = 0, ∀i ∈ β. Chứng minh. Bằng cách đưa vào một biến phụ, ta phát biểu lại MPEC dưới dạng tương đương sau đây: (EMPEC) min f (z) g(z) ≤ 0, h(z) = 0, G(z) − x = 0, H(z) − y = 0, (x, y) ∈ Ω, trong đó Ω := {x, y ∈ R2m : x ≥ 0, y ≥ 0, xT y = 0}. Đây là một bài toán tối ưu với các ràng buộc đẳng thức, bất đẳng thức và một ràng buộc tập không lồi (x, y) ∈ Ω với (x∗ , y ∗ , z ∗ ) = (G(z ∗ ), H(z ∗ ), z ∗ ) là một nghiệm địa phương. Áp dụng quy tắc giới hạn của quy tắc nhân tử Lagrange của Mordukhovich [7, Định lý 1(b)] ta suy ra tồn tại r ≥ 0, λ không đồng thời bằng 0 và (ξ, γ) ∈ NΩ (x∗ , y ∗ ) (Nón pháp tuyến giới hạn của Ω tại (x∗ , y ∗ )), sao cho         0 0 0 0 q     X g  X h  λi  0  + λi  0  0 = r  0  + i=1 i∈Ig 0 ∇f (z ∗ ) ∇gi (z ∗ ) ∇hi (z ∗ )       −ei 0 ξ m m X   X H    G − λi  λi  −ei  + γ  , 0 − i=1 i=1 ∇Gi (z ∗ ) ∇Hi (z ∗ ) 0 λgIg ≥ 0, 12 trong đó ei kí hiệu vectơ đơn vị có thành phần thứ i = 1. Từ đó suy ra 0 = λG + ξ, 0 = λH + γ, p X X g ∗ ∗ 0 = r∇f (z ) + λi ∇gi (z ) + λhi ∇hi (z ∗ ) i=1 − i∈Ig m X ∗ H ∗ [λG i ∇Gi (z ) + λi ∇Hi (z )], i=1 λgIg ≥ 0. Bởi vì (ξ, γ) ∈ NΩ (x∗ , y ∗ ) và NΩ (x∗, y∗) =         nếu x∗i > 0 nếu yi∗ > 0 ξi = 0 (ξ, γ) : γi = 0 hoặc ξi < 0, γi < 0 hoặc ξi γi < 0, nếu x∗ = y ∗ = 0 (xem [10], Mệnh đề 3.7) ta suy ra kết luận của định lí. 2 Do điều kiện M-dừng kiểu Fritz John, nếu r trong điều kiện khác 0, thì có thể lấy bằng 1. Vì vậy, điều kiện M-dừng kiểu KKT được suy ra. Định nghĩa 1.12 (NNAMCQ) Giả sử z ∗ là điểm chấp nhận được của MPEC, trong đó tất cả các hàm khả vi liên tục tại z ∗ . Ta nói rằng điều kiện chính quy NNAMCQ (No Nonzero Abnormal Multiplier Constraint Qualitification) đúng tại z ∗ nếu không tồn tại vectơ khác 0 λ = (λg , λh , λG , λH ) ∈ Rp+q+2m sao cho 0= X i∈Ig λgi ∇gi (z ∗ ) + p X λhi ∇hi (z ∗ ) i=1 − m X ∗ H ∗ [λG i ∇Gi (z ) + λi ∇Hi (z )], i=1 H λgIg ≥ 0, λG γ = 0, λα = 0, H G H hoặc λG i > 0, λi > 0, hoặc λi λi = 0, ∀i ∈ β.   13 Hệ quả 1.1 Giả sử z ∗ là nghiệm địa phương của MPEC, trong đó tất cả các hàm khả vi liên tục tại z ∗ . Giả sử điều kiện NNAMCQ thỏa mãn tại z ∗ . Khi đó, r trong Định lí 1.1 có thể lấy bằng một, tức là z ∗ là M-dừng. Định nghĩa 1.13 (MPEC GMFCQ) Giả sử z ∗ là điểm chấp nhận được của MPEC, trong đó tập tất cả các điểm là khả vi liên tục tại z ∗ . Ta nói rằng điều kiện chính quy Mangasarian -Fromovitz MPEC suy rộng thỏa mãn tại z ∗ nếu (i) Với mọi phân hoạch của β thành P, Q, R với R 6= ∅ tồn tại d sao cho ∇gi (z ∗ )T d ≤ 0, ∀i ∈ Ig , ∇hi (z ∗ )T d = 0, ∀i = 1, 2, . . . , q, ∇Gi (z ∗ )T d = 0, ∀i ∈ α ∪ Q, ∇Hi (z ∗ )T d = 0, ∀i ∈ γ ∪ P, ∇Gi (z ∗ )T d ≥ 0, ∇Hi (z ∗ )T d ≥ 0, i ∈ R, và với i nào đó thuộc R hoặc ∇Gi (z ∗ )T d > 0 hay ∇Hi (z ∗ )T d > 0; (ii) Với mọi phân hoạch β thành P,Q, các vectơ gradient ∇hi (z ∗ ), ∀i = 1, 2, . . . , q, ∇Gi (z ∗ ), ∀i ∈ α ∪ Q, ∇Hi (z ∗ ), ∀i ∈ γ ∪ P, là độc lập tuyến tính và tồn tại d ∈ Rn sao cho : ∇gi (z ∗ )T d < 0, ∀i ∈ Ig , ∇hi (z ∗ )T d = 0, ∀i = 1, 2, . . . , q, ∇Gi (z ∗ )T d = 0, ∀i ∈ α ∪ Q, ∇Hi (z ∗ )T d = 0, ∀i ∈ γ ∪ P, Mệnh đề 1.1 NNAMCQ tương đương với MPEC GMFCQ. 14 Chứng minh. Chú ý rằng β được chia thành các tập: P = {i ∈ β : λG i = 0}, Q = {i ∈ β : λH i = 0}, H R = {i ∈ β : λG i > 0, λi > 0} Vì vậy điều kiện NNAMCQ tương đương với hai điều kiện sau: (1) Với mọi phân hoạch β thành các tập P, Q, R với R 6= ∅ không tồn H tại các vectơ λgIg , λh , λG α∪Q∪R và λγ∪P ∪R thỏa mãn hệ : ∗ T H 0 = ∇g(z ∗ )T λgIg + ∇h(z ∗ )T λh − ∇G(z ∗ )T λG α∪Q∪R − ∇H(z ) λγ∪P ∪R , H λgIg ≥ 0, λG R > 0, λR > 0. (2) Với mọi phân hoạch của β thành các tập P, Q, không tồn tại các H vectơ λgIg , λh , λG α∪Q và λγ∪P thỏa mãn các hệ sau: ∗ T H 0 = ∇g(z ∗ )T λgIg + ∇h(z ∗ )T λh − ∇G(z ∗ )T λG α∪Q − ∇H(z ) λγ∪P , λgIg ≥ 0. Các kết quả này được suy ra bằng cách áp dụng các định lí luân phiên của Tucker và Motzkin (xem [6]) áp dụng đối với (i) và (ii). 2 Trong quy hoạch toán học ta biết rằng nếu tất cả các ràng buộc là affine thì điều kiện tối ưu KKT đúng không cần điều kiện chính quy nào. Định nghĩa 1.14 (Điều kiện chính quy tuyến tính MPEC) Ta nói rằng điều kiện chính quy tuyến tính MPEC thỏa mãn nếu tất cả các ánh xạ g,h,G,H là affine. Kết quả sau đây nhận được bằng cách phát biểu lại MPEC thành (P) và áp dụng các kết quả tương ứng cho OPVIC [(10), Hệ quả 4.8]. Định lý 1.2 (Điều kiện cần M-dừng kiểu KKT) Giả sử z ∗ là nghiệm tối ưu địa phương của MPEC, trong đó tất cả các hàm khả vi liên tục tại z ∗ . Nếu hoặc là MPEC GMCQ, hoặc là điều kiện chính quy tuyến tính MPEC thỏa mãn tại z ∗ thì z ∗ là M-dừng. 15 Chứng minh. Kết luận z ∗ là M-dừng với điều kiện MPEC GMFCQ được suy ra từ Hệ quả 1.1 và Mệnh đề 1.1. Để chứng minh z ∗ là M-dừng với điều kiện chính quy tuyến tính MPEC, ta xét các nghiệm của hệ ràng buộc nhiễu của EMPEC sau đây: X (p, q, r, s) := {(x, y, z) ∈ Ω × Rn :g(z) + p ≤ 0, h(z) + q = 0, G(z) − x + r = 0, H(z) − y + s = 0}. Dễ thấy rằng đồ thị của ánh xạ Σ là hợp của các tập lồi đa diện. Vì vậy, Σ là hàm đa trị đa diện. Theo [(8), Mệnh đề 1], Σ là Lipschitz trên tại điểm (0, 0, 0, 0) ∈ Rp+q+2m , tức là tồn tại lân cận U của (0, 0, 0, 0) và α ≥ 0 sao cho X X (p, q, r, s) ⊂ (0, 0, 0, 0) + α k(p, q, r, s)k clB, ∀(p, q, r, s) ∈ U Trong đó cl B là kí hiệu hình cầu đơn vị đóng. Một cách tương đương, hệ ràng buộc của EMPEC có một cận chặn địa phương tức là X d((x, y, z), (0, 0, 0, 0)) ≤ α k(p, q, r, s)k , X ∀(p, q, r, s) ∈ U, (x, y, z) ∈ (p, q, r, s), trong đó d(a,C) là khoảng cách từ điểm a tới tập C. Theo nguyên lí Clarke về hàm phạt chính xác [(3), Mệnh đề 2.4.3], (x∗ , y ∗ , z ∗ ) cũng là nghiệm tối ưu địa phương của bài toán không có ràng buộc sau: X min f (z) + µf d((x, y, z), (0, 0, 0, 0)), trong đó µf là hằng số Lipschitz của f. Vì vậy, theo tính chất của cận chặn địa phương ta có (z, p, q, r, s) = (z ∗ , 0, 0, 0, 0) là nghiệm tối ưu địa phương của bài toán sau: min f (z) + µf α k(p, q, r, s)k , g(z) + p ≤ 0, h(z) + q = 0, G(z) + r ≥ 0, H(z) + s ≥ 0, (G(z) + r)T (H(z) + s) = 0. Điều kiện NNAMCQ thỏa mãn tại (z ∗ , 0, 0, 0, 0) cho bài toán trên. Chú ý rằng mặc dù hàm mục tiêu có một số hạng không trơn khác 16 k(p, q, r, s)k, sử dụng kỹ thuật như ta đã chứng minh Định lí 1.1 cho gradients giới hạn và đẳng thức (1.15) được thay bởi bao hàm thức. Áp dụng Hệ quả 1.1 cho MPEC, ta nhận được điều kiện M-dừng, bởi vì z là thành phần của (1.15) cho bài toán trên cũng đúng như cho (1.15) MPEC. 2 Trong định lý sau đây, ta chỉ ra điều kiện M-dừng trở thành điều kiện đủ tối ưu hoặc điều kiện đủ tối ưu địa phương với điều kiện lồi suy rộng MPEC thích hợp. Định lý 1.3 (Điều kiện M-dừng đủ) Giả sử z ∗ là điểm chấp nhận được của MPEC và điều kiện M-dừng đúng tại z ∗ , tức là tồn tại λ = (λg , λh , λG , λH ) ∈ Rp+q+2m sao cho ∗ 0 = 5f (z ) + − X λgi ∗ 5 gi (z ) + q X λhi 5 hi (z ∗ ) i=1 i∈Ig m X (1.16) ∗ H ∗ [λG i 5 Gi (z ) + λi 5 Hi (z )], i=1 H λgIg ≥ 0, λG γ = 0, λα = 0, H G H ∀i ∈ β, hoặc là λG i > 0, λi > 0, hoặc là λi λi = 0. Đặt J + := {i : λhi > 0}, J − := {i; λhi < 0}, H λβ + := {i ∈ β : λG i > 0, λi > 0} H λβG+ := {i ∈ β : λG i = 0, λi > 0}, H βG− := {i ∈ β : λG i = 0, λi < 0} + H λβH := {i ∈ β : λG i > 0, λi = 0}, − H βH := {i ∈ β : λG i < 0, λi = 0} α+ := {i ∈ αiG > 0}, α− := {i ∈ α; λG i < 0}, γ + := {i ∈ γiH > 0}, γ − := {i ∈ γ; λH i < 0}, Hơn nữa, giả sử f là giả lồi tại z ∗ , gi (i ∈ Ig ), hi (i ∈ J + ), − + − hi (i ∈ J − ), Gi (i ∈ α− ∪ βH ), −Gi (i ∈ α+ ∪ βH ∪ β + ), Hi (i ∈ γ − ∪ βG− ), − Hi (i ∈ γ + ∪ βG+ ∪ β + ) là tựa lồi. − Khi đó, trong trường hợp α− ∪ γ − ∪ βG− ∪ βH = ∅, z ∗ là nghiệm tối ưu 17 − = ∅ hoặc khi z ∗ là điểm toàn cục của MPEC; trong trường hợp βG− ∪ βH − trong tương đối của tập Z ∩ {z : Gi (z) = 0, Hi (z) = 0, i ∈ βG− ∪ βH }, tức là với mọi điểm chấp nhận được z gần z ∗ , ta có: Gi (z) = 0, − Hi (z) = 0, ∀i ∈ βG− ∪ βH , z ∗ là nghiệm tối ưu địa phương của MPEC, trong đó Z là tập chấp nhận được của MPEC. Chứng minh. Giả sử z là điểm chấp nhận được bất kỳ của MPEC. Khi đó, với bất kỳ i ∈ Ig , gi (z) ≤ 0 = gi (z ∗ ) Do tính tựa lồi của gi tại z ∗ , ta suy ra gi (z ∗ + t(z − z ∗ )) = gi (tz + (1 − t)z ∗ ) ≤ g(z ∗ ) với mọi t ∈ (0, 1). Từ đó suy ra h5gi (z ∗ ), z − z ∗ i ≤ 0, ∀i ∈ Ig . (1.17) h5hi (z ∗ ), z − z ∗ i ≤ 0, ∀i ∈ J + , (1.18) Tương tự, ta có −h5hi (z ∗ ), z − z ∗ i ≤ 0, ∀i ∈ J − . (1.19) Bởi vì với bất kỳ điểm chấp nhận z ta có −G(z) ≤ 0, −H(z) ≤ 0, cho nên + ∪ β +. −h5Gi (z ∗ ), z − z ∗ i ≤ 0, ∀i ∈ α+ ∪ βH (1.20) −h5Hi (z ∗ ), z − z ∗ i ≤ 0, ∀i ∈ γ + ∪ βG+ ∪ β + . (1.21) Trong trường hợp − α− ∪ γ − ∪ βG− ∪ βH 6= ∅, nhân (1.17)-(1.21) với λgi ≥ 0 (i ∈ Ig ), λhi > 0 (i ∈ J + ), −λhi > 0 (i ∈ J − ), + + + H + + + λG i > 0 (i ∈ α ∪ βH ∪ β ), λi > 0 (i ∈ γ ∪ βG ∪ β )