BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC SƯ PHẠM TP. HỒ CHÍ MINH
KHOA TOÁN-TIN HOC
NGHIỆM THU ĐỀ TÀI CẤP CƠ SỞ

Định lí Farkas mở rộng cho hệ
có chứa ràng buộc lồi đảo và ứng dụng

Mã số: CS.2005.23.77
Người thực hiện: PGS.TS. Nguyễn Định

VÀO LÍ THUYẾT CÁC BÀI TOÁN TỐI ƯU LỒI
1 Giới thiệu
Bổ đề Farkas cổ điển được phát biểu như sau:
Bổ đề 1.1 Giả sử a
1
, a
2
, , a
m
, c ∈ R
n
. Khi đó các mệnh đề sau là tương đương:
(i) a
T
i
x ≥ 0, i = 1, 2, , m =⇒ c
T
(x) ≥ 0,
(ii) (∃λ
i
≥ 0, i = 1, 2, , m) c =

m
i=1
λ
i
a
i
.
Dạng cổ điển và đơn giản này đã được áp dụng một cách hiệu quả để nghiên cứu nhiều

ε
f(a) = ∅ nếu  > 0. Khi  = 0 ta quay trở lại khái niệm dưới vi phân của
hàm f tại a theo nghĩa thông thường của giải tích lồi. Trong trường hợp này ta sẽ kí hiệu
là ∂f (a) (thay vì ∂
0
f(a)). Dưới vi phân của một hàm lồi luôn là tập lồi, compact yếu
∗
(có
thể là tập rỗng).
2
2 Các kết quả dạng Farkas mở rộng
Sự thành công của việc vận dụng Bổ đề Farkas trong các bài toán tối ưu tuyến tính cũng
như sự hữu ích của nó trong việc nghiên cứu các bài toán tối ưu phi tuyến đẫ dẫn đến nhu
cầu mở rộng bổ đề này cho các hệ tuyến tính vô hạn chiều, các hệ phi tuyến, các hệ liên
quan đến các ánh xạ đa trị, Chúng ta sẽ đề cập ở đây một số dạng mở rộng tiêu biểu.
Tuy nhiên, chỉ có một số kết quả quan trọmg mới đây sẽ được trình bày chi tiết.
• Bổ đề Farkas cho hệ tuyến tính vô hạn chiều.
• Bổ đề Farkas cho hệ không trơn.
• Các kết qủa mở rộng dạng Farkas cho các hệ lồi theo nón.
Trong mục này chúng ta sẽ điểm qua một số kết qủa mở rộng Bổ đề Farkas được công
bố trong những năm vừa qua, chủ yếu của các tác giả V. Jeyakumar, G.M. Lee, M.A.
Goberna, M.A. Lopez và Nguyễn Định (xem chi tiết trong [1]).
Cho X, Z là hai không gian định chuẩn, C là một tập lồi đóng của X, S là một nón
lồi đóng trong Z còn g : X → Z là một ánh xạ S-lồi, liên tục và f : X → R là một hàm
lồi lên tục.
Định lí 2.1 (Bổ đề Farkas dạng tiệm cận) Giả sử hệ x ∈ C, g(x) ∈ −S là tương thích.
Khi đó với mọi α ∈ R,các phát biểu sau là tương đương:
(i) inf{f(x) : g(x) ∈ −S, x ∈ C} ≥ α,
(ii) (0, −α) ∈ epif
∗

∗
+ epi δ
∗
C
là đóng yếu
∗
.
Người ta chứng minh được rằng (xem [JDL]) điều kiện (CCCQ) yếu hơn các điều kiện
dạng mở rộng của các điều kiện dạng Slater mở rộng (cũng thường gọi là các điều kiện
điểm trong, thường được sử dụng trong các bài toán tối ưu lồi).
3
Định lí 2.2 (Bổ đề Farkas dạng không tiệm cận) Giả sử tập C ∩ g
−1
(−S) là không rỗng
và α ∈ R. Nếu điều kiện (CCCQ) thỏa mãn thi các phát biểu sau là tương đương:
(i) g(x) ∈ −S, x ∈ C =⇒ f(x) ≥ α,
(ii) (0, −α) ∈ epi f
∗
+ ∪
λ∈S
+
epi (λg)
∗
+ epi δ
∗
C
,
(iii) (∃λ ∈ S
+
)(∀x ∈ C) f(x) + λg(x) ≥ α.

