Luận văn Điều kiện cần và đủ cho nghiệm hữu hiệu của bài toán tối ưu đa mục tiêu qua dưới vi phân suy rộng

hỉ ra rằng, nếu f là liên tục, tựa lồi và có một dưới vi phân suy rộng dưới lồi trên một tập lồi Q thì với mỗi x, y ∈ Q, f(x) ≤ f(y)⇒ ∃ξ(n) ∈ ∂∗f(y), lim n→∞(ξ (n), x− y) ≤ 0. Nếu f có một dưới vi phân suy rộng chính quy trên tại x¯ thì ta có mệnh đề sau đây. Mệnh đề 1.1.1 Giả sử f có một dưới vi phân suy rộng chính quy trên ∂∗f(x¯) tại x¯ và f tựa lồi 6tại x¯ ∈ Q theo tập lồi Q. Khi đó, ∀x ∈ Q, f(x) ≤ f(x¯)⇒ ∀ξ ∈ ∂∗f(x¯), 〈ξ, x− x¯〉 ≤ 0. Chứng minh Vì f là tựa lồi tại x¯ theo Q, với mỗi x ∈ Q thỏa mãn f(x) ≤ f(x¯), ta có f+(x¯;x− x¯) ≤ 0. Do tính chính quy trên của dưới vi phân suy rộng ∂∗f(x¯), với mỗi x ∈ Q thỏa mãn f(x) ≤ f(x¯), ta có sup ξ∈∂∗f(x¯) 〈ξ, x− x¯〉 = f+(x¯;x− x¯) ≤ 0. Từ đó, ta có điều phải chứng minh. 2 Theo [20], hàm thực mở rộng f có một dưới vi phân suy rộng dưới lồi ∂∗f(x) trên Q được gọi là giả lồi tiệm cận dưới trên Q nếu với mỗi x, y ∈ Q, ∃ξ(n) ∈ ∂∗f(x), lim n→∞ 〈 ξ(n), y − x 〉 ≥ 0⇒ f(y) ≥ f(x). Hàm giá trị thực mở rộng f có một dưới vi phân suy rộng ∂∗f(x¯) tại x¯ được gọi là giả lồi tiệm cận tại x¯ theo Q nếu, với mỗi x ∈ Q ta có ∃ξ(n) ∈ conv∂∗f(x¯), lim n→∞ 〈 ξ(n), x− x¯ 〉 ≥ 0⇒ f(x) ≥ f(x¯). trong đó conv kí hiệu bao lồi Ví dụ 1.1.3 Cho f, g : R→ R f(x) :=  x, khi x ≤ 0,1 2x, khi x > 0, g(x) :=  x, khi x ∈ Q, 2x, khi x ∈ (R\Q) ∩ ]−∞, 0] , 1 2x, khi x ∈ (R\Q) ∩ [0,∞[ . 7Khi đó một dưới vi phân suy rộng của f tại 0 là ∂∗f(0) = { 1 2 ; 1 } và f là giả lồi tiệm cận tại 0 theo Q = R. Một dưới vi phân suy rộng dưới của g tại 0 là ∂∗g(0) = { 1 2 ; 2 } và g là giả lồi tiệm cận dưới tại 0 theo Q = R. Cho K là một nón lồi đóng trong Rn và K∗ := {ξ ∈ Rn : 〈ξ, x〉 ≥ 0,∀x ∈ K} là nón cực không âm của K. Cho f : Q ⊆ Rn → Rm và như vậy f = (f1, ..., fm). Giả sử fk có một dưới vi phân suy rộng ∂ ∗fk (x¯) tại x¯. Hàm f được gọi là giả lồi K - tiệm cận vô hướng tại x¯ theo Q nếu với mỗi λ ∈ K∗, hàm λTf là giả lồi tiệm cận tại x¯ trên Q. Các nón tiếp tuyến Bouligand và Clarke của tập C ⊆ Rn tại một điểm x¯ ∈ C được định nghĩa tương ứng bởi K(C, x¯) := {v ∈ Rn : ∃ vn → v,∃ tn ↓ 0 sao cho x¯+ tnvn ∈ C, ∀n} , T (C, x¯) := {v ∈ Rn : ∀ xn ∈ C, xn → x¯, ∀ tn ↓ 0 ,∃ vn → v sao cho xn + tnvn ∈ C, ∀n} . Nón các phương đạt được của C tại x¯ ∈ C là: A(C, x¯) = { v ∈ Rn : ∃δ > 0,∃γ : [0, δ]→ Rn sao cho γ(0) = x¯, γ(t) ∈ C, ∀t ∈ ]0, δ] , γ,(0) = lim t↓0 γ(t)−γ(0) t = v } . Nón pháp tuyến Clarke của C tại x¯ là N(C, x¯) = {ξ ∈ Rn : 〈ξ, v〉 ≤ 0 ∀ v ∈ T (C, x¯)} . Chú ý rằng các nón T (C, x¯) và N(C, x¯) là không rỗng, đóng và lồi; N(C, x¯) = −T ∗(C, x¯) và T (C, x¯) ⊆ K(C, x¯). Trong trường hợp C lồi thì T (C, x¯) = K(C, x¯). 1.1.2. Các dưới vi phân Clarke-Rockafellar, Clarke, Michel-Penot Sau đây ta sẽ thấy rằng các dưới vi phân Clarke-Rockafellar, Clarke, Michel- Penot,...đều là dưới vi phân suy rộng. 8Cho hàm f : Rn → R¯ là hữu hạn tại điểm x ∈ X . Nếu f là nửa liên tục dưới tại x thì dưới đạo hàm trên Clarke - Rockafellar của f tại x theo v được xác định bởi: f ↑ (x, v) = lim sup x′→f t↓0 x inf v′→v [f (x′ + tv′)− f (x′)] /t, trong đó x′ → fx nghĩa là x′ → x và f (x′)→ f (x) . Nếu f là nửa liên tục trên tại x thì dưới đạo hàm dưới Clarke-Rockafellar của f tại x theo v được xác định bởi f ↓ (x, v) = lim inf x′→ t↓0 f x sup v′→v [f (x′ + tv′)− f (x′)] /t. Nếu f là liên tục tại x thì x′ → fx trong các định nghĩa trên trở thành x′ → x. Dưới gradient suy rộng trên và dưới của f tại x được cho bởi ∂↑f (x) = { x∗ ∈ X∗ : 〈x∗, v〉 ≤ f ↑ (x, v) ,∀v ∈ X} , ∂↓f (x) = { x∗ ∈ X∗ : 〈x∗, v〉 ≥ f ↓ (x, v) ,∀v ∈ X} . Nếu f ↑ (x, 0) > −∞ thì ∂↑f (x) là tập con không rỗng, lồi, đóng của Rn và với mỗi v ∈ Rn, f ↑ (x, v) = sup x∗∈ ∂↑f(x) 〈x∗, v〉 . Tương tự, nếu f ↓ (x, 0) < ∞ thì ∂↓f (x) là tập con không rỗng, lồi, đóng của Rn và với mỗi v ∈ Rn, f ↓ (x, v) = inf x∗∈ ∂↓f(x) 〈x∗, v〉 . Nếu f là Lipschitz địa phương tại x thì f ↑ (x; v) = f o (x, v) , f ↓ (x; v) = fo (x, v) , trong đó, f o (x, v) = lim sup x′→ t↓0 x [f (x′ + tv)− f (x′)] /t, fo (x, v) = lim inf x′→ t↓0 x [f (x′ + tv)− f (x′)] /t. 9là các đạo hàm theo phương suy rộng trên và dưới Clarke của f tại x theo phương v. Dưới vi phân suy rộng Clarke được xác định bởi ∂of (x) = {x∗ ∈ X∗ : 〈x∗, v〉 ≤ f o (x, v) ,∀v ∈ X} . Hơn nữa, f o (x, v) = max x∗∈ ∂of(x) 〈x∗, v〉 , fo (x, v) = min x∗∈ ∂of(x) 〈x∗, v〉 . Do đó, nếu f là Lipschitz địa phương tại x thì ∂of (x) là dưới vi phân suy rộng của f tại x, bởi vì f− (x, v) ≤ f o (x, v) , f+ (x, v) ≥ fo (x, v) . với mỗi v ∈ X . Tương tự, nếu f là Lipschitz địa phương tại x thì đạo hàm theo phương trên và dưới Michel – Penot của f tại x tương ứng được cho bởi f♦ (x, v) = sup z∈X lim sup λ↓0 λ−1 [f (x+ λz + λv)− f (x+ λz)] , f♦ (x, v) = inf z∈X lim inf λ↓0 λ−1 [f (x+ λz + λv)− f (x+ λz)] . Khi đó dưới vi phân Michel – Penot được xác định bởi ∂♦f (x) := { x∗ ∈ Rn : f♦ (x, v) ≥ 〈x∗, v〉 ,∀v ∈ Rn} . Đạo hàm theo phương trên và dưới Michel – Penot f♦ (x, .) và f♦ (x, .) là dưới tuyến tính, hữu hạn, ∂♦f (x) là compact lồi f♦ (x, v) = max x∗∈ ∂♦f(x) 〈x∗, v〉 , f♦ (x, v) = min x∗∈ ∂♦f(x) 〈x∗, v〉 . Do đó, ∂♦f (x) cũng là một dưới vi phân suy rộng của f tại x, bởi vì f− (x, v) ≤ f♦ (x, v) và f+ (x, v) ≥ f♦ (x, v) với mỗi v ∈ Rn. Ví dụ 1.1.4 Định nghĩa f : R2 → R xác định bởi f (x, y) = |x| − |y| . 10 Khi đó ∂∗f (0) = {(1,−1) , (−1, 1)} . là một dưới vi phân suy rộng của f tại 0. Ta có ∂♦f (0) = ∂of (0) = co ({(1, 1) , (−1, 1) , (1,−1) , (−1,−1)}) . Chú ý rằng co (∂∗f (0)) ⊆ ∂♦f (0) = ∂of (0) . 1.1.3. Dưới vi phân suy rộng chính quy, dưới vi phân suy rộng tối thiểu Rõ ràng từ định nghĩa ta thấy dưới vi phân suy rộng trên và dưới không duy nhất. Vì vậy trong phần này chúng ta sẽ trình bày các điều kiện về tính duy nhất và tối thiểu của dưới vi phân suy rộng trên hoặc dưới. Trước tiên ta trình bày khái niệm dưới vi phân suy rộng chính quy trên và dưới. Hàm f : Rn → R được gọi là có một dưới vi phân suy rộng chính quy trên ∂∗f (x) ⊆ Rn tại x nếu ∂∗f (x) là tập đóng và với mỗi v ∈ Rn, f+ (x, v) = sup x∗∈∂∗f(x) 〈x∗, v〉 . Tương tự, hàm f được gọi là có một dưới vi phân suy rộng chính quy dưới ∂∗f (x) ⊆ Rn tại x nếu ∂∗f (x) là tập đóng và với mỗi v ∈ Rn. f− (x, v) = inf x∗∈∂∗f(x) 〈x∗, v〉 . Rõ ràng, mỗi dưới vi phân suy rộng chính quy trên (dưới) của f tại x là một dưới vi phân suy rộng của f tại x. Trong mệnh đề sau chúng ta sẽ trình bày mối liên hệ giữa tính khả vi và tính chính quy. Mệnh đề 1.1.2 Hàm f : Rn → R là khả vi Gâteaux tại x0 nếu và chỉ nếu f là khả vi theo phương tại x0 và f có một dưới vi phân suy rộng chính quy trên và chính quy 11 dưới tại x0. Chứng minh Nếu f là khả vi Gâteaux tại x0 thì nó khả vi theo phương và đạo hàm Gâteaux {f ′ (x0)} và là một dưới vi phân suy rộng chính quy trên và dưới của f tại x0. Ngược lại, nếu f khả vi theo phương tại x0 và nếu ∂ ∗f (x0) là một dưới vi phân suy rộng chính quy trên và dưới thì với mỗi v ∈ Rn. f ′ (x0, v) = f− (x0, v) = inf x∗∈∂∗f(x) 〈x∗, v〉 = f+ (x0, v) = sup x∗∈∂∗f(x) 〈x∗, v〉 . Do đó ∂∗f (x0) là tập một phân tử và vì vậy f khả vi Gâteaux tại x0. 2 Ta nói rằng ∂∗f (x) là dưới vi phân suy rộng tối thiểu (trên/dưới) của f tại x nếu không tồn tại một tập đóng C (x) trong Rn sao cho C (x) ⊂ ∂∗f (x) , C (x) 6= ∂∗f (x) và C (x) là một dưới vi phân suy rộng (trên/dưới) của f tại x. Ký hiệu tập các điểm cực biên của dưới vi phân suy rộng ∂∗f (x) của f tại x là Ext (∂∗f (x)). Mệnh đề 1.1.3 Giả sử rằng f : Rn → R có một dưới vi phân suy rộng chính quy compăc trên (dưới) ∂∗f (x) tại x. Khi đó Ext (co (∂∗f (x))) là dưới vi phân suy rộng chính quy trên (dưới) tối thiểu duy nhất của f tại x. Chứng minh Cho A ⊂ Rn có một dưới vi phân suy rộng chính quy trên của f tại x. Khi đó, với mỗi v ∈ Rn, f+ (x, v) = sup x∗∈∂∗f(x) 〈x∗, v〉 = sup x∗∈A 〈x∗, v〉 . Nên A là tập con đóng và bị chặn của Rn với co (∂∗f (x)) = co (A) . Khi đó, Ext (co (∂∗f (x))) = Ext (co (A)) . 12 Chúng ta chỉ ra rằng Ext (co (∂∗f (x))) ⊆ A. Thật vậy hiển nhiên ta có Ext (co (A)) ⊆ Ext (A) . Do đó, Ext (co (∂∗f (x))) = Ext (co (A)) ⊆ Ext (A) ⊂ A. Bởi vì A là tập đóng, ta có Ext (co (∂∗f (x))) ⊆ A. Mặt khác bởi vì, ∂∗f (x) là một dưới vi phân suy rộng chính quy compăc trên, cho nên Ext (co (∂∗f (x))) cũng là dưới vi phân suy rộng chính quy compăc trên của f tại x. Do đó, Ext (co (∂∗f (x))) là dưới vi phân suy rộng chính quy tối thiểu trên duy nhất của f tại x. Chứng minh tương tự cho trường hợp f có dưới vi phân suy rộng chính quy dưới. 2 Ta nói hàm f hữu hạn và liên tục tại x là chính quy trên tại x nếu với mỗi v ∈ Rn, f+ (x, v) = f ↑ (x, v) . Tương tự hàm f là chính quy dưới tại x nếu với mỗi v ∈ Rn, f− (x, v) = f ↓ (x, v) . Chú ý rằng, nếu f : Rn → R là Lipschitz địa phương trên Rn và nếu với mỗi v ∈ Rn, f+ (., v) [f− (., v)] là nửa liên tục trên [dưới], thì với mỗi x ∈ Rn và v ∈ Rn, f+ (x, v) = f o (x, v) = f ↑ (x, v) [ f− (x, v) = fo (x, v) = f ↓ (x, v) ] , cho nên, f là chính quy trên [dưới] tại x (xem [6]). Nếu f ↑ (x, 0) > −∞ và nếu f là chính quy trên tại x thì ∂↑f (x) khác rỗng, lồi, đóng của Rn và với mỗi v ∈ Rn, f+ (x, v) = f ↑ (x, v) = sup x∗∈∂↑f(x) 〈x∗, v〉 . 13 Do đó, ∂↑f (x) là một dưới vi phân suy rộng chính quy trên của f tại x. Tương tự, nếu f ↓ (x, 0) <∞ và f chính quy dưới tại x thì ∂↓f (x) khác rỗng, lồi, đóng của Rn và với mỗi v ∈ Rn, f− (x, v) = f ↓ (x, v) = inf x∗∈∂↓f(x) 〈x∗, v〉 . Cho nên ∂↓f (x) là dưới vi phân suy rộng chính quy dưới của f tại x. Nếu f : Rn → R là Lipschitz địa phương trên Rn và chính quy trên tại x, thì với mỗi v ∈ Rn, f+ (x, v) = f ↑ (x, v) = f o (x, v) = max x∗∈∂of(x) 〈x∗, v〉 . Do đó, Ext (∂of (x)) là dưới vi phân suy rộng chính quy tối thiểu trên duy nhất của f tại x. Chú ý rằng, nếu f là lồi thì Ext (∂f (x)) là dưới vi phân suy rộng chính quy tối thiểu trên duy nhất của f tại x, trong đó ∂f (x) := {x∗ ∈ X∗ : f (y)− f (x) ≥ 〈x∗, y − x〉 , ∀y ∈ Rn} là dưới vi phân lồi của f tại x. 1.2 Điều kiện cần Fritz John cho cực tiểu Pareto yếu Phần này trình bày các điều kiện cần Fritz John cho cực tiểu yếu địa phương dưới ngôn ngữ dưới vi phân suy rộng chính quy trên và bán chính quy trên. Xét bài toán tối ưu đa mục tiêu (P) sau: min f (x), g (x) ≤ 0, h (x) = 0, x ∈ C, trong đó f , g, h tương ứng là các ánh xạ từ Rn vào Rr, Rm, Rl; C là một tập con của Rn. Khi đó f = (f1, ..., fr), g = (g1, ..., gm), h = (h1, ..., hl), trong đó f1, ..., fr, g1, ..., gm, h1, ..., hl là những hàm giá trị thực mở rộng xác định trên 14 Rn. Với x, y ∈ Rn, ta viết x ≤ y nếu xi ≤ yi , (i = 1, ..., n). Như vậy g(x) ≤ 0 có nghĩa là gi(x) ≤ 0, (i = 1, ...,m) và h(x) = 0 có nghĩa là hj(x) = 0, (j = 1, ..., l). Đặt I = {1, ...,m}, J = {1, ..., r}, L = {1, ..., l}. Chú ý rằng điều kiện cần dưới ngôn ngữ dưới vi phân suy rộng cho bài toán với ràng buộc tập hoặc ràng buộc bất đẳng thức đã được nghiên cứu bởi Dutta-Chandra [7,8] và có ràng buộc đẳng thức và bất đẳng thức đã được nghiên cứu bởi Luu [15]. Kí hiệuM là tập chấp nhận được của bài toán (P): M := {x ∈ C : g(x) ≤ 0, h(x) = 0} , và I(x¯) := {i ∈ I : g(x¯) = 0} , H := {x ∈ Rn : h(x) = 0} . Mở rộng của định lý Ljusternik cổ điển của Jiménez-Novo trong [11] sẽ được sử dụng để dẫn điều kiện cần tối ưu. Mệnh đề 1.2.1 [11] Giả sử rằng (a) C là tập lồi và x¯ ∈ H ∩ C; (b) h liên tục trong một lân cận của x¯ và khả vi Fréchet tại x¯ với đạo hàm Fréchet là ∇h(x¯); (c) Điều kiện chính quy (RC) sau đây đúng: 0 ∈ ∑ j∈L γj∇hj(x¯) +N(C, x¯)⇒ γ1 = ... = γl = 0. Khi đó, A(H ∩ C; x¯) = T (H ∩ C; x¯) = (ker∇h(x¯)) ∩ T (C; x¯) = cl [(ker∇h(x¯)) ∩ cone(C − x¯)] , trong đó cl kí hiệu bao đóng. 15 Nhận xét 1.2.1 Nếu C = Rn, h thuộc lớp C1 trong một lân cận của x¯ và ∇h1(x¯), ...,∇hr(x¯) là độc lập tuyến tính, thì mệnh đề 1.2.1 trở thành định lý Ljusternik cổ điển. Thật vậy, khi đó ánh xạ∇h(x¯) là toàn ánh, T (C; x¯) = Rn, điều kiện chính quy (RC) đúng và ta có ker∇h(x¯) = T (C; x¯). Điều kiện (RC) sẽ được minh họa bởi ví dụ sau. Ví dụ 1.2.1 Cho h : R3 → R2 và C ⊂ R3 được xác định như sau h := (h1, h2), (x¯, y¯, z¯) = 0, h1(x, y, z) = x+ 2y + z, h2(x, y, z) = 2x+ 4y − z, C := {(x, y, z) : −1 ≤ x ≤ 0, −1 ≤ y, z ≤ 1} . Khi đó ∇h1(0, 0, 0) = (1, 2, 1), ∇h2(0, 0, 0) = (2, 4,−1), T (C; 0) = −R+ ì RìR, N (C; 0) = R+ì{0}ì {0} và điều kiện (RC) thỏa mãn. Thật vậy nếu 0 ∈ γ1∇h1(0) + γ2∇h2(0) +N(C; 0), có nghĩa là (0, 0, 0) ∈ (γ1 + 2γ2, 2γ1 + 4γ2, γ1 − γ2) + R+ ì {0} ì {0} , khi đó ta suy ra γ1 = γ2 = 0. Do đó, điều kiện (RC) đúng Nhắc lại rằng điểm x¯ ∈ M được gọi là cực tiểu Pareto yếu địa phương của bài toán (P) nếu tồn tại một số δ > 0 sao cho không tồn tại x ∈ M ∩ B (x¯; δ) thỏa mãn fk (x) < fk (x¯) (∀k ∈ J) , trong đó B (x¯; δ) là hình cầu mở bán kính δ tâm x¯. Giả thiết sau đây là cần thiết để dẫn các điều kiện cần cho nghiệm hữu hiệu yếu. 16 Giả thiết 1.2.1 Tồn tại một chỉ số s ∈ J sao cho fs có một dưới vi phân suy rộng trên ∂∗fs (x¯) tại x¯. Với mỗi k ∈ J, k 6= s và i ∈ I (x¯), các hàm fk và gi có các dưới vi phân suy rộng bán chính quy trên ∂∗fk (x¯) và ∂∗gi (x¯) tại x¯; tất cả các hàm gi (i /∈ I (x¯)) liên tục tại x¯. Trên cơ sở định lý Ljusternik suy rộng của Jiménez-Novo [11], ta chứng minh điều kiện cần cho cực tiểu Pareto yếu địa phương của (P). Định lý 1.2.1 Giả sử x¯ là cực tiểu Pareto yếu địa phương của (P). Giả sử rằng tất cả các giả thiết của mệnh đề 1.2.1 và giả thiết 1.2.1 đúng. Giả sử các hàm fk (k ∈ J) và gi (i ∈ I (x¯)) Lipschitz địa phương tại x¯. Khi đó, các hệ sau không có nghiệm v ∈ Rn: sup ξk∈conv∂∗fk(x¯) 〈ξk, v〉 < 0 (∀k ∈ J), (1.2) sup ξi∈conv∂∗gi(x¯) 〈ξi, v〉 < 0 (∀i ∈ I(x¯)), (1.3) 〈∇hj(x¯), v〉 = 0 (∀j ∈ L), (1.4) v ∈ T (x¯;C). (1.5) Chứng minh Ta chỉ ra rằng những điều kiện sau không có nghiệm v ∈ Rn: f−s (x¯; v) < 0, (1.6) f+k (x¯; v) < 0 (∀k ∈ J ; k 6= s), (1.7) g+i (x¯; v) < 0 (∀i ∈ I(x¯)), (1.8) 〈∇hj(x¯), v〉 = 0 (∀j ∈ L), (1.9) v ∈ T (x¯;C). (1.10) 17 Giả sử ngược lại rằng hệ (1.6) - (1.10) có một nghiệm v0 ∈ Rn. Khi đó, v0 ∈ (ker∇h(x¯)) ∩ T (C; x¯). áp dụng mệnh đề 1.2.1 ta suy ra (ker∇h(x¯)) ∩ T (C; x¯) = A(H ∩ C; x¯). Do đó, ∃δ > 0 và γ : [0, δ]→ Rn sao cho γ (0) = x¯, γ (t) ∈ H ∩ C (∀t ∈ ]0, δ]) , γ′ (0) = lim t↓0 γ (t)− γ (0) t = v0. (1.11) Như vậy, γ (t) ∈ C và h (γ (t)) = 0 (∀t ∈ ]0, δ]). (1.12) Từ (1.11) ta suy ra γ (t)− γ (0) t + o (t) t → v0 và γ (t)− γ (0) t → v0 khi t ↓ 0, trong đó o (t) t → 0 khi t ↓ 0. Vì fs là Lipschitz địa phương tại x¯, nên từ [3, tr.286] ta suy ra f−s (x¯; v0) = lim inf t↓0 fs(x¯+tv0)−fs(x¯) t = lim inf t↓0 fs(x¯+t(γ(t)−γ(0)t + o(t) t ))−fs(x¯) t = lim inf t↓0 fs(x¯+(γ(t)−x¯))−fs(x¯) t = lim inf t↓0 fs(γ(t))−fs(x¯) t < 0. Vì vậy, với mỗi số tự nhiên p, tồn tại tp ∈ ] 0, 1p [ ( 1 p ≤ δ ) sao cho lim inf t↓0 fs (γ (t))− fs (x¯) t = lim p→+∞ fs (γ (tp))− fs (x¯) tp < 0. Do đó, tồn tại số tự nhiên N1 sao cho với mọi p ≥ N1, fs (γ (tp)) < fs (x¯) . (1.13) 18 Vì fk là Lipschitz địa phương tại x¯, cho nên từ (1.11) với ∀k ∈ J, k 6= s ta có f+k (x¯; v0) = lim sup t↓0 fk ( x¯+ t ( γ(t)−γ(0) t + o(t) t )) − fk (x¯) t = lim p→+∞ sup t∈]o, 1p [ fk (γ (t))− fk (x¯) t < 0. Do đó, tồn tại số tự nhiên N2 (≥ N1) sao cho với mọi p ≥ N2, t ∈ ] 0, 1p [ , fk (γ (t)) < fk (x¯). Vì vậy với mọi ∀k ∈ J, k 6= s, ta có fk (γ (tp)) < fk (x¯) . (1.14) Tương tự, tồn tại một số tự nhiên N3 (≥ N2) sao cho với ∀i ∈ I (x¯) , p ≥ N3, ta có gi (γ (tp)) < 0. (1.15) Do tính liên tục của hàm gi (i /∈ I (x¯)), tồn tại số tự nhiên N4 (≥ N3) sao cho với mọi ∀i /∈ I (x¯) , p ≥ N4, ta có gi (γ (tp)) < 0 (1.16) Kết hợp (1.12) - (1.16), ta suy ra với mọi ∀p ≥ N4, fk (γ (tp)) < fk (x¯) (∀k ∈ J), gi (γ (tp)) < 0 (∀i ∈ I), h (γ (tp)) = 0, γ (tp) ∈ C. Điều này mâu thuẫn với giả thiết x¯ là cực tiểu Pareto yếu địa phương của (P). Từ giả thiết (1.2.1) ta suy ra rằng hệ (1.2) - (1.5) không tương thích. Từ đó ta suy ra điều phải chứng minh. 2 Đặt D (x¯) := ⋃{∑ k∈J λk conv ∂ ∗fk(x¯) + ∑ i∈I(x¯) ài conv ∂ ∗gi(x¯) + ∑ j∈L γj∇hj(x¯) +N(C; x¯) : λk ≥ 0(∀k ∈ J), ài ≥ 0, (∀i ∈ I(x¯)), γj ∈ R (∀j ∈ L) , (λ, à, γ) 6= (0, 0, 0) } , 19 trong đó λ = (λk)k∈J , à = (ài)i∈I(x¯), γ = (γj)j∈L Điều kiện cần Fritz John cho cực tiểu Pareto yếu địa phương của (P) dưới ngôn ngữ dưới vi phân suy rộng được phát biểu như sau. Định lý 1.2.2 Giả sử rằng x¯ là cực tiểu Pareto yếu địa phương của (P) và các giả thiết của định lý 1.2.1 thoả mãn. Khi đó tồn tại λ¯k ≥ 0 (∀k ∈ J) , à¯i ≥ 0 (∀i ∈ I (x¯)), (λ¯, à¯) 6= (0, 0) và γ¯ ∈ Rl sao cho 0 ∈ cl (∑ k∈J λ¯kconv∂ ∗fk(x¯) + ∑ i∈I(x¯) à¯iconv∂ ∗gi(x¯) + ∑ j∈L γ¯j∇hj(x¯) +N(C; x¯) ) . (1.17) Chứng minh Ta chỉ ra rằng 0 ∈ clD (x¯) . (1.18) Giả sử ngược lại 0 /∈ clD (x¯) . Ta có tậpD (x¯) là không rỗng và lồi. Khi đó ta áp dụng định lý tách mạnh cho các tập lồi rời nhau D (x¯) và {0} (xem [19], hệ quả 11.4.2), tồn tại v0 ∈ Rn, v0 6= 0 sao cho sup ξ∈D(x¯) 〈ξ, v0〉 < 0. (1.19) Theo định lý 1.2.1, hệ (1.2) - (1.5) là không tương thích. Khi đó, bằng cách chọn λk = 1, λp = 0, (∀p ∈ J, p 6= k), ài = 0 (∀i ∈ I(x¯)), γ = 0 và 0 = ζ ∈ N(C; x¯), từ (1.19) ta suy ra sup ξk∈conv∂∗fk(x¯) 〈ξk, v0〉 < 0 (∀k ∈ J). (1.20) Tương tự như trên, ta có sup ηi∈conv∂∗gi(x¯) 〈ηi, v0〉 < 0 (∀i ∈ I(x¯)). (1.21) 20 Ta chỉ ra 〈∇hj(x¯), v0〉 = 0 (∀j ∈ L) . (1.22) Thật vậy nếu (1.22) là sai, thì 〈∇hj0(x¯), v0〉 6= 0 với j0 nào đó ∈ L. Bằng cách lấy ξs ∈ ∂∗fs (x¯) , λs = 1, λk = 0 (∀k ∈ J, k 6= s) , ài = 0(∀i ∈ I(x¯)), γj = 0 (∀j ∈ L, j 6= j0) , 0 = ζ ∈ N(C; x¯), từ (1.19) ta suy ra 〈ξs, v0〉+ γj0 〈∇hj0(x¯), v0〉 < 0. (1.23) Ta chú ý rằng |〈ξs, v0〉| < +∞ và |〈∇hj0(x¯), v0〉| < +∞. Cho γj0 đủ lớn nếu 〈∇hj0(x¯), v0〉 > 0, còn γj0 < 0 với giá trị tuyệt đối đủ lớn nếu 〈∇hj0(x¯), v0〉 < 0, ta sẽ đi đến một mâu thuẫn với (1.23). Do vậy, (1.22) là đúng. Tiếp theo, ta chỉ ra rằng v0 ∈ T (C; x¯). (1.24) Thật vậy, nếu (1.24) không đúng thì sẽ ∃η0 ∈ N(C; x¯) sao cho (η0, v0) > 0. Bằng cách cho λk = 0 (∀k ∈ J, k 6= s) , λs > 0, ξs ∈ ∂∗fs (x¯) , ài = 0(∀i ∈ I(x¯)), γ = 0, với α > 0 ta có αη0 ∈ N(C; x¯) và λs 〈ξ0, v0〉+ α 〈η0, v0〉 < 0. (1.25) Vì 〈η0, v0〉 > 0 với α đủ lớn ta nhận được một mâu thuẫn với (1.25). Do đó 〈η0, v0〉 ≤ 0, (∀η ∈ N(C; x¯)). Chú ý rằng T (C; x¯) là một nón lồi đóng. Từ đó ta có v0 ∈ N 0(C; x¯) = T 00(C; x¯) = T (C; x¯). Kết hợp (1.20) - (1.22) và (1.24) ta suy ra hệ (1.6) - (1.10) có một nghiệm v0, và cũng là nghiệm của hệ (1.2) - (1.5). Điều này mâu thuẫn với định lý 1.2.1. Vì 21 vậy (1.18) đúng và do đó tồn tại λ (n) k ≥ 0, ξ(n)k ∈ conv∂∗fk (x¯) (∀k ∈ J) , à(n)i ≥ 0, η (n) i ∈ conv∂∗gi (x¯) (∀i ∈ I (x¯)) , γ(n)j ∈ R (∀j ∈ L) và ζ(n) ∈ N (C; x¯) với( λ(n), à (n) I(x¯), γ (n) ) 6= (0, 0, 0) sao cho 0 = lim n→∞ (∑ k∈J λ (n) k ξ (n) k + ∑ i∈I(x¯) à (n) i η (n) i + ∑ j∈L γ (n) j ∇hj (x¯) + ξ(n) ) , (1.26) trong đó λ(n) = ( λ (n) k ) k∈J , à (n) I(x¯) = ( à (n) i ) i∈I(x¯) , γ(n) = ( γ (n) j ) j∈L . Bởi vì ( λ(n), à (n) I(x¯), γ (n) 6= (0, 0, 0) ) , ta có thể xem như ‖ (λ(n), à(n)I(x¯), γ(n)) ‖= 1 (∀n) . Không mất tính tổng quát có thể giả sử ( λ(n), à (n) I(x¯), γ (n) ) → (λ¯, à¯I(x¯), γ¯) với λ¯ ≥ 0, à¯I(x¯) ≥ 0, γ¯ ∈ Rl và ‖ (λ¯, à¯I(x¯), γ¯) ‖= 1. Bởi vì clA+ clB ⊆ cl(A+B), và từ (1.26) ta suy ra 0 ∈ ∑ k∈J λ¯kclconv∂ ∗fk (x¯) + ∑ i∈I(x¯) à¯iclconv∂ ∗gi (x¯) + ∑ j∈L γ¯j∇hj (x¯) +N(C; x¯) ⊆ cl ∑ k∈J λ¯kconv∂ ∗fk (x¯) + ∑ i∈I(x¯) à¯iconv∂ ∗gi (x¯) + ∑ j∈L γ¯j∇hj (x¯) +N(C; x¯). (1.27) Ta có (1.27) đúng với ( λ¯, ௠) 6= (0, 0). Thật vậy nếu (λ¯, à¯) = (0, 0) thì γ¯ 6= 0. Tuy nhiên, kết hợp với (1.27) ta đi đến mâu thuẫn với điều kiện chính quy (RC). Do đó ( λ¯, ௠) 6= (0, 0). Suy ra điều phải chứng minh. 2 22 Hệ quả 1.2.1 Giả sử rằng C = Rn và các giả thiết của định lý 1.2.2 thoả mãn trong đó điều kiện chính quy (RC) trong mệnh đề 1.2.1 được thay thế bởi điều kiện: hệ ∇h1(x¯), ...,∇hl(x¯) là độc lập tuyến tính. Khi đó, tồn tại λ¯k ≥ 0 (∀k ∈ J), à¯i ≥ 0 (∀i ∈ I(x¯)) với (λ¯, à¯) 6= (0, 0) và γ¯j ∈ R (∀j ∈ L) sao cho (1.17) đúng. Chứng minh Với C = Rn, ta có N(C; x¯) = {0}. Do đó, nếu ∇h1(x¯), ...,∇hl(x¯) là độc lập tuyến tính thì điều kiện chính quy (RC) thỏa mãn. Theo định lý 1.2.2 ta suy ra điều phải chứng minh. 2 Trong trường hợp tập D(x¯) là tập đóng, ta nhận được hệ quả trực tiếp sau đây của định lý 1.2.1, trong đó bao đóng trong (1.17) có thể bỏ được. Hệ quả 1.2.2 Giả sử C = Rn. Giả sử các giả thiết của định lý 1.2.2 đúng và tập D(x¯) đóng. Khi đó ∃λ¯k ≥ 0 (∀k ∈ J), à¯i ≥ 0 (∀i ∈ I(x¯)) với ( λ¯, ௠) 6= (0, 0) và γ¯j ∈ R (∀j ∈ L) sao cho 0 ∈ ∑ k∈J λ¯kconv∂ ∗fk (x¯) + ∑ i∈I(x¯) à¯iconv∂ ∗gi (x¯) + ∑ j∈L γ¯j∇hj (x¯) +N(C; x¯). Nhận xét 1.2.2 Trong trường hợp C = Rn, cũng như trong nhận xét 3.1 trong [13], nếu ∂∗fk(x¯) (k ∈ J) và ∂∗gi(x¯)(i ∈ (I(x¯)) bị chặn và thỏa mãn điều kiện sau đây: 0 /∈ conv (⋃ k∈J conv∂∗fk (x¯) ∪ ⋃ i∈I(x¯) conv∂∗gi (x¯) ) + lin {∇hj(x¯) : j ∈ L} , thì D(x¯) là tập đóng, trong đó lin kí hiệu bao tuyến tính. Thật vậy ta có conv∂∗fk(x¯) (k ∈ J) và conv∂∗gi(x¯)(i ∈ (I(x¯)) là compăc và do đó tập sau cũng compăc: conv (⋃ k∈J conv∂∗fk (x¯) ∪ ⋃ i∈I(x¯) conv∂∗gi (x¯) ) . 23 Do đó, E(x¯) := conv (⋃ k∈J conv∂∗fk (x¯) ∪ ⋃ i∈I(x¯) conv∂∗gi (x¯) ) +lin {∇hj(x¯) : j ∈ L} là tập đóng. Hơn nữa, vì 0 /∈ E(x¯) và D(x¯) = coneE(x¯), cho nên D(x¯) là tập đóng, trong đó coneE(x¯) là nón sinh bởi E(x¯). Nhận xét 1.2.3 Điều kiện cần thu được trong định lý 1.2.2, các hệ quả 1.2.1, 1.2.2 và một vài điều kiện tối ưu đã trình bày dưới ngôn ngữ ∂∗f(x¯) là tốt hơn các điều kiện tối ưu dưới ngôn ngữ các dưới vi phân như các dưới vi phân Clarke, Mordukhovich và Michel-Penot. 24 Chương 2 Điều kiện chính quy và điều kiện tối ưu Karush-Kuhn-Tucker Trong chương 2 chúng ta sẽ trình bày các điều kiện chính quy và điều kiện cần Karush-Kuhn-Tucker, điều kiện đủ cho cực tiểu Pareto yếu của bài toán tối ưu đa mục tiêu có ràng buộc đẳng thức, bất đẳng thức và ràng buộc tập dưới ngôn ngữ dưới vi phân suy rộng. Các kết quả trình bày trong chương này được tham khảo trong [14]. 2.1 Điều kiện chính quy và điều kiện cần Karush-Kuhn- Tucker Chương 1 đã trình bày điều kiện cần Fritz John (1.17) với giả thiết 1.2.1 và giả thiết của mệnh đề 1.2.1, trong đó điều kiện chính quy (RC) đúng: 0 ∈ ∑ j∈L γj∇hj (x¯) +N(C; x¯) ⇒ γ1 = ... = γl = 0. Trong trường hợp C = Rn thì điều kiện này trở thành điều kiện: hệ∇h1, ...,∇hl là độc lập tuyến tính. Chú ý rằng trong điều kiện cần (1.17) ta có ( λ¯, ௠) 6= (0, 0). Để nhận được điều kiện cần cho nghiệm hữu hiệu trong đó λ¯ 6= 0, ta đưa vào điều kiện chính quy sau đây mà ta ký hiệu là (CQ1): ∃s ∈ J , d0 ∈ T (C, x¯), và các số ak > 0 (k ∈ J, k 6= s) , bi > 0 (i ∈ I (x¯)) sao cho 25 (i) 〈ξk, d0〉 ≤ −ak (∀ξk ∈ conv∂∗fk (x¯) ,∀k ∈ J, k 6= s) ; 〈ηi; d0〉 ≤ −bi (∀ηi ∈ conv∂∗gi (x¯) ,∀i ∈ I (x¯)) ; (ii) 〈∇hj (x¯) , d0〉 = 0 (∀j ∈ L) . Chúng ta cùng đưa vào điều kiện chính quy (CQ2): Với mọi λk ≥ 0 (k ∈ J, k 6= s) ; ài ≥ 0 (∀i ∈ I (x¯)), không đồng thời bằng 0, và γj ∈ R (∀j ∈ L), ta có 0 /∈ cl ( ∑ k∈J,k 6=s λkconv∂ ∗fk (x¯) + ∑ i∈I(x¯) àiconv∂ ∗gi (x¯) + ∑ j∈L γj∇hj(x¯) +N(C; x¯) ) . Trong phần tiếp theo ta trình bày mối quan hệ giữa (CQ1) và (CQ2). Mệnh đề 2.1.1 Giả sử rằng fk và gi có các dưới vi phân suy rộng trên ∂ ∗fk (x¯) và ∂∗gi (x¯) tại x¯, với mỗi k ∈ J, k 6= s, i ∈ I (x¯), h khả vi Fréchet tại x¯ và C là lồi. Khi đó (CQ1) kéo theo (CQ2) (∀s ∈ J). Chứng minh Giả sử ngược lại rằng (CQ1) đúng, nhưng (CQ2) sai, có nghĩa là ∃λk ≥ 0 (∀k ∈ J, k 6= s) ;ài ≥ 0 (∀i ∈ I (x¯)) với (λ(s), à) 6= (0, 0), trong đó (λ(s) = (λk)k∈J,k 6=s,à = (ài)i∈I(x¯)), ξ(n)k ∈ conv∂∗fk (x¯) (∀k ∈ J, k 6= s) , η (n) i ∈ conv∂∗gi (x¯) (∀i ∈ I (x¯)) , γj ∈ R (∀j ∈ L) và ζ(n) ∈ N(C; x¯) sao cho lim n→∞ ( ∑ k∈J,k 6=s λkξ (n) k + ∑ i∈I(x¯) àiη (n) i + ∑ j∈L γj∇hj(x¯) + ζ(n) ) = 0. Từ (CQ1) suy ra ∃d0 ∈ T (C; x¯) sao cho 0 = lim n→∞ ( ∑ k∈J,k 6=s λk 〈 ξ (n) k , d0 〉 + ∑ i∈I(x¯) ài 〈 η (n) i , d0 〉 + ∑ j∈L γj 〈∇hj(x¯), d0〉+ 〈 ζ(n), d0 〉) 26 ≤ lim n→∞ ( ∑ k∈J,k 6=s λk 〈 ξ (n) k , d0 〉 + ∑ i∈I(x¯) ài 〈 η (n) i , d0 〉) . (2.1) Vì (λ(s), à) 6= (0, 0) từ điều kiện (i) trong (CQ1) suy ra lim n→∞ ( ∑ k∈J,k 6=s λk 〈 ξ (n) k , d0 〉 + ∑ i∈I(x¯) ài 〈 η (n) i , d0 〉) ≤ − ∑ k∈J,k 6=s λkak − ∑ i∈I(x¯) àibi < 0. Điều này mâu thuẫn với (2.1). Do đó ta có điều phải chứng minh. 2 Một điều kiện cần Karush-Kuhn-Tucker cho nghiệm hữu hiệu có thể được phát biểu như sau: Định lý 2.1.1 Giả sử x¯ là cực tiểu Pareto yếu địa phương của (P). Giả sử tất cả các giả thiết của định lý 1.2.2 thoả mãn và giả sử điều kiện chính quy (CQ1) hoặc (CQ2) đúng (với s ∈ J). Khi đó, tồn tại λ¯s > 0, λ¯k ≥ 0(∀k ∈ J, k 6= s), à¯i ≥ 0(∀i ∈ I(x¯)), γ¯j ∈