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

Chia sẻ: Lavie Lavie | Ngày: | Loại File: PDF | Số trang:16

Thêm vào BST

Báo xấu

63
lượt xem 5
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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 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; 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; á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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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

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 Tp. Hồ Chí Minh, 2/2006
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. 1
Chươ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 ∈ Rn . Khi đó các mệnh đề sau là tương đương: (i) aTi x ≥ 0, i = 1, 2, ..., m =⇒ P cT (x) ≥ 0, (ii) (∃λi ≥ 0, i = 1, 2, ..., m) c = m i=1 λi ai . 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ì ∂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 ∗ + cl (∪λ∈S + epi(λg)∗ + epi(δC∗ )) , (iii) (∃(λn )n ⊂ S + ) (∀x ∈ C) f (x) + lim inf λn g(x) ≥ α. n 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 ∗ [ epi(λg)∗ + epi δC∗ là đóng yếu . λ∈S + 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{ epift∗ } + epiδC∗ . t∈T Đị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; (T ) (iii) tồn tại λ ∈ R+ sao cho X f (x) + λt ft (x) ≥ α, ∀x ∈ C. t∈T 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. 4
Định lí 3.1 (Điều kiện tối ưu) [JDL] Xét bài toán (P) và cho a ∈ C ∩ g −1 (−S). Giả sử rằng điều kiện (CCCQ) thỏa mãn. Khi đó a là một nghiệm của (P) nếu và chỉ nếu tồn tại λ ∈ S + sao cho 0 ∈ ∂f (a) + ∂(λg)(a) + NC (a) và λg(a) = 0, trong đó NC (a) là nón pháp tuyến với tập C tại a. Định lí 3.2 (Điều kiện tối ưu theo dãy I) Xét bài toán (P). Giả sử rằng a ∈ C ∩ g −1 (−S). Khi đó các điều kiện sau là tương đương: (i) f (a) = inf{f (x) : x ∈ C, −g(x) ∈ S} (a là ngiệm của (P)), (ii) (∃ u ∈ ∂f (a) )(∃{λn } ⊂ S + )(∃{n },{γn } ⊂ IR+ ) (∃{vn }, {wn } ⊂ X 0 ) sao cho vn ∈ ∂n (λn g)(a), wn ∈ ∂γn δC (a), u + vn + wn →∗ 0, n → 0, γn → 0 và λn g(a) → 0 khi n → ∞. Định lí 3.3 (Minimax Lagrange theo dãy) Đối với Bài toán (P), giả sử rằng tập các điểm ¯ n ) ⊂ S + sao cho chấp nhận được là không rỗng. Khi đó tồn tại một dãy (λ inf sup lim inf L(x, λn ) = sup inf lim inf L(x, λn ) x∈C (λn )⊂S + n→∞ (λn )⊂S + x∈C n→∞ ¯ n ) = inf(P ). = inf lim inf L(x, λ x∈C n→∞ 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 ft (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, ft : 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 | ft (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 (λt )t ∈ Λ+ sao cho X 0 ∈ ∂f (a) + λt ∂ft (a) + NC (a), λt ft (a) = 0, t ∈ T. (1) t∈T Sử dụng Bổ đề Farkas mở rộng chúng ta cũng thiết lập được các định lí đối ngẫu mạnh, các điều kiện điểm yên ngựa cho bài toán (P1). 5
Chương II BỔ ĐỀ FARKAS CHO HỆ BẤT ĐẳNG THỨC GỒM CÁC HÀM LỒI VÀ HÀM DC Giả sử Z là một không gian Banach, X là một không gian Banach phản xạ, f, g : X −→ R ∪ {+∞} là các hàm lsc, lồi, chân chính, và h : X −→ Z là ánh xạ S- lồi liên tục trong đó S là một nón lồi đóng trongZ. Trong suốt bài báo này ta giả sử 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 (−S). Các kết quả chính trong chương này sẽ được nêu lên sau đây. Định lí 1. (Bổ đề Farkas dạng tiệm cận) Cho α ∈ R. Nếu điều kiện (CC1) thoả mãn thì các mệnh đề sau tương đương (i) h(x) ∈ −S, x ∈ C =⇒ f (x) − g(x) ≥ α, (ii) (0, −α) + epi g ∗ ⊂ epi f ∗ + clK, (iii) (∀x∗ ∈ domg ∗ )(∃(λn )n ⊂ S + )(∀x ∈ C) f (x) + lim inf λn h(x) ≥ (x∗ , x) − g ∗ (x∗ ) + α, n→∞ (iv) (∀ > 0) (∀x ∈ C ∩ domg) (∃(λn )n ⊂ S + ) f (x) + lim inf λn h(x) − g(x) ≥ α − . n→∞ Đị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) f (x) + λh(x) ≥ (x∗ , x) − g ∗ (x∗ ) + α. (iv) (∀ > 0) (∀x ∈ C ∩ domg) (∃λ ∈ S + ) f (x) + λh(x) − g(x) ≥ α − . Để ý rằng trong trường hợp g ≡ 0 kết quả trên suy biến thành các kết quả cho cac hệ lồi vừa được thiết lập mới đây (Chương I). 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) thì các mệnh đề sau tương đương (i’) h(x) ∈ −S, x ∈ C =⇒ f (x) ≥ α, (ii’) (0, −α) ∈ epi f ∗ + cl (∪λ∈S + epi (λh)∗ + epi δC∗ ), (iii’) (∃(λn )n ⊂ S + )(∀x ∈ C) f (x) + lim inf λh(x) ≥ α. n→∞ −1 Hệ quả 3. Giả sử C ∩ h (−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∗ , (iii”) (∃λ ∈ S + )(∀x ∈ C) f (x) + λh(x) ≥ α. 7
Tài liệu [1] Nguyễn Định, 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, Tạp chí khoa học Đại học Sư phạm Tp. Hồ Chí Minh - Khoa học tự nhiên, 6(40), 2005, 3 - 25. [2] Nguyễn Định và Trần Thái An Nghĩa, Bổ đề Farkas cho các hệ bất đẳng thức gồm các hàm lồi và hàm DC, Tạp chí khoa học Đại học Sư phạm Tp. Hồ Chí Minh - Khoa học tự nhiên, 6(40), 2005, 41 - 52. [3] N. Dinh, Guy Vallet, and T.T.A. Nghia, A new approach to DC-programs with cone convex constraints (bản thảo, 2005). 8
Chương III BÀI TOÁN QUY HOẠCH DC VỚI RÀNG BUỘC LỒI THEO NÓN 1 Giới thiệu Trong chương này chúng ta sẽ xét bài toán tối ưu cực tiểu hóa một phiếm hàm DC (hiệu của 2 hàm lồi) với ràng buộc lồi theo nón và một ràng buộc tập có dạng sau: (P) inf (f (x) − g(x)) subject to x ∈ C, h(x) ∈ −S trong đó X, Z là các không gian Banach, C là một tập lồi đóng của X, f, g : X → R ∪ {+∞} là các hàm lồi, S là một nón lồi đóng trong Z (không nhất thiết có phần trong khác rỗng), và h : X → Z là một ánh xạ liên tục, S-lồi. Chúng ta quy ước rằng ∞ − ∞ = +∞. Trong suốt chương này chúng ta giả thiết rằng A := {x ∈ X | x ∈ C, h(x) ∈ −S} = C ∩ h−1 (−S) 6= ∅. Lúc này (P) có thể được viết lại là (P0 ): inf f (x) − g(x) x∈A hoặc là (P00 ): inf [(f (x) + δA (x)) − g(x)] x∈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(x0 ) ⊂ ∂(f + δA )(x0 ). 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(x0 ) ⊂ ∂f (x0 ) + NA (x0 ). (1) Bổ đề sau đây đóng một vai trò quan trọng trong toàn bộ các nghiên cứu của chương này. Nó được thiết lập bởi J. B. Hiriart-Urruty (2001). Bổ đề 1.1 x0 ∈ A là một nghiệm tối ưu toàn cục của (P’) nếu và chỉ nếu với mọi ≥ 0, ∂ g(x0 ) ⊂ ∂ (f + δA )(x0 ). (2) 1
2 Điều kiện tối ưu Kết quả chính của chương này là các điều kiện cần và đủ tối ưu cho bài toán (P). Chúng tôi đã chứng minh được các kết quả sau: Định lí 2.1 Giả sử rằng inf(P ) < +∞ và điều kiện (CC2) được thỏa mãn. Khi đó x¯ ∈ A là một nghiệm tối ưu toàn cục của (P) nếu và chỉ nếu với mỗi ≥ 0, với mỗi x∗ ∈ ∂ g(¯ x), tồn tại λ ∈ S + và 1 , 2 , 3 ≥ 0 sao cho 1 + 2 + 3 = + λh(¯ x) và x∗ ∈ ∂1 f (¯ x) + ∂2 (λh)(¯ x) + N3 (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 x∗ ∈ ∂f (¯ x) + ∂(λh)(¯ x) + N (C, x¯), λh(¯ x) = 0. Trường hợp đặc biệt, khi không có mặt ràng buộc x ∈ C, điều kiện tối ưu được cho ở dạng đơn giản sau: Hệ quả 2.1 Gỉa sử rằng C = X và inf(P ) < +∞. Nếu epif ∗ + λ∈S + epi(λh)∗ là đóng S yếu∗ thì x¯ là nghiệm tối ưu toàn cục của (P ) khi và chỉ khi với mỗi ≥ 0, [ [ x) ⊂ ∂ g(¯ {∂1 f (¯ x) + ∂2 (λh)(¯ x)} . (4) λ∈S + 1 +2 =+λh(¯x) 1 ,2 ≥0 Đặc biệt, nếu x¯ là một nghiệm của (P) thì [ x) ⊂ ∂g(¯ {∂f (¯ x) + ∂(λh)(¯ x)}. (5) λ∈S + λh(¯ x)=0 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 f (x) − g(x), x∈C, hi (x)≤0, i∈I, 2
trong đó I là một tập chỉ số tùy ý (có thể vô hạn); hi : X −→ R, i ∈ I, là các hàm lồi, liên tục trong khi f, g : X → R ∪ {+∞} là các hàm lồi chân chính, nửa liên tục dưới như trong các mục trước. Gọi Z = RI là không gian tích được trang bị tôpô tích. Khi đó không gian đối ngẫu tôpô Z ∗ của Z là R(I) , chính là không gian gồm các dãy suy rộng hữu hạn, nghĩa là bao gồm các hàm v : I → R với giá hữu hạn. Đặt S = RI+ . Khi đó nón đối ngẫu (dương) S + (I) của nón S là R+ với (I) R+ := {(λi )i∈I | λi ≥ 0, i ∈ I, λi = 0 voi moi i tru mot so huu han i ∈ I} Gọi A := {x ∈ C, hi (x) ≤ 0, ∀i ∈ I}. Kí hiệu h := (hi ). 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 epihi ∗ + epiδC∗ là S 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 (I) (I) mọi ≥ 0, với mọi x∗ ∈ ∂ g(¯x), tồn tại (λi ) ∈ R+ , (i ) ∈ R+ , α, β ≥ 0 sao cho X X α+β+ i = + λi hi (¯ x), i∈I i∈I X ∗ x ∈ ∂α f (¯ x) + ∂i (λi hi )(¯ x) + Nβ (C, x¯). i∈I Đặ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) (λi ) ∈ R+ sao cho X x∗ ∈ ∂f (¯ x) + λi ∂hi (¯ x) + NC (¯ x), λi hi (¯ x) = 0. (6) i∈I 3.2 Bài toán (P) với g là hàm đa diện Chúng ta sẽ xét trường hợp đặc biệt của Bài toán (P) khi C = X và g là hàm có dạng g(x) = max{(a∗i , x) + bi }, ∀x ∈ X (7) i∈I trong đó I = {1, 2, . . . , n}, a∗1 , a∗2 , . . . , a∗n ∈ X ∗ . Hàm g như thế được gọi là một hàm lồi đa diện. Ta có ( !) [ epig ∗ = cl co ({a∗i } × [−bi , +∞)) . i∈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 S hàm lồi đa diện xác định bởi (7). Giả sử thêm nữa rằng {h(x) ∈ −S} = 6 ∅ và epif ∗ + λ∈S + epi(λh)∗ là đóng yếu∗ . Nếu inf(P ) < +∞ thì x¯ là một nghiệm toàn cục của (P) khi và chỉ khi với mỗi i ∈ I, tồn tại λi ∈ S + sao cho [ a∗i ∈ {∂1 f (¯ x) + ∂2 (λi h)(¯ x)} , (8) 1 +2 =αi 1 ,2 ≥0 trong đó αi := λi h(¯ x) − gi (¯ x) + g(¯ 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 p(x) x∈C, h(x)∈−S 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 −p(x). x∈C, h(x)∈−S Để ý rằng sup(P M ) = −inf(P M 1). Đ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)∗ + epiδC∗ là đóng yếu∗ . TKhi đó x¯ là nghiệm tối ưu toàn cục của (PM) nếu và chỉ nếu với mỗi ≥ 0, mỗi x∗ ∈ ∂ p(¯ x), tồn tại λ ∈ S + và 1 , 2 ≥ 0 thỏa mãn 1 + 2 = + λh(¯ x) và x∗ ∈ ∂1 (λh)(¯ x) + N2 (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 triể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. Boberna, 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 [1] Nguyễn Định, 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, Tạp chí khoa học Đại học Sư phạm Tp. Hồ Chí Minh - Khoa học tự nhiên, 6(40), 2005, 3 - 25. [2] Nguyễn Định và Trần Thái An Nghĩa, Bổ đề Farkas cho các hệ bất đẳng thức gồm các hàm lồi và hàm DC, Tạp chí khoa học Đại học Sư phạm Tp. Hồ Chí Minh - Khoa học tự nhiên, 6(40), 2005, 41 - 52. [3] N. Dinh, Guy Vallet, and T.T.A. Nghia, A new approach to DC-programs with cone convex constraints (bản thảo, 2006). Tp. Hồ Chí Minh, ngày 26 thàng 2, năm 2006 Chủ nhiệm đề tài CS.2005.23.77 5
PGS.TS. Nguyễn Định 6
PHẦN PHỤ LỤC CÁC CÔNG TRÌNH Thực hiện trong khuôn khổ của đề tài: CS.2005.23.77 [1 ] Nguyễn Định, 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, Tạp chí khoa học Đại học Sư phạm Tp. Hồ Chí Minh - Khoa học tự nhiên, 6(40), 2005, 3 - 25. [2 ] Nguyễn Định và Trần Thái An Nghĩa, Bổ đề Farkas cho các hệ bất đẳng thức gồm các hàm lồi và hàm DC, Tạp chí khoa học Đại học Sư phạm Tp. Hồ Chí Minh - Khoa học tự nhiên, 6(40), 2005, 41 - 52. [3 ] N. Dinh, Guy Vallet, and T.T.A. Nghia, A new approach to DC-programs with cone convex constraints (bản thảo, 2006). 1