Tài liệu Về cận sai số của hàm nửa liên tục dưới

BỘ GIÁO DỤC VÀ ĐÀO TẠO VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM VIỆN TOÁN HỌC TRẦN THỊ HẰNG VỀ CẬN SAI SỐ CỦA HÀM NỬA LIÊN TỤC DƯỚI LUẬN VĂN THẠC SĨ TOÁN HỌC Hà Nội – Năm 2015 BỘ GIÁO DỤC VÀ ĐÀO TẠO VIỆN HÀN LÂM KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM VIỆN TOÁN HỌC TRẦN THỊ HẰNG VỀ CẬN SAI SỐ CỦA HÀM NỬA LIÊN TỤC DƯỚI Chuyên ngành: Toán ứng dụng Mã số: 60 46 01 12 LUẬN VĂN THẠC SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS.TRƯƠNG XUÂN ĐỨC HÀ Hà Nội – Năm 2015 Mục lục Lời nói đầu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Danh mục kí hiệu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1 Kiến thức chuẩn bị 6 1.1 Hàm nửa liên tục dưới . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.2 Nguyên lý biến phân Ekeland . . . . . . . . . . . . . . . . . . . . . . . 9 1.3 Tập lồi và hàm lồi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2 Một số đặc trưng cận sai số của các hàm nửa liên tục dưới 18 2.1 Khái niệm cận sai số . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.2 Điều kiện độ dốc mạnh và dưới vi phân . . . . . . . . . . . . . . . . . 20 2.3 2.2.1 Điều kiện độ dốc mạnh . . . . . . . . . . . . . . . . . . . . . . . 20 2.2.2 Điều kiện dưới vi phân . . . . . . . . . . . . . . . . . . . . . . . 25 Toán tử dưới vi phân trừu tượng . . . . . . . . . . . . . . . . . . . . . 36 3 Tính chính quy metric của ánh xạ đa trị 44 Kết luận . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 Tài liệu tham khảo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 1 Lời nói đầu Bài toán tìm điều kiện tồn tại cận sai số cho khoảng cách từ một điểm tới một tập mức của hàm nửa liên tục dưới đã được Hoffman nghiên cứu lần đầu từ năm 1952. Bài toán được phát biểu như sau: Cho một hàm nửa liên tục dưới f : X → R ∪ {+∞} xác định trên không gian metric đủ X, chúng ta nói rằng f có một cận sai số toàn cục tại mức α nếu tồn tại số thực dương σ thỏa mãn σd (x, [f ≤ α]) ≤ (f (x) − α)+ , ∀x ∈ X. (1) trong đó [f ≤ α] := {x ∈ X : f (x) ≤ α}, và d (x, [f ≤ α]) là khoảng cách từ điểm x đến tập [f ≤ α], t+ = max (t, 0). Hoffman đã thu được các kết quả cho các hàm lồi đa
diện dạng f (x) = max aTj x + bj , trong đó a1 , ..., am ∈ Rn và b1 , ..., bm ∈ R. Trong 1≤j≤m trường hợp hàm lồi trong không gian định chuẩn thỏa mãn điều kiện inf f ≤ α với X tập [f ≤ α] bị chặn ta cũng thu được bất đẳng thức (1). Thật vậy, giả sử f (x0 ) = α − θ < α với θ > 0 và lấy x ∈ X, f (x) > α khi đó xt := x + t (x0 − x) ∈ [f ≤ α] với t= f (x) − α ∈ [0, 1] và θ + f (x) − α ||x − x0 || ≤ ||x − xt || + ||xt − x0 || ≤ t||x − x0 || + r + ||x0 ||, r là bán kính hình cầu gốc 0 chứa tập [f ≤ α]. Như vậy ta thu được kết quả sau d (x, [f ≤ α]) ≤ r + ||x0 || (f (x) − α) . θ 2 Lời nói đầu Tiếp đó, Mangasarian, Auslender - Crouzeix và Klatte-Li đã tìm ra điều kiện đủ cho sự tồn tại cận sai số của hệ tuyến tính với điều kiện tiệm cận. Trong trường hợp không lồi, kết quả đầu tiên về cận sai số thuộc về Ioffe, Ng-Zheng và Wu-Ye. Penot là người đầu tiên nhận được kết quả trong trường hợp hàm tựa lồi. Các đặc trưng đầu tiên về cận sai số trong trường hợp hàm lồi được công bố bởi Corneia-Jourari-Zalinesco, một số tính chất khác được thiết lập bởi Lewis-Pang, Lemaire, Zalinesco. Sau đó Azé đã tìm ra những đặc trưng của cận sai số của các hàm nửa liên tục dưới trong không gian metric đầy đủ (xem tài liệu tham khảo trong bài báo [4]). Mục đích của luận văn này là trình bày lại một cách tổng quan một số kết quả trong các bài báo [4], [5] và [6], [7] về cận sai số đối với các hàm nửa liên tục dưới. Ngoài ra tác giả có trình bày một số ví dụ để minh họa các kết quả trên. Luận văn gồm 3 chương: Chương 1: Trình bày các kiến thức cơ sở về các hàm nửa liên tục dưới, Nguyên lý biến phân Ekeland và giải tích lồi. Chương 2: Trình bày một số đặc trưng của cận sai số của các hàm nửa liên tục dưới thông qua khái niệm độ dốc mạnh và dưới vi phân. Chương 3: Trình bày ứng dụng một số kết quả về cận sai số để nghiên cứu tính chính quy metric của ánh xạ đa trị. Luận văn được thực hiện và hoàn thành tại Viện Toán học, Viện Hàn lâm Khoa học và Công nghệ Việt Nam, dưới sự hướng dẫn khoa học của PGS. TS Trương Xuân Đức Hà. Qua đây, tôi xin được gửi lời cảm ơn sâu sắc đến cô giáo, người hướng dẫn khoa học của mình, PGS. TS Trương Xuân Đức Hà, người đã đưa ra đề tài và tận tình 3 Lời nói đầu hướng dẫn tôi trong suốt quá trình thực hiện luận văn. Tôi xin bày tỏ lòng biết ơn sâu sắc tới Ban lãnh đạo Viện Toán học, Trung tâm Đào tạo Sau đại học và tập thể cán bộ của Viện Toán học đã tạo điều kiện thuận lợi cho tôi trong thời gian học Cao học. Tôi xin gửi lời cảm ơn tới gia đình và bạn bè về sự khuyến khích giúp đỡ tôi trong quá trình học tập và nghiên cứu. Do thời gian và khối lượng kiến thức lớn, chắc chắn bản luận văn không thể tránh khỏi những thiếu sót, rất mong nhận được sự chỉ bảo tận tình của các thầy cô và bạn bè đồng nghiệp, tôi xin chân thành cảm ơn! Hà Nội, tháng 08 năm 2015 Trần Thị Hằng 4 Danh mục kí hiệu R Đường thẳng thực Rn Không gian Euclide n-chiều x∈M Phần tử x thuộc tập M y∈ /M Phần tử y không thuộc tập M ∀x Với mọi x ∃x Tồn tại x A∩B Giao của hai tập A và B A∪B Hợp của hai tập A và B A\B Tập các điểm thuộc tập A mà không thuộc tập B A×B Tích đề các của hai tập A và B A+B Tổng của hai tập A và B || · || Chuẩn trong không gian Banach || · ||∗ Chuẩn trong không gian đối ngẫu < x∗ , x > Giá trị của hàm x∗ tại x f :X→Y Ánh xạ đơn trị từ X vào Y F :X⇒Y Ánh xạ đa trị từ X vào Y intD Phần trong của tập D inf f (x) infimum của tập {f (x) : x ∈ A} sup f (x) supremum của tập {f (x) : x ∈ A} x∈A x∈A t+ max {t, 0}  Kết thúc chứng minh t.ư. tương ứng. 5 Chương 1 Kiến thức chuẩn bị Trong chương này chúng tôi trình bày khái quát một số kiến thức về hàm nửa liên tục dưới, nguyên lý biến phân Ekeland và giải tích lồi. Những kiến thức trình bày trong chương này được chọn chủ yếu từ các tài liệu [1], [2]. 1.1 Hàm nửa liên tục dưới Cho (X, d) là không gian metric và f : X → R ∪ {+∞} là hàm số xác định trên X. Kí hiệu dom(f ) = {x ∈ X : f (x) < +∞} là miền hữu hiệu của f , Cα (f ) = {x ∈ X : f (x) ≤ α} là tập mức dưới của f tại α, epi(f ) = {(x, α) ∈ X × R : f (x) ≤ α} là tập trên đồ thị của f . Hàm f được gọi là chính thường nếu domf 6= ∅. Định nghĩa 1.1. Cho (X, d) là không gian metric, một hàm f : X → R ∪ {+∞} được 6 Chương 1. Kiến thức chuẩn bị gọi là hàm nửa liên tục dưới tại x0 ∈ X nếu thỏa mãn f (x0 ) ≤ lim inf f (x) , x→x0 trong đó lim inf f (x) = inf {y : ∃ {xi } ∈ domf, {xi } → x0 , f (xi ) → y} . x→x0 Ta còn có định nghĩa khác về hàm nửa liên tục dưới như sau: Định nghĩa 1.2. Cho (X, d) là không gian metric, một hàm f : X → R ∪ {+∞} gọi là nửa liên tục dưới tại x0 ∈ X nếu với mọi ε > 0 tồn tại δ > 0 sao cho f (x) > f (x0 ) − ε, với x ∈ X thỏa mãn d (x, x0 ) ≤ δ. Hàm f được gọi là nửa liên tục dưới trên X nếu nó liên tục dưới tại mọi điểm của X. Ví dụ 1.1. Hàm f : R → R được cho bởi    x2    f (x) = 2x     1 2 nếu x < 1, nếu x > 1, nếu x = 1. liên tục tại mọi điểm trừ điểm x = 1. Tại x = 1, hàm f là nửa liên tục dưới. Định lý 1.1. Cho (X, d) là không gian metric và hàm f : X → R ∪ {+∞}. Khi đó các khẳng định sau là tương đương: (i) f là hàm nửa liên tục dưới trên X. (ii) Tập trên đồ thị của f là tập đóng trong X × R. (iii) Với mọi α ∈ R, tập mức dưới Cα (f ) là tập đóng trong X. 7 Chương 1. Kiến thức chuẩn bị Chứng minh. (i) =⇒ (ii) Giả sử f là nửa liên tục dưới trên X. Ta lấy dãy {(xn , αn )} ⊂ epif sao cho lim (xn , αn ) = (x0 , α0 ). Ta cần chỉ ra (x0 , α0 ) ∈ epif . n→∞ Thật vậy, ta có lim xn = x0 , lim αn = α0 và f là hàm nửa liên tục dưới tại x0 n→∞ n→∞ nên lim inf f (xn ) ≥ f (x0 ). Vì dãy {(xn , αn )} ⊂ epif nên f (xn ) ≤ αn với mọi n, suy n→∞ ra lim inf f (xn ) ≤ lim (αn ). Do đó f (x0 ) ≤ lim inf f (xn ) ≤ lim (αn ) = α0 . Chứng tỏ n→∞ n→∞ n→∞ n→∞ (x0 , α0 ) ∈ epif. (ii) =⇒ (iii) Giả sử epif là tập đóng trong X × R. Ta sẽ chứng minh mọi tập mức của f đều đóng trong X. Thật vậy, giả sử Cα (f ) = {x ∈ X : f (x) ≤ α} là tập mức dưới bất kì của f . Lấy {xn } ⊂ Cα (f ) thỏa mãn lim xn = x0 . Do {xn } ⊂ Cα (f ) nên f (xn ) ≤ α, tức là n→∞ (xn , α) ∈ epif, ∀n ∈ N. Mà lim xn = x0 suy ra lim (xn , α) = (x0 , α). Hơn nữa, epif n→∞ n→∞ đóng trong X × R suy ra (x0 , α) ∈ epif , cho nên f (x0 ) ≤ α. Vậy x0 ∈ Cα (f ). (iii) =⇒ (i) Giả sử Cα (f ) đóng trong X, ta cần chứng minh f là hàm nửa liên tục dưới trên tập X. Giả sử phản chứng, f không là hàm nửa liên tục dưới tại x0 ∈ X. Khi đó tồn tại dãy {xn } ⊂ X sao cho lim xn = x0 và lim inf f (xn ) < f (x0 ). Chọn n→∞ n→∞ ε > 0 đủ nhỏ sao cho có k ∈ N để f (xn ) ≤ f (x0 ) − ε, ∀n > k. Xét tập mức C = {x ∈ X | f (x) ≤ f (x0 ) − ε}. Do C đóng và lim xn = x0 nên suy ra x0 ∈ C. Do đó ta n→∞ có, f (x0 ) ≤ f (x0 ) − ε (vô lý). Vậy f là hàm nửa liên tục dưới trên X.  Định lý 1.2. Một hàm f nửa liên tục dưới trên tập compact U thuộc không gian metric phải đạt cực tiểu trên tập ấy. Tuy nhiên, nếu U không phải là tập compact thì điều này không còn đúng. Chẳng hạn ta xét ví dụ dưới đây: 8 Chương 1. Kiến thức chuẩn bị Ví dụ 1.2. Xét hàm số f : R → R xác định bởi   1 nếu x > 0, f (x) = x  +∞ nếu x ≤ 0. Ta thấy R không là tập compact. f liên tục trên R với mọi x ∈ R và inf f = 0. R Tuy nhiên không tồn tại x ∈ R để f (x) = 0. Vậy hàm f không đạt cực tiểu trên R. Trong trường hợp đó chúng ta sẽ tìm hiểu nguyên lý biến phân Ekeland dưới đây: 1.2 Nguyên lý biến phân Ekeland Nguyên lý biến phân do I.Ekeland đề xuất năm 1974 là một công cụ mạnh trong Giải tích phi tuyến, Giải tích không trơn, Giải tích đa trị, Giải tích biến phân và trong các hướng khác nhau của toán ứng dụng. Định nghĩa 1.3. Hàm f : X → R, với ε > 0 cho trước, một điểm xε ∈ X gọi là cực tiểu ε− xấp xỉ của f trên X nếu inf f (x) ≤ f (xε ) ≤ inf f (x) + ε. x∈X x∈X Ekeland đã chứng minh được rằng trong không gian metric đầy đủ, nếu xε là ε− cực tiểu xấp xỉ của một hàm nửa liên tục dưới thì ta sẽ tìm được một ε− cực tiểu xấp xỉ mới x∗ tốt hơn và điểm này là cực tiểu chính xác của hàm nhiễu của f . Định lý 1.3. [Nguyên lý biến phân Ekeland] Cho (X, d) là không gian metric đầy đủ và f : X → R ∪ {+∞} là hàm nửa liên tục dưới và bị chặn dưới. Giả sử ε > 0 và xε ∈ X thỏa mãn f (xε ) ≤ inf f (x) + ε. x∈X Khi đó, với λ > 0 bất kì, tồn tại x∗ ∈ X sao cho : 9 Chương 1. Kiến thức chuẩn bị (i) d(x∗ , xε ) ≤ λ. (ii) f (x∗ ) ≤ f (xε ). (iii) f (x∗ ) < f (x) + 1.3 ε λ d (x, x∗ ) , ∀x ∈ X\ {x∗ } . Tập lồi và hàm lồi Trong mục này, X là không gian Banach với chuẩn ||.||, X ∗ là không gian đối ngẫu của X. Khi đó X ∗ là không gian Banach với chuẩn ||.||∗ . Với mỗi x∗ ∈ X ∗ , x ∈ X ta ký hiệu hx∗ , xi = x∗ (x). Định nghĩa 1.4. Tập C ⊂ X được gọi là lồi nếu với mọi x, y ∈ C và mọi λ ∈ R sao cho λ ∈ [0, 1] thì λx + (1 − λ) y ∈ C. Ví dụ 1.3. Các tập sau đây đều là các tập lồi: 1) Hình cầu mở B (a, r) := {x ∈ X : ||x − a|| < r} , hay hình cầu đóng B (a, r) := {x ∈ X : ||x − a|| ≤ r} . 2) Các nửa không gian đóng {x ∈ Rn : ha, xi ≤ α} , {x ∈ Rn : ha, xi ≥ α} , hay các nửa không gian mở {x ∈ Rn : ha, xi < α} , với a ∈ Rn , a 6= 0, α ∈ R. 10 {x ∈ Rn : ha, xi > α} Chương 1. Kiến thức chuẩn bị 3) Nếu D, E là hai tập lồi, a là một điểm thì các tập sau là những tập lồi D + a := {x + a, x ∈ D}, D − a := {x − a, x ∈ D}, D + E := {x + y, x ∈ D, y ∈ E} , D − E := {x − y, x ∈ D, y ∈ E} . Định nghĩa 1.5. Tập con K của X được gọi là một nón nếu với mọi x ∈ K, mọi λ ≥ 0 thì λx ∈ K. Nón K gọi là nón lồi nếu K vừa là tập lồi vừa là nón. Định nghĩa 1.6. Cho C là một tập lồi trong X, x0 ∈ C. Khi đó tập N (x0 , C) = {t ∈ X ∗ : ht, x − x0 i ≤ 0, ∀x ∈ C} được gọi là nón pháp tuyến của tập C tại điểm x0 . Ví dụ 1.4. Cho C = {x = (x1 , x2 ) ∈ R2 : x1 ≥ 0, x2 ≥ 0} . Xét tại x0 = (0, 0) ∈ C. Ta được  N (x0 , C) = (x∗1 , x∗2 ) ∈ R2 |x∗1 x1 + x∗2 x2 ≤ 0, ∀ (x1 , x2 ) ∈ C .  = (x∗1 , x∗2 ) ∈ R2 |x∗1 ≤ 0, x∗2 ≤ 0 . Định nghĩa 1.7. Hàm f : X → R ∪ {+∞} xác định trên tập lồi X, được gọi là hàm lồi nếu với mọi x1 , x2 ∈ domf , mọi λ ∈ [0, 1] ta có f (λx1 + (1 − λ) x2 ) ≤ λf (x1 ) + (1 − λ) f (x2 ) . Hàm f gọi là hàm lồi chặt trên tập lồi X nếu f (λx1 + (1 − λ) x2 ) < λf (x1 ) + (1 − λ) f (x2 ) 11 Chương 1. Kiến thức chuẩn bị với bất kì x1 , x2 ∈ domf, x1 6= x2 , ∀λ ∈ ]0, 1[ . Ví dụ 1.5. Các hàm số sau là những hàm lồi: 1) Hàm chuẩn của một vector ||x||. 2) Hàm khoảng cách từ một điểm x ∈ X đến tập lồi C cho bởi: d (x, C) = inf ||x − y||. y∈C 3) Hàm chỉ của một tập lồi C IC (x) =   0 nếu x ∈ C,  +∞ nếu ngược lại. Thật vậy với mọi x, y ∈ domIC và mọi λ ∈ [0, 1], ta có IC (x) = 0, IC (y) = 0. Do C lồi nên λx + (1 − λ) y ∈ C. Suy ra IC (λx + (1 − λ) y) = 0 = λIC (x) + (1 − λ) IC (y) . Vậy IC là hàm lồi. Mệnh đề 1.1. Hàm số f xác định trên tập lồi khác rỗng U ⊆ X là hàm lồi khi và chỉ khi epi (f ) là tập lồi. Chứng minh. (=⇒) Giả sử f là hàm lồi trên tập lồi U . Lấy hai điểm bất kì (x1 , α1 ) và (x2 , α2 ) thuộc epi(f ). Theo định nghĩa thì α1 ≤ f (x1 ) và α2 ≤ f (x2 ). Với mọi λ ∈ [0, 1] ta có f (λx1 + (1 − λ) x2 ) ≤ λf (x1 ) + (1 − λ) f (x2 ) ≤ λα1 + (1 − λ) α2 , suy ra (λx1 + (1 − λ) x2 , λα1 + (1 − λ) α2 ) = λ (x1 , α1 ) + (1 − λ) (x2 , α2 ) ∈ epi (f ) . 12 Chương 1. Kiến thức chuẩn bị (⇐=) Ngược lại, giả sử epi(f ) là tập lồi. Vì (x1 , f (x1 )) và (x2 , f (x2 )) đều thuộc epi(f ) nên với mọi λ ∈ [0, 1] ta có λ (x1 , f (x1 )) + (1 − λ) (x2 , f (x2 )) = (λx1 + (1 − λ) x2 ) , λf (x1 ) + (1 − λ) f (x2 ) ∈ epif. Theo định nghĩa của epi (f ) ta có f (λx1 + (1 − λ) x2 ) ≤ λf (x1 ) + (1 − λ) f (x2 ) , ∀λ ∈ [0, 1]. Vậy f là hàm lồi.  Mệnh đề 1.2. Nếu hàm số f xác định trên tập lồi U ⊆ X là hàm lồi thì tập mức dưới Cα (f ) là tập lồi với mọi α ∈ R. Chứng minh. Lấy bất kì x1 , x2 ∈ Cα (f ) và λ ∈ [0, 1]. Khi đó ta có f (λx1 + (1 − λ) x2 ) ≤ λf (x1 ) + (1 − λ) f (x2 ) ≤ λα + (1 − λ) α = α Suy ra λx1 + (1 − λ) x2 ∈ Cα (f ). Vậy Cα (f ) là một tập lồi.  Cho hàm lồi f1 xác định trên tập lồi U1 ⊆ X, hàm lồi f2 xác định trên tập lồi U2 ⊆ X và số thực λ ≤ 0. Các phép toán λf, f1 + f2 , max {f1 , f2 } được định nghĩa như sau: (λf1 ) (x) := λf1 (x) , x ∈ U1 , (f1 + f2 ) (x) := f1 (x) + f2 (x) , x ∈ U1 ∩ U2 , max {f1 , f2 } (x) := max {f1 (x) , f2 (x)} , x ∈ U1 ∩ U2 . Định nghĩa 1.8. Cho hàm f : X → R ∪ {+∞}, C là một tập con của X, một điểm x ∈ C ∩ domf được gọi là một cực tiểu toàn cục của f trên C nếu f (x) ≤ f (x) với mọi x ∈ C. 13 Chương 1. Kiến thức chuẩn bị Đ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 (x) của x sao cho f (x) ≤ f (x) với mọi x ∈ C ∩ U (x). Định lý 1.4. Cho hàm f : X → R ∪ {+∞} là một hàm lồi, C là một tập con của X. Khi đó bất kì điểm cực tiểu địa phương nào của f trên C cũng là cực tiểu toàn cục. Chứng minh. Giả sử x là điểm cực tiểu địa phương của f trên X, khi đó tồn tại lân cận U (x) của x sao cho f (x) ≤ f (x) với mọi x ∈ X ∩ U (x) . Lấy tùy ý y ∈ X, ta có yλ = (1 − λ) x + λy ∈ U (x) với λ ∈ (0, 1) và λ là đủ nhỏ. Suy ra f (x) ≤ f (yλ ) với λ đủ nhỏ. Mặt khác f (yλ ) = (1 − λ) f (x) + λf (y) suy ra λf (x) ≤ λf (y) với λ đủ nhỏ. Vậy f (x) ≤ f (y) với mọi y ∈ X. Suy ra x là cực tiểu toàn cục.  Định nghĩa 1.9. Cho hàm lồi chính thường f : X → R ∪ {+∞}, vector x∗ ∈ X ∗ gọi là dưới gradient của f tại điểm x0 ∈ domf nếu thỏa mãn hx∗ , x − x0 i ≤ f (x) − f (x0 ) , ∀x ∈ X. 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à khả dưới vi phân tại x0 nếu ∂f (x0 ) 6= ∅. Ví dụ 1.6. 1) Dưới vi phân của hàm f (x) = ||x|| là   {x∗ ∈ X ∗ : ||x∗ || ≤ 1} ∂f (x) =  {x∗ ∈ X ∗ : hx∗ , xi = ||x||, ||x∗ || = 1} khi x = 0, khi x 6= 0 Thật vậy, khi x0 = 0 thì x∗ ∈ ∂f (x) khi và chỉ khi hx∗ , xi ≤ ||x||, ∀x ∈ R. Suy ra ||x∗ || ≤ 1. 14 Chương 1. Kiến thức chuẩn bị Khi x0 6= 0 thì x∗ ∈ ∂f (x) khi và chỉ khi hx∗ , x − x0 i ≤ ||x|| − ||x0 ||, ∀x ∈ R. Cho x = 0 ta được hx∗ , −x0 i ≤ −||x0 ||. Cho x = 2x0 ta được hx∗ , x0 i ≤ ||x0 || suy ra hx∗ , x0 i = ||x0 ||. Ta có hx∗ , x0 i = hx∗ , (x + x0 ) − x0 i ≤ ||x + x0 || − ||x0 || suy ra hx∗ , xi ≤ ||x|| suy ta ||x∗ || = 1. Ngược lại, nếu ||x∗ || = 1, hx∗ , x0 i = ||x0 || thì ta có hx∗ , x − x0 i = hx∗ , xi − hx∗ , x0 i ≤ ||x|| − ||x0 ||, ∀x hay x∗ ∈ ∂f (x) . Trong trường hợp riêng, hàm f : R → R cho    [−1, 1]    ∂f (x) = {1}     {−1} bởi f (x) = |x| thì ta được khi x = 0, khi x > 0, khi x < 0. 2) Dưới vi phân của hàm chỉ IC (x) tại x0 ∈ C, trong đó C là một tập lồi khác rỗng là ∂IC (x0 ) = NC (x0 ) (nón pháp tuyến ngoài của C tại x0 ). Thật vậy, với x0 ∈ C, ta có ∂f (x0 ) = ∂IC (x0 ) = {x∗ |hx∗ , x − x0 i ≤ IC (x) , ∀x} . Với x0 ∈ / C thì IC (x0 ) = +∞ nên bất đẳng thức trên luôn đúng. Suy ra ∂f (x0 ) = ∂IC (x0 ) = {x∗ |hx∗ , x − x0 i ≤ IC (x) , ∀x} = NC (x0 ). Vậy dưới vi phân của hàm chỉ IC (x) của tập lồi C tại x0 ∈ C khác rỗng là ∂IC (x0 )=NC (x0 ). Định lý 1.5. Một hàm lồi chính thường f trên X có dưới vi phân khác rỗng tại mỗi điểm x0 ∈ int (domf ) . Định lý 1.6. Cho hàm lồi f : X → R ∪ {+∞}. Khi đó ta có các khẳng định sau: (i) x∗ ∈ ∂f (x0 ) ⇔ (x∗ , −1) ∈ Nepif (x0 , f (x0 )), (ii) ∂f (x0 ) là tập lồi đóng, 15 Chương 1. Kiến thức chuẩn bị (iii) ∂f (x0 ) = {∇f (x0 )} nếu f (x) khả vi tại x0 . Trong đó ∇f (x0 ) là gradien của f tại x0 và ∇f (x0 )∗ là toán tử liên hợp của ∇f (x0 ). Định lý 1.7. (Điều kiện cần và đủ tối ưu) Giả sử C là một tập lồi trong X và f : X → R ∪ {+∞} là hàm lồi. Khi đó điều kiện cần và đủ để x ∈ C là điểm cực tiểu toàn cục của f trên C là 0 ∈ ∂f (x) + NC (x) . Định lý 1.8. Cho f1 , f2 là những hàm lồi chính thường trên Rn , với mỗi x ∈ Rn ta có ∂f1 (x) + ∂f2 (x) ⊂ ∂ (f1 + f2 ) (x) . Định nghĩa 1.10. Cho f : X → R ∪ {+∞}, đạo hàm của f tại điểm x theo phương y ∈ X là: f (x + ty) − f (x) t&0 t f 0 (x; y) := lim nếu giới hạn này tồn tại (hữu hạn hay vô hạn). Ví dụ 1.7. Cho hàm f : R → R xác định bởi f (x) = |x| Nhận xét f là hàm khả vi tại x 6= 0. Ta sẽ xét đạo hàm theo phương tại x = 0. Ta có: f 0 (0, −1) = lim t&0 f (0 + t. (−1)) − f (0) | − t| = lim = 1, t&0 t t f 0 (0, 1) = lim t&0 f (0 + t.1) − f (0) |t| = lim = 1. t&0 t t Định lý 1.9. Nếu f là hàm lồi chính thường trên X thì nó có đạo hàm theo mọi phương, tại mọi x0 ∈ domf và mọi y thì


