Tài liệu Hàm lồi, hàm lồi suy rộng và tính chất

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC Nguyễn Thị Hải Đường HÀM LỒI, HÀM LỒI SUY RỘNG VÀ TÍNH CHẤT CONVEX FUNCTIONS AND GENERALIZATIONS WITH THEIR PROPERTIES Chuyên ngành: TOÁN ỨNG DỤNG Mã số: 60 46 01 12 LUẬN VĂN THẠC SĨ TOÁN HỌC Thái Nguyên - 2014 Công trình được hoàn thành tại Trường Đại học khoa học - Đại học Thái Nguyên Người hướng dẫn khoa học: GS.TS. Trần Vũ Thiệu Phản biện 1: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .................................................................... Phản biện 2: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .................................................................... Luận văn sẽ được bảo vệ trước hội đồng chấm luận văn họp tại: Trường Đại học khoa học - Đại học Thái Nguyên Ngày 21 tháng 6 năm 2014 Có thể tìm hiểu tại Thư viện Đại học Thái Nguyên 1 Mục lục Lời nói đầu . . . . . . . . . . . . . . . . . . . . . . . . . . . Chương 1. HÀM LỒI VÀ HÀM LÕM 1.1. TẬP LỒI VÀ TẬP LỒI ĐA DIỆN . . . . . . . . . . . . 1.1.1. Định nghĩa tập lồi, bao lồi và nón lồi . . . . . . 1.1.2. Tập lồi đa diện . . . . . . . . . . . . . . . . . . 1.1.3. Các phép toán bảo toàn tập lồi . . . . . . . . . 1.2. HÀM LỒI (LỒI CHẶT) VÀ HÀM LÕM (LÕM CHẶT) 1.2.1. Định nghĩa và ví dụ . . . . . . . . . . . . . . . . 1.2.2. Tính chất cơ bản . . . . . . . . . . . . . . . . . 1.2.3. Hàm lồi khả vi và cách nhận biết hàm lồi . . . . 1.2.4. Các phép toán bảo toàn hàm lồi . . . . . . . . . Chương 2. HÀM LỒI VÀ HÀM LÕM SUY RỘNG 2.1. HÀM TỰA LỒI VÀ HÀM TỰA LÕM . . . . . . . 2.2. HÀM GIẢ LỒI VÀ HÀM GIẢ LÕM . . . . . . . . 2.3. HÀM LỒI TẠI MỘT ĐIỂM . . . . . . . . . . . . . 2.4. HÀM PHÂN THỨC AFIN . . . . . . . . . . . . . . 2.5. HÀM LÔGA-LỒI VÀ HÀM LÔGA-LÕM . . . . . . . . . . . . . . . . 2 . . . . . . . . . 4 4 4 6 8 8 8 12 15 17 . . . . . 21 21 27 30 32 33 Chương 3. CỰC TRỊ CỦA HÀM LỒI VÀ HÀM LÕM SUY RỘNG 3.1. CỰC TIỂU ĐỊA PHƯƠNG VÀ TOÀN CỤC . . . . . . . 3.2. CỰC TIỂU HÀM LỒI (CỰC ĐẠI HÀM LÕM) . . . . . 3.3. BÀI TOÁN TỐI ƯU TỰA LỒI . . . . . . . . . . . . . . KẾT LUẬN . . . . . . . . . . . . . . . . . . . . . . . . . . . TÀI LIỆU THAM KHẢO . . . . . . . . . . . . . . . . . . 36 36 37 41 43 44 2 Lời nói đầu Hàm lồi và hàm lõm có nhiều tính chất đặc biệt, đáng chú ý và được sử dụng nhiều trong lý thuyết và ứng dụng thực tiễn, đặc biệt trong giải tích lồi và tối ưu hóa. Chẳng hạn, cực tiểu địa phương của một hàm lồi trên một tập lồi luôn là cực tiểu toàn cục, hàm lồi khả vi đạt cực tiểu tự do tại điểm có đạo hàm bằng 0 hay hàm lồi đạt cực đại tại một đỉnh của tập lồi đa diện ... Một số hàm lồi suy rộng cũng có các tính chất tương tự. Vì thế hàm lồi và hàm lồi suy rộng là chủ đề hấp dẫn và luôn thu hút sự quan tâm của nhiều nhà nghiên cứu. Mục tiêu của luận văn này là tìm hiểu và trình bày các khái niệm và kết quả chính liên quan đến chủ đề về các hàm lồi, lõm và các hàm lồi, lõm suy rộng: hàm tựa lồi, tựa lõm (tựa lồi chặt, tựa lồi mạnh, tựa lõm chặt), giả lồi, giả lõm, giả lồi chặt, hàm lồi tại một điểm, hàm phân thức afin, các tính chất đáng chú ý của chúng, đặc biệt là tính chất cực trị và mối quan hệ giữa các hàm này. Các tính chất của hàm lồi và hàm lồi suy rộng hay được dùng trong thiết lập các điều kiện tối ưu và trong xây dựng các lược đồ tính toán giải các bài toán tối ưu có chứa các hàm lồi và hàm lõm. Luận văn được viết thành ba chương. Chương 1 “Hàm lồi và hàm lõm” nhắc lại một số kiến thức cơ bản về tập lồi, tập lồi đa diện và các phép toán bảo toàn tập lồi. Tiếp theo tập trung trình bày khái niệm về hàm lồi, hàm lõm và một số tính chất cơ bản như tính liên tục, đạo hàm theo hướng, dưới vi phân của hàm lồi, hàm liên hợp, dấu hiệu nhận biết hàm lồi và các phép toán bảo toàn hàm lồi, cho phép từ các hàm lồi đã có tạo ra nhiều hàm lồi mới. Nội dung trình bày trong chương được minh họa bằng nhiều ví dụ và hình vẽ cụ thể, cung cấp thêm các thông tin cần thiết giúp hiểu rõ hơn về tập lồi và hàm lồi. Chương 2 “Hàm lồi (lồi chặt) và hàm lõm (lõm chặt)” trình bày một số lớp hàm lồi, hàm lõm suy rộng và các tính chất đáng chú ý của chúng. Hàm tựa lồi (tựa lõm) là mở rộng trực tiếp của hàm lồi (hàm lõm). 3 Đáng chú ý là hàm tựa lồi khi và chỉ khi mọi tập mức dưới của nó là lồi. Các hàm tựa lồi chặt (tựa lõm chặt) có vai trò quan trọng trong lý thuyết tối ưu phi tuyến, bởi vì cực tiểu địa phương của hàm tựa lồi chặt (cực đại địa phương của hàm tựa lõm chặt) trên một tập lồi là cực tiểu (cực đại) toàn cục. Hàm tựa lồi chặt là tựa lồi nếu nó nửa liên tục dưới. Hàm giả lồi giống hàm lồi ở chỗ nếu ∇f (x̄) = 0 tại x̄ nào đó thì x̄ là cực tiểu toàn cục của hàm. Chú ý là hàm giả lồi vừa tựa lồi chặt vừa tựa lồi và hàm giả lồi chặt là hàm tựa lồi mạnh. Hàm phân thức afin vừa giả lồi vừa giả lõm. Trong một số trường hợp, hàm lồi có thể thay bằng hàm lồi tại một điểm. Các hàm lôga-lồi, lôga-lõm thường gặp trong lý thuyết xác suất và trong các nghiên cứu kinh tế cũng được đề cập tới ở chương này. Chương 3 "Cực trị của hàm lồi và hàm lõm suy rộng" trình bày tóm tắt những tính chất cực trị đáng chú ý của các hàm lồi và hàm lõm suy rộng, tương tự như các tính chất đặc trưng của hàm lồi và hàm lồi chặt. Chẳng hạn, mọi cực tiểu địa phương của hàm tựa lồi chặt đều là cực tiểu toàn cục, cực tiểu của hàm tựa lồi mạnh là duy nhất, cực đại của hàm tựa lồi liên tục trên đa diện lồi (nếu có) đạt được tại một đỉnh của đa diện đó. Do thời gian và kiến thức còn hạn chế nên chắc chắn luận văn này còn có những thiếu sót nhất định, kính mong quí thầy cô và các bạn đóng góp ý kiến để tác giả tiếp tục hoàn thiện luận văn sau này. Nhân dịp này tác giả xin bày tỏ lòng biết ơn sâu sắc tới GS.TS Trần Vũ Thiệu, người thầy đã trực tiếp hướng dẫn, cung cấp tài liệu và truyền đạt những kinh nghiệm nghiên cứu cho tôi. Tôi xin chân thành cảm ơn các thầy, cô giáo trong khoa Toán - Tin, Phòng Đào tạo trường Đại học Khoa học - Đại học Thái Nguyên, trường THPT Hoàng Văn Thụ và bạn bè đồng nghiệp đã giúp đỡ, tạo điều kiện cho tôi hoàn thành bản luận văn này. Thái Nguyên, 2014. Tác giả Nguyễn Thị Hải Đường 4 Chương 1 HÀM LỒI VÀ HÀM LÕM Chương này nhắc lại một số kiến thức cơ bản về tập lồi, tập lồi đa diện và các phép toán bảo toàn tập lồi. Tiếp theo tập trung trình bày khái niệm về hàm lồi, hàm lõm và một số tính chất cơ bản như tính liên tục, đạo hàm theo hướng, dưới vi phân của hàm lồi, hàm liên hợp, dấu hiệu nhận biết hàm lồi và các phép toán bảo toàn hàm lồi, cho phép từ các hàm lồi đã có tạo ra nhièu hàm lồi mới. Nội dung của chương được tham khảo chủ yếu từ các tài liệu [2], [4], [6] và [7]. 1.1. 1.1.1. TẬP LỒI VÀ TẬP LỒI ĐA DIỆN Định nghĩa tập lồi, bao lồi và nón lồi Tập lồi là một khái niệm quan trọng được sử dụng rộng rãi trong lý thuyết tối ưu. Tập lồi có nhiều tính chất đáng chú ý, đặc biệt là tập lồi đa diện. Định nghĩa 1.1. Tập con C trong Rn được gọi là một tập lồi nếu nó chứa trọn đoạn thẳng nối hai điểm bất kỳ thuộc nó. Nói cách khác, C là tập lồi nếu (1 − λ) a + λb ∈ C với mọi a, b ∈ C và mọi 0 ≤ λ ≤ 1. Nói riêng, tập ∅ (không chứa phần tử nào), tập gồm duy nhất một phần tử và toàn bộ không gian Rn đều là các tập lồi. Hình 1.1 Tập A lồi. Tập B không lồi Sau đây là một số tập lồi đáng chú ý: a) Tập afin là tập chứa trọn đường thẳng đi qua hai điểm bất kỳ thuộc nó. 5 b) Siêu phẳng là tập có dạng  H = x ∈ Rn : aT x = α, a ∈ R\ {0} , α ∈ R . c) Nửa không gian đóng   H1 = x ∈ Rn : aT x ≤ α , H2 = x ∈ Rn : aT x ≥ α . d) Nửa không gian mở   K1 = x ∈ Rn : aT x < α , K2 = x ∈ Rn : aT x > α . e) Hình cầu đóng B (a, r) = {x ∈ Rn : kx − ak ≤ r} , a ∈ Rn , r > 0 cho trước. f) Tập lồi đa diện D = {x ∈ Rn : Ax ≤ b} , trong đó A ∈ Rm×n , b ∈ Rm . g) Nón lồi đa diện K = {x ∈ Rn : Ax ≤ 0} , trong đó A ∈ Rm×n , 0 ∈ Rm . Từ định nghĩa tập lồi trực tiếp suy ra một số tính chất đơn giản sau: a) Giao của một họ bất kỳ các tập lồi là tập lồi. b) Tổng, hiệu của hai tập lồi cũng là tập lồi C ± D = {x ± y : x ∈ C, y ∈ D} . c) Nếu C ⊂ Rm , D ⊂ Rn thì tích C × D = {(x, y) : x ∈ C, y ∈ D} là một tập lồi trong Rm×n . (Có thể mở rộng cho tích của nhiều tập lồi). d) Tập M là một tập afin khi và chỉ khi M = a + L với a ∈ M và L là một không gian con, gọi là không gian con song song với M . Khái niệm tương đương: M là một tập afin khi và chỉ khi M là tập nghiệm của một hệ phương trình tuyến tính, tức có biểu diễn  M = x ∈ Rn : Ax = b, A ∈ Rm×n , b ∈ Rm . Giao của một họ bất kỳ các tập afin cũng là một tập afin. 6 Định nghĩa 1.2. a) Đ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 . b) Điểm x ∈ Rn có dạng x = λ1 a1 + λ2 a2 + ... + λk ak với ai ∈ Rn , λ1 + λ2 + ... + λk = 1, gọi là một tổ hợp afin của các điểm a1 , a2 , ..., ak . c) Điểm x ∈ Rn có dạng x = λ1 a1 + λ2 a2 + ... + λk ak với ai ∈ Rn , λi ≥ 0, gọi là một tổ hợp tuyến tính không âm hay tổ hợp nón của các điểm a1 , a2 , ..., ak . Định nghĩa 1.3. Cho E là một tập bất kỳ trong Rn . a) Giao của mọi tập afin chứa E gọi là bao afin của E, ký hiệu af f E. Đó là tập afin nhỏ nhất chứa E. b) Giao của tất cả các tập lồi chứa E gọi là bao lồi (convex hull) của E, ký hiệu là convE. Đó là tập lồi nhỏ nhất chứa E. Định nghĩa 1.4. Một tập con K của Rn được gọi là một nón hay tập nón (mũi tại 0) nếu với mọi x ∈ K và mọi λ > 0 thì λx ∈ K . Nón K được gọi là một nón lồi (convex cone) nếu K là tập lồi. 1.1.2. Tập lồi đa diện Tập lồi đa diện là một dạng tập lồi có cấu trúc đơn giản và rất hay gặp trong lý thuyết tối ưu. Định nghĩa 1.5. Một tập là giao của một số hữu hạn các nửa không gian đóng gọi là một tập lồi đa diện (polyhedral convex set). Nói cách khác, đó là tập nghiệm của một hệ hữu hạn bất phương trình tuyến tính: ai1 x1 + ai2 x2 + ... + ain xn ≤ bi , i = 1, 2, ..., m nghĩa là tập các x nghiệm đúng Ax ≤ b với A = (aij ) ∈ Rm×n , b = (b1 , ..., bm )T . Nhận xét 1.1. 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 tập nghiệm của một hệ (hữu hạn) phương trình và bất phương trình tuyến tính cũng là một tập lồi đa diện: Một tập lồi đa diện có thể không bị chặn (không giới nội). Một tập lồi đa diện bị chặn (giới nội) còn được gọi là một đa diện lồi (polytope). 7 Các đa giác lồi theo nghĩa thông thường trong R2 là những ví dụ cụ thể về đa diện lồi. Hình 1.2 Tập lồi đa diện Ta nhắc lại khái niệm điểm cực biên và phương cực biên của tập lồi C: • x0 ∈ C là điểm cực biên (extreme point) của C nếu không tồn tại
x1 , x2 ∈ C x1 6= x0 , x2 6= x0 và λ ∈ (0, 1) sao cho x0 = λx1 + (1 − λ) x2 . Nói cách khác, điểm cực biên của một tập lồi là những điểm không nằm ở trong đoạn thẳng nối hai điểm khác bất kỳ thuộc tập đó. • Một phương vô hạn của C gọi là một phương cực biên (extreme direction) của C nếu nó không thể biểu diễn dưới dạng tổ hợp tuyến tính dương của hai phương vô hạn khác của C. Như vậy, nếu d0 ∈ Rn là phương cực biên của C thì không thể có d0 = λ1 d1 + λ2 d2 với λ1 , λ2 > 0 và d1 6= d0 , d2 6= d0 là hai phương vô hạn của C . Khi C là một tập lồi đa diện thì điểm cực biên của C gọi là một đỉnh (vertex) của C và véc tơ chỉ phương của một cạnh vô hạn (unbounded edge) của C là một phương cực biên của C. Cho D = {x ∈ Rn : Ax = b, x ≥ 0}, tức D là tập nghiệm không âm của một hệ phương trình tuyến tính. Theo định nghĩa, D là một tập lồi đa diện. Tập này không chứa trọn đường thẳng nào (do x ≥ 0) nên D có đỉnh. Các phương cực biên (đã chuẩn hóa) của D là các nghiệm cơ sở của hệ Ay = 0, eT y = 1, y ≥ 0, trong đó e = (1, ..., 1)T . Ta có định lý biểu diễn sau đây, thường được dùng trong các chứng minh. Định lý 1.1. ([2], tr. 62). Mỗi điểm của tập lồi đa diện D = {x ∈ Rn : Ax = b, x ≥ 0} có thể biểu diễn dưới dạng một tổ hợp lồi của một tập hữu hạn các đỉnh của D cộng với một tổ hợp tuyến tính không 8 âm của một tập hữu hạn các phương cực biên của D. 1.1.3. Các phép toán bảo toàn tập lồi Các qui tắc thực tiễn để xác minh tính lồi của tập C: 1. Sử dụng định nghĩa: x1 , x2 ∈ C, 0 ≤ λ ≤ 1 ⇒ (1 − λ) x1 + λx2 ∈ C. 2. Chỉ ra rằng C nhận được từ các tập lồi đơn giản (siêu phẳng, nửa không gian, hình cầu đơn vị ...) bằng các phép toán bảo toàn tính lồi như phép giao, ảnh qua các hàm afin (affine function), hàm phối cảnh (perspective function), các hàm phân tuyến tính (linear-fractional function). Việc làm này dựa trên các tính chất sau của tập lồi. a) Giao của một số bất kỳ các tập lồi là một tập lồi. b) Với f : Rn → Rm là hàm afin (hàm phối cảnh hay hàm phân tuyến tính) thì ảnh và ảnh ngược của một tập lồi qua biến đổi f là một tập lồi. Cụ thể là C ⊆ Rn lồi ⇒ f (C) = {f (x) : x ∈ C} ⊆ Rm lồi, D ⊆ Rm lồi ⇒ f −1 (D) = {x ∈ Rn : f (x) ∈ D} ⊆ Rn lồi. Để tiện theo dõi, ta nêu lại khái niệm về các hàm này. • f : Rn → Rm là hàm afin khi f (x) = Ax + b với A ∈ Rm×n , b ∈ Rm . Để ý là phép đổi tỷ xích, phép tịnh tiến hay phép chiếu đều được xác định bởi hàm afin. • Hàm phối cảnh f : Rn+1 → Rn được xác định theo công thức f (x, t) = x/t với x ∈ Rn và t > 0 • Hàm phân tuyến tính f : Rn → Rm là hàm có dạng Ax + b với x ∈ Rn và cT x + d > 0. f (x) = T c x+d Chẳng hạn hàm phân tuyến tính trên R2 1 x, với x1 + x2 + 1 > 0. f (x) = x1 + x2 + 1 1.2. 1.2.1. HÀM LỒI (LỒI CHẶT) VÀ HÀM LÕM (LÕM CHẶT) Định nghĩa và ví dụ Định nghĩa 1.6. a) Hàm f : C → [−∞, +∞] xác định trên một tập lồi C ⊆ Rn gọi là một hàm lồi trên C nếu với mọi x1 , x2 ∈ C và mọi 9 λ ∈ (0, 1) ta có  