∗
+ clK is weak
∗
-closed.
Bây giờ chúng ta nêu ra Bổ đề Farkas dạng mở rộng và không tiệm cận.
Định lí 2.3 Nếu σ là FM, (CC) thỏa mãn và α ∈ R, thì các mệnh đề sau là tương đương.
(i) f (x) ≥ α là hệ quả của σ;
(ii) (0, −α) ∈ epif
∗
+ K;
(iii) tồn tại λ ∈ R
(T )
+
sao cho
f(x) +

t∈T
λ
t
f
t
(x) ≥ α, ∀x ∈ C.
3 Một số áp dụng vào bài toán tối ưu
Bài toán lồi với ràng buộc lồi theo nón.
Xét bài toán tối ưu lồi tổng quát
(P) Minimize f(x)
với ràng buộc x ∈ C, −g(x) ∈ S,
trong đó X, Y là các không gian định chuẩn thực, f : X → R là một hàm lồi, g : X →
là một ánh xạ S-lồi, liên tục với S là một nón lồi đóng trong Y (không nhất thiết có phần
trong khác rỗng) và C là một tập lồi đóng trong X.

n
}, {w
n
} ⊂ X

) sao
cho v
n
∈ ∂

n
(λ
n
g)(a), w
n
∈ ∂
γ
n
δ
C
(a), u + v
n
+ w
n
→
∗
0, 
n
→ 0, γ
n

lim inf
n→∞
L(x, λ
n
)
= inf
x∈C
lim inf
n→∞
L(x,
¯
λ
n
) = inf(P ).
Bài toán lồi vô hạn
Xét bài toán lồi vô hạn
(PI) Minimize f(x)
với ràng buộc f
t
(x) ≤ 0, ∀t ∈ T,
x ∈ C,
trong đó X là một không gian vectơ tôpô lồi địa phương Hausdorff, C ⊂ X là một tập
lồi đóng và f, f
t
: X → R ∪ {+∞} là các hàm lồi chân chính, l.s.c., mọi t ∈ T . Gọi
A := {x ∈ X | f
t
(x) ≤ 0, ∀t ∈ T, x ∈ C}.
Định lí 3.4 [DGLS] (Điều kiện tối ưu) Đối với bài toán (PI), giả sử rằng điều kiện (CC)
thỏa mãn, a ∈ A. Nếu thêm σ là FM thì a là một nghiệm của (PI) nếu và chỉ nếu tồn tại

C ∩ h
−1
(−S) ⊂ domg. Hạn chế về tính phản xạ của không gian X chỉ để tránh việc sử
dụng lưới (net). Các kết quả trong bài này vẫn còn đúng trong không gian vectơ tôpô tổng
quát.
Gọi K là nón lồi xác định bởi
K := ∪
λ∈S
+
epi(λh)
∗
+ epiδ
∗
C
.
Chúng ta sẽ sử dụng các điều kiệ n sau đây, liên quan đến hệ h(x) ∈ −S, x ∈ C và
hàm lsc, lồi, chân chính f :
(CC1) epif
∗
+ clK là đóng yếu
∗
.
(CC2) epif
∗
+ K là đóng yếu
∗
.
Để ý rằng điều kiện (CC1) sẽ được thoả mãn nếu f liên tục tại một điểm nào đó trong
C ∩ h
−1

