Luận văn Bài toán tối ưu với hàm thuần nhất dương

®¹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 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên ®¹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 M l Lêi nãi ®Çu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1 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 2 C¸ bµi to¸n tèi ­u 18 2.1 C¸ kh¸i niÖm ¬ b¶n . . . . . . . . . . . . . . . . . . . . . . . 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 3 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 . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 1 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 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 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 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é M , tø lµ ∀x1, x2 ∈ M , λ ∈ R ⇒ λx1 +(1−λ)x2 ∈ M . Nãi ¸ h kh¸ , M lµ tËp affine nÕu nã høa tæ hîp tuyÕn tÝnh ña hai ®iÓm bÊt kú thué M víi tæng ¸ hÖ sè b»ng 1. Ta gäi mét ®iÓm x ∈ R ã d¹ng x = k∑ i=1 λix i víi λ1, λ2, · · · , λk ∈ R vµ k∑ i=1 λi = 1 5 lµ tæ hîp affine ña ¸ ®iÓm λ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 on, tø lµ nÕu 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 M = x0 + L = { x0 + v | v ∈ L}, trong ®ã 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 víi M . Thø nguyªn (dimension) hay ßn gäi lµ sè hiÒu ña tËp affine M lµ thø nguyªn ña kh«ng gian on song song víi nã. Bao affine (affine hull) ña mét tËp E ⊆ Rn lµ giao ña tÊt ¶ ¸ tËp affine høa 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 VÝ d 1.2. Bao affine ña tËp E = { x ∈ R3 | 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 M ⊆ Rn lµ sè hiÒu ña bao affine ña nã, ký hiÖu lµ dimM . Cho tËp M ⊆ Rn ã dimM < 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 ña tËp M , ký hiÖu lµ riM , lµ tËp høa tÊt ¶ ¸ ®iÓm trong t­¬ng ®èi ña M . Mét tËp M ⊆ Rn ®­î gäi lµ ã thø nguyªn ®Çy ®ñ nÕu dimM = n. DÔ thÊy r»ng tËp M ã phÇn trong kh¸ rçng (intM 6= ∅) khi vµ hØ khi nã ã thø nguyªn ®Çy ®ñ. 6 VÝ d 1.3. Cho E = { x ∈ R3 | 0 ≤ x1 ≤ 1, 0 ≤ x2 ≤ 1, x3 = 0 } , ta ã: intE = ∅, riE = {x ∈ R3 | 0 < x1 < 1, 0 < x2 < 1, x3 = 0}, vµ dimE = 2. 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, x2 ∈ M , 0 ≤ λ ≤ 1 ta ã λx1 + (1− λ)x2 ∈ M . (b) ( ) (a) (d) H×nh 1.1. (a), (b) - TËp låi; ( ), (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∑ i=1 λix i víi λ1, λ2, · · · , λk ≥ 0 vµ k∑ i=1 λi = 1 lµ tæ hîp låi ña ¸ ®iÓm x1, x2, · · · , xk ∈ Rn. NÕu λi ≥ 0 víi ∀i = 1, 2, · · · , k th× ta nãi x lµ tæ hîp låi hÆt ña x1, x2, · · · , xk ∈ Rn. MÖnh ®Ò 1.1. Mét tËp M ⊂ 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 MÖnh ®Ò 1.2. a) NÕuM ⊂ Rn lµ tËp låi vµ sè thù α ∈ Rn th× αM = {y | y = αx, x ∈ M} òng lµ tËp låi. b) NÕu 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. Bao låi ( onvex hull) ña tËp E ⊂ Rn lµ giao ña tÊt ¶ ¸ tËp låi høa E vµ ®­î kÝ hiÖu lµ convE. §ã lµ tËp låi nhá nhÊt høa E. E convE convE H×nh 1.2. VÝ d vÒ bao låi MÖnh ®Ò 1.3. Bao låi ña tËp E ⊂ Rn høa tÊt ¶ ¸ tæ hîp låi ña ¸ phÇn tö thué E. Cho tËp låi M ⊂ Rn. Mét ®iÓm x ∈ M ®­î gäi lµ ®iÓm ù biªn (extreme point) ña 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 ã ®iÓm ù biªn khi vµ hØ khi nã kh«ng høa hän mét ®­êng th¼ng nµo. 8 (a) (b) 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 R n 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 | = α} ®­î 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 x0 x a = α H×nh 1.4. Siªu ph¼ng trong R 2 {x ∈ Rn | ≤ α} (hoÆ {x ∈ Rn | ≥ α}) víi a ∈ Rn \ {0} vµ α ∈ Rn lµ nöa kh«ng gian ®ãng vµ tËp {x ∈ Rn | > α}) lµ nöa kh«ng gian më x¸ ®Þnh bëi siªu ph¼ng {x ∈ Rn | = α} Cho tËp M ⊂ Rn, v t¬ a ∈ Rn \ {0} vµ sè thù α ∈ R. Ta gäi siªu ph¼ng H := {x ∈ Rn | = α} 9 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µ = α vµ ≤ α, ∀x ∈ M . M a x0 H×nh 1.5. Siªu ph¼ng tùa ña M t¹i x0 §Þnh lý 1.2. Qua mçi ®iÓm biªn x0 ña tËp låi M ⊂ Rn tån t¹i Ýt nhÊt mét siªu ph¼ng tùa ña M t¹i x0. §Þnh lý 1.3. Mét tËp låi ®ãng kh¸ rçng M ⊂ Rn 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 ã λ1x 1 + λ2x 2 ∈ M . 0 0 H×nh 1.6. (a) - Nãn låi (b) - Nãn kh«ng låi VÝ d 1.4. C¸ tËp sau ®©y lµ ¸ nãn låi ã ®Ønh t¹i gè 0 trong Rn: 10 • 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 k v t¬ v1, v2, · · · , vk ∈ Rn. TËp cone { v1, v2, · · · , vn} := {v ∈ Rn | v = k∑ i=1 λiv i, λi ≥ 0, i = 1, · · · , k } ⊂ Rn ®­î gäi lµ nãn sinh bëi tËp { v1, v2, · · · , vk}. V t¬ vh ∈ {v1, v2, · · · , vk} gäi lµ kh«ng thiÕt yÕu (non essential) nÕu cone { v1, · · · , vh−1, vh+1, · · · , vk} = cone{v1, v2, · · · , vk}. 0 0 v1 v2 v3 v1 v2 v3 (a) (b) H×nh 1.7. (a) - V t¬ v2 lµ kh«ng thiÕt yÕu (b) - HoÆ v t¬ v2 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 D ⊆ Rn. V t¬ d 6= 0 ®­î gäi lµ ph­¬ng lïi xa (re ession dire tion) ña 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 d xuÊt ph¸t tõ mét ®iÓm bÊt kú ña D ®Òu n»m hän trong D. Râ rµng r»ng tËp D kh«ng bÞ hÆn khi vµ hØ khi 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 D vµ kÝ hiÖu lµ recD. 11 Ta nãi hai ph­¬ng d1 vµ d2 kh¸ biÖt (distin t) nÕu d1 6= αd2 víi α > 0. Ph­¬ng lïi xa d ña tËp D ®­î gäi lµ ph­¬ng ù biªn (extreme dire tion) ña 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 = λ1d 1 + λ2d 2 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 | = α} 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 ≤ α ≤ ∀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 ∀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 ∈ Rn vµ ma trËn A Êp m× n. Khi ®ã, ≥ 0 víi mäi x tho¶ m·n Ax ≥ 0 khi vµ hØ khi ∃y ∈ Rn, y ≥ 0 sao ho a = ATy. 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 | ≥ 0} khi vµ hØ khi v t¬ ph¸p tuyÕn ña siªu ph¼ng {x ∈ Rn | = 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 tÝnh ≥ bi, i = 1, 2, · · · , m. (1.1) Mçi bÊt ®¼ng thø trong (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 | ≥ bi, i = 1, 2, · · · , m } = { x | ≥ bi, i ∈ {1, 2, · · · , m} \ {k} } Ta kÝ hiÖu A lµ ma trËn Êp m×n víi ai = (a1, a2, · · · , an), i = 1, 2, · · · , n, v t¬ 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   < a i, x > = bi, i = 1, 2, · · · , m1 ≥ bi, i = m1 + 1, · · · , m ò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 a2 a3 a4a 5 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 = bi, th× ta nãi ®iÓm x 0 tho¶ m·n hÆt rµng bué i. TËp 13 I(x0) := { i ∈ {1, 2, · · · , m} = bi } lµ tËp hîp ¸ hØ sè ¸ rµng bué tho¶ m·n hÆt t¹i x0 ∈ D. Mçi ®iÓm ù biªn ña tËp låi ®a diÖn D ®­î gäi lµ mét ®Ønh ña D. TËp on låi F 6= ∅ ®­î gäi lµ mét diÖn ña D nÕu F høa mét ®iÓm trong t­¬ng ®èi ña mét ®o¹n th¼ng nµo ®ã thué 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ú x1, x2 ∈ D vµ bÊt kú sè thù λ ∈ [0, 1] ta ã f ( λx1 + (1− λ)x2) ≤ λf(x1) + (1− λ)f(x2). Ta gäi 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 ∈ D, x1 6= x2 vµ bÊt kú sè thù λ ∈ (0, 1). MiÒn x¸ ®Þnh h÷u hiÖu ña hµm f lµ dom f = {x ∈ D | f(x) < +∞} Epigraph (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 f : D −→ R∪{+∞} ã thÓ ®­î më réng thµnh hµm låi trªn toµn kh«ng gian R n b»ng ¸ h ®Æt f(x) = +∞, ∀x /∈ dom f . V× vËy ®Ó ®¬n gi¶n, ta th­êng xt f lµ hµm låi trªn Rn. MÖnh ®Ò 1.5. a) Hµm f x¸ ®Þnh trªn tËp låi kh¸ rçng D ⊆ Rn lµ hµm låi khi vµ hØ khi epi(f) lµ tËp låi. b) Hµm g x¸ ®Þnh trªn tËp låi kh¸ rçng 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 hypo(g) := {(x, α) ∈ D × R | x ∈ D, α ≤ g(x)}. (a) (b) H×nh 1.9. (a) - Epigraph ña mét hµm låi; (b) - Hypogrph ña mét hµm lâm 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 D1 ⊆ Rn, hµm låi f2 x¸ ®Þnh trªn tËp låi 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 låi trªn D2 vµ hai sè thù α > 0, β > 0. Khi ®ã, ¸ hµm αf1 + βf2 vµ 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 f x¸ ®Þnh trªn tËp låi më D ⊆ Rn. Ta ã: §Þnh lý 1.5. NÕu f lµ hµm låi x¸ ®Þnh trªn tËp låi më D ⊆ Rn th× f liªn t trªn D. §Þnh lý 1.6. NÕu f : D −→ R lµ mét hµm låi x¸ ®Þnh trªn tËp låi D ⊆ Rn th× nã ã ®¹o hµm theo mäi h­íng d ∈ R \ {0} t¹i mäi ®iÓm 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ë D th× f ã ®¹o hµm theo mäi h­íng d ∈ R \ {0} t¹i mäi ®iÓm x0 ∈ dom f vµ = f ′(x0, d) ≤ f(x0 + d)− f(x0) 15 1.2.4. Tiªu huÈn nhËn biÕt hµm låi kh¶ vi §Þnh lý 1.7. Cho f lµ hµm kh¶ vi trªn tËp låi më D ⊆ Rn. Khi ®ã hµm f lµ hµm låi trªn D khi vµ hØ khi f(y)− f(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 f lµ hµm kh¶ vi hai lÇn trªn tËp låi më D ⊆ Rn. Khi ®ã f lµ hµm låi trªn D khi vµ hØ khi ma trËn Hesse ▽2f(x) lµ nöa x¸ ®Þnh d­¬ng trªn D, tø víi ∀x ∈ D th× yT ▽2 f(x)y ≥ 0, ∀y ∈ Rn Hµm f lµ hµm låi hÆt trªn D nÕu ▽2f(x) x¸ ®Þnh d­¬ng trªn D, tø víi mäi x ∈ D, th× yT ▽2 f(x)y > 0, ∀y ∈ Rn \ {0}. HÖ qu¶ 1.3. Cho hµm toµn ph­¬ng f(x) = 1 2 + + α, trong ®ã Q lµ ma trËn vu«ng ®èi xøng Êp n, c ∈ Rn vµ α ∈ R. Khi ®ã, f lµ hµm låi trªn R n nÕu Q lµ ma trËn nöa x¸ ®Þnh d­¬ng (f lµ hµm låi hÆt trªn R n nÕu Q lµ ma trËn x¸ ®Þnh d­¬ng). VÝ d 1.5. Cho f(x1, x2) = 2x 2 1 + 3x1x2 + 4x 2 2. Ta ã: ▽f(x) =   4x1 3x2 3x1 8x2   ▽2f(x) =   4 3 3 8   V× ma trËn Hesses ▽2f(