Tài liệu Luận văn dưới vi phân của hàm lồi và ứng dụng

LỜI CẢM ƠN Luận văn được hoàn thành tại trường Đại học sư phạm Hà Nội 2 dưới sự hướng dẫn của PGS.TS Nguyễn Năng Tâm. Tôi xin bày tỏ lòng biết ơn chân thành, sâu sắc tới PGS.TS Nguyễn Năng Tâm, người đã luôn quan tâm, động viên và tận tình hướng dẫn tôi trong quá trình thực hiện luận văn. Tôi xin được gửi lời cảm ơn chân thành tới Ban giám hiệu trường Đại học sư phạm Hà Nội 2, phòng Sau đại học, các thầy cô giáo trong nhà trường và các thầy cô giáo dạy cao học chuyên ngành Toán giải tích đã tạo điều kiện thuận lợi cho tôi trong quá trình học tập và nghiên cứu. Tôi xin bày tỏ lòng biết ơn tới gia đình, người thân đã động viên và tạo mọi điều kiện để tôi có thể hoàn thành bản luận văn này. Hà Nội, tháng 10 năm 2010 Nguyễn Thị Thanh LỜI CAM ĐOAN Tôi xin cam đoan luận văn là công trình nghiên cứu của riêng tôi dưới sự hướng dẫn của PGS.TS Nguyễn Năng Tâm. Hà Nội, tháng 10 năm 2010 Nguyễn Thị Thanh Mục lục Mở đầu 1 Chương 1. Tập lồi và hàm lồi 3 1.1. Định nghĩa tập lồi và các tính chất . . . . . . . . . . . . 3 1.2. Định nghĩa hàm lồi và các tính chất . . . . . . . . . . . . 6 1.2.1. Hàm lồi . . . . . . . . . . . . . . . . . . . . . . . 6 1.2.2. Các phép toán về hàm lồi . . . . . . . . . . . . . 11 1.2.3. Tính liên tục của hàm lồi . . . . . . . . . . . . . 13 1.3. Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 Chương 2. Dưới vi phân hàm lồi 16 2.1. Định nghĩa và các tính chất cơ bản . . . . . . . . . . . . 16 2.2. Một số phép toán dưới vi phân . . . . . . . . . . . . . . 25 2.3. Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 Chương 3. Ứng dụng của dưới vi phân hàm lồi 32 3.1. Một số tính chất cơ bản . . . . . . . . . . . . . . . . . . 32 3.2. Một số ví dụ . . . . . . . . . . . . . . . . . . . . . . . . . 35 3.3. Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 Kết luận 42 Tài liệu tham khảo 43 BẢNG KÍ HIỆU Rn không gian Euclid n chiều trên tập số thực R tập số thực (R = R1 ) R = R ∪ {−∞, +∞} tập số thực suy rộng s n P kxk = xi 2 chẩn Euclide của x i=1 F :X⇒Y ánh xạ đa trị từ X vào Y domf miền hữu hiệu của f epif trên đồ thị của f int Ω phần trong của Ω ri Ω phần trong tương đối của Ω cone Ω nón lồi sinh bởi Ω N (x̄, Ω) nón pháp tuyến của Ω tại x̄ ∇f (x) hay f 0 (x) đạo hàm của f tại x f 0 (x; v) đạo hàm theo hướng v của f tại x ∂f (x) dưới vi phân của f tại x MỞ ĐẦU 1. Lý do chọn đề tài Những hàm số không khả vi xuất hiện thường xuyên và được biết đến từ lâu trong Toán học và các khoa học ứng dụng khác. Vì lý thuyết vi phân cổ điển không thể ứng dụng được cho việc khảo sát những đối tượng không khả vi, nên các lý thuyết vi phân suy rộng đã ra đời và đã được xây dựng. Lý thuyết vi phân suy rộng đầu tiên là lý thuyết vi phân suy rộng cho các hàm lồi. Với những cống hiến quan trọng của T. R. Rockafellar và một số nhà toán học khác, ngày nay Giải tích lồi đã trở thành một bộ phận quan trọng và đẹp đẽ của Giải tích toán học, góp phần giải quyết được nhiều bài toán trong thực tế ([1], [7]). Với mong muốn được tìm hiểu sâu hơn về sự phát triển của phép tính vi-tích phân và ứng dụng của nó, tôi đã chọn nghiên cứu đề tài: “Dưới vi phân của hàm lồi và ứng dụng”. 2. Mục đích nghiên cứu Đề tài nghiên cứu các kết quả đạt được về dưới vi phân của hàm lồi và một số ứng dụng vào bài toán tối ưu. 3. Nhiệm vụ nghiên cứu Việc nghiên cứu luận văn với nhiệm vụ hệ thống, làm rõ khái niệm dưới vi phân của hàm lồi và một số tính chất, từ đó trình bày ứng dụng của nó trong một số bài toán. 4. Đối tượng và phạm vi nghiên cứu Dưới vi phân của hàm lồi và một số tính chất. Ứng dụng của dưới vi phân hàm lồi. 2 5. Phương pháp nghiên cứu Tổng hợp kiến thức thu thập được qua những tài liệu liên quan đến đề tài, sử dụng các phương pháp nghiên cứu của giải tích, giải tích lồi, giải tích đa trị, tối ưu hoá. 6. Những đóng góp của đề tài Trình bày một cách có hệ thống các kiến thức cơ bản về dưới vi phân của hàm lồi và một số tính chất. Nghiên cứu ứng dụng của dưới vi phân hàm lồi trong một số bài toán. Chương 1 Tập lồi và hàm lồi Trong chương này chúng ta sẽ trình bày những khái niệm cơ bản nhất của tập lồi và hàm lồi cùng với những tính chất đặc trưng của nó. 1.1. Định nghĩa tập lồi và các tính chất Định nghĩa 1.1.1. ([3], tr 3, định nghĩa 1.1) Tập A ⊂ Rn được gọi là lồi nếu với mọi x, y ∈ A và mọi λ ∈ R sao cho 0 ≤ λ ≤ 1 thì λx + (1 − λ)y ∈ A. Định lý 1.1.1. ([7], tr 10, định lý 2.1) Giao của một họ tùy ý các tập lồi trong Rn là một tập lồi trong Rn . Chứng minh. Giả sử Aα ∈ Rn (α ∈ I) là các tập lồi với I là tập chỉ số bất kì, ta cần chứng minh tập A = ∩ Aα là lồi. α∈I Lấy tùy ý x1 , x2 ∈ A. Khi đó x1 , x2 ∈ Aα , với mọi α ∈ I. Do Aα là lồi cho nên λx1 +(1−λ)x2 ∈ Aα với mọi λ ∈ [0, 1], do đó λx1 +(1−λ)x2 ∈ A. Vì vậy A là tập lồi. Hệ quả 1.1. ([7], tr 10, hệ quả 2.1.1) Cho bi ∈ Rn ; βi ∈ R; i ∈ I với I là tập chỉ số tùy ý. Khi đó A = {x ∈ Rn | hx; bi i ≤ βi ; i ∈ I} là một tập lồi trong Rn . Định nghĩa 1.1.2. Cho A và B là hai tập hợp tuỳ ý trong Rn A + B = {a + b | a ∈ A; b ∈ B} ; αA = {αa | a ∈ A} . 4 Định lý 1.1.2. ([3], tr 4, mệnh đề 1.2) Giả sử Ai ⊂ Rn lồi; λi ∈ R (i = 1, 2,..., m). Khi đó λ1 A1 + λ2 A2 + ... + λm Am là lồi. Định nghĩa 1.1.3. Vectơ x ∈ Rn được gọi là tổ hợp lồi của các vectơ m P x1 , ..., xm ∈ Rn nếu tồn tại λi ≥ 0 (i = 1, 2,..., m) λi = 1 sao cho x= m P i=1 λi xi . i=1 Định lý 1.1.3. ([7], tr 11, định lý 2.2) Một tập trong Rn là lồi khi và chỉ khi nó chứa tất cả các tổ hợp lồi của các phần tử của nó. A là tập lồi trong Rn khi và chỉ khi A = {x = m X λi xi | xi ∈ A; i=1 m X λi = 1; λi ≥ 0; i = 1, m, ∀m ∈ N}. i=1 Chứng minh. ⇐ / Chọn m = 2, khi đó A là tập lồi theo định nghĩa. ⇒ / Giả sử A là tập lồi, ta lấy tùy ý x1 , x2 , ..., xm ∈ A; λ1 , ..., λm ≥ 0 m m P P và λi = 1 ; x = λi xi . i=1 i=1 Ta chứng minh x ∈ A bằng quy nạp theo m. Với m = 1 : x1 ∈ A; λ1 = 1, khi đó x = x1 ∈ A. Với m = 2 : x1 , x2 ∈ A; λ1 +λ2 = 1 mà A lồi suy ra x = λ1 x1 +λ2 x2 ∈ A theo định nghĩa. Giả sử x ∈ A đúng với m − 1 , ta có m X λi xi ∈ A; ∀xi ∈ A; i=1 Xét x = m P i=1 λi xi = m X λi = 1; λi ≥ 0; i ∈ N. i=1 m−1 P λi xi + λm xm . i=1 Nếu λm = 0 thì x ∈ A theo giả thiết quy nạp. Nếu λm = 1 thì λ1 = ... = λm−1 = 0 khi đó x = xm ∈ A. Nếu 0 < λ < 1 ta có 1 − λm = λ1 + ... + λm−1 > 0 5 λi ≥ 0 (i = 1, ..., m − 1). 1 − λm Vì m−1 X i=1 m−1 X λi λi = 1 nên theo giả thiết quy nạp y = xi ∈ A, 1 − λm 1 − λ m i=1 từ đó với y ∈ A, xm ∈ A, 1 − λm > 0 và (1 − λm ) + λm = 1 suy ra x = (1 − λm )y + λm xm ∈ A do A là tập lồi. Định lý 1.1.4. Một tập A trong R là lồi khi và chỉ khi A liên thông. Chứng minh. ⇒ / Giả sử A không liên thông , khi đó A là hợp của hai tập mở rời nhau. Giả sử A = B ∪ C; B ∩ C = ∅; B, C mở, với y+z B = (x, y); C = (z, t), ở đó y < z. Suy ra ∈ / A, mâu thuẫn vì A 2 lồi. ⇐ / Giả sử A không lồi, khi đó tồn tại α ∈ (0, 1) và x, y ∈ A, x < y sao cho αx + (1 − α)y ∈ /A Lấy z ∈ A suy ra " z 6= αx + (1 − α)y ⇒ z > αx + (1 − α)y z < αx + (1 − α)y Lại do x < αx + (1 − α)y < y nên A = B ∪ C với B = {s ∈ A : s < αx + (1 − α)y} C = {s ∈ A : s > αx + (1 − α)y} Điều này mâu thuẫn với tính chất A liên thông. Ví dụ 1.1.1. Các tập lồi trong R: ∅, {x} , (a, b), (a, b] , [a, b) , [a, b] , R 6 1.2. Định nghĩa hàm lồi và các tính chất 1.2.1. Hàm lồi Định nghĩa 1.2.1. ([1], tr 78) Cho hàm f : S → R, trong đó S ⊂ Rn ; R = R ∪ {−∞, +∞}, các tập dom f = {x ∈ S | f (x) < +∞} , epi f = {(x, α) ∈ S × R | f (x) ≤ α} , được gọi lần lượt là miền hữu hiệu và trên đồ thị của hàm f . Định nghĩa 1.2.2. ([3], tr 39, định nghĩa 2.4) Hàm f : S → R được gọi là lồi nếu trên đồ thị của nó là một tập lồi trong S × R. Nếu dom f 6= ∅ và f (x) > −∞ với mọi x ∈ S ta nói hàm f là chính thường. Ví dụ 1.2.2. a) Hàm f :R→R f (x) = x2  epi f = (x; µ) ∈ R × R | f (x) = x2 ≤ µ là tập lồi trong R × R. Thật vậy, lấy hai điểm bất kỳ (x1 , µ1 ) ∈ epi f, (x2 , µ2 ) ∈ epi f , tức là µ1 ≥ x1 2 , µ2 ≥ x2 2 . Ta cần chứng minh λ (x1 , µ1 ) + (1 − λ) (x2 , µ2 ) ∈ epi f ; 0≤λ≤1 Điều này tương đương với (λx1 + (1 − λ)x2 , λµ1 + (1 − λ)µ2 ) ∈ epif ⇔ λµ1 + (1 − λ)µ2 ≥ (λx1 + (1 − λ)x2 )2 ⇔ λµ1 + (1 − λ)µ2 ≥ λ2 x1 2 + (1 − λ)2 x2 2 + 2λ(1 − λ)x1 x2 . Mà λµ1 + (1 − λ)µ2 ≥ λx1 2 + (1 − λ)x2 2 . 7 Và λx1 2 + (1 − λ)x2 2 ≥ λ2 x1 2 + (1 − λ)2 x2 2 + 2λ(1 − λ)x1 x2   2 2 2 ⇔ (λ − λ )x1 + (1 − λ) − (1 − λ) x2 2 − 2λ(1 − λ)x1 x2 ≥ 0 ⇔ λ(1 − λ)x1 2 + λ(1 − λ)x2 2 − 2λ(1 − λ)x1 x2 ≥ 0 ⇔ λ(1 − λ)(x1 − x2 )2 ≥ 0 (luôn đúng). Suy ra epi f là hàm lồi nên f là hàm lồi. b) Hàm f :R→R f (x) = x3 không là hàm lồi vì  epi f = (x; µ) ∈ R × R | f (x) = x3 ≤ µ không lồi trong R × R. Thật vậy, lấy hai điểm bất kỳ (0, 0) ∈ epif, (−1, −1) ∈ epif , lấy 1 λ = khi đó 2   1 1 1 1 λ(0, 0) + (1 − λ)(−1, −1) = (0, 0) + (−1, −1) = − , − 2 2 2 2 không thuộc epi f . Ví dụ 1.2.3. ([3], tr 40, ví dụ 1.4) Cho hàm chỉ δ(. | A) ( 0 khi x ∈ A; δ(x | A) := +∞ khi x ∈ / A. Nếu A là tập lồi, A ⊂ Rn thì δ(. | A) là hàm lồi. Thật vậy, khi x ∈ A thì epi δ = {(x, µ) ; µ ≥ 0} là tập lồi. Khi x ∈ / A thì epi δ = ∅ là tập lồi. Vậy epi δ lồi nên δ(. | A) là hàm lồi. 8 Định lý 1.2.1. ([3], tr 40, định lý 2.1) Giả sử A là tập lồi trong Rn , hàm f : A → (−∞; +∞]. Khi đó, f lồi trên A khi và chỉ khi f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y) (1.1) ∀λ ∈ [0; 1]; ∀x, y ∈ A. Chứng minh. ⇒ / Giả sử f là hàm lồi, ta có thể xem như λ ∈ (0; 1) vì với λ ∈ {0; 1} thì (1.1) hiển nhiên đúng. Lấy r = f (x); s = f (y). Vì f lồi suy ra dom f lồi. Thật vậy, dom f là hình chiếu trên X của epi f dom f = {x : f (x) < +∞} = {x : ∃r, (x, r) ∈ epi f } . Như vậy dom f là ảnh của tập lồi epi f qua một ánh xạ tuyến tính, do đó dom f lồi. Nếu x hoặc y không thuộc dom f , giả sử x không thuộc dom f thì f (x) = +∞, do λ ∈ (0; 1) nên f (x) = +∞ suy ra λf (x) = +∞ và (1.1) đúng. Nếu x, y ∈ dom f suy ra λx + (1 − λ)y ∈ dom f (vì dom f lồi) suy ra f (λx + (1 − λ)y) = +∞. Do epi f lồi nên với mọi (x, r) ∈ epi f ; (y, s) ∈ epi f ; λ ∈ (0; 1) ta có λ(x, r) + (1 − λ)(y, s) = (λx + (1 − λ)y; λr + (1 − λ)s) ∈ epif suy ra f (λx + (1 − λ)y) ≤ λr + (1 − λ)s. Vậy f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y). ⇐ / Giả sử (1.1) đúng. Lấy tùy ý (x, r) ∈ epi f ; (y, s) ∈ epi f ; λ ∈ [0; 1]. Ta phải chứng minh λ(x, r) + (1 − λ)(y, s) ∈ epi f. Vì (x, r) ∈ epi f ; (y, s) ∈ epif nên f (x) ≤ r; f (y) ≤ s. Từ đó suy ra f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y) ≤ λr + (1 − λ)s 9 hay (λx + (1 − λ)y; λr + (1 − λ)s) ∈ epi f . Vậy λ(x, r) + (1 − λ)(y, s) ∈ epi f . Định lý 1.2.2. (Bất đẳng thức Jensen)([3], tr 42, định lý 2.2) Giả sử f : Rn → (−∞; +∞]. Khi đó f là một hàm lồi khi và chỉ khi m P với mọi λi ≥ 0(i = 1, ..., m); λi = 1; mọi x1 , ..., xm ∈ R ta có i=1 f (λ1 x1 + ... + λm xm ) ≤ λ1 f (x1 ) + ... + λm f (xm ). (1.2) Chứng minh. Không giảm tổng quát, giả sử λi ≥ 0 (i = 1, ..., m). Ta có, nếu xi ∈ / dom f thì f (xi ) = +∞; λi f (xi ) = +∞. Khi đó (1.2) hiển nhiên đúng. domf lồi nên nếu f (xi ) < +∞; i = 1, ..., m thì Do m m P P f λi xi < +∞ vì λi xi ∈ dom f . i=1 i=1 Nếu xi ∈ dom f , do epi f lồi và (xi , f (xi )) ∈ epi f ; i = 1, ..., m nên theo định lý 1.1.3 ta có (λ1 x1 + ... + λm xm ; λ1 f (x1 ) + ... + λm f (xm ) ∈ epi f. Từ đó suy ra f (λ1 x1 + ... + λm xm ) ≤ λ1 f (x1 ) + ... + λm f (xm ). Mệnh đề 1.2.1. ([3], tr 42, mệnh đề 2.1) Giả sử f : Rn → R, f là hàm lồi khi và chỉ khi f (λx + (1 − λ)y) < λr + (1 − λ)s; ∀λ ∈ (0; 1); ∀x, y : f (x) < r; f (y) < s. Định nghĩa 1.2.3. ([3], tr 43, định nghĩa 2.5) Một hàm f xác định trên Rn được gọi là thuần nhất dương nếu f (λx) = λf (x) với mọi x ∈ Rn ; mọi λ > 0. Định lý 1.2.3. ([3], tr 44, định lý 2.4) Hàm thuần nhất dương f : Rn → (−∞; +∞] là lồi khi và chỉ khi f (x + y) ≤ f (x) + f (y); ∀x, y ∈ Rn . (1.3) 10 Chứng minh. ⇒ / Giả sử hàm thuần nhất dương f là lồi. Lấy x, y ∈ Rn 1 1 f (x + y) = 2f ( x) + f ( y) 2  2 1 1 ≤ 2 f (x) + f (y) 2 2 = f (x) + f (y). ⇐ / Giả sử (1.3) đúng. Lấy (xi , ri ) ∈ epi f (i = 1, 2), ta có (x1 + x2 , r1 + r2 ) ∈ epi f , bởi vì f (x1 + x2 ) ≤ f (x1 ) + f (x2 ) ≤ r1 + r2 . Mà f là hàm thuần nhất dương nên nếu (x, r) ∈ epi f thì f (x) ≤ r và λf (x) = f (λx) ≤ λr (0 < λ < ∞) suy ra λ(x, r) ∈ epi f . Vậy epi f đóng đối với phép cộng và phép nhân vô hướng. Hay λ(x1 , r1 ) + (1 − λ)(x2 , r2 ) ∈ epi f với mọi λ ∈ [0; 1]. Từ đó suy ra epi f là lồi, suy ra f là hàm lồi. Định lý 1.2.4. Một hàm thực một biến ϕ(t) khả vi trong một khoảng mở (a, b) ⊂ R lồi khi và chỉ khi ϕ0 (t) là hàm tăng. Chứng minh. ⇒ / Lấy t1 < t2 < t3 với t1 , t2 , t3 ∈ (a, b), bởi vì hàm ϕ(t) lồi và t2 = t3 − t2 t2 − t1 t1 + t3 . t3 − t1 t3 − t1 Cho nên ϕ(t2 ) ≤ t3 − t2 t2 − t1 ϕ(t1 ) + ϕ(t3 ), t3 − t1 t3 − t1 từ đó ta có ϕ(t2 ) − ϕ(t1 ) ≤ t2 − t1 [ϕ(t3 ) − ϕ(t1 )] , t3 − t1 ϕ(t3 ) − ϕ(t2 ) ≥ t3 − t2 [ϕ(t3 ) − ϕ(t1 )] . t3 − t1 Vậy ϕ(t2 ) − ϕ(t1 ) ϕ(t3 ) − ϕ(t1 ) ϕ(t3 ) − ϕ(t2 ) ≤ ≤ . t2 − t1 t3 − t1 t3 − t2 11 Cho t2 → t1 + rồi cho t2 → t3 − ta có ϕ0 (t1 ) ≤ ϕ(t3 ) − ϕ(t1 ) ≤ ϕ0 (t3 ). t3 − t1 Suy ra ϕ0 (t) tăng. ⇐ / ϕ0 (t) tăng kéo theo với mọi [t1 , t2 ] ⊂ [a, b] và mọi λ ∈ (0, 1) ta có Z t2 0≤λ [ϕ0 (t) − ϕ0 (λt)]dt  t1  ϕ(t1 + λ(t2 − t1 )) ϕ(t1 ) = λ ϕ(t2 ) − ϕ(t1 ) − + λ λ = λ [ϕ(t2 ) − ϕ(t1 )] − ϕ(t1 + λ(t2 − t1 )) + ϕ(t1 ). Do đó ϕ(t1 + λ(t2 − t1 )) ≤ ϕ(t1 ) + λ [ϕ(t2 ) − ϕ(t1 )] hay ϕ((1 − λ)t1 + λ(t2 − t1 )) ≤ (1 − λ)ϕ(t1 ) + λϕ(t2 ). Suy ra ϕ(t) lồi. 1.2.2. Các phép toán về hàm lồi Định lý 1.2.5. Cho f là một hàm lồi. f : Rn → (−∞; +∞] và ϕ là một hàm lồi ϕ : R → (−∞; +∞] không giảm, khi đó h = ϕ(f (x)) cũng lồi. Chứng minh. Với mọi x1 , x2 ∈ Rn ; λ ∈ (0; 1) h((1 − λ)x1 + λx2 ) = ϕ(f ((1 − λ)x1 + λx2 )) ≤ ϕ((1 − λ)f (x1 ) + λf (x2 )) ≤ (1 − λ)ϕ(f (x1 )) + λϕ(f (x2 )) ≤ (1 − λ)h(x1 ) + λh(x2 ). (do f lồi và ϕ không giảm). Từ đó suy ra h lồi. Định lý 1.2.6. ([3], tr 47, định lý 2.6) Cho fi (i = 1, ..., m) là hàm lồi, chính thường trên Rn khi đó f1 + f2 + ... + fm là một hàm lồi trên Rn . 12 Ví dụ 1.2.4. Cho ( 0 x∈A f1 = là hàm lồi, chính thường. +∞ x ∈ /A ( 0 x∈B f2 = là hàm lồi, chính thường. +∞ x∈ /B f1 + f2 lồi không chính thường nếu A ∩ B = ∅. Thật vậy, f1 + f2 lồi theo Định lý 1.2.6, ta chứng minh f1 + f2 không chính thường. Ta có, nếu x ∈ A thì x ∈ / B khi đó f2 (x) = +∞ nên (f1 + f2 )(x) = f1 (x) + f2 (x) = +∞ suy ra x ∈ / dom (f1 + f2 ). Nếu x ∈ B thì x ∈ / A khi đó f1 (x) = +∞ nên (f1 + f2 )(x) = f1 (x) + f2 (x) = +∞ suy ra x ∈ / dom (f1 + f2 ). Vậy dom (f1 + f2 ) = ∅, do đó f1 + f2 lồi không chính thường. Định lý 1.2.7. ([7], tr 33, định lý 5.3) Cho C là một tập lồi trong Rn+1 và đặt f (x) = inf {µ | (x, µ) ∈ C} . Khi đó f là hàm lồi trên miền xác định. Chứng minh. Lấy µ1 , µ2 ∈ R; λ ∈ (0; 1). Giả sử f (x) < µ1 ; f (y) < µ2 , ta có f ((1 − λ)x + λy) < (1 − λ)µ1 + λµ2 . Thật vậy theo định nghĩa f ta có f ((1 − λ)x + λy) = inf {µ | ((1 − λ)x + λy, µ) ∈ C} . Vì f (x) < µ1 nên với ε = µ − f (x) > 0; tồn tại µ1 : (x, µ1 ) ∈ C và µ1 < f (x) + ε. Do đó f (x) < µ1 < µ1 . Tương tự, từ f (y) < µ2 suy ra tồn tại µ2 : (y, µ2 ) ∈ C và µ2 < f (y) + ε1 mà f (y) < µ2 < µ2 . 13 Từ trên ta có ((1 − λ)x + λy; (1 − λ)µ1 + λµ2 ) ∈ C và (1 − λ)µ1 + λµ2 < (1 − λ)µ1 + λµ2 . Do đó f ((1 − λ)x + λy) ≤ (1 − λ)µ1 + λµ2 < (1 − λ)µ1 + λµ2 . Từ đây suy ra f lồi theo mệnh đề 1.2.1. 1.2.3. Tính liên tục của hàm lồi Định nghĩa 1.2.4. Cho X là không gian định chuẩn. 1) Ta nói rằng f là hàm Lipschitz trên tập D ⊂ X, nếu tồn tại số k sao cho |f (x) − f (x0 )| ≤ kkx − x0 k, ∀x, x0 ∈ D. 2) Hàm f được gọi là Lipschitz địa phương tại x ∈ X, nếu tồn tại số ε > 0 sao cho f là Lipschitz trên B(x, ε) ∩ D. 3) 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 của D. Mệnh đề 1.2.2. ([8], tr 44, mệnh đề 2.3) Một hàm lồi chính thường f trên Rn là liên tục tại mỗi điểm trong của miền hữu hiệu của nó. Định lý 1.2.8. ([8], tr 55, định lý 2.2) Cho một hàm lồi chính thường f trên Rn . Ta có các khẳng định sau là tương đương: i) f là liên tục tại điểm x0 ∈ Rn ; ii) f là bị chặn trên tại lân cận của x0 ∈ Rn ; iii) int(epi f ) 6= ∅; iv) int(dom f ) 6= ∅ và f là Lipschitz trên mỗi tập bị chặn chứa trong int(domf ); v) int(domf ) 6= ∅ và f là liên tục trên int(domf ). Chứng minh. [(i) ⇒ (ii)] Nếu f là liên tục tại một điểm x0 thì tồn tại một lân cận U của x0 thỏa mãn f (x) < f (x0 ) + 1 với mọi x ∈ U . [(ii) ⇒ (iii)] Từ giả thiết suy ra tồn tại lân cận U của x0 và c > 0 sao 14 cho f (x) ≤ c, với mọi x ∈ U . Đặt  V = (x, α) ∈ Rn+1 | x ∈ U, α > c , ta có V ⊂ epif và V là tập mở vì với bất kì (x, α) ∈ V thì (x, α) thuộc lân cận U × (c, +∞) ⊂ Rn+1 , nên ta suy ra int(epif ) 6= ∅. [(iii) ⇒ (iv)] Nếu int(epif ) 6= ∅ thì tồn tại một tập mở U và một khoảng mở I ⊂ R thỏa mãn U × I ⊂ epif , do đó U ⊂ domf , tức là int(domf ) 6= ∅. Xét tập compact bất kì C ⊂ int(domf ) và lấy B là hình cầu đơn vị trong Rn . Với mỗi r > 0, tập C + rB là compact, và họ những tập đóng {(C + rB)\int(domf ), r > 0} có giao là rỗng. Do tính compact của C + rB một họ con hữu hạn của những họ này phải có một giao bằng rỗng, do đó với r > 0 ta phải có (C + rB)\int(domf ) = ∅, nghĩa là (C +rB) ⊂ int(domf ). Bởi Mệnh đề 1.2.2 hàm f là liên tục trên int(domf ). Kí hiệu µ1 và µ2 là cực đại và cực tiểu của f trên C + rB. r(x − x0 ) 0 Lấy x, x là hai điểm phân biệt trong C và lấy z = x + . Khi đó kx − x0 k z ∈ C + rB ⊂ int(domf ). Vì 0 x = (1 − α)x + αz, kx − x0 k α= , r + kx − x0 k và z, x0 ∈ domf nên f (x) ≤ (1 − α)f (x0 ) + αf (z) = f (x0 ) + α(f (z) − f (x0 )), và f (x) − f (x0 ) ≤ α(f (z) − f (x0 )) ≤ α(µ1 − µ2 ) µ1 − µ2 ≤ kkx − x0 k, k = . r Bởi tính đối xứng, ta cũng có f (x0 ) − f (x) ≤ kkx − x0 k. Do vậy, với mọi x, x0 thỏa mãn x ∈ C, x0 ∈ C |f (x) − f (x0 )| ≤ k kx − x0 k , điều này chứng minh cho tính Lipschitz của f trên C. (iv) ⇒ (v) và (v) ⇒ (i) : là rõ ràng. 15 Ví dụ 1.2.5. Hàm f (x) = x2 , x ∈ R là hàm lồi liên tục trên R. Hàm f (x) = −∞, x ∈ R là hàm lồi không liên tục trên R. 1.3. Kết luận Trong chương này chúng ta đã trình bày định nghĩa, một số tính chất cơ bản của tập lồi và hàm lồi cùng với một số ví dụ minh họa. Một trong những ứng dụng chính của lý thuyết vi phân là tìm cực trị của các phiếm hàm. Tuy nhiên khi tìm cực trị của một số phiếm hàm không trơn (không khả vi) tại một số điểm thì lý thuyết vi phân nêu trên không vận dụng được. Do đó, trong chương tiếp theo ta sẽ mở rộng khái niệm vi phân cho dưới vi phân của hàm lồi. Chương 2 Dưới vi phân hàm lồi Trong chương này chúng ta sẽ trình bày những kiến thức cơ bản của dưới vi phân của hàm lồi cần dùng trong quá trình nghiên cứu một số bài toán tối ưu không trơn. 2.1. Định nghĩa và các tính chất cơ bản Định nghĩa 2.1.1. ([3], tr 110, định nghĩa 4.2) Cho f là hàm lồi chính thường trên Rn ; khi đó vectơ x∗ ∈ Rn được gọi là vectơ dưới gradient của f tại điểm x0 nếu f (x) − f (x0 ) ≥ hx∗ , x − x0 i ∀x ∈ Rn . (2.1) Tập tất cả các dưới gradient của f tại x0 được gọi là dưới vi phân của f tại x0 và được kí hiệu là ∂f (x0 ). Hàm f được gọi là dưới khả vi tại x0 nếu ∂f (x0 ) 6= ∅. Ví dụ 2.1.6. Cho f (x) = x2 , x ∈ R. a) Với x0 = 0, ta có x∗ ∈ ∂f (0) ⇔ x2 ≥ hx∗ , xi ∀x ∈ R ⇔ x2 − x∗ x ≥ 0 ∀x ∈ R ⇔ x∗ = 0. Vậy ∂f (0) = {0}.