Tài liệu Một thuật toán giải một lớp bài toán cân bằng với song hàm tựa lồi

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ——————–o0o——————– TRẦN DANH HÙNG MỘT THUẬT TOÁN GIẢI MỘT LỚP BÀI TOÁN CÂN BẰNG VỚI SONG HÀM TỰA LỒI LUẬN VĂN THẠC SĨ TOÁN HỌC THÁI NGUYÊN - 2020 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ——————–o0o——————– TRẦN DANH HÙNG MỘT THUẬT TOÁN GIẢI MỘT LỚP BÀI TOÁN CÂN BẰNG VỚI SONG HÀM TỰA LỒI 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 GS.TSKH. LÊ DŨNG MƯU THÁI NGUYÊN - 2020 Lời cam đoan Tôi xin cam đoan đây là công trình nghiên cứu khoa học của riêng bản thân tôi, dưới sự hướng dẫn khoa học của GS.TSKH. LÊ DŨNG MƯU. Các nội dung nghiên cứu, kết quả trong luận văn này là trung thực, không sao chép của bất cứ ai và chưa từng công bố dưới bất kỳ hình thức nào trước đây. Ngoài ra, trong luận văn tôi có sử dụng tài liệu, thông tin được đăng tải trên các tạp chí và một số kết quả của các tác giả khác đều có trích dẫn và chú thích nguồn gốc. Nếu phát hiện có sự sao chép kết quả nghiên cứu của đề tài khác, tôi xin hoàn toàn chịu trách nhiệm. Thái Nguyên, ngày 10 tháng 1 năm 2021 Tác giả TRẦN DANH HÙNG i Lời cảm ơn Trước tiên tôi xin cảm ơn tới GS.TSKH. LÊ DŨNG MƯU người đã trực tiếp hướng dẫn, tận tình chỉ bảo, giúp đỡ tôi tiến hành các hoạt động nghiên cứu khoa học để hoàn thành luận văn này. Tôi xin gửi lời cảm ơn sâu sắc tới các Giáo sư, Phó Giáo sư đang công tác tại Viện Toán học, các Thầy Cô trong Trường Đại học Khoa học Thái Nguyên, đã trực tiếp giảng dạy, đóng góp ý kiến. Qua đó tôi đã trau dồi thêm rất nhiều kiến thức, kỹ năng phục vụ cho việc nghiên cứu và công tác của bản thân. Tôi cũng muốn gửi lời cảm ơn Bộ môn Toán ứng dụng, Khoa Toán Trường Đại học Khoa học Thái Nguyên, đã tạo mọi điều kiện thuận lợi, hướng dẫn, phản biện để tôi có thể hoàn thành tốt luận văn này. Do thời gian có hạn, bản thân tôi còn hạn chế nên luận văn có thể có những thiếu sót. Tôi mong muốn nhận được ý kiến phản hồi, đóng góp và xây dựng của các thầy cô, và các bạn. Tôi xin chân thành cảm ơn! Thái Nguyên, ngày 10 tháng 1 năm 2021 Tác giả TRẦN DANH HÙNG ii Mục lục Lời cam đoan i Lời cảm ơn ii Mục lục iv Danh mục các ký hiệu, các chữ viết tắt v Lời mở đầu 1 1 Tập lồi, hàm lồi, hàm tựa lồi 4 1.1 1.2 Tập lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.1.1 Định nghĩa và ví dụ . . . . . . . . . . . . . . . . . . 4 1.1.2 Tổ hợp lồi và các tính chất cơ bản . . . . . . . . . . 5 Hàm lồi và hàm tựa lồi . . . . . . . . . . . . . . . . . . . . 8 1.2.1 Định nghĩa, ví dụ . . . . . . . . . . . . . . . . . . . 8 1.2.2 Các tính chất cơ bản . . . . . . . . . . . . . . . . . 10 1.2.3 Đạo hàm và dưới vi phân của hàm lồi và hàm tựa lồi 15 2 Bài toán cân bằng 2.1 2.2 23 Giới thiệu bài toán cân bằng . . . . . . . . . . . . . . . . . 23 2.1.1 Phát biểu bài toán . . . . . . . . . . . . . . . . . . . 23 Các trường hợp riêng của bài toán cân bằng . . . . . . . . . 24 2.2.1 Bài toán tối ưu . . . . . . . . . . . . . . . . . . . . 24 2.2.2 Bài toán điểm bất động . . . . . . . . . . . . . . . . 24 iii 2.2.3 Bài toán cân bằng Nash . . . . . . . . . . . . . . . . 25 2.2.4 Bài toán điểm yên ngựa . . . . . . . . . . . . . . . . 26 2.2.5 Bài toán bất đẳng thức biến phân . . . . . . . . . . 26 3 Một thuật toán dưới đạo hàm giải bài toán cân bằng Parađơn điệu 27 3.1 Tính đơn điệu . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.1.1 Định nghĩa và tính chất cơ bản . . . . . . . . . . . . 28 Thuật toán và sự hội tụ . . . . . . . . . . . . . . . . . . . . 29 3.2.1 29 3.2 Khảo sát sự hội tụ của thuật toán. . . . . . . . . . . Kết luận 37 Tài liệu tham khảo 38 iv Một số ký hiệu và chữ viết tắt Rn không gian Euclide n−chiều R = R ∪ {−∞, +∞} trục số thực mở rộng xT chuyển vị của x coA bao lồi của A A bao đóng của A ri(A) tập điểm trong tương đối của tập A int(A) tập hợp các điểm trong của A f hàm bao đóng của f domf miền hữu dụng của f epif trên đồ thị của f ∂f (x) dưới vi phân của f tại x Af f (A) giao của tất cả các đa tạp affine chứa A 2 kết thúc chứng minh v Lời mở đầu Ngày nay, lý thuyết về các tập lồi, hàm lồi và hàm tựa lồi ngày càng khẳng định được một vị trí quan trọng trong toán học nói chung và trong giải tích nói riêng cụ thể liên quan đến hầu hết các ngành như giải tích phức, giải tích hàm, giải tích lồi, hình học và toán kinh tế,... Một trong các công cụ chính trong giải tích lồi đó là “Bài toán cân bằng” và “Một thuật toán dưới đạo hàm giải bài toán cân bằng Para-đơn điệu”. Bài toán cân bằng là bài toán Tìm x∗ ∈ C sao cho φ(x∗ , y) ≥ 0, ∀y ∈ C, (EQ) trong đó C là tập cho trước và φ : C × C → R là một hàm cho trước sao cho φ(x, x) = 0. Giải tích lồi đóng vai trò quan trọng trong việc nghiên cứu lý thuyết các bài toán cực trị và các ngành toán học ứng dụng có sử dụng công cụ giải tích và không gian tuyến tính. Sau các kết quả đầu tiên của H. Minkowski (1910) về tập lồi và hàm lồi, lý thuyết giải tích lồi đã thu hút sự quan tâm nghiên cứu của nhiêu nhà toán học. Lý thuyết giải tích lồi được hoàn thiện khoảng ba chục năm nay, sau các công trình nổi tiếng của H. Minkowski, C. Carathéodory, W. Fenchel, L. D. Muu. Năm 1992 L. D. Muu và W. Oettli đã đặt tên cho bất đẳng thức trên là “Bài toán cân bằng” (equilibrium problem). Bài toán cân bằng là bài toán bao hàm nhiều lớp bài toán quen thuộc như: bài toán tối ưu, bài toán điểm bất động, bài toán cân bằng Nash, bài 1 toán điểm yên ngựa,...Về mặt hình thức, bài toán này khá đơn giản, tuy nhiên như đã nói ở trên bài toán cân bằng nó bao hàm được nhiều lớp bài toán quan trọng khác thuộc nhiều lĩnh vực quan trọng trong đời sống. Mục tiêu của luận văn là giới thiệu một số kiến thức cơ bản về tập lồi, hàm lồi, hàm tựa lồi và dưới vi phân của hàm lồi và hàm tựa lồi. Đặc biệt nội dung chính của luận văn sẽ tập chung nhấn mạnh vào những kiến thức cơ bản về bài toán cân bằng và một thuật toán dưới đạo hàm giải bài toán cân bằng Para- đơn điệu với song hàm và tựa lồi theo biến thứ hai. Ngoài phần mở đầu, kết luận và danh mục tài liệu tham khảo, luận văn gồm ba chương sau: Chương 1. Tập lồi, hàm lồi, hàm tựa lồi Trong chương này chúng tôi giới thiệu tổng quan và trình bày về một số khái niệm cơ bản, tính chất và ví dụ minh họa của tập lồi, hàm lồi, hàm tựa lồi được trích dẫn trong tài liệu số [1] và [2], đặc biệt phần cuối chương này tôi đi sâu vào các tính chất cơ bản của dưới vi phân hàm lồi và hàm tựa lồi. Chương 2. Bài toán cân bằng Đây là phần chính của luận văn, trong chương này, chúng tôi trình bày bài toán cân bằng, các trường hợp riêng của bài toán cân bằng như: Bài toán tối ưu, bài toán điểm bất động, bài toán cân bằng Nash và bài toán điểm yên ngựa. Với mỗi trường hợp của bài toán cân bằng tôi phát biểu bài toán và đưa ra ví dụ minh họa. Nội dung cụ thể của chương này được trích dẫn trong tài liệu số [6] và [7]. Chương 3. Một thuật toán dưới đạo hàm giải bài toán cân bằng Para-đơn điệu Đây cũng là phần chính và là chương cuối của luận văn. Trong chương này, chúng tôi trình bày hai nội dung chính và là hai nội dung quan trọng bao gồm: Thứ nhất sự đơn điệu của song hàm tựa lồi. Thứ hai thuật toán 2 và sự hội tụ. Nội dung cụ thể của chương này được trích dẫn từ tài liệu số [5]. 3 Chương 1 Tập lồi, hàm lồi, hàm tựa lồi Trong chương mở đầu của luận văn, chúng tôi trình bày một số khái niệm, một số tính chất cơ bản của tập lồi, hàm lồi, hàm tựa lồi, các ví dụ minh họa cho các khái niệm và tính chất trên. Đặc biệt phần cuối của chương sẽ đi sâu vào khái niệm dưới vi phân hàm lồi và hàm tựa lồi. Các kiến thức ở chương này được tổng hợp từ các tài liệu [1] và [2]. 1.1 Tập lồi Phần mở đầu của chương này chúng tôi sẽ trình bày về một số khái niệm cơ bản, ví dụ minh họa và các tính chất cơ bản của tập lồi, tổ hợp lồi. 1.1.1 Định nghĩa và ví dụ Cho Rn là một không gian vectơ, ta ký hiệu: L(x, y) = {λx + (1 − λ)y | λ ∈ R} là đường thẳng đi qua x, y. [x, y] = {λx + (1 − λ)y | λ ∈ [0, 1]} là đoạn thẳng nối hai điểm x, y. (x, y) = {λx + (1 − λ)y | λ ∈ (0, 1)} là đoạn thẳng mở nối hai điểm x, y. Định nghĩa 1.1.1. Một tập X ⊆ Rn được gọi là một tập lồi nếu x, y ∈ X ⇒ λx + (1 − λ)y ∈ X, ∀λ ∈ [0, 1], 4 nghĩa là nếu x, y ∈ X thì đoạn thẳng [x, y] ∈ X. Ví dụ 1.1.2. Nếu A và B là các tập lồi và α ∈ R thì các tập A + B, αA là các tập lồi. Ví dụ 1.1.3. Nếu A, B là các tập lồi trong Rn , thì A ∩ B := {x | x ∈ A, x ∈ B}, là tập lồi. Ví dụ 1.1.4. Nếu A là tập lồi trong Rn , X là tập lồi trong Rm thì tập sau là lồi:  A × X := x ∈ Rn+m | x = (a, c) : a ∈ A, c ∈ X . 1.1.2 Tổ hợp lồi và các tính chất cơ bản Định nghĩa 1.1.5. Ta nói x là tổ hợp lồi của các điểm (véc tơ) x1 , ..., xk nếu x= k X j λj x , λj > 0, ∀j = 1, . . . , k, j=1 k X λj = 1. j=1 Định nghĩa 1.1.6. Một tập M ⊂ X được gọi là đa tạp affine, hay đơn giản là tập affine, nếu với mọi cặp điểm x, y ∈ M ta có L[x, y] ⊂ M. Định nghĩa 1.1.7. Nếu A ∈ X là một tập con bất kỳ của X ta gọi bao affine của A, là giao của tất cả các đa tạp affine chứa A, kí hiệu là Af f (A). Nhận xét 1.1.8. Một tổ hợp affine x = Pk j j=1 λj x với các λj > 0, ∀j = 1, . . . , k sẽ được gọi là một tổ hợp lồi của các điểm (véc tơ) x1 , ..., xk . Định nghĩa 1.1.9. Tương tự bao affine, ta gọi bao lồi (convex hull) của một tập A ⊂ X ∈ Rn là giao của tất cả các tập lồi chứa A, kí hiệu bao lồi của A là coA. 5 Mệnh đề 1.1.10. Từ định nghĩa trên ta rút ra được một số tính chất sau. • coA = x với x là tổ hợp lồi của các véc tơ thuộc A. • X là tập lồi khi và chỉ khi X = coX , tức là ( m ) m X X X= λi ai | m ∈ N∗ ; ai ∈ X; λi ≥ 0 : λi = 1 i i Nếu X là tập lồi, ta định nghĩa số chiều của X chính là số chiều của Af f (X): dimX := dimAf f (X). Định nghĩa 1.1.11. Giả sử A ⊂ X , khi đó giao của tất cả các tập lồi đóng chứa A được gọi là bao lồi đóng của tập A và kí hiệu là coA. Nhận xét 1.1.12. coA là một tập lồi đóng. Đó là tập lồi đóng nhỏ nhất chứa A. Định nghĩa 1.1.13. (Toán tử chiếu lên tập lồi đóng) Cho C là một tập lồi đóng khác rỗng của R. Gọi y là một véc tơ bất kì, đặt dC (y) := inf||x − y||. x∈C Khi đó ta nói dC (y) là khoảng cách từ y tới C . Nếu tồn tại π ∈ C sao cho dC (y) = ||π − y||, thì ta nói π là hình chiếu vuông góc của y trên C . Theo định nghĩa trên, ta thất rằng hình chiếu pC (y) của y trên C sẽ là nghiệm của bài toán tối ưu   1 2 kx − yk , x ∈ C . min 2 Nói cách khác việc tìm hình chiếu của y trên C có thể đưa về việc tìm cực tiểu của hàm toàn phương ||x − y||2 trên C . Kí hiệu π = pC (y). 6 Tính chất toán tử chiếu lên tập lồi Tính chất 1: Cho C là một tập lồi đóng khác rỗng. Khi đó: (i) Với mọi y ∈ R, π ∈ C hai tính chất sau là tương đương: a) π = pC (y), b) y − π ∈ NC (π), trong đó NC (π) là nón pháp tuyến của tập C tại π . (ii) Với mọi y ∈ Rn , hình chiếu pC (y) của y trên C luôn tồn tại và duy nhất. (iii) Nếu y ∈ / C , thì hpC (y) − y, x − pC (y)i = 0 là siêu phẳng tựa của C tại pC (y) và tách hẳn y khỏi C , tức là hpC (y) − y, x − pC (y)i ≥ 0, ∀x ∈ C và hpC (y) − y, y − pC (y)i < 0. (iv) Ánh xạ y ,→ pC (y) có các tính chất sau: a) kpC (x) − pC (y)k ≤ kx − yk∀x, ∀y, (tính không giãn). b) hpC (x) − pC (y), x − yi ≥ kpC (x) − pC (y)k2 , (tính đồng bức). Tính chất 2: Giả sử α > 0. Với mỗi x ∈ C , đặt   1 h(x) := pC x − F (x) . α Khi đó x∗ = h (x∗ ) khi và chỉ khi x∗ là nghiệm của (V IP ). Cho C là một tập lồi đóng khác rỗng trong Rn và F : C → Rn . Bài toán bất đẳng thức biến phân (V IP ) có dạng:   Tìm x∗ ∈ C (V IP )  sao cho hF (x∗ ) , x − x∗ i ≥ 0, ∀x ∈ C. Tính chất 3: Giả sử C là tập lồi đóng và ánh xạ F : C → Rn đơn điệu mạnh L2 trên C với hệ số β và Lipschitz trên C với hằng số L. Khi đó nếu α > 2β 7 thì  h(x) := pC  1 x − F (x) α là ánh xạ co trên C với hệ số co r δ= 1.2 2β L2 1− + 2. α α Hàm lồi và hàm tựa lồi Trong mục này chúng tôi trình bày khái niệm về hàm lồi, hàm tựa lồi, các tính chất cơ bản của hàm lồi, hàm tựa lồi và một số ví dụ điển hình. Đồng thời trong mục này, tôi có trình bày các tính chất cơ bản của dưới vi phân hàm lồi và hàm tựa lồi. 1.2.1 Định nghĩa, ví dụ Định nghĩa 1.2.1. Cho X ⊆ Rn là tập lồi và một ánh xạ f : X → R. Các tập hợp domf := {x ∈ X | f (x) < +∞} epif := {(x, µ) ∈ X × R | f (x) ≤ µ} lần lượt được gọi là miền hữu dụng (effective domain) và trên đồ thị (epigraph) của hàm f. Khi đó ta nói hàm f : X → R được gọi là hàm lồi (convex function) trên X , nếu epif là một tập lồi trong Rn+1 . Ngoài ra với mỗi α ∈ R ta gọi các tập sau là tập mức dưới của hàm f tương ứng với mức α: Lf (α) := {x|f (x) ≤ α}, lf (α) := {x|f (x) < α}. Cho f : X → R, hàm f được gọi là chính thường (proper function) nếu domf 6= ∅ và f (x) > −∞, ∀x ∈ X. Hàm f được gọi là đóng (closed function), nếu epif là một tập đóng trong Rn+1 . 8 Mệnh đề 1.2.2. Cho f : X → R. Hàm f là lồi khi và chỉ khi f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y), ∀x, y ∈ X, ∀λ ∈ (0, 1). (1.1) Định nghĩa 1.2.3. Hàm f : Rn → R được gọi là lồi chặt (strictly convex function) trên X nếu f (λx + (1 − λ)y) < λf (x) + (1 − λ)f (y), ∀x, y ∈ X, ∀λ ∈ (0, 1). (1.2) Hàm f : Rn → R được gọi là lồi mạnh (strongly convex function) trên X với hệ số η > 0, nếu ∀x, y ∈ X, ∀λ ∈ (0, 1) ta có: 1 f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y) − ηλ(1 − λ)kx − yk2 . 2 (1.3) Hàm f : Rn → R được gọi là một hàm lõm (concave function) trên C , nếu −f lồi trên C . Ví dụ 1.2.4. Các hàm mũ chẵn x2 , x4 , ... và hàm lũy thừa ex là các hàm lồi cơ bản trong chương trình phổ thông. Ví dụ 1.2.5. Với x ∈ Rn , b ∈ R hàm affine aT x + b được gọi là hàm lồi. Khi b = 0 thì hàm trên được gọi là hàm tuyến tính. Ví dụ 1.2.6. Cho X là một tập lồi đóng, xét hàm khoảng cách được xác định bởi dX (x) := min||x − y|| với mọi y ∈ X . Hàm khoảng cách được xác định như trên được gọi là hàm lồi. Ví dụ 1.2.7. Giả sử x = (x1 , ..., xn ). Xét hàm chuẩn được xác định như sau: f (x) := ||x||1 := max|xi | hoặc f (x) := ||x|| := x21 + ... + x2n các hàm chuẩn xác định như trên là hàm lồi. 9
21 Định nghĩa 1.2.8. Cho C là một tập mở trên Rn , một hàm ϕ : Rn → R được gọi là tựa lồi trên C khi và chỉ khi với mỗi x, y ∈ C và λ ∈ [0; 1], thỏa mãn ϕ [(1 − λ)x + λy] ≤ max{ϕ(x), ϕ(y)}. (1.4) Ví dụ 1.2.9. Hàm Logarit là hàm tựa lồi trên trục số dương, nhưng không phải hàm lồi. Nói chung hàm đơn điệu 1-biến là tựa lồi. Ví dụ 1.2.10. Xét hàm số f (x) = x3 xác định trên R. Khi đó f (x) là hàm tựa lồi trên R nhưng không là hàm lồi. 1.2.2 Các tính chất cơ bản Định nghĩa 1.2.11. Một hàm f : Rn → R được gọi là nửa liên tục dưới đối với E tại một điểm x, nếu như với mọi dãy xk ⊂ E , xk → x ta có lim inff (xk ) ≥ f (x). Hàm f được gọi là nửa liên tục trên, đối với E , tại x nếu −f nửa liên tục dưới, đối với E , tại x. Nói một cách khác với mọi dãy xk ⊂ E , xk → x thì lim supf (xk ) ≤ f (x). Hàm f được gọi là liên tục đối với E, 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, đối với E , tại x. Mệnh đề 1.2.12. (Tính liên tục) Cho f : Rn → R ∪ {+∞}, khi đó các điều kiện sau là tương đương: (i) Trên đồ thị của f là một tập đóng trên Rn+1 , tức là f = f . (ii) Với mọi số thực α, tập mức dưới Lf (α) := {x|f (x) ≤ α} là một tập đóng. (iii) Hàm f là nửa liên tục dưới trên R. Chứng minh. Ta sẽ tiến hành chứng minh các điều kiện trên là tương đương: (i) → (ii). Giả sử xj → x, f (xj ) ≤ α. Khi đó (xj , α) ∈ epif . 10 Do epif đóng, nên (x, α) ∈ epif . Vậy x ∈ Lf (α). (ii) → (iii). Giả sử xj → x. Nếu lim inff (xj ) < f (x), khi đó tồn tại α < f (x) sao cho f (xj ) ≤ α với mọi j đủ lớn. Vậy xj ∈ Lf (α). Do xj → x và Lf (α) đóng, nên x ∈ Lf (α). Tức là f (x) ≤ α điều này mâu thuẫn với giả thiết α < f (x). (iii) → (i). Giả sử (xj , µj ) ∈ epif và (xj , µj ) → (x, µ). Khi đó f (xj ) ≤ µj với mọi j. Do (iii), suy ra lim inff (xj ) ≥ f (x). Vậy µ ≥ f (x). Suy ra (x, µ) ∈ epif do đó epif là tập đóng. Mệnh đề 1.2.13. Cho f là một hàm lồi chính thường trên Rn và x0 ∈ int(domf ), khi đó các điều kiện sau là tương đương. (i) f liên tục tại điểm x0 . (ii) f bị chặn trên trong lân cận của x0 . (iii) int(epif ) 6= ∅. (iv) int(domf ) 6= ∅ và f liên tục trên tập int(domf ). Chứng minh. Ta sẽ tiến hành chứng minh các điều kiện trên là tương đương: (i) → (ii). Vì f là hàm lồi chính thường trên Rn nên hàm f liên tục tại điểm x0 suy ra f bị chặn trên trong một lân cận của x0 . (ii) → (iii). Giả sử có một lân cận U sao cho f (x) ≤ c, ∀x ∈ U. Do đó U × (c, ∞) ⊂ epif. Vậy int(epif ) 6= ∅. (iii) → (iv). Do int(epif ) 6= ∅, nên nếu (x, µ) ∈ int(epif ) thì f bị chặn trên trong một lân cận của x. Hơn nữa do int(domf ) là hình chiếu của int(epif ) lên Rn , tức là int(domf ) = {x|∃µ ∈ R : (x, µ) ∈ int(epif )}. Vậy int(domf ) 6= ∅. (iv) → (i). Là hiển nhiên. 11 Mệnh đề 1.2.14. Giả sử f là một hàm lồi chính thường trên Rn . Khi đó f liên tục tại mọi điểm x ∈ int(domf ). Chứng minh. Do f lồi, nên domf và int(domf ) là các tập lồi. Khi đó có một đơn hình n-chiều S ⊂ int(domf ). Giả sử v 1 . . . v n+1 là các đỉnh của đơn hình S . Khi đó với mọi x ∈ S , ta có: x= n+1 X j λj v , λj ≥ 0, j=1 n+1 X λj = 1. j=1 Do f lồi nên f (x) ≤ n+1 X
λj f v j . j=1 Suy ra 
f (x) ≤ max f v j | j = 1, . . . , n + 1 . Thế nhưng do phần trong của đơn hình S khác rỗng, nên f bị chặn trên trong một lân cận của một điểm x0 ∈ int(S) và do đó, theo Mệnh đề 1.2.14 f liên tục trên tập int(domf ). Hệ quả 1.2.15. Cho f là một hàm lồi chính thường trên Rn . Khi đó với mọi tập com-pắc C ⊆ int(domf ), tập f (C) com-pắc. Định nghĩa 1.2.16. Một hàm f : Rn → R được gọi là Lipschitz địa phương tại x với hằng số Lipschitz L nếu tồn tại một lân cận U của x sao cho ||f (x) − f (y)|| 6 L||x − y|| ∀x, y ∈ U. Hàm f được gọi là Lipschitz địa phương trên D nếu nó Lipschitz địa phương tại mọi điểm thuộc D (tất nhiên hằng số Lipschitz có thể khác nhau ở mỗi điểm). Hàm lồi còn có tính liên tục Lipschitz. Mệnh đề sau đây sẽ chỉ ra mối liên hệ đó. 12 Mệnh đề 1.2.17. (Tính Lipschitz) Giả sử f là một 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.18. Nếu f : Rn → R lồi, thì f Lipschitz địa phương trên toàn Rn (do đó liên tục). Dưới đây là một số phép toán khác bảo toàn tính lồi. Cho f và g là hai hàm xác định trên C và không nhận giá trị −∞. Khi đó với mọi x ∈ C, ta định nghĩa các hàm: • (f + g)(x) := f (x) + g(x). • (λf )(x) := λf (x), λ là số thực. Mệnh đề 1.2.19. Nếu F là một tập lồi trong Rn+1 , thì hàm số f (x) := inf {µ ∈ R|(µ, x) ∈ F } là một hàm lồi trên Rn . Chứng minh. Giả sử x, y ∈ Rn và r, s ∈ R thỏa mãn f (x) < r, f (y) < s. Theo định nghĩa của cận dưới đúng, ta có µ ∈ R, v ∈ R, sao cho (µ, x) ∈ F, (v, y) ∈ F và µ < r, v < s. Do F là tập lồi, nên với mọi λ ∈ [0, 1], ta có: (λµ + (1 − λ)v, λx + (1 − λ)y) ∈ F. Từ đây và theo định nghĩa của f , suy ra f (λx + (1 − λ)y) 6 λµ + (1 − λ)v. Vậy theo Mệnh đề 1.2.9 f là hàm lồi. 13