Đăng ký Đăng nhập
Trang chủ Giáo dục - Đào tạo Cao đẳng - Đại học Luận văn điều kiện cần và đủ cho nghiệm hữu hiệu của bài toán tối ưu đa mục tiêu...

Tài liệu Luận văn điều kiện cần và đủ cho nghiệm hữu hiệu của bài toán tối ưu đa mục tiêu qua dưới vi phân suy rộng

.PDF
37
127
76

Mô tả:

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC SƯ PHẠM TRẦN THỊ NHÀN ĐIỀU KIỆN CẦN VÀ ĐỦ CHO NGHIỆM HỮU HIỆU CỦA BÀI TOÁN TỐI ƯU ĐA MỤC TIÊU QUA DƯỚI VI PHÂN SUY RỘNG LUẬN VĂN THẠC SĨ TOÁN HỌC Thái Nguyên - Năm 2015 i Lêi cam ®oan T«i xin cam ®oan r»ng c¸c kÕt qu¶ nghiªn cøu trong luËn v¨n nµy lµ trung thùc vµ kh«ng trïng lÆp víi c¸c ®Ò tµi kh¸c. T«i còng xin cam ®oan r»ng mäi sù gióp ®ì cho viÖc thùc hiÖn luËn v¨n nµy ®· ®­îc c¶m ¬n vµ c¸c th«ng tin trÝch dÉn trong luËn v¨n ®· ®­îc chØ râ nguån gèc. Th¸i Nguyªn, th¸ng 4 n¨m 2015 Ng­êi viÕt luËn v¨n TrÇn ThÞ Nhµn ii Lêi c¶m ¬n LuËn v¨n ®­îc thùc hiÖn vµ hoµn thµnh t¹i tr­êng §¹i häc s­ ph¹m - §¹i häc Th¸i Nguyªn d­íi sù h­íng dÉn khoa häc cña PGS. TS. §ç V¨n L­u. Qua ®©y, t¸c gi¶ xin ®­îc göi lêi c¶m ¬n s©u s¾c ®Õn thÇy gi¸o, ng­êi h­íng dÉn khoa häc cña m×nh, PGS. TS. §ç V¨n L­u, ng­êi ®· tËn t×nh h­íng dÉn trong suèt qu¸ tr×nh nghiªn cøu cña t¸c gi¶. §ång thêi t¸c gi¶ còng ch©n thµnh c¶m ¬n c¸c thÇy c« trong khoa To¸n, khoa Sau ®¹i häc - Tr­êng §¹i häc s­ ph¹m, §¹i häc Th¸i Nguyªn, ®· t¹o mäi ®iÒu kiÖn ®Ó t¸c gi¶ hoµn thµnh b¶n luËn v¨n nµy. T¸c gi¶ còng göi lêi c¶m ¬n ®Õn gia ®×nh vµ c¸c b¹n trong líp Cao häc To¸n K21b, ®· ®éng viªn gióp ®ì t¸c gi¶ trong qu¸ tr×nh häc tËp vµ lµm luËn v¨n. LuËn v¨n kh«ng thÓ tr¸nh khái nh÷ng thiÕu sãt, t¸c gi¶ rÊt mong nhËn ®­îc sù chØ b¶o tËn t×nh cña c¸c thÇy c« vµ b¹n bÌ ®ång nghiÖp. Th¸i Nguyªn, th¸ng 4 n¨m 2015 Ng­êi viÕt luËn v¨n TrÇn ThÞ Nhµn iii Môc lôc Lêi cam ®oan i Lêi c¶m ¬n ii Môc lôc iii Më ®Çu 1 1 3 §iÒu kiÖn cÇn Fritz John cho cùc tiÓu yÕu 1.1 C¸c kiÕn thøc bæ trî 2 . . . . . . . . . . . . . . . . . . . . . . . 3 . . . . . . . . . . . . . . . . . . . . 3 1.1.1. D­íi vi ph©n suy réng 1.1.2. C¸c d­íi vi ph©n Clarke-Rockafellar, Clarke, Michel-Penot 1.1.3. D­íi vi ph©n suy réng chÝnh quy, d­íi vi ph©n suy réng tèi thiÓu 1.2 . . . . . . . . . . . . . . . . . . . . . §iÒu kiÖn cÇn Fritz John cho cùc tiÓu Pareto yÕu 7 . . . . . . . . . 10 . . . . . . . . . 13 §iÒu kiÖn chÝnh quy vµ ®iÒu kiÖn tèi ­u Karush-Kuhn-Tucker 24 2.1 §iÒu kiÖn chÝnh quy vµ ®iÒu kiÖn cÇn Karush-Kuhn-Tucker . . . . 24 2.2 §iÒu kiÖn ®ñ cho cùc tiÓu Pareto yÕu . KÕt luËn . . . . . . Tµi liÖu tham kh¶o . . . . . . . . . . . . . . . 28 . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 1 Më ®Çu 1. Lý do chän luËn v¨n N¨m 1994, Demyanov [5] ®· ®­a ra kh¸i niÖm d­íi vi ph©n suy réng comp¨c låi. Kh¸i niÖm nµy lµ mét tæng qu¸t ho¸ cña kh¸i niÖm låi trªn vµ lâm d­íi (xem [6]). C¸c kh¸i niÖm d­íi vi ph©n suy réng ®ãng, kh«ng låi vµ Jacobian xÊp xØ ®­îc ®Ò xuÊt bëi Jeyakumar vµ Luc trong [9] vµ [10]. Kh¸i niÖm d­íi vi ph©n suy réng lµ tæng qu¸t ho¸ cña mét sè c¸c kh¸i niÖm d­íi vi ph©n ®· biÕt cña Clarke [4], Michel-Penot [17], Mordukhovich [18]. Mét ®iÒu kiÖn cÇn Fritz John cho cùc tiÓu yÕu cña bµi to¸n quy ho¹ch ®a môc tiªu d­íi ng«n ng÷ Jacobian xÊp xØ ®­îc ®­a ra bëi Luc [12]. §iÒu kiÖn cÇn tèi ­u Fritz John cho cùc tiÓu yÕu d­íi ng«n ng÷ d­íi vi ph©n suy réng ®­îc ®­a ra bëi Dutta- Chandra [7,8] cho bµi to¸n tèi ­u ®a môc tiªu víi c¸c rµng buéc bÊt ®¼ng thøc. §iÒu kiÖn cÇn cho cùc tiÓu yÕu vµ cùc tiÓu Pareto ®­îc ®­a ra bëi Luu [15] víi c¸c rµng buéc ®¼ng thøc, bÊt ®¼ng thøc vµ rµng buéc tËp. Dùa (2014) trªn ®· ®Þnh thiÕt lÝ lËp Ljusternik c¸c ®iÒu më kiÖn réng tèi ­u cña cho JimÐnez-Novo cùc tiÓu Pareto (2002), yÕu cña D.V.Luu bµi to¸n tèi ­u ®a môc tiªu cã rµng buéc ®¼ng thøc, bÊt ®¼ng thøc vµ rµng buéc tËp d­íi ng«n ng÷ d­íi vi ph©n suy réng (convexificator). §©y lµ ®Ò tµi ®ang ®­îc nhiÒu t¸c gi¶ trong vµ ngoµi n­íc quan t©m nghiªn cøu. ChÝnh v× thÕ em chän ®Ò tµi : “§iÒu kiÖn cÇn vµ ®ñ cho nghiÖm h÷u hiÖu cña bµi to¸n tèi ­u ®a môc tiªu qua d­íi vi ph©n suy réng”. 2. Ph­¬ng ph¸p nghiªn cøu 2 S­u tÇm vµ ®äc tµi liÖu tõ c¸c s¸ch, t¹p chÝ to¸n häc trong n­íc vµ quèc tÕ liªn quan ®Õn ®iÒu kiÖn tèi ­u cho bµi to¸n tèi ­u vÐc t¬. Qua ®ã, t×m hiÓu vµ nghiªn cøu vÒ vÊn ®Ò nµy. 3. Môc ®Ých cña luËn v¨n LuËn v¨n tr×nh bµy c¸c ®iÒu kiÖn cÇn vµ ®ñ cho nghiÖm h÷u hiÖu d­íi ng«n ng÷ d­íi vi ph©n suy réng trong bµi b¸o cña D. V. L­u ®¨ng trong t¹p chÝ Journal of Optimization Theory and Applications, Vol. 160 (2014), pp. 510-526. 4. Néi dung cña luËn v¨n LuËn v¨n bao gåm phÇn më ®Çu, 2 ch­¬ng, kÕt luËn vµ danh môc c¸c tµi liÖu tham kh¶o Ch­¬ng 1: §iÒu kiÖn cÇn Fritz John cho cùc tiÓu yÕu Tr×nh bµy mét sè kiÕn thøc c¬ b¶n vÒ d­íi vi ph©n suy réng vµ ®iÒu kiÖn cÇn Fritz John cho cùc tiÓu Pareto yÕu cña bµi to¸n tèi ­u ®a môc tiªu cã rµng buéc ®¼ng thøc, bÊt ®¼ng thøc vµ rµng buéc tËp víi c¸c hµm Lipschitz ®Þa ph­¬ng. Ch­¬ng 2: §iÒu kiÖn chÝnh quy vµ ®iÒu kiÖn tèi ­u Karush-Kuhn-Tucker Tr×nh bµy c¸c ®iÒu kiÖn chÝnh quy vµ ®iÒu kiÖn cÇn Karush-Kuhn-Tucker cho bµi to¸n tèi ­u ®a môc tiªu cã rµng buéc ®¼ng thøc, bÊt ®¼ng thøc vµ rµng buéc tËp víi c¸c hµm Lipschitz ®Þa ph­¬ng d­íi ng«n ng÷ d­íi vi ph©n suy réng víi c¸c gi¶ thiÕt vÒ tÝnh låi suy réng, c¸c ®iÒu kiÖn cÇn tèi ­u trë thµnh c¸c ®iÒu kiÖn ®ñ tèi ­u. 3 Ch­¬ng 1 §iÒu kiÖn cÇn Fritz John cho cùc tiÓu yÕu Trong ch­¬ng 1 chóng t«i tr×nh bµy mét sè kiÕn thøc c¬ b¶n vÒ d­íi vi ph©n suy réng vµ ®iÒu kiÖn cÇn Fritz John cho cùc tiÓu Pareto yÕu cña bµi to¸n tèi ­u ®a môc tiªu cã rµng buéc ®¼ng thøc, bÊt ®¼ng thøc vµ rµng buéc tËp d­íi ng«n ng÷ d­íi vi ph©n suy réng. C¸c kÕt qu¶ tr×nh bµy trong ch­¬ng nµy ®­îc tham kh¶o trong [9], [14]. 1.1 C¸c kiÕn thøc bæ trî 1.1.1. Cho D­íi vi ph©n suy réng f lµ hµm gi¸ trÞ thùc më réng ®­îc x¸c ®Þnh trªn hµm theo ph­¬ng Dini d­íi vµ trªn v ∈ Rn f− vµ f+ f cña t¹i Rn . Nh¾c l¹i r»ng ®¹o x̄ ∈ Rn theo ph­¬ng ®­îc x¸c ®Þnh nh­ sau: f (x + tv) − f (x̄) , t↓0 t   f (x̄ + tv) − f (x̄) + f (x̄; v) := lim sup . t↓0 t f − (x̄; v) := lim inf NÕu f t¹i t¹i x̄ x̄ f + (x̄; v) = f − (x̄; v) , th× gi¸ trÞ chung ®ã ®­îc gäi lµ ®¹o hµm cña hµm theo ph­¬ng v vµ ký hiÖu lµ f 0 (x̄; v) . Hµm nÕu tån t¹i ®¹o hµm theo ph­¬ng cña nã t¹i kh¶ vi FrÐchet t¹i x̄ víi ®¹o hµm FrÐchet ∇f (x̄) f x̄ th× gäi lµ kh¶ vi theo ph­¬ng theo mäi ph­¬ng. NÕu f f 0 (x̄; v) = h∇f (x̄, v)i . lµ 4 f Theo [9] hµm ∂∗ f (x̄) ) t¹i ®­îc gäi lµ cã d­íi vi ph©n suy réng trªn x̄ ∈ Rn nÕu ∂ ∗ f (x̄) (hay (∂∗ f (x̄)) ⊆ Rn f − (x̄; v) ≤ sup hξ, vi f + (x̄; v) ≥ ξ∈∂∗ f (x̄) Mét tËp ®ãng nÕu ∂ ∗ f (x̄) Theo ∂ ∗ f (x̄) ⊆ Rn ) lµ tËp ®ãng vµ  (∀v ∈ Rn ) . hξ, vi inf ®­îc gäi lµ mét d­íi vi ph©n suy réng cña ®ång thêi lµ d­íi vi ph©n suy réng trªn vµ d­íi cña [8] hµm ∂ ∗ f (x̄) ⊆ Rn t¹i f x̄ ®­îc nÕu (hay d­íi (∀v ∈ Rn ), ξ∈∂ ∗ f (x̄)  ∂ ∗ f (x̄) gäi lµ ∂ ∗ f (x̄) cã d­íi vi ph©n suy réng b¸n f t¹i x̄ chÝnh f t¹i x̄ . quy trªn lµ tËp ®ãng vµ f + (x̄; v) ≤ sup hξ, vi (∀v ∈ Rn ). ξ∈∂ ∗ f (x̄) (1.1) VÝ dô 1.1.1 Cho hµm f :R→R     x, f (x) := x4 − 4x3 + 4x2 ,    0, ®­îc x¸c ®Þnh bëi khi x ∈ Q ∩ [0; +∞[, x ∈ Q ∩ ]−∞; 0], khi , trong c¸c tr­êng hîp kh¸c trong ®ã Q lµ tËp c¸c sè h÷u tû. Khi ®ã   v, + f (0; v) =  0, khi v ≥ 0, khi v < 0, f − (0; v) = 0 (∀v ∈ R). TËp {0; 1} lµ d­íi vi ph©n suy réng b¸n chÝnh quy trªn cña nã còng lµ d­íi vi ph©n suy réng trªn cña réng d­íi cña Theo [9], f t¹i nÕu f t¹i x̄ . TËp {0} f t¹i x̄ , cho nªn lµ d­íi vi ph©n suy x̄ . x¶y ra ®¼ng thøc trong (1.1) th× ∂ ∗ f (x̄) ®­îc gäi lµ d­íi vi ph©n suy réng chÝnh quy trªn. Víi mét hµm Lipschitz ®Þa ph­¬ng, d­íi vi ph©n 5 Clarke vµ d­íi vi ph©n Michel-Penot lµ nh÷ng d­íi vi ph©n suy réng cña x̄ (xem [9]). f t¹i H¬n n÷a víi mét hµm Lipschitz ®Þa ph­¬ng chÝnh quy trong theo nghÜa Clarke [4], d­íi vi ph©n Clarke lµ mét d­íi vi ph©n suy réng chÝnh quy f trªn (xem [7]). Chó ý r»ng, nÕu hµm trªn t¹i x̄ cã mét d­íi vi ph©n suy réng chÝnh quy th× nã còng lµ d­íi vi ph©n suy réng b¸n chÝnh quy trªn t¹i x̄ ®ã nã ®­îc lµ d­íi vi ph©n suy réng trªn t¹i x̄ , vµ do . VÝ dô 1.1.2 Ta xÐt hµm f :R→R ®­îc x¸c ®Þnh bëi:   x2 cos π , x f (x) =  0, Ta cã f t¹i x̄ = 0 t­¬ng øng lµ x = 0. f t¹i f x̄ ∈ Q theo tÝnh t¹i x̄ ∈ Q theo Q Q nÕu t¹i {0} ph©n Clarke . C¸c tËp x̄ . TËp {0} vµ Michile- {0} [−π; π] , vµ lµ d­íi vi ph©n suy . Q nÕu víi mçi f (x) ≤ f (x̄) ⇒ ∀t ∈ ]0, 1[ , ®­îc gäi lµ tùa låi trªn vµ vi x̄ Theo [16] mét hµm gi¸ trÞ thùc më réng gäi lµ tùa låi t¹i D­íi [−π; π] lµ c¸c d­íi vi ph©n suy réng cña réng chÝnh quy trªn cña nÕu ±f f x¸c ®Þnh trªn tËp x∈Q Q f Q ⊆ Rn ®­îc , f (tx + (1 − t)x̄) ≤ f (x̄). lµ tùa låi t¹i suy réng d­íi låi trªn mét tËp låi f lµ tùa låi t¹i mçi Trong [20] Yang chØ ra r»ng, nÕu x̄ theo Q x∈Q f . gäi lµ tùa tuyÕn . lµ liªn tôc, tùa låi vµ cã mét d­íi vi ph©n th× víi mçi f (x) ≤ f (y) ⇒ ∃ξ (n) ∈ ∂∗ f (y), f khi . {−π; π} NÕu x 6= 0, f + (0; v) = f − (0; v) = 0, (∀v ∈ R) Penot cña f khi x, y ∈ Q , lim (ξ (n) , x − y) ≤ 0. n→∞ cã mét d­íi vi ph©n suy réng chÝnh quy trªn t¹i x̄ th× ta cã mÖnh ®Ò sau ®©y. MÖnh ®Ò 1.1.1 Gi¶ sö f cã mét d­íi vi ph©n suy réng chÝnh quy trªn ∂ ∗ f (x̄) t¹i x̄ vµ f tùa låi 6 t¹i x̄ ∈ Q theo tËp låi Q. Khi ®ã, ∀x ∈ Q, f (x) ≤ f (x̄) ⇒ ∀ξ ∈ ∂ ∗ f (x̄), hξ, x − x̄i ≤ 0. Chøng minh V× f x̄ lµ tùa låi t¹i theo Q , víi mçi x∈Q tháa m·n f (x) ≤ f (x̄) , ta cã f + (x̄; x − x̄) ≤ 0. Do tÝnh chÝnh quy trªn cña d­íi vi ph©n suy réng m·n ∂ ∗ f (x̄) , víi mçi x∈Q tháa f (x) ≤ f (x̄) , ta cã sup hξ, x − x̄i = f + (x̄; x − x̄) ≤ 0. ξ∈∂ ∗ f (x̄) 2 Tõ ®ã, ta cã ®iÒu ph¶i chøng minh. Theo [20], hµm thùc më réng trªn Q f cã mét d­íi vi ph©n suy réng d­íi låi Q x, y ∈ Q D E (n) lim ξ , y − x ≥ 0 ⇒ f (y) ≥ f (x). ®­îc gäi lµ gi¶ låi tiÖm cËn d­íi trªn ∃ξ (n) ∈ ∂∗ f (x), Hµm gi¸ trÞ thùc më réng lµ gi¶ låi tiÖm cËn t¹i x̄ f nÕu víi mçi , n→∞ cã mét d­íi vi ph©n suy réng theo ∃ξ (n) ∈ conv∂ ∗ f (x̄), Q ∂ ∗ f (x̄) t¹i x̄ ®­îc gäi x∈Q D E lim ξ (n) , x − x̄ ≥ 0 ⇒ f (x) ≥ f (x̄). nÕu, víi mçi ta cã n→∞ trong ®ã conv kÝ hiÖu bao låi VÝ dô 1.1.3 Cho ∂∗ f (x) f, g : R → R   x, khi x ≤ 0, f (x) :=  1 x, khi x > 0, 2   khi x ∈ Q,   x, g(x) := 2x, khi x ∈ (R\Q) ∩ ]−∞, 0] ,    1 khi x ∈ (R\Q) ∩ [0, ∞[ . 2 x, 7 Khi ®ã mét d­íi vi ph©n suy réng cña låi tiÖm cËn t¹i 0 theo 1 ∂∗ g(0) = 2 ; 2 Cho K vµ g Q=R . f t¹i 0 lµ ∂ ∗ f (0) = 1 ; 1 2 vµ Mét d­íi vi ph©n suy réng d­íi cña lµ gi¶ låi tiÖm cËn d­íi t¹i 0 theo lµ mét nãn låi ®ãng trong Rn f g lµ gi¶ t¹i 0 lµ Q=R . vµ K ∗ := {ξ ∈ Rn : hξ, xi ≥ 0, ∀x ∈ K} lµ nãn cùc kh«ng ©m . Gi¶ sö fk (f1 , ..., fm ) gäi lµ gi¶ låi λT f K K cña . Cho f : Q ⊆ Rn → Rm cã mét d­íi vi ph©n suy réng - tiÖm cËn v« h­íng t¹i lµ gi¶ låi tiÖm cËn t¹i x̄ trªn Q x̄ theo vµ ∂ ∗ fk (x̄) Q t¹i nh­ x̄ vËy f = f ®­îc . Hµm λ ∈ K∗ nÕu víi mçi , hµm . C¸c nãn tiÕp tuyÕn Bouligand vµ Clarke cña tËp C ⊆ Rn t¹i mét ®iÓm x̄ ∈ C ®­îc ®Þnh nghÜa t­¬ng øng bëi K(C, x̄) := {v ∈ Rn : ∃ vn → v, ∃ tn ↓ 0 sao cho x̄ + tn vn ∈ C, ∀n} , T (C, x̄) := {v ∈ Rn : ∀ xn ∈ C, xn → x̄, ∀ tn ↓ 0 , ∃ vn → v sao cho Nãn c¸c ph­¬ng ®¹t ®­îc cña A(C, x̄) = n C t¹i x̄ ∈ C xn + tn vn ∈ C, ∀n} . lµ: v ∈ Rn : ∃δ > 0, ∃γ : [0, δ] → Rn γ(0) = x̄, γ(t) ∈ C, ∀t ∈ ]0, δ] , γ , (0) = Nãn ph¸p tuyÕn Clarke cña C t¹i x̄ sao cho lim γ(t)−γ(0) t t↓0  =v . lµ N (C, x̄) = {ξ ∈ Rn : hξ, vi ≤ 0 ∀ v ∈ T (C, x̄)} . Chó ý r»ng c¸c nãn −T ∗ (C, x̄) vµ T (C, x̄) vµ N (C, x̄) T (C, x̄) ⊆ K(C, x̄) . lµ kh«ng rçng, ®ãng vµ låi; Trong tr­êng hîp C låi th× N (C, x̄) = T (C, x̄) = K(C, x̄) . 1.1.2. C¸c d­íi vi ph©n Clarke-Rockafellar, Clarke, Michel-Penot Sau ®©y ta sÏ thÊy r»ng c¸c d­íi vi ph©n Clarke-Rockafellar, Clarke, Michel- Penot,...®Òu lµ d­íi vi ph©n suy réng. 8 f : Rn → R̄ Cho hµm x d­íi t¹i lµ h÷u h¹n t¹i ®iÓm x∈X . f NÕu th× d­íi ®¹o hµm trªn Clarke - Rockafellar cña f t¹i lµ nöa liªn tôc x theo v ®­îc x¸c ®Þnh bëi: f ↑ (x, v) = lim sup inf [f (x0 + tv 0 ) − f (x0 )] /t, 0 x0 →f x v →v t↓0 trong ®ã NÕu f t¹i x f x0 → f x nghÜa lµ x0 → x lµ nöa liªn tôc trªn t¹i theo v x vµ f (x0 ) → f (x) . th× d­íi ®¹o hµm d­íi Clarke-Rockafellar cña ®­îc x¸c ®Þnh bëi f ↓ (x, v) = lim inf sup [f (x0 + tv 0 ) − f (x0 )] /t. 0 x → f x v 0 →v t↓0 NÕu f lµ liªn tôc t¹i x th× x0 → f x trong c¸c ®Þnh nghÜa trªn trë thµnh D­íi gradient suy réng trªn vµ d­íi cña f t¹i x x0 → x . ®­îc cho bëi  ∂ ↑ f (x) = x∗ ∈ X ∗ : hx∗ , vi ≤ f ↑ (x, v) , ∀v ∈ X ,  ∂ ↓ f (x) = x∗ ∈ X ∗ : hx∗ , vi ≥ f ↓ (x, v) , ∀v ∈ X . NÕu mçi f ↑ (x, 0) > −∞ th× ∂ ↑ f (x) lµ tËp con kh«ng rçng, låi, ®ãng cña Rn vµ víi v ∈ Rn , f ↑ (x, v) = sup hx∗ , vi . x∗ ∈ ∂ ↑ f (x) T­¬ng tù, nÕu f ↓ (x, 0) < ∞ Rn v ∈ Rn , vµ víi mçi th× ∂ ↓ f (x) f ↓ (x, v) = NÕu f lµ Lipschitz ®Þa ph­¬ng t¹i x lµ tËp con kh«ng rçng, låi, ®ãng cña inf↓ x∗ ∈ ∂ f (x) hx∗ , vi . th× f ↑ (x; v) = f o (x, v) , f ↓ (x; v) = fo (x, v) , trong ®ã, f o (x, v) = lim sup [f (x0 + tv) − f (x0 )] /t, x0 → x t↓0 fo (x, v) = lim inf [f (x0 + tv) − f (x0 )] /t. 0 x →x t↓0 9 f lµ c¸c ®¹o hµm theo ph­¬ng suy réng trªn vµ d­íi Clarke cña v t¹i x theo ph­¬ng . D­íi vi ph©n suy réng Clarke ®­îc x¸c ®Þnh bëi ∂ o f (x) = {x∗ ∈ X ∗ : hx∗ , vi ≤ f o (x, v) , ∀v ∈ X} . H¬n n÷a, f o (x, v) = f Do ®ã, nÕu cña f t¹i x ∗ max hx , vi , ∗ o x ∈ ∂ f (x) lµ Lipschitz ®Þa ph­¬ng t¹i x th× min ∗ o x ∈ ∂ f (x) ∂ o f (x) hx∗ , vi . lµ d­íi vi ph©n suy réng , bëi v× f − (x, v) ≤ f o (x, v) , víi mçi fo (x, v) = v∈X T­¬ng tù, nÕu f + (x, v) ≥ fo (x, v) . . f lµ Lipschitz ®Þa ph­¬ng t¹i d­íi Michel – Penot cña f t¹i x x th× ®¹o hµm theo ph­¬ng trªn vµ t­¬ng øng ®­îc cho bëi f ♦ (x, v) = sup lim sup λ−1 [f (x + λz + λv) − f (x + λz)] , z∈X λ↓0 f♦ (x, v) = inf lim inf λ−1 [f (x + λz + λv) − f (x + λz)] . z∈X λ↓0 Khi ®ã d­íi vi ph©n Michel – Penot ®­îc x¸c ®Þnh bëi  ∂ ♦ f (x) := x∗ ∈ Rn : f ♦ (x, v) ≥ hx∗ , vi , ∀v ∈ Rn . §¹o hµm theo ph­¬ng trªn vµ d­íi Michel – Penot tuyÕn tÝnh, h÷u h¹n, f ♦ (x, v) = Do ®ã, ∂ ♦ f (x) ∂ ♦ f (x) max hx∗ , vi , f♦ (x, v) = f + (x, v) ≥ f♦ (x, v) VÝ dô 1.1.4 f : R2 → R f♦ (x, .) x¸c ®Þnh bëi f (x, y) = |x| − |y| . hx∗ , vi . min x∗ ∈ ∂ ♦ f (x) còng lµ mét d­íi vi ph©n suy réng cña vµ vµ lµ compact låi x∗ ∈ ∂ ♦ f (x) f − (x, v) ≤ f ♦ (x, v) §Þnh nghÜa f ♦ (x, .) f t¹i víi mçi x , bëi v× v ∈ Rn . lµ d­íi 10 Khi ®ã ∂ ∗ f (0) = {(1, −1) , (−1, 1)} . lµ mét d­íi vi ph©n suy réng cña f t¹i 0. Ta cã ∂ ♦ f (0) = ∂ o f (0) = co ({(1, 1) , (−1, 1) , (1, −1) , (−1, −1)}) . Chó ý r»ng co (∂ ∗ f (0)) ⊆ ∂ ♦ f (0) = ∂ o f (0) . 1.1.3. D­íi vi ph©n suy réng chÝnh quy, d­íi vi ph©n suy réng tèi thiÓu Râ rµng tõ ®Þnh nghÜa ta thÊy d­íi vi ph©n suy réng trªn vµ d­íi kh«ng duy nhÊt. V× vËy trong phÇn nµy chóng ta sÏ tr×nh bµy c¸c ®iÒu kiÖn vÒ tÝnh duy nhÊt vµ tèi thiÓu cña d­íi vi ph©n suy réng trªn hoÆc d­íi. Tr­íc tiªn ta tr×nh bµy kh¸i niÖm d­íi vi ph©n suy réng chÝnh quy trªn vµ d­íi. Hµm f : Rn → R ∂ ∗ f (x) ⊆ Rn t¹i x ®­îc gäi lµ cã mét d­íi vi ph©n suy réng chÝnh quy trªn nÕu ∂ ∗ f (x) lµ tËp ®ãng vµ víi mçi f + (x, v) = v ∈ Rn , hx∗ , vi . sup x∗ ∈∂ ∗ f (x) T­¬ng tù, hµm ∂∗ f (x) ⊆ Rn f t¹i ®­îc x nÕu gäi lµ cã ∂∗ f (x) mét vi ph©n suy lµ tËp ®ãng vµ víi mçi f − (x, v) = Râ rµng, d­íi inf x∗ ∈∂∗ f (x) réng chÝnh f t¹i x d­íi v ∈ Rn . hx∗ , vi . mçi d­íi vi ph©n suy réng chÝnh quy trªn (d­íi) cña d­íi vi ph©n suy réng cña quy f t¹i x lµ mét . Trong mÖnh ®Ò sau chóng ta sÏ tr×nh bµy mèi liªn hÖ gi÷a tÝnh kh¶ vi vµ tÝnh chÝnh quy. MÖnh ®Ò 1.1.2 Hµm f : Rn → R ph­¬ng t¹i x0 vµ f lµ kh¶ vi G©teaux t¹i x0 nÕu vµ chØ nÕu f lµ kh¶ vi theo cã mét d­íi vi ph©n suy réng chÝnh quy trªn vµ chÝnh quy 11 d­íi t¹i x0 . Chøng minh NÕu f lµ kh¶ vi G©teaux t¹i {f 0 (x0 )} x0 th× nã kh¶ vi theo ph­¬ng vµ ®¹o hµm G©teaux f vµ lµ mét d­íi vi ph©n suy réng chÝnh quy trªn vµ d­íi cña Ng­îc l¹i, nÕu f kh¶ vi theo ph­¬ng t¹i x0 vµ nÕu v ∈ Rn suy réng chÝnh quy trªn vµ d­íi th× víi mçi f 0 (x0 , v) = f − (x0 , v) = = f + (x0 , v) = ∂ ∗ f (x0 ) t¹i x0 . lµ mét d­íi vi ph©n . inf ∗ x∗ ∈∂ f (x) hx∗ , vi hx∗ , vi . sup x∗ ∈∂ ∗ f (x) Do ®ã ∂ ∗ f (x0 ) Ta nãi r»ng lµ tËp mét ph©n tö vµ v× vËy ∂ ∗ f (x) vµ kh¶ vi G©teaux t¹i C (x) C (x) trong Rn sao cho lµ 2 . f t¹i x C (x) ⊂ ∂ ∗ f (x) , lµ mét d­íi vi ph©n suy réng (trªn/d­íi) cña Ký hiÖu tËp c¸c ®iÓm cùc biªn cña d­íi vi ph©n suy réng x x0 lµ d­íi vi ph©n suy réng tèi thiÓu (trªn/d­íi) cña nÕu kh«ng tån t¹i mét tËp ®ãng C (x) 6= ∂ ∗ f (x) f ∂ ∗ f (x) f cña t¹i x f t¹i . Ext (∂ ∗ f (x)) . MÖnh ®Ò 1.1.3 Gi¶ sö r»ng (d­íi) f : Rn → R cã mét d­íi vi ph©n suy réng chÝnh quy comp¨c trªn ∂ ∗ f (x) t¹i x. Khi ®ã Ext (co (∂ ∗ f (x))) lµ d­íi vi ph©n suy réng chÝnh quy trªn (d­íi) tèi thiÓu duy nhÊt cña f t¹i x. Chøng minh Cho A ⊂ Rn víi mçi cã mét d­íi vi ph©n suy réng chÝnh quy trªn cña v ∈ Rn , f + (x, v) = sup hx∗ , vi = sup hx∗ , vi . x∗ ∈A x∗ ∈∂ ∗ f (x) Nªn A lµ tËp con ®ãng vµ bÞ chÆn cña Rn víi co (∂ ∗ f (x)) = co (A) . Khi ®ã, Ext (co (∂ ∗ f (x))) = Ext (co (A)) . f t¹i x . Khi ®ã, 12 Chóng ta chØ ra r»ng Ext (co (∂ ∗ f (x))) ⊆ A. ThËt vËy hiÓn nhiªn ta cã Ext (co (A)) ⊆ Ext (A) . Do ®ã, Ext (co (∂ ∗ f (x))) = Ext (co (A)) ⊆ Ext (A) ⊂ A. Bëi v× A lµ tËp ®ãng, ta cã Ext (co (∂ ∗ f (x))) ⊆ A. MÆt kh¸c bëi v×, cho nªn trªn cña ∂ ∗ f (x) lµ mét d­íi vi ph©n suy réng chÝnh quy comp¨c trªn, Ext (co (∂ ∗ f (x))) f x t¹i . Do ®ã, còng lµ d­íi vi Ext (co (∂ ∗ f (x))) tèi thiÓu trªn duy nhÊt cña f t¹i x. ph©n suy réng chÝnh quy comp¨c lµ d­íi vi ph©n suy réng chÝnh quy Chøng minh t­¬ng tù cho tr­êng hîp f 2 d­íi vi ph©n suy réng chÝnh quy d­íi. Ta nãi hµm v ∈ Rn f cã h÷u h¹n vµ liªn tôc t¹i x lµ chÝnh quy trªn t¹i x nÕu víi mçi , f + (x, v) = f ↑ (x, v) . T­¬ng tù hµm f lµ chÝnh quy d­íi t¹i x nÕu víi mçi v ∈ Rn , f − (x, v) = f ↓ (x, v) . Chó ý r»ng, nÕu f : Rn → R v ∈ Rn f + (., v) [f − (., v)] , lµ Lipschitz ®Þa ph­¬ng trªn Rn vµ nÕu víi mçi lµ nöa liªn tôc trªn [d­íi], th× víi mçi x ∈ Rn vµ v ∈ Rn ,   f + (x, v) = f o (x, v) = f ↑ (x, v) f − (x, v) = fo (x, v) = f ↓ (x, v) , cho nªn, NÕu f lµ chÝnh quy trªn [d­íi] t¹i f ↑ (x, 0) > −∞ låi, ®ãng cña Rn vµ nÕu vµ víi mçi f x (xem [6]). lµ chÝnh quy trªn t¹i x th× v ∈ Rn , f + (x, v) = f ↑ (x, v) = sup x∗ ∈∂ ↑ f (x) hx∗ , vi . ∂ ↑ f (x) kh¸c rçng, 13 Do ®ã, ∂ ↑ f (x) tù, nÕu f ↓ (x, 0) < ∞ cña Rn lµ mét d­íi vi ph©n suy réng chÝnh quy trªn cña vµ víi mçi vµ f chÝnh quy d­íi t¹i ∂ ↓ f (x) víi mçi ∂ ↓ f (x) . T­¬ng kh¸c rçng, låi, ®ãng inf x∗ ∈∂ ↓ f (x) hx∗ , vi . lµ d­íi vi ph©n suy réng chÝnh quy d­íi cña f : Rn → R NÕu th× x t¹i v ∈ Rn , f − (x, v) = f ↓ (x, v) = Cho nªn x f lµ Lipschitz ®Þa ph­¬ng trªn Rn f t¹i x . vµ chÝnh quy trªn t¹i x , th× v ∈ Rn , ∗ f + (x, v) = f ↑ (x, v) = f o (x, v) = ∗ max hx , vi . o x ∈∂ f (x) Do ®ã, cña f Ext (∂ o f (x)) t¹i x lµ d­íi vi ph©n suy réng chÝnh quy tèi thiÓu trªn duy nhÊt . Chó ý r»ng, nÕu f lµ låi th× chÝnh quy tèi thiÓu trªn duy nhÊt cña f Ext (∂f (x)) t¹i lµ d­íi vi ph©n suy réng x , trong ®ã ∂f (x) := {x∗ ∈ X ∗ : f (y) − f (x) ≥ hx∗ , y − xi , ∀y ∈ Rn } lµ d­íi vi ph©n låi cña 1.2 f t¹i x . §iÒu kiÖn cÇn Fritz John cho cùc tiÓu Pareto yÕu PhÇn nµy tr×nh bµy c¸c ®iÒu kiÖn cÇn Fritz John cho cùc tiÓu yÕu ®Þa ph­¬ng d­íi ng«n ng÷ d­íi vi ph©n suy réng chÝnh quy trªn vµ b¸n chÝnh quy trªn. XÐt bµi to¸n tèi ­u ®a môc tiªu (P) sau:   min f (x),      g (x) ≤ 0,  h (x) = 0,      x ∈ C, f g h trong ®ã con cña , Rn , t­¬ng øng lµ c¸c ¸nh x¹ tõ . Khi ®ã , vµo Rr Rm Rl C , , ; lµ mét tËp f = (f1 , ..., fr ) g = (g1 , ..., gm ) h = (h1 , ..., hl ) f1 , ..., fr g1 , ..., gm h1 , ..., hl , Rn , , , trong ®ã lµ nh÷ng hµm gi¸ trÞ thùc më réng x¸c ®Þnh trªn 14 Rn cã x, y ∈ Rn . Víi nghÜa , ta viÕt x≤y nÕu xi ≤ yi , (i = 1, ..., n) . Nh­ vËy gi (x) ≤ 0 (i = 1, ..., m) lµ , (j = 1, ..., l) . §Æt vµ h(x) = 0 cã nghÜa lµ I = {1, ..., m} J = {1, ..., r} L = {1, ..., l} , , . g(x) ≤ 0 hj (x) = 0 , Chó ý r»ng ®iÒu kiÖn cÇn d­íi ng«n ng÷ d­íi vi ph©n suy réng cho bµi to¸n víi rµng buéc tËp hoÆc rµng buéc bÊt ®¼ng thøc ®· ®­îc nghiªn cøu bëi Dutta-Chandra [7,8] vµ cã rµng buéc ®¼ng thøc vµ bÊt ®¼ng thøc ®· ®­îc nghiªn cøu bëi Luu [15]. KÝ hiÖu M lµ tËp chÊp nhËn ®­îc cña bµi to¸n (P): M := {x ∈ C : g(x) ≤ 0, h(x) = 0} , vµ I(x̄) := {i ∈ I : g(x̄) = 0} , H := {x ∈ Rn : h(x) = 0} . Më réng cña ®Þnh lý Ljusternik cæ ®iÓn cña JimÐnez-Novo trong [11] sÏ ®­îc sö dông ®Ó dÉn ®iÒu kiÖn cÇn tèi ­u. MÖnh ®Ò 1.2.1 [11] Gi¶ sö r»ng x̄ ∈ H ∩ C ; (a) C lµ tËp låi vµ (b) h liªn tôc trong mét l©n cËn cña FrÐchet lµ x̄ vµ kh¶ vi FrÐchet t¹i x̄ víi ®¹o hµm ∇h(x̄); (c) §iÒu kiÖn chÝnh quy (RC) sau ®©y ®óng: 0∈ X γj ∇hj (x̄) + N (C, x̄) ⇒ γ1 = ... = γl = 0. j∈L Khi ®ã, A(H ∩ C; x̄) = T (H ∩ C; x̄) = (ker ∇h(x̄)) ∩ T (C; x̄) = cl [(ker ∇h(x̄)) ∩ cone(C − x̄)] , trong ®ã cl kÝ hiÖu bao ®ãng. 15 NhËn xÐt 1.2.1 NÕu C = Rn h , thuéc líp C1 trong mét l©n cËn cña x̄ vµ ∇h1 (x̄), ..., ∇hr (x̄) lµ ®éc lËp tuyÕn tÝnh, th× mÖnh ®Ò 1.2.1 trë thµnh ®Þnh lý Ljusternik cæ ®iÓn. ThËt vËy, khi ®ã ¸nh x¹ ®óng vµ ta cã ∇h(x̄) lµ toµn ¸nh, T (C; x̄) = Rn , ®iÒu kiÖn chÝnh quy (RC) ker ∇h(x̄) = T (C; x̄). §iÒu kiÖn (RC) sÏ ®­îc minh häa bëi vÝ dô sau. VÝ dô 1.2.1 Cho h R3 → R2 : vµ C ⊂ R3 ®­îc x¸c ®Þnh nh­ sau h := (h1 , h2 ) (x̄, ȳ, z̄) = 0, , h1 (x, y, z) = x + 2y + z, h2 (x, y, z) = 2x + 4y − z, C := {(x, y, z) : −1 ≤ x ≤ 0, −1 ≤ y, z ≤ 1} . Khi ®ã ∇h1 (0, 0, 0) = (1, 2, 1) ∇h2 (0, 0, 0) = (2, 4, −1) T (C; 0) = −R+ × , R × R N (C; 0) = R+ × {0} × {0} , , vµ ®iÒu kiÖn (RC) tháa m·n. ThËt vËy nÕu 0 ∈ γ1 ∇h1 (0) + γ2 ∇h2 (0) + N (C; 0), cã nghÜa lµ (0, 0, 0) ∈ (γ1 + 2γ2 , 2γ1 + 4γ2 , γ1 − γ2 ) + R+ × {0} × {0} , khi ®ã ta suy ra γ1 = γ2 = 0 . Do ®ã, ®iÒu kiÖn (RC) ®óng Nh¾c l¹i r»ng ®iÓm x̄ ∈ M bµi to¸n (P) nÕu tån t¹i mét sè ®­îc gäi lµ cùc tiÓu Pareto yÕu ®Þa ph­¬ng cña δ>0 sao cho kh«ng tån t¹i x ∈ M ∩ B (x̄; δ) tháa m·n (∀k ∈ J) , fk (x) < fk (x̄) trong ®ã B (x̄; δ) lµ h×nh cÇu më b¸n kÝnh δ t©m x̄ . Gi¶ thiÕt sau ®©y lµ cÇn thiÕt ®Ó dÉn c¸c ®iÒu kiÖn cÇn cho nghiÖm h÷u hiÖu yÕu. 16 Gi¶ thiÕt 1.2.1 Tån t¹i mét chØ sè t¹i x̄ ph©n . Víi suy mçi réng gi (i ∈ / I (x̄)) s∈J sao cho k ∈ J, k 6= s b¸n chÝnh liªn tôc t¹i quy fs vµ cã mét d­íi vi ph©n suy réng trªn i ∈ I (x̄) , trªn ∂ ∗ fk (x̄) c¸c vµ hµm fk ∂ ∗ gi (x̄) gi vµ t¹i x̄ ; cã tÊt ∂ ∗ fs (x̄) c¸c c¶ d­íi c¸c vi hµm x̄ . Trªn c¬ së ®Þnh lý Ljusternik suy réng cña JimÐnez-Novo [11], ta chøng minh ®iÒu kiÖn cÇn cho cùc tiÓu Pareto yÕu ®Þa ph­¬ng cña (P). §Þnh lý 1.2.1 Gi¶ sö x̄ lµ cùc tiÓu Pareto yÕu ®Þa ph­¬ng cña (P). Gi¶ sö r»ng tÊt c¶ c¸c gi¶ thiÕt cña mÖnh ®Ò 1.2.1 vµ gi¶ thiÕt 1.2.1 ®óng. Gi¶ sö c¸c hµm gi (i ∈ I (x̄)) Lipschitz ®Þa ph­¬ng t¹i x̄. fk (k ∈ J) vµ Khi ®ã, c¸c hÖ sau kh«ng cã nghiÖm v ∈ Rn : hξk , vi < 0 (∀k ∈ J), sup (1.2) ξk ∈conv∂ ∗ fk (x̄) sup hξi , vi < 0 (∀i ∈ I(x̄)), (1.3) ξi ∈conv∂ ∗ gi (x̄) h∇hj (x̄), vi = 0 (∀j ∈ L), (1.4) v ∈ T (x̄; C). (1.5) Chøng minh Ta chØ ra r»ng nh÷ng ®iÒu kiÖn sau kh«ng cã nghiÖm v ∈ Rn : fs− (x̄; v) < 0, (1.6) fk+ (x̄; v) < 0 (∀k ∈ J; k 6= s), (1.7) gi+ (x̄; v) < 0 (∀i ∈ I(x̄)), (1.8) h∇hj (x̄), vi = 0 (∀j ∈ L), (1.9) v ∈ T (x̄; C). (1.10)
- Xem thêm -

Tài liệu liên quan