f λx1 + (1 − λ) x2 ≤ λf x1 + (1 − λ) f x2 , mỗi khi vế phải xác định, nghĩa là hệ thức trên cần được thỏa mãn trừ

khi f x1 = −f x2 = ±∞ (vì biểu thức +∞ − ∞ không có nghĩa). b) Hàm f được gọi là hàm lồi chặt trên C nếu với mọi x1 , x2 ∈ C, x1 6= x2 , và mọi số thực λ ∈ (0, 1) ta có  

f λx1 + (1 − λ) x2 < λf x1 + (1 − λ) f x2 . Hiển nhiên, một hàm lồi chặt là hàm lồi, nhưng điều ngược lại không đúng. Định nghĩa 1.7. a) Hàm f gọi là hàm lõm (hàm lõm chặt) trên C nếu −f là hàm lồi (hàm lồi chặt) trên C. b) Hàm f gọi là hàm tuyến tính afin (hay đơn giản là hàm afin) trên C nếu f hữu hạn và vừa lồi, vừa lõm trên C. Một hàm afin trên Rn có dạng f (x) = aT x + α với a ∈ Rn , α ∈ R, bởi vì với mọi x1 , x2 ∈ Rn và mọi λ ∈ (0, 1) ta có  

f λx1 + (1 − λ) x2 = λf x1 + (1 − λ) f x2 , Hàm tuyến tính là trường hợp riêng của hàm afin, khi α = 0. Tuy nhiên, hàm afin (nói riêng, hàm tuyến tính) không lồi chặt hay lõm chặt. Định nghĩa 1.8. Cho hàm bất kỳ f : C → [−∞, +∞] với C ⊆ Rn . Các tập domf = {x ∈ C : f (x) < +∞} , epif = {(x, t) ∈ C × R : f (x) ≤ t} và hypof = {(x, t) ∈ C × R : f (x) ≥ t} được gọi lần lượt là miền hữu dụng, tập trên đồ thị và tập dưới đồ thị của hàm f . Nếu domf khác rỗng (f không đồng nhất bằng +∞) và f (x) > −∞ với mọi x ∈ C thì ta nói hàm f là chính thường (proper). Nói cách khác, f chính thường nếu domf 6= ∅và f hữu hạn trên domf . Có thể chứng minh rằng hàm f lồi trên C khi và chỉ khi epi f là một tập lồi. Tương tự, hàm f lõm trên C khi và chỉ khi hypo f là một tập lồi. Bất đẳng thức Jensen cơ bản: nếu f (x) là hàm lồi thì với mọi 0 ≤ θ ≤ 1 ta có f [θx + (1 − θ) y] ≤ θf (x) + (1 − θ) f (y) . 10 Hình 1.3 Hàm lồi (chặt). Hàm lồi (không chặt). Hàm không lồi. Hàm lõm Bất đẳng thức mở rộng: nếu f là hàm lồi thì f (Ez) ≤ Ef (z) với mọi biến ngẫu nhiên z (E là ký hiệu của kỳ vọng). Bất đẳng thức cơ bản là trường hợp riêng tương ứng với phân phối rời rạc: prob (z = x) = θ, prob (z = y) = 1 − θ. Nhận xét 1.2. Hàm lồi f : C → [−∞, +∞] 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 . Sau đây là một số ví dụ về hàm lồi và hàm lõm thường gặp. • Ví dụ về hàm lồi một biến: a) Hàm afin: ax + b trên R với mọi a, b ∈ R. b) Hàm mũ: eax trên R với mọi a ∈ R. c) Hàm luỹ thừa: xα trên R++ với α ≥ 1 hoặc α ≤ 0. d) Hàm lũy thừa của giá trị tuyệt đối: |x|p trên R với p ≥ 1. e) Hàm entropy âm: x log x lồi chặt trên R++ . • Ví dụ về hàm lõm một biến: a) Hàm afin: ax + b trên R với mọi a, b ∈ R. c) Hàm luỹ thừa: xα trên R++ với 0 ≤ α ≤ 1. e) Hàm lôga: log x trên R++ • Ví dụ trên Rn (véctơ n thành phần) và Rm×n (ma trận m hàng, n cột): a) Hàm afin: aT x + b với a ∈ Rn và b ∈ R là hàm vừa lồi, vừa lõm trên Rn . b) Mọi hàm chuẩn đều là hàm lồi trên Rn : n p 1/p P |xi | với p ≥ 1 và kxk∞ = max |xi | . kxkp = i=1 1≤i≤n Với C ⊆ Rn là một tập lồi khác rỗng, các hàm sau đây lồi trên Rn . 11  c) Hàm chỉ (indicator function) của C: δC (x) = 0 khi x ∈ C, +∞ khi x ∈ / C. d) Hàm tựa của C: SC (x) = supy∈C xT y (cận trên của xT y trên C). e) Hàm khoảng cách từ điểm x ∈ Rn tới C: dC (x) = infy∈C kx − yk. f) Hàm được xác định dưới đây là hàm lồi trên Rm×n với A = (aij )m×n
và X = xij m×n , b ∈ R và tr (C) = c11 + ... + cnn là vết của ma trận vuông C (cấp n): T
f (X) = T r A X + b = m X n X aij xij + b. i=1 j=1 g) f (x) = log n P exi là hàm lồi trên Rn . i=1 h) Chuẩn theo phổ (giá trị kỳ dị lớn nhất) là hàm lồi trên Rm×n :

