Tối ưu hóa phần 9

Định lý 18. Cho một tập lồi khác rỗng S ⊂ Rn và f: S → R là hàm lồi. Lúc đó, ∀ x ∈ S và hướng bất kỳ d ∈ R n sao cho x + λd ∈ S với λ 0 đủ nhỏ, luôn tồn tại đạo hàm theo hướng: f (x + λd) − f (x) . f/( x ,d) = lim λ→0+ λ Chứng minhChọn λ2 λ1 0 và đủ nhỏ. Do f là hàm lồi nên ta có:⎡λ ⎛ ⎛ λ ⎞ ⎤ λ λ ⎞ f ( x + λ1d...
Nội dung trích xuất từ tài liệu:
Tối ưu hóa phần 9 Định lý 18. Cho một tập lồi khác rỗng S ⊂ Rn và f: S → R là hàm lồi. Lúc đó, ∀ x ∈ S vàhướng bất kỳ d ∈ R n sao cho x + λd ∈ S với λ > 0 đủ nhỏ, luôn tồn tại đạo hàm theo hướng: f (x + λd) − f (x)f/( x ,d) = lim . λ λ→0+ Chứng minh Chọn λ2 > λ1 > 0 và đủ nhỏ. Do f là hàm lồi nên ta có: ⎡λ λ⎞⎤ λ ⎛ ⎛ λ⎞ f ( x + λ1d ) = f ⎢ 1 ( x + λ 2d ) + ⎜ 1 − 1 ⎟ x ⎥ ≤ 1 f ( x + λ 2d ) + ⎜ 1 − 1 ⎟ f ( x ) . ⎢ λ2 λ2 ⎠ ⎥ λ2 λ2 ⎠ ⎝ ⎝ ⎣ ⎦ f ( x + λ1d ) − f ( x ) f ( x + λ 2d ) − f ( x ) ≤ Từ đây suy ra: . Như vậy, hàm số λ1 λ2[ f (x + λd) − f (x)] / λ phụ thuộc λ > 0 là hàm không giảm. Bởi vậy ta có giới hạn: f ( x + λd ) − f ( x ) f ( x + λd ) − f ( x ) = inf lim (đpcm). λ λ + λ> 0 λ→03.2. Dưới vi phân của hàm lồi Định nghĩa 9. Cho f: S → R là hàm lồi. Lúc đó: Epigraph của f là tập hợp Epi f = {(x, y) : x ∈ S, y ≥ f (x)} ⊂ Rn+1. Hypograph của f là tập hợp Hyp f = {(x, y) : x ∈ S, y ≤ f (x)} ⊂ Rn+1. Xem minh họa hình VI.7. y Epi f y=f(x) x Hyp f 0 Hình VI.7. Minh họa Epigraph và Hypograph Có thể chứng minh được tính chất sau đây: Cho f: S →R là hàm lồi, lúc đó Epi f là tập lồivà ngược lại. Định nghĩa 10 (khái niệm dưới vi phân). Xét tập lồi khác rỗng S ⊂ Rn và f: S → R là hàm lồi. Lúc đó véc tơ ξ ∈ Rn được gọi là dướivi phân của f tại x nếu f (x) ≥ f (x) + ξT (x − x) , ∀x ∈ S . Ví dụ 4. i) Xét hàm y = f(x) = x2. Lúc đó véc tơ ξ = (2 x ) ∈ R1 chính là dưới vi phân củahàm đã cho tại x (trên hình VI.8a: ξT = tgα ). 153 y y π 4 f(x) f(x) ξT = tgα α f (x) f (x) x x x x x x 0 0 b) f(x) = ⎪x⎪ a) f(x) = x2 Hình VI.8. Minh họa hình học dưới vi phân ii) Xét hàm y = f(x) = ⎪x⎪. ∀ x ≠ 0, véc tơ ξ = sign x ∈ R1 chính là dưới vi phân duy nhất π (trên hình VI.8b: ξT = tgcủa hàm đã cho tại x = 1 tại x > 0). Còn tại 4x = 0, tồn tại vô số dưới vi phân ξ ∈ [–1, 1] ⊂ R1. Định lý 19 (về sự tồn tại dưới vi phân). Cho f: S → R là hàm lồi. Lúc đó với ∀ x ∈ int S luôn tồn tại véc tơ ξ sao cho siêu phẳng {(x, y) : y = f (x) + ξ (x − x)} ( x,f (x)) ...