Tài liệu Dưới vi phân hàm véctơ lồi và ứng dụng

Mục lục Lời mở đầu 1 1 Cơ sở giải tích lồi 3 1.1 Tập lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2 Hàm lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.3 Hàm liên hợp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.4 Dưới vi phân . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.5 Đặc trưng hàm lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 1.6 Một số ứng dụng vào bài toán tối ưu . . . . . . . . . . . . . . . . . . . 21 2 Hàm véctơ lồi và ứng dụng 34 2.1 Các khái niệm cơ bản . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 2.2 Tính liên tục, liên tục theo nón . . . . . . . . . . . . . . . . . . . . . . 41 2.3 Dưới vi phân của hàm véctơ lồi . . . . . . . . . . . . . . . . . . . . . . 47 2.4 Hàm liên hợp của hàm véctơ lồi . . . . . . . . . . . . . . . . . . . . . . 52 2.5 Các đặc trưng của hàm véctơ lồi . . . . . . . . . . . . . . . . . . . . . . 56 2.6 Một số ứng dụng vào bài toán tối ưu véctơ . . . . . . . . . . . . . . . . 70 Kết luận 75 Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . i 76 Lời mở đầu Rất nhiều bài toán trong thực tế có thể đưa được về dạng: Tìm x ∈ D sao cho f (x) ≤ f (x), ∀x ∈ D, trong đó, D là tập con của một tập nào đó và f : D → R là hàm số thực. Ta kí hiệu bài toán này là f (x) = min f (x) x∈D (1) và gọi nó là bài toán tối ưu. Bài toán này đóng vai trò trọng tâm trong lý thuyết tối ưu và có những bài toán liên quan như bài toán bất đẳng thức biến phân, bài toán cân bằng, bài toán minimax, bài toán điểm yên ngựa,... Trong trường hợp f là một hàm số khả vi thì bài toán (1) được gọi là tối ưu khả vi hay tối ưu trơn. Trong trường hợp ngược lại, bài toán (1) được gọi là tối ưu không trơn. Đối với tối ưu trơn ta đã có được những điều kiện cần và đủ cấp 1 và cấp 2, có phương pháp giải bằng phương pháp Newton và nhiều phương pháp khác. Trong mấy chục năm qua rất nhiều nhà toán học trên thế giới quan tâm nghiên cứu, tìm ra những phương pháp giải bài toán tối ưu không trơn. Năm 1947, nhà toán học người Mỹ, Danzig, đã tìm ra phương pháp đơn hình để giải bài toán quy hoạch tuyến tính: f là hàm tuyến tính, D là một đa diện lồi. Năm 1960 đến 1970, hai nhà toán học Mỹ là Jean Jacques Moreau và R. T. Ralph Tyrrell Rockafellar, đã đưa ra khái niệm dưới vi phân hàm lồi và từ đó đã hình thành môn Giải tích lồi để giải quy hoạch nói trên. Những năm 1980 nhà toán học Mỹ, Clarke, đưa ra khái niệm dưới vi phân của hàm Lipschitz địa phương và xây dựng nên môn Giải tích Lipschitz. Nhiều nhà toán học khác như J. P. Penot, Urruty, Mordukhovich, Nguyễn Văn Hiền, Strodiot,... cũng đưa ra những khái niệm về dưới vi phân để giải bài toán (1) trong những trường hợp khác. Đặc biệt, Đinh Thế Lục và Jeykumar, năm 1990-2010, đã đưa ra những khái niệm Jacobian xấp xỉ để giải bài toán trong trường hợp tổng quát: f là hàm liên tục và D là tập đóng. Tiếp theo người ta cần phát triển bài toán (1) trong trường hợp f từ tập D vào không gian véctơ khác. Để phát triển được bài toán tối ưu, người ta cần một quan hệ thứ tự, tương đương với điều kiện có một nón trên không gian. Từ thứ tự đó người ta đã phát biểu được các bài toán tối ưu khác nhau như tối ưu lý tưởng, tối ưu Pareto, tối ưu thực sự, tối ưu yếu. Từ đó hình thành nên môn học mới: Tối 1 ưu véctơ, là công cụ để giải quyết những bài toán tối ưu véctơ. Hơn thế, người ta còn nghiên cứu bài toán trên trong trường hợp f là ánh xạ đa trị, đề tài này rất phong phú và hấp dẫn và có nhiều ứng dụng trong thực tế. Chính vì vậy, tôi chọn đề tài cho luận văn thạc sĩ của mình là: "Dưới vi phân hàm véctơ lồi và ứng dụng." Ngoài phần mở đầu, phần kết luận và danh mục tài liệu tham khảo, luận văn gồm hai chương: Chương 1. Giải tích lồi trình bày một số khái niệm và kết quả trong tài liệu [2] về các tính chất cơ bản của giải tích lồi như tập lồi, hàm lồi, các tính chất liên tục, tính Lipschitz, hàm liên hợp, tính khả dưới vi phân hàm lồi và ứng dụng trong các bài toán tối ưu lồi vô hướng. Chương 2. Dưới vi phân hàm véctơ lồi và ứng dụng là nội dung chính của luận văn, trình bày những mở rộng cho các tính chất, kết quả của hàm lồi vô hướng cho hàm véctơ lồi theo nón như các khái niệm về nón, điểm hữu hiệu, tính liên tục theo nón, tính lồi, dưới vi phân, hàm liên hợp, các đặc trưng và một số ứng dụng của dưới vi phân vào bài toán tối ưu véctơ lồi. Luận văn được hoàn thành tại Viện Toán học thuộc Viện Hàn Lâm Khoa Học và Công Nghệ Việt Nam, dưới sự hướng dẫn tận tình của GS. TSKH. Nguyễn Xuân Tấn. Tôi muốn gửi tới Thầy lời biết ơn sâu sắc nhất. Tôi cũng xin gửi lời cảm ơn chân thành tới các Thầy, Cô và các cán bộ, nhân viên của Viện Toán Học, các bạn lớp Cao học K21 và các bạn lớp Cao học quốc tế K8 đã tạo điều kiện thuận lợi cho tôi trong quá trình học cao học và thực hiện bản luận văn này. Hà Nội, ngày 26/08/2015 Tác giả luận văn Nguyễn Thị Phương 2 Chương 1 Cơ sở giải tích lồi Chương này dành cho những kiến thức cơ bản của giải tích lồi cần dùng cho các bài toán tối ưu không trơn. Khi muốn xét sự tồn tại nghiệm hay tìm thuật toán để giải bài toán tối ưu, ta phải trang bị cho tập ràng buộc cũng như những hàm số những cấu trúc đại số và tôpô để mô tả những tính chất đặc thù của từng loại bài toán, từ đó tìm ra phương pháp giải. Ta bắt đầu bằng việc giới thiệu các cấu trúc ấy trên tập hợp. Để khỏi phải nhắc lại nhiều lần, ta giới hạn chỉ trình bày một số kiến thức cơ bản về giải tích lồi như: Tập lồi, hàm lồi, dưới vi phân,... Các kết quả về lý thuyết, về thuật toán, để giải bài toán (1) vẫn đúng cho trường hợp không gian tôpô tuyến tính lồi địa phương Hausdorff. Nhưng để cho người đọc thấy trực quan, trong luận văn này ta chỉ trình bày các vấn đề đó trong không gian hữu hạn chiều. 1.1 Tập lồi Ta kí hiệu R = R ∪ {±∞} là tập số thực mở rộng, h., .i là tích vô hướng trong Rn . Định nghĩa 1.1.1. Đường thẳng nối hai điểm (hai véctơ) a, b trong Rn là tập tất cả các véctơ x ∈ Rn có dạng x = αa + βb, α, β ∈ R, α + β = 1. Đoạn thẳng nối hai điểm a và b trong Rn là tập {x ∈ Rn |x = αa + βb, α ≥ 0, β ≥ 0, α + β = 1}. 3 Tương tự ta có các kí hiệu [a, b) , (a, b], (a, b)... Định nghĩa 1.1.2. Tập C ⊆ Rn đượ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. Dưới đây là một số ví dụ về tập lồi thường gặp Định nghĩa 1.1.3. Cho f ∈ Rn , α là một số thực cố định. H = {x ∈ Rn : hf, xi = α} được gọi là siêu phẳng, H + = {x ∈ Rn : hf, xi ≥ α} được gọi là nửa không gian trên, H − = {x ∈ Rn : hf, xi ≤ α} được gọi là nửa không gian dưới. Ta dễ dàng thấy H, H + , H − đều là các tập lồi xác định bởi f và α. Tiếp theo, ta nhắc lại một số khái niêm liên quan đến tập lồi. Định nghĩa 1.1.4. Cho A ⊂ Rn . i) Bao lồi của A là giao của tất các tập lồi chứa A, kí hiệu là coA; ii) Bao lồi đóng của tập A là giao của tất cả các tập lồi đóng chứa A, kí hiệu là coA. Định nghĩa 1.1.5. Tập hợp con C ⊂ Rn được gọi là nón có đỉnh tại gốc, nếu tx ∈ C, với mọi x ∈ C và t ≥ 0. Tập C ⊂ Rn được gọi là nón có đỉnh tại x0 , nếu tập C − {x0 } là nón có đỉnh tại gốc. Định nghĩa 1.1.6. i) Nón C được gọi là nón nhọn, nếu l(C) := C ∩ (−C) = {0}. ii) Nón cực của một nón C được định nghĩa là tập C 0 := {ξ ∈ L(Rn , R) : ξ(x) ≥ 0, ∀x ∈ C}. Khái niệm nón cho ta một quan hệ thứ tự mới trên không gian Rn . Định nghĩa 1.1.7. Với nón lồi C cho trước, ta định nghĩa quan hệ thứ tự từng phần C trên Rn như sau: x, y ∈ Rn , x C y, nếu x − y ∈ C. 4 Nếu không có sự nhầm lẫn, ta có thể viết đơn giản x  y. Cho x, y ∈ Rn , ta kí hiệu x  y, nếu x − y ∈ C \ lC và x  y, nếu x − y ∈ intC. Trong lý thuyết tối ưu ta sẽ thấy có những kết quả liên quan tới việc tách các tập lồi, chúng làm nền tảng cho những điều kiện cần và đủ để tồn tại nghiệm của bài toán tối ưu có ràng buộc. Sau đây, ta đưa ra một số khái niệm liên quan tới tách các tập lồi. Định nghĩa 1.1.8. Cho các tập A, B ⊂ Rn . Ta nói phiếm hàm tuyến tính liên tục f 6= 0 tách A và B, nếu tồn tại một số α sao cho hf, yi ≤ α ≤ hf, xi , ∀x ∈ A, ∀y ∈ B. (1.1) Nếu các bất đẳng thức ở (1.1) là thực sự, tức là, hf, yi < α < hf, xi , ∀x ∈ A, ∀y ∈ B, thì ta nói f tách chặt A và B. Siêu phẳng H = {x ∈ Rn : hf, xi = α} gọi là siêu phẳng tách A và B. Các tập A, B gọi là tách được. Phần chứng minh của những kết quả sau đây có thể tìm thấy trong [2]. Định lý 1.1.9. (Định lý tách thứ nhất). Cho A và B là các tập lồi trong Rn , A∩B = ∅. Khi đó, tồn tại phiếm hàm tuyến tính liên tục f 6= 0, f ∈ Rn tách A và B. Hệ quả 1.1.10. Cho A, B là các tập lồi trong Rn . Khi đó, A, B tách được khi và chỉ khi (intA) ∩ B = ∅. Định lý 1.1.11. Giả sử A là tập lồi đóng trong không gian Rn và x0 ∈ / A. Khi đó, tồn tại f ∈ Rn , f 6= 0 tách chặt A và x0 . Hệ quả sau đây được suy ra trực tiếp Định lý 1.1.11. Hệ quả 1.1.12. Cho A ⊂ Rn . Ta có i) coA trùng với giao của tất cả các nửa không gian chứa A; ii) Nếu A là tập lồi khi đó A đóng khi và chỉ khi A đóng. Định lý 1.1.13. (Định lý tách thứ hai). Cho A, B là hai tập lồi đóng khác rỗng sao cho A ∩ B = ∅. Giả sử có ít một trong hai tập là compact. Khi đó, hai tập này có thể tách mạnh được bởi một siêu phẳng. 5 1.2 Hàm lồi Trong mục này ta đưa ra một số tính chất của hàm số liên quan tới cấu trúc đại số và cấu trúc tôpô. Định nghĩa 1.2.1. Cho C ⊆ Rn là một tập lồi và f : C → R ∪ {±∞}. Ta kí hiệu domf := {x ∈ C|f (x) < ∞}. Tập domf được gọi là miền hữu hiệu của f. Tập epif := {(x, µ) ∈ C × R|f (x) ≤ µ} được gọi là trên đồ thị của hàm f. Tập lev (f, α) = {x ∈ C : f (x) ≤ α} được gọi là tập mức của f tại α ∈ R. Định nghĩa 1.2.2. 1) Hàm f được gọi là hàm lồi, nếu epif là tập lồi trong không gian tích C × R; 2) Hàm f gọi là hàm chính thường nếu domf 6= ∅ và f (x) > −∞, với mọi x ∈ C. Trong luận văn, để khỏi phải nhắc lại nhiều lần, ta luôn giả thiết hàm lồi là chính thường. Mệnh đề 1.2.3. ([2]). Hàm f : C → R xác định trên tập lồi C ⊆ Rn được gọi là 1. Hàm lồi khi và chỉ khi ∀x1 , x2 ∈ C, ∀λ ∈ [0, 1] ta có f (λx1 + (1 − λ)x2 ) ≤ λf (x1 ) + (1 − λ)f (x2 ); 2. Hàm lồi chặt, nếu ∀x1 , x2 ∈ Rn , ∀λ ∈ (0, 1) ta có f (λx1 + (1 − λ)x2 ) < λf (x1 ) + (1 − λ)f (x2 ); 3. Hàm lồi mạnh, với hệ số β > 0 nếu ∀x1 , x2 ∈ C, ∀λ ∈ (0, 1), ta có 1 f (λx1 + (1 − λ)x2 ) ≤ λf (x1 ) + (1 − λ)f (x2 ) − λ (1 − λ) βkx1 − x2 k2 ; 2 6 4. Hàm lõm (lõm chặt), nếu −f là hàm lồi (lồi chặt); 5. Hàm f tựa lồi nếu và chỉ nếu lev (f + g, α) là tập lồi ∀g, α ∈ R, trong đó (f + g) (x) = f (x) + g (x) . Chú ý 1.2.4. 1) Nếu f là hàm lồi thì domf là tập lồi; 2) Nếu f là hàm lồi thì {x : f (x) < α} , {x : f (x) ≤ α} là các tập lồi ∀α ∈ [−∞, +∞] . 1.2.1 Tính liên tục Tính chất lồi của một hàm kéo theo nhiều tính chất tôpô quan trọng, mặc dù trong định nghĩa hàm lồi ta không đòi hỏi một cách trực tiếp đến bất kỳ tính chất tôpô nào. Trước hết, ta nhắc lại rằng hàm f : D ⊂ Rn → R được gọi là nửa liên tục dưới tại điểm x ∈ D, nếu như với mọi dãy {xk } ⊂ D, xk → x ta có liminf f (xk ) ≥ f (x). k→∞ Hàm f được gọi là nửa liên tục trên tại điểm x ∈ D nếu −f nửa liên tục dưới tại x. Hay là với mọi dãy {xk } ⊂ D, xk → x ta có limsup(xk ) ≤ f (x). Hàm f được gọi là k→∞ nửa liên tục tại x nếu như nó vừa nửa liên tục trên và nửa liên tục dưới tại x. Hàm f được gọi là nửa liên tục dưới, nếu nó nửa liên tục dưới tại mọi điểm thuộc D. Tương tự, ta cũng nói như vậy với hàm nửa liên tục trên và hàm liên tục. Các kết quả sau có thể tìm thấy chứng minh trong tài liệu [2]. Định nghĩa 1.2.5. i) Bao đóng của hàm f là một hàm, kí hiệu clf, có trên đồ thị epi cl f = epif ; ii) Bao lồi đóng của hàm f là một hàm, kí hiệu cof, có trên đồ thị epi(cof ) = co(epif ); iii) Hàm f được gọi là đóng nếu epif là tập đóng trong Rn × R. Chú ý 1.2.6. Các khẳng định sau đây là đúng. i) Hàm f là lồi thì clf cũng là lồi; 7 ii) Hàm f là đóng khi và chỉ khi f = clf . Mệnh đề 1.2.7. Hàm f là đóng khi và chỉ khi lev (f, α) = {x : f (x) ≤ α} là tập đóng với α ∈ R. Mệnh đề 1.2.8. Hàm f là đóng khi và chỉ khi f là nửa liên tục dưới. Định lý sau cho ta các điều kiện để hàm lồi liên tục. Định lý 1.2.9. ([2]). Cho f là hàm lồi chính thường trên Rn khi đó các khẳng định sau là tương đương. i) f bị chặn trên tại lân cận của x0 ∈ Rn ; ii) f liên tục tại x0 ; iii) int(epif ) 6= ∅; vi) int(domf ) 6= ∅ và f liên tục trên int(domf ). 1.2.2 Tính Lipschitz Tính Lipschitz của hàm đóng vai trò quan trọng trong việc nghiên cứu những bài toán tối ưu. Trước tiên, ta đưa ra một số khái niệm cơ bản sau Định nghĩa 1.2.10. Hàm f : D ⊂ Rn → R được gọi là Lipschitz trên D nếu tồn tại hằng số L ≥ 0 sao cho |f (x) − f (y)| ≤ Lkx − yk, ∀x, y ∈ D. L được gọi là hằng số Lipschitz. Hàm f được gọi là Lipschitz địa phương tại điểm x̄ ∈ D nếu tồn tại lân cận U của x̄ để f Lipschitz trên U ∩ D. Hàm f được gọi là Lipschitz địa phương trên tập D ⊂ Rn nếu nó Lipschitz địa phương tại mọi điểm thuộc D. Định lý 1.2.11. ([2]). Giả sử f là hàm lồi chính thường trên Rn và bị chặn trên trong một lân cận của một điểm nào đó thuộc một tập mở D ⊂ domf . Khi đó, f Lipschitz địa phương trên tập D. Hệ quả 1.2.12. ([2]). Giả sử f : D → R là hàm lồi liên tục tại x0 thuộc tập lồi mở D. Khi đó, f Lipschitz địa phương trên D. 8 1.3 Hàm liên hợp Hàm liên hợp có một vai trò quan trọng trong lý thuyết tối ưu, đặc biệt là trong lý thuyết đối ngẫu. Trong phần này, trước hết chúng ta sẽ giới thiệu định nghĩa và đưa ra ví dụ minh họa cho hàm liên hợp. Tiếp đến sẽ khảo sát một số tính chất và quy tắc cơ bản cho việc tính toán với hàm liên hợp. 1.3.1 Phép biến đổi Young - Fenchel Ta có thể cho tương ứng hàm cho trước với một hàm lồi như sau: Định nghĩa 1.3.1. Phép biến đổi Young - Fenchel của hàm f : D ⊂ Rn → R hay hàm liên hợp của hàm f là hàm f ∗ : D∗ ⊂ Rn → R được xác định: f ∗ (x∗ ) = sup {hx∗ , xi − f (x)} . (1.2) x∈D Mệnh đề 1.3.2. f ∗ là hàm lồi đóng. Chứng minh. Với x cố định, hàm g (x∗ ) := hx∗ , xi − f (x) là hàm tuyến tính trên Rn . Do đó, g (x∗ ) lồi đóng. Trên đồ thị của f ∗ (x∗ ) là giao của trên đồ thị các hàm g (x∗ ), tức là, giao của các tập lồi đóng . Vì vậy, epif ∗ lồi đóng . Nhận xét. Từ Định nghĩa 1.3.1 ta có f (x) + f ∗ (x∗ ) ≥ hx∗ , xi , ∀x, x∗ ∈ Rn . Bất đẳng thức (1.3) gọi là bất đẳng thức Young - Fenchel. Ví dụ 1.3.3. Cho hàm f (x) = hx0 ∗ , xi + α, ∀x, x∗ ∈ Rn . ∗ ∗ ∗ ∗ ⇒ f (x ) = sup hx − x0 , xi − α x 9 =   −α, khi x∗ = x0 ∗ ,  ∞, khi x∗ 6= x0 ∗ . (1.3) 1.3.2 Tính chất của hàm liên hợp Từ Định nghĩa 1.3.1, suy ra f ∗∗ (x) = (f ∗ )∗ (x) = sup {hx∗ , xi − f ∗ (x∗ )} . (1.4) x∗ Mệnh đề 1.3.4. Với hàm bất kỳ ta có f ∗∗ ≤ f . Chứng minh. f ∗∗ (x) = sup {hx∗ , xi − f ∗ (x∗ )} x∗   ∗ ∗ = sup hx , xi − sup {hx , xi − f (x)} x∗ = sup x∗ x   hx∗ , xi + inf {f (x) − hx∗ , xi} x     ≤ sup {hx∗ , xi + f (x) − hx∗ , xi} x∗ = f (x) . Định lý 1.3.5. Giả sử f là hàm lồi chính thường đóng trên Rn . Khi đó, f ∗ là hàm lồi chính thường. Chứng minh. Theo Mệnh đề 1.3.2, f ∗ là hàm lồi. Ta chứng minh f ∗ là hàm chính thường. Lấy x0 ∈ domf ta có f ∗ (x∗ ) ≥ hx0 ∗ , x0 i − f (x0 ) > −∞, ∀x∗ ∈ Rn . Hơn nữa, (x0 , f (x0 ) − 1) ∈ / epif, theo Định lý tách thứ hai tồn tại (y0 ∗ , β0 ) sao cho sup {hy0 ∗ , x0 i + βo α} < hy0 ∗ , x0 i + βo (f (x0 ) − 1) . (1.5) (x,α)∈epif Rõ ràng βo 6= 0 và βo không thể là số dương vì nếu βo > 0 thì cận trên của vế trái bằng +∞. Chia hai vế của (1.5) cho |βo | , ta có  
 sup |β0 |−1 y0 ∗ , x − f (x) = f ∗ |β0 |−1 y0 ∗ < |β0 |−1 y0 ∗ , x0 + 1 − f (x0 ) < ∞. x∈domf Suy ra điều cần chứng minh. 10 Định lý 1.3.6. Cho A : Rn → Rm là phép đồng phôi tuyến tính, g là hàm xác định trên Rm . Đặt f (x) = λg (Ax + y0 ) + hx0 ∗ , xi + γ0 trong đó, y0 ∈ Rm , x0 ∗ ∈ Rn ,
