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

ĐIỀU KIỆN TỐI ƯU CHO MỘT SỐ LỚP BÀI TOÁN TỐI ƯU HAI CẤP NGUYỄN LÊ DUY (Học viên Cao Học khóa 16) NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS. TS. NGUYỄN ĐỊNH (Trường Đại Học Quốc Tế TP. HCM) TP.Hồ Chí Minh - Năm 2009 Lời cảm ơn Lời đầu tiên, tôi xin chân thành cảm ơn sâu sắc tới PGS. TS. NGUYỄN ĐỊNH, người Thầy đã tận tình chỉ dẫn và truyền đạt kiến thức trong quá trình học tập và luôn động viên để tôi hoàn thành luận văn này. Tôi cũng xin bày tỏ lời cảm ơn tới tất cả các Thầy cô của Khoa Toán-Tin trường Đại Học Khoa Học Tự Nhiên Tp.HCM đã giảng dạy tôi trong suốt quá trình học tập tại trường. Tôi xin cảm ơn gia đình đã tạo điều kiện tốt cho việc học của tôi và bạn bè đã hỗ trợ trong việc hoàn thành luận văn này. Tp. Hồ Chí Minh, tháng 9 năm 2009 Nguyễn Lê Duy 1 Lời nói đầu Bài toán tối ưu hai cấp (Bilevel Optimization Problem) lần đầu tiên được H.V.Stackelberg nghiên cứu vào năm 1934. Sau đó nó chính thức được giới thiệu trong cộng đồng tối ưu vào thập kỷ 70 của thế kỷ thứ 20. Bài toán phát triển rất nhanh chóng cả trong lý thuyết và ứng dụng thực tế. Các nhà toán học, nhà kinh tế học và những kỹ sư đã và đang không ngừng phát triển vấn đề này cùng với đó là số lượng các bài báo, tạp chí khoa học, ứng dụng trong kinh tế kỹ thuật xuất hiện ngày càng nhiều hơn. Bài toán tối ưu hai cấp là một bài toán tối ưu có cấp bậc trong đó một phần các ràng buộc của bài toán - được gọi là bài toán cấp trên (upper level problem) là tập nghiệm tối ưu của một bài toán tối ưu thứ hai - được gọi là bài toán cấp dưới (lower level problem). Do đó bài toán này là một bài toán rất phức tạp. Tuy nhiên trong thực tế có rất nhiều bài toán có mô hình toán học là bài toán tối ưu hai cấp. Hơn nữa bài toán tối ưu hai cấp có mối liên hệ chặt chẽ với những bài toán quan trọng khác, một trong số đó là bài toán MPECs (Mathematical Programs with Equilibrium Constraints) - là bài toán mở rộng của bài toán đó, cũng có ứng dụng rộng rãi trong giao thông, điều khiển robot, hệ thống mạng,. . . Đối với bài toán tối ưu hai cấp, các nhà toán học nghiên cứu nhiều vấn đề: sự tồn tại nghiệm, điều kiện tối ưu, các thuật toán,. . .Một vấn đề lớn trong việc nghiên cứu bài toán này là điều kiện tối ưu của nó. Luận văn này trình bày một cách tổng quan điều kiện tối ưu cho một số lớp bài toán tối ưu hai cấp quan trọng, bao gồm lớp bài toán trơn, lớp bài toán lồi và tuyến tính, lớp bài toán lipschitz. Cấu trúc chính của luận văn bao gồm bốn chương. Chương 1 trình bày các kiến thức cơ bản sẽ sử dụng cho các chương sau. Chương 2 giới thiệu bài toán tối ưu hai cấp tổng quát và các mô hình các bài toán thực tế. Phần chính là điều kiện cần tối ưu sẽ trình bày ở chương 3 và chương 4 trong đó đề cập đến các lớp bài toán tối ưu hai cấp hữu hạn và bài toán tối ưu hai cấp vô hạn. 2 Mục lục Lời cảm ơn 1 Lời nói đầu 2 1 Một số kiến thức cơ bản 5 1.1 Một số kiến thức cơ bản về giải tích lồi . . . . . . . . . . . . . . . . . 5 1.2 Hàm Lipschitz và dưới vi phân Clarke . . . . . . . . . . . . . . . . . . 11 1.3 Một số kiến thức cơ bản về giải tích đa trị . . . . . . . . . . . . . . . 12 1.4 Dưới vi phân, nón pháp tuyến và đối đạo hàm Mordukhovich . . . . . 16 2 Khái niệm về bài toán tối ưu hai cấp tổng quát 22 2.1 Giới thiệu bài toán . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.2 Mô hình các bài toán thực tế . . . . . . . . . . . . . . . . . . . . . . 27 3 Điều kiện tối ưu cho bài toán hai cấp hữu hạn 33 3.1 Điều kiện tối ưu khi bài toán cấp dưới lồi . . . . . . . . . . . . . . . . 34 3.2 Điều kiện tối ưu sử dụng dưới vi phân Mordukhovich . . . . . . . . . 49 3.3 Điều kiện tối ưu sử dụng dưới vi phân Clarke . . . . . . . . . . . . . 62 4 Điều kiện tối ưu cho bài toán hai cấp vô hạn 80 4.1 Bài toán hai cấp vô hạn . . . . . . . . . . . . . . . . . . . . . . . . . 80 4.2 Điều kiện tối ưu cho bài toán DC vô hạn . . . . . . . . . . . . . . . . 81 4.3 Điều kiện tối ưu cho bài toán hai cấp vô hạn . . . . . . . . . . . . . . 87 3 4.4 Điều kiện cần và đủ cho bài toán hai cấp lồi đơn giản . . . . . . . . . 93 Kết luận 99 Tài liệu tham khảo 101 4 Chương 1 Một số kiến thức cơ bản 1.1 Một số kiến thức cơ bản về giải tích lồi (1) Tập lồi và hàm lồi Giả sử X là không gian vectơ. Định nghĩa 1.1.1 [1] Tập K ⊆ X là lồi nếu ∀x, y ∈ K, ∀λ ∈ [0, 1], λx+ (1− λ)y ∈ K. Với K 6= ∅, bao lồi của K, ký hiệu là co(K), là tập tất cả các tổ hợp lồi hữu hạn của K, tức là co(K) := { ∑ i∈I αixi|αi ≥ 0, xi ∈ S, ∀i ∈ I; ∑ i∈I αi = 1, | I |< ∞}. Như vậy, bao lồi của K là tập lồi nhỏ nhất chứa K. Định nghĩa 1.1.2 [1] Cho hàm số f : X → R. Khi đó f được gọi là hàm lồi nếu ∀x, y ∈ X, ∀λ ∈ [0, 1], λf(x) + (1− λ)f(y) ≥ 0. Cho X, Y là các không gian vectơ. S là nón lồi trong Y . Định nghĩa 1.1.3 [1] Cho hàm số f : X → Y . Khi đó f được gọi là hàm S–lồi nếu 5 ∀x, y ∈ X, ∀λ ∈ [0, 1], λf(x) + (1− λ)f(y)− f(λx+ (1− λ)y) ∈ S. Nhận xét 1.1.1 Trường hợp f lồi là một trường hợp đặc biệt của hàm S–lồi khi S = R+. (2) Dưới vi phân của hàm lồi, đối ngẫu của hàm lồi (a) Dưới vi phân của hàm lồi Cho f là hàm số lồi, một hàm số lồi thì có thể không có đạo hàm do đó ta xét tới khái niệm sau. Chúng ta cần nêu ra vài khái niệm cơ bản: Hàm số thực mở rộng f : X → R trong đó trong đó R = R⋃{+∞;−∞} Miền hữu hiệu (domain) domf := {x ∈ X|f(x) < ∞} và đồ thị trên (epigraph) epif := {(x, α) ∈ X × R|f(x) ≤ α}. Định nghĩa 1.1.4 [1] Cho hàm số f : X → R lồi, và X∗ là không gian đối ngẫu của không gian vectơ X. Giả sử xo ∈ X và f(xo) 6= ±∞. Khi đó dưới vi phân của hàm lồi f tại xo được xác định như sau ∂f(xo) := {x∗ ∈ X∗ : 〈x∗, x− xo〉 ≤ f(x)− f(xo),∀x ∈ X}. (1.1) Nếu f không hữu hạn tại x thì ∂f(xo) = ∅. Mỗi thành phần x∗ ∈ ∂f(xo) được gọi là dưới gradient của dưới vi phân ∂f(xo), khi đó ∂f(xo) còn gọi là tập các dưới gradient. Đây là định nghĩa dưới vi phân cổ điển của hàm số f . Các phần sau ta sẽ nêu các định nghĩa dưới vi phân mở rộng. (b) Đối ngẫu của hàm lồi Cho X là không gian Banach và hàm f : X → R lồi, luôn luôn proper nghĩa là f(x) 6= ∞ trên X. Gọi X∗ là không gian đối ngẫu của X. 6 Định nghĩa 1.1.5 [1] Hàm đối ngẫu f ∗ : X∗ → R của f , được xác định như sau: f ∗(x∗) := sup{〈x∗, x〉 − f(x)|x ∈ X}. Nhận xét 1.1.2 Do f(x) 6= +∞(x ∈ domf) suy ra sup {〈x∗, x〉 − f(x)|x ∈ X} luôn 6= ∅ nên f ∗(x∗) cũng = sup {〈x∗, x〉 − f(x)|x ∈ domf}. Cho hàm f : X → R lồi, là proper nếu f(x) 6= ∞ trên X. Nhắc lại hàm đối ngẫu f ∗ : X∗ → R đối với f , xác định bởi f∗(x∗) := sup {〈x∗, x〉 − f(x)|x ∈ X = sup {〈x∗, x〉 − f(x)|x ∈ domf}. Cho hàm f : X → R lồi tại x ∈ domf và ε > 0 bất kì, thì dưới vi phân xấp xỉ của hàm f là ∂εf(x) := {x∗ ∈ X∗| 〈x∗, x− x〉 ≤ f(x)− f(x) + ε ∀x ∈ X}, ε ≥ 0 Nếu ε = 0 thì ta có ∂εf(x) = ∂of(x) là dưới vi phân cổ điển có dạng như (1.1). (3) Bài toán quy hoạch lồi và điều kiện tối ưu (a) Bài toán quy hoạch lồi đơn giản Xét bài toán (P) :  inff(x) gi(x) ≤ 0 i = 1,. . . , n x ∈ C trong đó X là không gian định chuẩn, C là tập lồi đóng trong X, f : X → R là hàm lồi, gi : X → R là hàm lồi liên tục. Một bài toán tối ưu có dạng như bài toán (P) ở trên được gọi là bài toán quy hoạch lồi đơn giản. Sau đây ta sẽ xét các điều kiện tối ưu phổ biến của bài toán này. Điều kiện tối ưu, nói đầy đủ là điều kiện tối ưu cho một số lớp bài toán tối ưu có nghiệm (nghiệm địa phương hay toàn cục). Thông thường người ta tìm được điều kiện cần, còn điều kiện đủ thì khó khăn hơn. Các dạng điều kiện phổ biến là điều kiện tối ưu dạng Fritz John và điều kiện tối ưu dạng KKT (Karush–Kuhn- Tucker). Sau đây chúng tôi xin nêu một kết quả về điều kiện tối ưu cho bài toán này. Phần chứng minh sẽ được làm rõ trong phần bài toán quy hoạch lồi tổng quát ngay sau đây. Hai điều kiện chính quy sau đây xem trong [1]. 7 Định nghĩa 1.1.6 (Điều kiện chính quy Slater) (Slater) ∃ x ∈ C, gi(x) < 0, i = 1, . . . , n và f liên tục tại x. Định lý 1.1.1 [1] (Điều kiện cần và đủ dạng KKT) Giả sử f, gi, i = 1, . . . , n và C thỏa mãn giả thiết của bài toán (P). Giả sử (Slater) thỏa mãn. Khi đó a ∈ C là nghiệm cực tiểu toàn cục của (P) khi và chỉ khi ∃(λ1, . . . , λn) ∈ Rn+ sao cho  0 ∈ ∂f(a) + ∑n i=1 λi∂gi(a) + NC(a) λigi(a) = 0∀i = 1, . . . , n trong đó ∂f(x) kí hiệu cho dưới vi phân của hàm số f tại điểm x. (b) Bài toán quy hoạch lồi tổng quát Một bài toán tối ưu có dạng như bài toán sau đây được gọi là bài toán quy hoạch lồi tổng quát (Ptq) :  inff(x) g(x) ∈ −S x ∈ C với giả thiết cơ bản (GTCB) sau: X,Y là các không gian định chuẩn thực, C là một tập lồi khác rỗng của X, f : X → R là hàm lồi liên tục, S là nón lồi đóng trong Y và g : X → Y là hàm S–lồi và liên tục. Mô hình bài toán này là khá tổng quát, rõ ràng khi S = Rn+ thì đó là bài toán ta xét ở đầu mục, ngoài ra nó còn bao quát hai dạng bài toán sau: (U) :  inff(x) gi(x) ≤ 0 i = 1,. . . , n A1x = b1 x ∈ C 8 trong đó A1 ∈ L(X,Rm) và b1 ∈ Rm. Một bài toán thứ hai cũng tương tự như bài toán (U), chỉ thay A1x = b1 bởi A2x = b2, và thay i ∈ {1, . . . , n} bởi i ∈ I trong đó I là tập chỉ số tùy ý, A2 ∈ L(X,Y2) với Y2 là không gian định chuẩn và b2 ∈ Y2. Ta có thể chuyển hai bài toán này về bài toán lồi tổng quát dễ dàng. Bây giờ, gọi A = {x ∈ X|x ∈ C, g(x) ∈ −S} là tập các điểm chấp nhận được của (P), rõ ràng tập A là lồi đóng trong X. Định nghĩa 1.1.7 [1] Nón đối ngẫu dương của nón lồi S, ký hiệu S+, được xác định: S+ = {y∗ ∈ Y | ≥ 0,∀s ∈ S} Định lý 1.1.2 ([1], Điều kiện cần tối ưu Fritz–John) Xét bài toán (Ptq) và các (GTCB) thỏa mãn và intS 6= ∅ và a ∈ A. Khi đó nếu a là nghiệm của (P) thì ∃λo ∈ R+, λ ∈ S+ không đồng thời bằng 0 sao cho: 0 ∈ λo∂f(a) + ∂(λg)(a) + NC(a)λg(a) = 0 trong đó ∂f(x) ký hiệu cho dưới vi phân của hàm số f tại điểm x. Chứng minh. Vì a ∈ A là nghiệm của (Ptq) nên hệ sau vô nghiệm theo x ∈ C : −(f(x)− f(a)) ∈ intR+, g(x) ∈ −S, x ∈ C Do vậy hệ sau vô nghiệm −(f(x)− f(a), g(x)) ∈ int(R+ × S), x ∈ C, nghĩa là tồn tại λ = (λo, λ) ∈ (R+ × S)+ với λ 6= (0, 0) sao cho λ(f(x)− f(a), g(x)) = λ0(f(x)− f(a)) + λg(x) ≥ 0,∀x ∈ C hay λof(x) − λ0f(a) + λg(x) ≥ 0,∀x ∈ C(1), cho x = a ta được λg(x) ≥ 0. Mặt khác ta có λg(x) ≤ 0 (do λ ∈ S+, g(a) ∈ −S), suy ra λg(x) = 0(2). Từ (1) và (2) ta có: λof(x)+λg(x) ≥ λof(a)+λg(a),∀x ∈ C. Do vậy a là nghiệm của bài toán lồi sau đây: 9 inf(λof(x) + λg(x)). Vì λ0f và λg liên tục nên từ đây suy ra 0 ∈ ∂(λof + λg)(a) +NC(a), Cũng vì λ0f và λg liên tục nên suy ra 0 ∈ ∂(λof)(a) + ∂(λg)(a) +NC(a). Vậy định lý được chứng minh. ¤ Chú ý : Nếu λ0 = 0 thì điều kiện sẽ không chứa thông tin gì về hàm mục tiêu f và do đó sẽ không có giá trị gì. Do đó việc khẳng định λ0 6= 0 là hết sức quan trọng. Các điều kiện đặt trên các biểu thức sao cho λo 6= 0 và có thể chọn λo = 1. Một trong các điều kiện quan trọng là điều kiện chính quy Slater (mở rộng) và điều kiện chính quy Kartin: Định nghĩa 1.1.8 Điều kiện chính quy Slater mở rộng (SCQ): ∃ x ∈ C sao cho −g(x) ∈ intS Điều kiện chính quy Kartin (KCQ): @ λ ∈ S+ và λ 6= 0 sao cho λg(x) ≥ 0,∀x ∈ C. Định lý 1.1.3 ([1], Điều kiện cần và đủ KKT) Giả sử các giả thiết như trên Định lý 1.3.2 và thêm (KCQ) thỏa mãn. Khi đó ta có kết luận như trên với λo = 1 nghĩa là a là nghiệm của (Ptq) khi và chỉ khi tồn tại λ ∈ S+ sao cho hệ sau thỏa: 0 ∈ ∂f(a) + ∂(λg)(a) + NC(a)λg(a) = 0 Chứng minh. Dựa trên Định lý 1.1.2 a) Điều kiện cần Theo Định lý 1.1.2, nếu a là nghiệm của bài toán thì tồn tại λ 6= 0 và λ ∈ R+×S+ sao cho  0 ∈ λo∂f(a) + ∂(λg)(a) + NC(a)λg(a) = 0 Giả sử λo = 0. Khi đó ta có 0 ∈ ∂(λg)(a) +NC(a) Do đó tồn tại x∗ ∈ ∂(λg)(a) sao cho −x∗ ∈ NC(a) hay x∗(x− a) ≥ 0,∀x ∈ C. Vậy (λg)(x)− (λg)(a) ≥ x∗(x− a) ≥ 0 10 kết hợp (λg)(a) = 0 suy ra (λg)(x) ≥ 0 mâu thuẫn với (KCQ). Vậy λ0 6= 0 do đó có thể lấy λ0 = 1, nghĩa là ta có hệ cần chứng minh. b) Điều kiện đủ Giả sử có λ ∈ S+ sao cho 0 ∈ ∂f(a) + ∂(λg)(a) + NC(a)λg(a) = 0 hay 0 ∈ ∂(f + λg)(a) +NC(a) điều này tương đương f(x) + (λg)(x) ≥ f(a) + λg(a) = f(a) (do λg(a) = 0), ∀x ∈ C. Mặt khác do x ∈ C, g(x) ∈ −S nên λg(x) ≤ 0 , suy ra f(x) ≥ f(a),∀x ∈ A nghĩa là x = a là nghiệm của bài toán. ¤ Các khái niệm thuộc lý thuyết vi phân được đề xuất bởi Clarke vào năm 1973. Năm 1983 lý thuyết này được Clarke bổ sung và hoàn chỉnh. Ở đây ta chỉ nêu một phần rất nhỏ của lý thuyết này, về hàm Lipschitz địa phương, đạo hàm theo hướng Clarke và dưới vi phân Clarke. 1.2 Hàm Lipschitz và dưới vi phân Clarke Cho hàm số thực f : Rn → R, và x ∈ Rn. Định nghĩa 1.2.1 [5] (Hàm Lipschitz địa phương) Hàm f được gọi là Lipschitz địa phương tại x, nếu tồn tại hằng số k và ε > 0 sao cho |f(x1)− f(x2)| ≤ k|x1 − x2| ∀x1, x2 ∈ x+ εB (1.2) với B là quả cầu đơn vị trong Rn. 11 Định nghĩa 1.2.2 [5] (Đạo hàm theo hướng của hàm Lipschitz địa phương) Cho f Lipschitz địa phương tại x, và v là vecto bất kì trong Rn. Khi đó đạo hàm theo hướng v của hàm f tại x, kí hiệu f o(x; v) xác định như sau: f o(x; v) := lim sup x′→x, t↓0 f(x′ + tv)− f(x′) t Định nghĩa 1.2.3 [5](Dưới vi phân Clarke) Dưới vi phân Clarke của hàm f tại x, kí hiệu ∂of(x) xác định như sau: ∂of(x) := {ξ ∈ Rn|f o(x; v) ≥ 〈v, ξ〉, ∀v ∈ Rn}. (1.3) Mỗi phần tử ξ ∈ ∂of(x) được gọi là dưới gradient Clarke. Tính chất [5] • Khi f trơn (nghĩa là khả vi chặt hay khả vi liên tục) thì ∂of(x) ≡ {∇f(x)} • Khi f lồi thì ∂of(x) ≡ {ξ|f(x + u) − f(x) ≥ 〈u, ξ〉}, ∀u ∈ Rn (tập dưới vi phân của hàm f tại x, (xem mục 1.1)). 1.3 Một số kiến thức cơ bản về giải tích đa trị (1) Ánh xạ đa trị Cho X, Y là hai tập bất kì. Cho F : X ⇒ Y là ánh xạ từ tập X vào toàn bộ các tập con của Y (được kí hiệu là 2Y ). Ta nói F là ánh xạ đa trị từ X vào Y. Như vậy với mỗi x ∈ X, F (x) là một tập con của Y (F (x) có thể = ∅). Nếu với mỗi x ∈ X, tập F (x) chỉ gồm đúng một phần tử của Y , thì F là ánh xạ đơn trị từ X vào Y và thay cho kí hiệu F : X ⇒ Y thì ta sử dụng kí hiệu quen thuộc là F : X → Y . Định nghĩa 1.3.1 [2, Định nghĩa 1.1.1] Đồ thị và miền hữu hiệu của ánh xạ đa trị F : X ⇒ Y tương ứng được xác định như sau: gphF = {(x, y) ∈ X × Y |y ∈ F (x)}, (1.4) domF = {x ∈ X|F (x) 6= ∅}. (1.5) 12 Nhắc lại, nếu ánh xạ đơn trị, là hàm thực mở rộng f : X → R thì miền hữu hiệu domf := {x ∈ X|f(x) < ∞} và đồ thị trên (epigraph) epif := {(x, α) ∈ X × R|f(x) ≤ α}. Định nghĩa 1.3.2 [21, Định lý 19.1] Tập M ⊂ Rn được gọi là tập lồi đa diện (polyhedral convex set) nếu M có thể biểu diễn được dưới dạng giao của một số hữu hạn nửa không gian đóng của Rn, nghĩa là tồn tại các điểm a1, . . . , ap ∈ M và các phương v1, . . . , q ∈ Rn sao cho M = { p∑ i=1 tia i + n∑ j=1 λjv j : ti ≥ 0 ∀i = 1, . . . , p, p∑ i=1 ti = 1, λj ≥ 0 ∀j = 1, . . . , n.} Bây giờ giả sử X, Y là các không gian metric. Định nghĩa 1.3.3 [2, Định nghĩa 1.2.1; 1.2.2; 1.2.3] Ta nói F là nửa liên tục trên (usc) tại x ∈ domF nếu với mọi tập mở V ⊂ Y thỏa F (x) ⊂ V tồn tại lân cận mở U của x sao cho F (x) ⊂ V ∀x ∈ U. Nếu F usc tại mọi điểm thuộc domF thì F được gọi là usc trong X Ta nói F là nửa liên tục dưới (lsc) tại x ∈ domF nếu với mọi tập mở V ⊂ Y thỏa F (x) ∩ V 6= ∅ tồn tại lân cận mở U của x sao cho F (x) ∩ V 6= ∅ ∀x ∈ U ∩ domF. Nếu F lsc tại mọi điểm thuộc domF thì F được gọi là lsc trong X Ta nói F là liên tục tại x ∈ domF nếu F đồng thời usc và lsc tại x. Nếu F liên tục tại mọi điểm thuộc domF thì F được gọi là liên tục trên X. Xét hàm thực mở rộng f : X → R với X là không gian metric. Định nghĩa 1.3.4 [2] Ta nói f là usc tại x ∈ dom f nếu lim inf x→x f(x) ≥ f(x) 13 trong đó lim inf x→x f(x) := inf{β ∈ R|∃xk → x, lim k→∞ f(xk) = β}. Ta nói f là lsc tại x ∈ dom f nếu lim sup x→x f(x) ≤ f(x) trong đó lim sup x→x f(x) := sup{β ∈ R|∃xk → x, lim k→∞ f(xk) = β}. (2) Tính chất của đồ thị trên và dưới vi phân đối với hàm thực mở rộng Xét hàm thực mở rộng f : X → R trong đó X là không gian Banach tùy ý. Theo [3], ta có epif ∗ = ⋃ ε≥0 { (x∗, 〈x∗, x〉+ ε− f(x))|x∗ ∈ ∂εf(x)}. Trong [3], ta cũng có epi(f1 + f2) ∗ = cl∗(epif ∗1 + epif ∗ 2 ) thỏa mãn với mọi hàm lsc và lồi fi : X → R, i = 1, 2, trong đó cl∗ có thể bỏ đi nếu fi liên tục tại điểm x ∈ domf1 ∩ domf2. Hơn nữa chúng ta còn có công thức tổng các dưới vi phân được thiết lập trong [3]. Bổ đề sau đây miêu tả hai yếu tố này: Bổ đề 1.3.1 [7, 9](Công thức tổng epi và tổng dưới vi phân cho hàm lồi) Giả sử fi : X → R, i = 1, 2 là lsc, lồi và domf1∩ domf2 6= ∅. Khi đó hai điều kiện sau tương đương: • (i) Tập epif ∗1 + epif ∗2 đóng yếu∗ trong X∗ × R. 14 • (ii) Công thức sau thỏa epi(f1 + f2) ∗ = (epif ∗1 + epif ∗ 2 ) (1.6) Hơn nữa, ta có ∂(f1 + f2)(x) = ∂f1(x) + ∂f2(x), với x ∈ domf1 ∩ domf2, (1.7) trong đó ∂f(.) là dưới vi phân cổ điển (Định nghĩa 1.1.4). Chứng minh. (xem [9]) Ngay sau sự ra đời của lý thuyết vi phân Clarke, thì năm 1976, Mordukhovich đã đề xuất những khái niệm về lý thuyết vi phân của riêng ông, từ đó đến nay thì ông đã hoàn chỉnh lý thuyết ấy. Thực sự giải tích hiện đại nghiên cứu về các đối tượng không trơn (nonsmooth) như tập, hàm, ánh xạ đa trị và các công cụ giải tích mở rộng của phép tính vi phân. Trong mục này chúng ta sẽ sử dụng các đối tượng đề xuất bởi Mordukhovich, đây là công cụ tính toán mạnh mẽ và đầy đủ, thích hợp để nghiên cứu về bài toán tối ưu hai cấp.Việc xây dựng lý thuyết vi phân vô hạn chiều của ông theo các bước chính: • Định nghĩa khái niệm dưới vi phân của các hàm số nhận giá trị trong tập số thực suy rộng. • Sử dụng dưới vi phân để định nghĩa nón pháp tuyến (không lồi) của các tập hợp. • Sử dụng nón pháp tuyến để định nghĩa đối đạo hàm (coderivative) của ánh xạ đa trị. Sau đây ta xin nêu các khái niệm trong lý thuyết vi phân mở rộng của Mor- dukhovich. Để tìm hiểu cụ thể xin xem trong ([2], chương 1, 4) và [17, 18] (sách mới nhất năm 2006) của Mordukhovich. 15 1.4 Dưới vi phân, nón pháp tuyến và đối đạo hàm Mordukhovich Xét ánh xạ đa trị F : X ⇒ X∗ giữa không gian Banach X và không gian đối ngẫu X∗ của nó. Kí hiệu lim sup x→x F (x) := {x∗ ∈ X∗|∃xk → x, x∗k →w ∗ x∗, x∗k ∈ F (xk) ∀k = 1, 2, . . .}. (1.8) dùng để chỉ giới hạn trên theo dãy theo nghĩa Painlevé-Kuratowski trong tôpô chuẩn của X và tôpô yếu∗ (kí hiệu bằng w∗) của X∗. Cho hàm f : X → R và tập Ω ⊂ X. Các kí hiệu x →f x và x →Ω x tương ứng có nghĩa là x → x với f(x) → f(x) và x → x với x ∈ Ω. Định nghĩa 1.4.1 ([2], Dưới vi phân Fréchet) Cho X là không gian Banach, xét hàm f : X → R là hàm thực suy rộng, hữu hạn tại x. Với mỗi ε ≥ 0, đặt ∂ˆεf(x) := {x∗ ∈ X∗| lim inf x→x f(x)− f(x)− 〈x∗, x− x〉 ||x− x|| ≥ −ε}. (1.9) Tập ∂ˆεf(x) được gọi là ε− dưới vi phân Fréchet của f tại x, còn các phần tử của nó là ε− dưới gradient Fréchet của f tại x. Tập ∂ˆf(x) := ∂ˆof(x) được gọi là dưới vi phân Fréchet của f tại x (rõ ràng ∂ˆf(x) ⊂ ∂ˆεf(x)). Định nghĩa 1.4.2 ([2], Dưới vi phân Mordukhovich) Tập hợp ∂f(x) := lim sup x→fx, ε↓0 ∂ˆεf(x) (1.10) được gọi là dưới vi phân Mordukhovich, trong đó ∂ˆεf(x) là ε− dưới vi phân Fréchet. 16 Ta nhắc lại hai khái niệm khả vi Frechet và khả vi chặt (trơn), (xem [2]). Hàm f được gọi là khả vi Frechet tại x ∈ X nếu tồn tại x∗ ∈ X∗ sao cho lim x→x f(x)− f(x)− 〈x∗, x− x〉 ||x− x|| = 0, khi đó x∗ được gọi là đạo hàm Frechet của f tại x, và dễ thấy {x∗} = ∂ˆf(x). Hàm f được gọi là khả vi chặt tại x ∈ X nếu f khả vi Frechet tại x và lim x→x, u→x f(x)− f(x)− 〈x∗, x− u〉 ||x− u|| = 0. Nếu X là không gian hữu hạn chiều thì hai khái niệm này là như nhau (xem [2], chương 3). Nhận xét 1.4.1 [2, Mệnh đề 4.2.1; 4.2.2] Nếu f khả vi chặt tại x thì tập ∂f(x) chỉ chứa một phần tử đó là đạo hàm hàm chặt của f tại x. Nếu f là hàm lồi thì tập ∂f(x) trùng với dưới vi phân của giải tích lồi (1.1) phần trên. Bây giờ chúng ta tìm hiểu cụ thể các đối tượng nón pháp tuyến và đối đạo hàm. Dựa trên nền tảng các đối tượng giải tích do Mordukhovich đề xuất, ta tách các trường hợp. Mục đích của việc tách là chúng ta xét hàm thực mở rộng trong trường hợp không gian Banach tùy ý và trong không gian hữu hạn, sẽ sử dụng cho bài toán hai cấp vô hạn và bài toán hai cấp hữu hạn (xem cụ thể chương 3 và chương 4 dưới đây). Trường hợp: f : X → R trong đó X là không gian Banach tùy ý. Nhắc lại, hàm chỉ số δ(x; Ω) =  0 nếu x ∈ Ω∞ nếu otherwise trong đó Ω ⊂ X. Bây giờ nhắc lại nón pháp tuyến cổ điển khi tập Ω lồi tại x ∈ Ω, xác định bởi N(x; Ω) := ∂δ(x; Ω) = {x∗ ∈ X∗| 〈x∗, x− x〉 ≤ 0 ∀x ∈ Ω} (1.11) 17 Nón pháp tuyến Fréchet được xác định như sau: Nˆ(x; Ω) := ∂δˆ(x; Ω) = {x∗ ∈ X∗| lim sup x→Ωx 〈x∗, x− x〉 ||x− x|| ≤ 0} (1.12) Và nón pháp tuyến mở rộng Mordukhovich của tập Ω (nói chung là không lồi) tại x ∈ Ω được xác định tương tự N(x; Ω) := ∂δ(x; Ω) = {x∗ ∈ X∗|∃xk →Ω x, εk → 0+ và x∗k →w ∗ x∗ : lim sup x→Ωxk 〈x∗, x− xk〉 ||x− xk|| ≤ εk}. (1.13) Bây giờ chúng ta tìm hiểu khái niệm "Đối đạo hàm": Xét ánh xạ đa trị F : X ⇒ Y giữa các không gian Banach. Định nghĩa 1.4.3 [2, Đối đạo hàm Fréchet, đối đạo hàm Mordukhovich] Đối đạo hàm Fréchet của F tại (x, y) ∈ gphF và đối đạo hàm Mordukhovich tại điểm tương ứng, lần lượt cho bởi Dˆ∗ F (x, y) (y∗) := { x∗ ∈ X∗|(x∗, −y∗) ∈ Nˆ((x, y); gphF ) } , (1.14) D∗ F (x, y) (y∗) := { x∗ ∈ X∗|(x∗, −y∗) ∈ N((x, y); gphF ) } . (1.15) Nếu F (x) = f(x) đơn trị, thì chúng ta viết Dˆ∗ f(x) thay cho Dˆ∗ f(x, f(x)) và viết D∗ f(x) thay cho D∗ f(x, f(x)). Khi đó nếu f tương ứng là khả vi Fréchet và khả vi chặt tại x thì các đối đạo hàm phía trên xác định như sau: Dˆ∗ f(x)(y∗) = (∇f(x))∗(y∗) ∀y∗ ∈ Y ∗ D∗ f(x)(y∗) = (∇f(x))∗(y∗) ∀y∗ ∈ Y ∗ Lúc này, với mọi y∗ ∈ Y ∗, Dˆ∗ f(x)(y∗) và D∗ f(x)(y∗) là các tập chỉ chứa một phần tử. Nếu f khả vi chặt, thì hai tập này bằng nhau D∗ f(x)(y∗) = Dˆ∗ f(x)(y∗) = (∇f(x))∗(y∗) ∀y∗ ∈ Y ∗. 18 Cuối cùng chúng tôi nêu mối quan hệ giữa đối đạo hàm của ánh xạ đơn trị Lipschitz địa phương (xem mục 1.2) f : X → Y với dưới vi phân Fréchet của hàm vô hướng (y∗o f)(x) := 〈y∗, f(x)〉, y∗ ∈ Y ∗ được mô tả bởi công thức sau: Dˆ∗ f(x)(y∗) = ∂ˆ〈y∗, f(x)〉. Trường hợp: f : X → R trong đó X là không gian hữu hạn chiều Giả sử X = Rn, như vậy hàm f trở thành f : Rn → R. Các khái niệm sau xem cụ thể trong ([14], mục 2). Đầu tiên, chúng ta tìm hiểu khái niệm nón pháp tuyến mở rộng của một tập khác rỗng. Cho tập Ω ⊂ Rn và x ∈ Ω ; khi đó nón pháp tuyến của Ω tại x xác định bởi N(x; Ω) := lim sup x→Ωx Nˆ(x; Ω) (1.16) với Nˆ(x; Ω) là nón pháp Fréchet của Ω tại x ∈ Ω, xác định như sau: Nˆ(x; Ω) := {v ∈ Rn| lim sup u→Ωx 〈v, u− x〉 ‖u− x‖ ≤ 0} (1.17) trong đó ” lim sup ” là giới hạn trên theo nghĩa Painlevé-Kuratowski của một ánh xạ đa trị S : Rn ⇒ Rm với u → x xác định bởi lim sup u→x S(u) := {v ∈ Rm|∃uk → u,∃vk → v, vk ∈ S(uk) khi k →∞}. Nón (1.16) thường không lồi (ví dụ lấy Ω = gph |x| tại x = (0, 0) ∈ R2 ), trong khi đó nón pháp Fréchet lồi và là đối ngẫu của nón Contingent (Bouligand) của Ω tại x ∈ Ω. Cho một ánh xạ đa trị S : Rn ⇒ Rm và một điểm (x, y) ∈ gphS với gphS := {(u, v) ∈ Rn × Rm|v ∈ S(u)} Xét ánh xạ đa trị: D∗S(x, y) : Rm → Rn với giá trị D∗S(x, y)(v) := {u ∈ Rm|(u,−v) ∈ N((x, y); gphS)}, v ∈ Rm. 19 Đây chính là ánh xạ đối đạo hàm của S tại (x, y). Nếu S đơn trị và khả vi chặt tại x với gradient ∇S(x) nghĩa là lim x→x,u→x S(u)− S(v)− 〈∇S(x), u− x〉 ‖u− x‖ = 0 (điều này hiển nhiên vì S khả vi liên tục quanh x) , do đó D∗S(x)(v) = {∇S(x)∗v} ∀v ∈ Rn. Công thức này là đạo hàm mở rộng của toán tử đạo hàm liên hợp của ánh xạ đơn trị đối với trường hợp "không trơn". Bây giờ ta xét một số tính chất của hàm Lipschitz, cho hàm ϕ : Rn → R liên tục lipschitz quanh x, có dưới vi phân như sau: ∂ϕ(x) = lim sup x→x ∂ˆϕ(x) (1.18) trong đó ∂ˆϕ(x) là dưới vi phân Fréchet của ϕ tại x. Dưới vi phân (1.18) luôn luôn khác rỗng và compac với mọi hàm Lipschitz địa phương. Rõ ràng nếu các hàm là khả vi chặt thì ∂ϕ(x) = {∇ϕ(x)}. Ngoài ra ∂ϕ(x) = {v ∈ Rn|(v,−1) ∈ N((x, ϕ(x)); epiϕ)} với N(.) xác định như (1.16). Nếu ánh xạ S đơn trị, Lipschitz địa phương thì D∗S(x)(v) = ∂〈v, S〉(x) v ∈ Rm trong đó ∂ϕ(.) xác định như (1.18) và 〈v, S〉(x) = 〈v, S(x)〉 Chúng ta sử dụng tính chất của bao lồi của dưới vi phân co∂(−ϕ)(x) = −co∂ϕ(x) (1.19) Cho ánh xạ đa trị S : Rn ⇒ Rm và một điểm x với S(x) 6= ∅, ta nói rằng S là nửa compac trong (inner semicompact) tại x nếu với mỗi dãy xv → x với S(xv) 6= ∅ thì có một dãy yv ∈ S(xv) chứa một dãy con hội tụ khi v → ∞. Rõ ràng trong không gian hữu hạn chiều thì "inner semicompactness" thỏa khi S là bị chặn đều ("uniformly bounded") quanh x nghĩa là có một lân cận U của x và tập C bị chặn ⊂ Rm sao cho S(x) ⊂ C khi x ∈ U. 20 Tiếp theo ta tìm hiểu một khái niệm khác, cho ánh xạ đa trị S : Rn ⇒ Rm, ta nói S là nửa liên tục trong (inner semicontinuous) tại (x, y) ∈ gphS nếu với bất kì dãy xv → x thì có một dãy yv ∈ S(xv) hội tụ về y khi v →∞. Lưu ý rằng tính nửa liên tục trong của S tại (x, y) có liên quan đến tính Lipschitz– like tại điểm này mà mở rộng tính liên tục Lipschitz địa phương của ánh xạ đa trị trong không gian Hausdorff. Ánh xạ đa trị S : Rn ⇒ Rm thỏa mãn tính chất Lipschitz–like tại điểm (x, y) ∈ gphS nếu có một lân cận U của x, V của y và một hằng số l ≥ 0 sao cho S(x) ∩ V ⊂ S(u) + l‖x− u‖B ∀x, u ∈ U trong đó B là quả cầu đơn vị đóng. Tính chất này được biết là tương đương với tính chính quy metric và tính mở tuyến tính của ánh xạ ngược S−1, có tầm quan trọng trong tối ưu và giải tích phi tuyến. Ngoài ra D∗S(x, y)(0) = {0} cung cấp đặc tính đầy đủ của tính Lipschitz–like của S tại (x, y). M 21 Chương 2 Khái niệm về bài toán tối ưu hai cấp tổng quát Các kiến thức cơ bản trong chương này chúng tôi tham khảo trong [10], và tổng quan từ các bài báo [4, 13]. 2.1 Giới thiệu bài toán (1) Bài toán tổng quát và các lớp bài toán chính Bài toán tối ưu hai cấp tổng quát là một bài toán tối ưu trong đó gồm hai biến x và y với y được chọn là một nghiệm tối ưu của một bài toán thứ hai chứa tham số x. Do đó đây là bài toán có cấp bậc theo ý nghĩa các ràng buộc của bài toán cấp trên (the upper level problem) được xác định bởi một bài toán cấp dưới (the lower level problem). Ta xét dạng của bài toán cấp trên: min x F (x, y) sao cho Gk(x, y) ≤ 0, k ∈ K, x ∈ X, y ∈ Ψ(x), (2.1) trong đó Ψ(x) là tập nghiệm tối ưu của bài toán cấp dưới: min y f(x, y) sao cho gi(x, y) ≤ 0, i ∈ I, hj(x, y) = 0, j ∈ J. (2.2) 22 Thông thường khi nghiên cứu điều kiện tối ưu thì người ta ít xét đến các ràng buộc đẳng thức hj(x, y) = 0 (trong luận văn chúng tôi chỉ trình bày bài toán tối ưu hai cấp bao gồm cả ràng buộc đẳng thức thế này, trong phần đầu của chương 3. Các phần còn lại của chương 3 và toàn bộ chương 4, chúng tôi bỏ đi ràng buộc đẳng thức này). Để hiểu một cách rõ ràng hơn, chúng tôi chia làm 3 lớp bài toán khác nhau. (a) Lớp bài toán tối ưu hai cấp hữu hạn Các hàm thực F,Gk, f, gi, hj đều xác định trên Rn × Rm (Rn × Rm → R). X đóng ⊆ Rn, thông thường X = {x ∈ Rn|G(x) ≤ 0}, G : Rn → R. Ψ là ánh xạ đa trị Rn ⇒ Rm có Ψ(x) là tập nghiệm tối ưu của bài toán cấp dưới, xác định bởi Ψ(x) := argmin y {f(x, y)|gi(x, y) ≤ 0, hj(x, y) = 0} gồm ràng buộc đẳng thức hay Ψ(x) := argmin y {f(x, y)|gi(x, y) ≤ 0} nếu không gồm ràng buộc đẳng thức. Số lượng các ràng buộc hữu hạn, nghĩa là i ∈ I hữu hạn, j ∈ J hữu hạn, k ∈ K hữu hạn. (b) Lớp bài toán tối ưu hai cấp vô hạn Các hàm thực mở rộng F, f : X ×Y → R, với R = R∪{+∞; −∞} trong không gian Banach X, Y tùy ý. Hàm thực mở rộng gt : Rn × Rm → R với t ∈ T , T là tập chỉ số vô hận. (c) Lớp bài toán tối ưu hai cấp nửa vô hạn Tương tự như ở lớp bài toán tối ưu hai cấp vô hạn, nhưng nếu chúng ta xét trong không gian hữu hạn chiều và giữ nguyên các giả thiết còn lại thì nó trở thành lớp bài toán tối ưu hai cấp nửa vô hạn. Trong luận văn chỉ xét hai lớp bài toán (a) và (b). Tùy các tính chất khả vi liên tục, khả vi chặt, hay lồi, lipschitz . . .mà chúng ta có các lớp bài toán được chia nhỏ tương ứng, là bài toán trơn, lồi, lồi hoàn toàn, lipschitz . . . . Vấn đề này sẽ được tìm hiểu cụ thể ở các chương sau. Đặt ϕ(x) := inf y {f(x, y) sao cho g(x, y) ≤ 0, h(x, y) = 0}. thì ϕ được gọi là hàm giá trị tối ưu của bài toán cấp dưới. 23 Bây giờ, để hiểu về quá trình hình thành bài toán, ta hãy đến với mô hình kinh tế, cũng là mô hình xuất hiện đầu tiên như sau. (2) Sự ra đời của bài toán và hai dạng bài toán cơ bản Bài toán hai cấp có cấp bậc theo nghĩa có hai nhân tố quyết định những chọn lựa trên những mức độ khác nhau về cấp bậc. Trong khi nhân tố thứ nhất – thường gọi là người quyết định cấp trên hoặc ông chủ, đưa ra các chọn lựa x (lúc này x cố định) của ông ấy trước, thì nhân tố thứ hai – thường được gọi là người quyết định cấp dưới hoặc người làm công, xác định giải pháp y sau đó của anh ta theo một trong các lựa chọn của ông chủ. Do đó biến x đóng một vai trò là tham số trong (bài toán cần giải quyết) của người làm công. Hơn nữa ông chủ phải lường trước lựa chọn của người làm công, vì doanh thu của công ty không chỉ phụ thuộc sự chọn lựa của ông ta mà còn cả sự tác động trở lại của người làm công. Theo đó, người làm công phải giải quyết bài toán chứa tham số x như sau: min y f(x, y) sao cho g(x, y) ≤ 0, h(x, y) = 0, (2.3) với giả thiết f, gi, hj : Rn × Rm → R, i = 1, . . . , p, j = 1, . . . , q và g(x, y) = (g1(x, y), . . . , gp(x, y)), h(x, y) = (h1(x, y), . . . , hq(x, y)). Đặt Ψ(x) là tập nghiệm tối ưu của bài toán này, Ψ(x) := argmin y {f(x, y)|g(x, y) ≤ 0, h(x, y) = 0} (2.4) Như vậy bài toán của ông chủ có dạng như (2.1), bao gồm cực tiểu hóa hàm F : Rn × Rm → R sao cho y ∈ Ψ(x) và x ∈ X với X tập đóng, X ⊆ Rn, nghĩa là giải quyết bài toán sau: min x F (x, y) sao cho x ∈ X, y ∈ Ψ(x). (2.5) trong đó Ψ(x) xác định như (2.4). Nguyên nhân bởi vì ông chủ điều khiển chỉ mỗi biến x, do đó bài toán hai cấp chỉ 24 được định nghĩa tốt (well-defined) trong trường hợp nghiệm tối ưu của bài toán cấp dưới (2.3) là duy nhất với mọi giá trị x ∈ X. Xét trường hợp thứ nhất: nghiệm tối ưu của bài toán (2.3) xác định duy nhất với mọi giá trị tham số x ∈ X. Định nghĩa 2.1.1 [10], (Nghiệm của bài toán hai cấp) Giả sử Ψ(x) chứa ít nhất 1 điểm với mọi giá trị x ∈ X. Khi đó một điểm (x∗, y∗) ∈ Rn × Rmđược gọi là nghiệm tối ưu địa phương của bài toán (2.5) nếu x∗ ∈ X, y∗ ∈ Ψ(x∗) và tồn tại một lân cận mở Uδ(x ∗), δ > 0 sao cho F (x, y) ≥ F (x∗, y∗) ∀(x, y) thỏa x ∈ Uδ(x∗), y ∈ Ψ(x). Nó được gọi là nghiệm tối ưu toàn cục của bài toán (2.5) nếu δ = ∞. Khái niệm trên mô tả khi nghiệm y = y(x) của người làm công được tiên đoán bởi ông chủ. Do đó ông chủ phải giải bài toán: min x {F (x, y(x))|x ∈ X} Bây giờ ta lấy ví dụ để minh họa cho khó khăn khi nghiệm tối ưu của bài toán cấp dưới (2.3) là không duy nhất. Ví dụ 2.1.1 Xét bài toán tối ưu hai cấp sau: min x {x2+y2|−1 ≤ x ≤ 1, y ∈ Ψ(x)}, trong đó: Ψ(x) = Argmin y {−xy|0 ≤ y ≤ 1} (bài toán cấp dưới). Khi đó, Ψ(x) =  0, nếu x < 0 1, nếu x > 0 [0, 1], nếu x = 0 Do đó F (x, y(x)) :  = x2 nếu x < 0 = 1+ x2 nếu x > 0 ∈ [0, 1] nếu x = 0 Hàm F (x, y(x)) chỉ phụ thuộc biến x. Ta có thể thấy ngay giá trị hàm mục tiêu của bài toán cấp trên là không rõ ràng nếu người làm công không thông tin lựa chọn của anh ta tới ông chủ. Việc giải quyết bài toán the cấp trên của ông chủ phụ thuộc vào tác động trở 25 lại của người làm công: bài toán cấp trên chỉ giải được trong trường hợp khi người làm công chọn y(0) = 0 ∈ Ψ(x). Do vậy giá trị tối ưu 0 của bài toán 2 cấp không bao giờ đạt được nếu người làm công không chọn y(0) = 0. Khái niệm giá trị tối ưu thực chất không rõ ràng ở chỗ: có rất nhiều chọn lựa x làm cho hàm F (x, y(x)) tiến về 0 nhưng có thể không đạt tại giá trị ấy. Ta không có khả năng khắc phục nhược điểm này nếu như người làm công được phép chọn tự do trong khi ông chủ cứ ngồi một vị trí mà theo dõi mọi chọn lựa của anh ta. Người làm công chỉ cần chọn 0.5 ∈ Ψ(0) và thế là bài toán ở ví dụ trên sẽ không có nghiệm. Để cho bài toán 2 cấp vẫn được xác định ta phải xét trường hợp thứ hai: nghiệm của bài toán cấp dưới (2.3) không duy nhất. Chúng ta có hai dạng bài toán phân biệt khắc phục trở ngại này: Bài toán hai cấp dạng optimistic: min x ϕ0(x) sao cho x ∈ X (2.6) khi ϕ0(x) := inf y {F (x, y)|y ∈ Ψ(x)}. (2.7) Bài toán hai cấp dạng pessimistic: min x ϕp(x) sao cho x ∈ X (2.8) khi ϕp(x) := sup y {F (x, y)|y ∈ Ψ(x)}. (2.9) trong đó Ψ(x) xác định theo (2.4). Ý nghĩa của hai bài toán (2.6) và (2.8): Bài toán hai cấp dạng optimistic được áp dụng khi ông chủ tin rằng (hoặc ông ta có khả năng thuyết phục) người làm công sẽ luôn tìm ra giải pháp tối ưu, cũng là lựa chọn tốt nhất từ ông chủ nên bài toán (2.6) còn gọi là bài toán hai cấp lạc quan. Bài toán hai cấp dạng pessimistic được nhắc đến khi người làm công tỏ vẻ không hợp tác với ông chủ do đó bài toán (2.8) còn gọi là bài toán hai cấp bi quan. 26 Chúng ta chỉ tập trung nghiên cứu về bài toán tối ưu hai cấp dạng optimistic trong luận văn này. Ta hãy nêu một số khái niệm cơ bản về nghiệm optimistic, nghĩa là nghiệm cho bài toán dạng optimistic. Ta nhắc lại đối với bài toán hai cấp dạng optimistic thì người làm công phải giải quyết bài toán (2.6). Điều này dẫn tới khái niệm sau Định nghĩa 2.1.2 ([10], Nghiệm tối ưu optimistic) Một điểm (x∗, y∗) ∈ Rn × Rm được gọi là nghiệm tối ưu optimistic địa phương cho bài toán (2.5) nếu x∗ ∈ X, y∗ ∈ Ψ(x∗) sao cho F (x∗, y∗) ≤ F (x∗, y),∀y ∈ Ψ(x∗) và tồn tại một lân cận mở Uδ(x ∗), δ > 0 sao cho ϕ0(x∗) ≤ ϕ0(x) ∀x ∈ X ∩ Uδ(x∗). Nếu δ = ∞ thì (x∗, y∗) gọi là nghiệm optimistic toàn cục của (2.5). 2.2 Mô hình các bài toán thực tế (1) Bài toán Stackelberg (Stackelberg Games) (a) Bài toán kinh tế thị trường (Market economy) Chúng ta chỉ xét trường hợp đơn giản gồm hai thành phần: kẻ bán và người mua. Kẻ bán ra lệnh bán giá sản phẩm và tích trữ sản phẩm của mình, khi anh ta quyết định anh ta phải lường trước sự phản ứng của người mua bởi vì lợi nhuận sinh ra phụ thuộc quyết định cả hai. Rõ ràng mỗi người ở vị trí của mình đều muốn tận dung triệt để lợi thế để sử dụng tốt nhất sự "đầu tư" của mình. Tuy nhiên người bán là người có được sản phẩm nên họ có vị trí độc lập( chỉ quan sát phản ứng bị phụ thuộc của người mua dựa trên quyết định của người này) do vậy anh ta cố gắng đẩy cao lợi nhuận tốt nhất có thể. Bài toán đặt ra được gọi là Stackelberg Game, có mô hình như sau: Lấy X, Y lần lượt là tập chấp nhận được của chiến lược x và y tương ứng của người bán(1), người mua(2). Giả sử giá trị chọn lựa đếm được nghĩa là hàm sử dụng lần lượt của (1), (2) là fL(x, y), fF (x, y). Trước quyết định x của (1) thì (2) phải 27 chọn y(x) sao cho hàm sử dụng tương ứng lớn nhất: y(x) ∈ Ψ(x) := argmax y {fF (x, y)|y ∈ Y }. Nhận thức được điều này, nên (1) giải "Stackelberg game" để đưa ra quyết định của mình : max x {fL(x, y)|x ∈ X, y ∈ Ψ(x)}. Thực ra bài toán tối ưu hai cấp tổng quát hơn " Stackelberg game" ở chỗ các tập chấp nhận được của mỗi người có thể phụ thuộc vào người còn lại. Nếu có thêm nhiều người mua và người bán nữa thì ta cần nghiên cứu bài toán mở rộng sau. (b) Bài toán cân bằng Cournot – Nash (Cournot – Nash Equilibria) Có n người bán và người mua tạo ra n thành phần, sản xuất ra số lượng xi sản phẩm đồng nhất, i = 1, . . . , n. Đặt các hàm hao tổn là f(xi) tất cả đều khả vi, liên tục, lồi, không âm và lợi nhuận tương ứng khi bán ra sản phẩm của họ ra thị trường là xip( ∑n j=1 xj). Ở đây p : R → R là hàm nhu cầu tiêu dùng mô tả sự phụ thuộc của giá cả theo số lượng yêu cầu của sản phẩm đó. Giả sử p là hàm khả vi liên tục, lồi chặt và giảm trên tập R++ := {r|r > 0} và hàm g(x) = xp(x) lõm trên R++. Lấy [ai, bi] ⊂ R++ là tập đóng, bị chặn trong đó thành phần i tin rằng sản phẩm đó đem lại lợi nhuận. Khi đó thành phần thứ i sẽ giải quyết bài toán tìm số lượng sản phẩm tối ưu để lợi nhuận lớn nhất max xi { xip( n∑ j=1 xj)− fi(xi)|xi ∈ Xi } . (2.10) Bây giờ giả sử thành phần thứ nhất có lợi thế so với các thành phần khác theo hướng nó cố định số lượng đã xuất ra x1 trước tiên, và do đó tất cả n − 1 thành phần còn lại có tác động trở lại x1. Khi đó n − 1 thành phần ấy phải tính toán "Nash Equilibrium" giữa nội bộ với nhau bằng cách giải quyết n− 1 bài toán kiểu (2.10). Giả sử "Nash Equilibrium" (x2(x1), . . . , xn(x1)) T xác định duy nhất với x1 cố định. Khi đó thành phần 1 phải giải bài toán sau để cho lợi nhuận lớn nhất: max x1 { x1p( n∑ j=1 xj)− f1(x1)|x1 ∈ X1, xi = xi(x1), i = 1, . . . , n } , 28 Nghĩa là: max x1 x1p( n∑ j=1 xj)− f1(x1) trong đó x1 ∈ X1 và xi ∈ argmax xi { xip( n∑ j=1 xj)− fi(xi) : xi ∈ Xi } , i = 2,. . . , n. (2) Bài toán hãng – đại lý (Principal – Agency Problems) Các hãng(1) luôn phân phối hàng hóa đến các đại lý(2) và các đại lý sẽ đại diện cho hãng đó đối với sản phẩm tương ứng. Họ kí kết hợp đồng trong đó (1) ủy quyền (một số) cho (2) qua đó (2) tự do chọn lựa hình thức buôn bán phù hợp với mục tiêu của nó. Việc đó dẫn đến (2) sẽ cố gắng maximize lợi nhuận theo hành động của nó: max a∈A ∫ X G(s(x), a)g(x|a)dx (2.11) trong đó a là hành động buôn bán, a ∈ A, X: tập chấp nhận được của hành động a, s(x) công trả cho (2) từ phía (1) tại x, s : X → R G : R×A → R là hàm sử dụng tính giá trị s(x) từ phía (1) theo tác động của hành động a và g là hàm mật độ mô tả xác suất của kết quả thực tế x khi (2) dùng hành động a. Từ cách quan sát của (1), hàm s mô tả một hệ dùng để thúc đẩy (2) hành động theo mục đích của (1). Do đó (1) phải chọn hàm này sao cho (1) đạt lợi nhuận tốt nhất có thể, (1) dùng hàm H : R → R đo bằng x − s(x) và (1) dùng hàm mật độ tương tự như g để đánh giá xác suất của x, (1) sẽ làm maximize: max s∈S ∫ X H(x− s(x))g(x|a′)dx (2.12) trong đó S: tập chấp nhận được của tăng trưởng, a′: giải quyết (2.12) với a cố định Dĩ nhiên chúng ta phải gắn với điều kiện sau:∫ X G(s(x), a′)g(x|a′)dx ≥ c (2.13) Rõ ràng nếu (2.13) không thỏa thì (2) sẽ không sẵn sàng kí hợp đồng với (1); (2.13) chính là ràng buộc quyết định sự tồn tại bài toán. 29 Tóm lại bài toán "Principal – Agency Problem": chọn s ∈ S, maximize (2.12) sao cho a′ ∈ A, maximize (2.11) và thỏa (2.13). (3) Bài toán Cân bằng hóa học tối ưu (Optimal Chemical Equilibria) Trong quá trình sản xuất ra chất hóa học, chúng ta luôn phải đặt ra câu hỏi làm thế nào để bào chế được một hỗn hợp chất sao cho: (i) chất ta muốn hình thành là kết quả của phản ứng hóa học (PUHH) trong lò phản ứng được mong muốn xuất hiện càng nhiều, (ii) độc chất hoặc tạp chất trong chất đó bằng không hoặc chiếm một lượng vô cùng bé. đây được xem là một bài toán tối ưu hai cấp, trong đó (i) là bài toán cấp dưới còn (ii) là bài toán cấp trên. Các nhà hóa học không thể quan sát PUHH trong nhiệt độ cao mà chỉ phân tích được thời điểm cuối của phản ứng, bởi một bài toán lồi. Trong bài toán lồi này, hàm entropi f(x, p, T ) được làm cho bé nhất sao cho thỏa điều kiện là nguyên lý bảo toàn khối lượng và các khối lượng đều không âm. Hiển nhiên là quá trình cân bằng hóa học phụ thuộc vào áp suất p, nhiệt độ T và khối lượng y của các chất trong phản ứng: min x N∑ i=1 ci(p, T )xi + G∑ i=1 xi ln xi 2 z = G∑ i=1 xj, Ax = Ay, x ≥ 0, đây là bài toán cấp dưới, trong đó G là số lượng khí, N là tổng số chất phản ứng (G ≤ N), A là ma trận tạo bởi các hàng là tương ứng một loại nguyên tố và các cột là tương ứng một loại chất, x là vecto của khối lượng các chất trong cân bằng hóa học, y là khối lượng ban đầu của các chất có trong PUHH, A là ma trận con của A có các cột tương ứng với các chất ban đầu, giá trị ci(p, T) cho biết điện hóa của một chất phụ thuộc theo biến p 30 và T . Gọi nghiệm tối ưu của bài toán cấp dưới là x(p, T, y), giả sử nghiệm này duy nhất. Khi ấy bài toán cấp trên có mô hình như sau: min p,T,y 〈c, x〉, (p, T, y) ∈ Y, x = x(p, T, y). (4) Bài toán kinh tế môi trường (Environmenttal Economics) Điều kiện sản xuất ảnh huởng tới kết quả của các hoạt động kinh tế trong quá trình sản xuất. Điều này có thể thấy ngay trong môi trường khi các nhà sản xuất làm ô nhiễm. Chúng ta phải làm sạch môi trường, đó là một trong các hoạt động cần thiết của quá trình sản xuất. Chẳng hạn giấy được sinh ra từ nhà máy hay xí nghiệp sản xuất giấy từ gỗ, do đó các cây xanh bị khai thác sẽ ảnh hưởng đến môi trường rừng, có tác động gián tiếp đến mực nước ngầm trong lòng đất và mực nước các con sông. Và hơn nữa nước thải trong quá trình sản xuất còn ảnh hưởng tới sự sống của cá, tôm trên dòng sông, ao hồ. Do đó các nhà nuôi trồng thủy sản cũng chịu ảnh hưởng nghiêm trọng. Bây giờ, giả sử GP (x1), GF (x1, x2) là lợi nhuận sản xuất của xí nghiệp giấy (1) và nhà nuôi trồng thủy sản (2), x1, x2 là các hoạt động kinh tế và GF là hàm giảm. Nếu cả (1) và (2) đều muốn lợi nhuận lớn nhất thì thị trường sẽ không tồn tại bởi vì (2) sẽ phá sản do chất thải tối đa từ (1) tạo ra. Bây giờ, giả sử chính phủ quan tâm tới quyền lợi của (2), thì phải đánh thuế vào của cải của (1) và số tiền này được quốc hữu hóa. Một cách hiểu đơn giản là số tiền thuế phụ thuộc tuyến tính vào x1, hàm lợi nhuận của (1) thay đổi thành: GP (x1)− r(x1), với r là chỉ số thuế. Gọi x1(r) là nghiệm tối ưu. Rõ ràng r tăng thì GP giảm và do đó sự thiệt hại của (2) sẽ giảm khi r tăng (cần thiết để bảo vệ (2)). Hệ quả là tài sản tối ưu của (2) x2(x1(r)) sẽ phụ thuộc r . Tiếp theo chính phủ có nhiệm vụ xác định chỉ số thuế hợp lý để tính toán ra phúc lợi xã hội phụ thuộc vào lượng giấy và thủy sản được sản xuất ra, như vậy giá trị thuế sẽ chi trả bởi (1). Ta cần có một hàm số để thực hiện công việc trên, hàm này phụ thuộc vào r: W (x1(r), x2(x1(r)), r) là lớn 31 nhất có thể (khi r cố định). Tóm lại mô hình bài toán hai cấp như sau: max r≥0 W (x1, x2, r) sao cho x1 thỏa bài toán max x1≥0 GP (x1)− r(x1), và x2 thỏa bài toán max x2≥0 GF (x1, x2), với r, x1 cho trước và thỏa mãn điều kiện GF (x1, x2) ≥ 0. (5) Vài ứng dụng thực tiễn khác(Other Real Applications) Danh sách các ứng dụng của bài toán hai cấp là vô cùng dài và được phát triển nhanh chóng. Sau đây ta sẽ nêu vài ứng dụng được trình bày ngắn gọn. Dĩ nhiên, những ứng dụng này có thể thực hiện và hoàn thiện trong tương lai xa và mục đích chủ yếu là đưa ra những nghiên cứu khác nhau về các vấn đề thực tế trong đó có liên quan đến mô hình bài toán tối ưu hai cấp nêu trên. + giải quyết xung đột trong phân chia nguồn nước các con sống lớn trên thế giới (sông Nin, Hằng) + công nghệ vật liệu + Cân bằng giao thông . . . M 32 Chương 3 Điều kiện tối ưu cho bài toán hai cấp hữu hạn Chương này tập trung xét các lớp bài toán hai cấp hữu hạn dạng optimistic và suy ra các điều kiện cần tối ưu của nó đối với nghiệm tối ưu optimistic địa phương. Vấn đề thiết lập điều kiện tối ưu cho bài toán hai cấp hữu hạn dạng optimistic đòi hỏi một quá trình rất dài. Ta có thể hình dung các bước cơ bản cần có như sau: • Chuyển các lớp bài toán tối ưu hai cấp dạng optimistic về các lớp bài toán tương đương bằng một trong bốn hướng tiếp cận (các hướng tiếp cận sẽ nói rõ bên dưới). • Thiết lập các điều kiện định tính ràng buộc (Constraint Qualification condi- tions, viết tắt là (CQ)) kèm theo mỗi hướng tiếp cận. • Tùy từng lớp bài toán mà ta áp đặt các tính chất cho các hàm F, f, g,Ψ, ϕ trong bài toán. • Áp dụng kiến thức cơ bản về điều kiện tối ưu cho bài toán tối ưu một cấp có chứa tham số. Từ đó thiết lập được điều kiện cần tối ưu cho bài toán tối ưu hai cấp dạng optimistic ban đầu. 33 Có bốn hướng tiếp cận khi thiết lập điều kiện tối ưu: Hướng tiếp cận (1) Sử dụng hàm Lagrange và tập nhân tử Lagrange thay thế bài toán cấp dưới lồi và dưới các điều kiện (CQ): (MFCQ), (SMFCQ). Hướng tiếp cận (2) Sử dụng nón pháp tuyến và đối đạo hàm (do Mordukhovich đề xuất) đối với đồ thị của ánh xạ (đa trị) tập nghiệm gphΨ của bài toán cấp dưới lồi. Hướng tiếp cận (3) Sử dụng dưới vi phân Mordukhovich để phát triển hàm giá trị tối ưu ϕ của bài toán cấp dưới dưới điều kiện CQ partially calm,. . . Hướng tiếp cận (4) Sử dụng dưới vi phân Clarke phát triển hàm giá trị tối ưu ϕ của bài toán cấp dưới dưới rất nhiều điều kiện CQ khác nhau. Sau đây ta tìm hiểu các hướng tiếp cận này bằng ba mục sau. Mục (3.1) gồm hai hướng tiếp cận (1) và hướng tiếp cận (2) cho bài toán hai cấp hữu hạn với giả thiết lồi ở bài toán cấp dưới, Mục (3.2) gồm hướng tiếp cận (3) và mục cuối cùng (3.3) gồm hướng tiếp cận (4). 3.1 Điều kiện tối ưu khi bài toán cấp dưới lồi Các kết quả trong phần này có liên quan tới [10], [14]. Hướng tiếp cận (1): Sử dụng hàm Lagrange và tập nhân tử Lagrange thay thế bài toán cấp dưới lồi Các yếu tố sau được xét trong [10, chương 4, 5] . Xét các bài toán như sau: min y {f(x, y)|g(x, y) ≤ 0, h(x, y) = 0} (3.1) min x {F (x, y)|y ∈ Ψ(x), x ∈ X}, (3.2) min x {ϕo(x)|x ∈ X}, (3.3) 34 ϕo(x) = min y {F (x, y)|y ∈ Ψ(x)} (3.4) với Ψ(.) xác định như (2.4) và F : Rn × Rm → R, Y ⊆ Rm là tập đóng, X = {x ∈ Rn|G(x) ≤ 0} trong đó ràng buộc bài toán cấp trên G : Rn → Rk, còn các hàm của bài toán cấp dưới f, g, h đều lồi. Như vậy bài toán hai cấp gốc ban đầu là: (3.1), (3.2). Bài toán hai cấp dạng opti- mistic là: (3.1), (3.3), (3.4). Xét hàm Lagrange L(x, y, λ, µ) := f(x, y)+λTg(x, y)+µTh(x, y) và (λ, µ) ∈ tập nhân tử Lagrange ∧(x, y) := {(λ, µ) ∈ Rp × Rq|λ ≥ 0, λTg(x, y) = 0, ∇yL(x, y, λ, µ) = 0}. Bằng cách sử dụng dạng KKT thay thế bài toán cấp dưới (3.1): ∇yL(x, y, λ, µ) = 0, g(x, y) ≤ 0, λ ≥ 0, λTg(x, y) = 0, h(x, y) = 0. Và chúng ta viết lại bài toán hai cấp với dạng KKT thay thế bài toán cấp dưới, như sau min x,y,λ,µ F (x, y) G(x) ≤ 0, ∇yL(x, y, λ, µ) = 0, g(x, y) ≤ 0, λ ≥ 0, λTg(x, y) = 0, h(x, y) = 0. (3.5) Khi bài toán cấp dưới (3.1) là lồi thì bài toán (3.5) tương đương với bài toán hai cấp gốc (3.1), (3.2) (xem [10, Chương 5]). 35 Tuy vậy sự khó khăn của bài toán (3.5) là, do nó là bài toán trơn nên một số giả thiết chính quy và điều kiện định tính ràng buộc (CQ) không thỏa mãn. Ta kí hiệu ∇f(.),∇xf(.),∇yf(.) tương ứng là gradient của hàm f , gradient của hàm f theo biến x, gradient của hàm f theo biến y. Ta có thể nêu giả thiết chính quy do Mangasarian–Fromowitz (MFCQ) đề ra: Định nghĩa 3.1.1 ([10], Mangasarian Fromowitz Constraint Qualification) (MFCQ) thỏa mãn cho bài toán min y {f(x, y)|g(x, y) ≤ 0, h(x, y) = 0} tại điểm (xo, yo) nếu có một hướng d sao cho ∇ygi(xo, yo)d < 0∀i ∈ I(xo, yo) := {j|gj(xo, yo) = 0}, ∇yhj(xo, yo)d = 0 ∀j = 1, . . . , q và gradient {∇yhj(xo, yo)|j = 1, . . . , q}, {∇gi(x, y)|i ∈ I(xo, yo)} độc lập tuyến tính. Do đó ta cần thiết lập dạng bài toán không trơn sao cho các (CQ) thỏa mãn, xét định lý sau: Định lý 3.1.1 ([10], Định lý 5.11) Nếu dạng KKT của bài toán (3.1) là một phần của các ràng buộc của một bài toán tối ưu thì (MFCQ) không thỏa mãn tại mọi điểm chấp nhận được. Chứng minh Đặt w(x, y) := −g(x, y) và xét dạng KKT của (3.1): ∇yL(x, y, λ, µ) = 0, w(x, y) := −g(x, y) ≥ 0, λ ≥ 0, λTw(x, y) = 0 (i), h(x, y) = 0 (ii). là một phần của các ràng buộc của bài toán tối ưu. Giả sử (MFCQ) thỏa mãn tại điểm chấp nhận được (x, y, λ, µ), thì từ bất đẳng thức 36 (i) và phương trình (ii) ở trên, ta có: (λT∇xw(x, y), λT∇yw(x, y), w(x, y), 0)T 6= 0 (3.6) và có một vecto (d, r, s) thỏa: λT∇xw(x, y)d+ λT∇yw(x, y)r + sTw(x, y) = 0, (3.7) ∇xwi(x, y)d+∇ywi(x, y)r > 0, ∀i : wi(x, y) = 0, (3.8) si > 0, ∀i : λi = 0. (3.9) Bây giờ từ (3.8) và (3.9) ta suy ra được λT∇xw(x, y)d+ λT∇yw(x, y)r + sTw(x, y) ≥ 0. (3.10) Thật vậy nếu ∇xwi(x, y)d+∇ywi(x, y)r ≤ 0 thì wi(x, y) > 0 (3.8), theo dòng 2 trên ta suy ra λi = 0 lại suy ra si > 0 (do (3.9)) nên ta có (3.10). Nếu si ≤ 0 suy ra wi(x, y) = 0, do (3.8) và (i). Tóm lại ta có (3.10). Mặt khác dấu đẳng thức ở (3.10) không xảy ra. Thật vậy, nếu wi(x, y) > 0 thì λi = 0, do (i) và si > 0 do (3.9) , do đó (3.10) không xảy ra dấu "=", điều này mâu thuẫn với (3.7). Do đó w(x, y) = 0. Tương tự, λi > 0 suy ra ∇xwi(x, y)d+∇ywi(x, y)r > 0 nên mâu thuẫn (3.7) suy ra λ = 0 Từ đây suy ra phải xảy ra đồng thời w(x, y) = 0, λ = 0 điều này lại mâu thuẫn với (3.6). Vậy (MFCQ) không thỏa mãn tại điểm chấp nhận (x, y, λ, µ). ¤ Để phá bỏ khó khăn này, một dạng cho bài toán hai cấp không trơn dạng opti- mistic được xây dựng như sau: min x,y,λ,µ F (x, y) G(x) ≤ 0, ∇yL(x, y, λ, µ) = 0, 37 min{−g(x, y), λ} = 0, h(x, y) = 0. (3.11) Bây giờ ta trở lại vấn đề chính là điều kiện tối ưu. Trước hết ta tìm hiểu mối quan hệ giữa bài toán hai cấp dạng optimistic và bài toán vừa thiết lập (3.11). Định lý 3.1.2 ([10], Định lý 5.15) Xét bài toán optimistic bilevel (3.1), (3.3), (3.4) và giả thiết bài toán cấp dưới (3.1) là bài toán tối ưu tham số lồi sao cho (MFCQ) thỏa mãn tại nghiệm chấp nhận (xo, yo) với G(xo) ≤ 0, yo ∈ Ψ(xo). Khi đó mỗi nghiệm tối ưu địa phương optimistic của (3.1), (3.3), (3.4) tương ứng là một nghiệm tối ưu địa phương cho bài toán (3.11). Chứng minh Giả sử xo là nghiệm tối ưu optimistic địa phương của (3.1), (3.3), (3.4), nghĩa là tồn tại một lân cận mở Uδ(x o) sao cho ϕo(x o) ≤ ϕo(x), ∀x ∈ Uδ(xo) với G(x) ≤ 0. Vì dạng KKT là cần và đủ trong bài toán cấp dưới nên ta có: ϕo(x o ≤ F (x, y), ∀(x, y), x ∈ Uδ(xo) và ∇yL(x, y, λ, µ) = 0, g(x, y) ≤ 0, λ ≥ 0, λTg(x, y) = 0, h(x, y) = 0. điều này có nghĩa là tồn tại một lân cận mở W²(x o, yo) sao cho ϕo(x o) ≤ F (x, y), ∀(x, y) ∈ W²(xo, yo) thỏa mãn ∇yL(x, y, λ, µ) = 0, g(x, y) ≤ 0, λ ≥ 0, λTg(x, y) = 0, h(x, y) = 0. ¤ Sau đây là điều kiện tối ưu dạng Fritz–John cho bài toán (3.11) Định lý 3.1.3 [10, Định lý 5.16](Điều kiện tối ưu dạng Fritz John)Nếu (zo, vo) với zo := (xo, yo) và vo := (λo, µo), là một nghiệm tối ưu địa phương của (3.11) thì 38 tồn tại một vectơ (κo, κ, ω, ζ, τ, ξ) 6= 0 thỏa: κo∇F (z0) + κT (0,∇xG(xo) +∇(∇yL(zo, vo)ω + ζT∇g(zo) + τT∇h(zo) = 0, (∇yg(zo),∇yh(zo))Tω − (ξ, 0)T = 0, κo, κ ≥ 0, gi(z o)ζi = 0, ∀i λoi ξ = 0, ∀i, ζiξi ≥ 0, ∀i ∈ K, κTG(xo) = 0.(3.12) trong đó tập K = {i|gi(xo, yo) = λoi = 0}. Chứng minh Bởi [4], tồn tại một vectơ (κo, κ, ω, τ, u) T sao cho κo∇F (zo) + κT (0,∇xG(xo)) +∇(∇yL(zo, vo)ω)− uTd+ rT∇h(zo) = 0, (∇yg(zo),∇yh(zo)Tω − uT (r, 0) = 0, κo, κ ≥ 0, κTG(xo) = 0 trong đó d ∈ ∂y min{−g(zo), λo} và r ∈ ∂λ min{−g(zo), λo} trong đó ∂(.) kí hiệu cho gradient mở rộng Clarke (xem [chương 1]). Bằng công thức tính toán, ta có: (di, ri) ∈ co{(−∇gi(zo), 0), (0, 0, 1)} trong đó co(.) kí hiệu bao lồi. Nếu gi(z o) = λo = 0 nghĩa là di = −αi∇gi(zo), ri = 1− αi với αi ∈ (0, 1). Ta có ui 6= 0 do đó (uiαi)ui(1− αi) ≥ 0. Chọn cặp(ζi, ξi) =  (ui, 0) khi λ o i > 0 (0, ui) khi gi(z o) < 0 (αiui, (1− αi)ui) khi gi(zo) = λoi = 0 39 từ đó ta có hệ cần chứng minh (3.12). ¤ Trên đây là điều kiện tối ưu dạng Fritz John với chỉ số κo,κ đều không âm. Việc khẳng định κo 6= 0 là hết sức quan trọng để suy ra điều kiện tối ưu dạng KKT. Ta cần nâng cấp bài toán (3.11) lên thành một bài toán mới như sau: min x,y,λ,µ F (x, y) G(x) ≤ 0, ∇yL(x, y, λ, µ) = 0, gi(x, y) = 0 khi gi(x 0, yo) = 0, λi = 0 khi λ o i = 0, gi(x, y) ≤ 0 khi gi(x0, yo) < 0, λi ≥ 0 khi λoi > 0, h(x, y) = 0. (3.13) Rõ ràng nghiệm chấp nhận được của bài toán (3.13) cũng là nghiệm chấp nhận được của bài toán (3.11). Ở đây nghiệm chấp nhận được là nghiệm thỏa mãn các giả thiết và ràng buộc của bài toán. Do đó nếu (xo, yo, λo, µo) là nghiệm tối ưu địa phương của (3.11) thì nó cũng là nghiệm tối ưu địa phương của (3.13). Ta cần thay đổi một số (CQ) thích hợp cho bài toán này. Trước hết là (MFCQ) cho bài toán tổng quát biến t. Định nghĩa 3.1.2 [10, Mục 5.5](Mangasarian Fromowitz Constraint Quali- fication) (MFCQ) thỏa mãn cho bài toán min{f(t)|g(t) ≤ 0, h(t) = 0} (3.14) tại điểm to nếu có một hướng d sao cho ∇gi(to)d < 0 ∀i ∈ I(to) := {j|gj(to) = 0},∇hj(to)d = 0 ∀j = 1, . . . , q và gradient {∇thj(to)|j = 1, . . . , q}, {∇gi(to)|i ∈ I(to)} độc lập tuyến tính. 40 và Định nghĩa 3.1.3 [10, Mục 5.5](Strict Mangasarian Fromowitz Constraint Qualification) (SMFCQ) thỏa mãn cho bài toán (3.14) tại điểm to nếu tồn tại một nhân tử Lagrange (λ, µ) thỏa λ ≥ 0, λTg(to) = 0, ∇f(to) + λT∇g(to) + µT∇h(to) = 0, và cùng với một hướng d sao cho ∇gi(to)d < 0∀i ∈ I(to) \ J(λ),∇gi(to)d = 0 ∀i ∈ J(λ),∇hj(to)d = 0 ∀j = 1, . . . , q và gradient {∇thj(to)|j = 1, . . . , q}, {∇gi(to)|i ∈ J(λ)} độc lập tuyến tính, trong đó J(λ) := {i|λi > 0} Bây giờ ta thiết lập điều kiện tối ưu dạng KKT cho bài toán (3.13). Định lý 3.1.4 [10, Định lý 5.17](Điều kiện tối ưu dạng KKT)Giả sử (xo, yo, λo, µo) là một nghiệm tối ưu địa phương của (3.11). (i) Nếu (MFCQ) đúng với bài toán (3.13) tại (xo, yo, λo, µo), thì tồn tại nhân tử (κ, ω, ζ, τ, ξ) thỏa mãn: ∇F (z0) + κT (0,∇xG(xo) +∇(∇yL(zo, vo)ω + ζT∇g(zo) + τT∇h(zo) = 0, (∇yg(zo),∇yh(zo))Tω − (ξ, 0)T = 0, κ ≥ 0, gi(z o)ζi = 0, ∀i λoi ξ = 0, ∀i, ζiξi ≥ 0, ∀i ∈ K, κTG(xo) = 0. (3.15) trong đó tập K = {i|gi(xo, yo) = λoi = 0}. 41 (ii) Nếu (SMFCQ) thêm vào đúng với bài toán (3.13), thì tồn tại nhân tử duy nhất (κ, ω, ζ, τ, ξ) thỏa mãn : ∇F (z0) + κT (0,∇xG(xo) +∇(∇yL(zo, vo)ω + ζT∇g(zo) + τT∇h(zo) = 0, (∇yg(zo),∇yh(zo))Tω − (ξ, 0)T = 0, κ ≥ 0, gi(z o)ζi = 0, ∀i λoi ξ = 0, ∀i, ζi ≥ 0, ξi ≥ 0, ∀i ∈ K, κTG(xo) = 0. (3.16) Chứng minh (i) Theo Định lý 3.1.3, mọi điểm cực tiểu địa phương của (3.13) thì thỏa mãn (3.12) với vectơ (κo, κ, ω, ζ, τ, ξ) 6= 0. Giả sử κo = 0. Khi đó: κT (0,∇xG(xo) = −∇(∇yL(zo, vo)ω − ζT∇g(zo)− τT∇h(zo) (3.17) 0 = (∇yg(zo),∇yh(zo))Tω − (ξ, 0)T (3.18) Đặt A = {1, . . . , p} \ J(λo). Nhắc lại (MFCQ) thỏa cho bài toán (3.13) nếu Gradient (∇2yyL(zo, vo),∇2xyL(zo, vo),∇yg(zo),∇yh(zo), và (∇xgI(zo)(zo),∇ygI(zo)(zo), 0, 0), (0, 0, eA, 0), (∇xh(zo),∇yh(zo), 0, 0) là độc lập tuyến tính và tồn tại vectơ (d, r, γ, η) thỏa mãn: ∇(∇yL(zo, vo)(d, r)T + γT∇yg(zo) + ηT∇yh(zo) = 0 (3.19) ∇ygI(zo)(zo)d+∇xgI(zo)(zo)r = 0 (3.20) 42 ∇yh(zo)d+∇xh(zo)r = 0 (3.21) γA = 0 (3.22) ∇Gi(xo) < 0, khiGi(xo) = 0. (3.23) Lưu ý là khi gi(x, y) ≤ 0 không hữu hiệu khi i /∈ I(xo, yo) thì ta có γi = 0. Nhân vế trái của (3.18) bởi (γTηT ) ta có γT∇yg(zo)ω + ηT∇yh(zo)ω = 0 ( vì ξi = 0 với λ o i > 0 và γi = 0 với o i = 0). Từ (3.19), ta có ∇(∇yL(zo, vo)(d, r)T = 0. Từ (3.20) và (3.21) ta có −∇(∇yL(zo, vo)ω)(d, r)T − ζT∇g(zo)(d, r)T − rT∇h(zo)(d, r)T = κT∇G(xo)r = 0. Vì κTG(xo) = 0 và ∇Gi(xo)r < 0 khi Gi(xo) = 0 suy ra κ = 0 Nhắc lại ∇(∇yL(z, v) = (∇2yxL(z, v),∇2yyL(z, v)) Kết hợp với sự độc lập tuyến tính và (3.17), (3.18) ta dẫn đến điều mâu thuẫn với định lý. Do đó κo 6= 0 và có thể cho nó = 1. Như vậy ta có hệ (3.15). (ii) Giả sử κ, ω, ζ, τ, ξ là các nhân tử Lagrange tương ứng điểm dừng của (3.13). Giả sử ζi < 0 với i ∈ K ⊆ I(xo, yo). Không mất tính tổng quát, lấy 1 ∈ K và ζ1 < 0. Bởi (SMFCQ) thỏa, nên (∇(∇yL(zo, vo),∇yg(zo),∇yh(zo)) (∇i(zo, 0, 0) khi gi(zo) = 0 (0, 0, ei, 0) khiλ o i = 0 (∇h(zo, 0, 0) (0,∇yGi(xo), 0, 0) khiκi > 0. là độc lập tuyến tính và tồn tại một vectơ (d, r, γ, η) thỏa mãn: ∇(∇yL(zo, λo, µo))(d, r)T + γT∇yG(zo) + ηT∇yh(zo) = 0 43 ∇gi(zo)(d, r)T = 0 khi gi(zo) = 0 γi = 0 khiλ o i = 0 ∇h(zo)(d, r)T = 0 ∇xGi(xo) = 0 khiκi > 0 ∇xGi(xo) < 0 khiκi = Gi(xo) = 0 bởi sự tuyến tính ở trên, nên tồn tại một vectơ (do, ro, γo, ηo) thỏa mãn: ∇(∇yL(zo, λo, µo))(do, ro)T + γoT∇yG(zo) + ηoT∇yh(zo) = 0 (3.24) ∇g1(do, ro)T = −1 (3.25) ∇gi(do, ro)T = 0 khi gi(zo) = 0, i 6= 1 (3.26) γoi = 0, khiλ o i = 0 (3.27) ∇h(zo)(do, ro)T = 0 (3.28) ∇xGi(xo)ro = 0 khiκi > 0 (3.29) Bởi (3.18) ta có γoT∇yG(zo)ω+ ηoT∇yh(zo)ω = 0, vì γoT ξ = 0. Do đó kết hợp (3.24) ta suy ra ∇(∇yL(zo, λo, µo))(do, ro)T = 0. Mặt khác ∇F (zo)(do, ro)T = ζ1 < 0. Do vậy (xo, yo, λo, µo) không phải là điểm dừng Bouligand–contingent (xem [10, chương 3, 5]) của bài toán: min x,y,λ,µ F (x, y) G(x) ≤ 0, ∇yL(x, y, λ, µ) = 0, gi(x, y) = 0 khi gi(x 0, yo) = 0, i 6= 1 λi = 0 khiλ o i = 0, gi(x, y) ≤ 0 khi gi(x0, yo) < 0, λi ≥ 0 khiλoi > 0, h(x, y) = 0. (3.30) 44 (bởi vì (SMFCQ) thỏa cho bài toán (3.13)) như vậy (xo, yo, λo, µo) không phải là nghiệm cực tiểu địa phương của (3.13), mâu thuẫn giả thiết. Do vậy ζ1 ≥ 0, tương tự ξi ≥ 0, ∀i ∈ K. Như vậy ta có hệ (3.16). ¤ Ví dụ sau chỉ ra (3.16) không thỏa nếu (SMFCQ) thay bằng (MFCQ). Ví dụ 3.1.1 Xét bài toán min{−z2 + z3} −z1 + z2 − z3 ≤ 0, −z3 ≤ 0 −z1 ≤ 0, −z1 − z2 ≤ 0, z1(z2 + z3) = 0. Nghiệm tối ưu của bài toán trên là zo1 = 0, z o 2 ≥ 0, zo3 ≥ 0. Xét điểm zo = (0, 0, 0)T , ta có (MFCQ) thỏa , giả sử hệ (3.16) nghĩa là : −ζ − κ1 − ξ = 0 (i) −1− ζ + κ1 = 0 (ii) 1− κ1 − κ2 = 0 κ1(−zo1 + zo2 − zo3) = κ2(−zo3) = 0 ζ(−zo1) = ξ(−zo1 − zo2) = 0 ζ ≥ 0, ξ ≥ 0, κ ≥ 0 (iii) Hệ này vô nghiệm vì phương trình (i) và bất phương trình (iii) cho ta ζ = ξ = κ = 0, (iv), mâu thuẫn với phương trình (ii). ¤ 45 Hướng tiếp cận (2): Sử dụng nón pháp tuyến và đối đạo hàm Mordukhovich đối với đồ thị của ánh xạ (đa trị) tập nghiệm gphΨ của bài toán cấp dưới lồi Trong tiểu mục này, chúng ta thiết lập điều kiện cần cho bài toán hai cấp khi bài toán cấp dưới là bài toán lồi. Các kết quả đạt được phải dựa trên công cụ của giải tích không trơn (nonsmooth analysis) cụ thể là nón pháp tuyến và đối đạo hàm của ánh xạ đa trị (xem chương 1, mục 1.3). Xét bài toán cấp trên (P) min x F (x, y) sao cho x ∈ Rn, y ∈ Ψ(x), (3.31) trong đó F : Rn × Rm → R và Ψ(x) là tập nghiệm của bài toán cấp dưới (LLP) min y f(x, y) sao cho y ∈ K(x), trong đó f : Rn × Rm → R, K(x) ⊆ Rm. Với mỗi x, thì f(x, .) là lồi và K(x) lồi. Như vậy bài toán hai cấp dạng optimistic như sau (OBP) min x ϕo(x), trong đó ϕo(x) là hàm giá trị tối ưu của hàm mục tiêu cấp trên (P), xác định như sau ϕo(x) := inf y {F (x, y)|y ∈ Ψ(x)}. Xét bài toán (P1) min x, y F (x, y) sao cho (x, y) ∈ gphΨ, (3.32) với ánh xạ đa trị Ψ : Rn ⇒ Rm và gphΨ xác định theo chương 1. Xét các mệnh đề về mối liên quan giữa nghiệm các bài toán (P) (dạng optimistic) và nghiệm của (P1): 46 Mệnh đề 3.1.1 [14, Mệnh đề 2.2] Nếu x là một nghiệm tối ưu toàn cục (dạng optimistic) cho bài toán (P). Khi đó (x, y) với y ∈ Ψ(x) và ϕo(x) = F (x, y), là một nghiệm tối ưu toàn cục của (P1). Điều ngược lại cũng đúng, nghĩa là: Mệnh đề 3.1.2 [14, Mệnh đề 2.3] Nếu (x, y) là một nghiệm tối ưu toàn cục của (P1), thì x là nghiệm tối ưu toàn cục của (P). Mệnh đề 3.1.3 [14, Mục 3] Nếu (x, y) là nghiệm tối ưu địa phương (hay toàn cục) của (P1) và F trơn, thì 0 ∈ ∇F (x, y) +NgphΨ(x, y), trong đó NgphΨ(x, y) hay có cách viết khác N ( (x, y); gphΨ ) là nón pháp tuyến Mordukhovich (chương 1). Sau đây chúng tôi xin nêu vài kết quả chính là điều kiện cần tối ưu cho các bài toán đã xét ở trên, và đây cũng là kết quả từ [14] Định lý 3.1.5 [14, Định lý 4.1] Xét bài toán (P1) với F : Rn ×Rn → R là hàm trơn và ánh xạ đa trị tập nghiệm của (LLP) Ψ : Rn ⇒ Rm với Ψ(x) = argmin y {f(x, y)|y ∈ K(x)} trong đó f(x, .) là hàm trơn lồi theo y với mỗi x cố định, và K(x) là tập lồi đóng. Giả sử (x, y) là nghiệm tối ưu địa phương (hay toàn cục) của (P1). Hơn nữa ∇yf : Rn ×Rm → Rm là khả vi liên tục tại (x, y). Cũng giả thiết điều kiện (CQ) sau thỏa mãn tại (x, y) : v ∈ Rm với 0 ∈ ∇ ( ∇yf(x, y) )T v +D∗NK ( (x, y), −∇yf(x, y) ) (v) =⇒ v = 0.(3.33) Khi đó tồn tại v∗ ∈ Rm sao cho 0 ∈ ∇F (x, y) +∇ ( ∇yf(x, y) )T v∗ +D∗NK ( (x, y), −∇yf(x, y) ) (v∗). (3.34) 47 Áp dụng định lý trên vào bài toán (P), ta có các hệ quả sau. Hệ quả 3.1.1 [14, Hệ quả 4.1] Xét bài toán tối ưu hai cấp (P) trong đó F : Rn × Rn → R là hàm trơn và Ψ(x) là tập nghiệm của bài toán (LLP) trong đó f : Rn × Rn → R là hàm trơn chặt và lồi theo y với mỗi x, và K(x) là tập lồi compac. Giả sử (x, y) là nghiệm tối ưu địa phương của (P). Hơn nữa ∇yf : Rn × Rm → Rm là khả vi liên tục tại (x, y). Cũng giả thiết điều kiện (CQ) sau thỏa mãn tại (x, y) : v ∈ Rm với 0 ∈ ∇ ( ∇yf(x, y) )T v +D∗NK ( (x, y), −∇yf(x, y) ) (v) =⇒ v = 0. Khi đó tồn tại v∗ ∈ Rm sao cho 0 ∈ ∇F (x, y) +∇ ( ∇yf(x, y) )T v∗ +D∗NK ( (x, y), −∇yf(x, y) ) (v∗). Hệ quả 3.1.2 [14, Hệ quả 4.2] Xét bài toán tối ưu hai cấp (P) trong đó F : Rn × Rn → R là hàm trơn và Ψ(x) là tập nghiệm của bài toán (LLP) trong đó f : Rn×Rn → R là hàm trơn và lồi theo y với mỗi x, và K(x) là tập lồi và giả thiết Ψ là usc. Giả sử x là nghiệm tối ưu địa phương (dạng optimistic) của (P) và giả sử có y ∈ Ψ(x) sao cho F (x, y) = ϕo(x). Hơn nữa ∇yf : Rn×Rm → Rm là khả vi liên tục tại (x, y). Cũng giả thiết điều kiện (CQ) sau thỏa mãn tại (x, y) : v ∈ Rm với 0 ∈ ∇ ( ∇yf(x, y) )T v +D∗NK ( (x, y), −∇yf(x, y) ) (v) =⇒ v = 0. Khi đó tồn tại v∗ ∈ Rm sao cho 0 ∈ ∇F (x, y) +∇ ( ∇yf(x, y) )T v∗ +D∗NK ( (x, y), −∇yf(x, y) ) (v∗). Các điều kiện cần tối ưu cấp hai cho bài toán hai cấp không nêu ra ở luận văn, có thể tham khảo trong [14]. 48 3.2 Điều kiện tối ưu sử dụng dưới vi phân Mor- dukhovich Các kết quả trong phần này có liên quan đến bài báo [17, 18, 12, 19, 20, 22, 23]. Mục đích là đưa ra các dạng bài toán hai cấp: trơn, lồi và tuyến tính, lipschitz. Các điều kiện CQ là partially calm và các giả thiết chính quy cho bài toán cấp trên và cấp dưới, cộng với các công cụ giải tích của Mordukhovich, ta sẽ thiết lập nên các điều kiện cần cho từng dạng bài toán. Nội dung chính: • Điều kiện tối ưu cho bài toán hai cấp trơn. • Điều kiện tối ưu cho bài toán hai cấp lồi, tuyến tính. • Điều kiện tối ưu cho bài toán hai cấp lipschitz. (1) Bài toán hai cấp trơn Chúng ta xét bài toán hai cấp dạng optimistic như sau: min x F (x, y) sao cho x ∈ X, y ∈ Ψ(x) (3.35) trong đó F : Rn×Rm → R là hàm mục tiêu cấp trên, X ⊂ Rn là tập ràng buộc cấp trên, và Ψ : Rn ⇒ Rm là ánh xạ đa trị cho bởi Ψ(x) := Argmin y {f(x, y)|y ∈ K(x)} (3.36) là tập nghiệm tối ưu của bài toán cấp dưới: min y f(x, y) sao cho y ∈ K(x) (3.37) với f : Rn × Rm → R và K : Rn ⇒ Rm. Để đơn giản chúng ta tập trung vào trường hợp khi ánh xạ đa trị K trong bài toán 49 cấp dưới và tập ràng buộc X của bài toán cấp trên được biểu diễn bằng hệ bất đẳng thức: K(x) = {y ∈ Rm|gi(x, y) ≤ 0, i = 1, . . . , p}, x ∈ Rn, (3.38) X = {x ∈ Rn|Gj(x) ≤ 0, j = 1, . . . , k} (3.39) với gi, Gj là các hàm thực. Sau đây chúng ta sẽ thiết lập các điều kiện tối ưu cần cho bài toán hai cấp "trơn" (nghĩa là tất cả các hàm đã cho đều khả vi chặt hay khả vi liên tục) Xét bài toán sau đây: minx,y F (x, y) sao cho x ∈ X, y ∈ K(x), f(x, y)− ϕ(x) ≤ 0, (3.40) trong đó K(x) và X xác định như trên, và ϕ(x) := inf y {f(x, y)|y ∈ K(x)} (3.41) là hàm giá trị tối ưu trong bài toán cấp dưới (3.35). Rõ ràng bài toán vừa thiết lập này thì tương đương đối với bài toán hai cấp (3.35) (nói một các đầy đủ là bài toán hai cấp (3.35)–(3.39) tương đương bài toán (3.38)–(3.41)). Tuy nhiên nó phát sinh các khó khăn sau: • Bài toán (3.38)–(3.41) là bài toán phi tuyến tính • Hàm giá trị tối ưu ϕ(x) không trơn • Các điều kiện CQ cổ điển (như SCQ, MFCQ) không thỏa dù cho có mở rộng trong trường hợp không trơn. Bây giờ chúng ta xét một CQ quan trọng là partially calm. Trước hết thiết lập bài toán dạng nhiễu của (3.40), bằng một tham số tuyến tính u ∈ R, có dạng sau: min x,y F (x, y) sao cho f(x, y)− ϕ(x) + u = 0, y ∈ K(x), x ∈ X. (3.42) 50 Chúng ta nói bài toán (3.40) 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ố λ > 0 và một lân cận U của bộ ba (x, y, 0) ∈ Rn ×Rm ×R sao cho với mọi bộ ba (x, y, u) ∈ U thỏa (3.42), ta có: F (x, y)− F (x, y) + λu ≥ 0 (3.43) Ta cần xây dựng hai giả thiết chính quy cho hai bài toán cấp dưới và cấp trên tương ứng. Giả thiết chính quy cho bài toán cấp dưới, cấp trên Cho điểm (x, y) thỏa các ràng buộc bất đẳng thức (3.38), kí hiệu I(x, y) := { i ∈ {1, . . . , p}|gi(x, y) = 0 } (3.44) Khi đó ta nói (x, y) ∈ Rn × Rm là chính quy cấp dưới nếu với bất kì λi ≥ 0 ta có[ ∑ i∈I(x,y) λi∇ygi(x, y) = 0 ] =⇒ [ λi = 0 ∀i ∈ I(x, y) ] . (3.45) Tương tự, cho x ∈ Rn, thỏa các ràng buộc bất đẳng thức (3.39), kí hiệu J(x) := {j ∈ {1, . . . , k}|Gj(x) = 0} (3.46) Khi đó ta nói x là chính quy cấp trên nếu với bất kì λj ≥ 0 ta có[ ∑ j∈J(x) λj∇Gj(x) = 0 ] =⇒ [ λj = 0 ∀j ∈ J(x) ] . (3.47) Thực chất hai giả thiết chính quy là dạng đối ngẫu của (MFCQ) cổ điển đã biết. Định lý 3.2.1 [12, Định lý 3.1](Điều kiện cần tối ưu cho bài toán hai cấp trơn) Giả sử (x, y) là một nghiệm tối ưu địa phương của bài toán hai cấp (3.35)– (3.39), trong đó tất cả các hàm đều trơn tại (x, y) và tại x, tương ứng. Giả sử bài toán hai cấp là partial calm tại (x, y) và các giả thiết chính quy của bài toán cấp dưới và cấp trên thỏa mãn tại (x, y) và tại x, tương ứng. Thêm vào đó hàm Ψ là 51 nửa liên tục trong (inner semicontinuous) tại (x, y). Khi đó tồn tại các số thực λ ≥ 0, λis với i = 1, . . . , p và s = 1, . . . , n + 1, µi với i = 1, . . . , p, ηs với s = 1, . . . , n+1, và αj với j = 1, . . . , k sao cho hệ sau thỏa mãn: ∇xF (x, y) + p∑ i=1 µi∇xgi(x, y)− λ n+1∑ s=1 ηs ( p∑ i=1 λis∇xgi(x, y) ) + k∑ j=1 αj∇Gj(x) = 0, (3.48) ∇yF (x, y) + λ∇yf(x, y) + p∑ i=1 µi∇ygi(x, y) = 0, (3.49) ∇yf(x, y) + p∑ i=1 λis∇xgi(x, y) = 0 ∀s = 1, . . . , n+ 1, (3.50) λis ≥ 0, λisgi(x, y) = 0, ∀i = 1, . . . , p, ∀s = 1, . . . , n+ 1, (3.51) µi ≥ 0, µigi(x, y) = 0, ∀i = 1, . . . , p, (3.52) ηs ≥ 0 ∀s = 1, . . . , n+ 1, n+1∑ s=1 ηs = 1, (3.53) αj ≥ 0, αjGj(x) = 0 ∀j = 1, . . . , k.(3.54) Chứng minh Vì (x, y) là một nghiệm tối ưu địa phương của bài toán hai cấp (3.35)–(3.39), do đó nó cũng là nghiệm tối ưu (optimistic) địa phương của bài toán một cấp (3.40) chứa hàm giá trị (3.41) và các ràng buộc (3.38), (3.39). Tóm lại (x, y) là một nghiệm tối ưu địa phương của bài toán sau: min x,y F (x, y) sao cho f(x, y)− ϕ(x) ≤ 0, gi(x, y) ≤ 0, i = 1, . . . , p, Gj(x) ≤ 0, j = 1, . . . , k. (3.55) trong đó hàm ϕ xác định như sau ϕ(x) = inf y {f(x, y)|gi(x, y) ≤ 0 khi i = 1, . . . , p}. (3.56) Ta có hàm giá trị (3.41) là lipschitz địa phương quanh x. Thật vậy, theo [17, Bổ đề 4.39] ánh xạ K(x) trong (3.38) là Lipschitz–like (xem chương 1, Mục 1.4) tại (x, y) 52 dưới giả thiết cấp dưới chính quy của (x, y). Do đó theo kết quả của [19, Định lý 5.2(i)] cộng với Ψ nửa liên tục trong tại (x, y) nên hàm f là Lipshitz địa phương tại (x, y). Áp dụng [23, Mệnh đề 3.3] cho bài toán (3.55), ta có điều kiện partial calmness tại (x, y) tương đương sự tồn tại λ > 0 sao cho (x, y) nghiệm (địa phương) đúng cho bài toán sau:  min x,y F (x, y) + λ(f(x, y)− ϕ(x)) sao cho gi(x, y) ≤ 0, i = 1, . . . , p, Gj(x) ≤ 0, j = 1, . . . , k. (3.57) là bài toán dạng Lipschitz. Áp dụng công thức nhân tử Lagrange mở rộng từ [18, Định lý 5.21(iii)], sử dụng dưới vi phân (1.18) (xem chương 1, Mục 1.4) đối với nghiệm tối ưu (x, y) trong bài toán (3.55) và công thức tổng dưới vi phân trong [18, Mệnh đề 1.107(ii)] và (1.18) cho trường hợp hàm trơn (khả vi chặt), chúng ta có các nhân tử không âm (λo, µ1, . . . , µp, α1, . . . , αk) và 6= 0 thỏa mãn: 0 ∈ λo∇F (x, y) + λoλ∇f(x, y) + ( λoλ∂(−ϕ)(x), 0 ) + p∑ i=1 µi∇gi(x, y) + k∑ j=1 ( αj∇Gj(x), 0 ) (3.58) và thỏa (3.52), (3.54). Do giả thiết chính quy tại (x, y) của lower và cấp trên, nên suy ra λo > 0, từ (3.58) ta suy ra dạng KKT bằng cách chọn λo = 1 : 0 ∈ ∇F (x, y) + λ∇f(x, y) + ( λ∂(−ϕ)(x), 0 ) + p∑ i=1 µi∇gi(x, y) + k∑ j=1 ( αj∇Gj(x), 0 ) (3.59) Ta có ∂(−ϕ)(x) ⊂ −co∂ϕ(x) trong đó ∂ϕ(x) và co∂ϕ(x) khác rỗng và compac (do ϕ Lipschitz địa phương tại x), hơn nữa áp dụng [20, Bổ đề 4] dưới giả thiết chính quy cấp dưới và điều kiện inner semicontinuous, ta có xấp xỉ trên của dưới vi phân 53 của hàm ϕ tại x : ∂ϕ(x) ⊂ ⋃ (λ1,...,λp)∈∧(x,y) [ ∇xf(x, y) + p∑ i=1 λi∇xgi(x, y) ] , (3.60) trong đó ∧(x, y) := { (λ1, . . . , λp) ∈ Rp|∇yf(x, y) + p∑ i=1 λi∇ygi(x, y) = 0, λi ≥ 0, λigi(x, y) = 0, i = 1, . . . , p } . (3.61) Lấy v ∈ co∂ϕ(x) và dùng định lý Carathéodory ta tìm được ηs ∈ R và vs ∈ Rn với s = 1, . . . , n+ 1 sao cho: v = n+1∑ s=1 ηsvs, n+1∑ s=1 ηs = 1, ηs ≥ 0, và vs ∈ ∂ϕ(x) s = 1, . . . , n+ 1. (3.62) Áp (3.60) vào (3.62) với mỗi vs ta tìm thấy λis sao cho: λis ≥ 0, λisgi(x, y), i = 1, . . . , p; ∇yf(x, y) + p∑ i=1 λis∇ygi(x, y) = 0, vs = ∇xf(x, y) + p∑ i=1 λis∇xgi(x, y) = 0, s = 1, . . . , n+ 1. Kết hợp tất cả từ (3.59), ta có (3.48)–(3.54) và có điều cần chứng minh. ¤ Nhận xét 3.2.1 [12, Nhận xét 3.5](Điều kiện tối ưu trong bài toán trơn khi inner semicontinuous không thỏa) Khi giả thiết inner semicontinuous không thỏa, nó được thay thế bởi inner semi- compact (đòi hỏi Ψ là uniformly bounded trong không gian hữu hạn chiều). Trong trường hợp hàm ϕ là Lipschitz địa phương tại x, áp dụng kết quả [19, Định lý 5.1(ii)]; [17, Định lý 5.38(ii), Bổ đề 4.35], ta có: ∂ϕ(x) ⊂ ⋃ y∈ψ(x) [ ⋃ (λ1,...,λp)∈∧(x,y) { ∂xf(x, y) + p∑ i=1 λi∂xgi(x, y) }] trong đó ∧(x, y) là tập nhân tử xác định bởi ∧(x, y) := { (λ1, . . . , λp) ∈ Rp|0 ∈ ∂yf(x, y) + p∑ i=1 λi∂ygi(x, y), 54 λi ≥ 0, λigi(x, y) = 0, i = 1, . . . , p } . Chúng ta áp dụng chứng minh của Định lý 3.2.1, thay (3.60) bằng bao hàm thức này thì có các số (λ, λis, µi, ηs, αi) như trong Định lý 3.2.1 và vectơ ys ∈ Ψ(x) với s = 1, . . . , n + 1 thỏa (3.53) và có (3.49), (3.52), (3.54) và thay y bởi ys có được (3.50), (3.51) và (3.48) thay thế bởi điều kiện sau: ∇xF (x, y) + λ∇xf(x, y)− λ n+1∑ s=1 ∇xf(x, ys) + p∑ i=1 µi∇xgi(x, y) −λ n+1∑ s=1 ηs( p∑ i=1 λis∇xgi(x, ys)) + k∑ j=1 αj∇Gj(x) = 0. (2) Bài toán hai cấp lồi, tuyến tính Trong mục này chúng ta sẽ nói về bài toán hai cấp với cấu trúc lồi cho bài toán cấp dưới hoặc cho cả hai bài toán cấp dưới và cấp trên. Đây là dạng bài đã xét ở mục 3.1, tuy nhiên lần này ta tiếp cận hướng khác. Các kết quả thu được thì khác so với trường hợp bài toán trơn và bài toán lipschitz. Do đó các điều kiện tối ưu cũng khác so với bài toán trơn và bài toán Lipschitz ở mục sau. Sau cùng chúng ta xét trường hợp đặc biệt khi bài toán cấp dưới tuyến tính. Thông thường khi các hàm không trơn, chúng ta hãy xét bài toán (3.35)–(3.39) lồi. Tính lồi ở đây là lồi hoàn toàn với tất cả các biến x và y. Bây giờ ta phải thay đổi các giả thiết chính quy (3.45) và (3.47) sao cho hợp lý. Chúng ta nói bài toán hai cấp lồi là chính quy cấp dưới nếu với mỗi x ∈ Rn với K(x) 6= ∅ trong (3.38) thì có yx ∈ Rm sao cho gi(x, yx) < 0, i = 1, . . . , p. (3.63) Tương tự, chúng ta nói bài toán hai cấp lồi là chính quy cấp trên nếu có x˜ ∈ Rn với Ψ(x˜) 6= ∅ thỏa điều kiện Gj(x˜) < 0 ∀j = 1, . . . , k. (3.64) 55 Định lý 3.2.2 [12, Định lý 4.1](Điều kiện tối ưu cần cho bài toán hai cấp lồi) Giả sử (x, y) là một nghiệm tối ưu của (3.35)–(3.39), trong đó mọi hàm đều là hàm lồi với các biến tương ứng. Giả sử rằng bài toán hai cấp là partially calm tại (x, y) và thỏa mãn các giả thiết chính quy (3.63), (3.64) cho bài toán lower và cấp trên. Giả sử Ψ là nửa compac trong (inner semicompact) tại x (điều này có được khi Ψ bị chặn đều (uniformly bounded) quanh x). Khi đó tồn tại λ > 0, (µ1, . . . , µp) ∈ Rp thỏa (3.52), (α1, . . . , αk) ∈ Rk thỏa (3.54), và y˜ ∈ Ψ(x) và (λ1, . . . , λp) ∈ Rp sao cho hệ sau thỏa: 0 ∈ ∂xF (x, y) + λ ( ∂xf(x, y)− ∂xf(x, y˜) ) + p∑ i=1 µi∂xgi(x, y) −λ p∑ i=1 λi∂xg(x, y˜) + k∑ j=1 αj∂Gj(x), (3.65) 0 ∈ ∂yF (x, y) + λ∂yf(x, y) + p∑ i=1 µi∂ygi(x, y), (3.66) 0 ∈ ∂yf(x, y˜) + p∑ i=1 λi∂ygi(x, y˜), (3.67) λi ≥ 0, λigi(x, y˜) = 0 ∀i = 1, . . . , p, (3.68) trong đó ∂, ∂x, ∂y lần lượt là dưới vi phân toàn bộ, cục bộ theo x, cục bộ theo y của các hàm lồi. Hơn nữa nếu Ψ là nửa liên tục trong tại (x, y) thì ta có thể cho y˜ = y vào hệ (3.65), (3.67), và (3.68). Chứng minh Đầu tiên ta có: (i) f, gi lồi suy ra ϕ lồi (ii) f, gi liên tục Lipschitz (do lồi và liên tục) cộng với chính quy cấp dưới nên ϕ là Lipschitz địa phương tại x (tham khảo [19, Định lý 5.1] và [17, Bổ đề 4.43]) Dùng tính partial calmness tại (x, y), theo Định lý 3.2.1 ở trên ta suy ra (x, y) là nghiệm tối ưu địa phương của bài toán (3.57), bài toán (3.57) trong trường hợp này là Lipschitz nhưng không lồi (vì hàm mục tiêu là hiệu hai hàm lồi). Tuy nhiên, 56 áp dụng công thức nhân tử mở rộng từ [18, Định lý 3.21(iii)] và công thức dưới vi phân trong cho hàm Lipschitz trong [17, Định lý 2.23(c)], ta suy ra: 0 ∈ λo∂F (x, y)+λoλ∂f(x, y)+ ( λoλ(−ϕ)(x), 0 ) + p∑ i=1 µi∂gi(x, y)+ k∑ j=1 αj ( ∂Gj(x), 0 ) , (3.69) trong đó tất cả nhân tử λo, µi, αj đều không âm và không đồng thời bằng 0 và thỏa (3.52), (3.54) Tương tự như trong chứng minh của Định lý 3.2.1, bởi 2 giả thiết chính quy cho bài toán lồi (3.63), (3.64) và (3.52), (3.54) cho µi, αj và (λo, µi, αj) 6= 0 nên ta suy ra λo > 0, và do đó ta suy ra điều kiện dạng KKT bằng cách cho λo = 1 : 0 ∈ ∂F (x, y) + λ∂f(x, y) + ( λ(−ϕ)(x), 0 ) + p∑ i=1 µi∂gi(x, y) + k∑ j=1 αj ( ∂Gj(x), 0 ) , (3.70) Theo [17, Bổ đề 3.44], ta có tính chất hàm lồi liên tục ψ(x, y) : ∂ψ(x, y) ⊂ ∂xψ(x, y)× ∂yψ(x, y). (3.71) áp dụng tính chất này vào dạng KKT ở trên, ta được (3.66) thỏa và 0 ∈ ∂xF (x, y) + λ∂xf(x, y) + λ∂(−ϕ)(x) + p∑ i=1 µi∂xg(x, y) + k∑ j=1 αj∂G(x). (3.72) Ngoài ra, do tính chất bao lồi của dưới vi phân (1.19) và tính lồi của dưới gradient tập ∂ϕ(x) (vì hàm ϕ lồi (xem (i)), nên ta có ∂(−ϕ)(x) ⊂ −∂ϕ(x). (3.73) Áp dụng kết quả trong [20, Định lý 8] (liên quan đến tính inner semicompact của hàm ϕ cho bởi (3.56) và tính chất (3.71)) ta có: ∂ϕ(x) ⊂ ⋃ y∈ψ(x) [ ⋃ (λ1,...,λp)∈∧(x,y) { ∂xf(x, y) + p∑ i=1 λi∂xgi(x, y) }] (3.74) trong đó Ψ(x) xác định bởi (3.32) và tập nhân tử xác định bởi: ∧(x, y) := { (λ1, . . . , λp) ∈ Rp|0 ∈ ∂yf(x, y) + p∑ i=1 λi∂ygi(x, y), λi ≥ 0, λigi(x, y) = 0, i = 1, . . . , p } . (3.75) 57 Kết hợp (3.72)–(3.75) ta suy ra (3.65), (3.67), (3.68); cùng với (3.66) thỏa phía trên, ta có điều cần chứng minh. Nếu Ψ(x) = {y} là singleton thì rõ ràng y˜ = y. Hơn nữa nếu Ψ inner semicon- tinuous tại (x, y) thì ta cũng thay y˜ = y và ta có (3.65)–(3.68) gọn hơn. ¤ Bây giờ chúng ta xét bài toán (3.35)–(3.39) vừa trơn vừa lồi. Bằng cách kết hợp cả hai Định lý 3.2.1 và Định lý 3.2.2. Ta có Định lý 3.2.3 [12, Định lý 4.4](Điều kiện tối ưu cần cho bài toán hai cấp trơn và lồi ở bài toán cấp dưới) Giả sử (x, y) là một nghiệm tối ưu địa phương của bài toán hai cấp (3.35)–(3.39), trong đó tất cả các hàm F,Gj, f, gi đều khả vi liên tục quanh (x, y), và x tương ứng ; hàm ϕ xác định bởi (3.41) hữu hạn tại x, và hàm f, gi lồi. Giả sử ánh xạ Ψ là nửa compac trong tại x và bài toán hai cấp được xét là partially calm tại (x, y) và (x, y) là chính quy cấp dưới theo (3.45) và x là chính quy cấp trên theo (3.47). Khi đó có λ > 0, (µ1, . . . , µp) ∈ Rp thỏa (3.52), (α1, . . . , αk) ∈ Rk thỏa (3.54), và (λ1, . . . , λp) ∈ Rp sao cho ta có (3.49) và hệ sau: ∇xF (x, y) + p∑ i=1 (µi − λλi)∇xgi(x, y) + k∑ j=1αj∇Gj(x) = 0, (3.76) ∇yf(x, y) + p∑ i=1 λi∇ygi(x, y) = 0, (3.77) λi ≥ 0, λigi∇xgi(x, y) = 0, ∀i = 1, . . . , p. (3.78) Bây giờ chúng ta xét điều kiện tối ưu cho bài toán hai cấp với bài toán cấp dưới là tuyến tính. Xét bài toán hai cấp (3.35)–(3.39) với cấp dưới (3.37) có dạng min cTy sao cho Ay ≤ x, (3.79) 58 trong đó vecto c ∈ Rn và ma trận A ∈ Rn×m cố định. Khi đó bài toán này là lồi. Áp dụng Định lý 3.2.3, nếu (x, y) là một nghiệm tối ưu với Ψ(x) := Argmin y {cTy|Ay ≤ x} và X xác định như (3.39) ta có hệ sau: ∇xF (x, y)− p∑ i=1 (µi − λβi) + k∑ j=1 ∇Gj(x) = 0, ∇yF (x, y) + λc+ p∑ i=1 µia i = 0, c+ βTA = 0, β ≥ 0, βT (Ay − x) = 0, µ ≥ 0, µT (Ay − x) = 0, α ≥ 0, αTG(x) = 0. trong đó λ > 0, β = (β1, . . . , βp) ∈ Rp, µ = (µ1, . . . , µp) ∈ Rp, α = (α1, . . . , αk) ∈ Rk và ai là hàng thứ i của ma trận A. (3) Bài toán hai cấp Lipschitz Bài toán hai cấp Lipschitz là bài toán mà tất cả các hàm số trong cả hai bài toán cấp dưới và cấp trên đều liên tục Lipschitz tại nghiệm tối ưu địa phương. Công cụ chính để sử dụng trong bài toán này là dưới vi phân của hàm liên tục Lipschitz địa phương dạng (1.18). Tương tự như mục trước, chúng ta phải thay đổi các giả thiết chính quy cho phù hợp. Cho điểm (x, y) ∈ Rn × Rm thỏa các ràng buộc bất đẳng thức (3.38) của cấp dưới, I(x, y) có trong (3.44). Điểm đó được gọi là chính quy cấp dưới nếu mệnh đề sau thỏa mãn : [ ∑ i∈I(x,y) λivi = 0, λi ≥ 0 ] =⇒ [ λi = 0 ∀i ∈ I(x, y) ] (3.80) 59 trong đó (ui, vi) ∈ ∂giI(x, y) với ui ∈ Rn khi i ∈ I(x, y). Tương tự cho điểm x ∈ Rn thỏa các ràng buộc (3.39) của cấp trên, J(x) có trong (3.46). Điểm đó được gọi là chính quy cấp trên nếu mệnh đề sau thỏa mãn :[ 0 ∈ ∑ j∈J(x) λj∂Gj(x), λj ≥ 0 ] =⇒ [ λj = 0 khi j ∈ J(x) ] . (3.81) Bây giờ chúng ta lại thiết lập điều kiện cần cho bài toán này. Ở hai bài toán vừa rồi chúng ta đã xét riêng các khái niệm nửa liên tục trong và nửa compact trong. Đối với bài toán này chúng ta xét cả hai trường hợp ấy. Định lý 3.2.4 [12, Định lý 5.1](Điều kiện cần cho bài toán hai cấp Lipschitz) Giả sử (x, y) là một nghiệm tối ưu địa phương của bài toán bilvel (3.35)–(3.39), và partially calm tại điểm này. Giả sử hàm f,Gj, j = 1, . . . , k là liên tục Lischitz địa phương tại (x, y), x và x thỏa chính quy cấp trên. Cộng với: (i) Giả sử thêm rằng Ψ là nửa liên tục trong tại (x, y), và điểm này thỏa chính quy cấp dưới. Các hàm f, gi, i = 1, . . . , p là liên tục Lipschitz địa phương tại (x, y). Khi đó tồn tại λ > 0, (µ1, . . . , µp) ∈ Rp thỏa (3.52), (η1, . . . , ηn+1) ∈ Rn+1 thỏa (3.53), (α1, . . . , αk) ∈ Rk thỏa (3.54), λis, i = 1, . . . , p ; s = 1, . . . , n + 1 thỏa (3.51) và (u1, . . . , un+1) ∈ Rn+1 sao cho hệ sau thỏa: (us, 0) ∈ ∂f(x, y) + p∑ i=1 λis∂gi(x, y) ∀s = 1, . . . , n+ 1,(3.82) ( λ n+1∑ s=1 ηsus, 0 ) ∈ ∂F (x, y) + λ∂f(x, y) + p∑ i=1 µi∂gi(x, y) + ( k∑ j=1 αj∂Gj(x), 0 ) (3.83) (ii) Giả sử thêm rằng Ψ là nửa compac trong tại x, với mỗi vecto y ∈ Ψ(x) cặp (x, y) là chính quy cấp dưới và các hàm f, gi liên tục Lipschitz địa phương tại (x, y). Khi đó tồn tại λ > 0, (µ1, . . . , µp) ∈ Rp thỏa (3.52), (η1, . . . , ηn+1) ∈ Rn+1 thỏa (3.53), (α1, . . . , αk) ∈ Rk thỏa (3.54), cùng với ys ∈ Ψ(x), us ∈ Rn, và λis với i = 1, . . . , p và s = 1, . . . , n + 1 sao cho bao hàm thức (3.83) thỏa mãn và hệ sau 60 thỏa: λis ≥ 0, λisgi(x, ys) = 0 ∀i = 1, . . . , p, s = 1, . . . , n+ 1, (3.84) (us, 0) ∈ ∂f(x, ys) + p∑ i=1 λis∂gi(x, ys)∀s = 1, . . . , n+ 1. (3.85) Chứng minh Xét trường hợp (i) khi ánh xạ Ψ là inner semicontinuous tại (x, y). Theo Định lý 3.2.1, dưới giả thiết điều kiện partially calm, đối với bài toán (3.57) có nghiệm tối ưu địa phương (x, y). Áp dụng [6, Bổ đề 4.34], [19, Định lý 5.2(i)] suy ra K(.) là Lipschitz–like tại (x, y), mà tại điểm này thỏa giả thiết cấp dưới chính quy nên ϕ là hàm Lipschitz địa phương, và do đó bài toán (3.57) là bài toán Lipschitz. Áp dụng tiếp [18, Định lý 5.21(ii)] và công thức tổng dưới vi phân trong[17, Định lý 2.23] ta có điều kiện cần tối ưu cho bài toán (3.57) sau đây: tồn tại các nhân tử (λo, µ1, . . . , µp, α1, . . . , αk) 6= 0 sao cho λo ≥ 0 và µi, αj thỏa mãn (3.52), (3.54) tương ứng; và thỏa dạng Fritz-John. Ta chứng minh được dưới giả thiết chính quy, suy ra λo > 0 , chọn λo = 1, với ∂f(.) là dưới vi phân dạng (1.18), ta có dạng KKT sau đây: 0 ∈ ∂F (x, y)+λ∂f(x, y) + ( λ∂(−ϕ)(x), 0 ) + p∑ i=1 µigi(x, y) + k∑ j=1 ( αj∂Gj(x), 0 ) . (3.86) Áp dụng [20, Định lý 8] cho trường hợp hàm Lipschitz địa phương ϕ trong bài toán cấp dưới, ta có: ∂ϕ(x) ⊂ ⋃ (λ1,...,λp) { u ∈ Rn | (u, 0) ∈ ∂f(x, y) + µigi(x, y), λi ≥ 0, λigi(x, y) = 0, i = 1, . . . , p } . (3.87) Bây giờ ta kết hợp (3.34), và thay (3.87) vào (3.86) ta suy ra được (3.82), (3.83) dưới trọng số ηs lồi thỏa (3.53) trong Định lý 3.2.1. Như vậy ta có (i). 61 Xét trường hợp (ii) khi ánh xạ Ψ inner semicompact, tương tự như (i), áp dụng [19, Định lý 5.2(ii)] và [20, Định lý 8] ta suy ra: ∂ϕ(x) ⊂ ⋃ y∈ψ(x) ⋃ (λ1,...,λp) { u ∈ Rn | (u, 0) ∈ ∂f(x, y) + p∑ i=1 λigi(x, y), λi ≥ 0, λigi(x, y) = 0, i = 1, . . . , p } . Áp dụng tiếp các Định lý 3.2.1, Định lý 3.2.2 và Nhận xét 3.2.1, ta có (ii). ¤ 3.3 Điều kiện tối ưu sử dụng dưới vi phân Clarke Các kết quả trong phần này có liên quan đến bài báo [22, 23, 16]. Các khái niệm có sử dụng trong chương 1, Mục 1.2. Xét lớp bài toán tối ưu hai cấp có dạng như sau: (BLPP) minF (x, y) sao cho y ∈ Ψ(x), Gk(x, y) ≤ 0, k ∈ K trong đó Ψ(x) là tập nghiệm của bài toán cấp dưới: (Px) min y f(x, y) sao cho gi(x, y) ≤ 0 i ∈ I trong đó I = {1, . . . , p}, K = {1, . . . , q} và các hàm F, f, gi : Rn ×Rm → R là khả vi liên tục. Hàm Gk : Rn × Rm → R cũng khả vi liên tục. Chúng ta không xét đến các ràng buộc đẳng thức. Bây giờ ta cũng tìm cách để viết lại bài toán (BLPP). Trước tiên, ta xây dựng hàm giá trị mở rộng của bài toán cấp dưới (Px) ϕ : Rn → R xác định bởi: ϕ(x) := inf y {f(x, y)|gi(x, y) ≤ 0, i ∈ I}, lưu ý là inf{∅} = +∞. Khi đó bài toán (BLPP) được viết lại dưới dạng bài toán một cấp (one level) sau: 62 (SP)ϕ min F (x, y) sao cho f(x, y)− ϕ(x) ≤ 0, gi(x, y) ≤ 0 i ∈ I, Gk(x, y) ≤ 0 k ∈ K. Bài 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