Tài liệu Điều khiển tối ưu

Lý thuyÕt ®iÒu khiÓn n©ng cao 28 November 2016 `Phô lôc Néi dung Phô lôc Bµi 1Giíi thiÖu chung 1 §Þnh nghÜa 2 §iÒu kiÖn h¹n chÕ 3 Bµi to¸n ®iÒu khiÓn tèi u 3.1 §iÒu khiÓn tèi u tÜnh 3.2 §iÒu khiÓn tèi u ®éng Bµi 2 §iÒu khiÓn tèi u tÜnh 1 M« t¶ to¸n häc. 2 BiÓu diÔn h×nh häc. 3 Gi¶ thiÕt cho lêi gi¶i. 3.1 Bµi to¸n tèi u kh«ng cã giíi h¹n. 3.2 Bµi to¸n tèi u cã giíi h¹n. Bµi 3 Ph¬ng ph¸p kh«ng dïng ®¹o hµm riªng 1. §Æt vÊn ®Ò. 2. Ph¬ng ph¸p Gauss/Seidel. 3. C¸c ph¬ng ph¸p kh¸c. 3.1 Ph¬ng ph¸p Rosenbrock. 3.2 Ph¬ng ph¸p ®¬n h×nh. 3.3 Ph¬ng ph¸p híng t×m ngÉu nhiªn. Bµi 4 Ph¬ng ph¸p ®¹o hµm riªng 1. §Æt vÊn ®Ò 2. §¹o hµm riªng theo nghÜa hÑp. 3. Ph¬ng ph¸p h¹ nhanh nhÊt. Bµi 5 Ph¬ng ph¸p híng liªn hîp 1. §Æt vÊn ®Ò. 2. ThuËt to¸n híng liªn hîp. Bµi 6 Ph¬ng ph¸p Newton/Raphson 1. Néi dung cña ph¬ng ph¸p. 2. ThuËt to¸n Newton-Raphson. Bµi 7 Cùc tiÓu ho¸ hµm mét biÕn 1. §Æt vÊn ®Ò. 2. Ph¬ng ph¸p nh¸t c¾t vµng. 3. Ph¬ng ph¸p Fibonaci. Bµi 8 Bµi to¸n tèi u cã giíi h¹n 1. Bµi to¸n tèi u cã giíi h¹n 2. Ph¬ng ph¸p ®æi biÕn ®éc lËp 3. Ph¬ng ph¸p sö dông hµm ph¹t vµ hµm chÆn. 3.1 Hµm ph¹t. 3.2 Hµm chÆn. Tµi liÖu tham kh¶o NguyÔn Hoµi Nam Trang 1 3 3 3 4 4 5 6 6 6 7 7 8 10 10 10 13 13 13 14 15 15 16 16 17 17 19 21 21 21 24 24 25 26 28 28 28 29 29 29 31 1 Lý thuyÕt ®iÒu khiÓn n©ng cao 28 November 2016 Bµi 1 Giíi thiÖu chung 1. §Þnh nghÜa. §iÒu khiÓn tèi u lµ mét chuyªn ngµnh c¬ b¶n trong ®iÒu khiÓn tù ®éng, nã cã vai trß x¸c ®Þnh vµ t¹o lËp nh÷ng luËt ®iÒu khiÓn cho hÖ thèng ®Ó hÖ thèng ®¹t ®îc chØ tiªu vÒ tÝnh hiÖu qu¶ ®· ®îc ®Þnh tríc díi d¹ng hµm môc tiªu Q. Trong thùc tÕ tån t¹i c¸c bµi to¸n ®iÒu khiÓn tèi u nh sau: - Bµi to¸n tèi u cùc tiÓu: + X¸c ®Þnh tham sè cña m« h×nh sao cho b×nh ph¬ng sai lÖch trung b×nh gi÷a m« h×nh vµ ®èi tîng ®¹t gi¸ trÞ nhá nhÊt, vÝ dô nh huÊn luyÖn m¹ng n¬-ron, nhËn d¹ng ®èi tîng, ... + §iÒu khiÓn mét qu¸ tr×nh ®¹t chØ tiªu chÊt lîng, kü thuËt cho tríc sao cho tæn hao n¨ng lîng lµ nhá nhÊt. + T¹o ra mét s¶n phÈm ®¹t chØ tiªu chÊt lîng cho tríc nhng chi phÝ lµ nhá nhÊt. + Bµi to¸n t×m ®êng ®i ng¾n nhÊt gi÷a hai ®iÓm bÊt kú, vÝ dô nh x¸c ®Þnh quÜ ®¹o chuyÓn ®éng cña c¸nh tay r« bèt, ®êng ®i thu r¸c, thu tiÒn ®iÖn, thu tiÒn níc, ®i chµo hµng ... - Bµi to¸n tèi u cùc ®¹i. + T¹o ra s¶n phÈm víi chi phÝ cho tríc, nhng cã chÊt lîng cao nhÊt. + Bµi to¸n t×m ®êng c¨ng. - Bµi to¸n tèi u t¸c ®éng nhanh: Thêi gian x¶y ra qu¸ tr×nh lµ ng¾n nhÊt, vÝ dô nh ®iÒu khiÓn tªn löa. 2. §iÒu kiÖn h¹n chÕ. Cho hÖ thèng nhiÒu ®Çu vµo vµ nhiÒu ®Çu ra, ®îc m« t¶ bëi hÖ c¸c ph¬ng tr×nh nh sau: y = f(x,u) ®îc gäi lµ m« h×nh to¸n häc T u = (u1 u2 . . . ur) lµ c¸c ®Çu vµo x = (x1 x2 . . . xn)T lµ c¸c tr¹ng th¸i y = (y1 y2 . . . ym)T lµ c¸c ®Çu ra NguyÔn Hoµi Nam 2 Lý thuyÕt ®iÒu khiÓn n©ng cao 28 November 2016 Do bµi to¸n tèi u ®îc thùc hiÖn trªn m« h×nh hÖ thèng, cho nªn lêi gi¶i cña bµi to¸n tèi u phô thuéc vµo ®é chÝnh x¸c cña m« h×nh hÖ thèng. Nh÷ng tÝn hiÖu kh«ng thÓ m« t¶ ®îc trong c¸c ph¬ng tr×nh trªn sÏ ®îc coi lµ nhiÔu t¸c ®éng. 3. Bµi to¸n ®iÒu khiÓn tèi u. Bµi to¸n tèi u ®îc x©y dùng dùa trªn c¸c gi¶ thiÕt sau: + Cã mét m« h×nh to¸n häc. + Kh«ng cã nhiÔu t¸c ®éng. + BiÕt c¸c ®iÒu kiÖn biªn cña m« h×nh nh ®iÓm lµm viÖc, thêi gian lµm viÖc cña hÖ thèng. + BiÕt miÒn gi¸ trÞ cho phÐp cña c¸c ®Çu vµo u. + BiÕt hµm môc tiªu Q m« t¶ tÝnh hiÖu qu¶ mµ hÖ thèng cÇn ®¹t ®îc. Môc ®Ých cña ®iÒu khiÓn tèi u lµ t×m tÝn hiÖu tèi u u* ®Ó hµm môc tiªu Q ®¹t gi¸ trÞ cùc ®¹i hoÆc cùc tiÓu. Víi nh÷ng gi¶ thiÕt nµy cã rÊt nhiÒu ph¬ng ph¸p gi¶i bµi to¸n ®iÒu khiÓn tèi u kh¸c nhau. Trong ch¬ng tr×nh cña m«n häc nµy, chóng ta sÏ nghiªn cøu c¸c ph¬ng ph¸p c¬ b¶n nhÊt cña lÜnh vùc ®iÒu khiÓn tèi u, ®îc chia thµnh hai nhãm chÝnh nh sau: + §iÒu khiÓn tèi u tÜnh. + §iÒu khiÓn tèi u ®éng. 3.1. §iÒu khiÓn tèi u tÜnh. Bµi to¸n ®iÒu khiÓn tèi u tÜnh lµ bµi to¸n trong ®ã quan hÖ vµo, ra vµ biÕn tr¹ng th¸i cña m« h×nh kh«ng phô thuéc vµo thêi gian. Gi¸ trÞ ®Çu ra t¹i mét thêi ®iÓm chØ phô thuéc vµo c¸c ®Çu ®Çu vµo vµ tr¹ng th¸i t¹i thêi ®iÓm ®ã. M« h×nh hÖ thèng ®îc cho nh sau: yk = fk(u1, u2, . . .ur), víi k = 1, 2, . . ., m, viÕt gän l¹i thµnh y = f(u). Hµm môc tiªu nh sau: Q = Q(u,y). Thay y = f(u) vµo hµm môc tiªu ®îc: Q = Q(u,y) = Q(u,f(u)) = Q(u), nh vËy Q chØ phô thuéc vµo c¸c ®Çu vµo vµ ®Çu ra. 3.2. §iÒu khiÓn tèi u ®éng. Bµi to¸n ®iÒu khiÓn tèi u ®éng lµ bµi to¸n trong ®ã m« h×nh to¸n häc cã Ýt nhÊt mét ph¬ng tr×nh vi ph©n. dx i  f i ( x, u ) dt NguyÔn Hoµi Nam 3 Lý thuyÕt ®iÒu khiÓn n©ng cao 28 November 2016 Cho m« h×nh hÖ thèng nh sau: viÕt gän l¹i thµnh: x f ( x, u ) . C¸c ®Çu ra cña hÖ thèng lµ y  x i  f i ( x1 , x 2 ..., x n , u1 , u 2 ..., u r ) g ( x, u ) víi y  ( y1 , y 2 ,..., y m ) T  Hµm môc tiªu ®îc ®Þnh nghÜa nh sau: Q  f 0 ( x, u )dt , víi i  1  n , . trontg ®ã T lµ thêi 0 gian x¶y ra qu¸ tr×nh tèi u. Víi bµi to¸n ®iÒu khiÓn tèi u tÜnh, ®©y chÝnh lµ bµi to¸n cùc trÞ víi nh÷ng ®iÒu kiÖn rµng buéc. Cã nhiÒu ph¬ng ph¸p gi¶i bµi to¸n cùc trÞ, ë ®©y chóng ta chØ nghiªn cøu c¸c ph¬ng ph¸p phi tuyÕn: + C¸c ph¬ng ph¸p kh«ng dïng ®¹o hµm riªng. + C¸c ph¬ng ph¸p ®¹o hµm riªng. + Ph¬ng ph¸p híng liªn hîp. + Ph¬ng ph¸p Newton-Raphson. Víi bµi to¸n ®iÒu khiÓn tèi u ®éng, chØ nghiªn cøu c¸c ph¬ng ph¸p sau: + Ph¬ng ph¸p biÕn ph©n kinh ®iÓn. + Ph¬ng ph¸p cùc ®¹i cña Pontrjagin + Ph¬ng ph¸p qui ho¹ch ®éng cña Bellman Bµi 2 §iÒu khiÓn tèi u tÜnh 1. M« t¶ to¸n häc. M« h×nh hÖ thèng cã d¹ng nh sau: y = f(u) víi u  U u = (u1 u2 . . . ur)T c¸c ®Çu vµo y = (y1 y2 . . . ym)T c¸c ®Çu ra U lµ miÒn thÝch hîp cña c¸c biÕn ®Çu vµo, ®îc ®Þnh nghÜa nh sau:  U  u  (u1 , u 2 ..., u ñ ) T u k min  u k  u k max ; k  1  r  Hµm môc tiªu cã d¹ng nh sau: Q = Q(u,y) = Q(u,f(u)) = Q(u) Kh«ng mÊt tÝnh tæng qu¸t nÕu gi¶ thiÕt tiªu chuÈn tèi u lµ: Q(u)  min Bµi to¸n ®iÒu khiÓn tèi u tÜnh ®îc ph¸t biÓu nh sau: T×m tÝn hiÖu tèi u u*  U , sao cho Q(u*) ®¹t gi¸ trÞ nhá nhÊt. Khi ®ã, ta cã Q(u )  Q(u ) u  U (1) NÕu u* tho¶ m·n (1) víi mäi u thuéc U, th× u* ®îc gäi lµ vÐc t¬ tèi u toµn côc. * NguyÔn Hoµi Nam 4 Lý thuyÕt ®iÒu khiÓn n©ng cao 28 November 2016 NÕu u* tho¶ m·n (1) víi mäi u thuéc l©n cËn u*, th× u* ®îc gäi lµ vÐc t¬ tèi u côc bé. 2. BiÓu diÔn h×nh häc. XÐt hÖ thèng cã hai tÝn hiÖu ®Çu vµo u 1 vµ u2. Hµm môc tiªu Q chØ phô thuéc vµo u1 vµ u2, Q = Q(u1,u2). Gi¶ thiÕt hµm môc tiªu Q cã ®å thÞ nh h×nh 1. u1*  lµ ®iÓm thuéc mÆt ph¼ng (u1,u2), t¹i ®ã mÆt cong * u  2 VËy ®iÓm tèi u u* =  Q ë ®iÓm thÊp nhÊt. §iÓm A lµ ®iÓm tèi u côc bé, ®iÓm B lµ ®iÓm yªn ngùa vµ ®iÓm C lµ ®iÓm tèi u toµn côc. TËp hîp c¸c ®iÓm n»m trong mÆt ph¼ng (u 1,u2), t¹i c¸c ®iÓm ®ã hµm môc tiªu Q cã cïng gi¸ trÞ ®îc gäi lµ ®êng ®ång møc. Q B A C O u1 ®êng ®ång møc u2 H×nh 1 3. Gi¶ thiÕt cho lêi gi¶i. 3.1. Bµi to¸n tèi u kh«ng cã giíi h¹n. - NghiÖm u* cña bµi to¸n tèi u kh«ng cã giíi h¹n lµ mét ®iÓm cùc trÞ. C¸c ®iÓm cùc trÞ tho¶ m·n hÖ ph¬ng tr×nh vi ph©n Q 0 u k k  1,2..., r hay Q Q Q Q T ( , ,..., ) 0 u u1 u 2 u r NguyÔn Hoµi Nam 5 Lý thuyÕt ®iÒu khiÓn n©ng cao 28 November 2016 - T¹i mçi ®iÓm u cña mÆt cong Q tån t¹i vÐc t¬ ®¹o hµm riªng gradQ  Q , u Q u , ký hiÖu lµ vÐc t¬ ®¹o hµm riªng gradQ cã c¸c tÝnh chÊt sau: + Cã ph¬ng vu«ng gãc víi mÆt cong Q. + Cã híng chØ chiÒu t¨ng gi¸ trÞ cña c¸c ®êng ®ång møc. + Cã ®é lín thÓ hiÖn tèc ®é t¨ng hay gi¶m gi¸ trÞ cña Q. Do ®ã t¹i ®iÓm cùc trÞ cña mÆt cong Q ph¶i cã gradQ = 0 (*). HÖ ph¬ng tr×nh nµy chØ lµ ®iÒu kiÖn cÇn ®Ó t×m nghiÖm tèi u u*. §Ó gi¶i hÖ ph¬ng tr×nh (*) sÏ gÆp nh÷ng vÊn ®Ò sau: + HÖ ph¬ng tr×nh (*) lµ hÖ phi tuyÕn, dÉn ®Õn viÖc gi¶i trùc tiÕp khã thùc hiÖn ®îc. + Cã nhiÒu ®iÓm u* tho¶ m·n hÖ ph¬ng tr×nh (*) nhng kh«ng ph¶i lµ nghiÖm tèi u. Thùc tÕ, c¸c ph¬ng ph¸p gÇn ®óng ®îc sö dông nhiÒu h¬n, theo thuËt to¸n t×m nghiÖm tõng bíc. ThuËt to¸n t×m nghiÖm tõng bíc. + Bíc 1: Cho   0 bÐ tuú ý, chän u0 bÊt kú. Thùc hiÖn c¸c bíc sau víi k = 1, 2 ... + Bíc 2: X¸c ®Þnh híng t×m vµ kho¶ng c¸ch bíc t×m. + Bíc 3: T×m uk theo híng t×m vµ kho¶ng c¸ch bíc t×m. + Bíc 4: KiÓm tra ®iÒu kiÖn. NÕu || uk - uk-1 ||   chuyÓn sang bíc 5. NÕu || uk - uk-1 || >  quay vÒ bíc 2. + Bíc 5: NghiÖm tèi u gÇn ®óng lµ u* = uk víi ®é chÝnh x¸c lµ  . 3.2. Bµi to¸n tèi u cã giíi h¹n. B¶n chÊt lµ t×m nghiÖm tèi u u* gÇn ®óng cho bµi to¸n mµ u bÞ giíi h¹n bëi miÒn thÝch hîp U. ThuËt to¸n t×m nghiÖm tõng bíc vÒ c¬ b¶n còng gièng nh trªn, nhng cÇn ph¶i chó ý c¸c trêng hîp sau: NguyÔn Hoµi Nam 6 Lý thuyÕt ®iÒu khiÓn n©ng cao 28 November 2016 + NÕu nghiÖm tèi u u* kh«ng n»m trªn biªn cña U th× gradQ = 0 vÉn lµ ®iÒu kiÖn cÇn ®Ó t×m u*. + NÕu trong miÒn thÝch hîp U kh«ng tån t¹i nghiÖm u* tho¶ m·n ®iÒu kiÖn gradQ = 0, khi ®ã nghiÖm tèi u u* n»m trªn biªn cña U vµ t¹i ®iÓm u* vÐc t¬ ®¹o hµm riªng gradQ ph¶i cã híng vµo trong miÒn U. ThuËt to¸n t×m nghiÖm tèi u u* cho bµi to¸n tèi u cã giíi h¹n. + Bíc 1: Cho   0 bÐ tuú ý, chän u0 bÊt kú. Thùc hiÖn c¸c bíc sau víi k = 1, 2 ... + Bíc 2: X¸c ®Þnh híng t×m vµ kho¶ng c¸ch bíc t×m thÝch hîp ®Ó cho u k  U . + Bíc 3: T×m uk theo híng t×m vµ kho¶ng c¸ch bíc t×m. + Bíc 4: KiÓm tra ®iÒu kiÖn. NÕu || uk - uk-1 ||   chuyÓn sang bíc 5. NÕu || uk - uk-1 || >  quay vÒ bíc 2. + Bíc 5: NghiÖm tèi u gÇn ®óng lµ u* = uk víi ®é chÝnh x¸c lµ  . NguyÔn Hoµi Nam 7 Lý thuyÕt ®iÒu khiÓn n©ng cao 28 November 2016 Bµi 3 Ph¬ng ph¸p kh«ng dïng ®¹o hµm riªng 1. §Æt vÊn ®Ò. ViÖc t×m u* th«ng qua hÖ ph¬ng tr×nh vi ph©n gradQ = 0 (*) kh«ng ph¶i lµ tèt nhÊt cho mäi trêng hîp v× nh÷ng lý do sau: + HÖ ph¬ng tr×nh (*) cã thÓ rÊt phøc t¹p. + Hµm môc tiªu Q cã thÓ tån t¹i nhiÒu ®iÓm cùc trÞ t¹i ®iÓm ®ã lu«n tho¶ m·n hÖ ph¬ng tr×nh (*). + Kh«ng ph¶i hµm môc tiªu nµo còng kh¶ vi. ChÝnh v× nh÷ng lý do nµy, mµ cÇn ph¶i cã c¸c ph¬ng ph¸p t×m nghiÖm tèi u u* mµ kh«ng dïng vÐc t¬ ®¹o hµm riªng (gradient). 2. Ph¬ng ph¸p Gauss/ Seidel. Cho m« h×nh hÖ thèng y = f(u). Hµm môc tiªu ®îc ®Þnh nghÜa lµ Q = Q(u). T×m u* ®Ó cho Q ®¹t gi¸ trÞ nhá nhÊt, tøc lµ Q  min . Gi¶ sö u* nghiÖm tèi u tho¶ m·n Q  min , ký hiÖu u* = argminQ. Néi dung cña ph¬ng ph¸p Gauss/Seidel. + Híng t×m ®îc chän song song víi c¸c trôc to¹ ®é ui víi i = 1, 2, ..., r. KÝ hiÖu híng t×m ë bíc thø k lµ hk. + Kho¶ng c¸ch bíc t×m ë bíc thø k ®îc ký hiÖu lµ sk. sk ®îc x¸c ®Þnh nh sau: s k*  arg min Q (u k  s k h k ) ThuËt to¸n t×m nghiÖm cña Gauss/Seidel. + Bíc 1: Cho   0 bÐ tuú ý, chän u0 bÊt kú. Thùc hiÖn c¸c bíc sau víi k = 0, 1, 2 ... + Bíc 2: 0  0  .  - X¸c ®Þnh híng t×m hk: h k  1 , hk lµ vÐc t¬ cã r hµng, chØ cã hµng thø k + 1   .  0    cã gi¸ trÞ b»ng 1, c¸c hµng kh¸c ®Òu b»ng kh«ng. - X¸c ®Þnh kho¶ng c¸ch bíc t×m sk: sk ®îc x¸c ®Þnh sao cho hµm môc tiªu ®¹t gi¸ trÞ nhá nhÊt trªn híng t×m hk. sk* = argminQ(uk + skhk) + Bíc 3: uk+1 = uk + sk*hk NguyÔn Hoµi Nam 8 Lý thuyÕt ®iÒu khiÓn n©ng cao 28 November 2016 + Bíc 4: KiÓm tra ®iÒu kiÖn. NÕu || uk+1 - uk ||   chuyÓn sang bíc 5. NÕu || uk+1 - uk || >  quay vÒ bíc 2. + Bíc 5: NghiÖm tèi u gÇn ®óng lµ u* = uk+1 VÝ dô: Cho hµm môc tiªu Q = u12  2u 22  3 , t×m u* ®Ó cho Q  min Bíc 1: Cho   10 3 , chän 1 u0    1 k = 0. Bíc 2: Chän 1  h0    0  1 1 1  s 0  u 1  u 0  s0 h 0     s0      1 0   1  Q(u1) = (1  s 0 ) 2  2  3 , ta cã Q (u 1 )  2(1  s 0 )  0 , s 0 suy ra s0 = -1 VËy s0* = argminQ(u1) = -1 Bíc 3: 1 1 1  s 0  0 u 1  u 0  s0 h 0     s0       1 0   1  1  Bíc 4: ||u1 - u0|| = 1 >  quay vÒ bíc 2 k =1. Bíc 2: Chän 0  h0    1  0  0   0  u 2  u 1  s1 h1     s1      1  1 1  s1  Q(u2) = 0  2(1  s1 ) 2  3 , ta cã Q (u 2 )  4(1  s1 )  0 , s1 suy ra s1 = -1 VËy s1* = argminQ(u2) = -1 Bíc 3:  0  0  u2     * 1  s1  0 Bíc 4: ||u2 - u1|| = 1 >  quay vÒ bíc 2 k = 2. Bíc 2: NguyÔn Hoµi Nam 9 Lý thuyÕt ®iÒu khiÓn n©ng cao 28 November 2016 Chän 1  h2    0  0  1   s  u 3  u 2  s2 h 2     s2     2  1  0   1  Q(u3) = s 22  2.0  3 , ta cã Q (u 3 )  2s 2  0 , s 2 suy ra s2 = 0 VËy s2* = argminQ(u3) = 0 Bíc 3:  s *  0  u2   2     0  0  Bíc 4: ||u3 - u2|| = 0 <  chuyÓn sang bíc 5 Bíc 5: u* = u3 = 0  0    Sau hai vßng tÝnh ta ®· t×m ®îc nghiÖm tèi u u* = u2. u ®iÓm cña ph¬ng ph¸p lµ: nÕu hÖ thèng cã r ®Çu vµo, hµm môc tiªu cã d¹ng chÝnh ph¬ng th× nghiÖm tèi u u* sÏ ®îc t×m thÊy sau ®óng r vßng. 3. C¸c ph¬ng ph¸p kh¸c. 3.1 Ph¬ng ph¸p Rosenbrock. HÖ trôc to¹ ®é ®îc xoay sau mçi lÇn t×m ®îc nghiÖm uk tõ uk-1 sao cho mét trôc to¹ ®é cña hÖ míi trïng víi híng cña vÐc t¬ uk - uk-1. ¦u ®iÓm cña ph¬ng ph¸p lµ tèc ®é héi tô cao h¬n ph¬ng ph¸p Gauss/Seidel khi hµm môc tiªu phøc t¹p (c¸c ®êng ®ång møc kh«ng ®èi xøng, hµm môc tiªu kh«ng cã d¹ng chÝnh ph¬ng). 3.2 Ph¬ng ph¸p ®¬n h×nh. TÝnh gi¸ trÞ hµm môc tiªu t¹i r +1 ®Ønh cña mét h×nh ®a diÖn  . Trong ®ã r lµ sè biÕn ®Çu vµo cña hÖ thèng. Sau ®ã ®a diÖn  ®îc lÊy ®èi xøng víi mét c¹nh (hoÆc mÆt) cña nã, sao cho ®a diÖn míi  ' thu ®îc cã gi¸ trÞ hµm môc tiªu t¹i c¸c ®Ønh kh«ng lín h¬n c¸c gi¸ trÞ cña hµm môc tiªu t¹i c¸c ®Ønh cña  t¬ng øng. PhÐp lÊy ®èi xøng vµ tÝnh gi¸ trÞ hµm môc tiªu Q sÏ ®îc tiÕp tôc nÕu ®a diÖn míi  ' vÉn n»m trong miÒn thÝch hîp U vµ gi¸ trÞ hµm môc tiªu Q t¹i c¸c ®Ønh cña  ' kh«ng lín h¬n so víi gi¸ trÞ hµm môc tiªu Q t¹i c¸c ®Ønh cña  . NguyÔn Hoµi Nam 10 Lý thuyÕt ®iÒu khiÓn n©ng cao 28 November 2016 VÝ dô: Víi hÖ thèng cã hai ®Çu vµo r = 2, ®a diÖn  lµ mét tam gi¸c. Qu¸ tr×nh t×m nghiÖm tèi u ®îc minh ho¹ nh h×nh 2. ë ®©y ®Ó ®¬n gi¶n ta chän tam gi¸c  lµ mét tam gi¸ vu«ng c©n. ChiÒu mòi tªn lµ chiÒu t×m nghiÖm tèi u. u2 c¸c ®êng ®ång møc u1 3.3 Ph¬ng ph¸p híng t×m ngÉu nhiªn. O H×nh 2 Híng t×m ngÉu nhiªn ®îc lÊy tõ tËp ngÉu nhiªn cã ph©n bè chuÈn, ®Òu c¸c híng trong kh«ng gian. uk ®îc t×m theo híng ®· ®îc chän ngÉu nhiªn ë bíc k. NÕu Q(uk) < Q(uk-1) th× híng t×m ®ã vÉn ®îc dïng ®Ó t×m uk+1 tiÕp theo, nÕu kh«ng th× chän theo híng ngîc l¹i. NguyÔn Hoµi Nam 11 Lý thuyÕt ®iÒu khiÓn n©ng cao 28 November 2016 Bµi 4 Ph¬ng ph¸p ®¹o hµm riªng 1. §Æt vÊn ®Ò. Theo ph¬ng ph¸p nµy, híng t×m ®îc x¸c ®Þnh theo vÐc t¬ ®¹o hµm riªng cña hµm môc tiªu Q theo c¸c biÕn ®Çu vµo gradQ. VÊn ®Ò ®Æt ra lµ tÝnh vÐc t¬ ®¹o hµm riªng gradQ nh thÕ nµo? Tuú thuéc vµo hµm môc tiªu Q ®îc cho díi d¹ng c«ng thøc, b¶ng tra hay thuËt to¸n mµ ta cã ph¬ng ph¸p tÝnh gradQ kh¸c nhau. Khi hµm gradQ cho díi d¹ng c«ng thøc, tÝnh gradQ theo ph¬ng ph¸p gi¶i tÝch.  Q   u   1  Q  gradQ(u k )   u 2  :  Q     u r  lÊy ®¹o hµm riªng theo tõng biÕn ®Çu vµo u i, sau ®ã thay u  uk gi¸ trÞ u = uk vµo. NÕu hµm môc tiªu Q cho díi d¹ng b¶ng tra hoÆc thuËt to¸n th× cã c¸c ph¬ng ph¸p tÝnh gradQ nh sau: + Ph¬ng ph¸p thø nhÊt: Q u i  u  uk  1 Q( k u1 , k u 2 ,..., k u i  u i ,..., k u r )  Q( k u1 , k u 2 ,..., k u i ,..., k u r ) u i  víi i = 1, 2, ..., r. + Ph¬ng ph¸p thø hai: Q u i  u  uk  1 Q( k u1 , k u 2 ,..., k u i  u i ,..., k u r )  Q( k u1 , k u 2 ,..., k u i  u i ,..., k u r ) 2u i NguyÔn Hoµi Nam 12  Lý thuyÕt ®iÒu khiÓn n©ng cao 28 November 2016 víi i = 1, 2, ..., r. 2. Ph¬ng ph¸p ®¹o hµm riªng theo nghÜa hÑp. Híng t×m cã híng ngîc l¹i so víi híng cña vÐc t¬ ®¹o hµm riªng gradQ hk = gradQ(uk). Kho¶ng c¸ch bíc t×m tØ lÖ víi ®é lín cña gradQ(uk). Gi¸ trÞ uk+1 ®îc tÝnh theo c«ng thøc sau: uk+1 = uk - s.gradQ(uk) Kho¶ng c¸ch bíc t×m s cã ¶nh hëng rÊt lín ®Õn tèc ®é héi tô cña ph¬ng ph¸p. + NÕu s nhá, sè bíc tÝnh lín, sè lÇn tÝnh gradQ nhiÒu. + NÕu s lín, chuçi gi¸ trÞ {uk} ph©n kú. V× t¹i ®iÓm cùc trÞ gradQ(u) = 0 nªn ph¬ng ph¸p sÏ cho mét d·y {uk} héi tô ®Õn mét ®iÓm cùc trÞ. Khi Q kh«ng cã ®iÓm yªn ngùa, ®iÓm cùc trÞ ®ã cã thÓ lµ côc bé hoÆc toµn côc. Muèn t×m nghiÖm tèi u u* toµn côc, nªn ¸p dông ph¬ng ph¸p cho nhiÒu ®iÓm ban ®Çu u0 kh¸c nhau. 3. Ph¬ng ph¸p h¹ nhanh nhÊt. B¶n chÊt cña ph¬ng ph¸p lµ ph¬ng ph¸p dïng vÐc t¬ ®¹o hµm riªng cã híng t×m kh«ng cè ®Þnh theo gradQ tõ ®Çu ®Õn cuèi. Híng t×m ®îc x¸c ®Þnh nh sau: h0 = -gradQ(u0). Kho¶ng c¸ch bíc t×m ®îc x¸c ®Þnh nh sau: s 0*  arg min Q(u 0  s 0 h 0 ) suy ra u1 = u0 + s0*h0. Víi k = 1, 2, ... Chän hk sao cho hkThk-1 = 0. Chuçi gi¸ trÞ {uk*} cã tèc ®é héi tô lín khi c¸ch xa u*, cµng gÇn u* th× ®é héi tô cµng gi¶m. ThuËt to¸n h¹ nhanh nhÊt. Bíc 1: Cho   0 ®ñ bÐ, chän u0 bÊt kú. h0 = -gradQ(u0) s 0*  arg min Q (u 0  s 0 h 0 ) u1 = u0 + s0*h0 Thùc hiÖn c¸c bíc sau víi k = 1, 2, 3, ... Bíc 2: T×m híng hk sao cho: hkThk-1 = 0 NguyÔn Hoµi Nam 13 Lý thuyÕt ®iÒu khiÓn n©ng cao 28 November 2016 T×m sk* nh sau: sk* = argminQ(uk + skhk) Bíc 3: TÝnh uk+1 = uk + sk*hk. Bíc 4: KiÓm tra ®iÒu kiÖn. NÕu || uk+1 - uk ||   chuyÓn sang bíc 5. NÕu || uk+1 - uk || >  quay vÒ bíc 2. Bíc 5: KÕt thóc NghiÖm tèi u gÇn ®óng u* = uk+1 víi ®é chÝnh x¸c lµ  . . Bµi 5 Ph¬ng ph¸p híng liªn hîp 1. §Æt vÊn ®Ò. XÐt hµm môc tiªu cã d¹ng chÝnh ph¬ng: Q 1 T T u Au  b u 2 A lµ ma trËn ®¬n vÞ. u = (u1 u2 . . . ur)T b = (b1 b2 . . . br)T Theo ph¬ng ph¸p Gauss/Seidel, u* ®îc t×m thÊy sau ®óng r bíc. u* tho¶ m·n ®iÒu kiÖn Q  0  Au  b  0  u *   Ab . u NguyÔn Hoµi Nam 14 Lý thuyÕt ®iÒu khiÓn n©ng cao 28 November 2016 Theo ph¬ng ph¸p Gauss/Seidel, c¸c híng t×m song song víi c¸c trôc to¹ ®é, xuÊt ph¸t tõ ®©y ®Ó ®i tíi ph¬ng ph¸p híng liªn hîp. ý tëng cña ph¬ng ph¸p lµ: híng t×m ë vßng thø k ®îc t×m theo híng t×m ë vßng thø k - 1, sao cho: hk-1Thk = 0. XÐt hµm môc tiªu bÊy kú, trong ®ã ma trËn A kh«ng ph¶i lµ ma trËn ®¬n vÞ. Nh vËy ta ph¶i chuyÓn hÖ trôc to¹ ®é ®Ó ®a A vÒ d¹ng ma trËn ®¬n vÞ. Khi ®ã híng t×m hk sÏ chuyÓn thµnh pk. Coi A lµ mét to¸n tö tuyÕn tÝnh biÕn ®æi hÖ trôc to¹ ®é, qua phÐp biÕn ®æi nµy hk chuyÓn thµnh pk. Khi ®ã pk ph¶i cã tÝnh chÊt sau: pk-1Apk = 0 C¸c híng t×m pk víi k = 1, 2, ...,r ®îc x¸c ®Þnh nhê c«ng thøc sau: T k 1 p i Av k i 1 pi A pi pk  vk   T pi vi víi i = 1, 2, ...,r lµ mét c¬ së cña kh«ng gian R r, cã nghÜa lµ c¸c vÐc t¬ v1, v2, ... vr ®éc lËp tuyÕn tÝnh víi nhau. Híng t×m ban ®Çu p0 cã thÓ ®îc x¸c ®Þnh nhê vÐc t¬ gradQ hoÆc ®îc x¸c ®Þnh ngÉu nhiªn. Däc theo híng t×m pk, uk ®îc t×m sao cho Q(uk) ®¹t gi¸ trÞ nhá nhÊt. sk* = argminQ(uk-1 + skpk) uk = uk-1 + sk*pk 2. ThuËt to¸n híng liªn hîp. Chän c¸c vÐc t¬ c¬ së vi nh sau: vk = -gk-1 víi k = 1, 2, ..., r. Trong ®ã gk = gradQ(uk) = Auk + b. pk+1 = -gk + ekpk víi k = 0, 1, ..., r-1. Trong ®ã p0 = -g0, hÖ sè ®æi híng T ek  p k Ag k T pk A pk . Däc theo híng t×m pk+1, uk+1 ®îc t×m theo tõ uk theo nguyªn t¾c hµm Q ®¹t gi¸ trÞ nhá nhÊt. sk+1* = argminQ(uk + sk+1pk+1) uk+1 = uk + sk+1*pk+1 ThuËt to¸n. Bíc 1: Chän u0, e0 = 0. p0 = -g0 = -(Au0 + b) Thùc hiÖn c¸c bíc sau víi k = 1, 2, ..., r-1. Bíc 2: NguyÔn Hoµi Nam 15 Lý thuyÕt ®iÒu khiÓn n©ng cao 28 November 2016 gk = gradQ(uk) = Auk + b T ek  p k Ag k T pk A pk pk+1 = -gk + ekpk sk+1* = argminQ(uk + sk+1pk+1) Bíc 3: uk+1 = uk + sk+1*pk+1 Bíc 4: u* = ur Ph¬ng ph¸p híng liªn hîp cã nh÷ng tÝnh chÊt sau: + giTgj = 0 víi i  j + piTgk = 0 víi i  k + NghiÖm tèi u u* tho¶ m·n hÖ ph¬ng tr×nh Au* + b = 0. Ph¬ng ph¸p nµy thÝch hîp cho hµm môc tiªu cã d¹ng: Q 1 T T u Au  b u 2 víi A lµ ma trËn x¸c ®Þnh d¬ng. Khi hµm môc tiªu cã d¹ng bÊt kú, kh«ng gièng víi d¹ng ë trªn ta cã thÓ dung ph¬ng ph¸p nµy ®Ó t×m u*, tuy nhiªn cÇn ph¶i thay ®æi. HÖ sè ®æi hëng ®îc tÝnh tõ Q cã d¹ng tæng qu¸t: ek  gk g k 1 2 2 NghiÖm tèi u t×m ®îc kh«ng ph¶i lµ nghiÖm ®óng. NguyÔn Hoµi Nam 16 Lý thuyÕt ®iÒu khiÓn n©ng cao 28 November 2016 Bµi 6 Ph¬ng ph¸p Newton-Raphson 1. Néi dung cña ph¬ng ph¸p. Ph¬ng ph¸p t×m nghiÖm tèi u sö dông ®¹o hµm bËc nhÊt vµ bËc hai cña hµm môc tiªu nªn ph¶i gi¶ thiÕt hµm môc tiªu Q(u) kh¶ vi hai lÇn. §Ó gi¶i hÖ ph¬ng tr×nh Q (u ) 0 u (*) b»ng ph¬ng ph¸p gi¶i tÝch, tríc tiªn hÖ (*) ®îc khai triÓn thµnh chuçi Taylor t¹i uk thuéc l©n cËn nghiÖm tèi u u* vµ lµ nghiÖm cña (*) nh sau: Q(u ) Q(u )  2 Q(u ) *   (u  u k )  ...  0 * 2 uk u u u u k u tiÕp theo, bá qua c¸c ®¹o hµm bËc cao. Khi ®ã u* sÏ kh«ng ph¶i lµ nghiÖm ®óng n÷a mµ chØ lµ nghiÖm gÇn ®óng. Gäi nghiÖm gÇn ®óng nµy lµ lµ uk+1  u* , thay vµo hÖ ph¬ng tr×nh trªn ta cã: Q(u )  2 Q(u )  (u k 1  u k ) 0 2 u u k u u k   2Q  2Q ...  2  u  u 1 u r 1  §Æt H(u) =  . . . . . .  2  2Q   Q ... 2  u r u 1 u r    ,    g k  gradQ (u k ) . Suy ra uk+1 = uk - H-1(uk)gk 2. ThuËt to¸n Newton-Raphson. Bíc 1: Cho   0 ®ñ bÐ, chän u0 bÊt kú. Thùc hiÖn c¸c bíc sau víi k = 0, 1, 2, ... NguyÔn Hoµi Nam 17 Lý thuyÕt ®iÒu khiÓn n©ng cao 28 November 2016 Bíc 2: TÝnh g  gradQ (u ) . TÝnh H(uk) Bíc 3: TÝnh uk+1 = uk - H-1(uk)gk Bíc 4: KiÓm tra ®iÒu kiÖn. NÕu || uk+1 - uk ||   chuyÓn sang bíc 5. NÕu || uk+1 - uk || >  quay vÒ bíc 2. Bíc 5: KÕt thóc NghiÖm tèi u gÇn ®óng u* = uk+1. ¦u ®iÓm: k k NÕu hµm môc tiªu cã d¹ng Q 1 T T u Au  b u , 2 ph¬ng ph¸p nµy sÏ cho ®óng gi¸ trÞ u* chØ sau ®óng mét vßng tÝnh. VÝ dô: Cho hµm môc tiªu Q = 3u12 + 4u22 + u1u2 víi   10 3  Q   u  6u  u 2  g  gradQ (u )   1    1   Q  8u 2  u1   u 2    2Q  u 2 H (u )   2 1   Q  u u  2 1 H 1 (u )  1 47  8  1   2Q   u1 u 2  6 1   2 Q  1 8 u 22   1 6   Bíc 1: 0  u0    1  Bíc 2: 6u  u 2  1 g0   1    8u 2  u1   0  8 , H 1 (u 0 )  H 1 (u )  1  1  8 47   1  1 6   Bíc 3: 0  1 8 u 1  u 0  H 1 (u 0 ) g 0      1 47  1  1 1 0       6  8 0  Bíc 4: NguyÔn Hoµi Nam 18 Lý thuyÕt ®iÒu khiÓn n©ng cao 28 November 2016 ||u1 - u0|| = 1 >  quay vÒ bíc 2 k = 1. Bíc 2: 6u  u 2  0  g1   1    , H 1 (u )  H 1 (u )  1  8  1 8u 2  u1   0  0  47   1 0  1 6   Bíc 3: 0  1  8 u 2  u 1  H 1 (u 1 ) g 1      0 47   1  1 0 0       6  0  0  Bíc 4: ||u2 - u1|| = 0 <  chuyÓn sang bíc 5 Bíc 5: NghiÖm tèi u lµ u* = 0  u2    0  Bµi 7 Cùc tiÓu ho¸ hµm mét biÕn 1. §Æt vÊn ®Ò. Trong c¸c ph¬ng ph¸p ®· häc, ®Ó t×m u* ta ph¶i t×m sk* b»ng c¸ch gi¶i bµi to¸n tèi u hµm môc tiªu theo mét híng ®· chän. sk* = argminQ(uk + skhk) NguyÔn Hoµi Nam 19 Lý thuyÕt ®iÒu khiÓn n©ng cao 28 November 2016 §i t×m sk*, ta ®· sö dông ph¬ng ph¸p ®¹o hµm, tøc lµ ph¶i gi¶i ph¬ng tr×nh: Q  0. s k §Ó cã thÓ cµi ®Æt thµnh thuËt to¸n, chóng ta sÏ sö dông mét sè ph¬ng ph¸p c¬ b¶n ®Ó t×m sk* mµ kh«ng dïng ®¹o hµm. Ta ®· biÕt Q(uk + skhk) lµ hµm sè mét biÕn, chØ phôc thuéc vµo s k, cho nªn ta chØ xÐt bµi to¸n cùc tiÓu ho¸ hµm mét biÕn. - XÐt hµm sè mét biÕn Q(s), gi¶ thiÕt hµm sè Q(s) tho¶ m·n c¸c ®iÒu kiÖn sau: + Q(s) ®¬n ®iÖu gi¶m khi 0 < s < s* + Q(s) ®¬n ®iÖu t¨ng khi s* < s + s* lµ nghiÖm tèi u. + BiÕt mét ®iÓm s = s1. §å thÞ cña hµm môc tiªu Q(s) cã d¹ng nh h×nh 1. Q(s) O s* f(x) H×nh 1 s s1 ChuÈn ho¸ hµm Q(s) víi s = xs1, suy ra O x x* s s1 H×nh 2 x 1 , nh vËy 0  x  1 . Khi ®ã hµm Q(s) = Q(xs1) = f(x), f(x) cã ®é thÞ nh h×nh 2. f(x) cã mét ®iÓm cùc tiÓu duy nhÊt x* trong kho¶ng (0 1), f(1) > f(0). [0 1] ®îc gäi lµ kho¶ng nghiÖm. Nguyªn t¾c t×m nghiÖm x* lµ thu nhá kho¶ng nghiÖm qua tõng bíc. Trong kho¶ng [0 1] chän 2 gi¸ trÞ bÊt kú x1 vµ x2 sao cho: 0 < x1 < x2 < 1. XÐt c¸c trêng hîp sau: + NÕu f(x1) < f(x2), kho¶ng nghiÖm míi ®îc chän lµ [0 x2]. + NÕu f(x1)  f(x2), kho¶ng nghiÖm míi ®îc chän lµ [x1 1]. VÊn ®Ò cßn l¹i lµ chän x1 vµ x2 nh thÕ nµo ®Ó tèc ®é héi tô lµ cao nhÊt, tøc lµ tèc ®é t×m thÊy x* nhanh nhÊt. 2. Ph¬ng ph¸p nh¸t c¾t vµng. NguyÔn Hoµi Nam 20