Tài liệu Bài toán tối ưu với hàm thuần nhất dương

www.VNMATH.com ®¹i häc Th¸i Nguyªn Tr-êng ®¹i häc khoa häc -------------  0  ------------- NguyÔn Xu©n Huy Bµi to¸n tèi -u víi hµm thuÇn nhÊt d-¬ng LuËn v¨n th¹c sÜ to¸n häc Th¸i Nguyªn - 2009 www.VNMATH.com ®¹i häc Th¸i Nguyªn Tr-êng ®¹i häc khoa häc -------------  0  ------------- NguyÔn Xu©n Huy Bµi to¸n tèi -u víi hµm thuÇn nhÊt d-¬ng Chuyªn ngµnh: To¸n øng dông M· sè: 60.46.36 LuËn v¨n th¹c sÜ to¸n häc Ng-êi h-íng dÉn khoa häc GS-TS TrÇn Vò ThiÖu Th¸i Nguyªn - 2009 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.Lrc-tnu.edu.vn www.VNMATH.com M l 1 2 Lêi nãi ®Çu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 Nh÷ng kiÕn thø vÒ gi¶i tÝ h låi 5 1.1 TËp affin vµ tËp låi . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2 Hµm låi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 C¸ bµi to¸n tèi ­u 18 2.1 C¸ kh¸i niÖm ¬ b¶n 3 . . . . . . . . . . . . . . . . . . . . . . . 18 2.2 Bµi to¸n tèi ­u kh«ng rµng bué . . . . . . . . . . . . . . . . . . 23 2.3 Bµi to¸n tèi ­u ã rµng bué . . . . . . . . . . . . . . . . . . . . 25 Bµi to¸n tèi ­u víi hµm thuÇn nhÊt d­¬ng 32 3.1 Hµm thuÇn nhÊt . . . . . . . . . . . . . . . . . . . . . . . . . . 32 3.2 Bµi to¸n tèi ­u víi hµm thuÇn nhÊt d­¬ng . . . . . . . . . . . . . 38 3.3 C¸ kÕt qu¶ ®èi ngÉu hÝnh . . . . . . . . . . . . . . . . . . . . 38 3.4 Tèi ­u toµn  . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 KÕt luËn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 Tµi liÖu tham kh¶o . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 54 www.VNMATH.com Lêi nãi ®Çu Hµm thù thuÇn nhÊt d­¬ng ( ßn gäi ®¬n gi¶n lµ hµm thuÇn nhÊt) rÊt quen thué vµ hay gÆp trong nhiÒu øng dng, ®Æ biÖt trong nghiªn øu kinh tÕ vi m«. Hµm tuyÕn tÝnh, hµm bË hai, hµm Cobb-Douglas, ¸ hµm ®a thø thuÇn nhÊt ... lµ ¸ vÝ d vÒ hµm thuÇn nhÊt d­¬ng. Hµm thuÇn nhÊt biÓu lé hµnh vi rÊt ®Òu ®Æn, khi mäi biÕn t¨ng theo ïng mét tØ lÖ. Ch¼ng h¹n, víi hµm thuÇn nhÊt bË 0, khi ¸ biÕn thay ®æi theo ïng mét tØ lÖ th× gi¸ trÞ ña hµm kh«ng hÒ thay ®æi; víi hµm thuÇn nhÊt bË 1, khi t¨ng gÊp ®«i (gÊp ba) mäi biÕn th× gi¸ trÞ ña hµm òng t¨ng gÊp ®«i (gÊp ba). Mét ®Æ tr­ng quan träng ña hµm thuÇn nhÊt lµ ¸ ®¹o hµm riªng ña mét hµm thuÇn nhÊt òng lµ mét hµm thuÇn nhÊt vµ ¸ hµm thuÇn nhÊt ã thÓ biÓu diÔn ®­î qua ¸ ®¹o hµm riªng ña nã (§Þnh lý Euler). §Ò tµi luËn v¨n ®Ò Ëp tíi líp bµi to¸n tèi ­u víi ¸ hµm thuÇn nhÊt d­¬ng, nghÜa lµ hµm m tiªu vµ ¸ hµm rµng bué ña bµi to¸n ®Òu lµ ¸ hµm thuÇn nhÊt (bË ã thÓ kh¸ nhau). Qui ho¹ h tuyÕn tÝnh vµ qui ho¹ h bË hai lµ nh÷ng tr­êng hîp riªng ña líp bµi to¸n nµy. ViÖ t×m hiÓu bµi to¸n tèi ­u víi ¸ hµm thuÇn nhÊt d­¬ng lµ hoµn toµn Çn thiÕt vµ h÷u Ý h, gióp ta hiÓu s©u h¬n vÒ ¸ bµi to¸n, ph­¬ng ph¸p tèi ­u phi tuyÕn vµ më réng ph¹m vi øng dng ña hóng. M tiªu ña luËn v¨n lµ t×m hiÓu vµ tr×nh bµy mét sè kÕt qu¶ ¬ b¶n liªn quan tíi bµi to¸n tèi ­u víi ¸ hµm thuÇn nhÊt d­¬ng. C¸ vÊn ®Ò ®Ò Ëp trong luËn v¨n ®­î tr×nh bµy mét ¸ h hÆt hÏ vÒ mÆt to¸n hä , mét sè kh¸i niÖm vµ sù kiÖn nªu trong luËn v¨n ã kÌm theo vÝ d vµ h×nh vÏ ®Ó minh ho¹. Néi dung luËn v¨n ®­î hia thµnh ba h­¬ng: Ch­¬ng 1 “Nh÷ng kiÕn thø vÒ gi¶i tÝ h låi” giíi thiÖu v¾n t¾t mét sè kiÕn thø ¬ b¶n, Çn thiÕt vÒ gi¶i tÝ h låi nh­ ¸ kh¸i niÖm vÒ tËp affine vµ bao affine, tËp låi vµ bao låi, nãn låi vµ tËp låi ®a diÖn, ïng víi ¸ kh¸i niÖm ®Ønh, ¹nh, diÖn ña tËp låi ®a diÖn vµ ¸ kh¸i niÖm vÒ hµm låi, hµm låi hÆt ïng 2 www.VNMATH.com mét sè tÝnh hÊt ¬ b¶n ña hóng. Néi dung tr×nh bµy trong h­¬ng nµy sÏ Çn ®Õn ë h­¬ng sau, khi nghiªn øu ¸ bµi to¸n tèi ­u phi tuyÕn nãi hung vµ bµi to¸n tèi ­u víi hµm thuÇn nhÊt d­¬ng nãi riªng. Ch­¬ng 2 “C¸ bµi to¸n tèi ­u” tr×nh bµy v¾n t¾t ¸ kh¸i niÖm vµ kÕt qu¶ vÒ bµi to¸n tèi ­u phi tuyÕn, ph©n biÖt tèi ­u ®Þa ph­¬ng vµ tèi ­u toµn  , tèi ­u kh«ng rµng bué vµ tèi ­u ã rµng bué , ¸ ®iÒu kiÖn Çn vµ ®iÒu kiÖn ®ñ ña tèi ­u, ®Æ biÖt lµ ®iÒu kiÖn KKT ho tèi ­u ã rµng bué . C¸ kh¸i niÖm nãn tiÕp xó , kh¸i niÖm hÝnh quy, hµm Lagrange vµ nh©n tö Lagrange òng ®­î giíi thiÖu. NhiÒu vÝ d ®· ®­î ®­a ra ®Ó minh ho¹ ho ¸ kh¸i niÖm vµ kÕt qu¶ tr×nh bµy. Ch­¬ng 3 “Bµi to¸n tèi ­u víi hµm thuÇn nhÊt d­¬ng” ®Ò Ëp tíi líp bµi to¸n tèi ­u phi tuyÕn víi ¸ hµm thuÇn nhÊt d­¬ng. Bµi to¸n ®­î xt ã thÓ diÔn ®¹t nh­ mét bµi to¸n “min-max” ®¬n gi¶n, víi “max” lµ bµi to¸n tuyÕn tÝnh th«ng th­êng ã mét rµng bué duy nhÊt. Tõ ®ã nªu ¸ h diÔn ®¹t míi ho qui ho¹ h tuyÕn tÝnh vµ qui ho¹ h toµn ph­¬ng rµng bué tuyÕn tÝnh. Víi nh÷ng gi¶ thiÕt nhÊt ®Þnh, ã thÓ hØ ra bµi to¸n tèi ­u kh«ng låi bË hai t­¬ng ®­¬ng víi bµi to¸n tèi ­u låi. Do thêi gian ã h¹n nªn luËn v¨n nµy míi hØ dõng l¹i ë viÖ t×m hiÓu tµi liÖu, s¾p xÕp vµ tr×nh bµy ¸ kÕt qu¶ nghiªn øu ®· ã theo hñ ®Ò ®Æt ra. Trong qu¸ tr×nh viÕt luËn v¨n òng nh­ trong xö lý v¨n b¶n h¾ h¾n kh«ng tr¸nh khái ã nh÷ng sai sãt nhÊt ®Þnh. T¸ gi¶ luËn v¨n rÊt mong nhËn ®­î sù gãp ý ña ¸ thÇy « vµ ¸ b¹n ®ång nghiÖp ®Ó luËn v¨n ®­î hoµn thiÖn h¬n. Nh©n dÞp nµy, t¸ gi¶ xin bµy tá lßng biÕt ¬n s©u s¾ ®Õn thÇy h­íng dÉn GS-TS TrÇn Vò ThiÖu ®· tËn t×nh gióp ®ì trong suèt qu¸ tr×nh lµm luËn v¨n. T¸ gi¶ xin h©n thµnh ¶m ¬n ¸ thÇy, « ë ViÖn C«ng nghÖ th«ng tin, ViÖn To¸n hä Hµ Néi, Khoa C«ng nghÖ th«ng tin, Khoa To¸n vµ Phßng §µo t¹o sau ®¹i hä tr­êng §¹i hä Khoa hä - §¹i hä Th¸i Nguyªn ®· tËn t×nh gi¶ng d¹y vµ t¹o mäi ®iÒu kiÖn thuËn lîi ho t¸ gi¶ trong qu¸ tr×nh hä tËp t¹i tr­êng. 3 www.VNMATH.com T¸ gi¶ òng xin h©n thµnh ¶m ¬n Ban l·nh ®¹o Së Gi¸o d vµ §µo t¹o Qu¶ng Ninh, Ban Gi¸m hiÖu vµ ¸ thÇy « gi¸o Tr­êng THPT Hoµng Què ViÖt, n¬i t¸ gi¶ «ng t¸ ®· t¹o nh÷ng ®iÒu kiÖn thuËn lîi nhÊt ®Ó t¸ gi¶ hoµn thµnh nhiÖm v hä tËp. T¸ gi¶ òng xin bµy tá sù quý mÕn vµ lßng biÕt ¬n s©u s¾ tíi Bè mÑ, gia ®×nh vµ ng­êi th©n ®· lu«n khuyÕn khÝ h, ®éng viªn t¸ gi¶ trong suèt qu¸ tr×nh hä ao hä vµ viÕt luËn v¨n nµy. Hµ Néi, th¸ng 9/2009 T¸ gi¶ 4 www.VNMATH.com Ch­¬ng 1 Nh÷ng kiÕn thø vÒ gi¶i tÝ h låi Ch­¬ng nµy nh¾ l¹i v¾n t¾t mét sè kiÕn thø ¬ b¶n, Çn thiÕt vÒ gi¶i tÝ h låi (tËp låi, hµm låi vµ ¸ tÝnh hÊt) ph v ho t×m hiÓu vµ nghiªn øu ¸ bµi to¸n tèi ­u. Néi dung tr×nh bµy ë h­¬ng nµy hñ yÕu dùa trªn ¸ tµi liÖu [1℄, [2℄. 1.1 TËp affin vµ tËp låi 1.1.1. TËp affine Cho x1, x2 lµ hai ®iÓm trong Rn . §­êng th¼ng qua x1, x2 lµ tËp ¸ ®iÓm x = λx1 + (1 − λ)x2 = x2 + λ(x1 − x2 ) , λ ∈ R TËp M ⊆ Rn ®­î gäi lµ tËp affine nÕu M høa hän ¶ ®­êng th¼ng ®i qua hai ®iÓm bÊt kú thué Nãi ¸ h kh¸ , kú thué M , tø lµ ∀x1, x2 ∈ M , λ ∈ R ⇒ λx1 + (1 − λ)x2 ∈ M . M lµ tËp affine nÕu nã høa tæ hîp tuyÕn tÝnh ña hai ®iÓm bÊt M víi tæng ¸ hÖ sè b»ng 1. Ta gäi mét ®iÓm x ∈ R ã d¹ng x= k X λi xi i=1 víi λ1 , λ2, · · · , λk ∈ R vµ k X λi = 1 i=1 5 www.VNMATH.com λ1 , λ2 , · · · , λk ∈ Rn . NÕu M ⊆ Rn lµ mét tËp  affine vµ x0 ∈ M th× tËp L = M − x0 = x − x0 | x ∈ M lµ mét kh«ng gian lµ tæ hîp affine on, tø lµ nÕu ña ¸ ®iÓm a, b ∈ L th× mäi ®iÓm c = λa + µb víi λ, µ ∈ R òng thué L (L ®ãng víi php éng vµ php nh©n v« h­íng). V× vËy, mét tËp affine ã thÓ biÓu diÔn bëi trong ®ã  M = x0 + L = x0 + v | v ∈ L , x0 ∈ M vµ L lµ kh«ng gian on. Kh«ng gian on L t­¬ng øng víi tËp affine M kh«ng ph thué vµo ¸ h hän x0, tø x0 lµ ®iÓm bÊt kú thué M . H¬n n÷a, kh«ng gian on L nµy x¸ ®Þnh duy nhÊt. Ta gäi L lµ kh«ng gian on song song affine víi M . Thø nguyªn (dimension) hay ßn gäi lµ sè hiÒu ña tËp M lµ thø nguyªn ña kh«ng gian on song song víi nã. Bao affine (affine hull) ña mét tËp høa E ⊆ Rn lµ giao ña tÊt ¶ ¸ tËp affine E . §ã lµ tËp affine nhá nhÊt høa E , kÝ hiÖu lµ aff E . VÝ d 1.1. TËp nghiÖm M ña hÖ ph­¬ng tr×nh tuyÕn tÝnh Ax = b, trong ®ã A lµ ma trËn Êp m × n vµ v t¬ b ∈ Rm , lµ mét tËp affine. ThËt vËy, víi x1, x2 ∈ M , ∀λ ∈ R, ta ã
A λx1 + (1 − λ)x2 = λAx1 + (1 − λ)Ax2 = λb + (1 − λ)b = b ⇒ λx1 + (1 − λ)x2 ∈ M  3 VÝ d 1.2. Bao affine ña tËp E = x ∈ R | 0 ≤ x1 ≤ 1, 0 ≤ x2 ≤ 1, x3 = 0  lµ mÆt ph¼ng høa h×nh vu«ng E ,  thÓ aff E = x ∈ R3 | x3 = 0 . 1.1.2. Sè hiÒu vµ ®iÓm trong t­¬ng ®èi Sè hiÒu (hay thø nguyªn) ña mét tËp ña nã, ký hiÖu lµ M ⊆ Rn lµ sè hiÒu ña bao affine dim M . Cho tËp M ⊆ Rn ã dim M < n. Mét ®iÓm a ∈ M ®­î gäi lµ ®iÓm trong t­¬ng ®èi (relative interior point) ña M nÕu tån t¹i h×nh Çu më
B(a, ǫ) sao ho: B(a, ǫ) ∩ aff M ⊂ M . PhÇn trong t­¬ng ®èi trong t­¬ng ®èi ña nÕu ña tËp M , ký hiÖu lµ ri M , lµ tËp høa tÊt ¶ ¸ ®iÓm M . Mét tËp M ⊆ Rn ®­î gäi lµ ã thø nguyªn ®Çy ®ñ dim M = n. DÔ thÊy r»ng tËp M ã phÇn trong kh¸ rçng (int M 6= ∅) khi vµ hØ khi nã ã thø nguyªn ®Çy ®ñ. 6 www.VNMATH.com  E = x ∈ R3 | 0 ≤ x1 ≤ 1, 0 ≤ x2 ≤ 1, x3 = 0 , ta ã:  int E = ∅, ri E = x ∈ R3 | 0 < x1 < 1, 0 < x2 < 1, x3 = 0 , vµ dim E = 2. VÝ d 1.3. Cho 1.1.3. TËp låi vµ ®iÓm ù biªn Cho hai ®iÓm x1, x2 ∈ Rn . TËp tÊt ¶ ¸ ®iÓm ã d¹ng x = λx1 + (1 − λ)x2 = x2 + λ(x1 − x2), 0 ≤ λ ≤ 1,   ®­î gäi lµ ®o¹n th¼ng nèi x1 , x2 , kÝ hiÖu lµ x1 , x2 . TËp M ⊆ Rn ®­î gäi lµ tËp låi ( onvex set) nÕu nã høa hän ®o¹n th¼ng nèi hai ®iÓm bÊt kú thué nã, tø lµ λx1 + (1 − λ)x2 ∈ M . (a) ∀x1 , x2 ∈ M , 0 ≤ λ ≤ 1 ta ã (b) ( ) H×nh 1.1. (a), (b) - TËp låi; (d) ( ), (d) - TËp kh«ng låi Tõ ®Þnh nghÜa dÔ thÊy r»ng giao ña mét hä bÊt kú ¸ tËp låi lµ tËp låi. Tuy nhiªn hîp ña ¸ tËp låi h­a h¾ lµ tËp låi. Ta gäi ®iÓm x ∈ Rn ã d¹ng x= k X λi xi i=1 víi λ1 , λ2, · · · , λk ≥ 0 vµ k X λi = 1 i=1 lµ tæ hîp låi ña ¸ ®iÓm x1 , x2, · · · th× ta nãi x lµ MÖnh ®Ò 1.1. tæ hîp låi hÆt Mét tËp ña M ⊂ Rn , xk ∈ Rn . NÕu λi ≥ 0 víi ∀i = 1, 2, · · · , k x1, x2, · · · , xk ∈ Rn . lµ låi khi vµ hØ khi nã høa tÊt ¶ ¸ tæ hîp låi ña nh÷ng phÇn tö thué nã. 7 www.VNMATH.com MÖnh ®Ò 1.2. a) NÕu M ⊂ Rn lµ tËp låi vµ sè thù α ∈ Rn th× αM = {y | y = αx, x ∈ M} òng lµ tËp låi. M1 , M2 ⊂ Rn lµ hai tËp låi th×  M1 + M2 = x | x = x1 + x2, x1 ∈ M1 , x2 ∈ M2 òng lµ tËp låi. b) NÕu Bao låi ( onvex hull) ña tËp vµ ®­î kÝ hiÖu lµ E ⊂ Rn lµ giao ña tÊt ¶ ¸ tËp låi høa E conv E . §ã lµ tËp låi nhá nhÊt høa E . convE E convE H×nh 1.2. VÝ d vÒ bao låi MÖnh ®Ò 1.3. tö thué E. Cho tËp låi point) ña Bao låi ña tËp E ⊂ Rn høa tÊt ¶ ¸ tæ hîp låi ña ¸ phÇn M ⊂ Rn . Mét ®iÓm x ∈ M ®­î gäi lµ ®iÓm ù biªn (extreme M nÕu x kh«ng thÓ biÓu diÔn ®­î d­íi d¹ng tæ hîp låi hÆt ña hai ®iÓm ph©n biÖt bÊt kú nµo ña M , tø lµ 6 ∃y, z ∈ M, y 6= z sao ho x = λy + (1 − λ)z, 0 < λ < 1. Theo ®Þnh nghÜa, mét ®iÓm ù biªn kh«ng thÓ lµ ®iÓm trong ña tËp låi. V× vËy tÊt ¶ ¸ ®iÓm ù biªn ®Òu lµ ¸ ®iÓm biªn. NÕu tËp hîp kh«ng høa biªn th× nã kh«ng ã ®iÓm ù biªn. MÖnh ®Ò 1.4. Mét tËp låi ®ãng kh¸ rçng M ⊂ Rn hØ khi nã kh«ng høa hän mét ®­êng th¼ng nµo. 8 ã ®iÓm ù biªn khi vµ www.VNMATH.com (b) (a) H×nh 1.3. (a) - H×nh vu«ng ã 4 ®iÓm ù biªn; (b) - H×nh trßn ã v« sè ®iÓm ù biªn Mét ®Æ tr­ng rÊt quan träng ña tËp låi ®ãng vµ bÞ hÆn lµ: §Þnh lý 1.1. (Krein- Milman) Mét tËp låi ®ãng, bÞ hÆn trong Rn lµ bao låi ña ¸ ®iÓm ù biªn ña nã. 1.1.4. Siªu ph¼ng, nöa kh«ng gian Cho a ∈ Rn \ {0} vµ α ∈ R. TËp H := {x ∈ Rn | < a, x > = α} ®­î gäi lµ mét siªu ph¼ng (hyperplane). §ã lµ mét tËp affine ã sè hiÒu b»ng n − 1. Ta gäi v t¬ a lµ v t¬ ph¸p tuyÕn ña siªu ph¼ng nµy. C¸ tËp a < a, x >= α x0 x H×nh 1.4. Siªu ph¼ng trong R2 {x ∈ Rn |< a, x > ≤ α} (hoÆ {x ∈ Rn |< a, x > ≥ α}) víi a ∈ Rn \ {0} vµ α ∈ Rn lµ nöa kh«ng gian ®ãng vµ tËp {x ∈ Rn |< a, x > < α} (hoÆ {x ∈ Rn |< a, x > > α}) lµ nöa kh«ng gian më Cho tËp x¸ ®Þnh bëi siªu ph¼ng {x ∈ Rn | < a, x > = α} M ⊂ Rn , v t¬ a ∈ Rn \ {0} vµ sè thù α ∈ R. Ta gäi siªu ph¼ng H := {x ∈ Rn | < a, x > = α} 9 www.VNMATH.com lµ siªu ph¼ng tùa (supporting hyperplane) ña M t¹i x0 ∈ M nÕu x0 ∈ H vµ M n»m hän trong nöa kh«ng gian ®ãng x¸ ®Þnh bëi H , tø lµ < a, x0 >= α vµ < a, x > ≤ α, ∀x ∈ M . a x0 M H×nh 1.5. Siªu ph¼ng tùa ña §Þnh lý 1.2. Qua mçi ®iÓm biªn siªu ph¼ng tùa ña §Þnh lý 1.3. M t¹i x0 M t¹i ña tËp låi x0 . Mét tËp låi ®ãng kh¸ rçng x0 M ⊂ Rn M ⊂ Rn tån t¹i Ýt nhÊt mét lµ giao ña hä ¸ nöa kh«ng gian tùa ña nã. 1.1.5. Nãn vµ nãn låi TËp M ⊂ Rn ®­î gäi lµ nãn ( one) nÕu x ∈ M, λ ≥ 0 ⇒ λx ∈ M Mét nãn lu«n høa ®iÓm gè 0 ∈ Rn . TËp M ⊂ Rn ®­î gäi lµ nãn låi nÕu M võa lµ nãn võa lµ låi, nghÜa lµ víi bÊt kú x1 , x2 ∈ M vµ λ1 , λ2 ≥ 0 ta ã λ1 x1 + λ2 x2 ∈ M . 0 0 (b) - Nãn kh«ng låi H×nh 1.6. (a) - Nãn låi VÝ d 1.4. C¸ tËp sau ®©y lµ ¸ nãn låi ã ®Ønh t¹i gè 10 0 trong Rn : www.VNMATH.com • Rn+ := {x = (x1, x2, · · · , xn) : xi ≥ 0, i = 1, 2, · · · , n} (orthant kh«ng ©m) • Rn++ := {x = (x1, x2, · · · , xn) : xi > 0, i = 1, 2, · · · , n} (orthant d­¬ng) MÖnh ®Ò 1.5. TËp M ⊂ Rn lµ nãn låi khi vµ hØ khi nã høa tÊt ¶ ¸ tæ hîp tuyÕn tÝnh kh«ng ©m ña ¸ phÇn tö ña nã. Cho tËp  1 k v t¬ v 1 , v 2, · · · , v k ∈ Rn . TËp 2 cone v , v , · · · , v n n n := v ∈ R | v = ®­î gäi lµ nãn sinh bëi tËp  k X i=1 o i λi v , λi ≥ 0, i = 1, · · · , k ⊂ Rn  v 1, v 2, · · · , v k . V t¬ v h ∈ v 1 , v 2, · · · , v k gäi lµ kh«ng thiÕt yÕu (non essential) nÕu   cone v 1 , · · · , v h−1, v h+1, · · · , v k = cone v 1, v 2, · · · , v k . v1 v1 v2 v3 0 v 0 (a) H×nh 1.7. (a) - V t¬ (b) - HoÆ v t¬ v2 v 2 v3 2 (b) lµ kh«ng thiÕt yÕu hoÆ v t¬ v3 lµ kh«ng thiÕt yÕu 1.1.6. Ph­¬ng lïi xa, ph­¬ng ù biªn Cho tËp låi kh¸ rçng (re ession dire tion) ña D ⊆ Rn . V t¬ d 6= 0 ®­î gäi lµ ph­¬ng lïi xa D nÕu {x + λd | λ ≥ 0} ⊂ D víi mçi x ∈ D. Mäi nöa ®­êng th¼ng song song víi mét ph­¬ng lïi xa ®iÓm bÊt kú ña khi vµ hØ khi d xuÊt ph¸t tõ mét D ®Òu n»m hän trong D. Râ rµng r»ng tËp D kh«ng bÞ hÆn D ã mét ph­¬ng lïi xa. TËp tÊt ¶ ¸ ph­¬ng lïi xa ña tËp låi D ⊆ Rn ïng v t¬ 0 t¹o thµnh mét nãn låi. Nãn låi ®ã ®­î gäi lµ nãn lïi xa ña tËp 11 D vµ kÝ hiÖu lµ rec D. www.VNMATH.com Ta nãi hai ph­¬ng Ph­¬ng lïi xa ña d1 vµ d2 kh¸ biÖt (distin t) nÕu d1 6= αd2 víi α > 0. d ña tËp D ®­î gäi lµ ph­¬ng ù biªn (extreme dire tion) D nÕu kh«ng tån t¹i ¸ ph­¬ng lïi xa kh¸ biÖt d1 vµ d2 ña D sao ho d = λ1d1 + λ2 d2 víi λ1 , λ2 > 0. 1.1.7. C¸ ®Þnh lý t¸ h tËp låi §©y lµ nh÷ng ®Þnh lý ¬ b¶n nhÊt ña gi¶i tÝ h låi, lµ «ng  h÷u hiÖu ña lý thuyÕt tèi ­u. Cho hai tËp C, D ⊂ Rn vµ siªu ph¼ng H := {x ∈ Rn | < a, x > = α} víi a ∈ Rn \ {0} vµ α ∈ R Ta nãi siªu ph¼ng H t¸ h hai tËp C vµ D nÕu < a, x > ≤ α ≤ < a, y > ∀x ∈ C, ∀y ∈ D vµ siªu ph¼ng H t¸ h h¼n (hay t¸ h hÆt ) hai tËp C, D nÕu < a, x > < α < < a, y > ∀x ∈ C, ∀y ∈ D §Þnh lý 1.4. (§Þnh lý t¸ h I) NÕu hai tËp låi C, D ⊂ Rn kh«ng rçng vµ rêi nhau th× ã mét siªu ph¼ng t¸ h hóng. §Þnh lý 1.5. (§Þnh lý t¸ h II) NÕu hai tËp låi ®ãng C, D ⊂ Rn kh«ng rçng, rêi nhau vµ Ýt nhÊt mét trong hai tËp Êy lµ ompa th× ã mét siªu ph¼ng t¸ h h¼n hóng. HÖ qu¶ 1.1. ®ã, (Bæ ®Ò Farkas) Cho v t¬ < a, x > ≥ 0 sao ho víi mäi a = AT y . x tho¶ m·n a ∈ Rn Ax ≥ 0 vµ ma trËn A Êp m × n. khi vµ hØ khi Khi ∃y ∈ Rn , y ≥ 0 Bæ ®Ò Farkas ã rÊt nhiÒu øng dng. VÒ mÆt h×nh hä , bæ ®Ò nµy hØ ra r»ng nãn K = {x ∈ Rn | Ax ≥ 0} n»m h¼n trong nöa kh«ng gian {x ∈ Rn |< a, x > ≥ 0} khi vµ hØ khi v t¬ ph¸p tuyÕn ña siªu ph¼ng {x ∈ Rn |< a, x > = 0} n»m trong nãn sinh bëi ¸ hµng ña ma trËn A. 1.1.8. TËp låi ®a diÖn TËp låi ®a diÖn P ⊆ Rn lµ giao ña mét sè h÷u h¹n nöa kh«ng gian ®ãng. Nãi ¸ h kh¸ , nã lµ tËp nghiÖm ña mét hÖ h÷u h¹n ¸ bÊt ®¼ng thø tuyÕn 12 www.VNMATH.com tÝnh < ai , x > ≥ bi , i = 1, 2, · · · , m. Mçi bÊt ®¼ng thø trong (1.1) (1.1) ®­î gäi lµ mét rµng bué . Rµng bué k ∈ {i = 1, 2, · · · , m} lµ mét rµng bué thõa nÕu  x |< ai , x > ≥ bi , i = 1, 2, · · · , m  = x |< ai , x > ≥ bi, i ∈ {1, 2, · · · , m} \ {k} Ta kÝ hiÖu A lµ ma trËn Êp m×n víi ai v t¬ = (a1, a2 , · · · , an ), i = 1, 2, · · · , n, b = (b1, b2, · · · , bm)T vµ x = (x1, x2, · · · , xn)T th× hÖ (1.1) ®­î viÕt d­íi d¹ng ma trËn nh­ sau Ax ≥ b V× mét ph­¬ng tr×nh tuyÕn tÝnh ã thÓ biÓu diÔn t­¬ng ®­¬ng bëi hai bÊt ph­¬ng tr×nh tuyÕn tÝnh nªn tËp nghiÖm ña hÖ ph­¬ng tr×nh vµ bÊt ph­¬ng tr×nh tuyÕn tÝnh   < ai , x > = bi , i = 1, 2, · · · , m1  < ai , x > ≥ b , i = m + 1, · · · , m i 1 òng lµ mét tËp låi ®a diÖn. DÔ thÊy r»ng tËp låi ®a diÖn lµ mét tËp låi, ®ãng. Mét tËp låi ®a diÖn bÞ hÆn ®­î gäi lµ ®a diÖn låi hay gäi t¾t lµ . ®a diÖn a1 a5 a2 4 a a3 H×nh 1.8. §a diÖn nµy lµ giao ña 5 nöa kh«ng gian Cho tËp låi ®a diÖn D x¸ ®Þnh bëi (1.1). NÕu ®iÓm x0 ∈ D tho¶ m·n < ai , x0 >= bi, th× ta nãi ®iÓm x0 tho¶ m·n hÆt rµng bué i. TËp 13 www.VNMATH.com  I(x0) := i ∈ {1, 2, · · · , m} < ai , x0 >= bi lµ tËp hîp ¸ hØ sè ¸ rµng bué tho¶ m·n hÆt t¹i Mçi ®iÓm ù biªn ña tËp låi ®a diÖn on låi F 6= ∅ ®­î gäi lµ mét diÖn ña ®èi ña mét ®o¹n th¼ng nµo ®ã thué x0 ∈ D . D ®­î gäi lµ mét ®Ønh ña D. TËp D nÕu F høa mét ®iÓm trong t­¬ng D th× F høa hän ¶ ®o¹n th¼ng ®ã, nghÜa lµ y ∈ D, z ∈ D, x = λy + (1 − λ)z ∈ F víi 0 < λ < 1 ⇒ y ∈ F, z ∈ F 1.2 Hµm låi 1.2.1. §Þnh nghÜa hµm låi vµ hµm låi hÆt Hµm f ®­î gäi lµ hµm låi ( onvex fun tion) x¸ ®Þnh trªn tËp låi D ⊆ Rn nÕu víi bÊt kú Ta gäi x1, x2 ∈ D vµ bÊt kú sè thù λ ∈ [0, 1] ta ã
f λx1 + (1 − λ)x2 ≤ λf (x1) + (1 − λ)f (x2). f lµ hµm låi hÆt (stri tly onvex fun tion) trªn tËp låi D nÕu
f λx1 + (1 − λ)x2 < λf (x1) + (1 − λ)f (x2). víi bÊt kú x1 , x2 f lµ dom f = {x ∈ D | f (x) < +∞} hiÖu ña hµm Epigraph ∈ D, x1 6= x2 vµ bÊt kú sè thù λ ∈ (0, 1). MiÒn x¸ ®Þnh h÷u (trªn ®å thÞ) ña hµm låi f lµ tËp hîp epi(f ) := {(x, α) ∈ D × R | x ∈ D, α ≥ f (x)}. Hµm låi kh«ng gian f : D −→ R ∪ {+∞} ã thÓ ®­î më réng thµnh hµm låi trªn toµn Rn b»ng ¸ h ®Æt f (x) = +∞, ∀x ∈ / dom f . V× vËy ®Ó ®¬n gi¶n, f lµ hµm låi trªn Rn . ta th­êng xt MÖnh ®Ò 1.5. a) Hµm f x¸ ®Þnh trªn tËp låi kh¸ rçng epi(f ) lµ tËp låi. b) Hµm g D ⊆ Rn x¸ ®Þnh trªn tËp låi kh¸ rçng lµ hµm låi khi vµ hØ khi D ⊆ Rn lµ hµm lâm khi vµ hØ khi tËp hypograph (d­íi ®å thÞ) ña nã lµ tËp låi, trong ®ã 14 www.VNMATH.com hypo(g) := {(x, α) ∈ D × R | x ∈ D, α ≤ g(x)}. (b) (a) (b) - Hypogrph ña mét hµm lâm H×nh 1.9. (a) - Epigraph ña mét hµm låi; 1.2.2. C¸ php to¸n vÒ hµm låi Cho hµm låi f1 x¸ ®Þnh trªn tËp låi låi D1 ⊆ Rn , hµm låi f2 x¸ ®Þnh trªn tËp D2 ⊆ Rn vµ sè thù λ > 0. C¸ php to¸n λf1, f1 + f2, max{f1 , f2} ®­î ®Þnh nghÜa nh­ sau: (λf1)(x) := λf1 (x), ∀x ∈ D1 (f1 + f2)(x) := f1 (x) + f2 (x), ∀x ∈ D1 ∩ D2 max{f1, f2}(x) := max{f1(x), f2(x)}, ∀x ∈ D1 ∩ D2 . MÖnh ®Ò 1.6. Cho hµm f1 lµ låi trªn D1 , f2 α > 0, β > 0. Khi ®ã, ¸ hµm αf1 + βf2 vµ låi trªn D2 vµ hai sè thù max{f1, f2} lµ låi trªn D1 ∩ D2 . 1.2.3. TÝnh liªn t vµ ®¹o hµm theo h­íng ña hµm låi Cho hµm låi §Þnh lý 1.5. trªn f x¸ ®Þnh trªn tËp låi më D ⊆ Rn . Ta ã: NÕu f lµ hµm låi x¸ ®Þnh trªn tËp låi më D. §Þnh lý 1.6. NÕu f : D −→ R D ⊆ Rn th× f lµ mét hµm låi x¸ ®Þnh trªn tËp låi th× nã ã ®¹o hµm theo mäi h­íng d ∈ R \ {0} t¹i mäi ®iÓm liªn t D ⊆ Rn x0 ∈ dom f vµ f ′ (x0, d) ≤ f (x0 + d) − f (x0) HÖ qu¶ 1.2. NÕu f lµ hµm låi kh¶ vi x¸ ®Þnh trªn tËp låi më hµm theo mäi h­íng d ∈ R \ {0} t¹i mäi ®iÓm x0 ∈ dom f D vµ < ▽f (x0), d >= f ′ (x0, d) ≤ f (x0 + d) − f (x0) 15 th× f ã ®¹o www.VNMATH.com 1.2.4. Tiªu huÈn nhËn biÕt hµm låi kh¶ vi §Þnh lý 1.7. hµm låi trªn Cho D f lµ hµm kh¶ vi trªn tËp låi më D ⊆ Rn . Khi ®ã hµm f lµ khi vµ hØ khi f (y) − f (x) ≥ < ▽f (x), y − x >, ∀x, y ∈ D Ta ®· biÕt víi hµm mét biÕn f x¸ ®Þnh trªn kho¶ng më D = (a, b) ⊆ R th× f lµ hµm låi trªn D khi vµ hØ khi f ′′ (x) ≥ 0, ∀x ∈ D §Þnh lý 1.8. Cho lµ hµm låi trªn trªn f lµ hµm kh¶ vi hai lÇn trªn tËp låi më D ⊆ Rn . Khi ®ã f D khi vµ hØ khi ma trËn Hesse ▽2 f (x) lµ nöa x¸ ®Þnh d­¬ng D, tø víi ∀x ∈ D th× y T ▽2 f (x)y ≥ 0, ∀y ∈ Rn f Hµm mäi lµ hµm låi hÆt trªn D nÕu x ∈ D, th× ▽2 f (x) x¸ ®Þnh d­¬ng trªn D, tø víi y T ▽2 f (x)y > 0, ∀y ∈ Rn \ {0}. HÖ qu¶ 1.3. Cho hµm toµn ph­¬ng f (x) = trong ®ã Q nÕu < x, Qx > + < c, x > + α, lµ ma trËn vu«ng ®èi xøng Êp hµm låi trªn Rn 1 2 Rn nÕu n, c ∈ Rn vµ Q lµ ma trËn nöa x¸ ®Þnh d­¬ng (f α ∈ R. Khi ®ã, f lµ lµ hµm låi hÆt trªn Q lµ ma trËn x¸ ®Þnh d­¬ng). VÝ d 1.5. Cho f (x1, x2) = 2x21 + 3x1x2 + 4x22. Ta ã:   4x1 3x2  ▽f (x) =  3x1 8x2  ▽2 f (x) =  V× ma trËn Hesses hÆt trªn R2 . 4 3 3 8   ▽2 f (x) x¸ ®Þnh d­¬ng nªn hµm f ®· ho lµ hµm låi 16 www.VNMATH.com Tãm l¹i, h­¬ng nµy ®· nh¾ l¹i ¸ kh¸i niÖm vÒ tËp låi (tËp affine vµ bao affine, tËp låi vµ bao låi, nãn låi vµ tËp låi ®a diÖn, ïng víi ¸ kh¸i niÖm ®Ønh, ¹nh, diÖn ña tËp låi ®a diÖn) vµ ¸ kh¸i niÖm vÒ hµm låi, hµm låi hÆt ïng mét sè tÝnh hÊt ¬ b¶n ña hóng. Néi dung tr×nh bµy trong h­¬ng sÏ Çn ®Õn ë ¸ h­¬ng sau, khi nghiªn øu ¸ bµi to¸n phi tuyÕn nãi hung vµ bµi to¸n tèi ­u víi hµm thuÇn nhÊt d­¬ng nãi riªng. 17 www.VNMATH.com Ch­¬ng 2 C¸ bµi to¸n tèi ­u Ch­¬ng nµy ®Ò Ëp tíi ¸ bµi to¸n tèi ­u phi tuyÕn, bao gåm tèi ­u ®Þa ph­¬ng vµ tèi ­u toµn  , tèi ­u kh«ng rµng bué vµ tèi ­u ã rµng bué . Víi mçi lo¹i bµi to¸n ã xt ®Õn ¸ ®iÒu kiÖn Çn vµ ®ñ ña tèi ­u. Néi dung ña h­¬ng hñ yÕu dùa trªn ¸ tµi liÖu [1℄, [2℄ vµ [3℄. 2.1 C¸ kh¸i niÖm ¬ b¶n Mét bµi to¸n tèi ­u tæng qu¸t ®­î ph¸t biÓu nh­ sau: min f (x) víi x ∈ D hoÆ trong ®ã D max f (x) víi x ∈ D (P2) ⊆ Rn ®­î gäi lµ tËp nghiÖm hÊp nhËn ®­î hay tËp rµng bué vµ f : D −→ R lµ nhËn ®­î (P1 ) . Mçi ®iÓm hµm m tiªu hay mét x ∈ D ®­î gäi lµ mét nghiÖm ph­¬ng ¸n hÊp nhËn ®­î ( ã thÓ gäi t¾t lµ mét hÊp ph­¬ng ). ¸n §iÓm x∗ ∈ D mµ −∞ < f (x∗) ≤ f (x), ∀x ∈ D ®­î gäi lµ nghiÖm tèi ­u (nghiÖm ù tiÓu) hoÆ nghiÖm tèi ­u toµn (nghiÖm ù tiÓu toµn  - global minimizer), hoÆ ®¬n gi¶n hØ lµ 18  nghiÖm