∗ γ0 ∈ R, λ > 0. Khi đó, f ∗ (x∗ ) = λg λ−1 A−1 (x∗ − x0 ∗ ) − hx∗ − x0 ∗ , A−1 y0 i − γ0 . Chứng minh. f ∗ (x∗ ) = sup {hx∗ , xi − λg (Ax + y0 ) − hx0 ∗ , xi − γ0 } . x Đặt y = Ax + y0 ta được    ∗ f ∗ (x∗ ) = λ sup λ−1 A−1 (x∗ − x0 ∗ ) , y − g (y) − x∗ − x0 ∗ , A−1 y0 − γ0 y
 ∗ = λg ∗ λ−1 A−1 (x∗ − x0 ∗ ) − x∗ − x0 ∗ , A−1 y0 − γ0 . Hệ quả 1.3.7. i) f (x) = g (x + x0 ) ⇒ f ∗ (x∗ ) = g ∗ (x∗ ) − hx∗ , x0 i ; ii) f (x) = g (x) + hx0 ∗ , xi ⇒ f ∗ (x∗ ) = g ∗ (x∗ − x0 ∗ ) ; iii) f (x) = λg (x) , λ > 0 ⇒ f ∗ (x∗ ) = λg ∗ (λ−1 x∗ ) ; iv) f (x) = λg (λ−1 x) , λ > 0 ⇒ f ∗ (x∗ ) = λg ∗ (x∗ ) ; v) f (x) = g (λx) , λ > 0 ⇒ f ∗ (x∗ ) = g ∗ (λ−1 x∗ ) . Định lý 1.3.8. (Định lý Fenchel - Moreau). Cho f : Rn → (−∞, +∞], khi đó f = f ∗∗ ⇔ f lồi đóng. Chứng minh. Theo Hệ quả 1.1.12, A là tập lồi. ⇒) Giả sử f = f ∗∗ theo Mệnh đề 1.3.2, f ∗∗ là hàm lồi đóng. Vậy, f ∗∗ lồi đóng. ⇐) Giả sử f lồi đóng. +) Nếu f (x) = +∞ thì hiển nhiên f = f ∗∗ . +) Nếu f (x) < +∞ theo Mệnh đề 1.3.4 f ∗∗ ≤ f. Vì vậy, ta cần chứng minh, nếu f là hàm lồi chính thường, đóng thì f ≤ f ∗∗ . Thật vậy, giả sử ∃x0 ∈ domf ∗∗ sao cho f (x0 ) > f ∗∗ (x0 ) . Ta có epif là tập lồi đóng, epif 6= ∅ và (x0 , f ∗∗ (x0 )) ∈ / epif . Theo Định lý tách thứ hai, tồn tại (y ∗ , β) ∈ Rn × R tách chặt (x0 , f ∗∗ (x0 )) và epif tức là sup {hy ∗ , yi + βα} < hy ∗ , x0 i + βf ∗∗ (x0 ) . (y,α)∈epif 11 (1.6) Khi đó, β ≤ 0 và nếu β > 0 thì cận trên phải bằng +∞. Mặt khác, theo Định lý 1.3.5, f ∗ là hàm lồi chính thường, như vậy domf ∗ 6= ∅. Nếu β = 0, lấy y1 ∗ ∈ domf ∗ , với t > 0 ta có f ∗ (y1 ∗ + ty ∗ ) = sup {hy1 ∗ + ty ∗ , yi − f (y)} y∈domf ≤ sup {hy1 ∗ , yi − f (y)} + t sup hy ∗ , yi y∈domf y∈domf = f ∗ (y1 ∗ ) + t sup hy ∗ , yi . (1.7) y∈domf Từ (1.6), với β = 0 suy ra hy ∗ , xi > sup hy ∗ , yi . y∈domf Vì vậy, từ (1.7) ta có f ∗∗ (x0 ) ≥ hy1 ∗ + ty ∗ , x0 i − f ∗ (y1 ∗ + ty ∗ )   ∗ ∗ ∗ ∗ ∗ ≥ hy1 , x0 i − f (y1 ) + t hy , x0 i − sup hy , yi . y∈domf Cho t → +∞, ta suy ra f ∗∗ (x0 ) = +∞ và như vậy x0 ∈ / domf ∗∗ mâu thuẫn với x0 ∈ domf ∗∗ ở trên. Từ đó ta có thể kết luận trường hợp β = 0 không xảy ra. Vậy, β < 0. Chia cả hai vế của (1.6) cho |β| và đặt x∗ = |β|−1 y ∗ ta được hx∗ , x0 i − f ∗∗ (x0 ) > sup {hx∗ , yi − α} (y,α)∈epif ≥ sup {hx∗ , yi − f (y)} = f ∗ (x∗ ) y∈domf ⇒ hx∗ , x0 i > f ∗∗ (x0 ) + f ∗ (x∗ ) . Điều này mâu thuẫn với bất đẳng thức Young - Fenchel. Định lý được chứng minh. Hệ quả 1.3.9. Giả sử f là hàm lồi chính thường đóng trên Rn . Khi đó,  f (x) = sup h (x) : h − affine liên tục, h ≤ f } . Chứng minh. Theo Định lý Fenchel - Moreau, f = f ∗∗ . Do đó, f (x) là lân cận trên 12 của các hàm affine có dạng x → hx∗ , xi − f ∗ (x∗ ) , (x∗ ∈ domf ∗ ) . Như vậy, f (x) = sup {hx∗ , xi − f ∗ (x∗ )} x  ≤ f (x) = sup h (x) : h − affine liên tục, h ≤ f } ≤ f (x).  Vì vậy f (x) = sup h (x) : h − affine liên tục, h ≤ f } . Hệ quả 1.3.10. Giả sử cof là hàm chính thường. Khi đó, f ∗∗ = cof. Chứng minh. Ta có epif ∗∗ là tập lồi đóng. Do f ≥ f ∗∗ nên epif ∗∗ ⊂ epif. Do đó, epif ⊆ co (epif ) ⊆ epif f ∗∗ ⇒ f ≥ cof ≥ f ∗∗ . (1.8) Chú ý rằng, nếu f1 ≤ f2 thì f1 ∗ ≥ f2 ∗ . Vì vậy, f ∗ ≤ (cof )∗ ⇒ f ∗∗ ≥ (cof )∗∗ ≥ cof. (1.9) Từ (1.8) và (1.9) suy ra f ∗∗ = cof. Hệ quả 1.3.11. Giả sử cof là hàm chính thường, khi đó f ∗ = (cof )∗ . Chứng minh. Theo Hệ quả 1.3.10, f ∗∗ = cof ⇒ (f ∗ )∗∗ = (cof )∗ . Theo Mệnh đề 1.3.2, f ∗ là hàm lồi đóng nên theo Định lý 1.3.8 thì (f ∗ )∗∗ = f ∗ . Vậy ta có f ∗ = (cof )∗ . 1.4 Dưới vi phân Tính khả vi phân của hàm lồi đóng vai trò quan trọng trong các bài toán tối ưu, trong các phương pháp tối ưu. Cho D ⊂ Rn , f : D → R̄, |f (x)| < +∞. Ta biết rằng trong trường hợp f khả vi tại x0 ∈ domf, thì tại lân cận của x0 , f được xấp xỉ một cách khá tốt bởi đạo hàm của nó. Hàm lồi, nói chung không khả vi, ta phải tìm cách tiếp cận khác. 13 Định nghĩa 1.4.1. Đạo hàm của f theo phương d tại x0 ∈ Rn , kí hiệu f 0 (x0 , d), được định nghĩa f (x0 + λd) − f (x0 ) , λ→0 λ f 0 (x0 , d) = lim nếu giới hạn này tồn tại (có thể hữu hạn hoặc bằng ±∞). Định nghĩa 1.4.2. Cho f : Rn → R là một hàm lồi. Một véctơ ξ ∈ Rn là dưới gradient của f tại x ∈ Rn nếu f (y) − f (x) > ξ(y − x), ∀y ∈ Rn . Định nghĩa 1.4.3. Tậ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, kí hiệu là ∂f (x), tức là, ∂f (x) = {ξ : f (y) − f (x) > ξ(y − x), ∀y ∈ Rn . Định nghĩa 1.4.4. Cho D là một tập lồi không rỗng của Rn và x0 ∈ D. Hướng d được gọi là hướng chấp nhận được của D tại x0 nếu tồn tại một số λ > 0 sao cho x0 + λd ∈ D. Tập hợp tất cả các hướng chấp nhận được của D tại x0 được kí hiệu là T (D, x0 ). Chú ý 1.4.5. Nếu f là hàm lồi chính thường trên Rn thì i) f 0 (x0 , .) là hàm thuần nhất dương trên Rn , tức là với mọi λ > 0, f 0 (x0 , λd) = λf 0 (x0 , d) ; ii) Với mọi x ∈ domf thì f 0 (x0 , .) là dưới tuyến tính. Mệnh đề 1.4.6. ([2]). Cho hàm f : Rn → R̄ là hàm lồi chính thường trên Rn . Khi đó, f có đạo hàm theo phương tại mọi điểm x ∈ domf đồng thời f 0 (x0 , d) = inf λ>0 f (x0 + λd) − f (x0 ) . λ Định nghĩa 1.4.7. i) Tập K ⊂ Rn được gọi là nón có đỉnh tại 0 nếu ∀x ∈ K, ∀λ > 0 thì λx ∈ K; ii) Tập K được gọi là nón có đỉnh tại x0 nếu K − x0 là nón có đỉnh tại 0; iii) Nón K có đỉnh tại 0 được gọi là nón lồi nếu ∀x, y ∈ K, ∀α, β > 0 : αx + βy ∈ K; 14 iv) Nếu K là lồi đóng thì nó được gọi là nón lồi đóng; v) Giao của tất cả các nón lồi có đỉnh tại 0 chứa tập A và điểm 0 là một nón lồi và được gọi là nón lồi sinh bởi A kí hiệu là KA . Mệnh đề 1.4.8. Giả sử f là hàm thuần nhất dương trên Rn , khi đó: i) Nếu f liên tục tại mọi điểm của U ⊂ Rn thì f liên tục tại mọi điểm của nón KU sinh bởi điểm U có thể trừ điểm 0; ii) Nếu f liên tục trong một lân cận của 0 thì f liên tục trên Rn . Chứng minh. i) Lấy x0 6= 0, x0 ∈ KU , khi đó tồn tại λ > 0 : λx0 ∈ U. Do f liên tục tại điểm λx0 nên ∀ε > 0, tồn tại lân cận V của λx0 sao cho |f (x) − f (x0 )| < λε ∀x ∈ V ; Như vậy λ1 V là một lân cận của x0 và với mọi x ∈ λ1 V , ta có |f (x) − f (x0 )| = 1 |f (λx) − f (λx0 )| < ε. λ Vậy f liên tục tại x0 . ii) Giả sử f liên tục tại lân cận W của 0, theo i) f liên tục tại mọi điểm của nón KW sinh bởi tập W (có thể trừ điểm 0). Ta có KW = Rn và tại điểm 0 ta đã giả thiết f liên tục. Vậy, f liên tục trên Rn . Phần chứng minh của các kết quả dưới đây có thể xem trong [2]. Định lý 1.4.9. Cho f : Rn → R̄ là một hàm lồi chính thường trên Rn liên tục tại các điểm của tập U ⊂ Rn . Khi đó: i) Nếu tại d0 ∈ Rn thoả mãn x + d0 ∈ U mà f 0 (x, d0 ) hữu hạn thì hàm f (x, .) liên tục tại mọi điểm của nón KU −x sinh bởi tập U − x (có thể trừ điểm 0); ii) Nếu f liên tục tại x thì f 0 (x, .) hữu hạn và liên tục trên Rn . Mệnh đề 1.4.10. Tại mỗi x ∈ D ta có T (D, x) là một nón lồi. Mệnh đề 1.4.11. Cho f là một hàm lồi từ một tập con lồi không rỗng D ⊆ Rn vào R̄ và x ∈ D, d ∈ T (D, Rn ), khi đó: 15 i) f có đạo hàm theo hướng d khi và chỉ khi tập  f (x + λd) − f (x) , λ > 0, x + λd ∈ D λ  bị chặn dưới và  0 f (x, d) = inf  f (x + λd) − f (x) , λ > 0, x + λd ∈ D ; λ ii) f 0 (x, .) là hàm thuần nhất dương, lồi khi domf 0 (x, .) lồi. Hệ quả 1.4.12. f (x, .) là hàm thuần nhất dương lớn nhất xác định trên domf 0 (x, .) có tính chất f (x + λd) − f (x) ≥ f 0 (x, λd) , ∀d ∈ domf 0 (x, .) , λ > 0; x + λd ∈ D. Mệnh đề 1.4.13. Cho hàm f lồi chính thường trên Rn và x ∈ domf. Khi đó các khẳng định sau đây là tương đương: i) x∗ ∈ ∂f (x0 ); ii) f (x0 ) + f ∗ (x∗ ) = hx∗ , x0 i ; iii) f 0 (x0 , d) ≥ hx∗ , di , ∀d ∈ X. Định lý 1.4.14. (Định lý Moreau-Rockafellar) i) Cho f1 , f2 là các hàm lồi chính thường trên Rn . Khi đó, ∂f1 (x) + ∂f2 (x) ⊆ ∂f (f1 + f2 ) (x) , ∀x ∈ Rn ; ii) Nếu tại x0 ∈ domf1 ∩ domf2 một trong hai hàm liên tục thì ∂f1 (x) + ∂f2 (x) = ∂f (f1 + f2 ) (x) , ∀x ∈ Rn . Chú ý 1.4.15. Bằng phương pháp quy nạp ta có thể chứng minh Định lý 1.4.14 trong trường hợp tổng quát. Cho f1 , f2 , ..., fm là các hàm lồi chính thường trên Rn . Khi đó, i) Với mọi x ∈ Rn , ∂f1 (x) + ∂f2 (x) + ... + ∂fm (x) ⊆ ∂f (f1 + f2 + ... + fm ) (x) ; 16 ii) Nếu tại x ∈ m T domfi tất cả các hàm fi
