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
∈ S, ∀i ∈ I;
i∈I
α
i
= 1, | I |< ∞}.
Như vậy, bao lồi của K là tập lồi nhỏ nhất chứa K.
Định nghĩa 1.1.2 [1] Cho hàm số f : X → R. Khi đó f được gọi là hàm lồi nếu
∀x, y ∈ X, ∀λ ∈ [0, 1], λf (x) + (1 − λ)f (y) ≥ 0.
Cho X, Y là các không gian vectơ. S là nón lồi trong Y .
Định nghĩa 1.1.3 [1] Cho hàm số f : X → Y . Khi đó f được gọi là hàm S–lồi nếu
5
∀x, y ∈ X, ∀λ ∈ [0, 1], λf (x) + (1 − λ)f (y) − f(λx + (1 − λ)y) ∈ S.
Nhận xét 1.1.1 Trường hợp f lồi là một trường hợp đặc biệt của hàm S–lồi khi
S = R
+
.
(2) Dưới vi phân của hàm lồi, đối ngẫu của hàm lồi
(a) Dưới vi phân của hàm lồi
Cho f là hàm số lồi, một hàm số lồi thì có thể không có đạo hàm do đó ta xét
tới khái niệm sau. Chúng ta cần nêu ra vài khái niệm cơ bản:
Hàm số thực mở rộng f : X → R trong đó trong đó R = R
{+∞; −∞}
Miền hữu hiệu (domain) domf := {x ∈ X|f(x) < ∞} và đồ thị trên (epigraph)
epif := {(x, α) ∈ X × R|f(x) ≤ α}.
Định nghĩa 1.1.4 [1] Cho hàm số f : X → R lồi, và X
∗
là không gian đối ngẫu
của không gian vectơ X. Giả sử x
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
đó ∂f(x
o
) còn gọi là tập các dưới gradient.
Đây là định nghĩa dưới vi phân cổ điển của hàm số f. Các phần sau ta sẽ nêu các
định nghĩa dưới vi phân mở rộng.
(b) Đối ngẫu của hàm lồi
Cho X là không gian Banach và hàm f : X → R lồi, luôn luôn proper nghĩa là
f(x) = ∞ trên X. Gọi X
∗
là không gian đối ngẫu của X.
6
Định nghĩa 1.1.5 [1] Hàm đối ngẫu f
∗
: X
∗
→ R của f, được xác định như sau:
f
∗
(x
∗
) := sup{x
∗
, x − f(x)|x ∈ X}.
Nhận xét 1.1.2 Do f(x) = +∞(x ∈ domf) suy ra sup {x
∗
, x − f(x)|x ∈ X}
luôn = ∅ nên f
∗
(x
∗
) 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ó ∂
ε
f(x) = ∂
o
f(x) là dưới vi phân cổ điển có dạng như (1.1).
(3) Bài toán quy hoạch lồi và điều kiện tối ưu
(a) Bài toán quy hoạch lồi đơn giản
Xét bài toán (P) :
inff(x)
g
i
(x) ≤ 0 i = 1,. . . , n
x ∈ C
trong đó X là không gian định chuẩn, C là tập lồi đóng trong X, f : X → R là hàm
lồi, g
i
: X → R là hàm lồi liên tục.
Một bài toán tối ưu có dạng như bài toán (P) ở trên được gọi là bài toán quy hoạch
lồi đơn giản. Sau đây ta sẽ xét các điều kiện tối ưu phổ biến của bài toán này.
Điều kiện tối ưu, nói đầy đủ là điều kiện tối ưu cho một số lớp bài toán tối ưu có
nghiệm (nghiệm địa phương hay toàn cục). Thông thường người ta tìm được điều
kiện cần, còn điều kiện đủ thì khó khăn hơn. Các dạng điều kiện phổ biến là điều
kiện tối ưu dạng Fritz John và điều kiện tối ưu dạng KKT (Karush–Kuhn-
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
λ
i
∂g
i
(a) + N
C
(a)
λ
i
g
i
(a) = 0∀i = 1, . . . , n
trong đó ∂f(x) kí hiệu cho dưới vi phân của hàm số f tại điểm x.
(b) Bài toán quy hoạch lồi tổng quát
Một bài toán tối ưu có dạng như bài toán sau đây được gọi là bài toán quy hoạch
lồi tổng quát
(P
tq
) :
inff(x)
g(x) ∈ −S
x ∈ C
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
x = b
1
x ∈ C
8
trong đó A
1
∈ L(X, R
m
) và b
1
∈ R
m
.
Một bài toán thứ hai cũng tương tự như bài toán (U), chỉ thay A
1
x = b
1
bởi A
2
x = b
2
, và thay i ∈ {1, . . . , n} bởi i ∈ I trong đó I là tập chỉ số tùy ý,
A
2
∈ L(X, Y
2
) với Y
2
là không gian định chuẩn và b
2
∈ 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:
0 ∈ λ
o
∂f(a) + ∂(λg)(a) + N
C
(a)
λg(a) = 0
trong đó ∂f(x) ký hiệu cho dưới vi phân của hàm số f tại điểm x.
Chứng minh.
Vì a ∈ A là nghiệm của (P
tq
) nên hệ sau vô nghiệm theo x ∈ C :
−(f(x) − f(a)) ∈ intR
+
, g(x) ∈ −S, x ∈ C
Do vậy hệ sau vô nghiệm −(f(x) − f(a), g(x)) ∈ int(R
+
× S), x ∈ C, nghĩa là tồn
tại λ = (λ
o
, λ) ∈ (R
+
× S)
+
với λ = (0, 0) sao cho
λ(f(x) − f(a), g(x)) = λ
0
(f(x) − f(a)) + λg(x) ≥ 0, ∀x ∈ C
hay λ
o
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).
Vậy định lý được chứng minh.
Chú ý : Nếu λ
0
= 0 thì điều kiện sẽ không chứa thông tin gì về hàm mục tiêu f
và do đó sẽ không có giá trị gì. Do đó việc khẳng định λ
0
= 0 là hết sức quan trọng.
Các điều kiện đặt trên các biểu thức sao cho λ
o
= 0 và có thể chọn λ
o
= 1. Một
trong các điều kiện quan trọng là điều kiện chính quy Slater (mở rộng) và điều kiện
chính quy Kartin:
Định nghĩa 1.1.8 Điều kiện chính quy Slater mở rộng (SCQ): ∃ x ∈ C sao
cho −g(x) ∈ intS
Điều kiện chính quy Kartin (KCQ): λ ∈ S
+
và λ = 0 sao cho λg(x) ≥ 0, ∀x ∈
C.
Định lý 1.1.3 ([1], Điều kiện cần và đủ KKT) Giả sử các giả thiết như trên
Định lý 1.3.2 và thêm (KCQ) thỏa mãn. Khi đó ta có kết luận như trên với λ
o
= 1
nghĩa là a là nghiệm của (P
tq
) khi và chỉ khi tồn tại λ ∈ S
+
sao cho hệ sau thỏ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
∗
∈ N
C
(a) hay x
∗
(x − a) ≥ 0, ∀x ∈ C. Vậy
(λg)(x) − (λg)(a) ≥ x
∗
(x − a) ≥ 0
10
kết hợp (λg)(a) = 0 suy ra (λg)(x) ≥ 0 mâu thuẫn với (KCQ). Vậy λ
0
= 0 do đó có
thể lấy λ
0
= 1,
nghĩa là ta có hệ cần chứng minh.
b) Điều kiện đủ
Giả sử có λ ∈ S
+
sao cho
0 ∈ ∂f(a) + ∂(λg)(a) + N
C
(a)
λg(a) = 0
hay
0 ∈ ∂(f + λg)(a) + N
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
∈ x + εB (1.2)
với B là quả cầu đơn vị trong R
n
.
11
Định nghĩa 1.2.2 [5] (Đạo hàm theo hướng của hàm Lipschitz địa phương)
Cho f Lipschitz địa phương tại x, và v là vecto bất kì trong R
n
. Khi đó đạo hàm
theo hướng v của hàm f tại x, kí hiệu f
o
(x; v) xác định như sau:
f
o
(x; v) := lim sup
x
→x, t↓0
f(x
+ tv) − f(x
)
t
Định nghĩa 1.2.3 [5](Dưới vi phân Clarke) Dưới vi phân Clarke của hàm f tại
x, kí hiệu ∂
o
f(x) xác định như sau:
∂
o
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 .
Định nghĩa 1.3.1 [2, Định nghĩa 1.1.1] Đồ thị và miền hữu hiệu của ánh xạ đa trị
F : X ⇒ Y tương ứng được xác định như sau:
gph F = {(x, y) ∈ X × Y |y ∈ F (x)}, (1.4)
dom F = {x ∈ X|F (x) = ∅}. (1.5)
12
Nhắc lại, nếu ánh xạ đơn trị, là hàm thực mở rộng f : X → R thì miền hữu
hiệu domf := {x ∈ X|f(x) < ∞} và đồ thị trên (epigraph) epif := {(x, α) ∈
X × R|f(x) ≤ α}.
Định nghĩa 1.3.2 [21, Định lý 19.1] Tập M ⊂ R
n
được gọi là tập lồi đa diện
(polyhedral convex set) nếu M có thể biểu diễn được dưới dạng giao của một số hữu
hạn nửa không gian đóng của R
n
, nghĩa là tồn tại các điểm a
1
, . . . , a
p
∈ M và các
phương v
1
, . . . , q ∈ R
n
sao cho
M = {
p
i=1
t
i
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
F (x) ∩ V = ∅ ∀x ∈ U ∩ dom F.
Nếu F lsc tại mọi điểm thuộc dom F thì F được gọi là lsc trong X
Ta nói F là liên tục tại x ∈ dom F nếu F đồng thời usc và lsc tại x. Nếu F liên tục
tại mọi điểm thuộc dom F thì F được gọi là liên tục trên X.
Xét hàm thực mở rộng f : X → R với X là không gian metric.
Định nghĩa 1.3.4 [2]
Ta nói f là usc tại x ∈ dom f nếu
lim inf
x→x
f(x) ≥ f(x)
13
Không có nhận xét nào:
Đăng nhận xét