ĐIỀU KIỆN TỐI ƯU CHO MỘT SỐ LỚP BÀI TOÁN TỐI ƯU HAI CẤP
NGUYỄN LÊ DUY
Trang nhan đề
Lời cảm ơn
Mục lục
Lời nói đầu
Chương_1: Một số kiến thức cơ bản
Chương_2: Khái niệm về bài toán tối ưu hai cấp tổng quát
Chương_3: Điều kiện tối ưu cho bài toán hai cấp hữu hạn
Chương_4: Điều kiện tối ưu cho bài toán hai cấp vô hạn
Kết luận
Tài liệu tham khảo
Möc löc
Líi c£m ìn 1
Líi nâi ¦u 2
1 Mët sè ki¸n thùc cì b£n 5
1.1 Mët sè ki¸n thùc cì b£n v· gi£i t½ch lçi . . . . . . . . . . . . . . . . . 5
1.2 H*m Lipschitz v* d÷îi vi ph¥n Clarke . . . . . . . . . . . . . . . . . . 11
1.3 Mët sè ki¸n thùc cì b£n v· gi£i t½ch a trà . . . . . . . . . . . . . . . 12
1.4 D÷îi vi ph¥n, nân ph¡p tuy¸n v* èi ¤o h*m Mordukhovich . . . . . 16
2 Kh¡i ni»m v· b*i to¡n tèi ÷u hai c§p têng qu¡t 22
2.1 Giîi thi»u b*i to¡n . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.2 Mæ h¼nh c¡c b*i to¡n thüc t¸ . . . . . . . . . . . . . . . . . . . . . . 27
3 i·u ki»n tèi ÷u cho b*i to¡n hai c§p húu h¤n 33
3.1 i·u ki»n tèi ÷u khi b*i to¡n c§p d÷îi lçi . . . . . . . . . . . . . . . . 34
3.2 i·u ki»n tèi ÷u sû döng d÷îi vi ph¥n Mordukhovich . . . . . . . . . 49
3.3 i·u ki»n tèi ÷u sû döng d÷îi vi ph¥n Clarke . . . . . . . . . . . . . 62
4 i·u ki»n tèi ÷u cho b*i to¡n hai c§p væ h¤n 80
4.1 B*i to¡n hai c§p væ h¤n . . . . . . . . . . . . . . . . . . . . . . . . . 80
4.2 i·u ki»n tèi ÷u cho b*i to¡n DC væ h¤n . . . . . . . . . . . . . . . . 81
4.3 i·u ki»n tèi ÷u cho b*i to¡n hai c§p væ h¤n . . . . . . . . . . . . . . 87
3
4.4 i·u ki»n c¦n v* õ cho b*i to¡n hai c§p lçi ìn gi£n . . . . . . . . . 93
K¸t luªn 99
T*i li»u tham kh£o 101
104 trang |
Chia sẻ: maiphuongtl | Lượt xem: 1891 | Lượt tải: 0
Bạn đang xem trước 20 trang tài liệu Luận văn Điều kiện tối ưu cho một số lớp bài toán tối ưu hai cấp, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
toán một cấp (SP )ϕ tương đương bài toán (BLPP) mà không cần giả thiết
lồi cho bài toán cấp dưới (P )x. Tuy nhiên lại gặp hai vấn đề lớn, đầu tiên là hàm
ϕ(x) không khả vi (dù cho hàm f, gi đã khả vi liên tục) do đó (SP )ϕ là bài toán
không trơn (nonsmooth problem). Để sử dụng công thức nhân tử Lagrange mở rộng
Clarke, thì hàm ϕ(x) phải liên tục Lipschitz, để ϕ(x) liên tục Lipschitz thì bài toán
cấp dưới phải thỏa (MFCQ) tại nghiệm tối ưu.
Vấn đề khó khăn tiếp theo là bởi cấu trúc đặc thù cho nên (MFCQ) rất tiếc lại
không thỏa mãn cho (SP )ϕ.
Do vậy cần có những CQ yếu hơn (MFCQ) (điều kiện partially calm chẳng hạn).
Mục đích của chúng ta trong hướng tiếp cận (4) này, là thiết lập " điều kiện
cần tối ưu dạng KKT cho (BLPP) " mà
• không sử dụng các yếu tố: giả thiết lồi ở bài toán cấp dưới, giả thiết tập nghiệm
Ψ(x) là singleton, giả thiết (MFCQ) cho bài toán cấp dưới.
• có sử dụng các yếu tố: điều kiện calm (theo Clarke) hay partial calmness hoặc
các điều kiện CQ mở rộng khác.
Ta trình bày theo thứ tự sau:
• Xây dựng hàm ψ và bài toán (SP)ψ
• Điều kiện tối ưu dạng KKT dưới giả thiết calm (Clarke)
• Điều kiện tối ưu dạng KKT dưới giả thiết CQ mở rộng
• Điều kiện tối ưu khi hàm f(x, y)− ϕ(x) lõm
63
(1) Xây dựng hàm ψ và bài toán (SP)ψ
Đặt Y (x) := {y ∈ Rm|gi(x, y) ≤ 0, i ∈ I} là tập chấp nhận được của (Px), (x, y)
là nghiệm tối ưu địa phương của (BLPP). Giả thiết ánh xạ Y bị chặn đều tại x
nghĩa là tồn tại một lân cận U của x sao cho tập
⋃
x∈U
Y (x) bị chặn. Tính bị chặn đều
của Y tại x đảm bảo cho ϕ tồn tại. Ta gọi U(x, y) là một lân cận mở bị chặn của
nghiệm tối ưu (x, y), U := {x ∈ Rn|∃ y sao cho (x, y) ∈ U(x, y)} và tập
⋃
x∈U
Y (x)
bị chặn. Khi đó ϕ khác rỗng và compac, chứa một lân cận mở của cl
⋃
x∈U
Y (x) với
clA là tập đóng của tập A.
Bây giờ ta đặt hàm σ(x, y, y′) := min{f(x, y) − f(x, y′),−max
i∈I
gi(x, y
′)} Xây
dựng hàm ψ như sau:
ψ(x, y) := max
y′∈ϕ
σ(x, y, y′). (3.88)
Bổ đề 3.3.1 ([22], Bổ đề 2.1)
(i) {x ∈ U, y ∈ Y (x)|f(x, y)− ϕ(x) < 0} = {x ∈ U, y ∈ Y (x)|ψ(x, y) < 0}
(ii) {x ∈ U, y ∈ Y (x)|f(x, y)− ϕ(x) = 0} ⊆ {x ∈ U, y ∈ Y (x)|ψ(x, y) = 0}
(iii) Lấy y ∈ Ψ(x) thì tập nghiệm của bài toán ψ(x, y) cho bởi Ψ(x).
Chứng minh
(i) Lấy x ∈ U, y ∈ Y (x)
Do ϕ compac nên ψ(x, y) < 0 ⇐⇒ σ(x, y, y′) < 0, ∀y ∈ ϕ, mà −max
i∈I
gi(x, y
′) ≥
0, ∀y′ ∈ ϕ nên
ψ(x, y) < 0 ⇐⇒ f(x, y) < f(x, y′), ∀y′ ∈ ϕ
Mặt khác Y (x) ⊂ ϕ nên điều này tương đương f(x, y) < f(x, y′), ∀y′ ∈ Y (x), kết
hợp định nghĩa của ϕ(x) nên điều này tương đương f(x, y)− ϕ(x) < 0, ∀y ∈ Y (x)
nghĩa là đẳng thức đầu được chứng minh.
Ngoài ra theo định nghĩa của hàm ψ ta suy ra tập thứ nhất = ∅, do đó suy ra (i).
(ii) Lấy x ∈ U, y ∈ Y (x) sao cho f(x, y) − ϕ(x) = 0 =⇒ y là nghiệm cực tiểu toàn
cục của (Px).
Nếu ψ(x, y) < 0 thì mâu thuẫn (i)
64
Nếu ψ(x, y) > 0 thì cũng không xảy ra. Thật vậy ψ(x, y) > 0, do định nghĩa của
hàm ψ trong (3.88)
=⇒ ∃ y′ ∈ ϕ sao choσ(x, y, y′) > 0
=⇒ f(x, y′) < f(x, y)∀y′ ∈ ϕ
=⇒ f(x, y′) < f(x, y) ∀y′ ∈ Y (x) ⊂ ϕ,
điều này mâu thuẫn với y là nghiệm cực tiểu toàn cục của (Px)
do đó ψ(x, y) = 0 =⇒ (ii)
(iii) Lấy y ∈ S(x).
Ta có ψ(x, y = maxy′∈ϕ σ(x, y, y′) với
σ(x, y, y′) = min{f(x, y)− f(x, y′), −max
i∈I
gi(x, y
′)}
Vì Ψ(x) là tập nghiệm của bài toán (Px), kết hợp (i), (ii) ta =⇒ (iii) ¤
Ta xây dựng tiếp bài toán tối ưu mới, kí hiệu là (SP )ψ, xác định như sau:
(SP)ψ min F (x, y)
sao cho ψ(x, y) ≤ 0,
gi(x, y) ≤ 0 i ∈ I,
Gk(x, y) ≤ 0 k ∈ K.
Bài toán này là bài toán tối ưu một cấp, xuất hiện để khắc phục những khó khăn
đã được phân tích của bài toán (SP )ϕ. Rõ ràng về cơ bản thì hai bài toán này như
nhau, và chỉ khác ở ràng buộc thứ nhất. Nhờ Bổ đề 3.3.1 mà bài toán (SP )ψ có
mối liên hệ với bài toán gốc (BLPP) như sau:
Nếu (x, y) là nghiệm tối ưu địa phương của (BLPP) thì nó cũng là nghiệm tối ưu
địa phương của (SP )ψ
65
(2) Điều kiện tối ưu dạng KKT dưới giả thiết calm
Trước tiên, ta thiết lập hàm Lagrange dạng Fritz John của bài toán cấp dưới
L(x, y, α, γ) = αf(x, y) +
∑
i∈I
γigi(x, y)
với số α ∈ R và γ ∈ Rp, và tập nhân tử dạng Fritz John của bài toán cấp dưới (Px)
tại y
FJ(x, y) = {(α, γ) ∈ R× Rp|(α, γ) ≥ 0, || (α, γ) ||1 = 1,
∇yL(x, y, α, γ) = 0,
∑
i∈I
γigi(x, y) = 0},
trong đó ||x||1 =
∑n
i=1 |xi| là chuẩn vectơ x trong Rn và ∇y kí hiệu là đạo hàm của
hàm Lagrange L(.) theo biến y.
Dễ thấy tập FJ(x, y) là đa diện lồi khác rỗng (khái niệm này xem chương 1, Mục
1.3).
Mệnh đề sau là kết quả của Bổ đề 3.3.1 ở trên và trong ([22], Mệnh đề 2.2)
Mệnh đề 3.3.1 Giả sử (x, y) là nghiệm tối ưu địa phương của bài toán tối ưu hai
cấp (BLPP).
Khi đó hàm ψ(x, y) liên tục Lipschitz tại (x, y), và
Gradient mở rộng Clarke tại (x, y) có xấp xỉ trên:
∂o ψ(x, y) ⊆ coW (x, y), (3.89)
trong đó
W (x, y) :=
⋃
y′∈Ψ(x)
{α∇f(x, y)− (∇xL(x, y′, α, γ, 0)|(α, γ) ∈ FJ(x, y′)}. (3.90)
Bây giờ áp dụng kết quả củaMệnh đề 3.3.1 vừa nêu ta có hàm ψ liên tục Lipschitz
tại nghiệm tối ưu địa phương, kết hợp với các công thức nhân tử Lagrange mở rộng
trong [5, Mệnh đề 6.4.4] với giả thiết calmness trong [20, Định nghĩa 6.4.1],
và Định lý Carathéodory, ta suy ra điều kiện tối ưu dạng KKT cho (BLPP).
66
Kết quả này tương tự như (mục 3.2, - bài toán trơn) , cách chứng minh xem trong
[[22], Mệnh đề 2.3] và [[5], Định lý 6.5.2]
Định lý 3.3.1 (Điều kiện cần KKT dưới giả thiết calm cho (BLPP)) Giả
sử (x, y) là nghiệm tối ưu địa phương của (BLPP) với S(x) 6= ∅ và bài toán (SP )ψ
là calm tại (x, y) theo nghĩa Clarke (xem [5], Định nghĩa 6.4.1).
Khi đó
tồn tại các nhân tử µ ∈ R+, η ∈ Rp+, β ∈ Rq+ sao cho
0 ∈ ∇F (x, y) + µ coW (x, y) +
∑
i∈I(x,y)
ηi∇gi(x, y) +
∑
k∈K(x,y)
βk∇Gk(x, y)
trong đó I(x, y) := {i ∈ I|gi(x, y) = 0}, K(x, y) := {k ∈ K|Gk(x, y) = 0}. Tương
đương, tồn tại λi ≥ 0, yi ∈ S(x), (αi, γi) ∈ FJ(x, yi), i = 1, . . . , n + m + 1, và
η ∈ Rp+, β ∈ Rq+ sao cho
0 = ∇F (x, y) +
∑
i∈I(x,y)
ηi∇gi(x, y) +
∑
k∈K(x,y)
βk∇Gk(x, y)
+
n+m+1∑
i=1
λi
[
αi∇f(x, y)−
(
∇xL(x, yi, αi, γi), 0
)]
.
(3) Điều kiện tối ưu dạng KKT dưới giả thiết CQ mở rộng
Trong mục này, ta sẽ thiết lập điều kiện tối ưu dạng KKT dưới giả thiết một
trong các CQs được nêu ra sau đây.
Khi điều kiện partially calm hoặc calm không thỏa mãn, ta phải xây dựng một loạt
các điều kiện CQ khác. Ta có thể tóm gọm nội dung mục này trong định lý sau:
Định lý 3.3.2 [22, Định lý 3.1]( Điều kiện cần tối ưu và mối quan hệ giữa
các CQ) Giả sử (x, y) là một nghiệm tối ưu địa phương của bài toán (BLPP) với
Ψ(x) 6= ∅.
(i) Khi đó dưới giả thiết một trong các CQs thỏa, thì (x, y) thỏa điều kiện dạng
67
KKT, nghĩa là:
0 ∈ ∇F (x, y) + cl cone
[
W (x, y) ∪
⋃
i∈I(x,y)
{
∇gi(x, y)
}
∪
⋃
k∈K(x,y)
{
∇Gk(x, y)
}]
.
(3.91)
(ii) Hơn nữa mối quan hệ giữa các CQs được miêu tả như sau:
(1.) N. weak reverse convex CQ =⇒ N. AHU CQ =⇒ N. Zangwill CQ =⇒ N. Kuhn
Tucker CQ =⇒ N. Abadie CQ,
(2.) N. AHU CQ =⇒ E. AHU CQ, N. Zangwill =⇒ E. Zangwill CQ, N. Kuhn
Tucker CQ =⇒ E. Kuhn Tucker CQ, N. Abadie CQ =⇒ E. Abadie CQ,
(3.) E. AHU CQ =⇒ E. Zangwill CQ =⇒ E. Kuhn Tucker CQ =⇒ E. Abadie CQ.
N. viết tắt của nonsmooth (không trơn), E. viết tắt của extend (mở rộng).
Các điều kiện định tính ràng buộc CQs
Ta sử dụng định nghĩa giả lõm và ∂ − giả lõm sau đây.
Định nghĩa 3.3.1 ([22], hàm giả lõm (pseudoconcave function)) Cho D ⊂
Rn là tập lồi. Đặt
C1 := {f : D → R|f liên tục và các đạo hàm riêng của f liên tục trên D }
Kí hiệu ∇f(x) là đạo hàm hàm số f theo x.
Một hàm f : D → R, ∈ C1 được gọi là giả lồi (pseudoconvex) nếu ∀x1, x2 ∈ D và
một hàm số thực k(x1, x2) > 0 sao cho:
(x1 − x2)T∇f(x2) ≤ k(x1, x2) [f(x1)− f(x2)]
Hàm f : D → R, ∈ C1 được gọi là giả lõm (pseudoconcave) nếu (−f) là hàm giả
lồi.
Định nghĩa 3.3.2 ([22], hàm ∂− giả lõm) Cho hàm f : Rn → R, x ∈ Rn
sao cho f Lipschitz địa phương tại x. Hàm f được gọi là ∂ − giả lõm tại x nếu
∀x ∈ Rn, max
w∈∂of(x)
wT (x− x) ≤ 0 =⇒ f(x) ≤ f(x), trong đó ∂of(.) là gradient mở
rộng Clarke.
68
Đặt h(x, y) := f(x, y)−ϕ(x) và giả sử (x, y) là nghiệm chấp nhận được của bài toán
(SP )ψ.
N. weak Reverse convex CQ
Ta nói N. weak Reverse convex CQ thỏa tại (x, y) nếu
• h(x, y) là ∂− giả lõm tại (x, y) với ∂h(x, y) ⊆ ∂ψ(x, y), và
• gi(x, y) giả lõm tại (x, y) với i ∈ I(x, y) = {i ∈ I|gi(x, y) = 0},
• Gk(x, y) giả lõm tại (x, y) với k ∈ K(x, y) = {k ∈ K|Gk(x, y) = 0}.
N. AHU CQ
Ta nói N. AHU CQ thỏa tại (x, y) nếu
h(x, y) là ∂− giả lõm tại (x, y) với ∂h(x, y) ⊆ ∂ψ(x, y), và
∃v sao cho
• wTv ≤ 0 ∀w ∈ ∂ψ(x, y)
• ∇gi(x, y)Tv ≤ 0 ∀i ∈ Λ
• ∇gi(x, y)Tv < 0 ∀i ∈ I(x, y) \ Λ
trong đó Λ := {i ∈ I(x, y)|gi giả lõm tại (x, y)}
• ∇Gk(x, y)Tv ≤ 0 ∀k ∈ Γ
• ∇Gk(x, y)Tv < 0 ∀k ∈ K(x, y) \ Γ
trong đó Γ := {k ∈ K(x, y)|Gk giả lõm tại (x, y)}
Đối với 3 CQs còn lại, trước hết ta gọi Θ là tập chấp nhận được của (BLPP) và giả
sử (x, y) là nghiệm chấp nhận được của (BLPP) nghĩa là (x, y) ∈ Θ.
Định nghĩa 3.3.3 ([22], Nón tuyến tính không trơn (nonsmooth linearization cone))
Nón tuyến tính không trơn của tập chấp nhận được Θ tại (x, y), xác định bởi
L((x, y),Θ) := {v|wTv ≤ 0w ∈ ∂ψ(x, y), ∇gi(x, y)Tv ≤ 0 i ∈ I(x, y),
∇Gk(x, y)Tv ≤ 0 k ∈ K(x, y)}
69
Định nghĩa 3.3.4 ([22], Nón contingent (contingent cone)) Nón contingent (con-
tingent cone) của tập M tại x, với M là tập con đóng trong Rn và x ∈ M ; là nón
đóng xác định bởi
T (x,M) := {v ∈ X|∃tn ↓ 0, vn → v sao cho x+ tnvn ∈ M ∀n}
Định nghĩa 3.3.5 ([22], Nón sinh bởi các hướng (cone of attainable directions))
Nón sinh bởi các hướng (cone of attainable directions) của tập M tại x là nón đóng
xác định bởi
A(x,M) := {v|∃δ > 0 và ánh xạα : R→ X sao choα(τ) ∈ M ∀τ ∈ (0, δ), α(0) = x
và lim
τ↓0
{α(τ)− α(0)
τ
= v},
nón này có định nghĩa tương đương là A(x,M) = lim inf
τ↓0
M − x
τ
Định nghĩa 3.3.6 ([22], Nón sinh bởi các hướng chấp nhận cone of feasible direc-
tions)) Nón sinh bởi các hướng chấp nhận (cone of feasible directions) của M tại x
là nón xác định bởi
D(x,M) := {v ∈ X|∃ δ > 0 sao cho x+ tv ∈ M ∀t ∈ (0, δ)}
Qua các định nghĩa trên, ta có nhận xét sau:
Nhận xét 3.3.1 Mối quan hệ của ba loại nón trên, như sau: clD(x,M) ⊆ A(x,M) ⊆
T (x,M)
N. Zangwill
Ta nói N. Zangwill thỏa tại (x, y) ∈ Θ nếu L((x, y),Θ) ⊆ clD((x, y,Θ) trong đó
D(.,Θ) xác định bởi (3.3.9)
N. Kuhn Tucker CQ
Ta nói N. Kuhn Tucker CQ thỏa tại (x, y) ∈ Θ nếu L((x, y),Θ) ⊆ A((x, y,Θ) trong
đó A(.,Θ) xác định bởi (3.3.8)
N. Abadie CQ
70
Ta nói N. Abadie CQ thỏa tại (x, y) ∈ Θ nếu L((x, y),Θ) ⊆ T ((x, y,Θ) ).
Để tìm hiểu các (E. CQ) ta mở rộng nón tuyến tính L của Θ thành nón tuyến
tính L′
Nhắc lại nón tyến tính trong trường hợp "không trơn",
L((x, y),Θ) := {v|wTv ≤ 0w ∈ ∂ψ(x, y), ∇gi(x, y)Tv ≤ 0 i ∈ I(x, y),
∇Gk(x, y)Tv ≤ 0 k ∈ K(x, y)}
Nón L′ là nón mở rộng của nón L ở trên, thông qua kết quả trong Mệnh đề
3.3.1 là (3.89): ∂o ψ(x, y) ⊆ coW (x, y) (hàm W xác định trong (3.90)), ta thay thế
w ∈ ∂ψ(x, y) bằng w ∈ W (x, y). Như vậy Nón L′ được xác định như sau:
L′((x, y),Θ) := {v|wTv ≤ 0w ∈ W (x, y), ∇gi(x, y)Tv ≤ 0 i ∈ I(x, y),
∇Gk(x, y)Tv ≤ 0 k ∈ K(x, y)}.
Bây giờ các CQs mở rộng được định nghĩa như sau
E. AHU CQ
Ta nói E. AHU CQ thỏa tại (x, y) nếu
h(x, y) là ∂− giả lõm tại (x, y) với ∂h(x, y) ⊆ ∂ψ(x, y),
và ∃v sao cho
• wTv ≤ 0 ∀w ∈ W (x, y) ( thay ∂ψ bởi W)
• ∇gi(x, y)Tv ≤ 0 ∀i ∈ Λ
• ∇gi(x, y)Tv < 0 ∀i ∈ I(x, y) \ Λ
trong đó Λ := {i ∈ I(x, y)|gi giả lõm tại (x, y)}
• ∇Gk(x, y)Tv ≤ 0 ∀k ∈ Γ
• ∇Gk(x, y)Tv < 0 ∀k ∈ K(x, y) \ Γ
trong đó Γ := {k ∈ K(x, y)|Gk giả lõm tại (x, y)}
71
E. Zangwill
Ta nói E. Zangwill thỏa tại (x, y) ∈ Θ nếu L′((x, y),Θ) ⊆ clD((x, y,Θ) trong đó
D(.,Θ) xác định bởi (3.3.9)
E. Kuhn Tucker CQ
Ta nói E. Kuhn Tucker CQ thỏa tại (x, y) ∈ Θ nếu L′((x, y),Θ) ⊆ A((x, y,Θ) trong
đó A(.,Θ) xác định bởi (3.3.8)
E. Abadie CQ
Ta nói N. Abadie CQ thỏa tại (x, y) ∈ Θ nếu L′((x, y),Θ) ⊆ T ((x, y,Θ).
Bây giờ trở lại Chứng minh Định lý 3.3.2.
Trước tiên ta chứng minh (ii)
+ Theo Định nghĩa của hai nón L((x, y),Θ) có một phần ràng buộc là wT ≤
0, w ∈ ∂ψ(x, y) và nón L′((x, y),Θ) có một phần ràng buộc là wT ≤ 0w ∈
W (x, y) , mặt khác do (3.90) của Mệnh đề 3.3.1, ta suy ra L′((x, y),Θ) ⊆
L((x, y),Θ)
+ Như vậy N. AHU CQ =⇒ E. AHU CQ là do (3.89), còn 3 CQs còn lại thì do mối
quan hệ giữa hai nón trên. Suy ra (2.)
N. weak reverse convex CQ =⇒ N. AHU CQ
Ta chỉ cần chỉ ra h(x, y) = f(x, y)−ϕ(x) ∂-giả lõm, ∂h(x, y) ⊆ ∂ψ(x, y), gi(x, y) (i ∈
I(x, y)), Gk(x, y) (k ∈ K(x, y)) giả lõm =⇒ ∃ v thỏa hệ 5 bất đẳng thức của N.
AHU CQ
+ Từ Định nghĩa 3.3.2, h là ∂- giả lõm suy ra ∃v ∈ Rn×Rm sao cho wTv ≤ 0 với
w ∈ ∂h(x, y), mà ∂h(x, y) ⊆ ∂ψ(x, y) suy ra bất đẳng thức thứ nhất.
+ Từ Định nghĩa 3.3.1, gi là giả lõm, ta suy ra gi[(x, y) + tv] ≤ gi(x, y), t > 0
suy ra
gi[(x,y)+tv]−gi(x,y)
t
≤ 0 suy ra ∇gi(x, y)Tv ≤ 0 từ đó suy ra hai bất đẳng thức
tiếp theo . Tương tự cho hàm G ta suy ra hai bất đẳng thức còn lại.
N. AHU CQ =⇒ N. Zangwill
+ Ta có, tồn tại v sao cho wTv ≤ 0 ∀w ∈ ∂ψ(x, y), mà ∂h(x, y) ⊆ ∂ψ(x, y) do đó
với t ≥ 0 ta có wT [(x, y) + tv − (x, y)] ≤ 0 ∀w ∈ ∂h(x, y)
72
Vì h(x, y) là ∂ - giả lõm tại (x, y), suy ra h[(x, y) + tv] ≤ h(x, y), mặt khác
h(x, y) = f(x, y)− ϕ(x) ≤ 0 nên
h[(x, y) + tv] ≤ 0, ∀t ≥ 0.
+ Tương tự ta có gi[(x, y)+ tv] ≤ 0 i ∈ I(x, y) và Gk[(x, y)+ tv] ≤ 0 k ∈ K(x, y)
Theo Bổ đề 3.3.1, ta suy ra tồn tại δ > 0 sao cho (x, y) + tv ∈ Θ suy ra v ∈
D((x, y),Θ) =⇒ N. Zangwill thỏa tại (x, y).
N. Zangwill CQ =⇒ N. Kuhn Tucker CQ =⇒ N. Abadie CQ
Từ Nhận xét 3.3.1, ta suy ra clD((x, y),Θ) ⊆ A((x, y),Θ) ⊆ T ((x, y),Θ), do đó
L((x, y),Θ) ⊆ clD((x, y),Θ) =⇒ L((x, y),Θ) ⊆ A((x, y),Θ)
=⇒ L((x, y),Θ) ⊆ T ((x, y),Θ).
Tóm lại ta có (1.), do đó ta có (3.) (thay nón L(.) bởi L′(.))
Bây giờ ta chứng minh (i)
qua (ii) ta cũng thấy E. Abadie CQ chính là CQ yếu nhất.
Ta sẽ chứng minh (i) thỏa với CQ yếu nhất và quan trọng này.
Rõ ràng N. Abadie CQ tương ứng với nón L(.), còn E. Abadie CQ tương ứng với
nón L′.
Bây giờ ta nêu một bổ đề tương ứng khi N. Abadie CQ thỏa, và cách chứng minh
cho (i) tương tự như cách chứng minh của bổ đề này.
Bổ đề 3.3.2 [22, Mệnh đề 3.1](Điều kiện tối ưu dạng KKT dưới giả thiết
N.Abadie CQ) Giả sử (x, y) là nghiệm tối ưu địa phương của (BLPP). Nếu N.
Abadie CQ thỏa tại (x, y) thì
0 ∈ ∇F (x, y) + cl cone
[
∂ψ(x, y) ∪
⋃
i∈I(x,y)
{
∇gi(x, y)
}
∪
⋃
k∈K(x,y)
{
∇Gk(x, y)
}]
.
(3.92)
73
Chứng minh
Vì (x, y) là nghiệm tối ưu của (BLPP), nên
∇F (x, y)Tv ≥ 0 ∀v ∈ T ((x, y),Θ).
Giả sử N. Abadie CQ thỏa tại (x, y). Thế thì
∇F (x, y)Tv ≥ 0 ∀v ∈ L((x, y),Θ).
Tương đương,
∇F (x, y)Tv ≥ 0 với max
a∈C
aTv ≤ 0,
trong đó C là nón lồi, sinh bởi
∂ψ(x, y) ∪
⋃
i∈I(x,y)
{∇gi(x, y)} ∪
⋃
k∈K(x,y)
{∇Gk(x, y)}.
Do đó hàm v → ∇F (x, y)Tv + δCo(v) đạt cực tiểu tại 0, trong đó
Co := {v ∈ Rn × Rm|vT c ≤ 0 ∀v ∈ C}
là nón đối cực của nón C, và δCo là hàm chỉ số của tập C
o
Theo kiến thức bài toán tối ưu lồi một cấp–chương 1, ta có điều này tương đương
0 ∈ ∇F (x, y) + ∂δCo(0).
Mặt khác ∂δCo(0) = C
oo = clC, do đó lại tương đương 0 ∈ ∇F (x, y) + clC. Suy ra
điều phải chứng minh.
Như vậy trong (3.92) ta thay ∂ψ bằng W ta sẽ có kết quả (3.91) của Định lý 3.3.2
đúng với giả thiết yếu nhất E. Abadie CQ. ¤
(4) Điều kiện tối ưu khi hàm f(x, y)− ϕ(x) lõm
Xét bài toán (BLPP) khi hàm f(x, y)− ϕ(x) là hàm lõm. Ta cũng có các mệnh
đề, định nghĩa và định lý tương ứng trong trường hợp này.
Mệnh đề 3.3.2 (xấp xỉ trên của gradient mở rộng Clark của ψ)
Giả sử (x, y) là nghiệm tối ưu địa phương của (BLPP) trong đó Ψ(x) 6= ∅ và hàm
74
ψ là lõm. Khi đó với bất kì y ∈ Ψ(x), gradient mở rộng Clarke của hàm ψ có
xấp xỉ trên:
∂ψ(x, y) ⊆ A :=
{(
−
∑
i∈I(x,y)
γi∇xgi(x, y), α∇yf(x, y)
)
| (α, γ) ∈ FJ(x, y)
}
. (3.93)
Chứng minh
Để ý
−ψ(x, y) = min
y′,z
{−z| − f(x, y) + f(x, y′) + z ≤ 0, gi(x, y′) + z ≤ 0 i ∈ I y′ ∈ ϕ},
bởi Bổ đề 3.3.1 thì nghiệm của bài toán trên là Ψ(x)× {0}.
Bởi vì −ψ(x, y) là lồi và bị chặn trên một lân cận của (x, y) nên −ψ là Lipschitz tại
(x, y) (xem [5, Mệnh đề 2.2.6], lấy ξ ∈ ∂(−ψ)(x, y) thế thì theo định nghĩa dưới
vi phân, ta có
−ψ(x, y)− (−ψ(x, y)) ≥ 〈ξ, (x, y)− (x, y)〉 ∀(x, y) ∈ Rn × Rm
Theo định nghĩa của ψ ta có ∀(x, y, y′, z) thỏa các ràng buộc sau
−z ≥ −f(x, y) + f(x, y′),
−z ≥ gi(x, y′) i ∈ I,
y′ ∈ ϕ
Kết hợp các yếu tố trên, ta có −z ≥ 〈ξ, (x, y)− (x, y)〉
Do đó (x, y, y′, z) = (x, y, y, 0) là một nghiệm của bài toán tối ưu sau:
min
x,y,y′,z
−z − 〈ξ, (x, y)− (x, y)〉
sao cho − f(x, y) + f(x, y′) + z ≤ 0,
gi(x, y
′) + z ≤ 0 i ∈ I,
y′ ∈ ϕ
(MFCQ) (xem chương 1) thỏa đối với bài toán trên, do đó ∃ (α, γ) ∈ R ×
Rs, (α, γ) ≥ 0, ||(α, γ)||1 = 1 sao cho
ξ = α[−∇f(x, y) +∇xf(x, y × 0] +
∑
i∈I
γi∇xgi(x, y)× 0,
75
0 = α∇yf(x, y) +
∑
i∈I
γi∇ygi(x, y),
0 =
∑
i∈I
γigi(x, y),
nghĩa là
ξ ∈ B :=
{( ∑
i∈I(x,y)
γi∇xgi(x, y), α∇yf(x, y)
)
| (α, γ) ∈ FJ(x, y)
}
.
Suy ra
∂(−ψ)(x, y) ⊆ B
Mặt khác ∂ψ(x, y) = −∂(−ψ)(x, y), do đó
∂ψ(x, y) ⊆ −B =
{(
−
∑
i∈I(x,y)
γi∇xgi(x, y), α∇yf(x, y)
)
| (α, γ) ∈ FJ(x, y)
}
. ¤
Bây giờ ta xác định nón mở rộng trong trường hợp lõm.
Định nghĩa 3.3.7 ([22], Nón tuyến tính mở rộng cho trường hợp hàm lõm)
Giả sử (x, y) ∈ Θ. Nón tuyến tính mở rộng cho trường hợp hàm lõm là tập:
L˜((x, y),Θ) :=
{
v|
(
−
∑
i∈I(x,y)
γi∇xgi(x, y)}, α∇yf(x, y)
)T
v ≤ 0, (α, γ) ∈ FJ(x, y),
∇gi(x, y)Tv ≤ 0, i ∈ I(x, y),
∇Gk(x, y)Tv ≤ 0, k ∈ K(x, y)
}
(3.94)
Định nghĩa 3.3.8 Ta nói E. Abadie CQ, E. Kuhn Tucker CQ, E. Zangwill cho
trường hợp lõm thỏa tại (x, y) nếu
L˜((x, y),Θ) ⊆ T ((x, y),Θ)
L˜((x, y),Θ) ⊆ A((x, y),Θ)
L˜((x, y),Θ) ⊆ cl D((x, y),Θ),
tương ứng.
76
Định nghĩa 3.3.9 Ta nói E. AHU CQ cho trường hợp lõm thỏa tại (x, y) nếu
ψ lõm,
và ∃v sao cho
+ (−∑i∈I(x,y) γi∇xgi(x, y)}, α∇yf(x, y))Tv ≤ 0 ∀(α, γ) ∈ FJ(x, y)
+ ∇gi(x, y)Tv ≤ 0 ∀i ∈ Λ
+ ∇gi(x, y)Tv < 0 ∀i ∈ I(x, y) \ Λ
trong đó Λ := {i ∈ I(x, y)|gi giả lõm tại (x, y)}
+ ∇Gk(x, y)Tv ≤ 0 ∀k ∈ Γ
+ ∇Gk(x, y)Tv < 0 ∀k ∈ K(x, y) \ Γ
trong đó Γ := {k ∈ K(x, y)|Gk giả lõm tại (x, y)}
Định lý 3.3.3 (Điều kiện cần tối ưu dạng KKT trong trường hợp lõm) Giả
sử (x, y) là nghiệm tối ưu của (BLPP) và S(x) 6= ∅. Giả sử h(x, y) = f(x, y)−ϕ(x)
là lõm và một trong các CQs thỏa mãn, gồm N. Abadie CQ, N. Kuhn Tucker CQ,
N. Zangwill CQ, N. weak reverse convex CQ, E. Abadie CQ, E. Kuhn Tucker CQ,
E. Zangwill CQ, E. AHU CQ cho trường hợp lõm, thì
(i) tồn tại (α, γ) ∈ FJ(x, y) và λ ≥ 0, η ∈ Rp+, β ∈ Rq+ sao cho
0 = ∇F (x, y) + λ(−
∑
i∈I(x,y)
γi∇xgi(x, y)}, α∇yf(x, y)) +
∑
i∈I(x,y)
ηi∇gi(x, y)
+
∑
k∈K(x,y)
βk∇Gk(x, y). (3.95)
Tương đương,
(ii) tồn tại λ ≥ 0, α ≥ 0, γ ∈ Rp+, η ∈ Rp+, β ∈ Rq+ sao cho ||(α, γ)|1 = 1 và
0 = ∇F (x, y) +
∑
i∈I
(ηi − λγi)∇gi(x, y) +
∑
k∈K(x,y)
βk∇Gk(x, y), (3.96)
0 = α∇yf(x, y) +
∑
i∈I(x,y)
γi∇ygi(x, y), (3.97)
γi = 0, ηi = 0 ∀i /∈ I(x, y). (3.98)
77
Tương đương,
(iii) tồn tại α ≥ 0, γ ∈ Rp+, ηg ∈ Rp, β ∈ Rq+ sao cho ||(α, γ)||1 = 1 và
0 = ∇F (x, y) +
∑
i∈I(x,y)
ηgi∇gi(x, y) +
∑
k∈K(x,y)
βk∇Gk(x, y), (3.99)
0 = α∇yf(x, y) +
∑
i∈I(x,y)
γi∇ygi(x, y), (3.100)
ηgi ≥ 0 i ∈ Io(x, y), (3.101)
trong đó Io(x, y) := {i ∈ I|gi(x, y) = 0 và γi = 0}.
Chứng minh
Rõ ràng tất cả CQs đều suy ra được E. Abadie CQ trong trường hợp lõm.
Bây giờ giả sử E. Abadie CQ trong trường hợp lõm thỏa. Thay thế nón tuyến tính
L((x, y),Θ) bởi tuyến tính mở rộng cho trường hợp lõm là L˜((x, y),Θ) trong chứng
minh của Bổ đề 3.3.2, ta có
0 ∈ ∇F (x, y) + cl cone
[
A ∪
⋃
i∈I(x,y)
{
∇gi(x, y)
}
∪
⋃
k∈K(x,y)
{
∇Gk(x, y)
}]
. (3.102)
trong đó A kí hiệu trong (3.93). Mặt khác do tập FJ(x, y) là đa diện lồi khác rỗng
(convex polytope) (xem định nghĩa của FJ(.)) và(
−
∑
i∈I(x,y)
γi∇xgi(x, y), α∇yf(x, y)
)
là ánh xạ tuyến tính của (α, γ) suy ra tập A cũng là đa diện lồi, xem [16, Định lý
19.3].
Theo định nghĩa của đa diện lồi, tập A là một bao lồi gồm hữu hạn điểm. Đặt
A1 := A ∪
⋃
i∈I(x,y)
{∇gi(x, y)} ∪
⋃
k∈K(x,y)
{∇Gk(x, y)}
⋃
{0}.
Theo [16, Hệ quả 19.7.1], nón lồi sinh bởi coB là đa diện.
Tuy nhiên, nón lồi sinh bởi tập
A2 := A ∪
⋃
i∈I(x,y)
{∇gi(x, y)} ∪
⋃
k∈K(x,y)
{∇Gk(x, y)}
78
cũng là đa diện, nên là nón đóng.
Do đó trong (3.102) phần đóng (cl(.)) là thừa. Nghĩa là do A lồi nên tồn tại (α, γ) ∈
FJ(x, y) và λ ≥ 0, η ≥ 0, β ≥ 0 sao cho (3.95) thỏa.
suy ra (i) thỏa.
Ta thấy (i) ⇐⇒ (ii); (ii) =⇒ (iii) là hiển nhiên. Bây giờ giả sử (iii) thỏa, ta lấy
λ là số dương bé nhất sao cho
ηgi + λγi ≥ 0 ∀i ∈ I(x, y)
và
η := ηg + λγ,
suy ra (ii) thỏa với nhân tử (λ, α, γ, η, β). ¤ M
79
Chương 4
Điều kiện tối ưu cho bài toán hai
cấp vô hạn
Các kết quả trong phần này có liên quan đến chương 3 và các bài báo [6, 7, 8,
9, 11].
Thực chất điều kiện tối ưu cho bài toán hai cấp vô hạn được phát triển dựa trên
một phần của hướng tiếp cận số (3) trong không gian hữu hạn trong Chương 3.
Ở đây ta xét trong không gian vô hạn chiều với tập chỉ số T vô hạn (xem chương 2,
(c) bài toán hai cấp vô hạn). Sau đây ta sẽ đi sâu vào lớp bài toán tối ưu hai cấp
vô hạn và điều kiện tối ưu của chúng.
4.1 Bài toán hai cấp vô hạn
Xét bài toán hai cấp vô hạn (dạng optimistic), như sau:
min F (x, y) sao cho x ∈ X, y ∈ Ψ(x) := {y ∈ G(x)| f(x, y) = ϕ(x)}. (4.1)
trong đó Ψ(x) là tập nghiệm của bài toán cấp dưới
min f(x, y) sao cho y ∈ G(x) := {y ∈ Y | gt(x, y) ≤ 0, t ∈ T}, T vô hạn. (4.2)
80
và ϕ(.) là hàm giá trị của bài toán cấp dưới
ϕ(x) := inf {f(x, y)| y ∈ G(x)}. (4.3)
Ta lưu ý X, Y là không gian Banach tùy ý và T là tập chỉ số trong các ràng buộc
bất đẳng thức của (4.2), là tùy ý. Chính điều này làm cho bài toán (4.1)–(4.3) này,
trở thành bài toán tối ưu hai cấp vô hạn.
Các giả thiết cố định như sau:
• hàm mục tiêu của bài toán cấp trên (4.1), F : X × Y → R proper, lsc và lồi.
• các hàm của bài toán cấp dưới (4.2), f, gt : X × Y → R proper, lsc và lồi.
• X,Y là hai không gian Banach tùy ý.
Bài toán có các giả thiết kiểu này, được gọi là bài toán lồi hoàn toàn (fully convex).
Các khái niệm proper, lsc xem chương 1.
Bây giờ ta tìm hiểu cụ thể một loạt các tính chất có liên quan chặt chẽ tới bài
toán hai cấp vô hạn.
Để thiết lập điều kiện tối ưu cho bài toán hai cấp vô hạn, thì ta phải xét bài
toán DC vô hạn có liên quan.
4.2 Điều kiện tối ưu cho bài toán DC vô hạn
(1) Bài toán DC vô hạn không chứa tham số
Trước tiên chúng ta xét dạng bài toán DC vô hạn không chứa tham số y là một
lớp các bài toán tối ưu trong không gian Banach với các hàm mục tiêu là hiệu của
hai hàm lồi (Difference of two Convex functions– viết tắt là DC).
minϑ(x)− θ(x) sao cho ϑt(x) ≤ 0, t ∈ T, và x ∈ Θ (4.4)
81
trong đó T là tập chỉ số tùy ý, Θ ⊂ X là tập con lồi đóng của không gian Banach
X; ϑ, θ, ϑt : X → R proper, lsc, lồi.
Kí hiệu tập nghiệm chấp nhận được của (4.16)
E := Θ ∩ {x ∈ X|ϑt(x) ≤ 0 ∀t ∈ T}. (4.5)
Xét không gian RT := {λ = (λt| t ∈ T )|λt ∈ R t ∈ T}
Không gian thực mở rộng R˜T := {λ ∈ RT |λt 6= 0 với hữu hạn t ∈ T}
Nón dương trong R˜T , xác định
R˜T+ := {λ ∈ R˜T |λt ≥ 0 ∀t ∈ T}. (4.6)
Cho vectơ u ∈ RT và λ ∈ R˜T , ta kí hiệu
suppλ := {t ∈ T |λt 6= 0},
chúng ta có tích vô hướng mở rộng
λu :=
∑
t∈T
λtut =
∑
t∈ suppλ
λtut.
Điều kiện định tính (CQ) sau đây đóng một vai trò rất quan trọng trong việc
thiết lập điều kiện cần tối ưu cho bài toán DC vô hạn (điều kiện tối ưu dạng KKT)
tương ứng cho hàm DC ϑ − θ. Vai trò của CQ này còn đảm bảo tồn tại các công
thức tính chứa các ràng buộc vô hạn.
Định nghĩa 4.2.1 ([7],Closedness Qualification Condition = CQC) Chúng ta nói
bộ ba (ϑ, ϑt,Θ) thỏa điều kiện CQC nếu tập
epiϑ∗ + cone
{⋃
t∈T
epiϑ∗t
}
+ epi δ∗(.; Θ)
là đóng yếu∗ trong không gian X∗ × R.
Tiếp theo, ta dùng CQC này để thiết lập điều kiện cần cho bài toán DC vô hạn
(4.4). Trước hết, xét tập nhân tử ràng buộc
A(x) := {λ ∈ R˜T+|λtϑt(x) = 0 ∀t ∈ suppλ}. (4.7)
82
Định lý 4.2.1 ([16], Điều kiện cần cho bài toán DC vô hạn)
Giả sử x ∈ E ∩ domϑ là nghiệm cực tiếu địa phương của (4.16) thỏa CQC. Khi đó
ta có
∂θ(x) ⊂ ∂ϑ(x) +
⋃
λ∈A(x)
[ ∑
t∈suppλ
λt∂ϑt(x)
]
+N(x; Θ). (4.8)
Chứng minh
Không mất tính tổng quát, giả sử x ∈ dom θ và ∂ θ(x) 6= ∅ (nếu ∂ θ(x) = ∅, thì
(4.8) luôn đúng). Theo công thức dưới vi phân xấp xỉ, với ε = 0, tồn tại x∗ ∈ ∂ θ(x)
(x∗ ∈ X∗) nghĩa là
θ(x)− θ(x) ≥ 〈x∗, x− x〉 ∀x ∈ X.
Điều này có nghĩa là x là cực tiểu địa phương cho bài toán vô hạn lồi sau:
min ϑ˜(x) := ϑ(x)− 〈x∗, x− x〉 − θ(x)
sao cho ϑt(x) ≤ 0, t ∈ T, và x ∈ Θ. (4.9)
Bài toán (4.9) là lồi, và nghiệm x là nghiệm toàn cục của bài toán này, nghĩa là
ϑ˜(x) ≤ ϑ˜(x) ∀x ∈ E.
Theo [6, Bổ đề 4], điều này tương đương với
(0,−ϑ˜(x) ∈ cl∗
(
epi ϑ˜∗ + cone
[⋃
t∈T
epiϑ∗t
]
+ epi δ∗ (.; Θ)
)
.
kết hợp với epi ϑ˜∗ = (−x∗, θ(x) − 〈x∗, x〉 + epiϑ∗ (xem cấu trúc của ϑ˜ trong (4.9),
ta có:
(0, - ϑ˜(x) ∈
(−x∗, θ(x)− 〈x∗, x〉) + cl∗
(
epiϑ∗ + cone
[⋃
t∈T
epiϑ∗t
]
+ epi δ∗ (.; Θ)
)
. (4.10)
Hơn nữa, do (i) =⇒ (ii) trong Bổ đề 4.2.1, dưới giả thiết CQC, nên (4.10) tương
đương với:
(x∗,−ϑ˜(x)− θ(x) + 〈x∗, x〉) ∈
(
epiϑ∗ + cone
[⋃
t∈T
epiϑ∗t
]
+ epi δ∗ (.; Θ)
)
. (4.11)
83
Áp dụng công thức epi f ∗ (xem Mục 1.3, phần (2)) vào các hàm đối ngẫu
ϑ∗, ϑ∗t , t ∈ T và δ∗(.; Θ), sau đó thế vào (4.11) và do cấu trúc nón dương (4.6)
R˜T+, và lưu ý là −ϑ˜(x)− θ(x) + 〈x∗, x〉 = 〈x∗, x〉 − ϑ(x), do đó chúng ta có
ε ≥ 0, u∗ ∈ ∂εϑ(x), λ ∈ R˜T , εt ≥ 0, u∗t ∈ ∂εtϑt(x) với t ∈ T, γ ≥ 0,
và v∗ ∈ ∂γ(x; Θ)
thỏa mãn hệ phương trình sau
(i)x∗ = u∗ +
∑
t∈T
λtu
∗
t + v
∗,
(ii)〈x∗, x〉 − ϑ(x) = 〈u∗, x〉+ ε− ϑ(x) +
∑
t∈T
λt[〈u∗t , x〉+ εt − ϑt(x)]
+〈v∗, x〉+ γ − δ(x; Θ). (4.12)
Xét hệ phương trình (4.12), ta thay (i) vào (ii), được
ε+
∑
t∈T
λtεt −
∑
t∈T
λtϑt(x) + γ = 0. (4.13)
Mặt khác bộ ba (ε, λt, γ) là phần tử của tập nhân tử ràng buộc (4.7), nên
ε ≥ 0, γ ≥ 0, λt ≥ 0, λtϑt(x) ≤ 0 ∀t ∈ T.
Kết hợp với phương trình (4.13) cho ta ε = γ = λtεt = λtϑt(x) = 0 ∀t ∈ T, suy ra
εt = 0 t ∈ suppλ. Do đó
u∗ ∈ ∂ϑ(x), u∗t ∈ ∂ϑt(x), v∗ ∈ ∂δ(x; Θ) = N(x; Θ)
và thay vào (i), ta có
x∗ ∈ ∂ϑ(x) +
∑
t∈suppλ
λt∂ϑt(x) +N(x; Θ) vi λtϑt(x) = 0 ∀t ∈ suppλ. (4.14)
Điều này suy ra (4.8). ¤
Sau đây ta tìm hiểu về bài toán DC vô hạn có chứa tham số và dưới Gradient
của hàm giá trị.
84
(2) Bài toán DC vô hạn chứa tham số
Bài toán DC vô hạn chứa tham số là một lớp các bài toán tối ưu trong không
gian Banach với các hàm mục tiêu là hiệu của hai hàm lồi (Difference of two Convex
functions– viết tắt là DC).
Chúng ta quan tâm đến các hàm giá trị cho bài toán DC chứa tham số, cho bởi
ϕ(x) := inf {f(x, y)− g(x, y)| y ∈ F (x) ∩G(x)} (4.15)
trong đó dạng hình học của các ràng buộc chứa tham số
F (x) := {y ∈ Y | (x, y) ∈ Ω} (4.16)
và các ràng buộc bất đẳng thức vô hạn
G(x) := {y ∈ Y | gt(x, y) ≤ 0, t ∈ T} (4.17)
với T là tập chỉ số tùy ý.
Không mất tính tổng quát, ta giả thiết X, Y là không gian Banach tùy ý; các hàm
f, g, gt : X × Y → R proper, lower semicontinuous (l.s.c) và lồi; tập Ω ⊂ X × Y lồi
và đóng.
Lưu ý :
• Hàm ϕ(.) không trơn cho dù f, g trơn (khả vi liên tục),
• Hàm ϕ(.) cũng không lồi cho dù f, g lồi.
Áp dụng CQC trong Định nghĩa 4.3.1 cho bộ ba (ϕ, ϕt,Ω) đối với bài toán (4.15)–
(4.17)
epiϕ∗ + cone
[⋃
t∈T
epiϕ∗t
]
+ epi δ∗(.; Ω) (4.18)
là đóng yếu∗ trong X∗ × Y ∗ × R.
Ánh xạ (cực tiểu) đa trị Ψ : X ⇒ Y tương ứng cho (4.15)–(4.17), là
Ψ(x) := {y ∈ F (x) ∩G(x)|ϕ(x) = f(x, y)− g(x, y)}, (4.19)
85
Tập ràng buộc trong (4.16), (4.17) là
Γ := Ω ∩ {(x, y) ∈ X × Y | gt(x, y) ≤ 0 ∀t ∈ T}, (4.20)
và tập nhân tử KKT phụ thuộc vào (x, y) ∈ gphΨ với Ψ trong (4.19) và vào y∗ ∈ Y ∗
∧(x, y, y∗) := {λ ∈ R˜T+ | y∗ ∈ ∂yf(x, y) +
∑
t∈suppλ
λt∂ygt(x, y) +Ny((x, y); Ω),
λtgt(x, y) = 0 t ∈ suppλ}.(4.21)
Tập nhân tử ràng buộc tại (x, y)
A(x, y) := {λ ∈ R˜T+|λtϑt(x, y) = 0 ∀t ∈ suppλ}. (4.22)
Bây giờ ta nêu định lý sau đây
Định lý 4.2.2 [7, Định lý 5.11](Công thức dưới gradient của hàm giá trị ϕ(.)
trong bài toán DC vô hạn lồi) Xét bài toán (4.15)–(4.17) với g = 0 trong không
gian Banach tùy ý, trong đó thỏa mãn các giả thiết đã nêu và ϕ(.) là lồi. Giả sử
điều kiện CQC trong (4.18) thỏa và domΨ 6= ∅ trong đó Ψ xác định bởi (4.19) với
g = 0.
Khi đó với bất cứ (x, y) ∈ gphΨ, dưới vi phân của ϕ(.) tại x (theo nghĩa giải tích
lồi) được tính bởi
∂ϕ(x) =
{
x∗ ∈ X∗| (x∗, 0) ∈ ∂f(x, y) +
⋃
λ∈A(x,y)
[ ∑
t∈suppλ
λt∂gt(x, y)
]
+N((x, y); Ω)
}
, (4.23)
trong đó A(x, y) xác định bởi (4.22).
Chứng minh
Với g = 0 lúc này ϕ(x) = infy{ϕ(x, y)|y ∈ F (x) ∩ G(x)}, trong đó F (x), G(x)
xác định bởi (4.16), (4.17), tương ứng. Không khó để suy ra ϕ(.) như trên, là lồi và
6= ∅ trong trường hợp g đã = 0.
Trước hết ta kiểm tra dấu ⊂. Lấy x∗ ∈ ∂ϕ(x), nghĩa là
ϕ(x)− ϕ(x) ≥ 〈x∗, x− x〉 với bất kì x ∈ X
86
Áp dụng [7, Định lý 4.1] (với γ = 0, η = ∞), ta có
(x∗, 0) ∈ ∂ϕ(x, y) +
⋃
λ∈A(x,y)
[ ∑
t∈supp λ
λt∂ϕt(x, y)
]
+N((x, y); Ω),
suy ra dấu ⊂ trong (4.32).
Để chứng tỏ bao hàm thức ngược lại, ta lấy x∗ ∈ X∗ sao cho
(x∗, 0) ∈ ∂ϕ(x, y) +
⋃
λ∈A(x,y)
[ ∑
t∈supp λ
λt∂ϕt(x, y)
]
+N((x, y); Ω),
do đó ta có λ ∈ A(x, y), (u∗, v∗) ∈ ∂ϕ(x, y), (u∗t , v∗t ) ∈ ∂ϕt(x, y), và (u˜∗, v˜∗) ∈
N((x, y); Ω) sao cho
(x∗, 0) = (u∗, v∗) +
∑
t∈suppλ
λt(u
∗
t , v
∗
t ) + (u˜
∗, v˜∗). (4.24)
Sử dụng tập nhân tử ràng buộc A(x, y) trong (4.22) và tập chấp nhận được Λ cùng
với các định nghĩa về dưới vi phân (giải tích lồi) và nón pháp tuyến cho (4.24), ta
có hệ sau
f(x, y) - ϕ(x) = f(x, y)− f(x, y) ≥ 〈u∗, x− x〉+ 〈v∗, y − y〉,
0 ≥ λtgt(x, y)− λtgt(x, y) ≥ λt〈u∗t , x− x〉+ λt〈v∗t , y − y〉, t ∈ suppλ,
0 ≥ 〈u˜∗, x− x〉+ 〈v˜∗, y − y〉 ∀(x, y) ∈ Λ.
Kết hợp bất đẳng thức cuối, cùng với (4.24), suy ra
f(x, y) + δ((x, y); Λ)− ϕ(x) ≥ 〈x∗, x− x〉 ∀(x, y) ∈ X × Y,
suy ra ϕ(x)− ϕ(x ≥ 〈x∗, x− x〉 ∀x ∈ X
Do đó x∗ ∈ ∂ϕ(x), suy ra dấu ⊃ trong (4.23). M
4.3 Điều kiện tối ưu cho bài toán hai cấp vô hạn
Trở lại bài toán hai cấp vô hạn dạng đã nêu ở đầu chương, là (4.1)–(4.3), với
các giả thiết tương ứng. Thật may khi bài toán cấp dưới (4.2) là bài toán vô hạn
87
chứa tham số, chính xác nó là trường hợp cụ thể của bài toán DC vô hạn có dạng
(4.15)–(4.17), với g = 0 và không có mặt (4.16). Tuy nhiên, đó mới chỉ là bài toán
cấp dưới, ta còn phải xét cả bài toán cấp trên nữa. Để tận dụng được lợi thế này, ta
phải sử dụng thêm một điều kiện CQ nữa, mục đích là chuyển bài toán hai cấp lồi
hoàn toàn (xem đầu chương 4) tương đương với bài toán DC vô hạn, mà bao gồm
hàm giá trị ϕ(.) lồi (4.3) đối với bài toán cấp dưới (4.2).
Áp dụng Điều kiện cần cho bài toán DC và công thức dưới vi phân của hàm giá trị
ϕ(.) để suy ra điều kiện cần cho bài toán hai cấp vô hạn.
Trước tiên, ta viết lại bài toán (4.1) thành dạng bài toán tương đương (toàn cục) min f(x, y) sao chof(x, y)− ϕ(x) ≤ 0, y ∈ G(x)
và bài toán tuyến tính dạng nhiễu với p ∈ R: min F (x, y) sao chof(x, y)− ϕ(x) + p = 0, y ∈ G(x) (4.25)
Nhắc lại điều kiện "Partially calm"
Ta nói bài toán (4.1) là partially calm tại nghiệm chấp nhận được (x, y) nếu tồn tại
một hằng số a > 0 và một lân cận U của bộ ba (x, y, 0) ∈ X × Y × R sao cho
F (x, y)−F (x, y) + a|p| ≥ 0 ∀(x, y, p) ∈ U, chấp nhận được đối với (4.25). (4.26)
Bổ đề sau đây cho thấy dưới điều kiện partially calm, thì bài toán tối ưu hai cấp
vô hạn (4.1) sẽ trở thành bài toán tối ưu DC một cấp với vô hạn ràng buộc. Thực
chất, để có sự tương đương hoàn toàn giữa hai loại bài toán kể trên, ta cần thêm
tính liên tục của hàm cấp trên.
Bổ đề 4.3.1 [7, Bổ đề 6.1] Giả sử (x, y) là nghiệm chấp nhận được partially calm
cho bài toán (4.1), với G : X ⇒ Y cho bởi (4.2) và hàm cấp trên F liên tục tại điểm
này.
88
Khi đó (x, y) là nghiệm tối ưu địa phương của bài toán sau: min a−1F (x, y) + f(x, y)− ϕ(x)sao cho gt(x, y) ≤ 0, t ∈ T, (4.27)
trong đó a > 0 là hằng số từ điều kiện partially calm (4.26).
Chứng minh
Bởi (4.1) là partially calm, ta có a > 0 và lân cận U của (x, y, 0) để (4.26) thỏa
mãn.
Vì F liên tục tại (x, y) nên tồn tại γ > 0 và η > 0 sao cho
V := [(x, y) + ηB]× (−γ, γ) ⊂ U
và
|F (x, y)− F (x, y)| ≤ aγ với (x, y)− (x, y) ∈ ηB.
Điều này suy ra
F (x, y)− F (x, y) + a(f(x, y)− ϕ(x)) ≥ 0 ∀(x, y) ∈ [(x, y) + ηB] ∩ gphG, (4.28)
trong đó G : X ⇒ Y xác định bởi (4.2).
Thật vậy,
+ Nếu (x, y, ϕ(x)− f(x, y) ∈ V thì (4.26) =⇒ (4.28).
+ Nếu (x, y, ϕ(x)−f(x, y) /∈ V , ta lấy f(x, y)−ϕ(x) ≥ γ nên a(f(x, y)−ϕ(x) ≥ aγ,
kết hợp với f(x, y)− f(x, y) ≥ −aγ nên =⇒ (4.28).
Hiển nhiên f(x, y) = ϕ(x) (do (x, y) là nghiệm chấp nhận được của (4.1)). Mặt khác
(4.28) nghĩa là (x, y) là nghiệm tối ưu địa phương của bài toán DC (4.27). ¤
Định lý kế tiếp cung cấp xấp xỉ trên của dưới vi phân của hàm lồi (4.3) tại
nghiệm partially calm đối với bài toán hai cấp.
Định lý 4.3.1 [7, Định lý 6.2](dưới gradient của hàm lồi ϕ(.) tại nghiệm
partially calm đối với bài toán hai cấp) Giả sử (x, y) là nghiệm chấp nhận
89
được partially calm cho bài toán (4.1). Giả sử điều kiện CQC trong (4.18) thỏa đối
với bài toán cấp dưới (4.2) và hàm cấp trên F liên tục tại (x, y).
Khi đó tồn tại hằng số a > 0 sao cho
∂ϕ(x)× {0} ⊂ a−1∂F (x, y) + ∂f(x, y) +
⋃
λ∈A(x,y)
[ ∑
t∈suppλ
λt∂gt(x, y)
]
(4.29)
cho hàm lồi ϕ(.) trong (4.3), trong đó A(x, y) xác định theo (4.22). Nói riêng, ta có
∂ϕ(x) ⊂ a−1∂xF (x, y) + ∂xf(x, y) +
⋃
λ∈A(x,y)
[ ∑
t∈suppλ
λt∂xgt(x, y)
]
(4.30)
Chứng minh
Cố định (x, y) thỏa mọi giả thiết của định lý. Bổ đề 4.5.1 suy ra (x, y) là nghiệm
tối ưu địa phương của bài toán DC (4.27), là dạng bài toán DC vô hạn có dạng tổng
quát (4.4) trong không gian X × Y với các hàm lsc, lồi. Đặt
ϑ(x, y) := a−1F (x, y) + f(x, y), θ(x, y) := ϕ(x), và ϑt(x, y) := gt(x, y) (4.31)
với Θ = X × Y như trong (4.4).
Dùng cấu trúc tập chấp nhận được
E := {(x, y) ∈ X × Y |gt(x, y) ≤ 0 ∀t ∈ T}
đối với bài toán (4.27), công thức epi(f1+f2)
∗ = cl∗((epif ∗1 +epif
∗
2 ) (xem [Chương
1, Bổ đề 1.3.1(ii)]) nếu epif ∗1 +epif
∗
2 không thỏa tính yếu
∗) và sử dụng CQC trong
(4.18), ta có một loạt các đẳng thức sau
epi(f + δ(.;E))∗ = cl∗(epif ∗ + epiδ∗(.;E)) = cl∗{epif ∗ + cl∗(cone[
⋃
t∈T
epig∗t ])}
= cl∗{epif ∗ + (cone[
⋃
t∈T
epig∗t ])} = epif ∗ + cone[
⋃
t∈T
epig∗t ].
Hơn nữa, từ Bổ đề 1.3.1(ii), áp dụng công thức (1.7) vào (4.31) với giả thiết F
liên tục tại (x, y), ta lại có
epif ∗ + cone[
⋃
t∈T
epig∗t ] = epi(a
−1F )∗ + epif ∗ + cone[
⋃
t∈T
epig∗t ]
90
= epi(a−1F )∗ + epi(f + δ(.;E))∗ = epi(ϑ+ δ(.;E))∗.
Điều này cho phép ta khẳng định epif ∗ + cone[
⋃
t∈T epig
∗
t ] là đóng yếu
∗ trong X∗×
Y ∗ × R, nghĩa là CQC cho giả thiết Định lý 4.3.1 thỏa, do đó áp dụng Định lý
4.3.1 vào bài toán DC (4.27) trên, ta lưu ý các hàm trong (4.31) có
∂θ(x, y) = ∂ϕ(x)
và
∂ϑ(x, y) = ∂(a−1F + f)(x, y) = a−1∂F (x, y) + ∂f(x, y),
do F liên tục tại (x, y), từ (4.8) ta suy ra (4.29) còn (4.30) suy ra từ (4.39) khi lấy
dưới vi phân cục bộ theo x, nhờ mối quan hệ sau (xem [16, Định lý 4.1], công thức
(4.11)).
f(x, y) ⊂ ∂xf(x, y)× ∂yf(x, y)
và
ft(x, y) ⊂ ∂xft(x, y)× ∂yft(x, y). (4.32)
¤
Bây giờ chúng ta thiết lập kết quả chính của chương này: điều kiện tối ưu cho
bài toán hai cấp lồi hoàn toàn với vô hạn ràng buộc bất đẳng thức.
Định lý 4.3.2 [7, Định lý 6.3](Điều kiện cần cho bài toán hai cấp vô hạn)
Giả sử (x, y) là nghiệm tối ưu partially calm của bài toán hai cấp (4.1) thỏa các giả
thiết đã nêu. Giả sử CQC trong (4.18) thỏa cho bài toán cấp dưới (4.2), hàm mục
tiêu của cấp trên F liên tục tại (x, y) và hàm giá trị trong (4.3) có ∂ϕ(x) 6= ∅.
Khi đó với mỗi y˜ ∈ Ψ(x) với Ψ(x) xác định trong (4.19), thì tồn tại một số a > 0,
và các nhân tử λ = (λt) ∈ R˜T+, β = (βt) ∈ R˜T+ với R˜T+ là nón dương xác định trong
(4.6) sao cho ta có hệ
0 ∈ ∂xF (x, y) + a[∂xf(x, y)− ∂xf(x, y˜)] +
∑
t∈suppλ
λt∂xgt(x, y)
91
−a
∑
t∈suppβ
βt∂xgt(x, y˜), (4.33)
0 ∈ ∂yF (x, y) + a∂yf(x, y) +
∑
t∈suppλ
λt∂ygt(x, y), (4.34)
0 ∈ ∂yf(x, y˜) +
∑
t∈suppβ
βt∂ygt(x, y˜), (4.35)
λtgt(x, y) = βtgt(x, y˜) = 0 ∀t ∈ T. (4.36)
Chứng minh
Vì ∂ϕ(x) 6= ∅, ta lấy x∗ ∈ ∂ϕ(x), theo Định lý 4.3.1, tồn tại a > 0 và λ ∈ R˜T+
thỏa mãn
a(x∗, 0) ∈ ∂F (x, y) + a∂f(x, y) +
∑
t∈suppλ
λt∂gt(x, y) (4.37)
với λtgt(x, y) = 0 ∀t ∈ suppλ. Mặt khác chọn y˜ ∈ Ψ(x) và sử dụng kết quả của
Định lý 4.4.1, kết hợp với bao hàm thức (4.32), ta tìm được β ∈ R˜T+ sao cho
x∗ ∈ ∂xf(x, y˜) +
∑
t∈suppβ
βt∂xgt(x, y˜), 0 ∈ ∂yf(x, y˜) +
∑
t∈suppβ
βt∂ygt(x, y˜), (4.38)
và βtgt(x, y˜) = 0 ∀t ∈ supp β.
Kết hợp (4.37), (4.38) với cấu trúc nón dương R˜T+ trong (4.6), ta có hệ (4.33)–(4.36).
¤
Nếu ta thay y˜ = y trong định lý trên, thì có hệ quả sau
Hệ quả 4.3.1 [7, Hệ quả 6.4](Trường hợp đặc biệt của Định lý 4.4.2) Giả sử
(x, y) là nghiệm tối ưu partially calm của bài toán hai cấp (4.1) thỏa các giả thiết
của Định lý (4.4.2). Khi đó tồn tại một số a > 0, và các nhân tử λ = (λt), β =
(βt) ∈ R˜T+ sao cho
0 ∈ ∂xF (x, y) +
∑
t∈T
[(λt − aβt)∂xgt(x, y),
0 ∈ ∂yF (x, y) + a∂yf(x, y) +
∑
t∈T
λt∂ygt(x, y),
0 ∈ ∂yf(x, y) +
∑
t∈T
βt∂ygt(x, y),
λtgt(x, y) = βtgt(x, y) = 0 ∀t ∈ T
92
Nhận xét 4.3.1 (So sánh với các kết quả đã biết dựa trên điều kiện tối ưu cho bài
toán lồi hoàn toàn ở chương 3)
So sánh Định lý 4.3.2 chương 4 và Định lý 3.2.2 chương 3, vấn đề " thiết lập
điều kiện tối ưu cần cho bài toán lồi" (vô hạn và hữu hạn, tương ứng). Cả hai đều
suy ra 4 kết quả tương tự nhau, dưới các giả thiết có khác nhau: điều kiện partially
calm, CQC so với điều kiện chính quy, Ψ(.) bị chặn đều (nghĩa là nửa compac
trong (inner semicopactness)); như vậy trong Định lý 4.3.2 không cần giả thiết
nửa compac trong.
Việc chọn y˜ = y đối với Định lý 3.2.2, cần phải có thêm giả thiết nửa liên tục trong
(inner semicontinuity) của Ψ(.) tại nghiệm tối ưu (x, y), trong khi điều này không
cần trong Hệ quả 4.3.1 của Định lý 4.3.2.
Cuối cùng là giả thiết trơn của Định lý 3.2.3, trong khi giả thiết này cũng không
cần trong cả Định lý 4.3.2 và Hệ quả 4.3.1 của nó. Mà chúng ta dùng các kỹ
thuật khác, khác với [12].
Cuối cùng ta tìm hiểu một bài toán hai cấp lồi đơn giản.
4.4 Điều kiện cần và đủ cho bài toán hai cấp lồi
đơn giản
Xét lớp bài toán hai cấp lồi đơn giản (Simple Convex Bilvel Problem)
(SCBP) min f(x) sao cho x ∈ S,
trong đó S cho bởi
S = argmin{h(x)|x ∈ Θ}
trong đó f, h là các hàm thực, lồi trên Rn và Θ là tập con lồi trong Rn. Cũng như
các hàm giá trị của bài toán cấp dưới phần trên, ta suy ra S là tập lồi và do đó bài
toán (SCBP) là bài toán lồi. Chúng ta gọi nó là bài toán tối ưu hai cấp lồi đơn
giản. Xem cụ thể bài toán này trong [11].
93
Giả sử S là tập khác rỗng và đặt α = inf
x∈Θ
h, thì bài toán (SCBP) tương đương với
bài toán một cấp sau
(RP) min f(x) sao cho h(x) ≤ α, x ∈ Θ
Câu hỏi đặt ra là liệu chúng ta có thể thiết lập được điều kiện tối ưu cả cần và đủ
cho bài toán (SCBP) hay không.
Trước hết ta xét
(1) Bài toán tối ưu nón–lồi
Xét lớp các bài toán nón-lồi (Cone-convex Problem), (xem [11]).
(CCP) min ϑ(x) sao cho g(x) ∈ −D, x ∈ C
trong đó ϑ : Rn → R là proper, lồi, lsc và g : Rn → Rm là ánh xạ D–lồi liên tục với
D là nón lồi đóng trong Rm và C là tập con trong Rn lồi và đóng.
Nhắc lại một số khái niệm. Nón pháp của C tại x là
NC(x) = {u ∈ Rn| 〈u, y − x〉 ≤ 0 ∀y ∈ C},
khi x ∈ C và NC(x) = ∅, trường hợp khác. Đặt A := {x ∈ C| g(x) ∈ −D}. Nón đối
ngẫu dương của D, kí hiệu D+ (có thể xem cụ thể ở chương 1)
D+ := {s∗ ∈ Rm| 〈s∗, s〉 ≥ 0, ∀s ∈ D}.
Định nghĩa 4.4.1 [11, Định nghĩa 3.1](Farkas–Minkowski constraint qualification,
viết tắt (FMCQ)) Ta nói bài toán (CCP) thỏa (FMCQ), nếu nón
K := cone[
⋃
λ∈D+
epi(λh)∗] + epi δ∗C . (4.39)
là đóng trong Rn × R.
Định nghĩa 4.4.2 (Closedness conditions constraint qualification, viết tắt (CCCQ))
Ta nói bài toán (CCP) thỏa (CCCQ), nếu
epiϑ∗ +K (4.40)
là đóng trong Rn × R với K cho bởi (4.39).
94
Nhận xét 4.4.1 [6] Ta đã biết nếu f liên tục tại ít nhất một điểm thuộc A, thì
epi(f + δA)
∗ = cl∗(epif ∗ + epiδ∗A) = epif
∗ + epiδ∗A = epif
∗ + cl∗K.
Vì thế nếu (FMCQ) thỏa (nghĩa là K đóng), thì (CCCQ) thỏa.
Định lý 4.4.1 [9](Điều kiện tối ưu cần và đủ cho bài toán (CCP)) Giả sử
bài toán (CCP) thỏa (CCCQ). Thế thì x ∈ A∩ domϑ là một nghiệm (toàn cục) của
(CCP) khi và chỉ khi tồn tại λ ∈ D+ sao cho
0 ∈ ∂ϑ(x) + ∂(λg)(x) +NC(x) (4.41)
λg(x) = 0. (4.42)
(2) Áp dụng vào bài toán hai cấp
Xét bài toán (SCBP), và bài toán tương đương (RP) như sau
min f(x) sao cho h(x)− α ≤ 0, x ∈ Θ.
với α = inf
x∈Θ
h, giả sử α hữu hạn, nghĩa là α < ∞ Rõ ràng điều kiện chính quy Slater
(xem chương 1) không thỏa cho (RP). Bây giờ ta đưa ra điều kiện chính quy khác
và thiết lập điều kiện tối ưu cần và đủ cho (RP).
Định lý 4.4.2 [11](Điều kiện tối ưu cần và đủ cho (RP)) Giả sử bài toán
(RP) thỏa cone [(0, α) + epih∗] + epiδ∗Θ là đóng. Thế thì x ∈ Θ là nghiệm toàn cục
của (RP) khi và chỉ khi tồn tại λ ∈ + sao cho
0 ∈ ∂f(x) + λ∂h(x) +NΘ(x) (4.43)
λ(h(x− α) = 0. (4.44)
Chứng minh
Trước tiên ta nhận thấy (RP) là có dạng của (CCP) tương ứng với D = D+ = R+
và C = Θ. Thứ hai, với mỗi u∗ ∈ Rm,
(h(.)− α)∗(u∗) = α + h∗(u∗).
95
Suy ra
epi(h(.)− α)∗ = (0, α) + epih∗.
Vì
cone[(0, α) + epih∗] + epi δ∗Θ
là đóng, nên (FMCQ) thỏa suy ra (CCCQ) thỏa do f liên tục (xem Nhận xét 4.4.1)
Theo Định lý 4.4.1, ta có tồn tại λ ∈ R+ sao cho
0 ∈ ∂f(x) + λ∂[h(.)− α](x) +NΘ(x) (4.45)
λ[h(x)− α] = 0. (4.46)
Vì ∂[h(.)− α](x) = (x) nên (4.45) suy ra (4.43), còn (4.46) chính là (4.44).
Ví dụ 4.4.1 Xét bài toán (CCP) với f(x) = x2+1, Θ =[-1, 1], và h(x) = max{0, x}.
Dễ thấy epiδ∗Θ = epi|.|, S = [−1, 0], và α = 0. Bài toán được viết lại
min f(x) sao cho h(x) ≤ 0, x ∈ [−1, 1]. (4.47)
Để ý là với mỗi u ∈ R, thì
h∗(u) = +∞ nếu u > 1 hoặc u < 0;= 0 nếu u ∈ [0, 1].
Ta có
epih∗ = {(u, r)|u ∈ [0, 1], r ≥ 0} = [0, 1]× R+,
và
cone [(0, α) + epih∗] + epi δ∗Θ = R2+ ∪ {(u, r)|u ≤ 0, r ≥ −u}.
là tập con đóng trong R2, chứng tỏ bài toán (4.47) thỏa (FMCQ), vì f liên tục nên
(CCCQ) cũng thỏa.
Do đó x = 0 là nghiệm của bài toán hai cấp. Vì NΘ(0) = {0}, ∂f(0) = {0} và
∂h(0) = [0, 1] nên (4.43), (4.44) thỏa với λ = 0.
96
(3) Bài toán (SCBP) với Θ mở rộng
Ta trở lại bài toán (SCBP) trong đó Θ = {x|g1(x) ∈ −D1, x ∈ C}, và ta viết
lại một cách đầy đủ, như sau:
inf
x∈S
f(x), (4.48)
trong đó S là tập nghiệm của bài toán cấp dưới sau:
min h(x) sao cho g(x) ∈ −D1, x ∈ C. (4.49)
với các giả thiết là h : Rn → R proper, lsc, lồi; và g1 : Rn → Rm là ánh xạ D1–lồi
với D1 là nón lồi đóng trong Rm và C là tập con trong Rn lồi và đóng.
Đặt
α = inf
g1(x)∈−D1,x∈C
h(x) < +∞,
để đơn giản giả sử α = 0. Thế thì bài toán (4.48) trở thành bài toán tương đương
sau:
min f(x) sao cho h(x) ≤ 0, g1(x) ∈ −D1, x ∈ C. (4.50)
Bây giờ lại đặt
D := R+ ×D1, g : Rn → Rm+1, g(x) = (h(x), g1(x)).
Bài toán (4.50) có thể viết lại như sau:
min f(x) sao cho g(x) ∈ −D, x ∈ C, (4.51)
bài toán (4.51) có dạng như (CCP). Áp dụng điều này để phát biểu điều kiện tối
ưu cho bài toán (4.48).
Định lý 4.4.3 [11, Định lý 3.5](Điều kiện cần và đủ KKT cho bài toán hai
cấp (4.48))
Giả sử bài toán tối ưu hai cấp (4.48) có
cone epih∗ +
⋃
λ∈D+1
epi (λg1)
∗ + epiδ∗C
97
là đóng. Thế thì x ∈ g−1(−D) ∩C là nghiệm toàn cục của (4.48) nếu và chỉ nếu có
r ∈ R+, và λ ∈ D1 sao cho
0 ∈ ∂f(x) + r∂h(x) + ∂(λg1)(x) +NC(x) (4.52)
rh(x) = 0 và λg1(x) = 0. (4.53)
Chứng minh
Ta có D+ = R+ ×D+1 và với bất kì λ˜ = (r, λ) ∈ D+,
(λ˜g)(x) = rh(x) + (λg1)(x).
Hơn nữa,
epi(λ˜g)∗ = cl∗ {epi (rh)∗ + epi (λg1)∗}
= epi (rh)∗ + epi (λg1)∗ = r. epih∗ + epi (λg1)∗.
Do đó, ⋃
λ˜∈D+
epi (λ˜g)∗ + epi δ∗C = cone epih
∗ +
⋃
λ∈D+1
epi (λg1)
∗ + epiδ∗C .
Theo giả thiết của định lý, tập này đóng. Do đó, (FMCQ) thỏa cho bài toán
(4.51), vì f liên tục nên (CCCQ) cũng thỏa cho bài toán (4.51).
Vì bài toán (4.48) tương đương với bài toán (4.60) theo cách xây dựng phía trên.
Áp dụng Định lý 4.4.1, x ∈ A là nghiệm tối ưu của (4.48) nếu và chỉ nếu tồn tại
λ = (r, ) ∈ D+ sao cho
0 ∈ ∂f(x) + ∂(λ˜g)(x) +NC(x), (4.54)
(λ˜g)(x) = 0. (4.55)
Rõ ràng
∂(λ˜g)(x) = r∂h(x) + ∂(λg1)(x),
thay vào (4.54) ta được (4.52) Mặt khác,
(λ˜g)(x) = r∂h(x) + λg1(x) = 0,
nên với λ ≥ 0, h(x) ≤ 0, λg1(x) ≤ 0, ta có ngay rh(x) = λg1(x) = 0, suy ra (4.52).
¤ M
98
Kết luận
Luận văn được trình bày một cách chuyên sâu từ bài toán tối ưu hai cấp hữu hạn
đến bài toán tối ưu hai cấp vô hạn với 4 hướng tiếp cận khác nhau. Trong bài toán
hai cấp hữu hạn, chúng tôi đã xét 4 lớp bài toán khác nhau, đó là bài toán trơn, bài
toán lồi, tuyến tính, bài toán Lipschitz. Còn bài toán hai cấp vô hạn, chúng tôi đã
xét bài toán lồi (hoàn toàn) với mọi hàm đều lồi, nửa liên tục dưới . Bằng các yếu
tố, gồm công cụ giải tích Clarke hay công cụ giải tích của Mordukhovich, các giả
thiết về hàm lồi, trơn, Lipschitz cùng với các điều kiện định tính ràng buộc chính
quy; chúng ta đã thiết lập được các điều kiện tối ưu cho các lớp bài toán tối ưu hai
cấp tương ứng. Các điều kiện chủ yếu là điều kiện cần, và ta cũng chỉ ra được điều
kiện đủ cho lớp bài toán hai cấp đơn giản ở mục cuối chương 4.
Thực chất hai loại bài toán vô hạn và hữu hạn cũng cho thấy có sự liên quan với
nhau. Tất cả chúng đều nói về nghiệm tối ưu địa phương optimistic. Điều thứ hai
của tính liên quan đó là, các kết quả về điều kiện cần cho lớp các bài toán hai cấp
vô hạn thực ra là sự mở rộng của lớp các bài toán hữu hạn, ngay sau sự ra đời của
lý thuyết vi phân mở rộng vô hạn chiều của Mordukhovich. (xem [17, 18] (năm
2006) để thấy rõ ràng hơn về điều này).
Một lưu ý đó là không phải bài toán vô hạn là tổng quát của bài toán hữu hạn,
chỉ trừ một vài lớp bài toán đặc biệt và phải thỏa những điều kiện đặc biệt như đã
nêu. Ở đây mỗi loại bài toán đều đưa ra một cách đa dạng các phương pháp và kỹ
thuật xây dựng bài toán, các giả thiết, ràng buộc cũng như cách thiết lập các điều
kiện tối ưu sử dụng tốt nhất các giả thiết đó.
Lý thuyết vi phân vô hạn của Mordukhovich đang tiếp tục phát triển, do đó các
vấn đề trong luận văn còn có thể tiếp tục phát triển nữa.
Chúng ta có 3 vấn đề còn tồn tại, thứ nhất là làm sao để thiết lập được nhiều
99
điều kiện đủ hơn cho mỗi lớp bài toán. Thứ hai là hãy đề xuất những công cụ giải
tích mạnh và phát triển yếu tố nghiệm tối ưu pessimistic thay vì chỉ nghiên cứu về
nghiệm tối ưu optimistic. Vấn đề cuối cùng là mở rộng và liên hệ đến các lớp bài
toán có liên quan đến bài toán hai cấp, chẳng hạn như bài toán tối ưu đa mục tiêu
và bài toán có nhiều ứng dụng quan trọng thực tiễn: (MPECs) (xem cụ thể trong
[15]).
Luận văn đã trình bày tổng quan nội dung chủ yếu về đề tài được đưa ra ở
những kết quả gần đây, tuy nhiên chưa đưa ra được cái mới của tác giả. Chúng tôi
rất mong sẽ được tiếp tục nghiên cứu những vấn đề có liên quan trong thời gian
tới. Dù đã có nhiều cố gắng nhưng luận văn sẽ không thể tránh khỏi những thiếu
sót. Vì vậy tôi rất mong nhận sự góp ý của quý Thầy, Cô cùng các bạn để luận văn
được hoàn thiện hơn. ¥
100
Tài liệu tham khảo
[1] Nguyễn Định, Quy hoạch lồi. Đại học khoa học tự nhiên thành phố Hồ Chí
Minh, 2006.
[2] Nguyễn Đông Yên, Giáo trình Giải tích đa trị. Nhà xuất bản khoa học tự nhiên
và công nghệ, Hà Nội, 2007.
[3] Burachik, R.S., Jeyakumar V.: A dual condition for the convex subdifferential
sum formula with applications. J. Convex Anal. 12, 279–290 (2005)
[4] Clarke, F.H.: A new approach to Lagrange multipliers. Mathematics of Opera-
tions Research, 1: 165–174 (1976)
[5] Clarke, F.H.: Optimization and Nonsmooth Analysis. Wiley-Interscience, New
York, 1983.
[6] Dinh, N., Goberna, M.A., López, M.A., Son, T.Q.: New Farkas-type results with
applications to convex infinite programming. ESAIM: Control Optim. Cal. Var.
13, 580–597 (2007)
[7] Dinh, N., Nghia, T.T.A., Mordukhovich, B.S.: Subdifferentials of value func-
tions and optimality conditions for some classes of DC and bilevel infinite
and semi-infinite programs. Research Report ] 4, Department of Mathematics,
Wayne State University, Detroit, Michigan (2008). To appear inMath. Program.
(2008)
101
[8] Dinh, N., Nghia, T.T.A., Mordukhovich, B.S.: Qualification and optimality
conditions for DC programs with infinte constraints. To appear in Acta Math-
ematica Vietnamica (2009)
[9] Dinh, N., Nghia, T.T.A., Vallet., G.: A closedness condition and its applications
to DC programs with convex constraints. To appear in Optimization. (2009)
[10] S. Dempe, Foundations of Bilevel Programming, Kluwer Academic Publishers,
Dordretch, 2002.
[11] Dempe., S., Dinh., N., Dutta., J.: Optimality conditions for a simple convex
bilevel programming problem, 1–10 (2009)
[12] Dempe., S., Dutta., J., Mordukhovich., B.S.: New necessary optimality condi-
tions in optimistic bilevel programming, 1–30 (2006)
[13] Dempe., S., Kalashnikov., V.V., Kalashnykova., N.: Optimality conditions for
bilevel programming problems. Optimization with Multivalued Mappings: The-
ory, Applications and Algorithms, 1–6 (2006)
[14] Dutta., J., Dempe., S.: Bilevel programming with convex lower level problems.
Optimization with Multivalued Mappings: Theory, Applications and Algorithms,
51–63 (2006)
[15] Luo., Z.Q., Pang., J. S., Ralph., D.: Mathematical Programs with Equilibrium
Constraints. Cambridge University Press, Cambridge, 1996.
[16] Mangasarian., O. L.: Nonlinear Programming. SIAM. Philadelphia, PA, 1994.
[17] Mordukhovich., B.S.: Variational analysis and Gerneralized Differentiation, I:
Basic Theory. Springer-Verlag, Berlin, 2006.
[18] Mordukhovich., B.S.: Variational analysis and Gerneralized Differentiation, II:
Applications. Springer-Verlag, Berlin, 2006.
102
[19] Mordukhovich., B. S., Nam., N.M.: Variational stability and marginal functions
via gerneralized differentiation. Math. oper. Res. 30, 800–816 (2005)
[20] Mordukhovich., B. S., Nam., N.M., Yen. N.D.: Subgradients of marginal func-
tions in parametric mathematical programming. To appear in Math. Prog.,
(2007)
[21] Rockafellar., R.T.: Convex Analysis. Princeton University Press, Princeton,
New Jork, 1970.
[22] Ye., J.J.: Constraint qualifications and KKT conditions for bilevel programming
problems. Optimization 31, 811–824 (2006)
[23] Ye., J.J., Zhu., D. L.: Optimality conditions for bilevel programming problems.
Optimization 33, 9–27 (1995)
103
Các file đính kèm theo tài liệu này:
- luan van nop sau bao ve.pdf
- bIA cHINH-NHU VANG.doc