Đ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
(Học viên Cao Học khóa 16)
NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS. TS. NGUYỄN ĐỊNH
(Trường Đại Học Quốc Tế TP. HCM)
TP.Hồ Chí Minh - Năm 2009
Lời cảm ơn
Lời đầu tiên, tôi xin chân thành cảm ơn sâu sắc tới PGS. TS. NGUYỄN ĐỊNH,
người Thầy đã tận tình chỉ dẫn và truyền đạt kiến thức trong quá trình học tập và
luôn động viên để tôi hoàn thành luận văn này.
Tôi cũng xin bày tỏ lời cảm ơn tới tất cả các Thầy cô của Khoa Toán-Tin trường
Đại Học Khoa Học Tự Nhiên Tp.HCM đã giảng dạy tôi trong suốt quá trình học
tập tại trường.
Tôi xin cảm ơn gia đình đã tạo điều kiện tốt cho việc học của tôi và bạn bè đã hỗ
trợ trong việc hoàn thành luận văn này.
Tp. Hồ Chí Minh, tháng 9 năm 2009
Nguyễn Lê Duy
1
Lời nói đầu
Bài toán tối ưu hai cấp (Bilevel Optimization Problem) lần đầu tiên được
H.V.Stackelberg nghiên cứu vào năm 1934. Sau đó nó chính thức được giới thiệu
trong cộng đồng tối ưu vào thập kỷ 70 của thế kỷ thứ 20. Bài toán phát triển rất
nhanh chóng cả trong lý thuyết và ứng dụng thực tế. Các nhà toán học, nhà kinh tế
học và những kỹ sư đã và đang không ngừng phát triển vấn đề này cùng với đó là
số lượng các bài báo, tạp chí khoa học, ứng dụng trong kinh tế kỹ thuật xuất hiện
ngày càng nhiều hơn.
Bài toán tối ưu hai cấp là một bài toán tối ưu có cấp bậc trong đó một phần
các ràng buộc của bài toán - được gọi là bài toán cấp trên (upper level problem)
là tập nghiệm tối ưu của một bài toán tối ưu thứ hai - được gọi là bài toán cấp
dưới (lower level problem). Do đó bài toán này là một bài toán rất phức tạp. Tuy

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
4
Chương 1
Một số kiến thức cơ bản
1.1 Một số kiến thức cơ bản về giải tích lồi
(1) Tập lồi và hàm lồi
Giả sử X là không gian vectơ.
Định nghĩa 1.1.1 [1] Tập K ⊆ X là lồi nếu
∀x, y ∈ K, ∀λ ∈ [0, 1], λx + (1 − λ)y ∈ K.
Với K = ∅, bao lồi của K, ký hiệu là co(K), là tập tất cả các tổ hợp lồi hữu hạn
của K, tức là
co(K) := {

i∈I
α
i
x
i
|α
i
≥ 0, x
i

o
∈ X và f(x
o
) = ±∞. Khi đó dưới vi phân của
hàm lồi f tại x
o
được xác định như sau
∂f(x
o
) := {x
∗
∈ X
∗
: x
∗
, x − x
o
 ≤ f(x) − f(x
o
), ∀x ∈ X}. (1.1)
Nếu f không hữu hạn tại x thì ∂f(x
o
) = ∅.
Mỗi thành phần x
∗
∈ ∂f(x
o
) được gọi là dưới gradient của dưới vi phân ∂f(x
o
), khi

) cũng = sup {x
∗
, x − f(x)|x ∈ domf}.
Cho hàm f : X → R lồi, là proper nếu f(x) = ∞ trên X. Nhắc lại hàm đối ngẫu
f
∗
: X
∗
→ R đối với f, xác định bởi f
∗
(x
∗
) := sup {x
∗
, x − f(x)| x ∈ X =
sup {x
∗
, x − f(x)| x ∈ domf}.
Cho hàm f : X → R lồi tại x ∈ domf và ε > 0 bất kì, thì dưới vi phân xấp xỉ của
hàm f là ∂
ε
f(x) := {x
∗
∈ X
∗
| x
∗
, x − x ≤ f(x) − f(x) + ε ∀x ∈ X}, ε ≥ 0
Nếu ε = 0 thì ta có ∂
ε

Tucker).
Sau đây chúng tôi xin nêu một kết quả về điều kiện tối ưu cho bài toán này.
Phần chứng minh sẽ được làm rõ trong phần bài toán quy hoạch lồi tổng quát ngay
sau đây. Hai điều kiện chính quy sau đây xem trong [1].
7
Định nghĩa 1.1.6 (Điều kiện chính quy Slater) (Slater) ∃ x ∈ C, g
i
(x) < 0, i =
1, . . . , n và f liên tục tại x.
Định lý 1.1.1 [1] (Điều kiện cần và đủ dạng KKT)
Giả sử f, g
i
, i = 1, . . . , n và C thỏa mãn giả thiết của bài toán (P). Giả sử (Slater)
thỏa mãn. Khi đó a ∈ C là nghiệm cực tiểu toàn cục của (P) khi và chỉ khi
∃(λ
1
, . . . , λ
n
) ∈ R
n
+
sao cho



