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

∈ 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