Tài liệu Luận văn đặc trưng cho tập nghiệm của bài toán quy hoạch lồi và bài toán bất đẳng thức biến phân

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC TRẦN VŨ MINH HOÀNG ĐẶC TRƯNG CHO TẬP NGHIỆM CỦA BÀI TOÁN QUY HOẠCH LỒI VÀ BÀI TOÁN BẤT ĐẲNG THỨC BIẾN PHÂN LUẬN VĂN THẠC SĨ TOÁN HỌC Thái Nguyên – 2015 Mục lục Mở đầu 1 1 Kiến thức chuẩn bị 4 1.1 Một số kiến thức giải tích lồi . . . . . . . . . . . . . . . 4 1.2 Bài toán tối ưu và bài toán bất đẳng thức biến phân . . 11 2 Đặc trưng cho tập nghiệm của bài toán quy hoạch lồi và bài toán bất đẳng thức biến phân 14 2.1 Đặc trưng cho tập nghiệm trong trường hợp f khả vi Gâteaux . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.2 Đặc trưng tập nghiệm qua dưới vi phân . . . . . . . . . 21 2.3 Đặc trưng tập nghiệm của bài toán bất đẳng thức biến phân . . . . . . . . . . . . . . . . . . . . . . . . . . . . Kết luận 28 36 Tài liệu tham khảo 37 i Mở đầu 1. Lý do chọn đề tài O. L. Mangasarian (1988) đã chứng minh rằng tập nghiệm của bài toán lồi: (P ) M in {f (x) : x ∈ C} , C ⊂ Rn , f : Rn → R Có thể đặc trưng bởi gradient của f khi f khả vi liên tục hai lần trên một tập mở chứa C và có thể đặc trưng bởi dưới vi phân của f khi f liên tục và phần trong tương đối của tập nghiệm khác rỗng. Z. L. Wu và S. Y. Wu (2006) đã chứng minh rằng với bài toán lồi (P) trong không gian định chuẩn với hàm mục tiêu khả vi Gâteaux tại một nghiệm tối ưu thì tập nghiệm bao gồm các điểm chấp nhận được nằm trong siêu phẳng mà véctơ pháp tuyến của nó bằng đạo hàm Gâteaux đó. Với bài toán quy hoạch lồi liên tục, điểm chấp nhận được là nghiệm khi và chỉ khi nó nằm trong siêu phẳng với vectơ pháp tuyến thuộc dưới vi phân của hàm mục tiêu tại điểm đó. Đồng thời có thể đặc trưng tập nghiệm của bài toán bất đẳng thức biến phân. Đây là đề tài được nhiều tác giả quan tâm nghiên cứu. Chính vì thế em chọn đề tài "Đặc trưng cho tập nghiệm của bài toán quy hoạch lồi và bất đẳng thức biến phân". 2. Mục đích của luận văn Luận văn trình bày các kết quả về đặc trưng cho tập nghiệm của bài toán quy hoạch lồi và bài toán bất đẳng thức biến phân của Z. L. Wu 1 và S. Y. Wu đăng trong J. Optim. Theory Appl (2006). 3. Nội dung của luận văn Luận văn bao gồm phần mở đầu, hai chương, kết luận và danh mục các tài liệu tham khảo. Chương 1. Kiến thức chuẩn bị Trình bày một số kiến thức cơ bản của giải tích lồi như: Phần trong tương đối, dưới vi phân hàm lồi, các phép tính về dưới vi phân hàm lồi. Chương 1 cũng trình bày bài toán quy hoạch lồi, bài toán bất đẳng thức biến phân, bài toán bất đẳng thức biến phân đối ngẫu và hàm sai khác đối ngẫu của bài toán bất đẳng thức biến phân sẽ được xét trong chương 2. Chương 2.Đặc trưng cho tập nghiệm của bài toán quy hoạch lồi và bài toán bất đẳng thức biến phân. Trình bày các tính chất đặc trưng cho tập nghiệm của bài toán quy hoạch lồi trong trường hợp hàm mục tiêu khả vi Gâteaux, trường hợp bài toán quy hoạch lồi liên tục và bài toán bất đẳng thức biến phân của Z. L. Wu và S. Y. Wu ([13], 2006). Trong trường hợp hàm mục tiêu của bài toán quy hoạch lồi khả vi Gâteaux, tập nghiệm sẽ nằm trong siêu phẳng mà vectơ pháp tuyến của nó bằng đạo hàm Gâteaux của hàm mục tiêu. Trong trường hợp quy hoạch lồi liên tục, một điểm chấp nhận được là nghiệm của tối ưu khi và chỉ khi nó nằm trong siêu phẳng mà vectơ pháp tuyến thuộc dưới vi phân của hàm mục tiêu tại điểm này. Trong một số trường hợp tập nghiệm của bài toán bất đẳng thức biến phân trùng với tập nghiệm của bài toán quy hoạch lồi với hàm sai khác đối ngẫu là hàm mục tiêu. Nhân dịp này tôi xin chân thành cảm ơn PGS.TS Đỗ Văn Lưu, người đã hướng dẫn tận tình, giúp đỡ tôi hoàn thành bản luận văn này. Tôi xin chân thành cảm ơn Ban chủ nhiệm Khoa Toán-Tin Trường Đại học Khoa học - Đại học Thái Nguyên cùng các thầy cô giáo đã tham gia giảng dạy khóa học. Xin chân thành cảm ơn gia đình, bạn 2 bè đồng nghiệp và các thành viên lớp Cao học Toán K7A đã luôn quan tâm động viên giúp đỡ tôi trong suốt quá trình làm luận văn. Thái Nguyên, ngày 20 tháng 05 năm 2015 Tác giả Trần Vũ Minh Hoàng 3 Chương 1 Kiến thức chuẩn bị Chương 1 trình bày một số kiến thức cơ bản của giải tích lồi như: Phần trong tương đối, dưới vi phân hàm lồi, các phép toán về dưới vi phân các hàm lồi, hàm khả vi Gâteaux. Chương này cũng trình bày bài toán quy hoạch lồi, bài toán bất đẳng thức biến phân, bài toán bất đẳng thức biến phân đối ngẫu và hàm sai khác đối ngẫu sẽ được xét trong chương 2. Các kiến thức trình bày trong chương này được tham khảo trong [1], [13]. 1.1 Một số kiến thức giải tích lồi Giả sử X là không gian tuyến tính trên trường số thực. Định nghĩa 1.1.1. Tập A ⊂ X được gọi là lồi nếu: ∀x1 , x2 ∈ A, ∀λ ∈ R : 0 ≤ λ ≤ 1 ⇒ λx1 + (1 − λ) x2 ∈ A, trong đó R là tập các số thực. Định nghĩa 1.1.2. a) Tập K ⊂ X được gọi là nón có đỉnh tại 0, nếu: ∀x ∈ K, ∀λ > 0 ⇒ λx ∈ K. K được gọi là nón có đỉnh tại x0 , nếu K − x0 là nón có đỉnh tại 0. 4 b) Nón K có đỉnh tại 0 được gọi là nón lồi, nếu K là một tập lồi có nghĩa là: ∀x, y ∈ K, ∀λ, µ > 0 ⇒ λx + µy ∈ K. Định nghĩa 1.1.3. Phần trong tương đối của tập A ⊂ Rn là phần trong của A trong affA; Kí hiệu là riA, trong đó affA là bao affine của tập A. Như vậy riA = {x ∈ affA :∃ε > 0, (x + εB) ∩ affA ⊂ A}, trong đó B là hình cầu đơn vị trong Rn . Định nghĩa 1.1.4. Trên đồ thị của hàm f : D ⊂ X → R, ký hiệu là epif, được định nghĩa như sau: epif = {(x, r) ∈ D × R : f (x) ≤ r} . Định nghĩa 1.1.5. Hàm f : D ⊂ X → R được gọi là chính thường nếu: domf 6= ∅ và f (x) > −∞ (∀x ∈ D) , trong đó domf = {x ∈ D : f(x) < +∞}. Định nghĩa 1.1.6. Hàm f được gọi là lồi trên D nếu epif là tập lồi trong X × R. Hàm f được gọi là lõm trên D nếu −f là hàm lồi trên D. Giải sử f là hàm xác định trên không gian lồi địa phương Haus
 dorffX, f X  < +∞. Định nghĩa 1.1.7. Đạo hàm của hàm f theo phương d tại x , ký hiệu là f 0 (x; d) được định nghĩa là giới hạn sau: f 0 (x; d) = lim λ↓0 f (x + λd) − f (x) λ Nếu giới hạn này tồn tại (có thể hữu hạn hoặc ±∞). 5 Định lí 1.1.1. Giả sử f là hàm lồi chính thường trên X . Khi đó f có đạo hàm theo phương tại mọi điểm x ∈ domf . Đồng thời, f (x + λd) − f (x) f 0 (x; d) = inf . λ λ>0 Nhận xét 1.1.1. Nếu f là lồi chính thường trên X , x ∈ domf thì f 0 (x, .) là hàm lồi. Giả sử f là hàm lồi trên X . Định nghĩa 1.1.8. Phiếm hàm x∗ ∈ X ∗ được gọi là dưới gradient (subgradient) của f tại x ∈ X nếu: f (x) − f (x) ≥ hx∗ , x − xi (∀x ∈ X) . Định nghĩa 1.1.9. Tập tất cả dưới gradient của f tại x được gọi là dưới vi phân (subdifferential) của f tại x, ký hiệu là ∂f (x), tức là: ∂f (x) = {x∗ ∈ X ∗ : f (x) − f (x) ≥ hx∗ , x − xi , ∀x ∈ X} . Định lí 1.1.2. Giả sử f là hàm lồi chính thường trên X và x ∈ domf . Khi đó, x∗ ∈ ∂f (x) ⇔ f 0 (x; d) ≥ hx∗ , di (∀d ∈ X) . Chứng minh. Nếu x∗ ∈ ∂f (x) thì ∀d ∈ X, λ > 0, ta có: f (x + λd) − f (x) ≥ λ hx∗ , di . Theo Định lý 1.1.1, f có đạo hàm tại x theo phương d, cho nên: f 0 (x; d) ≥ hx∗ , di (1.1) Ngược lại, nếu (1.1) đúng, ta lấy x ∈ X, d = x − x, từ Định lý 1.1.1, ta nhận được: hx∗ , x − xi ≤ f 0 (x; x − x) ≤ f (x + (x − x)) − f (x) . Do đó, x∗ ∈ ∂f (x). 6 Định lí 1.1.3. Giả sử f là hàm lồi chính thường trên X và x ∈ domf . Khi đó, x∗ ∈ ∂f (x) ⇔ f (x) + f ∗ (x∗ ) = hx∗ , xi . Chứng minh. Giả sử x∗ ∈ ∂f (x). Khi đó, f (x) − f (x) ≥ hx∗ , x − xi(∀x ∈ X) ⇒ hx∗ , xi − f (x) ≥ hx∗ , xi − f (x)(∀x ∈ X) ⇒ hx∗ , xi − f (x) ≥ sup{hx∗ , xi − f (x)}(∀x ∈ X) = f ∗ (x∗ ) . (1.2) Mặt khác, theo bất đẳng thức Young-Fenchel hx∗ , xi − f (x) ≤ f ∗ (x∗ ) . (1.3) Từ (1.2) và (1.3) suy ra: f (x) + f ∗ (x∗ ) = hx∗ , xi . (1.4) Giả sử (1.4)đúng. Từ bất đẳng thức Young-Fenchel với λ > 0, d ∈ X , ta có: f (x + λd) ≥ hx∗ , x + λdi − (hx∗ , xi − f (x)) f (x + λd) − f (x) hx∗ , λdi ≥ = hx∗ , di ⇒ λ λ 0 ∗ ⇒ f (x; d) ≥ hx , di (∀d ∈ X) ⇒ x∗ ∈ ∂f (x) . Ví dụ 1.1.1. Cho hàm affine f (x) = hx∗ , xi + α (x∗ ∈ X ∗ , α ∈ R). Khi đó, ∂f (x) = {x∗ } (∀x ∈ X). Ví dụ 1.1.2. 7 Cho hàm chỉ f (x) = δ (.| A), trong đó A là tập lồi khác ∅ Khi đó, với x ∈ A, x∗ ∈ ∂δ (x| A) ⇔ δ (x| A) ≥ δ (x| A) + hx∗ , x − xi (∀x ∈ X) ⇔ hx∗ , x − xi ≤ 0 (∀x ∈ A). Điều này có nghĩa là x∗ là véctơ pháp tuyến của A tại x. Như vậy, ∂δ (x| A) là nón pháp tuyến của A tại x, ∂δ (x| A) = N (x| A) . / A, ∂δ (x| A) = ∅. Chú ý: Với x ∈ Ví dụ 1.1.3. X = R, f (x) = |x| Với x 6= 0: f là hàm khả vi, và : n o −1 ∂f (x) = |x| x . Với x = 0: ∂f (0) = {ξ ∈ R : |z| ≥ hξ, zi , ∀z ∈ R} = {ξ ∈ R : |ξ| ≤ 1} = [−1, 1] . Định nghĩa 1.1.10. Hàm f được gọi là khả vi Gâteaux tại x ∈ X , nếu ∃x∗ ∈ X ∗ sao cho với mọi d ∈ X , f (x + td) = f (x) + t hx∗ , di + o (t) . (1.5) Khi đó, ta gọi x∗ là đạo hàm Gâteaux của f tại x: f 0G (x) = x∗ . Định lí 1.1.4. Giả sử f là hàm lồi trên X . Khi đó, a)Nếu f khả vi Gâteaux tại x với đạo hàm Gâteaux tại x là x∗ và 8 f khả dưới vi phân tại x, thì ∂f (x) = {x∗ }. b)Nếu f là hàm chính thường, liên tục tại x và ∂f (x) gồm một phần tử duy nhất x∗ thì f khả vi Gâteaux tại x và f 0G (x) = {x∗ }. Chứng minh. a) Từ (1.5) ta có:  f 0 (x; d) = f 0G (x) , d = hx∗ , di . Do đó, y ∗ ∈ ∂f (x) ⇔ hy ∗ , di ≤ hx∗ , di (∀d ∈ X) ⇔ hx∗ − y ∗ , di ≥ 0 (∀d ∈ X) ⇔ x∗ − y ∗ = 0 hay x∗ = y ∗ . Vậy ∂f (x) = {x∗ }. b) Giả sử ∂f (x) = {x∗ }. Ta có: f 0 (x; d) liên tục. Do đó, f 0 (x; d) là hàm đóng. Vì vậy, ∀d ∈ X ,
