Điều kiện tối ưu cho một số lớp bài toán tối ưu hai cấp

toán một cấp (SP )ϕ tương đương bài toán (BLPP) mà không cần giả thiết lồi cho bài toán cấp dưới (P )x. Tuy nhiên lại gặp hai vấn đề lớn, đầu tiên là hàm ϕ(x) không khả vi (dù cho hàm f, gi đã khả vi liên tục) do đó (SP )ϕ là bài toán không trơn (nonsmooth problem). Để sử dụng công thức nhân tử Lagrange mở rộng Clarke, thì hàm ϕ(x) phải liên tục Lipschitz, để ϕ(x) liên tục Lipschitz thì bài toán cấp dưới phải thỏa (MFCQ) tại nghiệm tối ưu. Vấn đề khó khăn tiếp theo là bởi cấu trúc đặc thù cho nên (MFCQ) rất tiếc lại không thỏa mãn cho (SP )ϕ. Do vậy cần có những CQ yếu hơn (MFCQ) (điều kiện partially calm chẳng hạn). Mục đích của chúng ta trong hướng tiếp cận (4) này, là thiết lập " điều kiện cần tối ưu dạng KKT cho (BLPP) " mà • không sử dụng các yếu tố: giả thiết lồi ở bài toán cấp dưới, giả thiết tập nghiệm Ψ(x) là singleton, giả thiết (MFCQ) cho bài toán cấp dưới. • có sử dụng các yếu tố: điều kiện calm (theo Clarke) hay partial calmness hoặc các điều kiện CQ mở rộng khác. Ta trình bày theo thứ tự sau: • Xây dựng hàm ψ và bài toán (SP)ψ • Điều kiện tối ưu dạng KKT dưới giả thiết calm (Clarke) • Điều kiện tối ưu dạng KKT dưới giả thiết CQ mở rộng • Điều kiện tối ưu khi hàm f(x, y)− ϕ(x) lõm 63 (1) Xây dựng hàm ψ và bài toán (SP)ψ Đặt Y (x) := {y ∈ Rm|gi(x, y) ≤ 0, i ∈ I} là tập chấp nhận được của (Px), (x, y) là nghiệm tối ưu địa phương của (BLPP). Giả thiết ánh xạ Y bị chặn đều tại x nghĩa là tồn tại một lân cận U của x sao cho tập ⋃ x∈U Y (x) bị chặn. Tính bị chặn đều của Y tại x đảm bảo cho ϕ tồn tại. Ta gọi U(x, y) là một lân cận mở bị chặn của nghiệm tối ưu (x, y), U := {x ∈ Rn|∃ y sao cho (x, y) ∈ U(x, y)} và tập ⋃ x∈U Y (x) bị chặn. Khi đó ϕ khác rỗng và compac, chứa một lân cận mở của cl ⋃ x∈U Y (x) với clA là tập đóng của tập A. Bây giờ ta đặt hàm σ(x, y, y′) := min{f(x, y) − f(x, y′),−max i∈I gi(x, y ′)} Xây dựng hàm ψ như sau: ψ(x, y) := max y′∈ϕ σ(x, y, y′). (3.88) Bổ đề 3.3.1 ([22], Bổ đề 2.1) (i) {x ∈ U, y ∈ Y (x)|f(x, y)− ϕ(x) < 0} = {x ∈ U, y ∈ Y (x)|ψ(x, y) < 0} (ii) {x ∈ U, y ∈ Y (x)|f(x, y)− ϕ(x) = 0} ⊆ {x ∈ U, y ∈ Y (x)|ψ(x, y) = 0} (iii) Lấy y ∈ Ψ(x) thì tập nghiệm của bài toán ψ(x, y) cho bởi Ψ(x). Chứng minh (i) Lấy x ∈ U, y ∈ Y (x) Do ϕ compac nên ψ(x, y) < 0 ⇐⇒ σ(x, y, y′) < 0, ∀y ∈ ϕ, mà −max i∈I gi(x, y ′) ≥ 0, ∀y′ ∈ ϕ nên ψ(x, y) < 0 ⇐⇒ f(x, y) < f(x, y′), ∀y′ ∈ ϕ Mặt khác Y (x) ⊂ ϕ nên điều này tương đương f(x, y) < f(x, y′), ∀y′ ∈ Y (x), kết hợp định nghĩa của ϕ(x) nên điều này tương đương f(x, y)− ϕ(x) < 0, ∀y ∈ Y (x) nghĩa là đẳng thức đầu được chứng minh. Ngoài ra theo định nghĩa của hàm ψ ta suy ra tập thứ nhất = ∅, do đó suy ra (i). (ii) Lấy x ∈ U, y ∈ Y (x) sao cho f(x, y) − ϕ(x) = 0 =⇒ y là nghiệm cực tiểu toàn cục của (Px). Nếu ψ(x, y) < 0 thì mâu thuẫn (i) 64 Nếu ψ(x, y) > 0 thì cũng không xảy ra. Thật vậy ψ(x, y) > 0, do định nghĩa của hàm ψ trong (3.88) =⇒ ∃ y′ ∈ ϕ sao choσ(x, y, y′) > 0 =⇒ f(x, y′) < f(x, y)∀y′ ∈ ϕ =⇒ f(x, y′) < f(x, y) ∀y′ ∈ Y (x) ⊂ ϕ, điều này mâu thuẫn với y là nghiệm cực tiểu toàn cục của (Px) do đó ψ(x, y) = 0 =⇒ (ii) (iii) Lấy y ∈ S(x). Ta có ψ(x, y = maxy′∈ϕ σ(x, y, y′) với σ(x, y, y′) = min{f(x, y)− f(x, y′), −max i∈I gi(x, y ′)} Vì Ψ(x) là tập nghiệm của bài toán (Px), kết hợp (i), (ii) ta =⇒ (iii) ¤ Ta xây dựng tiếp bài toán tối ưu mới, kí hiệu là (SP )ψ, xác định như sau: (SP)ψ min F (x, y) sao cho ψ(x, y) ≤ 0, gi(x, y) ≤ 0 i ∈ I, Gk(x, y) ≤ 0 k ∈ K. Bài toán này là bài toán tối ưu một cấp, xuất hiện để khắc phục những khó khăn đã được phân tích của bài toán (SP )ϕ. Rõ ràng về cơ bản thì hai bài toán này như nhau, và chỉ khác ở ràng buộc thứ nhất. Nhờ Bổ đề 3.3.1 mà bài toán (SP )ψ có mối liên hệ với bài toán gốc (BLPP) như sau: Nếu (x, y) là nghiệm tối ưu địa phương của (BLPP) thì nó cũng là nghiệm tối ưu địa phương của (SP )ψ 65 (2) Điều kiện tối ưu dạng KKT dưới giả thiết calm Trước tiên, ta thiết lập hàm Lagrange dạng Fritz John của bài toán cấp dưới L(x, y, α, γ) = αf(x, y) + ∑ i∈I γigi(x, y) với số α ∈ R và γ ∈ Rp, và tập nhân tử dạng Fritz John của bài toán cấp dưới (Px) tại y FJ(x, y) = {(α, γ) ∈ R× Rp|(α, γ) ≥ 0, || (α, γ) ||1 = 1, ∇yL(x, y, α, γ) = 0, ∑ i∈I γigi(x, y) = 0}, trong đó ||x||1 = ∑n i=1 |xi| là chuẩn vectơ x trong Rn và ∇y kí hiệu là đạo hàm của hàm Lagrange L(.) theo biến y. Dễ thấy tập FJ(x, y) là đa diện lồi khác rỗng (khái niệm này xem chương 1, Mục 1.3). Mệnh đề sau là kết quả của Bổ đề 3.3.1 ở trên và trong ([22], Mệnh đề 2.2) Mệnh đề 3.3.1 Giả sử (x, y) là nghiệm tối ưu địa phương của bài toán tối ưu hai cấp (BLPP). Khi đó hàm ψ(x, y) liên tục Lipschitz tại (x, y), và Gradient mở rộng Clarke tại (x, y) có xấp xỉ trên: ∂o ψ(x, y) ⊆ coW (x, y), (3.89) trong đó W (x, y) := ⋃ y′∈Ψ(x) {α∇f(x, y)− (∇xL(x, y′, α, γ, 0)|(α, γ) ∈ FJ(x, y′)}. (3.90) Bây giờ áp dụng kết quả củaMệnh đề 3.3.1 vừa nêu ta có hàm ψ liên tục Lipschitz tại nghiệm tối ưu địa phương, kết hợp với các công thức nhân tử Lagrange mở rộng trong [5, Mệnh đề 6.4.4] với giả thiết calmness trong [20, Định nghĩa 6.4.1], và Định lý Carathéodory, ta suy ra điều kiện tối ưu dạng KKT cho (BLPP). 66 Kết quả này tương tự như (mục 3.2, - bài toán trơn) , cách chứng minh xem trong [[22], Mệnh đề 2.3] và [[5], Định lý 6.5.2] Định lý 3.3.1 (Điều kiện cần KKT dưới giả thiết calm cho (BLPP)) Giả sử (x, y) là nghiệm tối ưu địa phương của (BLPP) với S(x) 6= ∅ và bài toán (SP )ψ là calm tại (x, y) theo nghĩa Clarke (xem [5], Định nghĩa 6.4.1). Khi đó tồn tại các nhân tử µ ∈ R+, η ∈ Rp+, β ∈ Rq+ sao cho 0 ∈ ∇F (x, y) + µ coW (x, y) + ∑ i∈I(x,y) ηi∇gi(x, y) + ∑ k∈K(x,y) βk∇Gk(x, y) trong đó I(x, y) := {i ∈ I|gi(x, y) = 0}, K(x, y) := {k ∈ K|Gk(x, y) = 0}. Tương đương, tồn tại λi ≥ 0, yi ∈ S(x), (αi, γi) ∈ FJ(x, yi), i = 1, . . . , n + m + 1, và η ∈ Rp+, β ∈ Rq+ sao cho 0 = ∇F (x, y) + ∑ i∈I(x,y) ηi∇gi(x, y) + ∑ k∈K(x,y) βk∇Gk(x, y) + n+m+1∑ i=1 λi [ αi∇f(x, y)− ( ∇xL(x, yi, αi, γi), 0 )] . (3) Điều kiện tối ưu dạng KKT dưới giả thiết CQ mở rộng Trong mục này, ta sẽ thiết lập điều kiện tối ưu dạng KKT dưới giả thiết một trong các CQs được nêu ra sau đây. Khi điều kiện partially calm hoặc calm không thỏa mãn, ta phải xây dựng một loạt các điều kiện CQ khác. Ta có thể tóm gọm nội dung mục này trong định lý sau: Định lý 3.3.2 [22, Định lý 3.1]( Điều kiện cần tối ưu và mối quan hệ giữa các CQ) Giả sử (x, y) là một nghiệm tối ưu địa phương của bài toán (BLPP) với Ψ(x) 6= ∅. (i) Khi đó dưới giả thiết một trong các CQs thỏa, thì (x, y) thỏa điều kiện dạng 67 KKT, nghĩa là: 0 ∈ ∇F (x, y) + cl cone [ W (x, y) ∪ ⋃ i∈I(x,y) { ∇gi(x, y) } ∪ ⋃ k∈K(x,y) { ∇Gk(x, y) }] . (3.91) (ii) Hơn nữa mối quan hệ giữa các CQs được miêu tả như sau: (1.) N. weak reverse convex CQ =⇒ N. AHU CQ =⇒ N. Zangwill CQ =⇒ N. Kuhn Tucker CQ =⇒ N. Abadie CQ, (2.) N. AHU CQ =⇒ E. AHU CQ, N. Zangwill =⇒ E. Zangwill CQ, N. Kuhn Tucker CQ =⇒ E. Kuhn Tucker CQ, N. Abadie CQ =⇒ E. Abadie CQ, (3.) E. AHU CQ =⇒ E. Zangwill CQ =⇒ E. Kuhn Tucker CQ =⇒ E. Abadie CQ. N. viết tắt của nonsmooth (không trơn), E. viết tắt của extend (mở rộng). Các điều kiện định tính ràng buộc CQs Ta sử dụng định nghĩa giả lõm và ∂ − giả lõm sau đây. Định nghĩa 3.3.1 ([22], hàm giả lõm (pseudoconcave function)) Cho D ⊂ Rn là tập lồi. Đặt C1 := {f : D → R|f liên tục và các đạo hàm riêng của f liên tục trên D } Kí hiệu ∇f(x) là đạo hàm hàm số f theo x. Một hàm f : D → R, ∈ C1 được gọi là giả lồi (pseudoconvex) nếu ∀x1, x2 ∈ D và một hàm số thực k(x1, x2) > 0 sao cho: (x1 − x2)T∇f(x2) ≤ k(x1, x2) [f(x1)− f(x2)] Hàm f : D → R, ∈ C1 được gọi là giả lõm (pseudoconcave) nếu (−f) là hàm giả lồi. Định nghĩa 3.3.2 ([22], hàm ∂− giả lõm) Cho hàm f : Rn → R, x ∈ Rn sao cho f Lipschitz địa phương tại x. Hàm f được gọi là ∂ − giả lõm tại x nếu ∀x ∈ Rn, max w∈∂of(x) wT (x− x) ≤ 0 =⇒ f(x) ≤ f(x), trong đó ∂of(.) là gradient mở rộng Clarke. 68 Đặt h(x, y) := f(x, y)−ϕ(x) và giả sử (x, y) là nghiệm chấp nhận được của bài toán (SP )ψ. N. weak Reverse convex CQ Ta nói N. weak Reverse convex CQ thỏa tại (x, y) nếu • h(x, y) là ∂− giả lõm tại (x, y) với ∂h(x, y) ⊆ ∂ψ(x, y), và • gi(x, y) giả lõm tại (x, y) với i ∈ I(x, y) = {i ∈ I|gi(x, y) = 0}, • Gk(x, y) giả lõm tại (x, y) với k ∈ K(x, y) = {k ∈ K|Gk(x, y) = 0}. N. AHU CQ Ta nói N. AHU CQ thỏa tại (x, y) nếu h(x, y) là ∂− giả lõm tại (x, y) với ∂h(x, y) ⊆ ∂ψ(x, y), và ∃v sao cho • wTv ≤ 0 ∀w ∈ ∂ψ(x, y) • ∇gi(x, y)Tv ≤ 0 ∀i ∈ Λ • ∇gi(x, y)Tv < 0 ∀i ∈ I(x, y) \ Λ trong đó Λ := {i ∈ I(x, y)|gi giả lõm tại (x, y)} • ∇Gk(x, y)Tv ≤ 0 ∀k ∈ Γ • ∇Gk(x, y)Tv < 0 ∀k ∈ K(x, y) \ Γ trong đó Γ := {k ∈ K(x, y)|Gk giả lõm tại (x, y)} Đối với 3 CQs còn lại, trước hết ta gọi Θ là tập chấp nhận được của (BLPP) và giả sử (x, y) là nghiệm chấp nhận được của (BLPP) nghĩa là (x, y) ∈ Θ. Định nghĩa 3.3.3 ([22], Nón tuyến tính không trơn (nonsmooth linearization cone)) Nón tuyến tính không trơn của tập chấp nhận được Θ tại (x, y), xác định bởi L((x, y),Θ) := {v|wTv ≤ 0w ∈ ∂ψ(x, y), ∇gi(x, y)Tv ≤ 0 i ∈ I(x, y), ∇Gk(x, y)Tv ≤ 0 k ∈ K(x, y)} 69 Định nghĩa 3.3.4 ([22], Nón contingent (contingent cone)) Nón contingent (con- tingent cone) của tập M tại x, với M là tập con đóng trong Rn và x ∈ M ; là nón đóng xác định bởi T (x,M) := {v ∈ X|∃tn ↓ 0, vn → v sao cho x+ tnvn ∈ M ∀n} Định nghĩa 3.3.5 ([22], Nón sinh bởi các hướng (cone of attainable directions)) Nón sinh bởi các hướng (cone of attainable directions) của tập M tại x là nón đóng xác định bởi A(x,M) := {v|∃δ > 0 và ánh xạα : R→ X sao choα(τ) ∈ M ∀τ ∈ (0, δ), α(0) = x và lim τ↓0 {α(τ)− α(0) τ = v}, nón này có định nghĩa tương đương là A(x,M) = lim inf τ↓0 M − x τ Định nghĩa 3.3.6 ([22], Nón sinh bởi các hướng chấp nhận cone of feasible direc- tions)) Nón sinh bởi các hướng chấp nhận (cone of feasible directions) của M tại x là nón xác định bởi D(x,M) := {v ∈ X|∃ δ > 0 sao cho x+ tv ∈ M ∀t ∈ (0, δ)} Qua các định nghĩa trên, ta có nhận xét sau: Nhận xét 3.3.1 Mối quan hệ của ba loại nón trên, như sau: clD(x,M) ⊆ A(x,M) ⊆ T (x,M) N. Zangwill Ta nói N. Zangwill thỏa tại (x, y) ∈ Θ nếu L((x, y),Θ) ⊆ clD((x, y,Θ) trong đó D(.,Θ) xác định bởi (3.3.9) N. Kuhn Tucker CQ Ta nói N. Kuhn Tucker CQ thỏa tại (x, y) ∈ Θ nếu L((x, y),Θ) ⊆ A((x, y,Θ) trong đó A(.,Θ) xác định bởi (3.3.8) N. Abadie CQ 70 Ta nói N. Abadie CQ thỏa tại (x, y) ∈ Θ nếu L((x, y),Θ) ⊆ T ((x, y,Θ) ). Để tìm hiểu các (E. CQ) ta mở rộng nón tuyến tính L của Θ thành nón tuyến tính L′ Nhắc lại nón tyến tính trong trường hợp "không trơn", L((x, y),Θ) := {v|wTv ≤ 0w ∈ ∂ψ(x, y), ∇gi(x, y)Tv ≤ 0 i ∈ I(x, y), ∇Gk(x, y)Tv ≤ 0 k ∈ K(x, y)} Nón L′ là nón mở rộng của nón L ở trên, thông qua kết quả trong Mệnh đề 3.3.1 là (3.89): ∂o ψ(x, y) ⊆ coW (x, y) (hàm W xác định trong (3.90)), ta thay thế w ∈ ∂ψ(x, y) bằng w ∈ W (x, y). Như vậy Nón L′ được xác định như sau: L′((x, y),Θ) := {v|wTv ≤ 0w ∈ W (x, y), ∇gi(x, y)Tv ≤ 0 i ∈ I(x, y), ∇Gk(x, y)Tv ≤ 0 k ∈ K(x, y)}. Bây giờ các CQs mở rộng được định nghĩa như sau E. AHU CQ Ta nói E. AHU CQ thỏa tại (x, y) nếu h(x, y) là ∂− giả lõm tại (x, y) với ∂h(x, y) ⊆ ∂ψ(x, y), và ∃v sao cho • wTv ≤ 0 ∀w ∈ W (x, y) ( thay ∂ψ bởi W) • ∇gi(x, y)Tv ≤ 0 ∀i ∈ Λ • ∇gi(x, y)Tv < 0 ∀i ∈ I(x, y) \ Λ trong đó Λ := {i ∈ I(x, y)|gi giả lõm tại (x, y)} • ∇Gk(x, y)Tv ≤ 0 ∀k ∈ Γ • ∇Gk(x, y)Tv < 0 ∀k ∈ K(x, y) \ Γ trong đó Γ := {k ∈ K(x, y)|Gk giả lõm tại (x, y)} 71 E. Zangwill Ta nói E. Zangwill thỏa tại (x, y) ∈ Θ nếu L′((x, y),Θ) ⊆ clD((x, y,Θ) trong đó D(.,Θ) xác định bởi (3.3.9) E. Kuhn Tucker CQ Ta nói E. Kuhn Tucker CQ thỏa tại (x, y) ∈ Θ nếu L′((x, y),Θ) ⊆ A((x, y,Θ) trong đó A(.,Θ) xác định bởi (3.3.8) E. Abadie CQ Ta nói N. Abadie CQ thỏa tại (x, y) ∈ Θ nếu L′((x, y),Θ) ⊆ T ((x, y,Θ). Bây giờ trở lại Chứng minh Định lý 3.3.2. Trước tiên ta chứng minh (ii) + Theo Định nghĩa của hai nón L((x, y),Θ) có một phần ràng buộc là wT ≤ 0, w ∈ ∂ψ(x, y) và nón L′((x, y),Θ) có một phần ràng buộc là wT ≤ 0w ∈ W (x, y) , mặt khác do (3.90) của Mệnh đề 3.3.1, ta suy ra L′((x, y),Θ) ⊆ L((x, y),Θ) + Như vậy N. AHU CQ =⇒ E. AHU CQ là do (3.89), còn 3 CQs còn lại thì do mối quan hệ giữa hai nón trên. Suy ra (2.) N. weak reverse convex CQ =⇒ N. AHU CQ Ta chỉ cần chỉ ra h(x, y) = f(x, y)−ϕ(x) ∂-giả lõm, ∂h(x, y) ⊆ ∂ψ(x, y), gi(x, y) (i ∈ I(x, y)), Gk(x, y) (k ∈ K(x, y)) giả lõm =⇒ ∃ v thỏa hệ 5 bất đẳng thức của N. AHU CQ + Từ Định nghĩa 3.3.2, h là ∂- giả lõm suy ra ∃v ∈ Rn×Rm sao cho wTv ≤ 0 với w ∈ ∂h(x, y), mà ∂h(x, y) ⊆ ∂ψ(x, y) suy ra bất đẳng thức thứ nhất. + Từ Định nghĩa 3.3.1, gi là giả lõm, ta suy ra gi[(x, y) + tv] ≤ gi(x, y), t > 0 suy ra gi[(x,y)+tv]−gi(x,y) t ≤ 0 suy ra ∇gi(x, y)Tv ≤ 0 từ đó suy ra hai bất đẳng thức tiếp theo . Tương tự cho hàm G ta suy ra hai bất đẳng thức còn lại. N. AHU CQ =⇒ N. Zangwill + Ta có, tồn tại v sao cho wTv ≤ 0 ∀w ∈ ∂ψ(x, y), mà ∂h(x, y) ⊆ ∂ψ(x, y) do đó với t ≥ 0 ta có wT [(x, y) + tv − (x, y)] ≤ 0 ∀w ∈ ∂h(x, y) 72 Vì h(x, y) là ∂ - giả lõm tại (x, y), suy ra h[(x, y) + tv] ≤ h(x, y), mặt khác h(x, y) = f(x, y)− ϕ(x) ≤ 0 nên h[(x, y) + tv] ≤ 0, ∀t ≥ 0. + Tương tự ta có gi[(x, y)+ tv] ≤ 0 i ∈ I(x, y) và Gk[(x, y)+ tv] ≤ 0 k ∈ K(x, y) Theo Bổ đề 3.3.1, ta suy ra tồn tại δ > 0 sao cho (x, y) + tv ∈ Θ suy ra v ∈ D((x, y),Θ) =⇒ N. Zangwill thỏa tại (x, y). N. Zangwill CQ =⇒ N. Kuhn Tucker CQ =⇒ N. Abadie CQ Từ Nhận xét 3.3.1, ta suy ra clD((x, y),Θ) ⊆ A((x, y),Θ) ⊆ T ((x, y),Θ), do đó L((x, y),Θ) ⊆ clD((x, y),Θ) =⇒ L((x, y),Θ) ⊆ A((x, y),Θ) =⇒ L((x, y),Θ) ⊆ T ((x, y),Θ). Tóm lại ta có (1.), do đó ta có (3.) (thay nón L(.) bởi L′(.)) Bây giờ ta chứng minh (i) qua (ii) ta cũng thấy E. Abadie CQ chính là CQ yếu nhất. Ta sẽ chứng minh (i) thỏa với CQ yếu nhất và quan trọng này. Rõ ràng N. Abadie CQ tương ứng với nón L(.), còn E. Abadie CQ tương ứng với nón L′. Bây giờ ta nêu một bổ đề tương ứng khi N. Abadie CQ thỏa, và cách chứng minh cho (i) tương tự như cách chứng minh của bổ đề này. Bổ đề 3.3.2 [22, Mệnh đề 3.1](Điều kiện tối ưu dạng KKT dưới giả thiết N.Abadie CQ) Giả sử (x, y) là nghiệm tối ưu địa phương của (BLPP). Nếu N. Abadie CQ thỏa tại (x, y) thì 0 ∈ ∇F (x, y) + cl cone [ ∂ψ(x, y) ∪ ⋃ i∈I(x,y) { ∇gi(x, y) } ∪ ⋃ k∈K(x,y) { ∇Gk(x, y) }] . (3.92) 73 Chứng minh Vì (x, y) là nghiệm tối ưu của (BLPP), nên ∇F (x, y)Tv ≥ 0 ∀v ∈ T ((x, y),Θ). Giả sử N. Abadie CQ thỏa tại (x, y). Thế thì ∇F (x, y)Tv ≥ 0 ∀v ∈ L((x, y),Θ). Tương đương, ∇F (x, y)Tv ≥ 0 với max a∈C aTv ≤ 0, trong đó C là nón lồi, sinh bởi ∂ψ(x, y) ∪ ⋃ i∈I(x,y) {∇gi(x, y)} ∪ ⋃ k∈K(x,y) {∇Gk(x, y)}. Do đó hàm v → ∇F (x, y)Tv + δCo(v) đạt cực tiểu tại 0, trong đó Co := {v ∈ Rn × Rm|vT c ≤ 0 ∀v ∈ C} là nón đối cực của nón C, và δCo là hàm chỉ số của tập C o Theo kiến thức bài toán tối ưu lồi một cấp–chương 1, ta có điều này tương đương 0 ∈ ∇F (x, y) + ∂δCo(0). Mặt khác ∂δCo(0) = C oo = clC, do đó lại tương đương 0 ∈ ∇F (x, y) + clC. Suy ra điều phải chứng minh. Như vậy trong (3.92) ta thay ∂ψ bằng W ta sẽ có kết quả (3.91) của Định lý 3.3.2 đúng với giả thiết yếu nhất E. Abadie CQ. ¤ (4) Điều kiện tối ưu khi hàm f(x, y)− ϕ(x) lõm Xét bài toán (BLPP) khi hàm f(x, y)− ϕ(x) là hàm lõm. Ta cũng có các mệnh đề, định nghĩa và định lý tương ứng trong trường hợp này. Mệnh đề 3.3.2 (xấp xỉ trên của gradient mở rộng Clark của ψ) Giả sử (x, y) là nghiệm tối ưu địa phương của (BLPP) trong đó Ψ(x) 6= ∅ và hàm 74 ψ là lõm. Khi đó với bất kì y ∈ Ψ(x), gradient mở rộng Clarke của hàm ψ có xấp xỉ trên: ∂ψ(x, y) ⊆ A := {( − ∑ i∈I(x,y) γi∇xgi(x, y), α∇yf(x, y) ) | (α, γ) ∈ FJ(x, y) } . (3.93) Chứng minh Để ý −ψ(x, y) = min y′,z {−z| − f(x, y) + f(x, y′) + z ≤ 0, gi(x, y′) + z ≤ 0 i ∈ I y′ ∈ ϕ}, bởi Bổ đề 3.3.1 thì nghiệm của bài toán trên là Ψ(x)× {0}. Bởi vì −ψ(x, y) là lồi và bị chặn trên một lân cận của (x, y) nên −ψ là Lipschitz tại (x, y) (xem [5, Mệnh đề 2.2.6], lấy ξ ∈ ∂(−ψ)(x, y) thế thì theo định nghĩa dưới vi phân, ta có −ψ(x, y)− (−ψ(x, y)) ≥ 〈ξ, (x, y)− (x, y)〉 ∀(x, y) ∈ Rn × Rm Theo định nghĩa của ψ ta có ∀(x, y, y′, z) thỏa các ràng buộc sau −z ≥ −f(x, y) + f(x, y′), −z ≥ gi(x, y′) i ∈ I, y′ ∈ ϕ Kết hợp các yếu tố trên, ta có −z ≥ 〈ξ, (x, y)− (x, y)〉 Do đó (x, y, y′, z) = (x, y, y, 0) là một nghiệm của bài toán tối ưu sau: min x,y,y′,z −z − 〈ξ, (x, y)− (x, y)〉 sao cho − f(x, y) + f(x, y′) + z ≤ 0, gi(x, y ′) + z ≤ 0 i ∈ I, y′ ∈ ϕ (MFCQ) (xem chương 1) thỏa đối với bài toán trên, do đó ∃ (α, γ) ∈ R × Rs, (α, γ) ≥ 0, ||(α, γ)||1 = 1 sao cho ξ = α[−∇f(x, y) +∇xf(x, y × 0] + ∑ i∈I γi∇xgi(x, y)× 0, 75 0 = α∇yf(x, y) + ∑ i∈I γi∇ygi(x, y), 0 = ∑ i∈I γigi(x, y), nghĩa là ξ ∈ B := {( ∑ i∈I(x,y) γi∇xgi(x, y), α∇yf(x, y) ) | (α, γ) ∈ FJ(x, y) } . Suy ra ∂(−ψ)(x, y) ⊆ B Mặt khác ∂ψ(x, y) = −∂(−ψ)(x, y), do đó ∂ψ(x, y) ⊆ −B = {( − ∑ i∈I(x,y) γi∇xgi(x, y), α∇yf(x, y) ) | (α, γ) ∈ FJ(x, y) } . ¤ Bây giờ ta xác định nón mở rộng trong trường hợp lõm. Định nghĩa 3.3.7 ([22], Nón tuyến tính mở rộng cho trường hợp hàm lõm) Giả sử (x, y) ∈ Θ. Nón tuyến tính mở rộng cho trường hợp hàm lõm là tập: L˜((x, y),Θ) := { v| ( − ∑ i∈I(x,y) γi∇xgi(x, y)}, α∇yf(x, y) )T v ≤ 0, (α, γ) ∈ FJ(x, y), ∇gi(x, y)Tv ≤ 0, i ∈ I(x, y), ∇Gk(x, y)Tv ≤ 0, k ∈ K(x, y) } (3.94) Định nghĩa 3.3.8 Ta nói E. Abadie CQ, E. Kuhn Tucker CQ, E. Zangwill cho trường hợp lõm thỏa tại (x, y) nếu L˜((x, y),Θ) ⊆ T ((x, y),Θ) L˜((x, y),Θ) ⊆ A((x, y),Θ) L˜((x, y),Θ) ⊆ cl D((x, y),Θ), tương ứng. 76 Định nghĩa 3.3.9 Ta nói E. AHU CQ cho trường hợp lõm thỏa tại (x, y) nếu ψ lõm, và ∃v sao cho + (−∑i∈I(x,y) γi∇xgi(x, y)}, α∇yf(x, y))Tv ≤ 0 ∀(α, γ) ∈ FJ(x, y) + ∇gi(x, y)Tv ≤ 0 ∀i ∈ Λ + ∇gi(x, y)Tv < 0 ∀i ∈ I(x, y) \ Λ trong đó Λ := {i ∈ I(x, y)|gi giả lõm tại (x, y)} + ∇Gk(x, y)Tv ≤ 0 ∀k ∈ Γ + ∇Gk(x, y)Tv < 0 ∀k ∈ K(x, y) \ Γ trong đó Γ := {k ∈ K(x, y)|Gk giả lõm tại (x, y)} Định lý 3.3.3 (Điều kiện cần tối ưu dạng KKT trong trường hợp lõm) Giả sử (x, y) là nghiệm tối ưu của (BLPP) và S(x) 6= ∅. Giả sử h(x, y) = f(x, y)−ϕ(x) là lõm và một trong các CQs thỏa mãn, gồm N. Abadie CQ, N. Kuhn Tucker CQ, N. Zangwill CQ, N. weak reverse convex CQ, E. Abadie CQ, E. Kuhn Tucker CQ, E. Zangwill CQ, E. AHU CQ cho trường hợp lõm, thì (i) tồn tại (α, γ) ∈ FJ(x, y) và λ ≥ 0, η ∈ Rp+, β ∈ Rq+ sao cho 0 = ∇F (x, y) + λ(− ∑ i∈I(x,y) γi∇xgi(x, y)}, α∇yf(x, y)) + ∑ i∈I(x,y) ηi∇gi(x, y) + ∑ k∈K(x,y) βk∇Gk(x, y). (3.95) Tương đương, (ii) tồn tại λ ≥ 0, α ≥ 0, γ ∈ Rp+, η ∈ Rp+, β ∈ Rq+ sao cho ||(α, γ)|1 = 1 và 0 = ∇F (x, y) + ∑ i∈I (ηi − λγi)∇gi(x, y) + ∑ k∈K(x,y) βk∇Gk(x, y), (3.96) 0 = α∇yf(x, y) + ∑ i∈I(x,y) γi∇ygi(x, y), (3.97) γi = 0, ηi = 0 ∀i /∈ I(x, y). (3.98) 77 Tương đương, (iii) tồn tại α ≥ 0, γ ∈ Rp+, ηg ∈ Rp, β ∈ Rq+ sao cho ||(α, γ)||1 = 1 và 0 = ∇F (x, y) + ∑ i∈I(x,y) ηgi∇gi(x, y) + ∑ k∈K(x,y) βk∇Gk(x, y), (3.99) 0 = α∇yf(x, y) + ∑ i∈I(x,y) γi∇ygi(x, y), (3.100) ηgi ≥ 0 i ∈ Io(x, y), (3.101) trong đó Io(x, y) := {i ∈ I|gi(x, y) = 0 và γi = 0}. Chứng minh Rõ ràng tất cả CQs đều suy ra được E. Abadie CQ trong trường hợp lõm. Bây giờ giả sử E. Abadie CQ trong trường hợp lõm thỏa. Thay thế nón tuyến tính L((x, y),Θ) bởi tuyến tính mở rộng cho trường hợp lõm là L˜((x, y),Θ) trong chứng minh của Bổ đề 3.3.2, ta có 0 ∈ ∇F (x, y) + cl cone [ A ∪ ⋃ i∈I(x,y) { ∇gi(x, y) } ∪ ⋃ k∈K(x,y) { ∇Gk(x, y) }] . (3.102) trong đó A kí hiệu trong (3.93). Mặt khác do tập FJ(x, y) là đa diện lồi khác rỗng (convex polytope) (xem định nghĩa của FJ(.)) và( − ∑ i∈I(x,y) γi∇xgi(x, y), α∇yf(x, y) ) là ánh xạ tuyến tính của (α, γ) suy ra tập A cũng là đa diện lồi, xem [16, Định lý 19.3]. Theo định nghĩa của đa diện lồi, tập A là một bao lồi gồm hữu hạn điểm. Đặt A1 := A ∪ ⋃ i∈I(x,y) {∇gi(x, y)} ∪ ⋃ k∈K(x,y) {∇Gk(x, y)} ⋃ {0}. Theo [16, Hệ quả 19.7.1], nón lồi sinh bởi coB là đa diện. Tuy nhiên, nón lồi sinh bởi tập A2 := A ∪ ⋃ i∈I(x,y) {∇gi(x, y)} ∪ ⋃ k∈K(x,y) {∇Gk(x, y)} 78 cũng là đa diện, nên là nón đóng. Do đó trong (3.102) phần đóng (cl(.)) là thừa. Nghĩa là do A lồi nên tồn tại (α, γ) ∈ FJ(x, y) và λ ≥ 0, η ≥ 0, β ≥ 0 sao cho (3.95) thỏa. suy ra (i) thỏa. Ta thấy (i) ⇐⇒ (ii); (ii) =⇒ (iii) là hiển nhiên. Bây giờ giả sử (iii) thỏa, ta lấy λ là số dương bé nhất sao cho ηgi + λγi ≥ 0 ∀i ∈ I(x, y) và η := ηg + λγ, suy ra (ii) thỏa với nhân tử (λ, α, γ, η, β). ¤ M 79 Chương 4 Điều kiện tối ưu cho bài toán hai cấp vô hạn Các kết quả trong phần này có liên quan đến chương 3 và các bài báo [6, 7, 8, 9, 11]. Thực chất điều kiện tối ưu cho bài toán hai cấp vô hạn được phát triển dựa trên một phần của hướng tiếp cận số (3) trong không gian hữu hạn trong Chương 3. Ở đây ta xét trong không gian vô hạn chiều với tập chỉ số T vô hạn (xem chương 2, (c) bài toán hai cấp vô hạn). Sau đây ta sẽ đi sâu vào lớp bài toán tối ưu hai cấp vô hạn và điều kiện tối ưu của chúng. 4.1 Bài toán hai cấp vô hạn Xét bài toán hai cấp vô hạn (dạng optimistic), như sau: min F (x, y) sao cho x ∈ X, y ∈ Ψ(x) := {y ∈ G(x)| f(x, y) = ϕ(x)}. (4.1) trong đó Ψ(x) là tập nghiệm của bài toán cấp dưới min f(x, y) sao cho y ∈ G(x) := {y ∈ Y | gt(x, y) ≤ 0, t ∈ T}, T vô hạn. (4.2) 80 và ϕ(.) là hàm giá trị của bài toán cấp dưới ϕ(x) := inf {f(x, y)| y ∈ G(x)}. (4.3) Ta lưu ý X, Y là không gian Banach tùy ý và T là tập chỉ số trong các ràng buộc bất đẳng thức của (4.2), là tùy ý. Chính điều này làm cho bài toán (4.1)–(4.3) này, trở thành bài toán tối ưu hai cấp vô hạn. Các giả thiết cố định như sau: • hàm mục tiêu của bài toán cấp trên (4.1), F : X × Y → R proper, lsc và lồi. • các hàm của bài toán cấp dưới (4.2), f, gt : X × Y → R proper, lsc và lồi. • X,Y là hai không gian Banach tùy ý. Bài toán có các giả thiết kiểu này, được gọi là bài toán lồi hoàn toàn (fully convex). Các khái niệm proper, lsc xem chương 1. Bây giờ ta tìm hiểu cụ thể một loạt các tính chất có liên quan chặt chẽ tới bài toán hai cấp vô hạn. Để thiết lập điều kiện tối ưu cho bài toán hai cấp vô hạn, thì ta phải xét bài toán DC vô hạn có liên quan. 4.2 Điều kiện tối ưu cho bài toán DC vô hạn (1) Bài toán DC vô hạn không chứa tham số Trước tiên chúng ta xét dạng bài toán DC vô hạn không chứa tham số y là một lớp các bài toán tối ưu trong không gian Banach với các hàm mục tiêu là hiệu của hai hàm lồi (Difference of two Convex functions– viết tắt là DC). minϑ(x)− θ(x) sao cho ϑt(x) ≤ 0, t ∈ T, và x ∈ Θ (4.4) 81 trong đó T là tập chỉ số tùy ý, Θ ⊂ X là tập con lồi đóng của không gian Banach X; ϑ, θ, ϑt : X → R proper, lsc, lồi. Kí hiệu tập nghiệm chấp nhận được của (4.16) E := Θ ∩ {x ∈ X|ϑt(x) ≤ 0 ∀t ∈ T}. (4.5) Xét không gian RT := {λ = (λt| t ∈ T )|λt ∈ R t ∈ T} Không gian thực mở rộng R˜T := {λ ∈ RT |λt 6= 0 với hữu hạn t ∈ T} Nón dương trong R˜T , xác định R˜T+ := {λ ∈ R˜T |λt ≥ 0 ∀t ∈ T}. (4.6) Cho vectơ u ∈ RT và λ ∈ R˜T , ta kí hiệu suppλ := {t ∈ T |λt 6= 0}, chúng ta có tích vô hướng mở rộng λu := ∑ t∈T λtut = ∑ t∈ suppλ λtut. Điều kiện định tính (CQ) sau đây đóng một vai trò rất quan trọng trong việc thiết lập điều kiện cần tối ưu cho bài toán DC vô hạn (điều kiện tối ưu dạng KKT) tương ứng cho hàm DC ϑ − θ. Vai trò của CQ này còn đảm bảo tồn tại các công thức tính chứa các ràng buộc vô hạn. Định nghĩa 4.2.1 ([7],Closedness Qualification Condition = CQC) Chúng ta nói bộ ba (ϑ, ϑt,Θ) thỏa điều kiện CQC nếu tập epiϑ∗ + cone {⋃ t∈T epiϑ∗t } + epi δ∗(.; Θ) là đóng yếu∗ trong không gian X∗ × R. Tiếp theo, ta dùng CQC này để thiết lập điều kiện cần cho bài toán DC vô hạn (4.4). Trước hết, xét tập nhân tử ràng buộc A(x) := {λ ∈ R˜T+|λtϑt(x) = 0 ∀t ∈ suppλ}. (4.7) 82 Định lý 4.2.1 ([16], Điều kiện cần cho bài toán DC vô hạn) Giả sử x ∈ E ∩ domϑ là nghiệm cực tiếu địa phương của (4.16) thỏa CQC. Khi đó ta có ∂θ(x) ⊂ ∂ϑ(x) + ⋃ λ∈A(x) [ ∑ t∈suppλ λt∂ϑt(x) ] +N(x; Θ). (4.8) Chứng minh Không mất tính tổng quát, giả sử x ∈ dom θ và ∂ θ(x) 6= ∅ (nếu ∂ θ(x) = ∅, thì (4.8) luôn đúng). Theo công thức dưới vi phân xấp xỉ, với ε = 0, tồn tại x∗ ∈ ∂ θ(x) (x∗ ∈ X∗) nghĩa là θ(x)− θ(x) ≥ 〈x∗, x− x〉 ∀x ∈ X. Điều này có nghĩa là x là cực tiểu địa phương cho bài toán vô hạn lồi sau: min ϑ˜(x) := ϑ(x)− 〈x∗, x− x〉 − θ(x) sao cho ϑt(x) ≤ 0, t ∈ T, và x ∈ Θ. (4.9) Bài toán (4.9) là lồi, và nghiệm x là nghiệm toàn cục của bài toán này, nghĩa là ϑ˜(x) ≤ ϑ˜(x) ∀x ∈ E. Theo [6, Bổ đề 4], điều này tương đương với (0,−ϑ˜(x) ∈ cl∗ ( epi ϑ˜∗ + cone [⋃ t∈T epiϑ∗t ] + epi δ∗ (.; Θ) ) . kết hợp với epi ϑ˜∗ = (−x∗, θ(x) − 〈x∗, x〉 + epiϑ∗ (xem cấu trúc của ϑ˜ trong (4.9), ta có: (0, - ϑ˜(x) ∈ (−x∗, θ(x)− 〈x∗, x〉) + cl∗ ( epiϑ∗ + cone [⋃ t∈T epiϑ∗t ] + epi δ∗ (.; Θ) ) . (4.10) Hơn nữa, do (i) =⇒ (ii) trong Bổ đề 4.2.1, dưới giả thiết CQC, nên (4.10) tương đương với: (x∗,−ϑ˜(x)− θ(x) + 〈x∗, x〉) ∈ ( epiϑ∗ + cone [⋃ t∈T epiϑ∗t ] + epi δ∗ (.; Θ) ) . (4.11) 83 Áp dụng công thức epi f ∗ (xem Mục 1.3, phần (2)) vào các hàm đối ngẫu ϑ∗, ϑ∗t , t ∈ T và δ∗(.; Θ), sau đó thế vào (4.11) và do cấu trúc nón dương (4.6) R˜T+, và lưu ý là −ϑ˜(x)− θ(x) + 〈x∗, x〉 = 〈x∗, x〉 − ϑ(x), do đó chúng ta có ε ≥ 0, u∗ ∈ ∂εϑ(x), λ ∈ R˜T , εt ≥ 0, u∗t ∈ ∂εtϑt(x) với t ∈ T, γ ≥ 0, và v∗ ∈ ∂γ(x; Θ) thỏa mãn hệ phương trình sau (i)x∗ = u∗ + ∑ t∈T λtu ∗ t + v ∗, (ii)〈x∗, x〉 − ϑ(x) = 〈u∗, x〉+ ε− ϑ(x) + ∑ t∈T λt[〈u∗t , x〉+ εt − ϑt(x)] +〈v∗, x〉+ γ − δ(x; Θ). (4.12) Xét hệ phương trình (4.12), ta thay (i) vào (ii), được ε+ ∑ t∈T λtεt − ∑ t∈T λtϑt(x) + γ = 0. (4.13) Mặt khác bộ ba (ε, λt, γ) là phần tử của tập nhân tử ràng buộc (4.7), nên ε ≥ 0, γ ≥ 0, λt ≥ 0, λtϑt(x) ≤ 0 ∀t ∈ T. Kết hợp với phương trình (4.13) cho ta ε = γ = λtεt = λtϑt(x) = 0 ∀t ∈ T, suy ra εt = 0 t ∈ suppλ. Do đó u∗ ∈ ∂ϑ(x), u∗t ∈ ∂ϑt(x), v∗ ∈ ∂δ(x; Θ) = N(x; Θ) và thay vào (i), ta có x∗ ∈ ∂ϑ(x) + ∑ t∈suppλ λt∂ϑt(x) +N(x; Θ) vi λtϑt(x) = 0 ∀t ∈ suppλ. (4.14) Điều này suy ra (4.8). ¤ Sau đây ta tìm hiểu về bài toán DC vô hạn có chứa tham số và dưới Gradient của hàm giá trị. 84 (2) Bài toán DC vô hạn chứa tham số Bài toán DC vô hạn chứa tham số là một lớp các bài toán tối ưu trong không gian Banach với các hàm mục tiêu là hiệu của hai hàm lồi (Difference of two Convex functions– viết tắt là DC). Chúng ta quan tâm đến các hàm giá trị cho bài toán DC chứa tham số, cho bởi ϕ(x) := inf {f(x, y)− g(x, y)| y ∈ F (x) ∩G(x)} (4.15) trong đó dạng hình học của các ràng buộc chứa tham số F (x) := {y ∈ Y | (x, y) ∈ Ω} (4.16) và các ràng buộc bất đẳng thức vô hạn G(x) := {y ∈ Y | gt(x, y) ≤ 0, t ∈ T} (4.17) với T là tập chỉ số tùy ý. Không mất tính tổng quát, ta giả thiết X, Y là không gian Banach tùy ý; các hàm f, g, gt : X × Y → R proper, lower semicontinuous (l.s.c) và lồi; tập Ω ⊂ X × Y lồi và đóng. Lưu ý : • Hàm ϕ(.) không trơn cho dù f, g trơn (khả vi liên tục), • Hàm ϕ(.) cũng không lồi cho dù f, g lồi. Áp dụng CQC trong Định nghĩa 4.3.1 cho bộ ba (ϕ, ϕt,Ω) đối với bài toán (4.15)– (4.17) epiϕ∗ + cone [⋃ t∈T epiϕ∗t ] + epi δ∗(.; Ω) (4.18) là đóng yếu∗ trong X∗ × Y ∗ × R. Ánh xạ (cực tiểu) đa trị Ψ : X ⇒ Y tương ứng cho (4.15)–(4.17), là Ψ(x) := {y ∈ F (x) ∩G(x)|ϕ(x) = f(x, y)− g(x, y)}, (4.19) 85 Tập ràng buộc trong (4.16), (4.17) là Γ := Ω ∩ {(x, y) ∈ X × Y | gt(x, y) ≤ 0 ∀t ∈ T}, (4.20) và tập nhân tử KKT phụ thuộc vào (x, y) ∈ gphΨ với Ψ trong (4.19) và vào y∗ ∈ Y ∗ ∧(x, y, y∗) := {λ ∈ R˜T+ | y∗ ∈ ∂yf(x, y) + ∑ t∈suppλ λt∂ygt(x, y) +Ny((x, y); Ω), λtgt(x, y) = 0 t ∈ suppλ}.(4.21) Tập nhân tử ràng buộc tại (x, y) A(x, y) := {λ ∈ R˜T+|λtϑt(x, y) = 0 ∀t ∈ suppλ}. (4.22) Bây giờ ta nêu định lý sau đây Định lý 4.2.2 [7, Định lý 5.11](Công thức dưới gradient của hàm giá trị ϕ(.) trong bài toán DC vô hạn lồi) Xét bài toán (4.15)–(4.17) với g = 0 trong không gian Banach tùy ý, trong đó thỏa mãn các giả thiết đã nêu và ϕ(.) là lồi. Giả sử điều kiện CQC trong (4.18) thỏa và domΨ 6= ∅ trong đó Ψ xác định bởi (4.19) với g = 0. Khi đó với bất cứ (x, y) ∈ gphΨ, dưới vi phân của ϕ(.) tại x (theo nghĩa giải tích lồi) được tính bởi ∂ϕ(x) = { x∗ ∈ X∗| (x∗, 0) ∈ ∂f(x, y) + ⋃ λ∈A(x,y) [ ∑ t∈suppλ λt∂gt(x, y) ] +N((x, y); Ω) } , (4.23) trong đó A(x, y) xác định bởi (4.22). Chứng minh Với g = 0 lúc này ϕ(x) = infy{ϕ(x, y)|y ∈ F (x) ∩ G(x)}, trong đó F (x), G(x) xác định bởi (4.16), (4.17), tương ứng. Không khó để suy ra ϕ(.) như trên, là lồi và 6= ∅ trong trường hợp g đã = 0. Trước hết ta kiểm tra dấu ⊂. Lấy x∗ ∈ ∂ϕ(x), nghĩa là ϕ(x)− ϕ(x) ≥ 〈x∗, x− x〉 với bất kì x ∈ X 86 Áp dụng [7, Định lý 4.1] (với γ = 0, η = ∞), ta có (x∗, 0) ∈ ∂ϕ(x, y) + ⋃ λ∈A(x,y) [ ∑ t∈supp λ λt∂ϕt(x, y) ] +N((x, y); Ω), suy ra dấu ⊂ trong (4.32). Để chứng tỏ bao hàm thức ngược lại, ta lấy x∗ ∈ X∗ sao cho (x∗, 0) ∈ ∂ϕ(x, y) + ⋃ λ∈A(x,y) [ ∑ t∈supp λ λt∂ϕt(x, y) ] +N((x, y); Ω), do đó ta có λ ∈ A(x, y), (u∗, v∗) ∈ ∂ϕ(x, y), (u∗t , v∗t ) ∈ ∂ϕt(x, y), và (u˜∗, v˜∗) ∈ N((x, y); Ω) sao cho (x∗, 0) = (u∗, v∗) + ∑ t∈suppλ λt(u ∗ t , v ∗ t ) + (u˜ ∗, v˜∗). (4.24) Sử dụng tập nhân tử ràng buộc A(x, y) trong (4.22) và tập chấp nhận được Λ cùng với các định nghĩa về dưới vi phân (giải tích lồi) và nón pháp tuyến cho (4.24), ta có hệ sau f(x, y) - ϕ(x) = f(x, y)− f(x, y) ≥ 〈u∗, x− x〉+ 〈v∗, y − y〉, 0 ≥ λtgt(x, y)− λtgt(x, y) ≥ λt〈u∗t , x− x〉+ λt〈v∗t , y − y〉, t ∈ suppλ, 0 ≥ 〈u˜∗, x− x〉+ 〈v˜∗, y − y〉 ∀(x, y) ∈ Λ. Kết hợp bất đẳng thức cuối, cùng với (4.24), suy ra f(x, y) + δ((x, y); Λ)− ϕ(x) ≥ 〈x∗, x− x〉 ∀(x, y) ∈ X × Y, suy ra ϕ(x)− ϕ(x ≥ 〈x∗, x− x〉 ∀x ∈ X Do đó x∗ ∈ ∂ϕ(x), suy ra dấu ⊃ trong (4.23). M 4.3 Điều kiện tối ưu cho bài toán hai cấp vô hạn Trở lại bài toán hai cấp vô hạn dạng đã nêu ở đầu chương, là (4.1)–(4.3), với các giả thiết tương ứng. Thật may khi bài toán cấp dưới (4.2) là bài toán vô hạn 87 chứa tham số, chính xác nó là trường hợp cụ thể của bài toán DC vô hạn có dạng (4.15)–(4.17), với g = 0 và không có mặt (4.16). Tuy nhiên, đó mới chỉ là bài toán cấp dưới, ta còn phải xét cả bài toán cấp trên nữa. Để tận dụng được lợi thế này, ta phải sử dụng thêm một điều kiện CQ nữa, mục đích là chuyển bài toán hai cấp lồi hoàn toàn (xem đầu chương 4) tương đương với bài toán DC vô hạn, mà bao gồm hàm giá trị ϕ(.) lồi (4.3) đối với bài toán cấp dưới (4.2). Áp dụng Điều kiện cần cho bài toán DC và công thức dưới vi phân của hàm giá trị ϕ(.) để suy ra điều kiện cần cho bài toán hai cấp vô hạn. Trước tiên, ta viết lại bài toán (4.1) thành dạng bài toán tương đương (toàn cục) min f(x, y) sao chof(x, y)− ϕ(x) ≤ 0, y ∈ G(x) và bài toán tuyến tính dạng nhiễu với p ∈ R: min F (x, y) sao chof(x, y)− ϕ(x) + p = 0, y ∈ G(x) (4.25) Nhắc lại điều kiện "Partially calm" Ta nói bài toán (4.1) là partially calm tại nghiệm chấp nhận được (x, y) nếu tồn tại một hằng số a > 0 và một lân cận U của bộ ba (x, y, 0) ∈ X × Y × R sao cho F (x, y)−F (x, y) + a|p| ≥ 0 ∀(x, y, p) ∈ U, chấp nhận được đối với (4.25). (4.26) Bổ đề sau đây cho thấy dưới điều kiện partially calm, thì bài toán tối ưu hai cấp vô hạn (4.1) sẽ trở thành bài toán tối ưu DC một cấp với vô hạn ràng buộc. Thực chất, để có sự tương đương hoàn toàn giữa hai loại bài toán kể trên, ta cần thêm tính liên tục của hàm cấp trên. Bổ đề 4.3.1 [7, Bổ đề 6.1] Giả sử (x, y) là nghiệm chấp nhận được partially calm cho bài toán (4.1), với G : X ⇒ Y cho bởi (4.2) và hàm cấp trên F liên tục tại điểm này. 88 Khi đó (x, y) là nghiệm tối ưu địa phương của bài toán sau: min a−1F (x, y) + f(x, y)− ϕ(x)sao cho gt(x, y) ≤ 0, t ∈ T, (4.27) trong đó a > 0 là hằng số từ điều kiện partially calm (4.26). Chứng minh Bởi (4.1) là partially calm, ta có a > 0 và lân cận U của (x, y, 0) để (4.26) thỏa mãn. Vì F liên tục tại (x, y) nên tồn tại γ > 0 và η > 0 sao cho V := [(x, y) + ηB]× (−γ, γ) ⊂ U và |F (x, y)− F (x, y)| ≤ aγ với (x, y)− (x, y) ∈ ηB. Điều này suy ra F (x, y)− F (x, y) + a(f(x, y)− ϕ(x)) ≥ 0 ∀(x, y) ∈ [(x, y) + ηB] ∩ gphG, (4.28) trong đó G : X ⇒ Y xác định bởi (4.2). Thật vậy, + Nếu (x, y, ϕ(x)− f(x, y) ∈ V thì (4.26) =⇒ (4.28). + Nếu (x, y, ϕ(x)−f(x, y) /∈ V , ta lấy f(x, y)−ϕ(x) ≥ γ nên a(f(x, y)−ϕ(x) ≥ aγ, kết hợp với f(x, y)− f(x, y) ≥ −aγ nên =⇒ (4.28). Hiển nhiên f(x, y) = ϕ(x) (do (x, y) là nghiệm chấp nhận được của (4.1)). Mặt khác (4.28) nghĩa là (x, y) là nghiệm tối ưu địa phương của bài toán DC (4.27). ¤ Định lý kế tiếp cung cấp xấp xỉ trên của dưới vi phân của hàm lồi (4.3) tại nghiệm partially calm đối với bài toán hai cấp. Định lý 4.3.1 [7, Định lý 6.2](dưới gradient của hàm lồi ϕ(.) tại nghiệm partially calm đối với bài toán hai cấp) Giả sử (x, y) là nghiệm chấp nhận 89 được partially calm cho bài toán (4.1). Giả sử điều kiện CQC trong (4.18) thỏa đối với bài toán cấp dưới (4.2) và hàm cấp trên F liên tục tại (x, y). Khi đó tồn tại hằng số a > 0 sao cho ∂ϕ(x)× {0} ⊂ a−1∂F (x, y) + ∂f(x, y) + ⋃ λ∈A(x,y) [ ∑ t∈suppλ λt∂gt(x, y) ] (4.29) cho hàm lồi ϕ(.) trong (4.3), trong đó A(x, y) xác định theo (4.22). Nói riêng, ta có ∂ϕ(x) ⊂ a−1∂xF (x, y) + ∂xf(x, y) + ⋃ λ∈A(x,y) [ ∑ t∈suppλ λt∂xgt(x, y) ] (4.30) Chứng minh Cố định (x, y) thỏa mọi giả thiết của định lý. Bổ đề 4.5.1 suy ra (x, y) là nghiệm tối ưu địa phương của bài toán DC (4.27), là dạng bài toán DC vô hạn có dạng tổng quát (4.4) trong không gian X × Y với các hàm lsc, lồi. Đặt ϑ(x, y) := a−1F (x, y) + f(x, y), θ(x, y) := ϕ(x), và ϑt(x, y) := gt(x, y) (4.31) với Θ = X × Y như trong (4.4). Dùng cấu trúc tập chấp nhận được E := {(x, y) ∈ X × Y |gt(x, y) ≤ 0 ∀t ∈ T} đối với bài toán (4.27), công thức epi(f1+f2) ∗ = cl∗((epif ∗1 +epif ∗ 2 ) (xem [Chương 1, Bổ đề 1.3.1(ii)]) nếu epif ∗1 +epif ∗ 2 không thỏa tính yếu ∗) và sử dụng CQC trong (4.18), ta có một loạt các đẳng thức sau epi(f + δ(.;E))∗ = cl∗(epif ∗ + epiδ∗(.;E)) = cl∗{epif ∗ + cl∗(cone[ ⋃ t∈T epig∗t ])} = cl∗{epif ∗ + (cone[ ⋃ t∈T epig∗t ])} = epif ∗ + cone[ ⋃ t∈T epig∗t ]. Hơn nữa, từ Bổ đề 1.3.1(ii), áp dụng công thức (1.7) vào (4.31) với giả thiết F liên tục tại (x, y), ta lại có epif ∗ + cone[ ⋃ t∈T epig∗t ] = epi(a −1F )∗ + epif ∗ + cone[ ⋃ t∈T epig∗t ] 90 = epi(a−1F )∗ + epi(f + δ(.;E))∗ = epi(ϑ+ δ(.;E))∗. Điều này cho phép ta khẳng định epif ∗ + cone[ ⋃ t∈T epig ∗ t ] là đóng yếu ∗ trong X∗× Y ∗ × R, nghĩa là CQC cho giả thiết Định lý 4.3.1 thỏa, do đó áp dụng Định lý 4.3.1 vào bài toán DC (4.27) trên, ta lưu ý các hàm trong (4.31) có ∂θ(x, y) = ∂ϕ(x) và ∂ϑ(x, y) = ∂(a−1F + f)(x, y) = a−1∂F (x, y) + ∂f(x, y), do F liên tục tại (x, y), từ (4.8) ta suy ra (4.29) còn (4.30) suy ra từ (4.39) khi lấy dưới vi phân cục bộ theo x, nhờ mối quan hệ sau (xem [16, Định lý 4.1], công thức (4.11)). f(x, y) ⊂ ∂xf(x, y)× ∂yf(x, y) và ft(x, y) ⊂ ∂xft(x, y)× ∂yft(x, y). (4.32) ¤ Bây giờ chúng ta thiết lập kết quả chính của chương này: điều kiện tối ưu cho bài toán hai cấp lồi hoàn toàn với vô hạn ràng buộc bất đẳng thức. Định lý 4.3.2 [7, Định lý 6.3](Điều kiện cần cho bài toán hai cấp vô hạn) Giả sử (x, y) là nghiệm tối ưu partially calm của bài toán hai cấp (4.1) thỏa các giả thiết đã nêu. Giả sử CQC trong (4.18) thỏa cho bài toán cấp dưới (4.2), hàm mục tiêu của cấp trên F liên tục tại (x, y) và hàm giá trị trong (4.3) có ∂ϕ(x) 6= ∅. Khi đó với mỗi y˜ ∈ Ψ(x) với Ψ(x) xác định trong (4.19), thì tồn tại một số a > 0, và các nhân tử λ = (λt) ∈ R˜T+, β = (βt) ∈ R˜T+ với R˜T+ là nón dương xác định trong (4.6) sao cho ta có hệ 0 ∈ ∂xF (x, y) + a[∂xf(x, y)− ∂xf(x, y˜)] + ∑ t∈suppλ λt∂xgt(x, y) 91 −a ∑ t∈suppβ βt∂xgt(x, y˜), (4.33) 0 ∈ ∂yF (x, y) + a∂yf(x, y) + ∑ t∈suppλ λt∂ygt(x, y), (4.34) 0 ∈ ∂yf(x, y˜) + ∑ t∈suppβ βt∂ygt(x, y˜), (4.35) λtgt(x, y) = βtgt(x, y˜) = 0 ∀t ∈ T. (4.36) Chứng minh Vì ∂ϕ(x) 6= ∅, ta lấy x∗ ∈ ∂ϕ(x), theo Định lý 4.3.1, tồn tại a > 0 và λ ∈ R˜T+ thỏa mãn a(x∗, 0) ∈ ∂F (x, y) + a∂f(x, y) + ∑ t∈suppλ λt∂gt(x, y) (4.37) với λtgt(x, y) = 0 ∀t ∈ suppλ. Mặt khác chọn y˜ ∈ Ψ(x) và sử dụng kết quả của Định lý 4.4.1, kết hợp với bao hàm thức (4.32), ta tìm được β ∈ R˜T+ sao cho x∗ ∈ ∂xf(x, y˜) + ∑ t∈suppβ βt∂xgt(x, y˜), 0 ∈ ∂yf(x, y˜) + ∑ t∈suppβ βt∂ygt(x, y˜), (4.38) và βtgt(x, y˜) = 0 ∀t ∈ supp β. Kết hợp (4.37), (4.38) với cấu trúc nón dương R˜T+ trong (4.6), ta có hệ (4.33)–(4.36). ¤ Nếu ta thay y˜ = y trong định lý trên, thì có hệ quả sau Hệ quả 4.3.1 [7, Hệ quả 6.4](Trường hợp đặc biệt của Định lý 4.4.2) Giả sử (x, y) là nghiệm tối ưu partially calm của bài toán hai cấp (4.1) thỏa các giả thiết của Định lý (4.4.2). Khi đó tồn tại một số a > 0, và các nhân tử λ = (λt), β = (βt) ∈ R˜T+ sao cho 0 ∈ ∂xF (x, y) + ∑ t∈T [(λt − aβt)∂xgt(x, y), 0 ∈ ∂yF (x, y) + a∂yf(x, y) + ∑ t∈T λt∂ygt(x, y), 0 ∈ ∂yf(x, y) + ∑ t∈T βt∂ygt(x, y), λtgt(x, y) = βtgt(x, y) = 0 ∀t ∈ T 92 Nhận xét 4.3.1 (So sánh với các kết quả đã biết dựa trên điều kiện tối ưu cho bài toán lồi hoàn toàn ở chương 3) So sánh Định lý 4.3.2 chương 4 và Định lý 3.2.2 chương 3, vấn đề " thiết lập điều kiện tối ưu cần cho bài toán lồi" (vô hạn và hữu hạn, tương ứng). Cả hai đều suy ra 4 kết quả tương tự nhau, dưới các giả thiết có khác nhau: điều kiện partially calm, CQC so với điều kiện chính quy, Ψ(.) bị chặn đều (nghĩa là nửa compac trong (inner semicopactness)); như vậy trong Định lý 4.3.2 không cần giả thiết nửa compac trong. Việc chọn y˜ = y đối với Định lý 3.2.2, cần phải có thêm giả thiết nửa liên tục trong (inner semicontinuity) của Ψ(.) tại nghiệm tối ưu (x, y), trong khi điều này không cần trong Hệ quả 4.3.1 của Định lý 4.3.2. Cuối cùng là giả thiết trơn của Định lý 3.2.3, trong khi giả thiết này cũng không cần trong cả Định lý 4.3.2 và Hệ quả 4.3.1 của nó. Mà chúng ta dùng các kỹ thuật khác, khác với [12]. Cuối cùng ta tìm hiểu một bài toán hai cấp lồi đơn giản. 4.4 Điều kiện cần và đủ cho bài toán hai cấp lồi đơn giản Xét lớp bài toán hai cấp lồi đơn giản (Simple Convex Bilvel Problem) (SCBP) min f(x) sao cho x ∈ S, trong đó S cho bởi S = argmin{h(x)|x ∈ Θ} trong đó f, h là các hàm thực, lồi trên Rn và Θ là tập con lồi trong Rn. Cũng như các hàm giá trị của bài toán cấp dưới phần trên, ta suy ra S là tập lồi và do đó bài toán (SCBP) là bài toán lồi. Chúng ta gọi nó là bài toán tối ưu hai cấp lồi đơn giản. Xem cụ thể bài toán này trong [11]. 93 Giả sử S là tập khác rỗng và đặt α = inf x∈Θ h, thì bài toán (SCBP) tương đương với bài toán một cấp sau (RP) min f(x) sao cho h(x) ≤ α, x ∈ Θ Câu hỏi đặt ra là liệu chúng ta có thể thiết lập được điều kiện tối ưu cả cần và đủ cho bài toán (SCBP) hay không. Trước hết ta xét (1) Bài toán tối ưu nón–lồi Xét lớp các bài toán nón-lồi (Cone-convex Problem), (xem [11]). (CCP) min ϑ(x) sao cho g(x) ∈ −D, x ∈ C trong đó ϑ : Rn → R là proper, lồi, lsc và g : Rn → Rm là ánh xạ D–lồi liên tục với D là nón lồi đóng trong Rm và C là tập con trong Rn lồi và đóng. Nhắc lại một số khái niệm. Nón pháp của C tại x là NC(x) = {u ∈ Rn| 〈u, y − x〉 ≤ 0 ∀y ∈ C}, khi x ∈ C và NC(x) = ∅, trường hợp khác. Đặt A := {x ∈ C| g(x) ∈ −D}. Nón đối ngẫu dương của D, kí hiệu D+ (có thể xem cụ thể ở chương 1) D+ := {s∗ ∈ Rm| 〈s∗, s〉 ≥ 0, ∀s ∈ D}. Định nghĩa 4.4.1 [11, Định nghĩa 3.1](Farkas–Minkowski constraint qualification, viết tắt (FMCQ)) Ta nói bài toán (CCP) thỏa (FMCQ), nếu nón K := cone[ ⋃ λ∈D+ epi(λh)∗] + epi δ∗C . (4.39) là đóng trong Rn × R. Định nghĩa 4.4.2 (Closedness conditions constraint qualification, viết tắt (CCCQ)) Ta nói bài toán (CCP) thỏa (CCCQ), nếu epiϑ∗ +K (4.40) là đóng trong Rn × R với K cho bởi (4.39). 94 Nhận xét 4.4.1 [6] Ta đã biết nếu f liên tục tại ít nhất một điểm thuộc A, thì epi(f + δA) ∗ = cl∗(epif ∗ + epiδ∗A) = epif ∗ + epiδ∗A = epif ∗ + cl∗K. Vì thế nếu (FMCQ) thỏa (nghĩa là K đóng), thì (CCCQ) thỏa. Định lý 4.4.1 [9](Điều kiện tối ưu cần và đủ cho bài toán (CCP)) Giả sử bài toán (CCP) thỏa (CCCQ). Thế thì x ∈ A∩ domϑ là một nghiệm (toàn cục) của (CCP) khi và chỉ khi tồn tại λ ∈ D+ sao cho 0 ∈ ∂ϑ(x) + ∂(λg)(x) +NC(x) (4.41) λg(x) = 0. (4.42) (2) Áp dụng vào bài toán hai cấp Xét bài toán (SCBP), và bài toán tương đương (RP) như sau min f(x) sao cho h(x)− α ≤ 0, x ∈ Θ. với α = inf x∈Θ h, giả sử α hữu hạn, nghĩa là α < ∞ Rõ ràng điều kiện chính quy Slater (xem chương 1) không thỏa cho (RP). Bây giờ ta đưa ra điều kiện chính quy khác và thiết lập điều kiện tối ưu cần và đủ cho (RP). Định lý 4.4.2 [11](Điều kiện tối ưu cần và đủ cho (RP)) Giả sử bài toán (RP) thỏa cone [(0, α) + epih∗] + epiδ∗Θ là đóng. Thế thì x ∈ Θ là nghiệm toàn cục của (RP) khi và chỉ khi tồn tại λ ∈ + sao cho 0 ∈ ∂f(x) + λ∂h(x) +NΘ(x) (4.43) λ(h(x− α) = 0. (4.44) Chứng minh Trước tiên ta nhận thấy (RP) là có dạng của (CCP) tương ứng với D = D+ = R+ và C = Θ. Thứ hai, với mỗi u∗ ∈ Rm, (h(.)− α)∗(u∗) = α + h∗(u∗). 95 Suy ra epi(h(.)− α)∗ = (0, α) + epih∗. Vì cone[(0, α) + epih∗] + epi δ∗Θ là đóng, nên (FMCQ) thỏa suy ra (CCCQ) thỏa do f liên tục (xem Nhận xét 4.4.1) Theo Định lý 4.4.1, ta có tồn tại λ ∈ R+ sao cho 0 ∈ ∂f(x) + λ∂[h(.)− α](x) +NΘ(x) (4.45) λ[h(x)− α] = 0. (4.46) Vì ∂[h(.)− α](x) = (x) nên (4.45) suy ra (4.43), còn (4.46) chính là (4.44). Ví dụ 4.4.1 Xét bài toán (CCP) với f(x) = x2+1, Θ =[-1, 1], và h(x) = max{0, x}. Dễ thấy epiδ∗Θ = epi|.|, S = [−1, 0], và α = 0. Bài toán được viết lại min f(x) sao cho h(x) ≤ 0, x ∈ [−1, 1]. (4.47) Để ý là với mỗi u ∈ R, thì h∗(u) = +∞ nếu u > 1 hoặc u < 0;= 0 nếu u ∈ [0, 1]. Ta có epih∗ = {(u, r)|u ∈ [0, 1], r ≥ 0} = [0, 1]× R+, và cone [(0, α) + epih∗] + epi δ∗Θ = R2+ ∪ {(u, r)|u ≤ 0, r ≥ −u}. là tập con đóng trong R2, chứng tỏ bài toán (4.47) thỏa (FMCQ), vì f liên tục nên (CCCQ) cũng thỏa. Do đó x = 0 là nghiệm của bài toán hai cấp. Vì NΘ(0) = {0}, ∂f(0) = {0} và ∂h(0) = [0, 1] nên (4.43), (4.44) thỏa với λ = 0. 96 (3) Bài toán (SCBP) với Θ mở rộng Ta trở lại bài toán (SCBP) trong đó Θ = {x|g1(x) ∈ −D1, x ∈ C}, và ta viết lại một cách đầy đủ, như sau: inf x∈S f(x), (4.48) trong đó S là tập nghiệm của bài toán cấp dưới sau: min h(x) sao cho g(x) ∈ −D1, x ∈ C. (4.49) với các giả thiết là h : Rn → R proper, lsc, lồi; và g1 : Rn → Rm là ánh xạ D1–lồi với D1 là nón lồi đóng trong Rm và C là tập con trong Rn lồi và đóng. Đặt α = inf g1(x)∈−D1,x∈C h(x) < +∞, để đơn giản giả sử α = 0. Thế thì bài toán (4.48) trở thành bài toán tương đương sau: min f(x) sao cho h(x) ≤ 0, g1(x) ∈ −D1, x ∈ C. (4.50) Bây giờ lại đặt D := R+ ×D1, g : Rn → Rm+1, g(x) = (h(x), g1(x)). Bài toán (4.50) có thể viết lại như sau: min f(x) sao cho g(x) ∈ −D, x ∈ C, (4.51) bài toán (4.51) có dạng như (CCP). Áp dụng điều này để phát biểu điều kiện tối ưu cho bài toán (4.48). Định lý 4.4.3 [11, Định lý 3.5](Điều kiện cần và đủ KKT cho bài toán hai cấp (4.48)) Giả sử bài toán tối ưu hai cấp (4.48) có cone epih∗ + ⋃ λ∈D+1 epi (λg1) ∗ + epiδ∗C 97 là đóng. Thế thì x ∈ g−1(−D) ∩C là nghiệm toàn cục của (4.48) nếu và chỉ nếu có r ∈ R+, và λ ∈ D1 sao cho 0 ∈ ∂f(x) + r∂h(x) + ∂(λg1)(x) +NC(x) (4.52) rh(x) = 0 và λg1(x) = 0. (4.53) Chứng minh Ta có D+ = R+ ×D+1 và với bất kì λ˜ = (r, λ) ∈ D+, (λ˜g)(x) = rh(x) + (λg1)(x). Hơn nữa, epi(λ˜g)∗ = cl∗ {epi (rh)∗ + epi (λg1)∗} = epi (rh)∗ + epi (λg1)∗ = r. epih∗ + epi (λg1)∗. Do đó, ⋃ λ˜∈D+ epi (λ˜g)∗ + epi δ∗C = cone epih ∗ + ⋃ λ∈D+1 epi (λg1) ∗ + epiδ∗C . Theo giả thiết của định lý, tập này đóng. Do đó, (FMCQ) thỏa cho bài toán (4.51), vì f liên tục nên (CCCQ) cũng thỏa cho bài toán (4.51). Vì bài toán (4.48) tương đương với bài toán (4.60) theo cách xây dựng phía trên. Áp dụng Định lý 4.4.1, x ∈ A là nghiệm tối ưu của (4.48) nếu và chỉ nếu tồn tại λ = (r, ) ∈ D+ sao cho 0 ∈ ∂f(x) + ∂(λ˜g)(x) +NC(x), (4.54) (λ˜g)(x) = 0. (4.55) Rõ ràng ∂(λ˜g)(x) = r∂h(x) + ∂(λg1)(x), thay vào (4.54) ta được (4.52) Mặt khác, (λ˜g)(x) = r∂h(x) + λg1(x) = 0, nên với λ ≥ 0, h(x) ≤ 0, λg1(x) ≤ 0, ta có ngay rh(x) = λg1(x) = 0, suy ra (4.52). ¤ M 98 Kết luận Luận văn được trình bày một cách chuyên sâu từ bài toán tối ưu hai cấp hữu hạn đến bài toán tối ưu hai cấp vô hạn với 4 hướng tiếp cận khác nhau. Trong bài toán hai cấp hữu hạn, chúng tôi đã xét 4 lớp bài toán khác nhau, đó là bài toán trơn, bài toán lồi, tuyến tính, bài toán Lipschitz. Còn bài toán hai cấp vô hạn, chúng tôi đã xét bài toán lồi (hoàn toàn) với mọi hàm đều lồi, nửa liên tục dưới . Bằng các yếu tố, gồm công cụ giải tích Clarke hay công cụ giải tích của Mordukhovich, các giả thiết về hàm lồi, trơn, Lipschitz cùng với các điều kiện định tính ràng buộc chính quy; chúng ta đã thiết lập được các điều kiện tối ưu cho các lớp bài toán tối ưu hai cấp tương ứng. Các điều kiện chủ yếu là điều kiện cần, và ta cũng chỉ ra được điều kiện đủ cho lớp bài toán hai cấp đơn giản ở mục cuối chương 4. Thực chất hai loại bài toán vô hạn và hữu hạn cũng cho thấy có sự liên quan với nhau. Tất cả chúng đều nói về nghiệm tối ưu địa phương optimistic. Điều thứ hai của tính liên quan đó là, các kết quả về điều kiện cần cho lớp các bài toán hai cấp vô hạn thực ra là sự mở rộng của lớp các bài toán hữu hạn, ngay sau sự ra đời của lý thuyết vi phân mở rộng vô hạn chiều của Mordukhovich. (xem [17, 18] (năm 2006) để thấy rõ ràng hơn về điều này). Một lưu ý đó là không phải bài toán vô hạn là tổng quát của bài toán hữu hạn, chỉ trừ một vài lớp bài toán đặc biệt và phải thỏa những điều kiện đặc biệt như đã nêu. Ở đây mỗi loại bài toán đều đưa ra một cách đa dạng các phương pháp và kỹ thuật xây dựng bài toán, các giả thiết, ràng buộc cũng như cách thiết lập các điều kiện tối ưu sử dụng tốt nhất các giả thiết đó. Lý thuyết vi phân vô hạn của Mordukhovich đang tiếp tục phát triển, do đó các vấn đề trong luận văn còn có thể tiếp tục phát triển nữa. Chúng ta có 3 vấn đề còn tồn tại, thứ nhất là làm sao để thiết lập được nhiều 99 điều kiện đủ hơn cho mỗi lớp bài toán. Thứ hai là hãy đề xuất những công cụ giải tích mạnh và phát triển yếu tố nghiệm tối ưu pessimistic thay vì chỉ nghiên cứu về nghiệm tối ưu optimistic. Vấn đề cuối cùng là mở rộng và liên hệ đến các lớp bài toán có liên quan đến bài toán hai cấp, chẳng hạn như bài toán tối ưu đa mục tiêu và bài toán có nhiều ứng dụng quan trọng thực tiễn: (MPECs) (xem cụ thể trong [15]). Luận văn đã trình bày tổng quan nội dung chủ yếu về đề tài được đưa ra ở những kết quả gần đây, tuy nhiên chưa đưa ra được cái mới của tác giả. Chúng tôi rất mong sẽ được tiếp tục nghiên cứu những vấn đề có liên quan trong thời gian tới. Dù đã có nhiều cố gắng nhưng luận văn sẽ không thể tránh khỏi những thiếu sót. Vì vậy tôi rất mong nhận sự góp ý của quý Thầy, Cô cùng các bạn để luận văn được hoàn thiện hơn. ¥ 100 Tài liệu tham khảo [1] Nguyễn Định, Quy hoạch lồi. Đại học khoa học tự nhiên thành phố Hồ Chí Minh, 2006. [2] Nguyễn Đông Yên, Giáo trình Giải tích đa trị. Nhà xuất bản khoa học tự nhiên và công nghệ, Hà Nội, 2007. [3] Burachik, R.S., Jeyakumar V.: A dual condition for the convex subdifferential sum formula with applications. J. Convex Anal. 12, 279–290 (2005) [4] Clarke, F.H.: A new approach to Lagrange multipliers. Mathematics of Opera- tions Research, 1: 165–174 (1976) [5] Clarke, F.H.: Optimization and Nonsmooth Analysis. Wiley-Interscience, New York, 1983. [6] Dinh, N., Goberna, M.A., López, M.A., Son, T.Q.: New Farkas-type results with applications to convex infinite programming. ESAIM: Control Optim. Cal. Var. 13, 580–597 (2007) [7] Dinh, N., Nghia, T.T.A., Mordukhovich, B.S.: Subdifferentials of value func- tions and optimality conditions for some classes of DC and bilevel infinite and semi-infinite programs. Research Report ] 4, Department of Mathematics, Wayne State University, Detroit, Michigan (2008). To appear inMath. Program. (2008) 101 [8] Dinh, N., Nghia, T.T.A., Mordukhovich, B.S.: Qualification and optimality conditions for DC programs with infinte constraints. To appear in Acta Math- ematica Vietnamica (2009) [9] Dinh, N., Nghia, T.T.A., Vallet., G.: A closedness condition and its applications to DC programs with convex constraints. To appear in Optimization. (2009) [10] S. Dempe, Foundations of Bilevel Programming, Kluwer Academic Publishers, Dordretch, 2002. [11] Dempe., S., Dinh., N., Dutta., J.: Optimality conditions for a simple convex bilevel programming problem, 1–10 (2009) [12] Dempe., S., Dutta., J., Mordukhovich., B.S.: New necessary optimality condi- tions in optimistic bilevel programming, 1–30 (2006) [13] Dempe., S., Kalashnikov., V.V., Kalashnykova., N.: Optimality conditions for bilevel programming problems. Optimization with Multivalued Mappings: The- ory, Applications and Algorithms, 1–6 (2006) [14] Dutta., J., Dempe., S.: Bilevel programming with convex lower level problems. Optimization with Multivalued Mappings: Theory, Applications and Algorithms, 51–63 (2006) [15] Luo., Z.Q., Pang., J. S., Ralph., D.: Mathematical Programs with Equilibrium Constraints. Cambridge University Press, Cambridge, 1996. [16] Mangasarian., O. L.: Nonlinear Programming. SIAM. Philadelphia, PA, 1994. [17] Mordukhovich., B.S.: Variational analysis and Gerneralized Differentiation, I: Basic Theory. Springer-Verlag, Berlin, 2006. [18] Mordukhovich., B.S.: Variational analysis and Gerneralized Differentiation, II: Applications. Springer-Verlag, Berlin, 2006. 102 [19] Mordukhovich., B. S., Nam., N.M.: Variational stability and marginal functions via gerneralized differentiation. Math. oper. Res. 30, 800–816 (2005) [20] Mordukhovich., B. S., Nam., N.M., Yen. N.D.: Subgradients of marginal func- tions in parametric mathematical programming. To appear in Math. Prog., (2007) [21] Rockafellar., R.T.: Convex Analysis. Princeton University Press, Princeton, New Jork, 1970. [22] Ye., J.J.: Constraint qualifications and KKT conditions for bilevel programming problems. Optimization 31, 811–824 (2006) [23] Ye., J.J., Zhu., D. L.: Optimality conditions for bilevel programming problems. Optimization 33, 9–27 (1995) 103