1/2 f (X) = kXk2 = σmax (X) = λmax X T X . n , xét hàm Chẳng hạn, f : S n → R với f (X) = logdetX, dom f = S++ một biến   −1/2 −1/2 g (t) = log det (X + tV ) = log det X + log det I + tX VX = log det X + log det n X log (1 + tλi ) i=1 trong đó λi là các giá trị riêng của X −1/2 V X −1/2 . Có thể thấy g là hàm lõm theo t với mọi X  0 (X xác định dương) và V ∈ S n . Vì thế, f là hàm lõm. Sau đây là một số dạng hàm lồi đáng chú ý: a) Hàm bình phương nhỏ nhất (least-squares objective): f (x) = kAx − bk22 là hàm lồi với mọi ma trận A ∈ Rm×n và b ∈ Rm bởi vì ∇f (x) = 2AT (Ax − b) và ∇2 f (x) = 2AT A < 0 (nửa xác định dương) b) Hàm bậc hai trên bậc nhất (quadratic-over-linear): f (x, y) = x2 /y    T y y là hàm lồi với y > 0, bởi vì ∇2 f (x, y) = y13 < 0 (nửa xác −x −x định dương ). n P c) Hàm lôga của tổng các hàm mũ (log-sum-exp): f (x) = log e xk k=1 2 là lồi vì ∇ f (x) = 1 z1 +...+zn diag (z) − 1 T z1 +...+zn zz xk (zk = e ). 12 Để chỉ rõ ∇2 f (x) < 0 ta cần kiểm tra v T ∇2 f (x) v < 0 với mọi v ∈ Rn : T 2 v ∇ f (x) v = vì
2 ( 2 k zk vk P )( P ( k zk )− P 2 ( k zk ) P k 2 vkT zk ) ≥0
P 2 z v k k k ( k zk ) theo bất đẳng thức Cauchy-Schwarz.  n 1/n Q d) Hàm trung bình nhân (geometric mean): f (x) = xk là T k vk zk P ≤ P k=1 hàm lõm trên hàm mũ. 1.2.2. Rn++ . Chứng minh tương tự như hàm lôga của tổng các Tính chất cơ bản Mục này đề cập tới một số tính chất cơ bản của hàm lồi và hàm lõm. Định lý sau đây nêu mối liên hệ đáng chú ý giữa hàm lồi (lõm) và tập lồi. Định lý 1.2. ([2], tr. 66). Giả sử f : Rn → [−∞; +∞] là một hàm lồi trên Rn và α ∈ [−∞; +∞]. Khi đó, các tập mức dưới Cα = {x : f (x) < α} , C α = {x : f (x) ≤ α} 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. Chứng minh. Theo định nghĩa của hàm lồi ta có   