∗∗ f 0 (x; d) = f 0 (x, .) (d) (Định lý Fenchel-Moreau) = sup {hy ∗ , di : y ∗ ∈ ∂f (x)} = hx∗ , di . Suy ra: f 0G (x) = x∗ . Hệ quả 1.1.1. Giả sử X là không gian Banach, f là hàm lồi khả vi Fréchet tại x ∈ X với đạo hàm Fréchet tại x ∈ X là f 0 (x). Khi đó,  ∂f (x) = f 0 (x) . Định lí 1.1.5. Giả sử f là hàm lồi chính thường trên không gian lồi địa phương Hausdorff X , liên tục tại x ∈ X . Khi đó, ∂f (x) khác ∅, lồi, compact yếu∗ . Đồng thời, f 0 (x; d) = max {hx∗ , di : x∗ ∈ ∂f (x)} . 9 Chứng minh. a) Ta chứng minh ∂f (x) lồi? Lấy x∗1 , x∗2 ∈ ∂f (x) và λ ∈ [0, 1]. Khi đó, ∀x ∈ X , hλx∗1 , x − xi ≤ λ (f (x) − f (x)) h(1 − λ) x∗2 , x − xi ≤ (1 − λ) (f (x) − f (x)) ⇒ hλx∗1 + (1 − λ) x∗2 , x − xi ≤ f (x) − f (x) (∀x ∈ X) ⇒ λx∗1 + (1 − λ) x∗2 ∈ ∂f (x) ⇒ ∂f (x) lồi. b) Ta chứng minh ∂f (x) 6= ∅. Theo Định lý 4.2 [1] f 0 (x; .) liên tục trên X. Do đó, ∂f (x) 6= ∅ (Mệnh đề 4.6 [1]). c) Ta chứng minh ∂f (x) compact yếu∗ . Do f 0 (x; d) liên tục, f 0 (x; d) là hàm đóng. Theo Định lý 4.5 [1], sup {hx∗ , di : x∗ ∈ ∂f (x)} = f 0 (x; d) < +∞ (∀d ∈ X) . Khi d chạy trên các tập hữu hạn A trên X , thì: −∞ < max f 0 (x; d) < +∞. d∈A Vì vậy, ∂f (x) bị chặn trên tôpô yếu∗ của X ∗ . T Mặt khác, ∂f (x) = Hd , trong đó Hd là nửa không gian đóng yếu∗ trong X ∗, d∈X Hd = {x∗ ∈ X ∗ : hx∗ , di ≤ f (x + d) − f (x)} . ⇒ ∂f (x) là tập đóng yếu∗ trong X ∗ . ⇒ ∂f (x) compact yếu∗ trong X ∗ . Mệnh đề 1.1.1. Giả sử f là hàm lồi chính thường trên X và λ > 0. Khi đó, ∀x ∈ X , ∂ (λf ) (x) = λ∂f (x) . 10 Định lí 1.1.6. (Moreau-Rockafellar) Giả sử f1 , f2 , ..., fm là hàm lồi chính thường trên X . Khi đó, ∀x ∈ X , ∂ (f1 + ... + fm ) (x) ⊃ ∂f1 (x) + ... + ∂fm (x) . Hơn nữa, nếu tại điểm x ∈ m T domfi , tất cả các hàm f1 , f2 , ..., fm i=1 liên tục (có thể trừ ra một hàm), thì ∂ (f1 + ... + fm ) (x) = ∂f1 (x) + ... + ∂fm (x) . Hệ quả 1.1.2. Giả sử f1 , f2 , ..., fm là các hàm lồi chính thường trên X và λ1 > 0, ..., λm > 0. Khi đó, ∀x ∈ X , ∂ (λ1 f1 + ... + λm fm ) (x) ⊃ λ1 ∂f1 (x) + ... + λm ∂fm (x) . m T domfi , tất cả các hàm f1 , f2 , ..., fm Hơn nữa, nếu tại điểm x ∈ i=1 liên tục (có thể trừ ra một hàm),thì với mọi x ∈ X , ∂ (λ1 f1 + ... + λm fm ) (x) = λ1 ∂f1 (x) + ... + λm ∂fm (x) . 1.2 Bài toán tối ưu và bài toán bất đẳng thức biến phân Xét bài toán quy hoạch lồi: M in {f (x) : x ∈ C} trong đó C là một tập lồi trong Rn . Trong [9] Mangasarian đã chứng minh rằng tập nghiệm của bài toán đó có thể đặc trưng bởi gradient của f khi f khả vi liên tục hai lần trên một tập lồi mở chứa C và bởi dưới vi phân của f khi f là liên tục và phần trong tương đối của tập nghiệm khác rỗng. 11 Giả sử X là không gian vectơ định chuẩn thực, C là tập lồi khác rỗng trong X . Với hàm f : X → (−∞, +∞] và x ∈ X với f (x) < +∞, đạo hàm theo phương của f tại x theo phương v ∈ X là: f 0 (x; v) := lim+ [f (x + tv) − f (x)] /t. t→0 Dưới vi phân của hàm lồi f tại x là: ∂f (x) := {ξ ∈ X ∗ : f (y) − f (x) ≥ hξ, y − xi , ∀y ∈ X}. Ta biết dưới vi phân của hàm f là đơn điệu, có nghĩa là: với (x, y) ∈ X × X, ξ ∈ ∂f (x) , η ∈ ∂f (y) ⇒ hξ − η, x − yi ≥ 0. Nếu hàm lồi f liên tục tại x thì ∂f (x) khác rỗng. Nếu f khả vi Gâteaux tại x thì ∂f (x) = {∇f (x)}. Với một tập lồi đóng C trong X và một ánh xạ F : X → X ∗ , bài toán bất đẳng thức biến phân là tìm véctơ x∗ ∈ C sao cho: (V IP (C, F )) hF (x∗ ), x − x∗ i ≥ 0 với mọi x ∈ C. Bài toán bất đẳng thức biến phân đối ngẫu là tìm x∗ ∈ C sao cho: (DV IP (C, F )) hF (x) , x∗ − xi ≤ 0 với mọi x ∈ C. Bài toán VIP(C,F) thuộc loại bài toán bất đẳng thức biến phân Stampachia, còn bài toán DVIP(C,F) được gọi là bài toán bất đẳng thức biến phân Minty (xem [6], [8]). Ký hiệu: Tập nghiệm của VIP(C,F) là C ∗ , và của DVIP(C,F) là C∗ . Rõ ràng là hF (x∗ ) , x∗ − x∗ i = 0, ∀ (x∗ , x∗ ) ∈ C ∗ × C∗ . Hàm sai khác đối ngẫu G(x) ghép với VIP(C,F) được xác định bởi, G (x) := sup {hF (c) , x − ci : c ∈ C} với x ∈ X. Ta ký hiệu: Λ(x) := {c ∈ C : hF (c), x − ci = G(x)} . 12 Dễ thấy rằng với x∗ ∈ C, x∗ ∈ C∗ khi và chỉ khi G (x∗ ) = 0 khi và chỉ khi x∗ ∈ Λ(x∗ ). Chú ý: G là không âm trên C và lồi trên toàn không gian X . Vì vậy C∗ cũng là tập nghiệm của bài toán quy hoạch lồi M in {G(x) : x ∈ C} khi cực tiểu bằng không Nhắc lại: Một ánh xạ F : X → X ∗ được gọi là giả đơn điệu trên C nếu: hF (x) , y − xi ≥ 0 ⇒ hF (y) , y − xi ≥ 0, với mỗi (x, y) ∈ C × C; F được gọi là giả đơn điệu∗ trên C nếu nó giả đơn điệu trên C và thỏa mãn: (x, y) ∈ C × C, hF (x) , x − yi = 0, hF (y) , x − yi = 0 ⇒ F (x) = kF (y) , với k > 0 nào đó. Nói riêng, F là giả đơn điệu+ nếu F là giả đơn điệu∗ trên C với k = 1. Rõ ràng là khi F là giả đơn điệu trên C thì C ∗ ⊆ C∗ . 13 Chương 2 Đặc trưng cho tập nghiệm của bài toán quy hoạch lồi và bài toán bất đẳng thức biến phân Chương 2 trình bày các tính chất đặc trưng cho tập nghiệm của bài toán quy hoạch lồi trong trường hợp hàm mục tiêu khả vi Gâteaux, trường hợp bài toán quy hoạch lồi liên tục và bài toán bất đẳng thức biến phân. Kết quả chỉ ra rằng tập nghiệm của bài toán quy hoạch lồi nằm trong siêu phẳng mà vectơ pháp tuyến của nó bằng đạo hàm Gâteaux của hàm mục tiêu. Trong trường hợp quy hoạch lồi liên tục, một điểm chấp nhận được là nghiệm tối ưu khi và chỉ khi nó nằm trong siêu phẳng mà vectơ pháp tuyến của nó thuộc dưới vi phân của hàm mục tiêu tại điểm này. Trong một số trường hợp, tập nghiệm của bài toán bất đẳng thức biến phân trùng với tập nghiệm của bài toán quy hoạch lồi với hàm sai khác đối ngẫu là hàm mục tiêu. Các kết quả trình bày trong chương này là của Z. L. Wu - S. Y. Wu ([13], 2006). 2.1 Đặc trưng cho tập nghiệm trong trường hợp f khả vi Gâteaux Để đặc trưng tập nghiệm của bài toán quy hoạch lồi ta bắt đầu với phát biểu sau cho hàm không nhất thiết lồi. 14 Mệnh đề 2.1.1. Giả sử x∗ là nghiệm của bài toán min {f (x) : x ∈ C}. Nếu f là khả vi Gâteaux tại x∗ thì h∇f (x∗ ) , x − x∗ i ≥ 0 với mỗi x ∈ C. Nhắc lại, F là liên tục theo phương tại x ∈ X nếu: lim F (x + tv) = F (x) , ∀v ∈ X. t→0+ Khi F là liên tục theo phương tại mỗi điểm trong C thì sự tồn tại nghiệm của bài toán DVIP(C,F) kéo theo sự tồn tại nghiệm của bài toán VIP(C,F). Với các điều kiện đơn điệu suy rộng thì một số kết quả tồn tại nghiệm của DVIP(C,F) đã nhận được (xem [10], [11] cho trường hợp đơn điệu, [14] cho trường hợp giả đơn điệu). Mệnh đề sau cho ta sự tồn tại nghiệm của bài toán VIP(C,F) nếu hàm được xây dựng nhận cực tiểu trên C tại một điểm liên tục theo phương của F . Mệnh đề 2.1.2. Giả sử x∗ ∈ C , F liên tục theo phương tại x∗ và Z1 f (x) := hF (x∗ + s (x − x∗ )) , x − x∗ ids 0 xác định với mọi x trong tập mở chứa C . Nếu f có cực tiểu trên C tại x∗ thì f có đạo hàm Gâteaux F (x∗ ) tại x∗ và x∗ ∈ C ∗ . Nói riêng nếu x∗ ∈ C∗ thì f có cực tiểu trên C tại x∗ và vì vậy x∗ ∈ C ∗ . Chứng minh. Vì F là liên tục theo phương tại x∗ cho nên: f 0 (x∗ , v) = lim+ Z1 t→0 hF (x∗ + stv) , vi ds = hF (x∗ , v)i , ∀v ∈ X; 0 Điều đó có nghĩa là đạo hàm Gâteaux của f tại x∗ tồn tại và bằng F (x∗ ). Do đó, từ Mệnh đề 2.1.1 ta suy ra: x∗ ∈ C ∗ . 15 Nếu x∗ ∈ C∗ thì hF (x∗ + s (x − x∗ )) , x − x∗ i ≥ 0 với mỗi (x, s) ∈ C × (0, 1] . Từ đó ta thấy rằng f có cực tiểu trên C tại x∗ và x∗ ∈ C ∗ . Nhận xét 2.1.1. (i) Trong Mệnh đề 2.1.2, nếu tập lồi C là đóng và hàm f là nửa liên tục dưới và bị chặn dưới trên C và nếu 0 < α,0 < ε ≤ +∞, và mỗi x ∈ C với inf f < f (x) < inf f+ε, tồn tại y ∈ C sao cho 0 < α kx − yk ≤ f (x) − f (y) , theo Định lý 2.2 (trong [12]), f có cực tiểu tại một điểm nào đó trong C . Trong trường hợp này Mệnh đề 2.1.2 có thể xem như kết quả tồn tại nghiệm của VIP(C,F). (ii) Với Mệnh đề 2.1.2, chú ý rằng C không nhất thiết bị chặn và F không đòi hỏi liên tục trên toàn bộ C và x∗ có thể không nằm trong C∗ . Chẳng hạn, xét C = [0, +∞) × [0, +∞) và với x = (x1 , x2 ) ∈ R2 ,  F (x) = (1, 1) , nếu (x1 , x2 ) = (0, 0) , (0, 0) , nếu (x1 , x2 ) 6= (0, 0) . Rõ ràng là C không bị chặn và F không liên tục tại (0, 0) ∈ C . Tuy nhiên, vì F liên tục tại x∗ = (1, 1) và f nhận cực tiểu trên C tại x∗ , theo Mệnh đề 2.1.2, x∗ ∈ C ∗ còn x∗ ∈ / {(0, 0)} = C∗ . Mệnh đề tiếp theo dùng để chứng minh kết quả chính trong phần này. Mệnh đề 2.1.3. Giả sử x∗ , y ∗ ∈ X . Khi đó, với hàm f : X → R ta có: (i) ⇒ (ii) ⇒ (iii) ⇒ (iv) ⇒ (v), trong đó (i) − (v) là các phát biểu sau đây: (i) Tồn tại ξ ∈ ∂f (x∗ ) và η ∈ ∂f (y ∗ ) sao cho hξ, x∗ − y ∗ i = 0 và hη, x∗ − y ∗ i = 0. (ii) Tồn tại ξ ∈ ∂f (x∗ ) và η ∈ ∂f (y ∗ ) sao cho:hξ − η, x∗ − y ∗ i ≤ 0. (iii) ∂f (x∗ ) ∩ ∂f (y ∗ ) 6= ∅. 16 (iv) Tồn tại ξ ∈ ∂f (x∗ ) và η ∈ ∂f (y ∗ ) sao cho {v ∈ X : hξ, vi ≥ 0} = {v ∈ X : hη, vi ≥ 0} . (v) Tồn tại ξ ∈ ∂f (x∗ ) và η ∈ ∂f (y ∗ ) sao cho hξ, x∗ − y ∗ i ≥ 0 ⇔ hη, x∗ − y ∗ i ≥ 0, hξ, y ∗ − x∗ i ≥ 0 ⇔ hη, y ∗ − x∗ i ≥ 0. Nếu C là tập lồi trong X và f khả vi Gâteaux tại x∗ và y ∗ mà chúng là nghiệm của bài toán min {f (x) : x ∈ C} thì các phát biểu (i) − (v) là tương đương nhau. Chứng minh. Suy luận (i) ⇒ (ii) và (iii) ⇒ (iv) ⇒ (v) là tầm thường. Vì vậy, ta chỉ cần chỉ ra (ii) ⇒ (iii). Giả sử ξ ∈ ∂f (x∗ ) và η ∈ ∂f (y ∗ ) thỏa hξ − η, x∗ − y ∗ i ≤ 0. Khi đó với mọi y ∈ X , hξ, y − y ∗ i = hξ, x∗ − y ∗ i + hξ, y − x∗ i ≤ hη, x∗ − y ∗ i + f (y) − f (x∗ ) ≤ f (x∗ ) − f (y ∗ ) + f (y) − f (x∗ ) = f (y) − f (y ∗ ) . Điều này kéo theo ξ ∈ ∂f (y ∗ ). Như vậy, suy luận (ii) ⇒ (iii) là đúng. Giả sử C lồi và x∗ , y ∗ là nghiệm của bài toán min {f (x) : x ∈ C}. Nếu f khả vi Gâteaux tại x∗ , y ∗ , theo Mệnh đề 2.1.1 ta có: hξ, y ∗ − x∗ i ≥ 0 và hη, x∗ − y ∗ i ≥ 0 với ξ = ∇f (x∗ ) và η = ∇f (y ∗ ). Trong trường hợp này (v) ⇒ (i) phải đúng. Nhận xét 2.1.2. Dễ thấy (ii) trong Mệnh đề 2.1.3 tương đương với hξ − η, x∗ − y ∗ i = 0 với ξ nào đó thuộc ∂f (x∗ ) và η nào đó thuộc 17 ∂f (y ∗ ). Từ chứng minh của Mệnh đề 2.1.3 đẳng thức này kéo theo {ξ, η} ⊆ ∂f (x∗ ) ∩ ∂f (y ∗ ) . Nếu f là khả vi Gâteaux tại x∗ thì h∇f (x∗ ) − η, x∗ − y ∗ i = 0 ⇒ η = ∇f (x∗ ) . Với điều kiện f khả vi Gâteaux tại nghiệm x∗ của bài toán min {f (x) : x ∈ C}, nếu y ∗ ∈ C cũng là nghiệm của bài toán đó thì (i) trong mệnh đề 2.1.3 kéo theo (iii), có nghĩa là: ∇f (x∗ ) ∈ ∂f (y ∗ ) . Kết quả chính sau phát biểu rằng tập nghiệm của bài toán min {f (x) : x ∈ C} chỉ bao gồm các điểm chấp nhận được mà tại đó (i) trong Mệnh đề 2.1.3 thỏa mãn với phần tử nào đó thuộc tập dưới vi phân. Đặc biệt hơn tập nghiệm tối ưu bao gồm các điểm chấp nhận được nằm trong siêu phẳng mà véctơ pháp tuyến của nó là gradient của hàm mục tiêu tại nghiệm tối ưu đã cho. Định lí 2.1.1. Giả sử f : X → (−∞, +∞] là hàm lồi chính thường, C là tập nghiệm của bài toán min {f (x) : x ∈ C} và f khả vi Gâteaux tại x∗ ∈ C . Ký hiệu C (x∗ ) : = {x ∈ C : {v ∈ X : hξ, vi ≥ 0}}  = v ∈ X : h∇f (x∗ ) , vi ≥ 0, với ξ nào đó thuộc ∂f (x) . Khi đó, C = C0 = C1 = C2 = C3 = C4 = C5 , trong đó C0 := {x ∈ C : hξ, y − xi ≥ 0, với ξ nào đó ∈ ∂f (x) với ∀y ∈ C}, C1 := {x ∈ C : h∇f (x∗ ) , x − x∗ i = 0, ∇f (x∗ ) ∈ ∂f (x)}, C2 := {x ∈ C (x∗ ) : h∇f (x∗ ) , x − x∗ i = 0} , C3 := {x ∈ C : hξ, x − x∗ i = h∇f (x∗ ) , x − x∗ i = 0, với ξ nào đó thuộc ∂f (x)}, 18