Tài liệu Về bài toán cực đại hàm lồi và ứng dụng của nó

.. ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC HOÀNG THỊ HƯƠNG VỀ BÀI TOÁN CỰC ĐẠI HÀM LỒI VÀ ỨNG DỤNG CỦA NÓ Chuyên ngành: TOÁN ỨNG DỤNG LUẬN VĂN THẠC SĨ TOÁN HỌC Người hướng dẫn khoa học: GS.TSKH. LÊ DŨNG MƯU THÁI NGUYÊN - NĂM 2014 Mục lục Mục lục i Lời cảm ơn ii Mở đầu 1 1 Bài toán cực đại hàm lồi trên tập lồi đa diện 3 1.1 1.2 Tập lồi đa diện và hàm lồi . . . . . . . . . . . . . . . . . . . . . 3 1.1.1 Tập lồi đa diện . . . . . . . . . . . . . . . . . . . . . . . 3 1.1.2 Hàm lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 Bài toán cực đại hàm lồi . . . . . . . . . . . . . . . . . . . . . . 14 1.2.1 Tồn tại và điều kiện tối ưu . . . . . . . . . . . . . . . . 14 1.2.2 Tính chất cực đại hàm lồi . . . . . . . . . . . . . . . . . 17 1.2.3 Ví dụ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2 Một số thuật toán giải bài toán cực đại hàm lồi 23 2.1 Hàm bao lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.2 Thuật toán nhánh cận . . . . . . . . . . . . . . . . . . . . . . . 27 2.2.1 Phép chia đơn hình vét kiệt . . . . . . . . . . . . . . . . 27 2.2.2 Thuật toán . . . . . . . . . . . . . . . . . . . . . . . . . . 30 2.3 Thuật toán xấp xỉ ngoài . . . . . . . . . . . . . . . . . . . . . . 37 2.4 Thuật toán xấp xỉ trong . . . . . . . . . . . . . . . . . . . . . . 41 Kết luận 45 Tài liệu tham khảo 46 i Lời cảm ơn Trong suốt quá trình làm luận văn, tôi luôn nhận được sự hướng dẫn và giúp đỡ nghiêm túc, nhiệt tình của GS.TSKH. Lê Dũng Mưu (Viện Toán học, Viện Hàn lâm Khoa học và Công nghệ Việt Nam). Tôi xin bày tỏ lòng biết ơn sâu sắc đến Thầy và kính chúc Thầy cùng gia đình luôn mạnh khỏe. Tôi xin chân thành cảm ơn các quý thầy, cô giảng dạy tại Đại học Thái Nguyên, Viện Toán học, Viện Hàn lâm Khoa học và Công nghệ Việt Nam, đã mang lại cho tôi nhiều kiến thức và quan tâm giúp đỡ tôi trong suốt quá trình học tập, nghiên cứu. Tôi cũng xin cảm ơn các bạn cùng lớp đã giúp đỡ tôi trong suốt thời gian học tập tại Đại học Thái Nguyên và trong quá trình hoàn thành luận văn này. Cuối cùng, con xin cảm ơn bố mẹ. Nhờ có bố mẹ gian khó, vất vả tạo mọi điều kiện tốt nhất để con có được thành quả ngày hôm nay. Thái Nguyên, tháng 6 - 2014 Người viết Luận văn Hoàng Thị Hương ii Mở đầu Giải tích lồi là một phần quan trọng của toán học. Hầu hết các ngành như tối ưu hóa, giải tích hàm, hình học, toán kinh tế,... đều liên quan đến lý thuyết về các tập lồi và hàm lồi. Đã có rất nhiều nhà toán học nghiên cứu về vấn đề này và đưa ra nhiều lý thuyết cũng như ứng dụng thực tế. Một trong những tính chất cơ bản của hàm lồi cho chúng ta sử dụng rộng rãi trong bài toán tối ưu đó là tính chất đạt giá trị cực đại trên biên. Trong toán học ứng dụng ta thường gặp bài toán tìm cực đại của hàm lồi trên một tập lồi. Bài toán này có nhiều ứng dụng trong thực tế, hơn nữa một số bài toán khác của tối ưu toàn cục có thể quy về bài toán này. Bài toán này có những tính chất rất cơ bản, tuy nhiên tính chất quan trọng của bài toán cực đại hàm lồi trên một tập lồi vẫn là nghiệm tối ưu (toàn cục) luôn đạt trên một điểm cực biên. Lợi dụng tính chất này, người ta đã đưa ra các thuật toán giải bài toán trên. Mục đích của luận văn này là giới thiệu bài toán cực đại hàm lồi trên tập lồi đa diện, trong đó ta đi trình bày điều kiện nghiệm tối ưu và các tính chất của bài toán. Tiếp đó là trình bày ba thuật toán cơ bản để giải bài toán trên. Cụ thể luận văn trình bày ba thuật toán sau: thuật toán nhánh cận, thuật toán xấp xỉ ngoài và thuật toán xấp xỉ trong. Luận văn gồm mục lục, hai chương, kết luận và tài liệu tham khảo. Chương 1: Trình bày các kiến thức cơ bản của giải tích lồi. Đó là tập lồi, tập lồi đa diện và hàm lồi cùng với những tính chất đặc trưng của nó. Tiếp theo giới thiệu bài toán cực đại của hàm lồi trên một tập lồi cùng với điều kiện nghiệm tối ưu (toàn cục), tính chất cực đại hàm lồi và xét một số ví dụ về bài toán cực đại của hàm lồi. Chương 2: Giới thiệu một số kiến thức cơ bản về hàm bao lồi. Trình bày 1 ba thuật toán cơ bản giải bài toán tìm cực đại hàm lồi trên một tập lồi. Đó là thuật toán nhánh cận, thuật toán xấp xỉ ngoài và thuật toán xấp xỉ trong. Sau mỗi thuật toán sẽ có một ví dụ minh họa cho thuật toán. Luận văn đượ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 trực tiếp của GS. TSKH. Lê Dũng Mưu. Mặc dù tác giả đã hết sức cố gắng nhưng do vấn đề được nghiên cứu là khá phức tạp và kinh nghiệm nghiên cứu còn hạn chế nên khó tránh khỏi thiếu sót. Trong quá trình viết luận văn cũng như xử lý văn bản chắc chắn không tránh khỏi những sai sót nhất định. Tác giả mong nhận được sự góp ý của các quý thầy cô và các bạn để luận văn được hoàn thiện hơn. 2 Chương 1 Bài toán cực đại hàm lồi trên tập lồi đa diện Trong chương này ta trình bày các khái niệm cơ bản của tập lồi, tập lồi đa diện và hàm lồi cùng với những tính chất đặc trưng của nó. Tiếp theo trình bày điều kiện cần và đủ của nghiệm tối ưu, tính chất cực đại hàm lồi và xét một số ví dụ về bài toán cực đại của hàm lồi. Các kiến thức trình bày trong chương này được tham khảo chủ yếu từ các tài liệu [1], [2], [3], [6], [7]. 1.1 1.1.1 Tập lồi đa diện và hàm lồi Tập lồi đa diện Định nghĩa 1.1. Một đường thẳng đi qua hai điểm (hai véc-tơ) a, b trong Rn là tập hợp tất cả các véc-tơ x ∈ Rn có dạng {x ∈ Rn : x = αa + βb, α, β ∈ R, α + β = 1}. Định nghĩa 1.2. Đoạn thẳng nối hai điểm a và b trong Rn là tập hợp các véc-tơ x có dạng {x ∈ Rn : x = αa + βb, α ≥ 0, β ≥ 0, α + β = 1}. Định nghĩa 1.3. Một 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. 3 Định nghĩa 1.4. Điểm x ∈ Rn có dạng x = λ1 a1 + λ2 a2 + ... + λk ak với ai ∈ Rn , λi ≥ 0, λ1 + λ2 + ... + λk = 1 gọi là một tổ hợp lồi của các điểm a1 , a2 ,..., ak . Định nghĩa 1.5. Thứ nguyên (hay số chiều) của một tập lồi C , ký hiệu dimC, là số chiều của bao affine của nó. Một tập lồi C trong Rn gọi là có thứ nguyên đầy nếu dimC = n. Định nghĩa 1.6. Tập C ⊆ Rn gọi là một tập affine (hay đa tạp tuyến tính) nếu C chứa trọn cả đường thẳng đi qua hai điểm bất kỳ của nó, tức là ∀a, b ∈ C, ∀λ ∈ R ⇒ (1 − λ)a + λb ∈ C. Nhận xét 1.1. Nếu C là một tập affine và a ∈ Rn thì i) a + C = {a + x : x ∈ C} cũng là một tập affine. ii) C là một tập affine chứa gốc khi và chỉ khi C là một không gian con, nghĩa là nếu a, b thuộc C thì mọi điểm λa + µb cũng thuộc C với λ, µ ∈ R. Định nghĩa 1.7. Điểm x ∈ Rn có dạng x = λ1 a1 + λ2 a2 + ... + λk ak với ai ∈ Rn và λ1 + λ2 + ... + λk = 1 gọi là một tổ hợp affine của các điểm a1 , a2 ,..., ak . Định nghĩa 1.8. Thứ nguyên (hay số chiều) của một tập affine C , ký hiệu dimC, là số chiều của không gian con song song với nó. Ta quy ước: dim∅ = −1. Định nghĩa 1.9. Một tập C ⊂ Rn được gọi là nón nếu ∀λ > 0, ∀x ∈ C ⇒ λx ∈ C. Một nón được gọi là nón lồi nếu nó đồng thời là một tập lồi. Một nón được gọi là nón nhọn nếu nó không chứa đường thẳng. Nếu nón này là một tập lồi đa diện thì ta nói nó là nón lồi đa diện. Định nghĩa 1.10. Cho C ⊆ Rn là một tập lồi và x ∈ C. (i) Tập NC (x) := {w ∈ Rn : hw, y − xi ≤ 0, ∀y ∈ C}, được gọi là nón pháp tuyến ngoài của C tại x và tập −NC (x) được gọi là nón pháp tuyến trong của C tại x. 4 (ii) Tập NC (x) := {w ∈ Rn : hw, y − xi ≤ , ∀y ∈ C}, được gọi là nón pháp tuyến  của C tại x. Hiển nhiên 0 ∈ NC (x) và dùng định nghĩa ta có NC (x) là một nón lồi đóng. Định nghĩa 1.11. Bao lồi của một tập C là giao của tất cả các tập lồi chứa C. Bao lồi của một tập C được ký hiệu là coC. Bao lồi đóng của một tập C là tập lồi đóng nhỏ nhất chứa C. Ta ký hiệu bao đóng của một tập C là coC. Bao affine của C là giao của tất cả các tập affine chứa C. Bao affine của một tập C được ký hiệu là aff C. Định nghĩa 1.12. Siêu phẳng trong không gian Rn là một tập hợp các điểm có dạng {x ∈ Rn : ha, xi = α}, trong đó a ∈ Rn là một véc-tơ khác 0 và α ∈ R. Véc-tơ a thường được gọi là véc-tơ pháp tuyến của siêu phẳng. Định nghĩa 1.13. Nửa không gian đóng là một tập hợp có dạng {x ∈ Rn : ha, xi ≥ α}, trong đó a 6= 0 và α ∈ R. Tập {x ∈ Rn : ha, xi > α}, là nửa không gian mở. Một siêu phẳng sẽ chia không gian ra làm hai nửa không gian, mỗi nửa không gian ở về một phía của siêu phẳng. Nếu hai nửa không gian này là đóng thì phần chung của chúng chính là siêu phẳng đó. Định nghĩa 1.14. Cho hai tập C và D khác rỗng. (i) Ta nói siêu phẳng ha, xi = α tách C và D nếu ha, xi ≤ α ≤ ha, yi, ∀x ∈ C, ∀y ∈ D. 5 (ii) Ta nói siêu phẳng ha, xi = α tách chặt C và D nếu ha, xi < α < ha, yi, ∀x ∈ C, ∀y ∈ D. (iii) Ta nói siêu phẳng ha, xi = α tách mạnh C và D nếu sup ha, xi < α < inf ha, yi. y∈D x∈C Định lý 1.1. (Định lý tách 1). Cho C và D là hai tập lồi khác rỗng trong Rn sao cho C ∩ D = ∅. Khi đó có một siêu phẳng tách C và D. Định lý 1.2. (Định lý tách 2). Cho C và D là hai tập lồi đóng khác rỗng sao cho C ∩ D = ∅. Giả sử có ít nhất một 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. Hệ quả 1.1. (Bổ đề Farkas) Cho a ∈ Rn và A là ma trận cấp m × n. Khi đó ha, xi ≥ 0, với mọi x thỏa mãn Ax ≥ 0, khi và chỉ khi tồn tại y ≥ 0 thuộc Rm sao cho a = AT y. Ý nghĩa hình học của bổ đề Farkas: Siêu phẳng đi qua gốc tọa độ ha, xi = 0, để nón Ax ≥ 0 về một phía của nó khi và chỉ khi véc-tơ pháp tuyến a của siêu phẳng nằm trong nón sinh bởi các hàng của ma trận A. Định nghĩa 1.15. Một tập con lồi F của một tập lồi C gọi là một diện của C nếu x, y ∈ C mà (1 − λ)x + λy ∈ F , 0 < λ < 1 thì [x, y] ⊂ F, nghĩa là nếu một đoạn thẳng bất kỳ thuộc C có một điểm trong tương đối thuộc F thì cả đoạn thẳng ấy phải nằm trọn trong F . Một diện có số chiều 0 gọi là một điểm cực biên của C . Một diện có số chiều 1 gọi là một cạnh của C . Nếu một tập lồi C có diện là một nửa đường thẳng thì véc-tơ chỉ phương của nửa đường thẳng này gọi là một phương cực biên của C. Tính chất 1.1. Các tính chất sau về diện của các tập lồi • Một diện của một nón lồi là một nón lồi. • Một diện của một diện của C cũng là một diện của C. • Một diện E của một tập lồi đóng C là một tập lồi đóng. • Giao của tập lồi C với một siêu phẳng tựa của C là một diện của C. 6 • Giả sử F ⊂ Rn là một tập bất kỳ và C = convF. Khi đó, mọi điểm cực biên của C đều thuộc F. Định nghĩa 1.16. Một tập lồi mà là giao của một số hữu hạn nửa không gian đóng gọi là một tập lồi đa diện. Nói cách khác, đó là tập nghiệm của một hệ hữu hạn các bất phương trình tuyến tính hai , xi ≤ bi , i = 1, 2, ..., m (ai ∈ Rn , bi ∈ R), (1.1) nghĩa là tập các x nghiệm đúng Ax ≤ b với A là một ma trận cấp m × n và b ∈ Rm . Vì một phương trình tuyến tính có thể biểu diễn tương đương bằng hai bất phương trình tuyến tính nên một tập lồi đa diện cũng là tập nghiệm của một hệ các phương trình và bất phương trình tuyến tính hai , xi = bi , i = 1, 2, ..., p hai , xi ≤ bi , i = p + 1, ..., m. Hạng của hệ bất phương trình tuyến tính (1.1) được định nghĩa bằng hạng của ma trận A. Nếu hạng của hệ này bằng m thì ta nói hệ độc lập tuyến tính. Nhận xét 1.2. i) Một tập lồi đa diện có thể không bị chặn (không giới nội). ii) Một tập lồi đa diện bị chặn còn được gọi là một đa diện lồi. iii) Mỗi điểm cực biên của một tập lồi đa diện còn được gọi là một đỉnh của nó. Tập các đỉnh của C ký hiệu là V (C). Mỗi cạnh vô hạn của một tập lồi đa diện tương ứng với một phương cực biên của nó. Cho tập lồi đa diện D 6= ∅ xác định bởi hệ bất phương trình tuyến tính (1.1). Khi đó mỗi bất phương trình (1.1) gọi là một ràng buộc của D. Ta nói ∗ điểm x0 ∈ D thỏa mãn chặt ràng buộc i∗ nếu hai , x0 i = bi . Với mỗi x ∈ D, ký hiệu I(x) = {i : hai , xi = bi } là tập chỉ số của những ràng buộc thỏa mãn chặt tại x. Ký hiệu I0 = {i : hai , xi = bi , ∀x ∈ D}. Tính chất đặc trưng của các diện, các đỉnh và cạnh của D được cho trong định lý sau. 7 Định lý 1.3. Một tập con khác rỗng F ⊂ D là một diện thực sự của D khi và chỉ khi F = {x : hai , xi = bi , i ∈ I; hai , xi ≤ bi , i ∈ / I}, với I là tập chỉ số sao cho I0 ⊂ I ⊂ {1, ..., m} (I - tập chỉ số xác định diện F ). Hơn nữa, ta có dimF = n − rank{ai : i ∈ I} và dimD = n − rank{ai : i ∈ I0 }. Hệ quả 1.2. Nếu D là một tập lồi đa diện xác định bởi hệ (1.1) thì a) Điểm x0 ∈ D là một đỉnh của D khi và chỉ khi rank{ai : i ∈ I(x0 )} = n, nghĩa là x0 thỏa mãn chặt n ràng buộc độc lập tuyến tính của hệ (1.1). b) Nếu một đoạn thẳng (nửa đường thẳng hay cả đường thẳng) Γ ⊂ D là một cạnh của D thì Γ được xác định bởi một tập chỉ số I sao cho rank{ai : i ∈ I} = n − 1, tức là mọi x ∈ riΓ cùng thỏa mãn chặt n − 1 ràng buộc độc lập tuyến tính của hệ (1.1). Mỗi tập lồi đa diện có một số hữu hạn đỉnh và cạnh (hữu hạn hay vô hạn). Hình 1.1: Tập lồi đa diện Định lý 1.4. a) Mỗi đa diện lồi C bằng bao lồi của tất cả các đỉnh của nó: C = conv V (C) hay x ∈ C khi và chỉ khi x = λ1 v 1 + ... + λp v p với mọi λi ≥ 0, λ1 + ... + λp = 1 và v i (i = 1, ..., p) là các đỉnh của C . 8 b) Với tập lồi đa diện C không giới nội, mỗi x ∈ C có thể biểu diễn dưới dạng một tổ hợp lồi của các đỉnh của C cộng với một tổ hợp tuyến tính không âm của các phương cực biên của C , nghĩa là x ∈ C khi và chỉ khi x = λ1 v 1 + ... + λp v p + µ1 u1 + ... + µq uq , với mọi λi ≥ 0, λ1 + ... + λp = 1, µj ≥ 0, p, q ≥ 0 là số nguyên, v i là đỉnh của C (i = 1, ..., p), uj (j = 1, ..., q) là phương của các cạnh vô hạn của C . Với tập lồi đa diện C không có đỉnh thì trong biểu diễn trên chỉ cần các v i ∈ C và các uj ∈ rec C. Định lý trên cho thấy ứng với mỗi tập lồi đa diện C cho trước có hai nhóm hữu hạn véc-tơ, sao cho tập lồi ấy chính là tập tất cả các điểm có thể biểu diễn thành tổng của một tổ hợp lồi của các véc-tơ thuộc nhóm thứ nhất và một tổ hợp tuyến tính không âm của các véc-tơ thuộc nhóm thứ hai. Các véc-tơ trong nhóm thứ nhất đều là các đỉnh của C , các véc-tơ trong nhóm thứ hai đều là các phương vô hạn của C . Nếu C bị chặn thì trong biểu diễn trên chỉ còn lại tổng thứ nhất. Ngược lại, có thể chứng minh được rằng nếu cho trước hai nhóm hữu hạn véc-tơ thì tập tất cả các điểm có biểu diễn như trên xác định một tập lồi đa diện. 1.1.2 Hàm lồi Định nghĩa 1.17. Hàm f : C → R ∪ {+∞} xác định trên một tập hợp lồi C ⊆ Rn . Hàm f được gọi là hàm lồi trên C nếu f [(1 − λ)x + λy] ≤ (1 − λ)f (x) + λf (y), ∀x, y ∈ C, x 6= y, ∀λ ∈ [0, 1]. Hàm f được gọi là hàm lồi chặt trên C nếu f [(1 − λ)x + λy] < (1 − λ)f (x) + λf (y), ∀x, y ∈ C, x 6= y, ∀λ ∈ (0, 1). Hàm f được gọi là hàm lõm (lõm chặt) trên C nếu hàm −f là hàm lồi (lồi chặt) trên C . 9 Hàm f được gọi là hàm tuyến tính affine (hay hàm affine) trên C nếu f hữu hạn và vừa lồi vừa lõm trên C . Hàm lồi f : C → R ∪ {+∞} có thể được mở rộng thành hàm lồi xác định trên toàn không gian Rn bằng cách đặt f (x) = +∞ với mọi x ∈ / C . Vì vậy để đơn giản ta thường xét hàm lồi trên toàn Rn . Nhận xét 1.3. i) Hàm affine không lồi chặt hay lõm chặt. ii)Một hàm lồi chặt là lồi, nhưng điều ngược lại không đúng. Định nghĩa 1.18. Cho hàm bất kỳ f : C → R ∪ {+∞} với C ⊆ Rn . Miền hữu dụng của f là tập domf = {x ∈ C : f (x) < +∞}. Tập trên đồ thị của f là epif = {(x, α) ∈ C × R : f (x) ≤ α}. Nếu domf 6= ∅ và f (x) > −∞, ∀x ∈ C thì f được gọi là hàm lồi chính thường. Chú ý 1.1. Ta có thể chứng minh hàm f lồi trên C khi và chỉ khi i) Tập trên đồ thị epif là một tập lồi, hoặc ii) f ( m P k=1 λ k xk ) ≤ m P λk f (xk ) với mọi xk ∈ C , m P λk = 1 và λk ≥ 0 với mọi k=1 k=1 k , trong đó m ≥ 2, m là số nguyên (bất đẳng thức Jensen). Ví dụ 1.1. Cho C là một tập lồi, khác rỗng của không gian Rn . Hàm chỉ của C được định nghĩa bởi δC (x) =  0 nếu x ∈ C,  +∞ nếu x ∈ / C. là hàm lồi. Định nghĩa 1.19. Hàm f (x) xác định trên một tập lồi C ⊂ Rn được gọi là lồi mạnh trên C , nếu tồn tại hằng số ρ > 0 (hằng số lồi mạnh) sao cho với mọi x, y ∈ C và mọi số λ ∈ [0, 1] ta có bất đẳng thức f [λx + (1 − λ)y] 6 λf (x) + (1 − λ)f (y) − λ(1 − λ)ρ k x − y k2 . 10 Ta có thể chứng minh hàm f (x) lồi mạnh khi và chỉ khi f (x) − ρ k x k2 là hàm lồi. Một hàm lồi mạnh thì lồi chặt, nhưng điều ngược lại không chắc đúng. Chẳng hạn, hàm ex , x ∈ R, lồi chặt nhưng không lồi mạnh. Các hàm lồi mạnh có vai trò đặc biệt quan trọng trong nghiên cứu các bài toán tối ưu. Ví dụ 1.2. Hàm f (x1 , x2 ) = x21 + x22 lồi mạnh. Tổng quát, xét hàm bậc hai 1 f (x) = hx, Qxi + hp, xi, 2 với Q là một ma trận vuông đối xứng cấp n xác định dương và p ∈ Rn . Tính lồi mạnh của f được suy ra từ hệ thức f [λx + (1 − λ)y] ≤ λf (x) + (1 − λ)f (y) − λ(1 − λ)hx − y, Q(x − y)i ≤ λf (x) + (1 − λ)f (y) − λ(1 − λ)ρ k x − y k2 , chú ý rằng với 0 ≤ λ ≤ 1 thì λ2 ≤ λ, (1 − λ)2 ≤ (1 − λ) và vì rằng hx − y, Q(x − y)i ≥ ρ k x − y k2 , trong đó ρ là giá trị riêng nhỏ nhất (dương) của ma trận Q. Tính chất 1.2. Bốn phép toán cơ bản bảo toàn hàm lồi • Nếu fi : Rn → R (i = 1, ..., m) là hàm lồi thì α1 f1 + ... + αm fm lồi với mọi αi ≥ 0 và lồi chặt nếu ít nhất một trong các hàm fi lồi chặt với αi > 0. • Nếu fi (i ∈ I) : Rn → R là hàm lồi thì hàm f (x) = supi∈I fi (x) là hàm lồi. • Nếu A : Rn → Rm là biến đổi tuyến tính và g : Rm → R là hàm lồi thì hàm hợp f (x) = g(Ax) là hàm lồi. • Nếu g : D ⊆ Rn → R là hàm lồi và h : R → R là hàm lồi không giảm thì hàm hợp f (x) = h(g(x)) là hàm lồi. Định lý 1.5. Giả sử f : S → R ∪ {+∞} là một hàm lồi trên Rn và α ∈ R ∪ {+∞}. Khi đó, các tập mức dưới Cα = {x : f (x) < α}, Cα = {x : f (x) ≤ α} 11 là tập lồi. Tương tự, nếu f là một hàm lõm trên Rn thì các tập mức trên Dβ = {x : f (x) > β}, Dβ = {x : f (x) ≥ β} là tập lồi. Nhận xét 1.4. i) Mệnh đề đảo của định lý trên không đúng. ii) Một hàm f mà mọi tập mức dưới là tập lồi gọi là một hàm tựa lồi. Ví dụ 1.3. f (x) = x3 hay f (x) = p kxk trên R là hàm tựa lồi nhưng không là hàm lồi. Định lý 1.6. Cho C là một tập lồi, khác rỗng trong Rn và f : Rn → R là một hàm lồi. Mọi điểm cực tiểu địa phương của f trên C đều là điểm cực tiểu toàn cục. Tập Argminx∈C f (x) là tập con lồi của C. Hệ quả 1.3. Bất cứ điểm cực đại địa phương nào của một hàm lõm trên một tập lồi cũng là điểm cực đại toàn cục. Tập tất cả các điểm cực đại của một hàm lõm trên một tập lồi là lồi. Định lý 1.7. Hàm f (x), x ∈ Rn , là hàm lồi khi và chỉ khi hàm một biến số ϕ(λ) ≡ f (x + λd) là hàm lồi theo λ với mỗi x, d ∈ Rn . Định lý 1.8. Hàm lồi chính thường f trên Rn liên tục tại mọi điểm trong của miền hữu dụng của nó (f liên tục trên int(domf )). Nhận xét 1.5. Một hàm lồi chính thường chỉ có thể gián đoạn tại những điểm biên của miền hữu dụng của nó. Ví dụ 1.4. Xét hàm một biến số xác định trên tập C = [0, +∞) có dạng: f (x) = ex với mọi x > 0 và f (0) = 2. Dễ thấy epif là tập lồi nên f là hàm lồi trên C . Hàm f liên tục tại mọi điểm trong x > 0 và gián đoạn tại điểm biên x = 0. Tại x = 0 hàm f nửa liên tục trên trên C. Định lý 1.9. Cho một tập lồi C ⊂ Rn và hàm f : Rn → R khả vi trên C . a) Hàm f lồi trên C khi và chỉ khi f (y) ≥ f (x) + hOf (x), y − xi, 12 với mọi x, y ∈ C . b) Nếu f (y) > f (x) + hOf (x), y − xi, với mọi x, y ∈ C và x 6= y thì hàm f lồi chặt trên C . Định lý 1.10. Cho một tập lồi mở C ⊂ Rn và hàm f : Rn → R hai lần khả vi liên tục trên C . O2 f (x) là ma trận các đạo hàm riêng cấp hai của f tại x. a) Nếu O2 f (x) nửa xác định dương với mỗi x ∈ C (tức là hy, O2 f (x)yi > 0 với mọi y ∈ Rn ) hoặc nếu O2 f (x) có mọi giá trị riêng không âm thì hàm f lồi trên C . b) Nếu O2 f (x) xác định dương với mỗi x ∈ C (tức là hy, O2 f (x)yi > 0, với mọi y ∈ Rn \ {0}) hoặc nếu O2 f (x) có mọi giá trị riêng dương thì hàm f lồi chặt trên C . c) Nếu C = Rn và hàm f lồi thì O2 f (x) nửa xác định dương với mọi x ∈ Rn . Hệ quả 1.4. (Điều kiện cần cho hàm lồi/ lõm). Giả sử f : Rn → R là một ” (x) là đạo hàm riêng hai lần của f theo cùng hàm hai lần khả vi liên tục và fjj biến xj . ” (x) ≥ 0, j = 1, ..., n với mọi x. • Nếu f (x) lồi thì fjj ” (x) ≤ 0, j = 1, ..., n với mọi x. • Nếu f (x) lõm thì fjj ” (x) > 0, j = 1, ..., n với mọi x. • Nếu f (x) lồi chặt thì fjj ” (x) < 0, j = 1, ..., n với mọi x. • Nếu f (x) lõm chặt thì fjj Định lý 1.11. Cho Q là một ma trận vuông đối xứng thực cấp n × n. Hàm toàn phương f (x) = hx, Qxi lồi khi và chỉ khi Q nửa xác định dương. Hơn nữa, hàm f lồi chặt khi và chỉ khi Q xác định dương. Hệ quả 1.5. Hàm bậc hai f (x) = 21 hx, Qxi + hc, xi + α lồi (lồi chặt) trên Rn khi và chỉ khi ma trận Q nửa xác định dương (xác định dương) và f lõm (lõm chặt) trên Rn khi và chỉ khi ma trận Q nửa xác định âm (xác định âm). Ví dụ 1.5. Xét hàm f (x) = f (x1 , x2 ) = x21 − 2x1 x2 + 3x22 . Ta thấy     2x1 − 2x2 2 −2 2 Of (x) = −2x + 6x và O f (x) = −2 6 . 1 2 13 Do O2 f (x) xác định dương ∀x nên hàm f đã cho lồi chặt trên R2 . Định nghĩa 1.20. Với d ∈ Rn \ {0}, nếu tồn tại giới hạn (hữu hạn hay vô hạn)
f x0 + λd −f (x0 ) lim λ λ→0 thì giới hạn đó gọi là đạo hàm theo hướng d của hàm f tại x0 , ký hiệu là f 0 (x0 , d). Định nghĩa 1.21. Cho hàm lồi chính thường f trên Rn , véc-tơ p ∈ Rn gọi là dưới đạo hàm của f tại điểm x0 nếu hp, x − x0 i + f (x0 ) ≤ f (x), ∀x ∈ Rn . Tập tất cả các dưới đạo hàm của f tại x0 gọi là dưới vi phân của f tại x0 và ký hiệu là ∂f (x0 ). Hàm f được gọi là khả dưới vi phân tại x0 nếu ∂f (x0 ) 6= ∅. Ví dụ 1.6. Dưới vi phân của hàm chỉ δC (x) của một tập lồi C 6= ∅ tại một điểm x0 ∈ C chính là nón pháp tuyến ngoài của C ∂δC (x0 ) = {p : hp, x − x0 i ≤ 0, ∀x ∈ C}. 1.2 Bài toán cực đại hàm lồi Do min{f (x) : x ∈ C} = − max{−f (x) : x ∈ C} và tập nghiệm của hai bài toán này trùng nhau nên lý thuyết cực tiểu (hay cực đại) hàm lồi cũng chính là lý thuyết cực đại (hay cực tiểu) hàm lõm. 1.2.1 Tồn tại và điều kiện tối ưu Sự tồn tại nghiệm tối ưu Xét bài toán max{f (x) : x ∈ C ⊆ Rn } Có bốn trường hợp tồn tại nghiệm tối ưu • C = ∅ (không có điểm chấp nhận được). • f không bị chặn trên trên C (sup f (x) = +∞). x∈C 14 (P ) • sup f (x) < ∞ nhưng không có nghiệm. x∈C • Tồn tại x∗ ∈ C sao cho f (x∗ ) = max f (x). x∈C Định lý 1.12. Điều kiện cần và đủ cho sự tồn tại nghiệm tối ưu của Bài toán (P ) là F + (C) := {t ∈ R : f (x) ≥ t, x ∈ C}, đóng và bị chặn trên. Chứng minh. Nếu x∗ là nghiệm tối ưu thì F + (C) = [−∞, f (x∗ )] là đóng (phần bù của một tập mở) và rõ ràng là bị chặn trên. Ngược lại, giả sử F + (C) bị chặn trên. Đặt t∗ = sup F + (C) < +∞. Vì F + (C) là đóng, t∗ ∈ F + (C) nên tồn tại x∗ ∈ C sao cho f (x∗ ) = t∗ . Chứng tỏ x∗ là một nghiệm cực đại của f trên C . Định lý 1.13. (Weistrass) Nếu C là tập compact khác rỗng và f là hàm nửa liên tục trên trên C, thì Bài toán (P ) có nghiệm tối ưu. Chứng minh. Đặt α := sup f (x). Theo định nghĩa có một dãy {xk } ⊂ C sao x∈C cho lim k→−∞ f (xk ) = α. Do C compact nên ta có một dãy con hội tụ về x0 ∈ C , không giảm tính tổng quát ta có thể coi xk → x0 . Vì f nửa liên tục trên nên α < +∞. Nhưng x0 ∈ C nên theo định nghĩa của α, ta phải có f (x0 ) ≤ α. Vậy f (x0 ) = α. Hệ quả 1.6. Nếu C là tập đóng khác rỗng, f là hàm nửa liên tục trên trên C và thỏa mãn điều kiện bức sau f (x) → −∞ khi x ∈ C, kxk → +∞, thì f có điểm cực đại trên C . Chứng minh. Đặt C(a) := {x ∈ C : f (x) ≥ f (a)}, với a ∈ C. Ta thấy C(a) đóng và bị chặn nên f có điểm cực đại trong C(a) mà điểm đó cũng là điểm cực đại của f trên C . 15 Điều kiện tối ưu Mệnh đề 1.1. Giả sử C ⊂ Rn là tập lồi và f : C → R là hàm lồi. Nếu f (x) đạt cực đại trên C tại điểm trong tương đối x0 của C (x0 ∈ riC) thì f (x) bằng hằng số trên C . Tập Argmaxx∈C f (x) là hợp của một số diện của C. Chứng minh. Giả sử f đạt cực đại trên C tại điểm x0 ∈ riC và giả sử x là điểm tuỳ ý thuộc C . Do x0 ∈ riC nên tìm được y ∈ C sao cho x0 = λx+(1−λ)y với λ nào đó thuộc (0, 1). Khi đó f (x0 ) ≤ λf (x) + (1 − λ)f (y). Vì thế λf (x) ≥ f (x0 ) − (1 − λ)f (y) ≥ f (x0 ) − (1 − λ)f (x0 ) = λf (x0 ). Như vậy f (x) ≥ f (x0 ). Từ đó f (x) = f (x0 ) hay f (x) bằng hằng số trên C . Mặt khác, nếu một điểm trong tương đối của một diện là điểm cực đại, thì mọi điểm của diện đều là điểm cực đại. Mệnh đề 1.2. Giả sử C là tập lồi, đóng và f : C → R là hàm lồi. Nếu C không chứa đường thẳng nào và f (x) bị chặn trên trên mọi nửa đường thẳng trong C thì max{f (x) : x ∈ C} = max{f (x) : x ∈ V (C)}, trong đó V (C) là tập các điểm cực biên của C , nghĩa là nếu cực đại của f (x) đạt được trên C thì cũng đạt được trên V (C). Chứng minh. Ta có C = coV (C) + K, trong đó K là nón lồi sinh bởi các phương cực biên của C . Một điểm bất kỳ thuộc C mà nó không phải là điểm cực biên, sẽ thuộc nửa đường thẳng xuất phát từ một điểm v nào đó thuộc V (C) theo phương của một tia trong K . Do f (x) hữu hạn và bị chặn trên trên nửa đường thẳng này, nên cực đại của nó trên đường thẳng này đạt được tại v . Như vậy max của f (x) trên C bằng max của f trên coV (C). Khi đó, vì bất kỳ x ∈ coV (C) đều có dạng X λi v i với v i ∈ V (C) và λi ≥ 0, x= i∈I X i∈I 16 λi = 1, cho nên f (x) ≤ X λi f (v i ) ≤ max f (v i ). i∈I i∈I Hệ quả 1.7. Hàm lồi f trên tập lồi đa diện C , không chứa đường thẳng nào, hoặc không bị chặn trên trên một cạnh vô hạn nào đó của C , hoặc đạt cực đại tại một đỉnh của C . 1.2.2 Tính chất cực đại hàm lồi Định nghĩa 1.22. Cho C ⊆ Rn khác rỗng và f : Rn → R. Một điểm x∗ ∈ C được gọi là cực đại địa phương của f trên C nếu tồn tại một lân cận U của x∗ sao cho f (x) ≤ f (x∗ ) ∀x ∈ U ∩ C. Nếu f (x) ≤ f (x∗ ) ∀x ∈ C, thì x∗ được gọi là cực đại toàn cục hay cực đại tuyệt đối của f trên C. Chú ý 1.2. Ta thấy rằng cực đại địa phương của một hàm lồi không nhất thiết là cực đại tuyệt đối. Ví dụ hàm f (x) = x2 có điểm cực đại địa phương trên đoạn [−1, 2] là x = −1, nhưng điểm cực đại tuyệt đối lại là x = 2. Nếu xét hàm này trên đoạn [−2, 2] ta thấy tập các điểm cực đại tuyệt đối của nó trên đoạn này là không lồi vì nó chỉ gồm hai điểm −2 và 2. Dưới đây, nếu không nói gì thêm, ta luôn hiểu cực đại là cực đại tuyệt đối. Từ định nghĩa hàm lồi, ta thấy rằng, nếu f lồi chính thường trên một tập lồi C và a, b ∈ C, thì với mọi x thuộc đoạn [a, b], tức là x = λa + (1 − λ)b, 0 < λ < 1, ta có f (x) ≤ λf (a) + (1 − λ)f (b) ≤ max{f (a), f (b)}. Từ đây suy ra rằng cực đại của một hàm lồi f trên một đoạn [a, b] đạt tại đầu mút của đoạn đó. Một cách tổng quát ta có. 17