0 ∈ ∂f(a) +

n
i=1
λ

với giả thiết cơ bản (GTCB) sau: X, Y là các không gian định chuẩn thực, C là một
tập lồi khác rỗng của X, f : X → R là hàm lồi liên tục, S là nón lồi đóng trong Y
và g : X → Y là hàm S–lồi và liên tục.
Mô hình bài toán này là khá tổng quát, rõ ràng khi S = R
n
+
thì đó là bài toán
ta xét ở đầu mục, ngoài ra nó còn bao quát hai dạng bài toán sau:
(U) :















inff(x)
g
i
(x) ≤ 0 i = 1,. . . , n
A
1

∈ Y
2
.
Ta có thể chuyển hai bài toán này về bài toán lồi tổng quát dễ dàng.
Bây giờ, gọi A = {x ∈ X|x ∈ C, g(x) ∈ −S} là tập các điểm chấp nhận được
của (P), rõ ràng tập A là lồi đóng trong X.
Định nghĩa 1.1.7 [1] Nón đối ngẫu dương của nón lồi S, ký hiệu S
+
, được xác
định:
S
+
= {y
∗
∈ Y | < y
∗
, s > ≥ 0, ∀s ∈ S}
Định lý 1.1.2 ([1], Điều kiện cần tối ưu Fritz–John) Xét bài toán (P
tq
) và
các (GTCB) thỏa mãn và intS = ∅ và a ∈ A. Khi đó nếu a là nghiệm của (P) thì
∃λ
o
∈ R
+
, λ ∈ S
+
không đồng thời bằng 0 sao cho:



f(x) − λ
0
f(a) + λg(x) ≥ 0, ∀x ∈ C(1), cho x = a ta được λg(x) ≥ 0. Mặt
khác ta có λg(x) ≤ 0 (do λ ∈ S
+
, g(a) ∈ −S), suy ra λg(x) = 0(2).
Từ (1) và (2) ta có: λ
o
f(x)+λg(x) ≥ λ
o
f(a)+λg(a), ∀x ∈ C. Do vậy a là nghiệm
của bài toán lồi sau đây:
9
inf(λ
o
f(x) + λg(x)).
Vì λ
0
f và λg liên tục nên từ đây suy ra 0 ∈ ∂(λ
o
f + λg)(a) + N
C
(a),
Cũng vì λ
0
f và λg liên tục nên suy ra 0 ∈ ∂(λ
o
f)(a) + ∂(λg)(a) + N
C
(a).



0 ∈ ∂f(a) + ∂(λg)(a) + N
C
(a)
λg(a) = 0
Chứng minh. Dựa trên Định lý 1.1.2
a) Điều kiện cần
Theo Định lý 1.1.2, nếu a là nghiệm của bài toán thì tồn tại λ = 0 và λ ∈ R
+
×S
+
sao cho



0 ∈ λ
o
∂f(a) + ∂(λg)(a) + N
C
(a)
λg(a) = 0
Giả sử λ
o
= 0. Khi đó ta có 0 ∈ ∂(λg)(a) + N
C
(a)
Do đó tồn tại x
∗
∈ ∂(λg)(a) sao cho −x

C
(a)
điều này tương đương
f(x) + (λg)(x) ≥ f(a) + λg(a) = f(a) (do λg(a) = 0), ∀x ∈ C.
Mặt khác do x ∈ C, g(x) ∈ −S nên λg(x) ≤ 0 , suy ra f(x) ≥ f(a), ∀x ∈ A
nghĩa là x = a là nghiệm của bài toán. 
Các khái niệm thuộc lý thuyết vi phân được đề xuất bởi Clarke vào năm 1973.
Năm 1983 lý thuyết này được Clarke bổ sung và hoàn chỉnh. Ở đây ta chỉ nêu một
phần rất nhỏ của lý thuyết này, về hàm Lipschitz địa phương, đạo hàm theo hướng
Clarke và dưới vi phân Clarke.
1.2 Hàm Lipschitz và dưới vi phân Clarke
Cho hàm số thực f : R
n
→ R, và x ∈ R
n
.
Định nghĩa 1.2.1 [5] (Hàm Lipschitz địa phương) Hàm f được gọi là Lipschitz
địa phương tại x, nếu tồn tại hằng số k và ε > 0 sao cho
|f(x
1
) − f(x
2
)| ≤ k|x
1
− x
2
| ∀x
1
, x
2

