Download miễn phí 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
Mụ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
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung tài liệu:
∈ Rn sao chof(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...