∗
) + α,
(iv) (∀ > 0) (∀x ∈ C ∩ domg) (∃(λ
n
)
n
⊂ S
+
)
f(x) + lim inf
n→∞
λ
n
h(x) − g(x) ≥ α − .
Định lí 2. (Bổ đề Farkas dạng không tiệm cận) Cho α ∈ R. Nếu điều kiện (CC2) thoả
mãn thì các mệnh đề sau là tương đương
(i) h(x) ∈ −S, x ∈ C =⇒ f(x) − g(x) ≥ α,
(ii) (0, −α) + epi g
∗
⊂ epi f
∗
+ K,
6
(iii) (∀x
∗
∈ domg
∗
)(∃λ ∈ S
+
)(∀x ∈ C)

),
(iii’) (∃(λ
n
)
n
⊂ S
+
)(∀x ∈ C) f(x) + lim inf
n→∞
λh(x) ≥ α.
Hệ quả 3. Giả sử C ∩ h
−1
(−S) khác rỗng và α ∈ R. Nếu f liên tục tại một điểm nào
đó trong C ∩ h
−1
(−S) và điều kiện K là đóng yếu
∗
thì các mệnh đề sau là tương đương:
(i”) h(x) ∈ −S, x ∈ C =⇒ f(x) ≥ α,
(ii”) (0, −α) ∈ epi f
∗
+ ∪
λ∈S
+
epi (λh)
∗
+ epi δ
∗
C
,

(P

): inf
x∈A
f(x) − g(x)
hoặc là
(P

): inf
x∈X
[(f(x) + δ
A
(x)) − g(x)]
Một điều kiện cần để một điểm a ∈ A là cực tiểu toàn cục của (P) là:
∂g(x
0
) ⊂ ∂(f + δ
A
)(x
0
).
Dưới một điều kiện chính quy nào đó, điều kiện vừa nêu có thể viết lại là:
∂g(x
0
) ⊂ ∂f (x
0
) + N
A
(x
0

1
, 
2
, 
3
≥ 0 sao cho 
1
+ 
2
+ 
3
=  + λh(¯x) và
x
∗
∈ ∂

1
f(¯x) + ∂

2
(λh)(¯x) + N

3
(C, ¯x). (3)
Đặc biệt, nếu ¯x ∈ A là một nghiệm toàn cục của (P) thì với mỗi x
∗
∈ ∂g(¯x), tồn tại
λ ∈ S
+
sao cho

1
,
2
≥0
{∂

1
f(¯x) + ∂

2
(λh)(¯x)} . (4)
Đặc biệt, nếu ¯x là một nghiệm của (P) thì
∂g(¯x) ⊂

λ∈S
+
λh(¯x)=0
{∂f(¯x) + ∂(λh)(¯x)}. (5)
3 Áp dụng
Trong mục này các kết quả đạt được trong Mục 2 sẽ được áp dụng để nghiên cứu các
lớp toán cụ thể, chẳng hạn, lớp các bài toán DC với ràng buộc lồi, lớp các bài toán trong
đó hàm g là hàm đa diện (maximum của một họ hữu hạn các hàm tuyến tính), bài toán
maximum một phiếm hàm lồi trên một tập lồi.
3.1 Bài toán DC với ràng buộc lồi
Xét bài toán:
(PCI): inf
x∈C, h
i
(x)≤0, i∈I,
f(x) − g(x),

| λ
i
≥ 0, i ∈ I, λ
i
= 0 voi moi i tru mot so huu han i ∈ I}
Gọi A := {x ∈ C, h
i
(x) ≤ 0, ∀i ∈ I}. Kí hiệu h := (h
i
). Dễ dàng nhận thấy rằng
h : X −→ Z là liên tục, S-lồi và rằng Bài toán (PCI) có thể viết lại dưới dạng Bài toán
(P). Giả sử rằng A := h
−1
(−S) ∩ C là một tập không rỗng của X.
Điều kiện tối ưu cho (PCI) được cho ở định lí sau:
Định lí 3.1 Giả sử rằng inf (PCI) < +∞ và rằng epif
∗
+ cone

i∈I
epih
i
∗
+ epiδ
∗
C
là
một tập đóng yếu
∗
. Khi đó, ¯x là một nghiệm tối ưu toàn cục của (PCI)nếu và chỉ nếu với

∈ ∂
α
f(¯x) +

i∈I
∂