f(x) := {ξ ∈ R
n
|f
o
(x; v) ≥ v, ξ, ∀v ∈ R
n
}. (1.3)
Mỗi phần tử ξ ∈ ∂
o
f(x) được gọi là dưới gradient Clarke.
Tính chất[5]
• Khi f trơn (nghĩa là khả vi chặt hay khả vi liên tục) thì ∂
o
f(x) ≡ {∇f(x)}
• Khi f lồi thì ∂
o
f(x) ≡ {ξ|f(x + u) − f(x) ≥ u, ξ}, ∀u ∈ R
n
(tập dưới vi
phân của hàm f tại x, (xem mục 1.1)).
1.3 Một số kiến thức cơ bản về giải tích đa trị
(1) Ánh xạ đa trị
Cho X, Y là hai tập bất kì. Cho F : X ⇒ Y là ánh xạ từ tập X vào toàn bộ các
tập con của Y (được kí hiệu là 2
Y
). Ta nói F là ánh xạ đa trị từ X vào Y. Như vậy
với mỗi x ∈ X, F (x) là một tập con của Y (F (x) có thể = ∅).
Nếu với mỗi x ∈ X, tập F (x) chỉ gồm đúng một phần tử của Y , thì F là ánh xạ đơn
trị từ X vào Y và thay cho kí hiệu F : X ⇒ Y thì ta sử dụng kí hiệu quen thuộc
là F : X → Y .

a
i
+
n

j=1
λ
j
v
j
: t
i
≥ 0 ∀i = 1, . . . , p,
p

i=1
t
i
= 1,
λ
j
≥ 0 ∀j = 1, . . . , n.}
Bây giờ giả sử X, Y là các không gian metric.
Định nghĩa 1.3.3 [2, Định nghĩa 1.2.1; 1.2.2; 1.2.3] Ta nói F là nửa liên tục trên
(usc) tại x ∈ dom F nếu với mọi tập mở V ⊂ Y thỏa F (x) ⊂ V tồn tại lân cận mở
U của x sao cho
F (x) ⊂ V ∀x ∈ U.
Nếu F usc tại mọi điểm thuộc dom F thì F được gọi là usc trong X
Ta nói F là nửa liên tục dưới (lsc) tại x ∈ dom F nếu với mọi tập mở V ⊂ Y thỏa
F (x) ∩ V = ∅ tồn tại lân cận mở U của x sao cho

→ x, lim
k→∞
f(x
k
) = β}.
(2) Tính chất của đồ thị trên và dưới vi phân đối với hàm
thực mở rộng
Xét hàm thực mở rộng f : X → R trong đó X là không gian Banach tùy ý. Theo
[3], ta có
epif
∗
=

ε ≥0
{ (x
∗
, x
∗
, x + ε − f (x))| x
∗
∈ ∂
ε
f(x)}.
Trong [3], ta cũng có
epi(f
1
+ f
2
)
∗

