Download miễn phí Luận văn Dưới vi phân của hàm lồi và ứng dụng trong tối ưu hoá không trơn
Mục lục
Mở đầu 2
Chương 1: Dưới vi phân 5
1.1. Định nghĩa và kí hiệu . . . . . . . . . . . . . . . . . . . . 5
1.2. Một số tính chất cơ bản của dưới vi phân . . . . . . . . . 6
1.3. Phép toán về dưới vi phân . . . . . . . . . . . . . . . . . 12
Chương 2: Điều kiện tồn tại nghiệm tối ưu 18
2.1. Sự tồn tại nghiệm tối ưu . . . . . . . . . . . . . . . . . . 18
2.2. Các bài toán tối ưu . . . . . . . . . . . . . . . . . . . . . 22
2.3. Bài toán tối ưu không ràng buộc . . . . . . . . . . . . . 23
2.3.1 Điều kiện tối ưu cấp 1 . . . . . . . . . . . . . . . 24
2.3.2 Điều kiện tối ưu cấp 2 . . . . . . . . . . . . . . . 25
2.4. Bài toán tối ưu có ràng buộc . . . . . . . . . . . . . . . . 40
2.4.1 Điều kiện tối ưu cấp 1 . . . . . . . . . . . . . . . 44
2.4.2 Điều kiện tối ưu cấp 2 . . . . . . . . . . . . . . . 47
Kết luận 62
Tài liệu tham khảo 63
Để 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:
g buộc mà trênđó đạo hàm của hàm số triệt tiêu. Tại những điểm này mà ta sử dụng
những điều kiện liên quan tới đạo hàm bậc nhất để suy ra hàm đạt giá
trị tối ưu thì những điều kiện đó được gọi là điều kiện đủ tối ưu cấp
một. Tiếp theo, nếu hàm số có đạo hàm bậc hai và tại những điểm của
tập con này, đạo hàm bậc hai dương chặt (hay âm chặt) thì điểm ấy
chính là nghiệm tối ưu của bài toán. Điều kiện này được gọi là điều kiện
đủ tối ưu cấp hai.
Mục đích của chương này là tìm các điều kiện cần và đủ để bài
toán tối ưu không trơn có nghiệm dựa trên các thông tin về các tập dưới
vi phân và ma trận Hesian. Trước hết ta nhắc lại khái niệm về các loại
nghiệm của bài toán tối ưu.
Cho X là không gian tôpô tuyến tính lồi địa phương Hausdorff và D ⊂ X
là tập hợp khác rỗng. Xét hàm f : D → R, ta có
Định nghĩa 2.1.
i) x0 ⊂ D là điểm cực tiểu ( cực tiểu chặt ) của f trên D nếu
f(x0) ≤ f(x), ∀x ∈ D ( f(x0) < f(x), ∀x ∈ D, x 6= x0 ).
ii) x0 ∈ D được gọi là điểm cực tiểu địa phương nếu tồn tại lân cận U
chứa x0 để các bất đẳng thức trên thoả mãn với mọi x ∈ U ∩D.
19
Nhiều khi ta sử dụng kí hiệu
f(x0) = min
x∈D
f(x) (P )
chung cho các loại tối ưu trên.
Bài toán tìm cực đại của một hàm trên tập cho trước cũng được phát
biểu một cách tương tự. Nhưng để ý
min
x∈D
f(x) = −max
x∈D
(−f(x))
ta suy ra bài toán cực đại hoàn toàn có thể quy về bài toán cực tiểu. Do
đó trong lý thuyết tối ưu, nói chung ta chỉ cần xây dựng lý thuyết giải
cho một trong hai loại: cực tiểu hay cực đại. Trong chương này ta chỉ
quan tâm tới bài toán cực tiểu.
Chú thích:
Nếu x0 ∈ D là cực tiểu của f trên D thì x0 còn được gọi là cực tiểu toàn
cục của f trên D. Khi ấy bài toán (P ) được gọi là bài toán tối ưu toàn
cục. Trái lại, bài toán (P ) được gọi là bài toán tối ưu địa phương.
Mệnh đề và định lý sau đây cho ta những điều kiện tổng quát nhất
về sự tồn tại nghiệm tối ưu của các bài toán dạng trên.
Mệnh đề 2.1. Điều kiện cần và đủ để tồn tại nghiệm cực tiểu của hàm
f là tập hợp
f(D)+ = {t ∈ R|f(x) ≤ t, x ∈ D }
đóng và có một cận dưới hữu hạn.
Chứng minh. Giả sử x0 là nghiệm tối ưu của bài toán (P ). Khi đó ta có
f(x0) = min
x∈D
f(x), f(D)+ = [f(x0),+∞).
Hiển nhiên f(D)+ là tập đóng và nhận f(x0) là một cận dưới.
Ngược lại, nếu tập f(D)+ có một cận dưới hữu hạn thì cận dưới lớn nhất
20
( hay infimum ) của tập này là hữu hạn và ta ký hiệu nó là t0. Theo định
nghĩa của infimum, t ≥ t0 với mọi t ∈ f(D)+ và tồn tại {tn} ⊂ f(D)+
hội tụ đến t0. Vì f(D)+ là tập đóng nên t0 ∈ f(D)+. Theo định nghĩa của
tập f(D)+ tồn tại x0 ∈ D sao cho t0 ≥ f(x0). Hiển nhiên f(x0) ∈ f(D)+
và vì t0 là cận dưới lớn nhất của tập f(D)+ nên ta có f(x0) ≥ t0. Suy
ra t0 = f(x0). Điều đó chứng tỏ x0 là nghiệm tối ưu của bài toán (P ).
Định lý 2.1. Cho D là tập compact khác rỗng. Khi đó nếu f nửa liên
tục dưới trên D thì f đạt cực tiểu trên D.
Chứng minh. Theo Mệnh đề 2.1, ta chỉ cần chỉ ra f(D)+ là tập đóng và
bị chặn dưới. Thật vậy giả sử tập này không bị chặn dưới tức là tồn tại
dãy điểm {xn} ⊂ D sao cho
lim
n→∞ f(xn) = −∞.
Vì D là tập compact, không mất tính tổng quát ta có thể giả thiết
lim
n→∞xn = x0 ∈ D.
Ta thấy rằng giá trị của hàm f tại x0 là hữu hạn và hàm f là nửa liên
tục dưới, do đó không thể có
f(x0) ≤ lim
n→∞ f(xn) = −∞.
Vậy f(D)+ bị chặn dưới. Đặt t bằng cận dưới của tập này. Theo định
nghĩa của infimum, t cũng là infimum của hàm f trên D. Do vậy tồn tại
{xn} ⊂ D sao cho
lim
n→∞ f(xn) = t.
Vì D compact nên limn→∞ xn = x0 ∈ D. Do f nửa liên tục dưới kéo theo
t = lim
n→∞ f(xn) ≥ f(x0).
21
Từ đây ta suy ra t = f(x0) và x0 là cực tiểu của hàm f trên tập D.
2.2 Các bài toán tối ưu
Cho hàm f : D → R. Bài toán
min
x∈D
f(x) (P )
được gọi là bài toán tối ưu không ràng buộc.
Cho các hàm h1, ..., hk : D → R, g1, ..., gm : D → R. Bài toán
min
x∈D0
f(x) (CP )
với
D0 = { x ∈ D | gi(x) ≤ 0, hj(x) = 0, ∀ i = 1,m; j = 1, k }
được gọi là bài toán tối ưu có ràng buộc. Tập D0 được gọi là tập chấp
nhận được.
Định nghĩa 2.2. Điểm x0 ∈ D được gọi là nghiệm tối ưu của bài toán
(CP ) nếu nó là cực tiểu của hàm f trên tập chấp nhận được D0. Khi đó
f(x0) được gọi là giá trị tối ưu của bài toán.
Định lý 2.2. Cho D là tập compact trong không gian X, f, g1, ..., gm là
các hàm nửa liên tục dưới và h1, ..., hk là các hàm liên tục trong D. Khi
đó bài toán (CP ) có nghiệm nếu D 6= ∅.
Chứng minh. Định lý được chứng minh nhờ tính nửa liên tục dưới của
các hàm số gi, tính liên tục của các hàm hj để đảm bảo tính compact
của tập D0 và Định lý 2.1.
22
2.3 Bài toán tối ưu không ràng buộc
Trong phần này, chúng ta sẽ nghiên cứu các điều kiện tối ưu đối với hàm
hợp
φ(x) = f(x) + h(c(x)) (2.1)
với f(x) : Rn → R1, c(x) : Rn → Rm là các hàm trơn thuộc lớp C1, còn
h(c) : Rm → R1 là các hàm lồi nhưng không trơn thuộc lớp C0 và ở đây
ta nghiên cứu hàm h(c) có dạng
h(c) = max
i
cThi + bi (2.2)
với các véctơ hi và các số bi cho trước.
Như vậy h(c) là một hàm lồi đa diện và đồ thị của nó được tạo bởi một
số hữu hạn các siêu phẳng tựa cThi + bi. Hầu hết sự quan tâm hướng về
ba trường hợp đặc biệt sau đây mà trong đó bi = 0 với mọi i
Trường hợp 1 : h(c) = maxi ci
Trường hợp 2 : h(c) = ‖c‖∞
Trường hợp 3 : h(c) = ‖c‖1
Khi đó dưới vi phân của các hàm trên lần lượt là:
∂ max
i
ci = { λ :
∑
λi = 1, λ ≥ 0, ci < max
i
ci ⇒ λi = 0 }.
∂‖c‖∞ = { λ : c 6= 0 ⇒
∑
λi = 1
|ci| < ‖ci‖∞ ⇒ λi = 0
|ci| = ‖ci‖∞ ⇒ λici ≥ 0
c = 0 ⇒
∑
λi ≤ 1 }.
∂‖c‖1 = { λ : |λi| ≤ 1, ci 6= 0 ⇒ λi = signci }.
23
2.3.1 Điều kiện tối ưu cấp 1
Cho x(k) → x′ là dãy định hướng với δ(k) ↓ 0 và s(k) → s ( tức là
x(k) = x′ + δ(k)s(k) ).
Theo khai triển Taylor ta có
f (k) = f ′ + δ(k)g′Ts(k) + 0(δ(k))
trong đó g′ = ∇f(x′). Từ đó
f (k) − f ′
δ(k)
→ g′Ts
và
c(k) = c′ + δ(k)A′Ts(k) + 0(δ(k)),
với A′ là ma trận có cột i là ∇ci(x′). Vì thế c(k) → c′ là dãy định hướng
trong Rm với
c(k) − c′
δ(k)
→ A′Ts.
Từ Bổ đề 1.6 với h(c) ta có
lim
k→∞
φ(k) − φ′
δ(k)
= max
λ∈∂h′
sT (g′ + A′λ) (2.3)
và điều này dẫn tới đạo hàm theo hướng tại x′ là theo hướng s đối với
hàm φ(x) trong (2.1).
Từ (2.3) nếu x∗ là cực tiểu địa phương của φ(x) thì φ(k) ≥ φ∗ với mọi k
đủ lớn và do đó
max
λ∈∂h∗
sT (g∗ + A∗λ) ≥ 0, ∀s : ‖s‖ = 1.
Đây là điều kiện cần cấp 1 đối với cực tiểu địa phương và cũng giống
như (1.10), nó có thể được hiểu là đạo hàm theo mọi hướng là không
âm. Một lần nữa ta đưa ra kết quả tương tự là
0 ∈ ∂φ(x∗) = { γ : γ = g + Aλ, ∀λ ∈ ∂h }x=x∗. (2.4)
24
Do đó tập ∂φ∗ xác định, là tập lồi, compact nhưng không khả dưới vi
phân vì φ có thể không là hàm lồi.
Để phát biểu điều kiện (2.4) theo một cách khác, ta đưa ra hàm
Lagrange
L(x, λ) = f(x) + λT c(x).
Khi đó một phát biểu tương tự (2.4) là
Định lý 2.3. (Điều kiện cần cấp một)
Nếu x∗ là cực tiểu của φ(x) thì tồn tại một véctơ λ∗ ∈ ∂h∗ thoả m