f λx1 + (1 − λ) x2 ≤ max f x1 , f x2 ∀x1 , x2 ∈ Rn , λ ∈ (0; 1). Từ đó suy ra các kết luận của định lý.  Hệ quả 1.1. Nếu gi (x) : Rn → R, i = 1, ..., m, là các hàm lồi thì {x : gi (x) ≤ 0, i = 1, 2, ..., m} là tập lồi. Tương tự, tập {x : gi (x) ≥ 0, i = 1, 2, ..., m} lồi nếu mọi gi (x) là hàm lõm. Một tính chất quan trọng của các hàm lồi, hàm lõm là các hàm này liên tục tại mọi điểm trong của miền hữu dụng (int (dom f )). Chẳng hạn Định lý 1.3. ([4], tr. 100). 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 dom f (tức là f liên tục trên int (dom f )). 13 Nhận xét 1.3. 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.1. Xét hàm một biến số xác định trên tập D = [x : |x| ≤ 1] có dạng: f (x) = x2 với |x| < 1 và f (x) = 2 với |x| = 1. Dễ thấy epi f là tập lồi nên f là một hàm lồi trên D. Hàm f liên tục tại mọi điểm trong −1 < x < 1 và gián đoạn tại các điểm biên x = ±1. Tại x = ±1 hàm f nửa liên tục trên. Hàm lồi n biến có mối quan hệ chặt chẽ với hàm lồi một biến. Ta có Định lý 1.4. ([2], tr. 68). 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) với dom dom ϕ = {λ : x + λd ∈ domf } là hàm lồi theo λ với mọi x ∈ domf và mọi d ∈ Rn . Tính chất này đúng cả với các hàm lõm. Chứng minh. Điều kiện cần là rõ ràng. Ta chứng minh điều kiện đủ. Giả sử ϕ (λ) là hàm lồi theo λ với mọi x ∈ domf và mọi d ∈ Rn . Lấy bất kỳ x, y ∈ domf và đặt d = y − x. Khi đó với mọi λ ∈ (0, 1) ta có f ((1 − λ) x + λy) = f (x + λd) = ϕ (λ) = ϕ ((1 − λ) .0 + λ.1) ≤ (1 − λ) ϕ (0) + λϕ (1) = (1 − λ) f (x) + λf (y)  Khái niệm đạo hàm theo hướng rất hữu ích cho việc thiết lập các tiêu chuẩn tối ưu và xây dựng các thủ tục tính toán trong qui hoạch phi tuyến, ở đó người ta quan tâm tới việc tìm hướng dọc theo đó một hàm đã cho tăng hoặc giảm. Định nghĩa 1.9. Cho f : Rn → [−∞; +∞] là một hàm bất kỳ và x là một điểm tại đó f hữu hạn (nghĩa là |f (x)| < +∞). Với d ∈ Rn , d 6= 0, nếu tồn tại giới hạn (hữu hạn hay vô cực) lim+ λ→0 f (x̄ + λd) − f (x̄) λ thì giới hạn đó gọi là đạo hàm theo hướng d của hàm f tạix , ký hiệu là f 0 (x, d). Định lý 1.5. ([2], tr. 77). Nếu f là hàm lồi chính thường thì f có đạo hàm theo mọi hướng tại mọi điểm x ∈ domf và f (x + d) − f (x) ≥ f 0 (x, d). 14 Hàm lồi có thể không khả vi, tức là có những điểm tại đó hàm không có đạo hàm hay véctơ gradient. Thay vào đó là khái niệm dưới gradient và dưới vi phân của hàm lồi. Định nghĩa 1.10. Cho hàm lồi chính thường f trên Rn . Véctơ p ∈ Rn gọi là dưới gradient của hàm f tại điểm x nếu p thỏa mãn pT (x − x) + f (x) ≤ f (x) , ∀x ∈ Rn . Hình 1.4 Dưới gradient p ∈ ∂f (x̄)) Tập tất cả các véctơ dưới gradient của f tại x gọi là dưới vi phân của f tại x và ký hiệu là ∂f (x). Hàm f được gọi là khả dưới vi phân tại x nếu ∂f (x) 6= ∅. Định lý 1.6. ([2], tr. 74). Một hàm lồi chính thường f trên Rn có dưới vi phân khác rỗng tại mỗi điểm x ∈ int (domf ) và ∂f (x) là một tập lồi đóng. Ví dụ 1.2. Sau đây là dưới vi phân của một số hàm lồi quen thuộc. a) Hàm af in = aT x + a (x ∈ Rn , a ∈ R) có ∂f (x) = {a} với mọi x ∈ Rn . b) 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 x ∈ C chính là nón pháp tuyến ngoài của C tại x:  ∂δC (x) = p : pT (x − x) ≤ 0, ∀x ∈ C c) Nếu f (x) = kxk (chuẩn Euclid) thì  {p : kpk ≤ 1} khi x̄ = 0, ∂f (x) = {x̄/ kx̄k} khi x̄ 6= 0. Định lý sau nêu mối liên hệ giữa dưới vi phân và đạo hàm theo hướng. 15 Định lý 1.7. ([2], tr. 78). Nếu f là hàm lồi chính thường và x ∈ domf thi p ∈ ∂f (x) khi và chỉ khi pT d ≤ f 0 (x, d) với mọi d ∈ Rn , d 6= 0. Một loại hàm lồi hay được dùng nhiều trong lý thuyết đối ngẫu Lagrange, đó là hàm liên hợp. Hàm liên hợp của một hàm tuỳ ý f : Rn → [−∞; +∞] là hàm  f ∗ (y) = sup y T x − f (x) , y ∈ Rn . x∈domf f ∗ là hàm lồi (ngay cả khi f không lồi), vì f ∗ là hàm cận trên theo từng điểm (lấy trên dom f ) của một họ hàm afin theo y. Đáng chú ý là bất đẳng thức Fenchel: f (x) + f ∗ (y) ≥ xT y (suy từ định nghĩa). Khi lấy liên hợp hai lần ta có f ∗∗ = f nếu hàm f lồi và đóng. Sau đây là một số ví dụ về hàm liên hợp: • f (x) = ax + b ⇒ f ∗ (y) = −b với mọi y ∈ R. • f (x) = ex ⇒ f ∗ (y) = y log y − y với y > 0. • f (x) = x log x ⇒ f ∗ (y) = ey−1 .  −1 − log(−y) nếu y < 0, +∞ nếu y ≥ 0. x>0  n ⇒ f ∗ (y) = sup y T x − 1 xT Qx = 1 y T Q−1 y. • f (x) = 21 xT Qx với Q ∈ S++ 2 2 • f (x) = − log x ⇒ f ∗ (y) = sup {xy + log x} = x 1.2.3. Hàm lồi khả vi và cách nhận biết hàm lồi Mục này đề cập tới các hàm lồi, hàm lõm khả vi. Trước hết, với hàm một biến số ta chú ý đến kết quả sau (xem [7], tr. 44). Định lý 1.8. ([7], tr 44). Hàm khả vi ϕ (t) là lồi trên khoảng (a, b) khi và chỉ khi đạo hàm ϕ0 (t) là một hàm không giảm. Hàm hai lần khả vi ϕ (t) là lồi trên (a, b) khi và chỉ khi đạo hàm bậc hai ϕ00 (t) không âm trên (a, b). Ta cũng có định lý tương tự cho hàm lõm. Ta nhắc lại khái niệm vi phân của hàm nhiều biến số. Cho S là một tập khác rỗng trong Rn và cho hàm f : S → R. Khi đó f gọi là khả vi 16 tại x ∈ int S nếu tồn tại véctơ gradient ∇f (x) và hàm số α : Rn → R sao cho f (x) = f (x) + ∇f (x)T (x − x) + kx − xk α (x,x − x) với mọi x ∈ S. với limx→x α (x, x − x) = 0. Hàm f gọi là khả vi trên tập mở S 0 ⊆ S nếu f khả vi tại mọi điểm thuộc S 0 . Cách biểu diễn f như trên gọi là khai triển (chuỗi Taylor) bậc một của f tại điểm x (hay quanh x). Để ý rằng nếu hàm f khả vi tại x thì có duy nhất một véctơ gradient ∇f (x) được cho bởi ∇f (x) = (∂f (x) /∂x1 , ..., ∂f (x) /∂xn )T , trong đó ∂f (x) /∂xi là đạo hàm riêng của hàm f theo biến xi lấy tại điểm x với mọi i = 1, ..., n. Định lý 1.9. ([2], tr. 76). Nếu f là hàm lồi chính thường, khả vi tại x ∈ domf thì ∂f (x) = {∇f (x)}, tức là ∇f (x) là véctơ dưới gradient duy nhất của f tại x . Ngược lại có thể chứng minh rằng nếu f có tại x̄ một véctơ dưới gradient duy nhất thì f khả vi tại x̄. Định lý sau đây nêu lên một tính chất đặc trưng của các hàm lồi khả vi, giúp nhận biết các hàm nhiều biến là hàm lồi. Định lý 1.10. ([6], tr. 31). Cho một tập lồi C ⊆ Rn và một hàm f : Rn → R khả vi trên Rn : a) Hàm f lồi trên C khi và chỉ khi f (y) ≥ f (x) + ∇f (x)T (y − x) , với mọi x, y ∈ C. b) Hàm f lồi chặt trên C khi và chỉ khi f (y) > f (x)+∇f (x)T (y − x) với mọi x, y ∈ C, x 6= y. Định lý sau nêu một đặc trưng cần và đủ khác của các hàm lồi khả vi. Định lý 1.11. ([4], tr. 111). Cho một tập lồimở khác rỗng C ⊆ Rn và một hàm f : C → R khả vi trên C: a) Hàm f lồi trên C khi và chỉ khi [∇f (y) − ∇f (x)]T (y − x) ≥ 0, ∀x, y ∈ C. b) Tương tự, hàm f lồi chặt trên C khi và chỉ khi [∇f (y) − ∇f (x)]T (y − x) > 0 với mọi x, y ∈ C, x 6= y. 17 Mặc dù các Định lý 1.10 và 1.11 cho các đặc trưng cần và đủ của các hàm lồi và lồi chặt, nhưng về mặt tính toán việc kiểm tra các điều kiện này rất khó khăn. Có thể nhận được một đặc trưng đơn giản và dễ sử dụng hơn, ít ra là đối với các hàm bậc hai, nếu hàm đó hai lần khả vi. Định nghĩa 1.11. Cho tập khác rỗng S ⊆ Rn và f : S → R . Khi đó f gọi là khả vi hai lần tại x ∈ intS nếu tồn tại véctơ ∇f (x) và ma trận đối xứng cấp n × n∇2 f (x) , gọi là ma trận Hessian, và hàm a(x, x − x) : Rn → R sao cho 1 f (x) = f (x) + ∇f (x)T (x − x) + (x − x)T ∇2 f (x) (x − x) + ||x − x||2 α (x, x − x) 2 với mọi x ∈ S, trong đó limx→x α (x, x − x) = 0. Hàm f gọi là khả vi hai lần trên tập mở S 0 ⊆ S nếu f khả vi hai lần tại mọi điểm thuộc S 0 . Định lý 1.12. ([6], tr. 34). Cho một tập lồi C ⊆ Rn và một hàm f : Rn → R hai lần khả vi liên tục trên Rn . ∇2 f (x) là ma trận Hessian các đạo hàm riêng cấp 2 của f tại x. a) Nếu ∇2 f (x) nửa xác định dương với mọi x ∈ C (tức y T ∇2 f (x) y ≥ 0, ∀y ∈ Rn ) hoặc nếu ∇2 f (x) có mọi giá trị riêng không âm thì hàm f lồi trên C. b) Nếu ∇2 f (x) xác định dương với mọi x ∈ C (tức y T ∇2 f (x) y > 0, ∀y ∈ Rn , y 6= 0) hoặc nếu ∇2 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 là tập lồi mở và hàm f lồi trên C thì ∇2 f (x) nửa xác định dương với mọi x ∈ C. 1.2.4. Các phép toán bảo toàn hàm lồi Các phương pháp thực tiễn để xác minh tính lồi của hàm: 1. Dùng định nghĩa (thường đơn giản nhờ thu hẹp hàm trên đường thẳng). 2. Với hàm hai lần khả vi, chỉ ra ∇2 f (x) < 0 (nửa xác định dương). 3. Chỉ ra f nhận được từ các hàm lồi đơn giản bằng các phép bảo toàn tính lồi của hàm: tổng với trọng số không âm, phép hơp với hàm afin, lấy max và sup theo từng điểm, lấy hàm hợp, tìm cực tiểu hoá, lấy phối cảnh. Cụ thể: a) Nhân với hệ số không âm: αf lồi khi f lồi vàα ≥ 0. 18 b) Lấy tổng: f1 +f2 lồi nếu f1 , f2 lồi (mở rộng cho tổng vô hạn, lấy tích phân); hợp với hàm afin: f (Ax + b) lồi nếu f lồi (A ∈ Rm×n , b ∈ Rm ). Chẳng hạn: + Hàm chắn lôga đối với các bất đẳng thức tuyến tính f (x) = − m X
log bi − aTi x , domf = {x : aTi x < bi , i = 1, ..., m}. i=1 + Chuẩn (bất kỳ) của hàm afin: f (x) = ||Ax + b|| . c) Nếu f1 , ..., fm là các hàm lồi thì f (x) = max {f1 (x) , ..., fm (x)} cũng là hàm lồi. Chẳng hạn: + Hàm tuyến tính từng khúc f (x) = maxi = 1, ...., m (aTi x + bi ) là hàm lồi. + Tổng của r thành phần lớn nhất của x ∈ Rn : f (x) = x[1] + x[2] + ... + x[r] là hàm lồi (x[i] là thành phần lớn thứ i của x), bởi vì f (x) = max{xi1 + xi2 + ... + xir : 1 ≤ i1 < i2 < ... < ir ≤ n}. d) Nếu hàm f (x, y) lồi theo x với mỗi y ∈ S thì hàm g (x) = supy ∈S f (x, y) là hàm lồi, chẳng hạn: + Hàm tựa của tập C : sC (x) = supy ∈C xT y là hàm lồi theo x. + Khoảng cách tới điểm xa nhất trong tập C : f (x) = supy ∈C ||x − y||. + Giá trị riêng lớn nhất của ma trận đối xứng: với X ∈ S n λmax (X) = supkyk2 = 1y T Xy. e) Hàm hợp vô hướng: hợp của g : Rn → R và h : R → R: f (x) = h (g (x)) . Khi đó, hàm f lồi nếu g lồi, h lồi không giảm, hoặc g lõm, h lồi không tăng. Chứng minh cho trường hợp n = 1 và g, h khả vi: f 00 (x) = h00 (g (x)) × g 0 (x)2 + h0 (g (x)) × g 00 (x) . Chẳng hạn, eg(x) là hàm lồi nếu g(x) lồi và 1/g(x) là hàm lồi nếu g(x) lõm và g(x) > 0.