sau tương đương:
• (i) Tập epif
∗
1
+ epif
∗
2
đóng yếu
∗
trong X
∗
× R.
14
• (ii) Công thức sau thỏa
epi(f
1
+ f
2
)
∗
= (epif
∗
1
+ epif
∗
2
) (1.6)
Hơn nữa, ta có
∂(f
1

15
1.4 Dưới vi phân, nón pháp tuyến và đối đạo hàm
Mordukhovich
Xét ánh xạ đa trị F : X ⇒ X
∗
giữa không gian Banach X và không gian đối
ngẫu X
∗
của nó. Kí hiệu
lim sup
x→x
F (x) := {x
∗
∈ X
∗
|∃x
k
→ x, x
∗
k
→
w
∗
x
∗
, x
∗
k
∈ F (x
k

, x − x
||x − x||
≥ −ε}. (1.9)
Tập
ˆ
∂
ε
f(x) được gọi là ε− dưới vi phân Fréchet của f tại x, còn các phần tử của
nó là ε− dưới gradient Fréchet của f tại x.
Tập
ˆ
∂f(x) :=
ˆ
∂
o
f(x) được gọi là dưới vi phân Fréchet của f tại x
(rõ ràng
ˆ
∂f(x) ⊂
ˆ
∂
ε
f(x)).
Định nghĩa 1.4.2 ([2], Dưới vi phân Mordukhovich)
Tập hợp
∂f(x) := lim sup
x→
f
x, ε↓0
ˆ

lim
x→x, u→x
f(x) − f(x) − x
∗
, x − u
||x − u||
= 0.
Nếu X là không gian hữu hạn chiều thì hai khái niệm này là như nhau (xem [2],
chương 3).
Nhận xét 1.4.1 [2, Mệnh đề 4.2.1; 4.2.2] Nếu f khả vi chặt tại x thì tập ∂f(x) chỉ
chứa một phần tử đó là đạo hàm hàm chặt của f tại x.
Nếu f là hàm lồi thì tập ∂f(x) trùng với dưới vi phân của giải tích lồi (1.1) phần
trên.
Bây giờ chúng ta tìm hiểu cụ thể các đối tượng nón pháp tuyến và đối đạo hàm.
Dựa trên nền tảng các đối tượng giải tích do Mordukhovich đề xuất, ta tách các
trường hợp. Mục đích của việc tách là chúng ta xét hàm thực mở rộng trong trường
hợp không gian Banach tùy ý và trong không gian hữu hạn, sẽ sử dụng cho bài toán
hai cấp vô hạn và bài toán hai cấp hữu hạn (xem cụ thể chương 3 và chương 4
dưới đây).
Trường hợp: f : X → R trong đó X là không gian Banach tùy ý. Nhắc
lại, hàm chỉ số
δ(x; Ω) =



0 nếu x ∈ Ω
∞ nếu otherwise
trong đó Ω ⊂ X.
Bây giờ nhắc lại nón pháp tuyến cổ điển khi tập Ω lồi tại x ∈ Ω, xác định bởi
N(x; Ω) := ∂δ(x; Ω) = {x

|∃x
k
→
Ω
x, ε
k
→ 0
+
và x
∗
k
→
w
∗
x
∗
:
lim sup
x→
Ω
x
k
x
∗
, x − x
k

||x − x
k
||

F (x, y) (y
∗
) :=

x
∗
∈ X
∗
|(x
∗
, −y
∗
) ∈ N((x, y); gph F )

. (1.15)
Nếu F (x) = f(x) đơn trị, thì chúng ta viết
ˆ
D
∗
f(x) thay cho
ˆ
D
∗
f(x, f(x)) và viết
D
∗
f(x) thay cho D
∗
f(x, f(x)). Khi đó nếu f tương ứng là khả vi Fréchet và khả
vi chặt tại x thì các đối đạo hàm phía trên xác định như sau:

ˆ
D
∗
f(x)(y
∗
) và D
∗
f(x)(y
∗
) là các tập chỉ chứa một phần
tử. Nếu f khả vi chặt, thì hai tập này bằng nhau
D
∗
f(x)(y
∗
) =
ˆ
D
∗
f(x)(y
∗
) = (∇f(x))
∗
(y
∗
) ∀y
∗
∈ Y
∗
.

Các khái niệm sau xem cụ thể trong ([14], mục 2).
Đầu tiên, chúng ta tìm hiểu khái niệm nón pháp tuyến mở rộng của một tập
khác rỗng.
Cho tập Ω ⊂ R
n
và x ∈ Ω ; khi đó nón pháp tuyến của Ω tại x xác định bởi
N(x; Ω) := lim sup
x→
Ω
x
ˆ
N(x; Ω) (1.16)
với
ˆ
N(x; Ω) là nón pháp Fréchet của Ω tại x ∈ Ω, xác định như sau:
ˆ
N(x; Ω) := {v ∈ R
n
| lim sup
u→
Ω
x
v, u − x
u − x
≤ 0} (1.17)
trong đó ” lim sup ” là giới hạn trên theo nghĩa Painlevé-Kuratowski của một ánh
xạ đa trị S : R
n
⇒ R
m

∗
S(x, y) : R
m
→ R
n
với giá trị
D
∗
S(x, y)(v) := {u ∈ R
m
|(u, −v) ∈ N((x, y); gphS)}, v ∈ R
m
.
19
Đây chính là ánh xạ đối đạo hàm của S tại (x, y).
Nếu S đơn trị và khả vi chặt tại x với gradient ∇S(x) nghĩa là
lim
x→x,u→x
S(u) − S(v) − ∇S(x), u − x
u − x
= 0
(điều này hiển nhiên vì S khả vi liên tục quanh x) , do đó
D
∗
S(x)(v) = {∇S(x)
∗
v} ∀v ∈ R
n
.
Công thức này là đạo hàm mở rộng của toán tử đạo hàm liên hợp của ánh xạ đơn

nửa compac trong (inner semicompact) tại x nếu với mỗi dãy x
v
→ x với S(x
v
) = ∅
thì có một dãy y
v
∈ S(x
v
) chứa một dãy con hội tụ khi v → ∞. Rõ ràng trong
không gian hữu hạn chiều thì "inner semicompactness" thỏa khi S là bị chặn đều
("uniformly bounded") quanh x nghĩa là có một lân cận U của x và tập C bị chặn
⊂ R
m
sao cho
S(x) ⊂ C khi x ∈ U.
20
Tiếp theo ta tìm hiểu một khái niệm khác, cho ánh xạ đa trị S : R
n
⇒ R
m
, ta
nói S là nửa liên tục trong (inner semicontinuous) tại (x, y) ∈ gphS nếu với bất kì
dãy x
v
→ x thì có một dãy y
v
∈ S(x
v
) hội tụ về y khi v → ∞.

(the lower level problem).
Ta xét dạng của bài toán cấp trên:
min
x
F (x, y) sao cho G
k
(x, y) ≤ 0, k ∈ K, x ∈ X, y ∈ Ψ(x), (2.1)
trong đó Ψ(x) là tập nghiệm tối ưu của bài toán cấp dưới:
min
y
f(x, y) sao cho g
i
(x, y) ≤ 0, i ∈ I, h
j
(x, y) = 0, j ∈ J. (2.2)
22
Thông thường khi nghiên cứu điều kiện tối ưu thì người ta ít xét đến các ràng buộc
đẳng thức h
j
(x, y) = 0 (trong luận văn chúng tôi chỉ trình bày bài toán tối ưu hai
cấp bao gồm cả ràng buộc đẳng thức thế này, trong phần đầu của chương 3. Các
phần còn lại của chương 3 và toàn bộ chương 4, chúng tôi bỏ đi ràng buộc đẳng
thức này). Để hiểu một cách rõ ràng hơn, chúng tôi chia làm 3 lớp bài toán khác
nhau.
(a) Lớp bài toán tối ưu hai cấp hữu hạn
Các hàm thực F, G
k
, f, g
i
, h

y
{f(x, y)|g
i
(x, y) ≤ 0} nếu không gồm ràng buộc đẳng thức.
Số lượng các ràng buộc hữu hạn, nghĩa là i ∈ I hữu hạn, j ∈ J hữu hạn, k ∈ K hữu
hạn.
(b) Lớp bài toán tối ưu hai cấp vô hạn
Các hàm thực mở rộng F, f : X × Y → R, với R = R ∪ {+∞; −∞} trong không
gian Banach X, Y tùy ý.
Hàm thực mở rộng g
t
: R
n
× R
m
→ R với t ∈ T, T là tập chỉ số vô hận.
(c) Lớp bài toán tối ưu hai cấp nửa vô hạn
Tương tự như ở lớp bài toán tối ưu hai cấp vô hạn, nhưng nếu chúng ta xét trong
không gian hữu hạn chiều và giữ nguyên các giả thiết còn lại thì nó trở thành lớp
bài toán tối ưu hai cấp nửa vô hạn.
Trong luận văn chỉ xét hai lớp bài toán (a) và (b).
Tùy các tính chất khả vi liên tục, khả vi chặt, hay lồi, lipschitz. . . mà chúng ta
có các lớp bài toán được chia nhỏ tương ứng, là bài toán trơn, lồi, lồi hoàn toàn,
lipschitz. ... Vấn đề này sẽ được tìm hiểu cụ thể ở các chương sau. Đặt
ϕ(x) := inf
y
{f(x, y) sao cho g(x, y) ≤ 0, h(x, y) = 0}.
thì ϕ được gọi là hàm giá trị tối ưu của bài toán cấp dưới.
23
Bây giờ, để hiểu về quá trình hình thành bài toán, ta hãy đến với mô hình kinh

1
(x, y), . . . , h
q
(x, y)).
Đặt Ψ(x) là tập nghiệm tối ưu của bài toán này,
Ψ(x) := arg min
y
{f(x, y)|g(x, y) ≤ 0, h(x, y) = 0} (2.4)
Như vậy bài toán của ông chủ có dạng như (2.1), bao gồm cực tiểu hóa hàm
F : R
n
× R
m
→ R sao cho y ∈ Ψ(x) và x ∈ X với X tập đóng, X ⊆ R
n
, nghĩa là
giải quyết bài toán sau:
min
x
F (x, y) sao cho x ∈ X, y ∈ Ψ(x). (2.5)
trong đó Ψ(x) xác định như (2.4).
Nguyên nhân bởi vì ông chủ điều khiển chỉ mỗi biến x, do đó bài toán hai cấp chỉ
24