i
(λ
i
h
i
)(¯x) + N
β
(C, ¯x).
Đặc biệt, nếu ¯x là một nghiệm tối ưu toàn cục của (PCI) thì với mọi x
∗
∈ ∂g(¯x), tồn tại
(λ
i
) ∈ R
(I)
+
sao cho
x
∗
∈ ∂f(¯x) +

i∈I
λ

∗
. Hàm g như thế được gọi là một hàm lồi
đa diện. Ta có
epig
∗
= cl

co


i∈I
({a
∗
i
} × [−b
i
, +∞))

.
Điều kiện tối ưu cho (P) trong trường hợp này được cho ở định lí sau:
3
Định lí 3.2 Đối với Bài toán (P), giả sử rằng C = X và g là một hàm lồi đa diện xác
định bởi (7). Giả sử thêm nữa rằng {h(x) ∈ −S} = ∅ và epif
∗
+

λ∈S
+
epi(λh)
∗

2
(λ
i
h)(¯x)} , (8)
trong đó α
i
:= λ
i
h(¯x) + g(¯x) − g
i
(¯x) ≥ 0.
3.3 Bài toán cực đại một hàm lồi trên một tập lồi
Xét bài toán cực đại hóa một hàm lồi sau:
(PM): sup
x∈C, h(x)∈−S
p(x)
trong đó p : X −→ R ∪{+∞} là một hàm lồi chân chính, nửa liên tục dưới, h : X −→ Z
là một ánh xạ liên tục, S-lồi. Các không gian X, Z, các tập C, nón S như ở các Mục 1 và
2.
Bài toán (PM) tương đương với bài toán sau:
(PM1): inf
x∈C, h(x)∈−S
−p(x).
Để ý rằng sup(P M) = −inf(P M1). Điều kiện cần và đủ tối ưu cho (PM) được thiết lập
nhờ vào Định lí 2.1 ở Mục 2.
Định lí 3.3 Giả sử rằng sup (PM) > −∞ và K := K := ∪
λ∈S
+
epi(λh)
∗

(C, ¯x). (9)
Đặc biệt, nếu ¯x là nghiệm toàn cục của (PM) thì với mỗi x
∗
∈ ∂p(¯x) tồn tại λ ∈ S
+
sao
cho
x
∗
∈ ∂(λh)(¯x) + N(C, ¯x) v λh(¯x) = 0.
4
KẾT LUẬN
Đề tài đã nêu lên một bức tranh về sự phát triển của Bổ đề Farkas trong vài thập niên
qua. Qua đó nêu lên được tầm quan trọng của kết quả dạng này trong lí thuyết tối ưu hiện
đại. Thông qua việc phát tr iển, mở rộng của kết quả quan trọng này, các điều kiện chính
quy (mà nhờ có nó các điều kiện cần tối ưu dạng Karush-Kuhn-Tucker mới có thể được
thiết lập) cũng được làm yếu đi một cách đáng kể.
Đề tài cũng đã lần đầu tiên đề xuất các dạng mở rộng của Bổ đề Farkas cho các hệ có
chứa các ràng buộc dạng DC. Các kết quả này có giá trị một cách độc lập. Nó có thể dùng
để thiết lập các đặc trưng cho các bao hàm thức của một tập lồi chứa trong một tập DC.
Các kết quả này mở rộng các kết quả mới công bố gần đây của chủ nhiệm đề tài với các
đồng nghiệp V. jeyakumar, M.A. Bober na, G.M. Lee (2005, 2006).
Với những kết quả dạng Farkas mở rộng ở trên, đề tài cũng đề xuất một cách tiếp cận
mới đối với lớp các bài toán quy hoạch DC, lớp bài toán khó mà cho tới hiện nay, theo sự
hiểu biết của chúng tôi, các kết quả nghiên cứu định tính đang còn khá thưa thớt.
Kết quả đạt được của đề tài có thể xem như những khởi đầu cho một cách tiếp cận
nghiên cứu các bài toán quy hoạch DC. Rất nhiều điều cần phải được tiếp tục nghiên cứu
theo hướng này, chẳng hạn, các kết quả về đối ngẫu, ổn định với nhiễu, của lớp toán
này.
Tài liệu