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

Đề tài: Định lý Farkas mở rộng cho hệ có chứa ràng buộc lồi đảo và ứng dụng
TÓM TẮT KẾT QUẢ NGHIÊN CỨU CỦA ĐỀ TÀI
Đị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
BÁO CÁO TỔNG QUAN
Bổ đề Farkas đóng một vai trò cơ bản trong lí thuyết tối ưu tuyến tính cũng như tối ưu
phi tuyến. Trong những thập niên vừa qua, Bổ đề Farkas đã được mở rộng và phát triển
ra cho các hệ tuyến tính (vô hạn chiều), các hệ phi tuyến cũng như các hệ đa trị, dưới các
dạng khác nhau. Cùng với các mở rộng này là áp dụng của nó vào lí thuyết quy hoạch
lồi nửa vô hạn, quy hoach lồi tổng quát, các bài toán quy hoạch lồi nửa các định (convex
semi-definite programs (SDP)), các bài toán tối ưu đa mục tiêu.
Kết quả nghiên cứu của đề tài đã được viết thành 3 bài báo trong đó có 2 bài đăng
trong Tạp chí Khoa học của Trường Đại học Sư phạm Tp. Hồ Chí Minh và 1 bài sẽ gửi
đăng trên một tạp chí toán quốc tế. Các kết quả này sẽ được trình bày trong 3 chương sau
đây và toàn văn 3 bài báo sẽ được đính kèm ở phần sau trong tập báo cáo nghiệm thu này.
Chương 1 trình bày tổng quan sự phát triển của các dạng mở rộng của Bổ đề Farkas
trong các thập niên gần đây, bao gồm các dạng trong không gian hữu hạn chiều và không
gian vô hạn chiều; cả các dạng tiệm cận và không tiệm cận mới được thiết lập trong những
năm cuối của thế kỉ 20 và những năm đầu của thế kỉ 21, cùng với những áp dụng đa dạng
của các dạng mở rộng này trong lý thuyết tối ưu. Chương 2 là các kết quả mới của đề tài,
mở rộng Bổ đề Farkas cho các hệ có chứa các bất đẳng thức lồi và các bất đẳng thức DC.
Chương 3, trình bày các áp dụng của các dạng mở rộng của Bổ đề Farkas vào các bài toán
quy hoạch DC với ràng buộc lồi theo nón và ràng buộc tập.
1Chương I
CÁC KẾT QUẢ DẠNG FARKAS MỞ RỘNG VÀ ÁP DỤNG
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ử a1, a2, , am, 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 =
Pm
i=1
λiai
.
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
lớp các bài toán tối ưu tuyến tính cũng như phi tuyến. Điều này là động lực để các nhà
toán học tìm kiếm các dạng tổng quát hơn nhằm mở rông phạm vi áp dụng của nó, chẳng
hạn vào các bài toán điều khiển tối ưu, các bài toán quy hoạch vô hạn hoặc áp dụng vào
lớp các bài toán nửa xác định đang phát triển và có rất nhiều ứng dụng trong những năm
gần đây.
Để có thể trình bày các mở rộng của Bổ đề Farkas, trước hết ta nêu ra một số khái
niệm cơ bản của giải tích lồi mà chúng ta sẽ sử dụng thường xuyên trong chương này và
các chương sau.
Cho f : X → R ∪ {+∞}. Miền hữu hiệu của f là tập
dom f = {x ∈ X | f(x) < +∞}.
Hàm f được gọi là chân chính nếu domf =6 ∅.
Giả sử f : X → R ∪ {+∞} là một hàm lồi chân chính và nửa liên tục dưới (l.s.c.).
Hàm đối ngẫu của f, f
∗
: X∗ → R ∪ {+∞}, được định nghĩa bởi
f
∗
(v) = sup{v(x) ư f(x) | x ∈ dom f}.
Epigraph của f, kí hiệu là epif, là tập
epi f = {(x, r) ∈ X × R | x ∈ dom f, f(x) ≤ r}.
Với ε ≥ 0, ε-dưới vi phân của f tại a ∈ domf được định nghĩa là tập lồi đóng yếu
∗
∂εf(a) := {v ∈ X
0
| f(x) ư f(a) ≥ v(x ư a) ư ε, ∀x ∈ dom f}.
Để ý rằng ∂εf(a) =6 ∅ 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ì ∂0f(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).
22 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
∗ + cl (∪λ∈S+epi(λg)
∗ + epi(δ
∗
C
)),
(iii) (∃(λn)n ⊂ S
+
) (∀x ∈ C)
f(x) + lim inf
n
λng(x) ≥ α.
Dạng tiệm cận này của Bổ đề Farkas đã được sử dụng để thiết lập các định lí về điểm
yên ngựa, các định lí đối ngẫu mạnh cho bài toán tối ưu lồi tổng quát với ràng buộc lồi
theo nón dạng g(x) ∈ ưS, cũng như cho bài toán nửa xác định (SDP).
Định nghĩa 2.1 Hệ x ∈ C, g(x) ∈ ưS được gọi là thỏa mãn điều kiện chính quy dạng
nón đóng (CCCQ) nếu tập hợp
[
λ∈S+
epi(λg)
∗
+ 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) ≥ α.
ã Các mở rộng của Bổ đề Farkas cho hệ lồi vô hạn
Trong mục này chúng ta chủ yếu nghiên cứu hệ (gồm một số vô hạn các bất đẳng thức
lồi và một ràng buộc tập) sau
σ := {ft(x) ≤ 0, t ∈ T; x ∈ C},
trong đó T là một tập chỉ số tùy ý (có thể vô hạn), C ⊂ X là một tập con lồi đóng, X
là một không gian vectơ tôpô lồi địa phương Hausdorff và ft
: X → R ∪ {+∞} với mọi
t ∈ T. Giả sử rằng ft
là các hàm lồi chân chính, nửa liên tục dưới (l.s.c.), mọi t ∈ T.
Gọi
K := cone{
[
t∈T
epif
∗
t } + epiδ
∗
C.
Định nghĩa 2.2 Chúng ta nói rằng hệ σ is Farkas-Minkowski (ngắn gọn FM) nếu tập K
là đóng yếu
∗
.
Liên quan đến hàm f và hệ σ, ta sẽ sử dụng điều kiện sau:
(CC) : The set epif
∗
+ 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) +
X
t∈T
λtft(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.