Tài liệu Các quy tắc tổng tính dưới vi phân và dưới vi phân xấp xỉ

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ------------------------------- NGUYỄN TRƯỜNG GIANG CÁC QUY TẮC TỔNG TÍNH DƯỚI VI PHÂN VÀ DƯỚI VI PHÂN XẤP XỈ Chuyên ngành: Toán ứng dụng Mã số : 8 46 01 12 LUẬN VĂN THẠC SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC TS. Dương Thị Việt An THÁI NGUYÊN - 2020 Mục lục Danh mục ký hiệu 2 Mở đầu 4 Lời cảm ơn 6 1 Kiến thức chuẩn bị 7 1.1 Tập lồi và hàm lồi . . . . . . . . . . . . . . . . . . . . . 7 1.2 Dưới vi phân và Dưới vi phân xấp xỉ . . . . . . . . . . . 9 1.3 Một số kết quả bổ trợ . . . . . . . . . . . . . . . . . . . 12 2 Quy tắc tổng tính dưới vi phân của các hàm lồi 15 2.1 Định lý Moreau-Rockafellar phiên bản cổ điển . . . . . . 15 2.2 Định lý Moreau-Rockafellar phiên bản hình học . . . . . 20 2.3 Áp dụng . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3 Quy tắc tổng tính dưới vi phân xấp xỉ của các hàm lồi 24 3.1 Quy tắc tổng cho dưới vi phân xấp xỉ . . . . . . . . . . 24 3.2 Áp dụng . . . . . . . . . . . . . . . . . . . . . . . . . . 30 Kết luận 34 1 Danh mục ký hiệu R trường số thực R tập số thực suy rộng R+ tập số thực không âm ∅ tập rỗng ∀x với mọi x ∃x tồn tại x M ∩N giao của hai tập hợp M và N |x| giá trị tuyệt đối của x ||x|| chuẩn của véctơ x BX hình cầu đơn vị đóng trong X int A phần trong của tập A R+ (A) nón sinh bởi tập A inf f (x) infimum của tập số thực {f (x) | x ∈ K} x∈K sup f (x) supremum của tập số thực {f (x) | x ∈ K} x∈K N (x̄; Ω) nón pháp tuyến theo nghĩa giải tích lồi của Ω tại x̄ Nε (x̄; Ω) tập ε- pháp tuyến của Ω tại x̄ 2 f∗ hàm liên hợp của hàm f f ∗∗ hàm liên hợp của hàm f ∗ δΩ (.) hàm chỉ của tập Ω epi f trên đồ thị của hàm f dom f miền hữu hiệu của hàm f hx∗ , xi giá trị của phiếm hàm x∗ tại x ∂f (x) dưới vi phân của hàm lồi f tại x ∂ε f (x) dưới vi phân xấp xỉ của hàm lồi f tại x A:X→Y toán tử tuyến tính liên tục từ X vào Y A∗ : Y ∗ → X ∗ toán tử liên hợp của toán tử A 3 Mở đầu Giải tích lồi là một bộ môn cơ bản của giải tích hiện đại, nghiên cứu về tập lồi và hàm lồi cùng với những vấn đề liên quan. Bộ môn này có vai trò quan trọng trong nhiều lĩnh vực khác nhau của toán ứng dụng, đặc biệt là trong tối ưu hóa, bất đẳng thức biến phân, các bài toán cân bằng,. . . Các hàm giá trị tối ưu đóng vai trò quan trọng trong giải tích biến phân, tối ưu có ràng buộc, lý thuyết điều khiển, và nhiều ứng dụng khác nhau của các lý thuyết đó. Song song với việc đưa ra các điều kiện đủ để hàm giá trị tối ưu là liên tục Lipschitz địa phương tại một tham số cho trước, trong khoảng 50 năm trở lại đây, người ta quan tâm nghiên cứu tính ổn định vi phân của các bài toán tối ưu theo nghĩa nghiên cứu các tính chất khả vi và khả vi theo hướng của hàm giá trị tối ưu của bài toán đó. Vai trò của tính lồi khi nghiên cứu tính ổn định vi phân khó có thể đánh giá thấp được. Vào những thập niên sáu mươi của thế kỷ trước, một công thức tiên phong dùng để tính toán dưới vi phân của tổng hai hàm lồi được đưa ra bởi J.-J. Moreau và R.T. Rockafellar. Cùng với những nghiên cứu trước đó, các kết quả này dẫn đến một lý thuyết đẹp đẽ về giải tích lồi [5]. Các quy tắc tính toán dưới vi phân có vai trò cực kì quan trọng trong giải tích lồi và quy hoạch lồi. Năm 1965, 4 Brøndsted và Rockafellar [4] đã đưa ra khái niệm ε-dưới vi phân (hay còn gọi là dưới vi phân xấp xỉ) của hàm lồi, đây là khái niệm mở rộng cho khái niệm đạo hàm khi hàm không khả vi. Điều này cho thấy vai trò của dưới vi phân nói chung và dưới vi phân xấp xỉ nói riêng trong giải tích hiện đại cũng có tầm quan trọng như vai trò của đạo hàm trong giải tích cổ điển. Luận văn gồm phần mở đầu, phần kết luận, danh mục tài liệu tham khảo, và ba chương có nội dung như sau: Chương 1: Kiến thức chuẩn bị nhắc lại định nghĩa và các tính chất về tập lồi, hàm lồi, dưới vi phân và dưới vi phân xấp xỉ của hàm lồi. Cuối chương chúng tôi cũng trình bày một số kết quả về hàm liên hợp và định lý tách để phục vụ cho việc chứng minh các kết quả ở hai chương sau. Chương 2: Quy tắc tổng tính dưới vi phân của các hàm lồi nghiên cứu hai phiên bản khác nhau của Định lý Moreau-Rockafellar, một kết quả nổi tiếng của Giải tích lồi trong việc tính toán dưới vi phân của tổng hai hàm lồi, chính thường. Nội dung cuối chương là phần áp dụng các quy tắc tổng trong việc nghiên cứu điều kiện cần và đủ tối ưu của bài toán tối ưu lồi có ràng buộc tập. Các kết quả của chương được tổng hợp từ các tài liệu [1], [2] và [6]. Chương 3: Quy tắc tổng tính dưới vi phân xấp xỉ của các hàm lồi trình bày một quy tắc tổng để tính toán dưới vi phân xấp xỉ của hai hàm lồi, chính thường. Nội dung của chương được dịch và sắp xếp lại từ Mục 3 của bài báo [3]. Các kết quả về điều kiện cần và đủ tối ưu sử dụng dưới vi phân xấp xỉ cũng được nghiên cứu ở cuối chương này. 5 Lời cảm ơn Luận văn này được hoàn thành tại trường Đại học Khoa học, Đại học Thái Nguyên dưới sự hướng dẫn tận tình của TS. Dương Thị Việt An. Em xin bày tỏ lòng biết ơn chân thành tới Cô đã hướng dẫn hiệu quả và truyền cho em những kinh nghiệm nghiên cứu trong quá trình em học tập và hoàn thiện luận văn này. Em cũng xin chân thành cảm ơn các thầy cô trong Khoa Toán Tin, trường Đại học Khoa học, Đại học Thái Nguyên đã giảng dạy và tạo điều kiện thuận lợi cho em trong suốt quá trình em học tập ở trường. Luận văn này chắc chắn sẽ không tránh khỏi những khuyết điểm, vì vậy em rất mong được sự góp ý của các quý thầy cô để luận văn này được hoàn chỉnh hơn. Thái Nguyên, ngày 16 tháng 8 năm 2020 Học viên Nguyễn Trường Giang 6 Chương 1 Kiến thức chuẩn bị Chương này chúng tôi nhắc lại các kiến thức cơ bản về tập lồi, hàm lồi, dưới vi phân và dưới vi phân xấp xỉ của hàm lồi. Nội dung của chương được tham khảo từ các tài liệu [1], [2], và [6]. 1.1 Tập lồi và hàm lồi Cho X là không gian tuyến tính trên trường số thực. Đoạn thẳng nối hai điểm a, b trong X là tập hợp các véctơ x có dạng [a, b] := {x ∈ X | x = λa + (1 − λ)b, λ ∈ [0, 1]}. Định nghĩa 1.1. (Xem [1, trang 3]) Một tập C ⊆ X được gọi là một tập lồi nếu C chứa mọi đoạn thẳng đi qua hai điểm bất kỳ của nó. Tức là, C lồi khi và chỉ khi ∀x, y ∈ C, ∀λ ∈ [0, 1] ⇒ λx + (1 − λ)y ∈ C. Ví dụ 1.1. Đoạn thẳng, tam giác, hình tròn . . . là các ví dụ đơn giản nhất về tập lồi trong mặt phẳng. Giả sử X là không gian lồi địa phương và C ⊆ X là tập lồi. Cho hàm f : C → R = R ∪ {±∞}. Ta ký hiệu miền hữu hiệu của hàm f là 7 y x x y Hình 1: Ví dụ về tập lồi và tập không lồi dom f , được định nghĩa như sau: dom f := {x ∈ C | f (x) < +∞}. Tập epi f := {(x, µ) ∈ C × R | f (x) ≤ µ} được gọi là trên đồ thị của hàm f . Bằng cách cho f (x) = +∞ nếu x∈ / C , ta có thể coi f xác định trên toàn không gian và khi đó dom f = {x ∈ X | f (x) < +∞}, epi f = {(x, µ) ∈ X × R | f (x) ≤ µ}. Do sẽ phải làm việc với cả hàm số nhận giá trị −∞ và +∞ nên như thường lệ ta sẽ quy ước nếu λ = 0 thì λf (x) = 0 với mọi x. Định nghĩa 1.2. (Xem [1, trang 39]) Cho ∅ 6= C ⊆ X và f : C → R. Ta nói f là hàm lồi trên C nếu epi f là một tập lồi trong X × R. Về sau, ta chủ yếu làm việc với hàm f : X → R ∪ {+∞}. Trong trường hợp này, ta có kết quả sau: Định lý 1.1. (Xem [1, trang 40]) Giả sử C là tập con lồi của X , hàm f : C → (−∞, +∞]. Khi đó, f là hàm lồi trên C khi và chỉ khi với mọi λ ∈ [0, 1], ta có f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y), ∀x, y ∈ C. 8 Ví dụ 1.2. Cho C là một tập con lồi của X . Hàm chỉ của tập C được định nghĩa bởi δC (x) =    0 nếu x ∈ C   +∞ nếu x 6∈ C, là hàm lồi. Thật vậy: Ta cần chỉ ra với mọi x, y ∈ X, λ ∈ [0, 1] thì δC (λx + (1 − λ)y) ≤ λδC (x) + (1 − λ)δC (y). (1.1) • Với mọi x, y ∈ C, λ ∈ [0, 1]. Khi đó δC [λx + (1 − λ)y] = λδC (x) + (1 − λ)δC (y) = 0. Suy ra (1.1) đúng. • Với mọi x ∈ C, y ∈ / C, λ ∈ [0, 1] (tương tự cho trường hợp với mọi x∈ / C, y ∈ C ) ta có δC (x) = 0, δC (y) = +∞. Khi đó (1.1) là tầm thường. • Với mọi x, y ∈ / C, λ ∈ [0, 1]. Khi đó δC (x) = δC (y) = +∞. Do đó bất đẳng thức (1.1) đúng. 1.2 Dưới vi phân và Dưới vi phân xấp xỉ Trong chương trình giải tích ở phổ thông, ta đã biết rằng hàm lồi khả vi tại một điểm nào đó thì tiếp tuyến tại điểm đó luôn nằm dưới đồ thị. Tuy nhiên, một hàm lồi có thể không khả vi, ví dụ hàm lồi một biến f (x) = |x| không khả vi tại x = 0. Trong trường hợp này, người ta mở rộng khái niệm đạo hàm bằng dưới vi phân, sao cho vẫn có được các tính chất cơ bản của đạo hàm khi hàm đó khả vi. 9 Cho X là không gian vectơ tôpô lồi địa phương Hausdorff với các không gian đối ngẫu được ký hiệu là X ∗ . Cho tập lồi C ⊂ X , nón pháp tuyến của C tại x̄ ∈ C được cho bởi N (x̄; C) = {x∗ ∈ X ∗ | hx∗ , x − x̄i ≤ 0, ∀x ∈ C}. Định nghĩa 1.3. Cho f : X → R ∪ {+∞}. Ta nói rằng x∗ ∈ X ∗ là dưới gradient của f tại x̄ nếu f (x) − f (x̄) ≥ hx∗ , x − x̄i, ∀x ∈ X. Tập hợp tất cả các dưới gradient của f tại x̄ được gọi là dưới vi phân của hàm f tại x̄, được kí hiệu là ∂f (x̄). Khi đó, ∂f (x̄) = {x∗ ∈ X ∗ | f (x) − f (x̄) ≥ hx∗ , x − x̄i, ∀x ∈ X}. Về mặt hình học, từ định nghĩa dưới vi phân ta thấy rằng hàm affine ϕ(x) := f (x̄) + hx∗ , x − x̄i, ∀x ∈ X có đồ thị là một siêu phẳng tựa của epif tại điểm (x̄, f (x̄)). Từ định nghĩa của dưới vi phân, ta dễ dàng chỉ ra được
x∗ ∈ ∂f (x̄) ⇔ (x∗ , −1) ∈ N (x̄, f (x̄)); epi f . Ví dụ 1.3. Sau đây, ta đưa ra một số ví dụ về dưới vi phân. (a) Xét hàm chuẩn f (x) = kxk với x ∈ X . Tại điểm x = 0, hàm này không khả vi nhưng nó khả dưới vi phân và ∂f (x) = {x∗ ∈ X ∗ | hx∗ , xi ≤ kxk, ∀x}. (b) f = δC là hàm chỉ của một tập lồi C khác rỗng. Khi đó, với x ∈ X , ∂δC (x) = {x∗ ∈ X ∗ | hx∗ , u − xi ≤ δC (u), ∀u}. 10 Với u ∈ / C thì δC (u) = +∞ nên bất đẳng thức này luôn đúng. Vậy ∂δC (x) = {x∗ ∈ X ∗ | hx∗ , u − xi ≤ 0, ∀u ∈ C} = N (x; C), ở đó N (x; C) là nón pháp tuyến của C tại x. Định nghĩa 1.4. Cho f là hàm lồi xác định trên X , x̄ ∈ dom f , và ε ≥ 0. Tập ε-dưới vi phân (dưới vi phân xấp xỉ) của f tại x̄ là tập ∂ε f (x̄) := {x∗ ∈ X ∗ | hx∗ , x − x̄i ≤ f (x) − f (x̄) + ε, ∀x ∈ X}. Tập ∂ε f (x̄) trùng với tập dưới vi phân ∂f (x̄) khi ε = 0. Từ định nghĩa, ta thấy ∂ε f (x̄) là tập lồi. Hơn nữa, với mọi số không âm ε1 , ε2 mà ε1 ≤ ε2 , ta có ∂ε1 f (x̄) ⊂ ∂ε2 f (x̄). Thêm vào đó, \ ∂f (x̄) = ∂0 f (x̄) = ∂ε f (x̄). ε>0 Dưới vi phân xấp xỉ thường được sử dụng trong thực tế bởi hai lý do chính sau đây. Một là hàm lồi có thể không khả dưới vi phân tại những điểm thuộc biên của miền hữu hiệu của nó nhưng trong miền này dưới vi phân xấp xỉ luôn tồn tại. Thứ hai, trong ứng dụng người ta thường chỉ cần tính dưới vi phân một cách xấp xỉ. Ta xét ví dụ sau đây. Ví dụ 1.4. Cho X = R và x̄ = 0. Rõ ràng, hàm f : X → R được cho bởi f (x) =   √  − x nếu x ≥ 0,   +∞ nếu trường hợp khác là hàm lồi, nửa liên tục dưới và x̄ ∈ dom f . Với mọi ε > 0, ta có ∂ε f (x̄) = {x∗ ∈ X ∗ | hx∗ , x − x̄i ≤ f (x) − f (x̄) + ε, ∀x ∈ X}  √ = x∗ ∈ R | x∗ x ≤ − x + ε, ∀x ≥ 0   1 = −∞, − . 4ε 11 Trong khi đó, dễ dàng kiểm tra được ∂f (x̄) = ∅. Định nghĩa 1.5. Tập ε- pháp tuyến (normal directions) Nε (x̄; C) của C tại x̄ ∈ C được định nghĩa bởi Nε (x̄; C) = {x∗ ∈ X ∗ | hx∗ , x − x̄i ≤ ε, ∀x ∈ C}. Từ định nghĩa trên, với x̄ ∈ C , ta có ∂ε δC (x̄) = {x∗ ∈ X ∗ | hx∗ , x − x̄i ≤ ε, ∀x ∈ C} = Nε (x̄; C), với mọi ε ≥ 0. Khi ε = 0, Nε (x̄; C) trùng với tập nón pháp tuyến của C tại x̄. Trong trường hợp tổng quát, Nε (x̄; C) có thể không là nón với ε > 0. 1.3 Một số kết quả bổ trợ Theo định nghĩa hàm liên hợp của hàm f : X → R là hàm f ∗ : X ∗ → R được cho bởi f ∗ (x∗ ) = sup [hx∗ , xi − f (x)] , x∈X ∗ x∗ ∈ X ∗ . Hàm liên hợp của hàm f , kí hiệu bởi f ∗∗ , là hàm xác định trên X , nhận giá trị trong R: f ∗∗ (x) = sup [hx∗ , xi − f ∗ (x∗ )] x∗ ∈X ∗ (x ∈ X). Rõ ràng, hàm f ∗∗ là lồi và đóng (theo nghĩa tập epi f ∗∗ là đóng theo tôpô yếu của X × R). Theo Định lý Fenchel–Moreau (xem [6, Theorem 1, tr. 175]), nếu f là hàm xác định trên X không nhận giá trị −∞, khi đó f = f ∗∗ nếu và chỉ nếu f là lồi và đóng. Cho X là không gian vectơ tôpô lồi địa phương Hausdorff, X ∗ là không gian liên hợp của X , tức là không gian các phiếm hàm tuyến tính liên tục trên X . 12 Định nghĩa 1.6. (Xem [1, trang 63]) Tập hợp M ⊂ X thỏa mãn: bất cứ đường thẳng nào đi qua hai điểm của M cũng nằm chọn trong M được gọi là một đa tạp tuyến tính trong X . Chú ý rằng khái niệm đa tạp tuyến tính chính là khái niệm tập affine trong không gian hữu hạn chiều. Lấy x∗ ∈ X ∗ , x∗ 6= 0, β ∈ R và ký hiệu H(x∗ , β) = {x ∈ X | hx∗ , xi = β}, H + (x∗ , β) = {x ∈ X | hx∗ , xi ≤ β}, H − (x∗ , β) = {x ∈ X | hx∗ , xi ≥ β}. Định nghĩa 1.7. (Xem [1, trang 64]) Với 0 6= x∗ ∈ X ∗ , β ∈ R, tập H(x∗ , β) được gọi là một siêu phẳng trong X . Các tập H + (x∗ , β) và H − (x∗ , β) được gọi là các nửa không gian sinh bởi siêu phẳng H(x∗ , β). Định nghĩa 1.8. (Xem [1, trang 64]) Cho các tập A, B ∈ X . Ta nói phiếm hàm tuyến tính liên tục x∗ 6= 0 tách A và B nếu tồn tại α sao cho hx∗ , yi ≤ α ≤ hx∗ , xi, ∀x ∈ A, ∀y ∈ B. (1.2) Ta nói x∗ tách ngặt A và B nếu (1.2) có dạng hx∗ , yi < α < hx∗ , xi, ∀x ∈ A, ∀y ∈ B. Siêu phẳng đóng H(x∗ , β) = {x ∈ X | hx∗ , xi = β} được gọi là siêu phẳng tách A và B , các tập A và B được gọi là tách được. Định lý 1.2. (Xem [1, trang 71]) (Định lý tách thứ nhất) Giả sử A, B là hai tập lồi trong không gian lồi địa phương X , A ∩ B = ∅, int A 6= ∅. Khi đó, tồn tại x∗ ∈ X ∗ , x∗ 6= 0 tách A và B . 13 H(x∗ , β) A B Hình 2: Minh họa siêu phẳng tách Định lý 1.3. (Xem [1, trang 71]) (Định lý tách thứ hai) Giả sử tập A là tập con lồi đóng trong không gian lồi địa phương X và x̄ 6∈ A. Khi đó tồn tại x∗ 6= 0 thuộc X ∗ tách ngặt A và x̄. 14 Chương 2 Quy tắc tổng tính dưới vi phân của các hàm lồi Trong chương này, chúng tôi trình bày hai phiên bản khác nhau của Định lý Moreau-Rockafellar. Cuối chương chúng tôi cũng đưa ra một áp dụng của các định lý này vào việc nghiên cứu điều kiện cần và đủ cực trị cho bài toán tối ưu lồi có ràng buộc. Nội dung của chương được tham khảo từ các tài liệu [1], [2] và [6]. 2.1 Định lý Moreau-Rockafellar phiên bản cổ điển Định lý sau đây là một kết quả đẹp về tính toán dưới vi phân của tổng các hàm lồi. Định lý này có nhiều phiên bản chứng minh, trong luận văn này chúng tôi trình bày chi tiết lại chứng minh theo cuốn tài liệu [6, trang 48-50]. Định lý 2.1. (Moreau-Rockafellar) Giả sử f1 , ..., fm là các hàm lồi chính thường trên X . Khi đó với ∀x ∈ X , ∂(f1 + ... + fm )(x) ⊇ ∂f1 (x) + ... + ∂fm (x). 15 Hơn nữa, nếu tại điểm x̄ ∈ m T i=1 domfi , tại đó có m − 1 hàm fi liên tục thì ∂(f1 + ... + fm )(x) = ∂f1 (x) + ... + ∂fm (x), ∀x ∈ X. Chứng minh. Ta chứng minh cho trường hợp m = 2. Trường hợp tổng quát dùng quy nạp. Lấy x∗i ∈ ∂fi (x) (i = 1, 2). Khi đó với mọi z ∈ X , ta có hx∗1 , z − xi ≤ f1 (z) − f1 (x), hx∗2 , z − xi ≤ f2 (z) − f2 (x). Cộng vế với vế của hai bất đẳng thức trên ta được hx∗1 + x∗2 , z − xi ≤ (f1 + f2 )(z) − (f1 + f2 )(x). Suy ra x∗1 + x∗2 ∈ ∂(f1 + f2 )(x). Ta chứng minh rằng, nếu f1 liên tục tại x̄ ∈ domf2 thì ∂(f1 + f2 )(x) = ∂f1 (x) + ∂f2 (x). Lấy x∗ ∈ ∂(f1 + f2 )(x), ta cần chỉ ra x∗ có thể phân tích được thành x∗ = x∗1 + x∗2 , trong đó x∗1 ∈ ∂f1 (x) và x∗2 ∈ ∂f2 (x). Ta có int(epif1 ) 6= ∅. Thật vậy vì f1 liên tục tại x̄ nên ∀ε > 0, tồn tại lân cận U mở của x̄ sao cho |f1 (z) − f1 (x̄)| < ε, ∀z ∈ U ⇒ f1 (z) − f1 (x̄) < ε, ∀z ∈ U ⇒ f1 (z) < f1 (x̄) + ε, ∀z ∈ U. Đặt A := {(α, z) ∈ R × X | α > f1 (x̄) + ε, z ∈ U } ⊂ epif1 . Ta có A = (f1 (x̄) + ε, +∞) × U . Suy ra A là tập mở trong R × X . Vậy 16 int(epif1 ) 6= ∅. Xét hai tập hợp sau: C1 = {(α, z) ∈ R × X | α ≥ f1 (x + z) − f1 (x)}. C2 = {(α, z) ∈ R × X | α ≤ hx∗ , zi − f2 (x + z) + f2 (x)}. Khi đó C1 = epif1 − (x, f1 (x)). Thật vậy (α, z) ∈ C1 ⇔ α ≥ f1 (x + z) − f1 (x) ⇔ f1 (x) + α ≥ f1 (x + z) ⇔ (x + z, f1 (x) + α) ∈ epif1 ⇔ (z, α) ∈ epif1 − (x, f1 (x)). • C1 là tập lồi. Thật vậy: Lấy bất kỳ (α1 , z1 ), (α2 , z2 ) ∈ C1 , λ ∈ [0, 1]. Ta có α1 ≥ f1 (x + z1 ) − f1 (x) ⇒ λα1 ≥ λf1 (x + z1 ) − λf1 (x), α2 ≥ f1 (x + z2 ) − f1 (x) ⇒ (1 − λ)α2 ≥ (1 − λ)f1 (x + z1 ) − (1 − λ)f1 (x) Cộng vế với vế của hai bất đẳng thức trên ta được λα1 + (1 − λ)α2 ≥ λf1 (x + z1 ) + (1 − λ)f1 (x + z2 ) − f1 (x)   ≥ f1 λ(x + z1 ) + (1 − λ)(x + z2 ) − f1 (x)   = f1 x + λz1 + (1 − λ)z2 − f1 (x). Suy ra λ(α1 , z1 )+(1−λ)(α2 , z2 ) ∈ C1 . Vậy C1 là tập lồi. Vì int(epif ) 6= ∅, suy ra int C1 6= ∅. • C2 là tập lồi. Thật vậy: Lấy bất kỳ (α1 , z1 ), (α2 , z2 ) ∈ C2 , λ ∈ [0, 1]. Khi đó α1 ≤ hx∗ , z1 i − f2 (x + z1 ) + f2 (x), α2 ≤ hx∗ , z2 i − f2 (x + z2 ) + f2 (x). 17 Suy ra λα1 + (1 − λ)α2 ≤ λhx∗ , z1 i − λf2 (x + z1 ) + λf2 (x) + (1 − λ)hx∗ , z2 i − (1 − λ)f2 (x + z2 ) + (1 − λ)f2 (x) = hx∗ , λz1 + (1 − λ)z2 i   − λf2 (x + z1 ) + (1 − λ)f2 (x + z2 ) + f2 (x) ≤ hx∗ , λz1 + (1 − λ)z2 i   − f2 λ(x + z1 ) + (1 − λ)(x + z2 ) + f2 (x)   = hx∗ , λz1 + (1 − λ)z2 i − f2 x + λz1 + (1 − λ)z2 + f2 (x). Suy ra λ(α1 , z1 ) + (1 − λ)(α2 , z2 ) ∈ C2 . Vậy C2 là tập lồi. • Ta chứng minh C1 ∩ C2 = ∅. Giả sử phản chứng, tồn tại (α0 , z0 ) ∈ C1 ∩ C2 . Khi đó hx∗ , z0 i − f2 (x + z0 ) + f2 (x) > f1 (x + z0 ) − f1 (x). Suy ra hx∗ , z0 i > f1 (x + z0 ) + f2 (x + z0 ) − (f1 (x) + f2 (x)) = (f1 + f2 )(x + z0 ) − (f1 + f2 )(x). Điều này mâu thuẫn với x∗ ∈ ∂(f1 + f2 )(x). Vậy theo Định lý 1.2 tồn tại x∗1 ∈ X ∗ , β ∈ R, (x∗1 , β) 6= (0, 0) sao cho sup (βα + hx∗1 , zi) ≤ (α,z)∈C1 inf (βα + hx∗1 , zi). (α,z)∈C2 Ta sẽ chỉ ra β < 0. Nếu β > 0 thì vế phải của (3.3) có thể là +∞ và vế trái có thể là −∞. Vô lý. 18 Nếu β = 0 thì (3.3) có dạng sup z∈domf1 −x hx∗1 , zi ≤ inf z∈domf2 −x hx∗1 , zi. Mặt khác, x∗1 6= 0 vì β = 0. Do đó hx∗1 , x̄ − xi < sup hx∗1 , zi ≤ z∈U −x inf z∈domf2 −x sup z∈domf1 −x hx∗1 , zi ≤ hx∗1 , x̄ − xi < hx∗1 , zi sup z∈domf1 −x hx∗1 , zi. Điều này mâu thuẫn với (3.4). Vì vậy β < 0. Không giảm tổng quát ta có thể xem β = −1. Như vậy ta đã chứng minh được C1 và C2 được tách bởi siêu phẳng: H = {(α, z) ∈ R × X | α − hx∗1 , zi = 0}. Từ (3.3) ta suy ra sup{hx∗1 , zi − f1 (x + z) + f1 (x)} z ≤ inf {hx∗1 − x∗ , zi + f2 (x + z) − f2 (x)}. z (2.1) Để ý rằng với z = 0 thì vế trái và vế phải của (3.5) đều bằng không. Vì vậy f1 (x + z) − f1 (x) ≥ hx∗1 , zi, ∀z ∈ X. Đặt x∗2 = x∗ − x∗1 , ta được f2 (x + z) − f2 (x) ≥ hx∗2 , zi, ∀z ∈ X. Suy ra x∗i ∈ ∂fi (x) (i = 1, 2). Vậy định lý đã được chứng minh xong. 19