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 đflng thøc lçi và các b§t đflng 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) aTx ≥ 0, i = 1,2,...,m =⇒ cT(x) ≥ 0, (ii) (∃λi ≥ 0,i = 1,2,...,m) c = 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ó, chflng 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 = ∅. 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 ∈ X0 | f(x)−f(a) ≥ v(x−a)−ε, ∀x ∈ dom f}. Đ” ý r‹ng ∂ε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ì ∂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). 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(δ∗ )), (iii) (∃(λn)n ⊂ S+ ) (∀x ∈ C) f(x)+liminf λ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 [ epi(λg)∗ +epi δ∗ 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 δ∗ , (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 đflng 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; (iii) tçn t⁄i λ ∈ R(T) sao cho X f(x)+ λtft(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 ... - tailieumienphi.vn