i = 1, m liên tục (có thể trừ một hàm) i=1 thì ∂f1 (x) + ∂f2 (x) + ... + ∂fm (x) = ∂f (f1 + f2 + ... + fm ) (x) . Mệnh đề 1.4.16. Cho hàm lồi f từ một tập khác rỗng D ⊂ Rn vào R̄ và x ∈ D. Nếu f khả vi dưới vi phân tại x thì domf (x, .) = T (D, x). Mệnh đề 1.4.17. Cho f là một hàm lồi từ tập con lồi không rỗng D ⊆ Rn vào R̄ và
x ∈ D, ξ ∈ L x, R . Khi đó, ξ ∈ ∂f (x) ⇔ ξ (d) ≤ f 0 (x, d) , ∀d ∈ T (D, x) . Định lý 1.4.18. (Định lý giá trị trung bình). Cho [x, y] là một đoạn thẳng trong tập mở mà hàm f là hàm lồi. Khi đó, tồn tại u ∈ (x, y) sao cho f (y) − f (x) ∈ {ξ(y − x) | ξ ∈ ∂f (u)}. Mệnh đề dưới đây cho ta một định nghĩa khác tương đương với định nghĩa của dưới vi phân. Mệnh đề 1.4.19. ([1], Chương 11, Mệnh đề 11.2). Cho f : Rn → R ∪ {+∞} lồi, chính thường. i) x∗ ∈ ∂f (x) khi và chỉ khi f 0 (x, y) ≥ hx∗ , yi, ∀y. Nếu x ∈ ri(domf ) thì f 0 (x, y) = sup hx∗ , yi, ∀y. x∗ ∈∂f (x) ii) Nếu f là hàm lồi chính thường trên Rn thì với mọi x ∈ dom(∂f ), ta có f (x) = f¯(x) và ∂f (x) = ∂ f¯(x). Mệnh đề 1.4.20. ([1], Chương 11, Mệnh đề 11.3). Cho f : Rn → R ∪ {+∞} lồi, chính thường. Khi đó: i) Nếu x ∈ domf thì ∂f (x) 6= ∅; ii) Nếu x ∈ int(domf ) thì ∂f (x) 6= ∅ và compact. Ngược lại, nếu ∂f (x) 6= ∅, compact thì x ∈ ri(domf ). 17 Ví dụ sau đây cho thấy nếu x ∈ / int(domf ) thì tập ∂f (x) có thể bằng rỗng. Cho hàm một biến f (x) =   −2x1\2 , x ≥ 0,  +∞, x < 0. Khi đó, ∂f (0) = ∅. Mệnh đề 1.4.21. Cho f là một hàm lồi chính thường trên Rn . Khi đó, i) Với mọi tập bị chặn C ⊂ ri(domf ), ∪ ∂f (x) bị chặn, với riA là phần trong tương x∈C đối của A với tôpô sinh cảm sinh từ không gian affin nhỏ nhất chứa A; ii) Nếu có thêm f đóng thì có đẳng thức Fenchel sau: f ∗ (x∗ ) + f (x) = hx∗ , xi ⇔ x∗ ∈ ∂f (x), x ∈ ∂f ∗ (x∗ ). Mệnh đề 1.4.22. Giả sử f : Rn → R ∪ {+∞} lồi, chính thường và x ∈ domf . Khi đó, f khả vi tại x khi và chỉ khi tồn tại x∗ ∈ Rn sao cho f 0 (x, y) = hx∗ , yi, ∀y. Ngoài ra, x ∈ int(domf ) và ∇f (x) = x∗ . 1.5 Đặc trưng hàm lồi Trước khi đưa ra đặc trưng của hàm lồi ta cần nhắc lại một số khái niệm liên quan đến ánh xạ đơn điệu và Hessian suy rộng của hàm lồi. Định nghĩa 1.5.1. Ánh xạ F : C → Rn được gọi là đơn điệu trên C, nếu hF (x) − F (y), x − yi ≥ 0, ∀x, y ∈ DomF. Ánh xạ F được gọi là đơn điệu mạnh trên C với hệ số β > 0, nếu hF (x) − F (y), x − yi ≥ βkx − yk2 , ∀x, y ∈ DomF. Ta có thể mở rộng khái niệm này cho trường hợp ánh xạ đa trị. n Định nghĩa 1.5.2. ([1]). Ánh xạ đa trị T : Rn → 2R được gọi là đơn điệu trên 18 C ⊆ domT, nếu với mọi cặp (x1 , y 1 ), (x2 , y 2 ) ∈ G(T ), xi ∈ C, (i = 0, ..., m), ta có hy 2 − y 1 , x2 − x1 i ≥ 0, ∀y 1 ∈ T (x1 ), ∀y 2 ∈ T (x2 ). (1.10) Sau đây là đặc trưng của hàm lồi cho trường hợp khả vi. Mệnh đề 1.5.3. ([1]). Cho f : Rn → R ∪ {+∞} khả vi và C ⊂ Rn . Các điều kiện sau là tương đương: i) f lồi, chính thường trên C; ii) hf 0 (y) − f 0 (x), y − xi ≥ 0, ∀x, y ∈ domf. Kết quả này được mở rộng cho trường hợp không khả vi như sau. Mệnh đề 1.5.4. Giả sử S là một toán tử từ Rn vào Rn . Điều kiện cần và đủ để tồn tại một hàm lồi, đóng, chính thường f trên Rn sao cho S(x) ⊆ ∂f (x), ∀x ∈ ∂f (x), là toán tử S đơn điệu. Hệ quả trực tiếp của mệnh đề này là đặc trưng cấp 1 của hàm lồi chính thường không khả vi. Hệ quả 1.5.5. Điều kiện cần và đủ để hàm f : C ⊂ Rn → R lồi đóng chính thường là n ánh xạ dưới vi phân ∂f (.) : C → 2R là toán tử đơn điệu. Tiếp theo ta nhắc lại một số khái niệm liên quan đến tính liên tục của ánh xạ đa trị n Định nghĩa 1.5.6. Ánh xạ T : Rn → 2R được gọi là đóng tại x, nếu với mọi dãy xk → x, mọi y k ∈ T (xk ) và y k → y, thì y ∈ T (x). n Định nghĩa 1.5.7. Ánh xạ T : Rn → 2R được gọi là nửa liên tục trên (dưới) tại x, nếu với mọi tập mở G chứa T (x)(G ∩ T (x) 6= ∅) tồn tại một lân cận mở U của x sao cho T (z) ⊆ G (tương tự, (T (z) ∩ G 6= ∅), ∀z ∈ U ). Ta nói ánh xạ T là đóng, nửa liên tục trên (dưới) trên tập C nếu nó đóng, nửa liên tục trên (dưới) tại mọi điểm thuộc C. Mệnh đề sau khẳng định tính nửa liên tục trên của ánh xạ ∂f . 19