f x0 + ty − f x0 ≥ f 0 x0 , y . 16 Chương 1. Kiến thức chuẩn bị Định lý 1.10. Nếu f là hàm lồi chính thường trên tập lồi U ⊆ X thì nó có đạo hàm theo mọi hướng d ∈ X \ {0} tại mọi điểm x0 ∈ domf và f 0 (x0 , d) ≤ f (x0 + d) − f (x0 ) . Chứng minh. Cho vector d ∈ Rn . Do f là hàm lồi nên hàm một biến ϕ (t) = f (x0 + td) là hàm lồi trên {t|x0 + td} ∈ X. Theo định nghĩa của đạo hàm theo hướng, ta có ϕ (t) − ϕ (0) f (x0 + td) − f (x0 ) = lim = ϕ0+ (0) . t&0 t&0 t t f 0 (x0 , d) = lim Nếu với mọi t > 0 mà x0 + td ∈ / domf thì ta có f (x0 + td) = ϕ (t) = +∞ và ϕ0+ (0) = +∞. Do đó kết luận của định lý là đúng. Nếu tồn tại t > 0 để x0 + td ∈ domf thì với mọi t1 mà 0 < t1 < t ta có t1 t Vì ϕ là hàm lồi nên ϕ (t1 ) ≤ < 1 và t1 = t1 ϕ (t) t t1 t t + 1− t1 t + 1−
t1 t
0. ϕ (0) . Suy ra ϕ (t1 ) − ϕ (0) ϕ (t) − ϕ (0) . ≤ t1 t  Tức là dãy ϕ (t) − ϕ (0) t  không tăng khi t → 0+ . Do đó tồn tại giới hạn ϕ (t) − ϕ (0) = ϕ0+ (0) . t&0 t lim Suy ra với t > 0 ta luôn có
ϕ (t) − ϕ (0) ≤ ϕ0+ (0) = f 0 x0 , d . t Lấy t = 1 ta có ϕ (t) − ϕ (0) = f (x0 + d) − f (x0 ) ≤ f 0 (x0 , d) . 17  Chương 2 Một số đặc trưng cận sai số của các hàm nửa liên tục dưới Trong chương này sẽ trình bày khái niệm cơ bản về cận sai số của các hàm nửa liên tục dưới. Sau đó chúng tôi trình bày điều kiện đủ cho sự tồn tại cận sai số, đó là điều kiện độ dốc mạnh, điều kiện dưới vi phân và toán tử dưới vi phân trừu tượng. 2.1 Khái niệm cận sai số Trong phần này chúng ta xét (X, d) là không gian metric và hàm f : X → R ∪ {+∞} là hàm nửa liên tục dưới. Với U ⊂ X và r ∈ ]0, +∞] (t.ư, r ∈ [0, +∞[), ta định nghĩa Br (U ) (t.ư, Br (U ) ) là lân cận mở (đóng) của U : Br (U ) = {x ∈ X : d (x, U ) < r} Br (U ) = {x ∈ X : d (x, U ) ≤ r} , 18