Luận văn Dưới vi phân của hàm lồi và một số ứng dụng trong tối ưu

1Đại học thái nguyên Trường đại học sư phạm - - - - - - - - - - - - - - - - - Nông Thị Mai Dưới vi phân của hàm lồi và một số ứng dụng trong tối ưu Chuyên ngành: Giải tích Mã số:60.46.01 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 2008 2Mục lục Trang Trang phụ bìa 1 Mục lục 2 Danh mục các ký hiệu, các chữ viết tắt 3 Lời nói đầu 4 Chương1. Các kiến thức cơ bản về tập lồi và hàm lồi 5 1.1. Tập lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2. Hàm lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.2.1. Hàm lồi . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.2.2. Tính liên tục của hàm lồi . . . . . . . . . . . . . . . . . 15 1.2.3. Các phép toán bảo toàn tính lồi . . . . . . . . . . . . . 15 1.2.4. Bất đẳng thức lồi . . . . . . . . . . . . . . . . . . . . . 16 1.2.5. Hàm liên hợp . . . . . . . . . . . . . . . . . . . . . . . 16 Chương2. Dưới vi phân của hàm lồi 18 2.1. Đạo hàm theo phương . . . . . . . . . . . . . . . . . . . . . . 18 2.2. Dưới vi phân và các tính chất . . . . . . . . . . . . . . . . . . 22 2.2.1. Dưới vi phân . . . . . . . . . . . . . . . . . . . . . . . 22 2.2.2. Tính khả vi của hàm lồi . . . . . . . . . . . . . . . . . 30 2.2.3. Tính đơn điệu của dưới vi phân . . . . . . . . . . . . . 35 2.2.4. Tính liên tục của dưới vi phân . . . . . . . . . . . . . . 39 2.2.5. Phép tính với dưới đạo hàm . . . . . . . . . . . . . . . 43 2.3. Dưới vi phân xấp xỉ . . . . . . . . . . . . . . . . . . . . . . . 45 Chương3. Một số ứng dụng của dưới vi phân trong tối ưu hoá 52 3.1. Các khái niệm . . . . . . . . . . . . . . . . . . . . . . . . . . 52 3.2. Bài toán lồi không có rằng buộc . . . . . . . . . . . . . . . . . 53 3.3. Bài toán lồi với rằng buộc đẳng thức . . . . . . . . . . . . . . 53 3.4. Bài toán lồi với rằng buộc bất đẳng thức . . . . . . . . . . . . 54 Kết luận 63 Tài liệu tham khảo 64 3Danh mục các ký hiệu, các chữ viết tắt Với n là số nguyên dương, ký hiệu: Rn: không gian Euclide n-chiều trên trường số thực; Rn+: góc không âm của R n (tập các véc-tơ có mọi toạ độ đều không âm ); R: trục số thực (R = R1); R: trục số thực mở rộng (R = R ∪ {−∞,+∞}); N : tập hợp số nguyên dương; 2R n : tập hợp tất cả các tập con của Rn; Với mọi véc-tơ x, y ∈ Rn, ký hiệu: xi: toạ độ thứ i của x; xT : véc-tơ hàng (chuyển vị của x); 〈x, y〉 = xTy = xy := ∑nj=1 xjyj: tích vô hướng của hai véc-tơ x và y; ||x|| = √∑n j=1 x 2 j : chuẩn Euclide của x; [x, y]: đoạn thẳng đóng nối x và y; (x, y): đoạn thẳng mở nối x và y; Với tập A, ký hiệu: A: bao đóng của A; coA: bao lồi của A; aff A: bao a-phin của A; intA: tập hợp các điểm trong của A; riA: tập hợp các điểm trong tương đối của A; Với hàm f của n biến, ký hiệu: f : hàm bao đóng của f ; dom f : tập hữu dụng của f ; f ∗: hàm liên hợp của f ; epi f : trên đồ thị của f ; ∂f(x): dưới vi phân của f tại x; ∂f(x): - dưới vi phân của f tại x; Of(x) hoặc f ′(x): đạo hàm của f tại x; f ′(x, d): đạo hàm theo phương d của f tại x; 4Lời nói đầu Giải tích lồi là một bộ môn quan trọng trong giải tích phi tuyến hiện đại. Giải tích lồi nghiên cứu những khía cạnh giải tích của tập lồi và hàm lồi. Dưới vi phân là một khái niệm cơ bản của giải tích lồi. Đây là mở rộng cho đạo hàm khi hàm không khả vi. Điều này cho thấy vai trò của dưới vi phân trong giải tích hiện đại cũng có tầm quan trọng như vai trò của đạo hàm trong giải tích cổ điển. Dưới vi phân của hàm lồi có rất nhiều ứng dụng trong giải tích phi tuyến và đặc biệt trong các bộ môn toán ứng dụng, như tối ưu hoá, bất đẳng thức biến phân, cân bằng v...v. Mục đích của luận văn là trình bày một cách có hệ thống, các kiến thức cơ bản và quan trọng nhất về dưới vi phân của hàm lồi và xét một số ứng dụng điển hình của dưới vi phân trong tối ưu hoá. Luận văn gồm 3 chương. Trong chương 1 sẽ trình bày những kiến thức cơ bản về tập lồi và hàm lồi. Đây là các kiến thức bổ trợ cho chương 2 và do đó sẽ không được chứng minh trong luận văn này. Trong chương 2 sẽ đề cập về đạo hàm theo phương, dưới vi phân, dưới vi phân xấp xỉ và một số tính chất cơ bản của chúng. Dựa trên các kết quả đã nghiên cứu trong các chương trước, trong chương 3 sẽ trình bày các điều kiện cực trị cho các bài toán quy hoạch lồi với các rằng buộc khác nhau (không rằng buộc, rằng buộc đẳng thức, rằng buộc bất đẳng thức). Bản luận văn này được hoàn thành dưới sự hướng dẫn khoa học của GS -TSKH Lê Dũng Mưu. Nhân đây em xin chân thành cảm ơn thầy đã hướng dẫn, động viên, khuyến khích em học tập, nghiên cứu để hoàn thành luận văn này. Chương 1 Các kiến thức cơ bản về tập lồi và hàm lồi Trong luận văn này, chúng ta sẽ làm việc với không gian euclid-n chiều trên trường số thực R. Không gian này được kí hiệu là Rn. Chương này nhằm giới thiệu 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ó. Các kiến thức ở trong chương này đuợc lấy ở tài liệu : + Giáo trình "Nhập môn giải tích lồi ứng dụng" của tác giả Lê Dũng Mưu và Nguyễn Văn Hiền. + Cuốn "Convex Analysis" của tác giả T.Rockafellar. Do chương này chỉ mang tính chất bổ trợ, nên ta không chứng minh các kết quả nêu ở đây. 1.1 Tập lồi Định nghĩa 1.1. Đ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.2. 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. 5 6Ví dụ 1.1. (Về tập lồi). a) Tập C = R2+ là tập lồi. b) Tập C = [−2; 3) là tập lồi. c) Tập C ≡ oxy trong R3 là tập lồi. d) Các tam giác, hình tròn trong mặt phẳng là các tập lồi. Ví dụ 1.2. (Về tập không lồi). a) Tập C = (−2; 0) ∪ (0; 3) không là tập lồi. b) Tập C = {(x, y) ∈ R2 | xy = 0} không là tập lồi. Định nghĩa 1.3. 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∑ j=1 λjx j , λj > 0 , ∀j = 1, ..., k , k∑ j=1 λj = 1. Định nghĩa 1.4. 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 | aTx = α}, 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. Một siêu phẳng sẽ chia không gian ra hai nửa không gian. Nửa không gian được định nghĩa như sau: Định nghĩa 1.5. Nửa không gian là một tập hợp có dạng {x | aTx > α}, trong đó a 6= 0 và α ∈ R. Đây là nửa không gian đóng. Định nghĩa 1.6. Cho C ⊆ Rn là một tập lồi và x ∈ C. Tập NC(x) := {ω | 〈ω, y − x〉 6 0 , ∀y ∈ C}, được gọi là nón pháp tuyến ngoài của C tại x. Nhận xét. NC(x) là một nón lồi đóng. 7Ví dụ 1.3. Trong R2, xét tập C = R2+. NC(0) = {ω | 〈ω, y − 0〉 6 0 , ∀y ∈ C} = {ω | 2∑ i=1 ωiyi 6 0} = {ω | ωi 6 0}. Định nghĩa 1.7. Một điểm a ∈ C được gọi là điểm trong tương đối của C nếu nó là điểm trong của C theo tô-pô cảm sinh bởi aff C. Ta sẽ ký hiệu tập hợp các điểm trong tương đối của C là riC. Theo định nghĩa trên ta có: riC := {a ∈ C | ∃B : (a+B) ∩ aff C ⊂ C}, trong đó B là một lân cận mở của gốc. Hiển nhiên riC := {a ∈ aff C | ∃B : (a+B) ∩ aff C ⊂ C}. Như thường lệ, ta ký hiệu C, là bao đóng của C. Tập hợp C \ riC được gọi là biên tương đối của C. Mệnh đề 1.1. Cho C ⊆ Rn là một tập lồi. Giả sử x ∈ riC. Khi đó với mọi y ∈ C tất cả các điểm trên đoạn thẳng nối x và y, có thể trừ y, đều thuộc riC. Nói cách khác, với mọi 0 6 λ < 1, thì (1− λ) riC + λC ⊂ riC. Định nghĩa 1.8. Một đường thẳng nối 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.9. Một tập C được gọi là tập a-phin nếu nó chứa mọi đường thẳng đi qua hai điểm bất kỳ của nó, tức là ∀x, y ∈ C , ∀λ ∈ R =⇒ λx+ (1− λ)y ∈ C. Ví dụ 1.4. (Về tập a-phin). Tập C = R2 là tập a-phin, không gian con là một tập affine 8Nhận xét. Tập a-phin là một trường hợp riêng của tập lồi. Định nghĩa 1.10. Bao lồi của một tập E là giao của tất cả các tập lồi chứa E. Bao lồi của một tập E sẽ được ký hiệu là coE. Bao lồi đóng của một tập E là tập lồi đóng nhỏ nhất chứa E. Ta sẽ ký hiệu bao lồi đóng của một tập E là coE. Bao a-phin của E là giao của tất cả các tập a-phin chứa E. Bao a-phin của một tập E sẽ được ký hiệu là aff E. Định nghĩa 1.11. Cho E ⊆ Rn. Điểm a được gọi là điểm trong của E nếu tồn tại một lân cận mở U(a) của a sao cho U(a) ⊂ E. Ký hiệu tập hợp các điểm trong của tập E là intE và B là quả cầu đơn vị tâm ở gốc. Khi đó theo định nghĩa ta có intE = {x | ∃r > 0 : x+ rB ⊂ E}. Điểm a được gọi là điểm biên của E nếu mọi lân cận của a đều có điểm thuộc E và điểm không thuộc E. Tập E được gọi là tập mở nếu mọi điểm của E đều là điểm trong của E. Tập E được gọi là tập đóng nếu E chứa mọi điểm biên của nó. Tập E được gọi là bị chặn, nếu tồn tại một hình cầu chứa E. Trong Rn tập E được gọi là tập compắc nếu E là một tập đóng và bị chặn. Định nghĩa 1.12. Cho C là một tập lồi. Một tập F ⊂ C được gọi là một diện của một tập lồi C nếu F là tập lồi và ∀x, y ∈ C , tx+ (1− t)y ∈ F , 0 < t < 1 =⇒ [x, y] ⊂ F. Ví dụ 1.5. Cho C := {(x, y, z) ∈ R3 | x, y, z ∈ [0, 1]}. Tập F1 := {(x, y, z) ∈ R3 | x, y ∈ [0, 1], z = 0} là một diện của tập C. Tập F2 := {(x, y, z) ∈ R3 | y ∈ [0, 1], x = 1, z = 0} là một diện của tập C. Điểm cực biên là diện có thứ nguyên (chiều) bằng 0. 9Định nghĩa 1.13. Cho x0 ∈ C. Ta nói aTx = α là siêu phẳng tựa của C tại x0, nếu aTx0 = α , aTx > α ∀x ∈ C. Như vậy siêu phẳng tựa của C tại x0 ∈ C là siêu phẳng đi qua x0 và để tập C về một phía. Nửa không gian aTx > α trong định nghĩa trên, được gọi là nửa không gian tựa của C tại x0. Định lý 1.1. (Krein-Milman). Mọi tập lồi đóng khác rỗng, không chứa đường thẳng đều có điểm cực biên. Định lý 1.2. (Xấp xỉ tuyến tính tập lồi). Mọi tập lồi đóng khác rỗng và không trùng với toàn bộ không gian đều là giao của tất cả các nửa không gian tựa của nó. Định nghĩa 1.14. Cho hai tập C và D khác rỗng. Ta nói siêu phẳng aTx = α tách C và D nếu aTx 6 α 6 aTy , ∀x ∈ C , ∀y ∈ D. Ta nói siêu phẳng aTx = α tách chặt C và D nếu aTx < α < aTy , ∀x ∈ C , ∀y ∈ D. Ta nói siêu phẳng aTx = α tách mạnh C và D nếu Supx∈C a Tx < α < infy∈D aTy. Ví dụ 1.6. (Tách nhưng không tách chặt). Cho tập C = {(x, y) ∈ R2 | x2 + y2 6 1}, và D = {(x, y) ∈ R2 | − 1 6 x 6 1, 1 6 y 6 3}. Ta có: 10 + C và D khác rỗng. + C,D tách được vì tồn tại siêu phẳng (0, 1)(x, y) = 1 thoả mãn (0, 1)(x, y) 6 1 6 (0, 1)(x′, y′) ∀(x, y) ∈ C, ∀(x′, y′) ∈ D. Hay y 6 1 6 y′ ∀(x, y) ∈ C, ∀(x′, y′) ∈ D. + C,D không tách chặt được vì không tồn tại siêu phẳng (a1, a2)(x, y) = α nào thoả mãn (a1, a2)(x, y) < α < (a1, a2)(x ′, y′) ∀(x, y) ∈ C, ∀(x′, y′) ∈ D. Ví dụ 1.7. (Tách nhưng không tách mạnh). Cho tập C = {(x, y) ∈ R2 | x > 0, y = 0}, và D = {(x, y) ∈ R2 | y > 1 x , y > 0, x > 0}. Ta có: + C và D khác rỗng. + C,D tách được vì tồn tại siêu phẳng (0, 1)(x, y) = 0 thoả mãn (0, 1)(x, y) = 0 6 (0, 1)(x′, y′) ∀(x, y) ∈ C, ∀(x′, y′) ∈ D. Hay y = 0 6 y′ ∀(x, y) ∈ C, ∀(x′, y′) ∈ D. + C,D không tách mạnh được vì Sup(x,y)∈C(0, 1)(x, y) = 0, inf(x′,y′)∈D(0, 1)(x′, y′) = 0. Định lý 1.3. (Đị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. 11 Hệ quả 1.1. (Bổ đề liên thuộc). Cho C ⊂ Rn là một tập lồi khác rỗng. Giả sử x0 6∈ C. Khi đó tồn tại t ∈ Rn , t 6= 0 thoả mãn 〈t, x〉 > 〈t, x0〉 ∀x ∈ C. Định lý 1.4. (Đị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à compắc. Khi đó hai tập này có thể tách mạnh được bởi một siêu phẳng. Hệ quả 1.2. Cho C ⊂ Rn là một tập lồi đóng khác rỗng sao cho 0 6∈ C. Khi đó tồn tại một véc-tơ t ∈ Rn , t 6= 0 và α > 0 sao cho 〈t, x〉 > α > 0 , ∀x ∈ C. 1.2 Hàm lồi 1.2.1 Hàm lồi Cho C ⊆ Rn và f : C −→ R ∪ {−∞,+∞}. Ta sẽ kí hiệu: dom f := {x ∈ C | f(x) < +∞} . Tập dom f được gọi là miền hữu dụng của f epi f := {(x, à) ∈ C ì R | f(x) 6 à}. Tập epi f được gọi là trên đồ thị của hàm f . Bằng cách cho f(x) = +∞ nếu x 6∈ C, ta có thể coi f được xác định trên toàn không gian và hiển nhiên là dom f := {x ∈ Rn | f(x) < +∞}. epi f := {(x, à) ∈ Rn ìR | f(x) 6 à}. Định nghĩa 1.15. Cho ∅ 6= C ⊆ Rn lồi và f : C −→ R ∪ {−∞,+∞}. Ta nói f là hàm lồi trên C nếu epi f là một tập lồi trong Rn+1. Sau đây ta sẽ chủ yếu làm việc với hàm f : Rn −→ R ∪ {+∞}.Trong trường hợp này, định nghĩa trên tương đương với: 12 Hàm f : Rn −→ R ∪ {+∞} là hàm lồi trên C nếu f [λx+ (1− λ)y] 6 λf(x) + (1− λ)f(y) , ∀x, y ∈ C , ∀λ ∈ (0, 1) Hàm f : Rn −→ R ∪ {+∞} là hàm lồi chặt trên C nếu f [λx+ (1− λ)y] < λf(x) + (1− λ)f(y) , ∀x, y ∈ C , ∀λ ∈ (0, 1) Hàm f : Rn −→ R ∪ {+∞} là hàm lồi mạnh trên C với hệ số lồi η > 0 nếu f [λx+ (1− λ)y] 6 λf(x) + (1− λ)f(y)− 1 2 ηλ(1− λ)||x− y||2 , ∀x, y ∈ C , ∀λ ∈ (0, 1). Hàm f được gọi là một hàm lõm trên C, nếu −f là hàm lồi trên C. Ví dụ 1.8. Hàm a-phin. f(x) = aTx+ α, a ∈ Rn, α ∈ R ∀x, y ∈ Rn,∀λ ∈ (0, 1), ta có f [λx+ (1− λ)y] = aT [λx+ (1− λ)y] + α = λaTx+ (1− λ)aTy + α = λaTx+ λα + (1− λ)aTy + (1− λ)α = λ(aTx+ α) + (1− λ)(aTy + α) = λf(x) + (1− λ)f(y). Vậy f là một hàm lồi trên Rn. ∀x, y ∈ Rn,∀λ ∈ (0, 1), lại có −f [λx+ (1− λ)y] = −aT [λx+ (1− λ)y]− α = −λaTx− (1− λ)aTy − α = −λaTx− λα− (1− λ)aTy − (1− λ)α = −λ(aTx+ α)− (1− λ)(aTy + α) = −λf(x)− (1− λ)f(y). Vậy −f là một hàm lồi trên Rn. Suy ra f là một hàm lõm trên Rn. 13 Ví dụ 1.9. Hàm chỉ. Cho C 6= ∅ là một tập lồi . Đặt δC(x) := { 0 nếu x ∈ C, +∞ nếu x 6∈ C. Ta nói δC là hàm chỉ của C. + ∀x, y ∈ C, ∀λ ∈ (0, 1), ta có: δC(x) = 0 , δC(y) = 0. Do C lồi nên λx+ (1− λ)y ∈ C. Suy ra δC [λx+ (1− λ)y] = 0 = λδC(x) + (1− λ)δC(y). + ∀x ∈ C, ∀y 6∈ C, ∀λ ∈ (0, 1), ta có : δC(x) = 0 , δC(y) = +∞ , δC [λx+ (1− λ)y] 6 +∞. Suy ra δC [λx+ (1− λ)y] 6 λδC(x) + (1− λ)δC(y). + ∀x, y 6∈ C, ∀λ ∈ (0, 1), ta có : δC(x) = +∞ , δC(y) = +∞ , δC [λx+ (1− λ)y] 6 +∞. Suy ra δC [λx+ (1− λ)y] 6 λδC(x) + (1− λ)δC(y). Vậy δC là hàm lồi trên R n . Ví dụ 1.10. Hàm tựa. Đặt SC(y) := Supx∈C〈y, x〉.Ta nói SC là hàm tựa của C. ∀x, y ∈ C, ∀λ ∈ (0, 1), ta có SC [λx+ (1− λ)y] = Supz∈C〈λx+ (1− λ)y, z〉 = Supz∈C{〈λx, z〉+ 〈(1− λ)y, z〉} 6 Supz∈C〈λx, z〉+ Supz∈C〈(1− λ)y, z〉 = λ Supz∈C〈x, z〉+ (1− λ) Supz∈C〈y, z〉 = λSC(x) + (1− λ)SC(y). Vậy SC là hàm lồi trên C. Định nghĩa 1.16. Cho f : Rn −→ R ∪ {+∞} (không nhất thiết lồi), C ⊆ Rn là một tập lồi khác rỗng và η là một số thực . Ta nói η là hệ số lồi của f trên C, nếu với mọi λ ∈ (0, 1), với mọi x, y ∈ C, ta có: f [(1− λ)x+ λy] 6 (1− λ)f(x) + λf(y)− 1 2 ηλ(1− λ)||x− y||2. 14 Nếu η = 0 thì f lồi trên C. Nếu f có hệ số lồi trên C là η > 0, thì f lồi mạnh trên C với hệ số η. Định nghĩa 1.17. Một hàm f : Rn −→ R∪{+∞} được gọi là chính thường nếu dom f 6= ∅ và f(x) > −∞ với mọi x. Định nghĩa 1.18. Hàm f : Rn −→ R ∪ {+∞} được gọi là đóng, nếu epi f là một tập đóng trong Rn+1 Chú ý 1.1. 1. Nếu f là một hàm lồi trên một tập lồi C, thì có thể thác triển f lên toàn không gian bằng cách đặt fe(x) = { f(x) nếu x ∈ C, +∞ nếu x 6∈ C. Hiển nhiên fe(x) = f(x) với mọi x ∈ C và fe lồi trên Rn. Hơn nữa fe là chính thường khi và chỉ khi f chính thường. Tương tự fe đóng khi và chỉ khi f đóng. 2. Nếu f là một hàm lồi trên Rn thì dom f là một tập lồi vì dom f chính là hình chiếu trên Rn của epi f , tức là: dom f = {x|∃à ∈ R : (x, à) ∈ epi f}. Định nghĩa 1.19. Cho f : Rn −→ R ∪ {+∞}. Hàm f được gọi là thuần nhất dương (bậc 1) trên Rn nếu f(λx) = λf(x) ∀x ∈ Rn,∀λ > 0. Hàm f được gọi là dưới cộng tính nếu f(x+ y) 6 f(x) + f(y) ∀x, y. Hàm f được gọi là dưới tuyến tính nếu f là thuần nhất dương và dưới cộng tính. Ví dụ 1.11. Hàm chuẩn f(x) = ‖x‖ là hàm dưới tuyến tính. Thật vậy, ∀x ∈ Rn,∀λ > 0, ta có: f(λx) = ‖λx‖ = |λ|.‖x‖ = λ‖x‖ = λf(x). ∀x, y ∈ Rn, ta có: f(x+ y) = ‖x+ y‖ 6 ‖x‖+ ‖y‖ = f(x) + f(y). Mệnh đề 1.2. Cho f : Rn −→ R ∪ {+∞} là một hàm thuần nhất dương trên Rn. Khi đó: f lồi khi và chỉ khi f là dưới cộng tính. 15 1.2.2 Tính liên tục của hàm lồi Định nghĩa 1.20. Cho hàm f : E −→ R ∪ {−∞,+∞}. Hàm f được gọi là nửa liên tục dưới tại một điểm x ∈ E nếu với mọi dãy {xk} ⊂ E, xk → x ta có lim inf f(xk) > f(x). Hàm f được gọi là nửa liên tục trên tại x ∈ E nếu −f nửa liên tục dưới tại x ∈ E. Như vậy f nửa liên tục trên tại x ∈ E nếu với mọi dãy {xk} ⊂ E, xk → x ta có lim sup f(xk) 6 f(x). Hàm f được gọi là liên tục tại x ∈ E 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 ∈ E. Hàm f được gọi là nửa liên tục dưới trên E nếu nó nửa liên tục dưới tại mọi điểm thuộc E. Hàm f được gọi là nửa liên tục trên trên E nếu nó nửa liên tục trên tại mọi điểm thuộc E. Hàm f được gọi là liên tục trên E nếu nó nửa liên tục trên và nửa liên tục dưới trên E. Định nghĩa 1.21. Cho hai hàm f và g xác định trên Rn. Ta nói g là bao đóng của f , nếu epi g = epi f . Bao đóng của f sẽ được kí hiệu là f . Vậy epi f = epi f . Hàm f được gọi là đóng nếu epi f = epi f . 1.2.3 Các phép toán bảo toàn tính lồi Định nghĩa 1.22. Giả sử {fα}α∈I là một họ tuỳ ý các hàm số trên Rn và E ⊆ Rn. Hàm cận trên của họ hàm này trên coE, ký hiệu là Vα∈Ifα là hàm số được định nghĩa như sau: (Vα∈Ifα)(x) := Supα∈I fα(x) với mỗi x ∈ coE. 16 Mệnh đề 1.3. Giả sử {fα}α∈I là một họ hàm lồi trên Rn và E ⊆ Rn. Khi đó hàm cận trên của họ hàm này là một hàm lồi trên coE. 1.2.4 Bất đẳng thức lồi Định nghĩa 1.23. Cho D ⊆ Rn là một tập lồi và f1, ..., fm là các hàm lồi trên Rn. Hệ bất đẳng thức x ∈ D, fi(x) <= 0, i ∈ I được gọi là hệ bất đẳng thức lồi, trong đó I là tập chỉ số và ký hiệu <= có thể hiểu là < hoặc 6. Mệnh đề 1.4. Cho f1, ..., fm là các hàm lồi hữu hạn trên một tập lồi D 6= ∅ và A là một ma trận thực cấp k ì n. Giả sử b ∈ riA(D). Khi đó hệ x ∈ D, Ax = b, fi(x) < 0 i = 1, ..,m không có nghiệm, khi và chỉ khi tồn tại t ∈ Rk và λi > 0, i = 1, ..,m sao cho ∑m i=1 λi = 1 và 〈t, Ax− b〉+ m∑ i=1 λifi(x) > 0 ∀x ∈ D. 1.2.5 Hàm liên hợp Định nghĩa 1.24. Cho f : Rn −→ [−∞,+∞] là một hàm bất kỳ. Hàm f ∗(x∗) := Sup{〈x∗, x〉 − f(x) | x ∈ Rn} được gọi là hàm liên hợp của f . Chú ý 1.2. Như thường lệ, trong định nghĩa trên ta qui ước cận trên đúng trên một tập rỗng là −∞. Như vậy nếu f ≡ +∞, thì f ∗ ≡ −∞, ngoài ra nếu f có nhận giá trị −∞ thì f ∗ ≡ +∞. Để khỏi phải làm việc với hàm liên hợp đồng nhất bằng +∞ hoặc đồng nhất bằng −∞, ta sẽ hạn chế việc xét hàm liên hợp trong lớp hàm có tính chất sau: f 6≡ +∞ và tồn tại một hàm non a-phin của f. 17 Ví dụ 1.12. Xét hàm chỉ δC(x) = { 0 nếu x ∈ C, +∞ nếu x 6∈ C. Ta có: δ∗C(x ∗) := Supx∈Rn{〈x∗, x〉 − δC(x)} = Supx∈C{〈x∗, x〉 − δC(x)} = Supx∈C{〈x∗, x〉 − 0} = Supx∈C〈x∗, x〉 = SC(x ∗). Mệnh đề 1.5. Với mọi hàm số f , hàm liên hợp f ∗ là một hàm lồi đóng thoả mãn bất đẳng thức Fenchel sau: f ∗(x∗) > 〈x∗, x〉 − f(x) ∀x,∀x∗. Chú ý 1.3. Trong nhiều trường hợp, ta quan tâm đến hàm liên hợp thứ hai. Theo định nghĩa hàm liên hợp thì f ∗∗(x) := (f ∗)∗(x) = Sup{〈x, s〉 − f ∗(s) | s ∈ Rn}. Hàm liên hợp thứ hai tất nhiên luôn là một hàm lồi đóng. Mệnh đề 1.6. Giả sử f 6≡ +∞ và tồn tại một hàm non a-phin của f . Khi đó epi f ∗∗ = co(epi f). Hệ quả 1.3. f ≡ f ∗∗ khi và chỉ khi f là hàm lồi, đóng. Định nghĩa 1.25. Hàm l là hàm non a-phin của một hàm f trên Rn nếu l là hàm a-phin trên Rn và l(x) 6 f(x) ∀x ∈ Rn. Chương 2 Dưới vi phân của hàm lồi Phép tính vi phân là một trong những đề tài cơ bản nhất của giải tích cổ điển. Trong giải tích lồi, lý thuyết này lại càng trở nên phong phú nhờ những tính chất đặc biệt của tập lồi và hàm lồi. Mục đầu tiên của chương này sẽ xét đến đạo hàm theo phương của một hàm lồi. Tiếp đến ở mục 2, sẽ đưa ra định nghĩa về dưới vi phân và các tính chất của nó như: Xét tính khả vi của hàm lồi, khảo sát tính đơn điệu của dưới vi phân, khảo sát tính liên tục của ánh xạ dưới vi phân và một số phép tính với dưới vi phân. Mục cuối của chương sẽ giới thiệu về dưới vi phân xấp xỉ và một số tính chất của nó. 2.1 Đạo hàm theo phương Cho một hàm n-biến f : Rn −→ R∪{+∞}. Khi cố định một phương và xét hàm nhiều biến trên phương đó , thì ta có một hàm một biến. Giả sử y 6= 0 là một phương cho trước xuất phát từ điểm x0. Khi đó mọi điểm x thuộc đường thẳng đi qua x0 và có phương y đều có dạng x = x0 + λy với λ ∈ R. Nếu đặt ξ(λ) = f(x0 + λy) thì ξ lồi trên R khi và chỉ khi f lồi trên Rn. Định nghĩa 2.1. Cho f : Rn −→ R ∪ {+∞} và x0 ∈ Rn sao cho f(x0) < +∞. Nếu với một véc-tơ y ∈ Rn mà giới hạn lim λ→0 f(x0+λy)−f(x0) λ tồn tại (hữu hạn hay vô hạn) thì ta nói f có đạo hàm theo phương y tại điểm x0. Ta sẽ ký hiệu giới hạn này là f ′(x0, y). 18 19 Ví dụ 2.1. Giả sử f được cho như sau: f(x) =  0 nếu x < 0, 1 nếu x = 0, +∞ nếu x > 0. Ta có dom f = (−∞; 0]⇒ dom f 6= ∅ , f(x) > −∞,∀x . Vậy f là hàm chính thường . Ta có: f ′(0,−1) = lim λ→0 f(0+λ(−1))−f(0) λ = limλ→0 0−1 λ = −∞, f ′(0, 0) = lim λ→0 f(0+λ0)−f(0) λ = limλ→0 1−1 λ = 0, f ′(0, 1) = lim λ→0 f(0+λ1)−f(0) λ = limλ→0 ∞−1 λ = +∞. Suy ra f ′(0, .) không là hàm chính thường. Mệnh đề 2.1. Cho f : Rn −→ R ∪ {+∞} lồi. Khi đó với mọi x ∈ dom f và mọi y ∈ Rn ta có: i) ϕ là hàm đơn điệu không giảm trên (0; +∞) , trong đó ϕ(λ) := f(x+ λy)− f(x) λ , và do đó f ′(x, y) tồn tại với mọi y ∈ Rn và f ′(x, y) := infλ>0 f(x+ λy)− f(x) λ . ii) Hàm f ′(x, .) thuần nhất dương bậc 1. Ngoài ra nếu f ′(x, .) > −∞ thì hàm f ′(x, .) là dưới tuyến tính trên Rn (do đó nó là hàm lồi chính thường trên Rn). iii) −f ′(x,−y) 6 f ′(x, y) ∀y ∈ Rn. iv) Hàm f ′(x, .) nhận giá trị hữu hạn trên F khi và chỉ khi x ∈ ri(dom f), trong đó F là không gian con của dom f . Chứng minh. i) Ta chứng minh hàm ϕ đơn điệu không giảm trên miền (0; +∞). 20 Định nghĩa hàm h : R −→ R ∪ {+∞} xác định bởi h(λ) = f(x+ λ.y)− f(x). Khi đó h(0) = 0. Giả sử 0 < λ′ 6 λ, do f là hàm lồi nên h là hàm lồi , không nhận giá trị −∞. Ta có h(λ′) = h[ λ′ λ λ+ (1− λ ′ λ )0] 6 λ ′ λ h(λ) + (1− λ ′ λ )h(0) = λ′ λ h(λ). Do ϕ(λ) = f(x+λy)−f(x)λ = h(λ) λ nên ϕ(λ ′) 6 ϕ(λ). Vậy ϕ là hàm không giảm trên miền (0; +∞). Suy ra f ′(x, y) = lim λ→0 ϕ(λ) tồn tại và lim λ→0 ϕ(λ) = infλ>0 ϕ(λ) = infλ>0 f(x+ λ.y)− f(x) λ . ii) Theo định nghĩa, ta có f ′(x, 0) = lim λ→0 f(x+ λ0)− f(x) λ = 0. Chứng minh tính thuần nhất dương . Với t > 0, ta viết f ′(x, ty) = lim λ→0 f(x+ λty)− f(x) λ . Đặt λ′ = λt, ta có tiếp f ′(x, ty) = t lim λ→0 f(x+ λ′y)− f(x) λ′ = tf ′(x, y). Vậy f ′(x, .) thuần nhất dương. Chứng minh tính dưới tuyến tính. 21 Giả sử f ′(x, .) > −∞, với mọi u và v ta có: f ′(x, u+ v) = infλ>0 f [x+ λ2(u+ v)]− f(x) λ 2 (theo i) = infλ>0 f [(x2 + λ 2u) + ( x 2 + λ 2v)]− 12f(x)− 12f(x) λ 2 . Do f là hàm lồi không nhận giá trị −∞ ,nên f [( x 2 + λ 2 u) + ( x 2 + λ 2 v)]− 1 2 f(x)− 1 2 f(x) 6 1 2 [f(x+ λu)− f(x)] + 1 2 [f(x+ λv)− f(x)]. Do đó f ′(x, u+ v) 6 infλ>0 f(x+ λu) λ + infλ>0 f(x+ λv) λ = f ′(x, u) + f ′(x, v). (f ′(x, u) + f ′(x, v) có nghĩa vì f ′(x, .) > −∞). Vậy f ′(x, .) là hàm dưới cộng tính. Suy ra f ′(x, .) là hàm dưới tuyến tính trên Rn. Vì f ′(x, .) > −∞, f ′(x, 0) = 0 và f ′(x, .) là dưới tuyến tính trên Rn, nên nó là hàm lồi, chính thường trên toàn không gian. iii) Do f ′(x, 0) = 0 và theo tính chất dưới cộng tính, ta có: 0 = f ′(x, 0) = f ′(x, y − y) 6 f ′(x, y) + f ′(x,−y) ∀y ∈ Rn. Suy ra −f ′(x,−y) 6 f ′(x, y) với mọi y ∈ Rn. iv) Giả sử x ∈ ri(dom f) . Ta cần chứng tỏ f ′(x, .) hữu hạn trên F . Từ iii) suy ra f ′(x, .) > −∞. Vậy cần chỉ ra f ′(x, y) < +∞ với mọi y ∈ F . Do x ∈ ri(dom f), nên ∀y ∈ F , x+ λ.y ∈ dom f ∀λ > 0 đủ nhỏ. Do đó f ′(x, y) = infλ>0 f(x+λ.y)−f(x) λ < +∞. Ngược lại, giả sử f ′(x, y) hữu hạn với mọi y ∈ F . Ta cần chứng tỏ x ∈ ri(dom f). 22 Thật vậy, nếu trái lại sẽ tồn tại y ∈ F và một dãy {λk} các số dương hội tụ đến 0 và x+ λk.y 6∈ dom f với mọi k đủ lớn. Trong trường hợp này f(x+ λk.y)− f(x) = +∞ với mọi k đủ lớn. Do đó f ′(x, y) = +∞. Mâu thuẫn với giả thiết. Vậy x ∈ ri(dom f). 2.2 Dưới vi phân và các tính chất 2.2.1 Dưới vi phân Định nghĩa 2.2. Cho f : Rn −→ R ∪ {+∞}. Ta nói x∗ ∈ Rn là dưới đạo hàm của f tại x nếu 〈x∗, z − x〉+ f(x) 6 f(z) ∀z. Kí hiệu tập hợp tất cả các dưới đạo hàm của f tại x là ∂f(x). Vậy ∂f(x) là một tập (có thể bằng ∅) trong Rn. Khi ∂f(x) 6= ∅, thì ta nói hàm f khả dưới vi phân tại x. Theo định nghĩa, một điểm x∗ ∈ ∂f(x) khi và chỉ khi nó thoả mãn một hệ vô hạn các bất đẳng thức tuyến tính . Như vậy ∂f(x) là giao của các nửa không gian đóng. Vậy ∂f(x) luôn là một tập lồi đóng (có thể rỗng). Kí hiệu dom(∂f) := {x|∂f(x) 6= ∅}. Ví dụ 2.2. 1) Hàm chuẩn f(x) = ‖x‖, x ∈ Rn. Tại điểm x = 0, ta có ∂f(0) = {x∗|〈x∗, x〉 6 ‖x‖,∀x}. Vậy hàm f(x) khả dưới vi phân. Lại có lim x→0 f(x)− f(0)− 〈x∗, x− 0〉 ‖x− 0‖ = limx→0 ‖x‖ − 〈x∗, x〉 ‖x‖ = 1 6= 0. Vậy hàm f(x) không khả vi tại x = 0. 23 2) Hàm chỉ f(x) = δC(x) := { 0 nếu x ∈ C, +∞ nếu x 6∈ C. Trong đó C là một tập lồi khác ∅. Khi đó với x0 ∈ C, ta có ∂f(x0) = ∂δC(x 0) = {x∗|〈x∗, x− x0〉 6 δC(x),∀x}. Với x 6∈ C thì δC(x) = +∞, nên bất đẳng thức này luôn đúng. Vậy ∂f(x0) = ∂δC(x 0) = {x∗|〈x∗, x− x0〉 6 0,∀x ∈ C} = NC(x0). Vậy dưới vi phân của hàm chỉ của một tập lồi C khác ∅ tại một điểm x0 ∈ C chính là nón pháp tuyến ngoài của C tại x0. Mệnh đề 2.2. i) x∗ ∈ ∂f(x) khi và chỉ khi f ′(x, y) > 〈x∗, y〉 ,∀y. 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). Chứng minh. i) Theo định nghĩa x∗ ∈ ∂f(x)⇔ 〈x∗, z − x〉+ f(x) 6 f(z) ∀z. Với bất kì y, lấy z = x+ λ.y, λ > 0, ta có 〈x∗, λ.y〉+ f(x) 6 f(x+ λ.y). Từ đây suy ra 〈x∗, y〉 6 f(x+ λ.y)− f(x) λ ∀λ > 0. (2.1) Theo định nghĩa của f ′(x, y), suy ra ngay 〈x∗, y〉 6 f ′(x, y) ∀y. Ngược lại, giả sử (2.1) thoả mãn. Lấy z bất kì và áp dụng (2.1) với y = z − x và λ = 1, ta có 〈x∗, z − x〉 6 f(z)− f(x) ∀z. Vậy x∗ ∈ ∂f(x). ii) Cho x ∈ dom(∂f), thì ∂f(x) 6= ∅, tức là tồn tại x∗ ∈ ∂f(x). 24 Theo định nghĩa của f , ta có epi f = epi f . Mặt khác, ta lại có epi f ⊂ epi f , suy ra epi f ⊂ epi f . Vậy f(x) > f(x). (2.2) Theo giả thiết f là hàm lồi chính thường trên Rn, nên f là hàm lồi đóng trên Rn, theo hệ quả 1.1, ta có f(x) = f ∗∗(x). (2.3) Theo tính chất của hàm liên hợp thứ 2, ta có f ∗∗(x) >< 〈x∗, x〉 − f ∗(x∗) = f(x). (2.4) Từ (2.2),(2.3) và (2.4) ta có f(x) = f(x). Ta lấy y∗ ∈ ∂f(x) thì ∀z tacó 〈y∗, z − x〉+ f(x) 6 f(z). Mặt khác f(z) > f(z) > 〈y∗, z − x〉+ f(x) = 〈y∗, z − x〉+ f(x). Suy ra y∗ ∈ ∂f(x). Vậy ∂f(x) ⊂ ∂f(x). (2.5) Ngược lại, lấy z0 ∈ ri(dom f). Với mọi z ta có f(z) = f(z) = lim t→0 f [(1− t).z + t.z0]. Vậy theo định nghĩa của dưới vi phân ta có : x∗ ∈ ∂f(x)⇔ 〈x∗, (1− t).z + t.z0 − x〉+ f(x) 6 f [(1− t).z + t.z0]. Cho t→ 0 ta được : 〈x∗, z − x〉+ f(x) 6 f(z). 25 Hay 〈x∗, z − x〉+ f(x) 6 f(z) Chứng tỏ x∗ ∈ ∂f(x). Vậy ∂f(x) ⊂ ∂f(x). (2.6) Từ (2.5) và (2.6) ta có ∂f(x) = ∂f(x). Mệnh đề 2.3. Cho f : Rn −→ R ∪ {+∞} lồi, khi đó : i) Nếu x 6∈ dom f , thì ∂f(x) = ∅. ii) x ∈ ri(dom f) khi và chỉ khi ∂f(x) 6= ∅ và compắc. Chứng minh. i) Cho z ∈ dom f , thì f(z) < +∞. Vậy nếu x 6∈ dom f thì f(x) = +∞ và do đó không thể tồn tại x∗ tho mãn 〈x∗, z − x〉+ f(x) 6 f(z) < +∞. Vậy ∂f(x) = ∅. ii) Giả sử x ∈ ri(dom f). Ta có điểm (x, f(x)) nằm trên biên của epi f . Do f lồi, chính thường, nên tồn tại siêu phẳng tựa của epi f đi qua (x, f(x)). Tức là tồn tại p ∈ Rn, t ∈ R không đồng thời bằng 0 sao cho 〈p, x〉+ t.f(x) 6 〈p, y〉+ t.à , ∀(y, à) ∈ epi f. (2.7) Ta có t 6= 0, vì nếu t = 0 thì 〈p, x〉 6 〈p, y〉 ,∀y ∈ dom f . Hay 〈p, x− y〉 6 0 ,∀y ∈ dom f . Nhưng do x ∈ ri(dom f), nên điều này kéo theo p = 0. Mâu thuẫn với p, t không đồng thời bằng 0. Vậy t 6= 0. Hơn nữa t > 0, vì nếu t < 0 thì trong bất đẳng thức (2.7), khi cho à→∞ ta suy ra mâu thuẫn vì vế trái cố định. Chia hai vế của (2.7) cho t > 0, ta được: 〈p t , x〉+ f(x) 6 〈p t , y〉+ à ∀y ∈ dom f. 26 Thay à = f(y), ta được 〈p t , x〉+ f(x) 6 〈p t , y〉+ f(y) ∀y ∈ dom f. Đặt x∗ = −pt , ta được −〈x∗, x〉+ f(x) 6 −〈x∗, y〉+ f(y) ∀y ∈ dom f. Hay 〈x∗, y − x〉+ f(x) 6 f(y) ∀y ∈ dom f. Nếu y 6∈ dom f thì f(y) =∞, do đó 〈x∗, y − x〉+ f(x) 6 f(y) ∀y. Chứng tỏ x∗ ∈ ∂f(x). Vậy ∂f(x) 6= ∅ . Bây giờ ta chỉ ra tập ∂f(x) compắc. Do x ∈ ri(dom f), theo mệnh đề (2.2) x∗ ∈ ∂f(x)⇐⇒ f ′(x, d) > 〈x∗, d〉 ∀d. (2.8) Gọi F là không gian tuyến tính của dom f . Lấy ei là véc-tơ đơn vị thứ i (i=1,...,n) của Rn (toạ độ thứ i của ei bằng 1 và mọi toạ độ khác là 0). Không giảm tổng quát, ta giả sử rằng các véc-tơ đơn vị e1, ...ek ∈ F , áp dụng (2.8) lần lượt với d = ei với i=1,...k, ta có x∗i 6 f ′(x, ei). Tương tự , áp dụng với d = −ei với i=1,...k, ta có −x∗i 6 f ′(x,−ei). Hay x∗i > −f ′(x,−ei). Tóm lại −f ′(x,−ei) 6 x∗i 6 f ′(x, ei) ,với mọi i=1,...k. Theo (iv) mệnh đề (2.1), do x ∈ ri(dom f) và F là không gian con của dom f , nên f ′(x, y) hữu hạn với mọi y ∈ F . Nói riêng f ′(x,−ei) và f ′(x, ei) hữu hạn với mọi i=1,...k. Vậy ∂f(x) bị chặn , và do tính đóng nên nó là compắc. Ngược lại, giả sử rằng ∂f(x) 6= ∅ và ∂f(x) compắc. Ta chỉ ra rằng x ∈ ri(dom f). Do ∂f(x) 6= ∅ nên x ∈ dom f . Nếu trái lại x 6∈ ri(dom f), thì x ở trên biên tương đối của dom f . 27 Do dom f lồi, theo mệnh đề về siêu phẳng tựa, tồn tại một siêu phẳng tựa của dom f tại x, tức là tồn tại vectơ p ∈ Rn, p 6= 0 sao cho 〈p, x〉 > 〈p, z〉 ∀z ∈ dom f. Lấy x∗ ∈ ∂f(x). Từ đây và theo định nghĩa dưới vi phân ta có: f(z)− f(x) > 〈x∗, z − x〉 > 〈x∗, z − x〉+ λ.〈p, z − x〉 = 〈x∗ + λ.p, z − x〉 ∀λ > 0,∀z. Chứng tỏ x∗ + λ.p ∈ ∂f(x) ∀λ > 0. Điều này mâu thuẫn với tính bị chặn của ∂f(x). Vậy x ∈ ri(dom f). Ví dụ 2.3. Cho hàm một biến f(x) = { −2x 12 nếu x > 0, +∞ nếu x < 0. Ta có dom f = [0; +∞) , 0 6∈ int(dom f). x∗ ∈ ∂f(0)⇔ 〈x∗, x〉+ f(0) 6 f(x) ,∀x ⇔ x∗.x 6 −2x 12 ,∀x > 0. (2.9) Nếu x∗ < 0 , ta chọn x = 0.01 thì (2.9) không thoả mãn. Nếu x∗ 6 0 thì (2.9) không thoả mãn. Vậy ∂f(0) = ∅. Ví dụ trên cho thấy nếu x 6∈ int(dom f) thì tập ∂f(x) có thể bằng rỗng. Mệnh đề 2.4. Cho f : Rn −→ R ∪ {+∞} và x ∈ dom f . Khi đó i) Nếu x ∈ ri(dom f), thì f ′(x, y) = maxx∗∈∂f(x) 〈x∗, y〉 ,∀y. ii) Với mọi tập bị chặn C ⊂ int(dom f), tập ∪x∈C∂f(x) bị chặn . iii) Nếu có thêm f đóng, thì f ∗(x∗) + f(x) = 〈x∗, x〉 ⇐⇒ x∗ ∈ ∂f(x), x ∈ ∂f(x∗). 28 Chứng minh. i) Do f ′(x, .) là hàm lồi, thuần nhất dương, nên mọi hàm non a-phin của f ′(x, .) đều tuyến tính, tức là có dạng 〈p, .〉. Vậy nếu 〈p, .〉 là hàm non a-phin của f ′(x, .) trên Rn, thì 〈p, y〉 6 f ′(x, y) ,∀y. Theo mệnh đề 2.2 ta có p ∈ ∂f(x). Hơn nữa, do f ′(x, .) là một hàm lồi đóng, nên theo định lý xấp xỉ tập lồi nó là bao trên của các hàm non a-phin của nó. Vậy f ′(x, y) = Supp∈∂f(x) 〈p, y〉. ii) Giả sử C ⊆ int(dom f). Đặt ξ = Supx∗∈∂f(C) ‖x∗‖ = Supx∈C Supx∗∈∂f(C) ‖x∗‖ (2.10) Xét ánh xạ tuyến tính 〈x∗, z〉. Chuẩn của ánh xạ tuyến tính này là ‖x∗‖ = Sup‖z‖=1 〈x∗, z〉. Thay vào (2.10) ta có : ξ = Supx∈C Supx∗∈∂f(C) Sup‖z‖=1 〈x∗, z〉. Do f ′(x, z) = Supx∗∈∂f(x) 〈x∗, z〉 nên ta có tiếp ξ = Sup‖z‖=1 Supx∈C f ′(x, z). Đặt g(z) = Supx∈C f ′(x, z). Do x ∈ C ⊆ int(dom f), nên hàm f ′(x, .) lồi trên Rn ( do đó liên tục ). Suy ra hàm g liên tục vì là bao trên của một họ hàm lồi liên tục trên Rn. Vậy ξ = Sup‖z‖=1 g(z) = max‖z‖=1 g(z) < +∞. Chứng tỏ ∂f(C) bị chặn. 29 iii) Theo định nghĩa hàm liên hợp, ta có f ∗(x∗) = Supx {〈x∗, x〉 − f(x)}. Điều này tương đương với f ∗(x∗) > 〈x∗, y〉 − f(y) ,∀y. Do đó f ∗(x∗) + f(x) = 〈x∗, x〉 ⇔ 〈x∗, y〉 − f(y) + f(x) 6 〈x∗, x〉 ,∀y. Hay 〈x∗, y − x〉+ f(x) 6 f(y) ,∀y. Vậy x∗ ∈ ∂f(x). Do f đóng, nên theo hệ quả 1.1, ta có f = f ∗∗. Theo định nghĩa của hàm liên hợp, ta có: f ∗∗ = Supx∗ {〈x, x∗〉 − f ∗(x∗)}. Điều này tương đương với f ∗∗(x) > 〈x, y〉 − f ∗(y) ,∀y. Hay f(x) > 〈x, y〉 − f ∗(y) ,∀y. Do đó f ∗(x∗) + f(x) = 〈x∗, x〉 ⇔ 〈x, y〉 − f ∗(y) + f ∗(x∗) 6 〈x∗, x〉 ,∀y. Hay 〈x, y − x∗〉+ f ∗(x∗) 6 f ∗(y) ,∀y. Vậy x ∈ ∂f ∗(x∗). 30 2.2.2 Tính khả vi của hàm lồi Định nghĩa 2.3. Cho một hàm f xác định trên một lân cận của x ∈ Rn. Hàm f được gọi là khả vi tại x, nếu tồn tại x∗ sao cho lim z→x f(z)− f(x)− 〈x∗, z − x〉 ‖z − x‖ = 0. Một điểm x∗ như thế nếu tồn tại sẽ duy nhất và được gọi là đạo hàm của f tại x. Thông thường đạo hàm này được kí hiệu là Of(x) hoặc f ′(x). Giả sử f : Rn −→ R ∪ {+∞} lồi, chính thường và x ∈ dom f . Nếu f khả vi tại x, thì với mọi y 6= 0, ta có: lim λ→0 f(x+ λ.y)− f(x)− 〈Of(x), λ.y〉 λ.‖y‖ = 0. Hay là f ′(x, y)− 〈Of(x), y〉 ‖y‖ = 0. Suy ra f ′(x, y) = 〈Of(x), y〉 ,∀y. Lấy y = ei (i=1,...,n) là véc-tơ đơn vị thứ i của Rn, ta có : 〈Of(x), ei〉 = ( ∂f ∂xi )(x)(i = 1, .., n). Vậy f ′(x, y) = n∑ i=1 yi( ∂f ∂xi )(x). Từ đây ta có mệnh đề sau: Mệnh đề 2.5. Giả sử f : Rn −→ R ∪ {+∞} lồi, chính thường và x ∈ dom f . Khi đó f khả vi tại x khi và chỉ khi tồn tại x∗ ∈ Rn sao cho f ′(x, y) = 〈x∗, y〉 ,∀y. Ngoài ra x ∈ int(dom f) và Of(x) = x∗. Chứng minh. Nếu f khả vi tại x thì như ở trên, ta đã chỉ ra rằng f ′(x, y) = 〈Of(x), y〉 ,∀y. 31 Vậy f ′(x, y) hữu hạn trên toàn Rn, nên x ∈ int(dom f). Ngược lại f ′(x, y) = 〈Of(x), y〉 ,∀y. Trước hết ta có x ∈ int(dom f) vì f ′(x, .) hữu hạn trên toàn Rn. Để chứng minh tính khả vi của f tại x, ta lấy g(y) := f(x+ y)− f(x)− 〈x∗, y〉. Do f lồi, chính thường và f hữu hạn, nên g cũng là một hàm lồi, chính thường trên Rn. Ta cần chứng tỏ lim y→0 g(y) ‖y‖ = 0. Trước hết từ f ′(x, y) = 〈x∗, y〉, theo định nghĩa của f ′(x, y), ta có g(y) > 0 ,∀y và g(0) = 0. Nếu y 6= 0 thì véc-tơ y‖y‖ thuộc siêu hộp H := [−1, 1]n. Vậy theo định lý Krein-Milman điểm y ‖y‖ biểu diễn được bởi một tổ hợp lồi của các đỉnh của H, tức là tồn tại các số thực βi (phụ thuộc y) sao cho βi > 0, ∑ i∈I βi = 1 và y ‖y‖ = ∑ i∈I βiv i, trong đó vi(i ∈ I) là các đỉnh của H. Ta có g(y) := g(‖y‖ y‖y‖) = g(‖y‖ ∑ i∈I βiv i) = g( ∑ i∈I βi‖y‖vi). Theo tính lồi của g thì g( ∑ i∈I βi‖y‖vi) 6 ∑ i∈I βig(‖y‖vi). Tóm lại 0 6 g(y)‖y‖ 6 ∑ i∈I βi g(‖y‖vi) ‖y‖ . Theo định nghĩa của g ta lại có g(‖y‖vi) ‖y‖ → 0 khi y → 0. Vậy g(y) ‖y‖ → 0. Chứng tỏ f khả vi tại x và do đó Of(x) = x∗. 32 Mệnh đề 2.6. Cho f : Rn −→ R ∪ {+∞} khả vi và C ⊂ Rn. Ba điều kiện sau tương đương. a) η là hệ số lồi của f trên C. b) f(y) > f(x) + 〈f ′(x), y − x〉+ η2‖x− y‖2 ∀x, y ∈ C c)〈f ′(y)− f ′(x), y − x〉 > η‖x− y‖2 ∀x, y ∈ C Chứng minh. (a)→ (b): Do η là hệ số lồi của trên C, nên với t ∈ (0; 1) và mọi x,y thuộc C ta có: f [t.y + (1− t)x] 6 tf(y) + (1− t)f(x)− η 2 t(1− t)‖x− y‖2. Suy ra f(y)− f(x) > f [ty + (1− t)x]− f(x) + η 2t(1− t)‖x− y‖2 t = f [x+ t(y − x)]− f(x) t + η 2 (1− t)‖x− y‖2. Cho t→ 0, do f khả vi, ta được: f(y)− f(x) > f ′(x, y − x) + η 2 ‖x− y‖2. (b)→(a): Cho t ∈ (0; 1) và ω = (1− t)x+ ty. Khi đó y = ω + (1− t)(y − x), x = ω + (−t)(y − x). Ap dụng (b), ta được: f(y) > f(ω) + 〈f ′(ω), y − ω〉+ η 2 ‖ω − y‖2, f(x) > f(ω) + 〈f ′(ω), x− ω〉+ η 2 ‖ω − x‖2. Hay f(y) > f(ω) + 〈f ′(ω), (1− t)(y − x)〉+ η 2 (1− t)2‖y − x‖2, f(x) > f(ω) + 〈f ′(ω), (−t)(y − x)〉+ η 2 t2‖y − x‖2. 33 Nhân bất đẳng thức trên với t > 0 và bất đẳng thức dưới với 1− t > 0 ta được : tf(y) > tf(ω) + 〈f ′(ω), t(1− t)(y − x)〉 + η 2 t(1− t)2‖y − x‖2, (1− t)f(x) > (1− t)f(ω) + 〈f ′(ω),−t(1− t)(y − x)〉 + η 2 t2(1− t)‖y − x‖2. Cộng hai bất đẳng thức trên và chuyển vế, ta có: tf(y) + (1− t)f(x) > f(ω) + η 2 t(1− t)‖y − x‖2. Hay f [(1− t)x+ ty] 6 (1− t)f(x) + tf(y)− η 2 t(1− t)‖y − x‖2. Chứng tỏ η là hệ số lồi của f trên C. (b)→(c): Do (b), nên ∀x, y ∈ C, ta có: f(y)− f(x) > 〈f ′(x), y − x〉+ η 2 ‖x− y‖2, f(x)− f(y) > 〈f ′(y), x− y〉+ η 2 ‖x− y‖2. Cộng hai bất đẳng thức lại ta được: 0 > 〈f ′(x)− f ′(y), y − x〉+ η‖x− y‖2. Hay 〈f ′(y)− f ′(x), y − x〉 > η‖x− y‖2. (c)→(b): Đặt γ(t) = f [(1− t)x+ ty] = f [x+ t(y − x)]. Khi đó γ′(t) = 〈f ′[x+ t(y − x)], y − x〉, 34 và f(y)− f(x) = γ(1)− γ(0) = ∫ 1 0 γ′(t)dt. Bây giờ giả sử có (c). Với x, y ∈ C, đặt h := y − x. Khi đó f(y)− f(x) = ∫ 1 0 γ′(t)dt = ∫ 1 0 〈f ′[x+ t(y − x)], y − x〉dt = ∫ 1 0 f ′(x+ th).hdt = ∫ 1 0 [f ′(x) + f ′(x+ th)− f ′(x)]hdt = ∫ 1 0 (f ′(x)h+ [f ′(x+ th)− f ′(x)]h)dt = f ′(x)ht|10 + ∫ 1 0 [f ′(x+ th)− f ′(x)]hdt = f ′(x)h+ ∫ 1 0 [f ′(x+ th)− f ′(x)]hdt. Theo (c) ta có : 〈f ′(x+ th)− f ′(x), th〉 > η‖th‖2, hay [f ′(x+ th)− f ′(x)]h > ηt‖h‖2. Suy ra ∫ 1 0 [f ′(x+ th)− f ′(x)]hdt > ∫ 1 0 ηt‖h‖2dt = η t2 2 ‖h‖2|10 = η 2 ‖h‖2. Vậy f(y)− f(x) > f ′(x)h+ η 2 ‖h‖2, 35 hay f(y)− f(x) > 〈f ′(x), y − x〉+ η 2 ‖y − x‖2. 2.2.3 Tính đơn điệu của dưới vi phân Cho T là một toán tử đa trị trên Rn, tức là với mỗi x ∈ Rn, thì T (x) là một tập (có thể bằng rỗng). Như thường lệ ta ký hiệu tập hợp tất cả các tập con của Rn là 2R n . Kí hiệu miền xác định của T là domT := {x ∈ Rn | T (x) 6= ∅}, và đồ thị của T là G(T ) := {(x, y) ∈ Rn ìRn | y ∈ T (x)}. Định nghĩa 2.4. Cho T : Rn −→ 2Rn và C ⊆ domT . Ta nói T là đơn điệu tuần hoàn trên C, nếu với mọi số nguyên dương m và mọi cặp (xi, yi) ∈ G(T ), xi ∈ C (i=0,...,m) ta có: 〈x1 − x0, y0〉+ 〈x2 − x1, y1〉+ ...+ 〈x0 − xm, ym〉 6 0. (2.11) Nếu (2.11) chỉ đúng với m = 1, thì ta nói T đơn điệu trên C, tức là 〈y − y′, x− x′〉 > 0 ,∀x, x′ ∈ C , ∀y ∈ T (x) ,∀y′ ∈ T (x′). Nếu T đơn điệu (hoặc đơn điệu tuần hoàn) trên toàn domT , thì ta nói ngắn gọn là T đơn điệu (đơn điệu tuần hoàn). Nếu T ≡ ∂f thì T đơn điệu tuần hoàn trên dom(∂f). Thật vậy: ∀m ∈ N ,∀(xi, yi) ∈ G(∂f) , xi ∈ dom(∂f) (i = 0, ...n) ta có: G(∂f) = {(xi, yi) | yi ∈ ∂f(xi)}. 36 Suy ra 〈y0, x1 − x0〉+ f(x0) 6 f(x1) 〈y1, x2 − x1〉+ f(x1) 6 f(x2) ... ... ... 〈ym, x0 − xm〉+ f(xm) 6 f(x0). Cộng vế với vế của các bất đẳng thức trên, ta được: 〈y0, x1 − x0〉+ 〈y1, x2 − x1〉+ ...+ 〈ym, x0 − xm〉 6 0. Theo định nghĩa, T ≡ ∂f đơn điệu tuần hoàn trên dom(∂f). Một câu hỏi được đặt ra là điều ngược lại có đúng không? Trả lời câu hỏi này ta có mệnh đề sau: Mệnh đề 2.7. Giả sử S là một toán tử đa trị từ Rn −→ 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 là toán tử S đơn điệu tuần hoàn. Chứng minh. Điều kiện cần: Nếu tồn tại một hàm f lồi, đóng, chính thường trên Rn sao cho S(x) ⊆ ∂f(x) ,∀x thì S là toán tử đơn điệu tuần hoàn. ∀m ∈ N ,∀(xi, yi) ∈ G(S), xi ∈ domS(i = 0, ...m). Từ (xi, yi) ∈ G(S) ⇒ yi ∈ S(xi) ⊆ ∂f(xi), (∀i = 0, ..m), do ∂f là đơn điệu tuần hoàn trên dom(∂f) nên 〈y0, x1 − x0〉+ 〈y1, x2 − x1〉+ ...+ 〈ym, x0 − xm〉 6 0. Suy ra S là đơn điệu tuần hoàn trên domS. Điều kiện đủ: Nếu S là toán tử đơn điệu tuần hoàn thì tồn tại một hàm f lồi, đóng, chính thường trên Rn sao cho S(x) ⊆ ∂f(x) ,∀x Giả sử (x0, y0) ∈ G(S), định nghĩa hàm f bằng cách lấy f(x) := Sup{〈x− xm, ym〉+ ...+ 〈x1 − x0, y0〉}, 37 trong đó cận trên đúng được lấy trên tất cả các cặp (xi, yi) ∈ G(S) và các số nguyên dương m. Ta chứng minh: f lồi, đóng, chính thường và S(x) ⊆ ∂f(x) ,∀x. Do f là bao trên của một họ các hàm a-phin, nên f là một hàm lồi đóng. Do tính đơn điệu tuần hoàn của S, nên f(x0) := Sup{〈xo−xm, ym〉+〈xm−xm−1, ym−1〉+ ...+〈x1−x0, y0〉} := 0, suy ra dom f 6= ∅. Vậy f là chính thường. Với bất kì cặp (x, x∗) ∈ G(S), ta có x∗ ∈ S(x), ta sẽ chứng minh x∗ ∈ ∂f(x). Muốn thế ta sẽ chứng minh rằng ∀α < f(x) và y ∈ Rn , ta có α + 〈x∗, y − x〉 < f(y). Thật vậy, do α < f(x), nên theo tính chất của cận trên đúng, sẽ tồn tại các cặp (xi, yi) ∈ G(S) và số nguyên dương m (i=1,...m) thỏa mãn α < 〈x− xm, ym〉+ 〈xm − xm−1, ym−1〉+ ...+ 〈x1 − x0, y0〉. Theo định nghĩa của f(y), ta được: f(y) > 〈y − xm, ym〉+ ...+ 〈x1 − x0, y0〉 = 〈y − xm+1, ym〉+ 〈xm+1 − xm, ym〉+ ...+ 〈x1 − x0, y0〉. Thay xm+1 = x , ym = x∗, ta có f(y) > 〈y − x, x∗〉+ 〈x− xm, ym〉+ 〈xm − xm−1, ym−1〉 + ...+ 〈x1 − x0, y0〉 > 〈y − x, x∗〉+ α. Điều này đúng với mọi (x, x∗) ∈ G(S) nên S(x) ⊂ ∂f(x) ,∀x. Định nghĩa 2.5. Ta nói một toán tử T : Rn −→ 2Rn là đơn điệu cực đại nếu nó là đơn điệu và đồ thị của nó không phải là tập con thực sự của đồ thị của một toán tử đơn điệu nào khác. Toán tử T được gọi là đơn điệu tuần hoàn cực đại, nếu nó là đơn điệu tuần hoàn và đồ thị của nó không phải là tập con thực sự của đồ thị của một toán tử đơn điệu tuần hoàn nào khác. 38 Ví dụ 2.4. (Toán tử đơn điệu) Xét NC(x) := {ω | 〈ω, y − x〉 6 0 , ∀y ∈ C}. Ta chứng tỏ rằng nón pháp tuyến có tính chất đơn điệu theo nghĩa 〈ω − ω′, x− x′〉 > 0 ∀x, x′ ∈ C , ∀ω ∈ NC(x) , ∀ω′ ∈ NC(x′). Thật vậy: ∀x, x′ ∈ C ta có: + ω ∈ NC(x)⇔ 〈ω, y − x〉 6 0 ∀y ∈ C. Với y = x′, ta có 〈ω, x′ − x〉 6 0. + ω′ ∈ NC(x′)⇔ 〈ω′, y − x′〉 6 0 ∀y ∈ C. Với y = x, ta có 〈ω′, x− x′〉 6 0. ⇒ 〈ω, x′ − x〉+ 〈ω′, x− x′〉 6 0. ⇒ 〈ω − ω′, x− x′〉 > 0. Ví dụ 2.5. (Toán tử đơn điệu) Xét ánh xạ f : R2 −→ R2 x 7−→ f(x) = Qx = (x2,−x1). Với x = (x1, x2), Q = ( 0 1 −1 0 ) . Với mọi x = (x1, x2), y = (y1, y2) ∈ R2 ta có: + x− y = (x1 − y1, x2 − y2). + f(x)− f(y) = (x2 − y2,−x1 + y1). Suy ra 〈f(x)− f(y), x− y〉 = (x2 − y2)(x1 − y1) + (−x1 + y1)(x2 − y2) = 0 ∀x, y ∈ R2. Vậy f là ánh xạ đơn điệu trên R2. Hệ quả 2.1. Mọi toán tử đơn điệu tuần hoàn cực đại trong Rn đều là dưới vi phân của một hàm lồi, đóng, chính thường trên Rn. 39 Chứng minh. Giả sử S là toán tử đơn điệu tuần hoàn cực đại trong Rn. Theo định nghĩa ta có : + S là toán tử đơn điệu tuần hoàn . + G(S) không là tập con thực sự của đồ thị của một toán tử đơn điệu tuần hoàn nào khác. Do S là toán tử đơn điệu tuần hoàn nên theo mệnh đề 2.7, 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. Ta có :∀(x, y) ∈ G(S)⇒ y ∈ S(x) do S(x) ⊆ ∂f(x),∀x nên y ∈ ∂f(x) ⇒ (x, y) ∈ G(∂f). Vậy G(S) ⊂ G(∂f). Do G(S) không là tập con thực sự của đồ thị của một toán tử đơn điệu tuần hoàn nào khác và ∂f là toán tử đơn điệu tuần hoàn nên G(S) = G(∂f). Suy ra S ≡ ∂f . 2.2.4 Tính liên tục của dưới vi phân Định nghĩa 2.6. Một ánh xạ T : Rn −→ 2Rn được gọi là đóng tại x, nếu với mọi dãy xk → x, mọi yk ∈ T (xk) và yk → y thì y ∈ T (x) Định nghĩa 2.7. Một ánh xạ T : Rn −→ 2Rn được gọi là nửa liên tục trên tại x, nếu với mọi tập mở G chứa T(x), tồn tại một lân cận mở U của x sao cho T (z) ⊂ G,∀z ∈ U. Ta nói ánh xạ T là đóng (nửa liên tục trên) trên tập C, nếu nó đóng (nửa liên tục trên) tại mọi điểm thuộc C. Một ánh xạ T được gọi là đóng nếu đồ thị của T là một tập đóng. Nói một cách khái quát, bổ đề dưới đây chỉ ra rằng: Một dãy hàm lồi nếu bị chặn trên bởi một hàm lồi theo từng điểm ở trên một tập lồi, mở, thì sẽ bị chặn trên đều bởi chính hàm lồi đó trên mọi tập compắc thuộc tập mở này. Bổ đề 2.1. Cho một tập lồi, mở G ⊆ Rn và f là một hàm lồi nhận giá trị hữu hạn trên G. Giả sử {fi}i ∈ I là một dãy các hàm lồi hữu hạn trên G và hội tụ theo từng điểm trên G đến f . Giả sử lim sup fi(x) 6 f(x) ,∀x ∈ G. 40 Khi đó với mọi tập compắc K ⊆ G, với mọi  > 0, tồn tại chỉ số i sao cho fi(x) 6 f(x) +  , ∀i > i ,∀x ∈ K. Chứng minh. Với mọi x ∈ G, mọi i ∈ N , định nghĩa gi(x) := max{fi(x), f(x)}. Hàm gi lồi, hữu hạn trên G vì nó là hàm bao trên của hai hàm lồi, hữu hạn trên G. Do G mở, nên gi liên tục trên G. Do K ⊆ G compắc, nên dãy {gi(x)}i ∈ I bị chặn. Không giảm tổng quát, bằng cách qua dãy con, ta có thể coi gi(x)→ l(x) khi i→ +∞. Theo định nghĩa của gi(x) và do lim sup fi(x) 6 f(x) ∀x ∈ K, ta suy ra l(x) = f(x). Vậy dãy gi(x) hội tụ theo từng điểm đến f trên tập compắc K, nên nó hội tụ đều đến f trên K. Nhưng do gi := max{fi(x), f(x)}, nên với mọi tập compắc K ⊆ G, với mọi  > 0,∃i : ∀i > i ta có fi(x) 6 f(x) +  , ∀x ∈ K. Từ mệnh đề sau, suy ra tính nửa liên tục trên của ánh xạ ∂f . Cụ thể là: Mệnh đề 2.8. Cho một tập lồi, mở U ⊆ Rn và f là một hàm lồi nhận giá trị hữu hạn trên U . Giả sử {fi}i ∈ I là một dãy các hàm lồi hữu hạn trên U và hội tụ theo từng điểm trên U đến f . Khi đó, nếu dãy {xi} ⊂ U hội tụ đến x ∈ U , thì với mọi  > 0, tồn tại chỉ số i sao cho ∂fi(x i) ⊂ ∂f(x) + .B(0, 1) ,∀i > i, trong đó B(0, 1) là hình cầu đơn vị đóng tâm ở O 41 Chứng minh. Cho α > 0 , y ∈ Rn. Với mỗi x ∈ U đặt à := f ′(x, y) + α. Do f lồi, hữu hạn trên tập U mở và x ∈ U , nên x ∈ int(dom f), do đó à hữu hạn. Do x ∈ int(dom f), nên với mọi y, tồn tại δ > 0 sao cho x+ λ.y ∈ int(dom f) với mọi 0 < λ < δ. Do α > 0 và định nghĩa của f ′(x, y), ta có : f(x+ λ.y)− f(x) λ < à ,∀λ ∈ (0, δ). (2.12) Do fi(x+ λ.y)→ f(x+ λ.y) và fi(xi)→ f(x), nên từ (2.12), tồn tại i1 sao cho fi(x i + λ.y)− fi(xi) λ i1 ,∀λ ∈ (0, δ). Do f ′i(x i, y) 6 fi(x i + λ.y)− fi(xi) λ nên f ′i(x i, y) 6 à với mọi i > i1. Vậy lim sup f ′i(x i, y) 6 à = f ′(x, y) + α. Do điều này đúng với mọi α > 0, ta suy ra lim sup f ′i(x i, y) < f ′(x, y). Vì f ′i(x i, .) và f ′(x, .) lồi, hữu hạn trên U ( do x ∈ U ⊂ int(dom f)) nên áp dụng bổ đề 2.1 cho các hàm lồi f ′i(x i, .) và f ′(x, .) với G = Rn, K = B(0, 1) ta có : Với mọi tập compắc B(0, 1) ⊆ Rn ,∀ > 0 ,∃i sao cho ∀i > i ta có f ′i(x i, y) 6 f ′(x, y) +  , ∀y ∈ B(0, 1). Từ đây, với mọi y 6= 0, theo tính chất thuần nhất dương của f ′(x, .), ta có: 1 ‖y‖f ′ i(x i, y) = f ′i(x i, y ‖y‖) 6 f ′(x, y ‖y‖) + . 42 Hay f ′i(x i, y) 6 f ′(x, y) + .‖y‖ ,∀i > i ,∀y. Do f ′i(x i, y) là hàm tựa của ∂fi(x i) và f ′(x, y) là hàm tựa của ∂f(x) nên từ đây suy ra ∂fi(x i) ⊆ ∂f(x) + .B(0, 1). Mệnh đề 2.9. Cho f là một hàm lồi chính thường trên Rn. Khi đó ánh xạ dưới vi phân x −→ ∂f(x) nửa liên tục trên tại mọi điểm x ∈ int(dom f) Chứng minh. Ta có f lồi nên nó hữu hạn trên tập int(dom f). Vậy áp dụng mệnh đề 2.8 với U = int(dom f) và fi = f, ∀i, ta có: Nếu x ∈ int(dom f) và {xi} ⊂ int(dom f) hội tụ đến x thì với mọi  > 0, tồn tại i sao cho ∀i > i ta có ∂f(xi) ⊂ ∂f(x) + .B(0, 1). Suy ra ∂f nửa liên tục trên tại mọi điểm x ∈ int(dom f). Mệnh đề 2.10. Cho f là một hàm lồi chính thường trên Rn. Nếu f khả vi trên tập int(dom f) thì nó khả vi liên tục trên tập này. Chứng minh. Cho x ∈ int(dom f) và dãy{xi} ⊂ int(dom f). Ta áp dụng mệnh đề 2.8 với U = int(dom f) và Ofi = Of , ∀i, ta có: ∀ > 0 tồn tại i sao cho ∀i > i, ‖Of(xi)− Of(x)‖ 6 . Chứng tỏ Of(.) liên tục tại x. 2.2.5 Phép tính với dưới đạo hàm Tương tự giải tích cổ điển, nếu f là một hàm lồi chính thường trong Rn thì ∂(λf)(x) = λ.∂f(x) ,∀λ > 0 ,∀x. 43 Thật vậy x∗ ∈ ∂(λf)(x)⇔ 〈x∗, z − x〉+ (λf)(x) 6 (λf)(z) ,∀z ⇔ 〈x∗, z − x〉+ λf(x) 6 λf(z) ,∀z ⇔ 〈x ∗ λ , z − x〉+ f(x) 6 f(z) ,∀z ⇔ x ∗ λ ∈ ∂f(x) ⇔ x∗ ∈ λ∂f(x). Đối với dưới vi phân của tổng các hàm lồi, ta có định lý sau: Mệnh đề 2.11. (Định lý Moreau-Rockafellar). Cho fi, i=1,...,m là các hàm lồi chính thường trên Rn. Khi đó m∑ i=1 ∂fi(x) ⊆ ∂( m∑ i=1 fi(x)) ,∀x. Nếu ∩ ri(dom fi) 6= ∅ thì m∑ i=1 ∂fi(x) = ∂( m∑ i=1 fi(x)) ,∀x Chứng minh. Ta chứng minh m∑ i=1 ∂fi(x) ⊆ ∂( m∑ i=1 fi(x)),∀x. Nếu x∗ ∈∑mi=1 ∂fi(x) thì x∗ = ∑mi=1 x∗i , x∗i ∈ ∂fi(x), i = 1, ..,m. Ta có x∗i ∈ ∂fi(x), i = 1, ...,m⇔ 〈x∗i , z − x〉+ fi(x) 6 fi(z) ,∀z , i = 1, ...,m ⇒ 〈 m∑ i=1 x∗i , z − x〉+ m∑ i=1 fi(x) 6 m∑ i=1 fi(z),∀z ⇔ 〈x∗, z − x〉+ m∑ i=1 fi(x) 6 m∑ i=1 fi(z),∀z ⇔ x∗ ∈ ∂( m∑ i=1 fi(x)) ,∀x. Vậy ∑m i=1 ∂fi(x) ⊆ ∂( ∑m i=1 fi(x)),∀x. 44 Ta chứng minh m∑ i=1 ∂fi(x) ⊇ ∂( m∑ i=1 fi(x)) ,∀x. Chỉ cần chứng minh với m = 2, với m > 2 dùng quy nạp. Lấy x0 ∈ Rn và x∗ ∈ ∂( 2∑ i=1 fi(x 0)) = ∂(f1(x 0) + f2(x 0)) = ∂(f1 + f2)(x 0). Theo định nghĩa của dưới vi phân ta có: 〈x∗, x− x0〉+ f1(x0) + f2(x0) 6 f1(x) + f2(x) ∀x ⇔f1(x) + f2(x)− f1(x0)− f2(x0)− 〈x∗, x− x0〉 > 0 ∀x ⇔ { f1(x) + f2(y)− f1(x0)− f2(x0)− 〈x∗, x− x0〉 < 0 x = y không có nghiệm. Lấy D = dom f1ì dom f2 và A(x, y) = x− y. Theo giả thiết f1 liên tục tại một điểm a ∈ dom f1 ∩ dom f2, nên tồn tại một lân cận U của gốc sao cho U = (a+ U)− a ⊂ dom f1 − dom f2 = A(D). Vậy 0 ∈ intA(D), áp dụng mệnh đề 1.4 với f(x, y) = f1(x) + f2(y)− f1(x0)− f2(x0)− 〈x∗, x− x0〉 A(x, y) = x− y. Ta có 〈t, x− y〉+ [f1(x) + f2(y)− f1(x0)− f2(x0)− 〈x∗, x− x0〉] > 0, ∀x ∈ dom f1 , y ∈ dom f2. Đối với x 6∈ dom f1 và y 6∈ dom f2, thì bất đẳng thức trên là hiển nhiên. Vậy 〈t, x− y〉+ [f1(x) + f2(y)− f1(x0)− f2(x0)− 〈x∗, x− x0〉] > 0 ,∀x, y. 45 Lấy x = x0 ta có 〈t, y − x0〉+ f2(x0) 6 f2(y) ,∀y. Chứng tỏ t ∈ ∂f2(x0). Lấy y = x0 ta có 〈x∗ − t, x− x0〉+ f1(x0) 6 f1(x) ,∀x. Chứng tỏ x∗ − t ∈ ∂f1(x0). Do đó x∗ = (x∗ − t) + t ∈ ∂f1(x0) + ∂f2(x0). 2.3 Dưới vi phân xấp xỉ Dưới vi phân xấp xỉ, hay còn được gọi là -dưới vi phân, thường được sử dụng trong thực tế bởi hai lý do chính sau đây. Một là hàm lồi có thể không khả dưới vi phân tại những điểm thuộc biên của miền hữu dụng của nó, trong khi đó, như sẽ thấy dưới đây, trong miền này, dưới vi phân xấp xỉ luôn tồn tại. Lý do thứ hai quan trọng hơn là trong ứng dụng, thường người ta chỉ cần, và nhiều khi chỉ tính được dưới vi phân một cách xấp xỉ. Định nghĩa 2.8. Cho  > 0. Một véctơ x∗ được gọi là -dưới đạo hàm của f tại x, nếu 〈x∗, y − x〉+ f(x) 6 f(y) +  , ∀y. Kí hiệu tập hợp tất cả -dưới đạo hàm của f tại x là ∂f(x). Tập hợp này được gọi là -dưới vi phân. Hiển nhiên ∂0f(x) = ∂f(x). Vậy dưới đạo hàm xấp xỉ là một khái niệm tổng quát hoá của dưới đạo hàm chính xác. Nhận xét: Theo định nghĩa x∗ ∈ ∂f(x)⇔ 〈x∗, z − x〉+ f(x) 6 f(z) +  , ∀z. 46 Thay z = y + x , ta được 〈x∗, y〉+ f(x) 6 f(x+ y) +  , ∀y. Từ đây, nếu đặt h(y) = f(x+ y)− f(x) , ta có 〈x∗, y〉 − h(y) 6  , ∀y. Theo định nghĩa hàm liên hợp, ta có ∂f(x) = {x∗|h∗(x∗) 6 }. Do h∗ là một hàm lồi, đóng nên từ đây thấy rằng ∂f(x) luôn là một tập lồi, đóng . Hiển nhiên ∂f(x) ⊆ ∂′f(x) nếu  6 ′. Hơn nữa ∩>0∂f(x) nếu khác rỗng thì sẽ bằng ∂f(x). Ví dụ 2.6. Cho hàm một biến f(x) = { −2x 12 nếu x > 0, +∞ nếu x < 0. Ta có ∂f(0) 6= ∅ với  > 0. Thật vậy, lấy x∗ ∈ ∂f(0), ta có: x∗ ∈ ∂f(0)⇔ 〈x∗, y − 0〉+ f(0) 6 f(y) +  , ∀y ⇔ x∗y 6 −2√y +  , ∀y > 0. Nếu y = 0 thì 0 6 . Vậy bất đẳng thức trên được thoả mãn với mọi x∗. Nếu y > 0 thì x∗ 6 −2 √ y y . Vậy ∂f(0) 6= ∅ với  > 0. Mặt khác ∂f(0) = ∅ ( đã chứng minh phần trước ). Ví dụ trên cho thấy rằng ∂f(x) 6= ∅ với mọi  > 0, tuy nhiên ∂f(x) = ∅. Mệnh đề sau đây nói rằng mọi hàm lồi đóng đều khả -dưới vi phân với mọi  > 0 tại mọi điểm thuộc miền hữu dụng của nó . Mệnh đề 2.12. Cho f là một hàm lồi đóng chính thường trên Rn. Khi đó với mọi  > 0 và mọi x0 ∈ dom f , tập ∂f(x0) 6= ∅. Hơn nữa với mọi tập bị chặn C ⊂ int(dom f) tập ∂f(C) bị chặn. 47 Chứng minh. Do f lồi, đóng, chính thường nên epi f lồi, đóng, khác rỗng. Do epi f đóng nên điểm (x0, f(x0) − ) 6∈ epi f với mọi  > 0. Ta áp dụng định lý tách chặt cho hai tập C := epi f và D := {(x0, f(x0)− )}, sẽ tồn tại (p, t) 6= 0, p ∈ Rn, t ∈ R và số thực η ( phụ thuộc ) sao cho: 〈p, t〉 − tν < η < 〈p, x0〉 − t[f(x0)− ] ,∀(x, ν) ∈ epi f. (2.13) Từ đây ta có t 6= 0, vì nếu t=0 thì 〈p, x〉 < η < 〈p, x0〉 ,∀x ∈ dom f và do đó ta có mâu thuẫn nếu lấy x = x0. Hơn nữa t > 0, vì nếu t < 0 ta sẽ có mâu thuẫn từ (2.13) khi cho ν đủ lớn . Thay ν = f(x) và chia hai vế của (2.13) cho t > 0, ta có 〈p t , x〉 − f(x) < η t < 〈p t , x0〉 − f(x0) + . Suy ra 〈p t , x− x0〉+ f(x0) < f(x) + . Vậy p t ∈ ∂f(x0) hay ∂f(x0) 6= ∅. Giả sử C ⊂ int(dom f), C bị chặn. Đặt ξ = Supx∗∈∂f(C) ‖x∗‖ = Supx∈C Supx∗∈∂f(C) ‖x∗‖. (2.14) Xét ánh xạ tuyến tính 〈x∗, z〉. Chuẩn của ánh xạ tuyến tính này là ‖x∗‖ = Sup‖z‖=1〈x∗, z〉. Thay vào (2.14) ta có ξ = Supx∈C Supx∗∈∂f(x) Sup‖z‖=1〈x∗, z〉. Mặt khác x∗ ∈ ∂f(x)⇔ f ′(x, y) + β > 〈x∗, y〉 ,∀β > 0 ,∀y. 48 Do đó f ′(x, y) + β = Supx∗∈∂f(x)〈x∗, y〉 ,∀β > 0 ,∀y. Hay f ′(x, z) + β = Supx∗∈∂f(x)〈x∗, z〉 ,∀β > 0 ,∀z. Ta có tiếp ξ = Sup‖z‖=1 Supx∈C(f ′(x, z) + β) = Sup‖z‖=1 Supx∈C f ′(x, z) + β. Đặt g(z) := Supx∈C f ′(x, z). Do x ∈ C ⊆ int(dom f), nên hàm f ′(x, z) lồi trên Rn (do đó liên tục). Suy ra hàm g liên tục vì là bao trên của một họ hàm lồi liên tục trên Rn. Vậy ξ = Sup‖z‖=1 g(z) + β = max‖z‖=1 g(z) + β < +∞. Chứng tỏ ∂f(C) bị chặn. Mệnh đề 2.13. Cho f : Rn −→ R là hàm lồi đóng. Khi đó một véc-tơ x∗ là - dưới vi phân của f tại x ∈ dom f khi và chỉ khi f ∗(x∗) + f(x)− 〈x∗, x〉 6 . Chứng minh. Dùng định nghĩa -dưới đạo hàm ta có: x∗ ∈ ∂f(x)⇔ 〈x∗, y − x〉+ f(x) 6 f(y) +  , ∀y ∈ dom f ⇔ [〈x∗, y〉 − f(y)] + f(x)− 〈x∗, x〉 6  , ∀y ∈ dom f. Theo định nghĩa của f ∗(x∗) ta có: f ∗(x∗) = Supy{〈x∗, y〉 − f(y)}. Vậy f ∗(x∗) + f(x)− 〈x∗, x〉 6 . 49 Định nghĩa 2.9. Cho C ⊆ Rn là một tập lồi, đóng và x ∈ C. Tập -nón pháp tuyến ngoài của C tại x là -dưới vi phân của hàm chỉ của C tại x. Tức là: NC,(x) := ∂δC(x) = {x∗ ∈ Rn | 〈x∗, y − x〉 6  , ∀y ∈ C} Định lý 2.1. Cho f là hàm lồi, đóng, chính thường trên Rn. 0 ∈ ∂f(x)⇔ f(x) 6 f(y) +  , ∀y ∈ Rn. Chứng minh. Theo định nghĩa dưới vi phân xấp xỉ ta có: 0 ∈ ∂f(x)⇔ 〈0, y − x〉+ f(x) 6 f(y) +  , ∀y ∈ Rn ⇔ f(x) 6 f(y) +  , ∀y ∈ Rn. Mệnh đề 2.14. Cho fi, i=1,...,m là các hàm lồi chính thường trên R n . Giả sử ∩ri(dom fi) 6= ∅. Khi đó ∂ ( m∑ i=1 fi(x) ) ⊆ m∑ i=1 ∂fi(x) ∀x. Đặc biệt ∂ ( m∑ i=1 fi(x) ) = m∑ i=1 ∂fi(x), ∀x⇔  = 0. Chứng minh. Ta chứng minh cho m = 2. Với m > 2 dùng quy nạp. Ta lấy x0 ∈ Rn và x∗ ∈ ∂( 2∑ i=1 fi(x 0)) = ∂(f1(x 0) + f2(x 0)) = ∂(f1 + f2)(x 0). 50 Theo định nghĩa của dưới vi phân xấp xỉ, ta có: x∗ ∈ ∂(f1 + f2)(x0) ⇔〈x∗, x− x0〉+ (f1 + f2)(x0) 6 (f1 + f2)(x) +  ∀x ⇔〈x∗, x− x0〉+ f1(x0) + f2(x0) 6 f1(x) + f2(x) +  ∀x ⇔f1(x) + f2(x)− f1(x0)− f2(x0)− 〈x∗, x− x0〉+  > 0 ∀x ⇒hệ { f1(x) + f2(y)− f1(x0)− f2(x0)− 〈x∗, x− x0〉+  < 0 x = y không có nghiệm. (2.15) Lấy D = dom f1 ì dom f2, A(x, y) = x− y, f(x, y) = f1(x) + f2(y)− f1(x0)− f2(x0)− 〈x∗, x− x0〉+ . Theo giả thiết f1 liên tục tại một điểm a ∈ dom f1 ∩ dom f2, nên tồn tại một lân cận U của gốc sao cho U = (a+ U)− a ⊂ dom f1 − dom f2 = A(D). Vậy 0 ∈ intA(D). Lúc này (2.15) có dạng: hệ  f(x, y) < 0 A(x, y) = 0 (x, y) ∈ D không có mghiệm Ap dụng mệnh đề 1.4 ta có: 〈t, A(x, y)− 0〉+ f(x, y) > 0 ∀(x, y) ∈ D. ⇔ 〈t, x− y〉+ f1(x) + f2(y)− f1(x0)− f2(x0) + 〈x∗, x− x0〉+  > 0, ∀x ∈ dom f1 ,∀y ∈ dom f2. 51 Đối với x 6∈ dom f1 và y 6∈ dom f2 thì bất đẳng thức trên là hiển nhiên. Vậy 〈t, x− y〉+ f1(x) + f2(y)− f1(x0)− f2(x0) + 〈x∗, x−x0〉+  > 0 ∀x, y. Lấy x = x0 ta có : 〈t, x0 − y〉+ f2(y)− f2(x0) +  > 0 ∀y ⇔ 〈t, y − x0〉+ f2(x0) 6 f2(y) +  ∀y ⇔ t ∈ ∂f2(x0). Lấy y = x0 ta có: 〈t, x− x0〉+ f1(x)− f1(x0)− 〈x∗, x− x0〉+  > 0 ∀x ⇔ 〈x∗ − t, x− x0〉+ f1(x0) 6 f1(x) +  ∀x ⇔ x∗ − t ∈ ∂f1(x0). Do đó x∗ = (x∗ − t) + t ⊆ ∂f1(x0) + ∂f2(x0). Vậy ∂(f1(x 0) + f2(x 0)) ⊆ ∂f1(x0) + ∂f2(x0). Chương 3 Một số ứng dụng của dưới vi phân trong tối ưu hoá Chương này trước hết giới thiệu một số khái niệm chung về cực tiểu, - cực tiểu của một hàm lồi. Tiếp theo trình bày điều kiện cần và đủ của nghiệm tối ưu của bài toán lồi với các ràng buộc khác nhau (Không ràng buộc, ràng buộc đẳng thức, ràng buộc bất đẳng thức). Cuối chương trình bày điều kiện cần và đủ của nghiệm tối ưu xấp xỉ của bài toán lồi với các ràng buộc khác nhau. 3.1 Các khái niệm Định nghĩa 3.1. Cho C ⊆ Rn khác rỗng và f : Rn −→ R ∪ {+∞}. a) Điểm x∗ ∈ C được gọi là cực tiểu đị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∗) 6 f(x),∀x ∈ U ∩ C. b) Điểm x∗ ∈ C được gọi là cực tiểu toàn cục (hay cực tiểu tuyệt đối ) của f trên C nếu f(x∗) 6 f(x),∀x ∈ C. c) Điểm x ∈ C được gọi là điểm chấp nhận được của bài toán. Định nghĩa 3.2. Cho  > 0. Một điểm x ∈ C được gọi là điểm -cực tiểu toàn cục của f trên C nếu f(x) 6 f(x) + ,∀x ∈ C. 52 53 3.2 Bài toán lồi không có ràng buộc Xét bài toán (P1) {minh(x) | x ∈ Rn}. Trong đó h là một hàm lồi chính thường trên Rn. Mệnh đề 3.1. x∗ là nghiệm của bài toán (P1)⇔ 0 ∈ ∂h(x∗). Chứng minh. Ta có: x∗là nghiệm của bài toán (P1)⇔ x∗là điểm cực tiểu của h trên Rn ⇔ h(x∗) 6 h(x) ,∀x ∈ Rn ⇔ 〈0, x− x∗〉+ h(x∗) 6 h(x) ,∀x ∈ Rn ⇔ 0 ∈ ∂h(x∗). 3.3 Bài toán lồi với ràng buộc đẳng thức Xét bài toán (P2) {min f(x) | x ∈ C}. Trong đó C ⊆ Rn là một tập lồi khác rỗng và f là một hàm lồi trên C. Mệnh đề 3.2. Giả sử ri(dom f) ∩ riC 6= ∅. x∗ ∈ C là nghiệm của bài toán (P2)⇔ 0 ∈ ∂f(x∗) +NC(x∗), trong đó NC(x ∗) := {ω | 〈ω, x− x∗〉 6 0 ,∀x ∈ C} là nón pháp tuyến ngoài của C tại x∗. Chứng minh. Gọi δC(.) là hàm chỉ của tập C , tức là δC(x) := { 0 nếu x ∈ C, +∞ nếu x 6∈ C. 54 Khi đó x∗ là nghiệm của bài toán (P2) ⇔x∗ là điểm cực tiểu của f trên C ⇔x∗ là điểm cực tiểu của h(x) := f(x) + δC(x) trênRn ⇔0 ∈ ∂h(x∗) (theo mệnh đề 3.1). Do ri(dom f) ∩ riC 6= ∅, theo định lý Moreau-Rockafellar ta có: ∂h(x∗) = ∂[f(x∗) + δC(x∗)] = ∂f(x∗) + ∂δC(x∗). Vì x∗ ∈ C nên ∂δC(x∗) = NC(x∗). Vậy ∂h(x∗) = ∂f(x∗) +NC(x∗). Suy ra 0 ∈ ∂f(x∗) +NC(x∗). 3.4 Bài toán lồi với ràng buộc bất đẳng thức Xét bài toán tìm cực tiểu của một hàm lồi trên một tập lồi có dạng sau: (OP ) {min f(x) | gi(x) 6 0 (i = 1, ....m), x ∈ X}. Trong đó X ⊆ Rn là một tập lồi đóng khác rỗng và f, gi (i=1,..m) là các hàm lồi hữu hạn trên X . Ta sẽ luôn giả sủ rằng X có điểm trong. Bài toán (OP) này được gọi là một quy hoạch lồi. Hàm f được gọi là hàm mục tiêu. Các điều kiện x ∈ X, gi(x) 6 0 (i = 1, ...m) được gọi là các ràng buộc. Tập D := {x ∈ X | gi(x) 6 0 i = 1, ...m} được gọi là miền chấp nhận được. Một điểm x ∈ D được gọi là điểm chấp nhận được của bài toán (OP). Do X là tập lồi, các hàm gi (i=1,..,m) lồi trên X nên D là một tập lồi. Điểm cực tiểu của f trên D cũng được gọi là nghiệm tối ưu của bài toán (OP). 55 Ta xây dựng hàm sau, được gọi là hàm Lagrange, cho bài toán (OP): L(x, λ) := λ0f(x) + m∑ i=1 λigi(x), với λ = (λ0, ..., λm) Dựa vào hàm Lagrange ta có kết qủa sau: Định lý 3.1. (Karush- Kuhn- Tucker) Giả sử ri(dom f) ∩ ri(dom gi) ∩ riX 6= ∅ a) Nếu x∗ là nghiệm của bài toán (OP) thì tồn tại λ∗i > 0 (i=0,...,m) không đồng thời bằng 0 sao cho: 1) L(x∗, λ∗) = minx∈X L(x, λ∗) (điều kiện đạo hàm triệt tiêu ) (⇔ 0 ∈ λ∗0∂f(x∗) + m∑ i=1 λ∗i∂gi(x ∗) +NX(x∗) ). Trong đó NX(x ∗) là nón pháp tuyến ngoài của X tại x∗ . 2) λ∗i gi(x ∗) = 0 (i = 1, ...,m) (điều kiện độ lệch bù). Hơn nữa nếu điều kiện Slater sau thoả mãn: ∃x0 ∈ X : gi(x0) 0. b) Nếu hai điều kiện đạo hàm triệt tiêu và độ lệch bù ở trên được thoả mãn với λ∗0 > 0 thì điểm chấp nhận được x ∗ là nghiệm tối ưu của bài toán (OP) Chứng minh. a) Giả sử x∗ là nghiệm của bài toán (OP). Đặt C :={(λ0, λ1, ..., λm) ∈ Rm+1|∃x ∈ X : f(x)− f(x∗) < λ0, gi(x) 6 λi, i = 1, ...,m}. Do X 6= ∅ lồi, f, gi lồi trên X , nên C là một tập lồi . 56 Ta có C 6= ∅. Thật vậy: + Lấy (λ0, ..., λm) ∈ intRm+1+ . Khi đó λi > 0 (i = 1, ...,m). + Với x = x∗, ta có f(x∗)− f(x∗) = 0 < λ0 gi(x ∗) 6 0 < λi (i = 1, ...,m). ⇒ (λ0, ..., λm) ∈ C. ⇒ intRm+1+ ⊂ C. ⇒ C 6= ∅ trong Rm+1. Hơn nữa 0 6∈ C. Thật vậy, nếu 0 ∈ C thì ∃x ∈ X : f(x)− f(x∗) < 0 gi(x) 6 0 (i = 1, ...,m). Do đó x∗ không là nghiệm của bài toán (OP)⇒ mâu thuẫn. Vậy 0 6∈ C. Theo định lý tách thứ 1, có thể tách các tập C và {0}, tức là ∃λ∗i (i=0,...m) không đồng thời bằng 0 sao cho m∑ i=0 λ∗iλi > 0 ∀(λ0, ..., λm) ∈ C. (3.1) Do intRm+1+ ⊂ C, ta suy ra λ∗i > 0. Với  > 0 và x ∈ X , lấy λ0 = f(x)− f(x∗) +  λi = gi(x) (i = 1, ...,m). Thay vào (3.1) ta có λ∗0[f(x)− f(x∗) + ] + m∑ i=1 λ∗i gi(x) > 0 ∀x ∈ X. Cho → 0 ta được λ∗0f(x) + m∑ i=1 λ∗i gi(x) > λ∗0f(x∗) ∀x ∈ X. (3.2) 57 Do x∗ là điểm chấp nhận được nên ta có gi(x∗) 6 0 (i = 1, ...,m). Vậy λ∗0f(x ∗) > λ∗0f(x∗) + m∑ i=1 λ∗i gi(x ∗). (3.3) Từ (3.2) và (3.3) ta có λ∗0f(x) + m∑ i=1 λ∗i gi(x) > λ∗0f(x∗) + m∑ i=1 λ∗i gi(x ∗) ∀x ∈ X ⇔L(x, λ∗) > L(x∗, λ∗) ∀x ∈ X ⇔L(x∗, λ∗) = minx∈X L(x, λ∗) (điều kiện đạo hàm triệt tiêu). Ta chú ý rằng x∗ là nghiệm của bài toán {minL(x, λ∗), x ∈ X} khi và chỉ khi x∗ là điểm cực tiểu của hàm L(x, λ∗) trên X ⇔x∗ là điểm cực tiểu của hàm L1(x, λ∗) := L(x, λ∗) + δX(x) trênRn. ⇔0 ∈ ∂L1(x∗, λ∗) (theo mệnh đề 3.1). Do ri(dom f) ∩ ri(dom gi) ∩ riX 6= ∅ và f, gi (i:=1,...,m) là các hàm lồi, hữu hạn trên X nên theo định lý Moreau-Rockafellar ta có ∂L1(x ∗, λ∗) = ∂[L(x∗, λ∗) + δX(x∗)] = ∂[λ∗0f(x ∗) + m∑ i=1 λ∗i gi(x ∗)] + ∂δX(x∗) = λ∗0∂f(x ∗) + m∑ i=1 λ∗i∂gi(x ∗) +NX(x∗) (vì ∂δX(x ∗) = NX(x∗) ). Vậy 0 ∈ λ∗0∂f(x∗) + m∑ i=1 λ∗i∂gi(x ∗) +NX(x∗). Do x∗ là điểm chấp nhận được nên gi(x∗) 6 0 (i = 1, ...,m). Nếu ∃i ∈ {1, ...,m} : gi(x∗) = ξ < 0 thì ∀ > 0 , f(x∗)− f(x∗) = 0 <  gj(x ∗) 6 0 < (j = 1, ..., i− 1, i+ 1, ...,m). 58 ⇒ (, ..., , ξ, , ..., ) ∈ C (ξ ở vị trí thứ i). ⇒ λ∗i ξ > 0 ( thay vào (3.1) và cho → 0) ⇒ λ∗i 6 0. Theo chứng minh trên ta có λ∗i > 0. Vậy λ∗i = 0. Như vậy là, nếu gi(x ∗) < 0 thì λ∗i = 0. Do đó λ∗i gi(x ∗) = 0 (i = 1, ..,m) (điều kiện độ lệch bù ). Giả sử điều kiện Slater được thoả mãn: ∃x0 ∈ X : gi(x0) < 0. Khi đó nếu λ∗0 = 0 thì do điều kiện đạo hàm triệt tiêu và độ lệch bù ta có 0 = λ∗0f(x ∗) + m∑ i=1 λ∗i gi(x ∗) 6 λ∗0f(x) + m∑ i=1 λ∗i gi(x) ,∀x ∈ X. Do λ∗0 = 0 nên phải có ít nhất một λ ∗ i > 0. Thay x0 vào bất đẳng thức trên, sẽ được 0 = λ∗0f(x ∗) + m∑ i=1 λ∗i gi(x ∗) 6 λ∗0f(x0) + m∑ i=1 λ∗i gi(x 0) < 0. Suy ra mâu thuẫn. Vậy λ∗0 6= 0 tức là λ∗0 > 0. b) Giả sử x∗ là điểm chấp nhận được thoả mãn hai điều kiện đạo hàm triệt tiêu và độ lệch bù ở trên với λ∗0 > 0, λ ∗ i > 0 (i = 1, ...,m). Do λ∗0 > 0, nên bằng cách chia cho λ ∗ 0, ta có thể coi hàm Lagrange là L(x, λ) = f(x) + m∑ i=1 λigi(x). Từ điều kiện đạo hàm triệt tiêu và độ lệch bù, ta có: f(x∗) + m∑ i=1 λ∗i gi(x ∗) 6 f(x) + m∑ i=1 λ∗i gi(x) ∀x ∈ X λ∗i gi(x ∗) = 0 (i = 1, ...,m). Suy ra f(x∗) 6 f(x) + m∑ i=1 λ∗i gi(x) ,∀x ∈ X. (3.4) 59 Với mọi x là điểm chấp nhận được, tức là: x ∈ X : gi(x) < 0 , i = 1, ...,m, ta có f(x) + m∑ i=1 λ∗i gi(x) 6 f(x). (3.5) Từ (3.4) và (3.5) suy ra f(x∗) 6 f(x) ,∀x ∈ X .Chứng tỏ x∗ là nghiệm tối ưu của bài toán (OP). Ví dụ 3.1. Ap dụng định lý cho bài toán sau: {min f(x) | gi(x) 6 0 (i = 1, 2) , x ∈ X}, (OP ) trong đó f(x) = x2, g1(x) = x 2 − x, g2(x) = −x,X = [−12 , 12 ]. Giải: Ta có miền chấp nhận được D = {x ∈ X | gi(x) 6 0 (i = 1, 2)} = [0, 1 2 ]. Giả sử tồn tại λ∗i > 0 (i = 0, ..., 2) không đồng thời bằng 0 sao cho: 1) L(x∗, λ∗) = minx∈X L(x, λ∗) (⇔ 0 ∈ λ∗0∂f(x∗) + ∑2 i=1 λ ∗ i∂gi(x ∗) +NX(x∗) ). 2) λ∗i gi(x ∗) = 0, i = 1, 2. 3) λ∗0 > 0. Từ định lí 3.1, suy ra x∗ là nghiệm tối ưu của bài toán (OP) ⇔f(x∗) 6 f(x), ∀x ∈ D ⇔x∗2 6 x2, ∀x ∈ D ⇔x∗2 6 0 ⇔x∗ = 0. Ngược lại, nếu x∗ = 0 là nghiệm của bài toán (OP) thì từ định lí 3.1, suy ra tồn tại λ∗i > 0 (i = 0, ..., 2) không đồng thời bằng 0 sao cho : 60 1) L(x∗, λ∗) = minx∈X L(x, λ∗) (⇔ 0 ∈ λ∗0∂f(x∗) + ∑2 i=1 λ ∗ i∂gi(x ∗) +NX(x∗) ). 2) λ∗i gi(x ∗) = 0, i = 1, 2. Ta có L(x∗, λ∗) = minx∈X L(x, λ∗) ⇔L(x, λ∗) > L(x∗, λ∗), ∀x ∈ X ⇔λ∗0f(x) + 2∑ i=1 λ∗i gi(x) > λ∗0f(x∗) + 2∑ i=1 λ∗i gi(x ∗), ∀x ∈ X ⇔λ∗0x2 + λ∗1(x2 − x)− λ∗2x > 0, ∀x ∈ X. Ta có λ∗i gi(x ∗) = 0, i = 1, 2⇔ λ∗i .0 = 0, i = 1, 2⇔ λ∗i > 0, i = 1, 2. Do λ∗i > 0 (i = 0, ..., 2) không đồng thời bằng 0 nên: + Chọn λ∗1 = λ ∗ 2 = 0. Ta có λ∗0x 2 + λ∗1(x 2 − x)− λ∗2x > 0, ∀x ∈ X ⇔λ∗0x2 > 0, ∀x ∈ X ⇔λ∗0 > 0 ⇒Chọnλ∗0 = 1. + Chọn λ∗1 = λ ∗ 2 = 1. Ta có λ∗0x 2 + λ∗1(x 2 − x)− λ∗2x > 0, ∀x ∈ X ⇔(λ∗0 + 1)x2 − 2x > 0, ∀x ∈ X ⇒Không tồn tại λ∗0. + Chọn λ∗1 = 0, λ ∗ 2 = 1. Ta có λ∗0x 2 + λ∗1(x 2 − x)− λ∗2x > 0, ∀x ∈ X ⇔λ∗0x2 − x > 0, ∀x ∈ X ⇒Không tồn tại λ∗0. 61 + Chọn λ∗1 = 1, λ ∗ 2 = 0. Ta có λ∗0x 2 + λ∗1(x 2 − x)− λ∗2x > 0, ∀x ∈ X ⇔(λ∗0 + 1)x2 − x > 0, ∀x ∈ X ⇒Không tồn tại λ∗0. Vậy x∗ = 0 là nghiệm tối ưu của bài toán (OP) và λ∗0 = 1, λ ∗ 1 = λ ∗ 2 = 0 là các nhân tử Lagrang tương ứng. Chú ý 3.1. Trong nhiều trường hợp bài toán (P1), (P2) và (OP) có thể không có lời giải tối ưu chính xác. Hơn nữa trong thực tế thường người ta không tính được lời giải tối ưu (chính xác), mà chỉ tính được lời giải xấp xỉ. Khi đó ta dùng khái niệm lời giải tối ưu xấp xỉ hay còn gọi là - tối ưu. Mệnh đề 3.3. x là  -nghiệm của bài toán (P1)⇔ 0 ∈ ∂h(x) Chứng minh. Ta có: x là − nghiệm của bài toán (P1) ⇔x là điểm − cực tiểu của h trên Rn ⇔h(x) 6 h(x) +  , ∀x ∈ Rn (theo định nghĩa3.2) ⇔0 ∈ ∂h(x) (theo định lý2.1). Mệnh đề 3.4. Giả sử ri(dom f) ∩ riC 6= ∅. Khi đó x ∈ C là  -nghiệm của bài toán (P2) =⇒ 0 ∈ ∂f(x) +NC,(x), trong đó NC,(x) := {ω | 〈ω, x − x〉 6  , ∀x ∈ C} là  -nón pháp tuyến ngoài của C tại x. Chứng minh. Gọi δC(.) là hàm chỉ của tập C , tức là δC(x) := { 0 nếu x ∈ C, +∞ nếu x 6∈ C. 62 Khi đó x là − nghiệm của bài toán (P2) ⇔x là điểm − cực tiểu của f trên C ⇔x là điểm − cực tiểu của h(x) := f(x) + δC(x) trên Rn ⇔0 ∈ ∂h(x) (theo mệnh đề 3.3). Do ri(dom f) ∩ riC 6= ∅, ta có: ∂h(x) = ∂[f(x) + δC(x)] ⊆ ∂f(x) + ∂δC(x) (theo mệnh đề 2.14) = ∂f(x) +NC,(x) (Vì x ∈ C nên theo định nghĩa 2.9 ∂δC(x) = NC,(x) ). Vậy 0 ∈ ∂f(x) +NC,(x). 63 Kết luận Như vậy, luận văn này đã trình bày một cách hệ thống các khái niệm, tính chất cơ bản của tập lồi và hàm lồi. Sau đó lại đề cập về đạo hàm theo phương, dưới vi phân, dưới vi phân xấp xỉ và chứng minh một cách cụ thể một số tính chất của chúng. Cuối cùng luận văn trình bày các điều kiện cực trị cho các bài toán quy hoạch lồi với các rằng buộc khác nhau. Tài liệu tham khảo [1] Lê Dũng Mưu và Nguyễn Văn Hiền (2003), Nhập môn giải tích lồi ứng dụng, Giáo trình. [2] . Tạ Quang Sơn (2008), Some Qualitative Problems In Optimization, Luận án tiến sĩ. [3] T. Rockafellar (1970), Convex Analysis, Princeton University Press, Princeton, New Jersey. [4] J. Hiriart-Urruty and C. Lemarechal, Convex Analysis and Minimization Algorithms. 64