【正文】 大。因此，第二項(xiàng)使約束邊界成為探索點(diǎn)的一個(gè)不能跳出可行域之外的障礙，所以又稱為障礙項(xiàng)或障礙函數(shù)，也有稱圍墻函數(shù)的。為了取得約束面上的最優(yōu)解，在迭代過(guò)程中就要逐漸減小懲罰因子的值，直至為零，這樣才能 迫使 ()( , )kXr? 的極值點(diǎn) X*( ()kr )收斂到原函數(shù) ()fX的約束最優(yōu)點(diǎn) X*。因此，懲罰因子 ()kr 又稱為懲罰參數(shù)。 第 12 頁(yè) 共 36 頁(yè) 2． 2． 1． 2 懲罰函數(shù) 內(nèi)點(diǎn)法的迭代步驟： 1) 取初始懲罰因子 (0)r ＞ 0(例如取 (0)r ＝ 1)，允許誤差 c＞ 0； 2) 在可行域內(nèi)選取初始點(diǎn) (0)X ，令 k＝ l； 3) 從 ( 1)kX ? 點(diǎn)出發(fā)用無(wú)約束最優(yōu)化方法求解： minx??()( , )kXr? 的極值點(diǎn) X*( ()kr )； 4) 檢驗(yàn)迭代終止準(zhǔn)則：如果滿足 ( ) ( 1 ) 1* ( ) * ( )kkX r X r ???? 和 ( ) ( 1 )2( 1 )( * , ) ( * , )( * , )kkkX r X rXr?? ?? ??? ? 則停止迭代計(jì)算，并以 X*( ()kr )為原目標(biāo)函數(shù) ()fX的約束最憂解，否則轉(zhuǎn)入下一步； 5) 取 ( 1)kr ? ＝ C ()kr ， (0)X ＝ X*( ()kr )， k＝ k+1，轉(zhuǎn)向步驟 3）。 內(nèi)點(diǎn)法的計(jì)算程序框圖如圖 22所示： 第 13 頁(yè) 共 36 頁(yè) 圖 22 內(nèi)點(diǎn)法程序框圖 2． 2． 1． 3 應(yīng)注意的問(wèn)題： 1） 初始點(diǎn) (0)X 的選擇 因?yàn)閮?nèi)點(diǎn)法將懲罰函數(shù)定義于可行域內(nèi)，故要求 (0)X 嚴(yán)格滿足全部約束條件，且應(yīng)避免 (0)X 位于邊界上，即應(yīng)使 ( ) 0 ( 1 , 2 ,ug X u?? … ， m)。但當(dāng)約束條件多而復(fù)雜時(shí)，要確定一個(gè)初始可行點(diǎn)也并不十分容易。在計(jì)算中一旦取得 ( ) 0ugX? 即可以停機(jī)以節(jié)省時(shí)間，這樣得到的點(diǎn)作為初始點(diǎn)至少比原初始點(diǎn)要多滿足一個(gè)約束條件。 求初始可行點(diǎn)的另一種常用方法，可按下述迭代計(jì)算步驟進(jìn)行： I） 任取一點(diǎn) (0) nXE? ， (0) 0r ? （例如取 (0) 1r ? ），令 k=0； II） 定出下標(biāo)集 kT 與 kS ： ? ?()| ( ) 0 , 1 , 2 ,kkuT u g X u? ? ? … ， s ? ?()| ( ) 0 , 1 , 2 ,kkuS u g X u s s? ? ? ? ? … ， m III） 檢查 kS 是否為空集，若是則停止迭代，并取塞 ()kX 為初始內(nèi)點(diǎn)，否則進(jìn)行下一步； IV) 以 ()kX 為初始點(diǎn)，解問(wèn)題 第 15 頁(yè) 共 36 頁(yè) () 1m in ( ) ()kkkuuu S u Tg X r gX??????????? 受約束于 ( ) 0ugX? kuT? 令所得的這個(gè)問(wèn)題的最優(yōu)解為 ( 1)kX ? ，轉(zhuǎn)下一步； V） 令 ()kr ＝ ( 1)kr ? (C可取為 0． 1一 0． 5，常取 0． 1亦可取 0． 02)，令k＝ k+1，轉(zhuǎn)向步驟 II）。 2） 初始懲罰參數(shù) (0)r 的選擇 (0)r 的選擇對(duì) SUMT 法的計(jì)算效率影響很大，在 SUMT 法中是個(gè)比較重要的環(huán)節(jié)，選擇時(shí)需有一定的技巧和經(jīng)驗(yàn)。相反，若 (0)r 值取得太大，則 開(kāi)始幾次構(gòu)造的懲罰函數(shù) ()( , )kXr? 的無(wú)約束極值點(diǎn)就會(huì)離約束邊界很遠(yuǎn)，將使計(jì)算效率降低。 通 常 ， 當(dāng) 初 始 點(diǎn) (0)X 是 一 個(gè) 嚴(yán) 格 的 內(nèi) 點(diǎn) 時(shí) ， 則 應(yīng) 使 懲 罰 項(xiàng)( 0) ( 0)11 ()muur gX????????在新目標(biāo)函數(shù) (0)( , )Xr? 中所起的作用與原目標(biāo)函數(shù)()fX的作用相當(dāng)，于是得 ( 0 )( 0 )( 0 )1()1()mu ufXrgX??? 第 16 頁(yè) 共 36 頁(yè) 倘若約束區(qū)域是非凸的且初始點(diǎn) (0)X 亦不靠近約束邊界，則 (0)r 的取值可更小些，約為上式算得值的 0． 1—— 0． 5倍。這時(shí)應(yīng)當(dāng)加大 (0)r 值。所以在求解時(shí)，應(yīng)對(duì) (0)r 做幾次試算，以取得最合適值。 變尺度法是無(wú)約束最優(yōu)化方法在最近二十多年來(lái)發(fā)展中最有影響的研究 成果之一，它被公認(rèn)為求解無(wú)約束極值問(wèn)題最有效的算法之一，這種方法是在牛頓法的基礎(chǔ)上發(fā)展起來(lái)的。由于這一類方法的迭代形式與牛頓法類似。因?yàn)樗怯脕?lái)代替 1[ ( )]kHX? 的，而且從一次迭代到另一次迭代是變化的，故稱為變尺度矩陣。 在迭代過(guò)程中 ()kA 應(yīng)逐漸地逼近 1[ ( )]kHX? 。計(jì)算時(shí)可取 A (0)＝ I，即第 l步探索是用負(fù)梯度方向。求出 A (k+1)后，便可按式 ( ) ( ) ( )[ ] ( )k k kS A f X? ? ?的方法決定新的探索方向： ( 1 ) ( 1 ) ( 1 )()k k kS A f X? ? ?? ? ? 可以證明，這樣產(chǎn)生的方向也是共扼方向，而且對(duì)于非二次函數(shù)來(lái)說(shuō)，它比用其它方法產(chǎn)生的共輛方向共扼性更好。對(duì)于多維 (n＞ 100)問(wèn)題，由于收斂快、效果亦佳，被認(rèn)為是無(wú)約束極值問(wèn)題最好的優(yōu)化方法之一。 2． 2． 2． 2 DFP 變尺度法的計(jì)算步驟 1) 選定初始點(diǎn) (0)X 并給定計(jì)算精度 ? ，維數(shù) n； 2) 置 k＝ 0， ()kA ＝ A (0)＝ I(單位矩陣 )，計(jì)算 ( ) ( ) ( 0 )( ) ( )kkg f x f x? ? ? ?，這時(shí)探索方向?yàn)椋? ( ) ( ) ( )[ ] ( )k k kS A f X? ? ?= ()kA ()kg 3) 進(jìn)行一維探索求 ()k? ，使 ( ) ( ) ( ) ( ) ( )( ) m i n ( )k k k k kf X S f X S???? ? ? ( 1 ) ( ) ( ) ( )k k k kX X S?? ?? 4) 計(jì)算 ( 1) ( 1)()kkg f X???? ，如果 ( 1)kg? ＜ ? ，則 ( 1)kX ? 即為極小點(diǎn)，停止迭代，否則轉(zhuǎn)下一步； 5）檢查迭代次數(shù)，若 k=n（問(wèn)題的維數(shù)），則 (0)X = ( 1)nX ? ，并轉(zhuǎn)向步驟2），若 kn，則進(jìn)行下一步； 6) 構(gòu)造新的探索方向 ( 1 ) ( 1 ) ( 1 ) ( 1 ) ( 1 )()k k k k kS A f X A g? ? ? ? ?? ? ? ? ? 第 19 頁(yè) 共 36 頁(yè) 為此應(yīng)計(jì)算 ( ) ( ),kkXg?? ( ) ( 1 ) ( ) ( ),k k k kE A A E? ?? 然后令 k=k+1，轉(zhuǎn)向步驟 3)。 對(duì)于目標(biāo)函數(shù) ()fX受約束于 ( ) 0 ( 1 , 2 ,ug X u?? … ， m)的最優(yōu)化設(shè)計(jì)問(wèn)題．利用外點(diǎn)法求解時(shí)，作為無(wú)約束新目標(biāo)函數(shù)的懲罰函數(shù)，其一般表達(dá)式為 ? ?( ) ( )1( , ) ( ) m a x [ ( ) , 0 ]mkkuuX M f X M g X????? ? 式中右邊第二項(xiàng) —— 懲罰項(xiàng)； ? —— 構(gòu)造懲罰項(xiàng)函數(shù)的指數(shù)，其值將影響函數(shù) ()( , )kXM? 等值線在約束面處的性質(zhì)，一般取 ? ＝ 2； ()kM —— 懲罰因子，是大于零的一個(gè)遞增數(shù)列，即應(yīng)滿足： 0 (0)M (1)M (2)M ? ()kM ( 1)kM? ? ?? ()lim kk M?? ? ?? 在懲罰項(xiàng)中： ()( ) ( )m a x [ ( ) , 0]2 0 uuuugXg X g XgX ??? ??? 由此可見(jiàn)，當(dāng)探索點(diǎn) ()kX 在可行城內(nèi)時(shí)，懲罰項(xiàng)為零；若不在可行域內(nèi)，則不為零，且 ()kM 愈大 ，則受到的“懲罰”亦愈大。這就保證了在可行域內(nèi) ()( , )kXM? 與 ()fX是等價(jià)的。 同樣有： 0 (0)M (1)M (2)M ? ()kM ( 1)kM? ? ?? (當(dāng) ( ) 0ugX? 時(shí)） (當(dāng) ( ) 0ugX? 時(shí)） 第 21 頁(yè) 共 36 頁(yè) 在懲罰項(xiàng)中： ()( ) ( )m i n [ 0 , ( ) ]2 0 uuuugXg X g XgX ??? ??? 當(dāng)約束條件中尚包括 ( ) 0vhX? (v＝ 1， 2，?， p)的等式約束時(shí)，則在式中的右邊尚需加進(jìn)第三項(xiàng) —— 懲罰項(xiàng) ? ?2()1()pk vvM h X??。可以將懲罰函數(shù)無(wú)約束極值問(wèn)題的最優(yōu)解 ()*( )kXM 看作是以()kM 為參數(shù)的一條軌跡，當(dāng)取 0 (0)M (1)M (2)M ? ()kM ( 1)kM? ???時(shí)．點(diǎn)列 (){ * ( )}kXM 就沿著這條軌跡趨于原目標(biāo)函數(shù) ()fX的約束最優(yōu)解。 2． 2． 3． 2 懲罰函數(shù)外點(diǎn)法的迭代步驟： 1） 選擇參數(shù)： 初始懲罰因子 (0)M ＞ 0(例如取 (0)M ＝ 1)； 允許誤差 12??， ( 12??， 均應(yīng)大于零 )； 遞增系數(shù) C(C＝ ( 1)()kkMM? ， C＝ 5一 10，可取 8)； 初始點(diǎn) (0)X (可在可行域外部或內(nèi)部任意選擇，不論怎樣選擇，()( , )kXM? 的無(wú)約束極值點(diǎn)均在可行域外 )； 懲罰因子的控制量 R，當(dāng) ()kM ＞ R 時(shí)即可判別是否達(dá)到收斂精度要求。 (當(dāng) ( ) 0ugX? 時(shí) ) (當(dāng) ( ) 0ugX? 時(shí) ) 第 22 頁(yè) 共 36 頁(yè) 2） 從 ( 1)kX? 點(diǎn)出發(fā)用無(wú)約束最優(yōu)化方法求解： ()m in ( , )n kXE XM?? 得 ()*( )kXM 其中 ? ? 2( ) ( ) 1( , ) ( ) m a x[ ( ) , 0 ]mkk uuX M f X M g X? ??? ? 3） 計(jì)算 ()*( )kXM 點(diǎn)違反約束的最大量： ? ?()m a x [ * ( ) ] , 1 , 2 ,kuQ g X M u?? … ， m 4） 檢驗(yàn)迭代終止準(zhǔn)則：如果滿足 ? ?()m a x [ * ( ) ] , 1 , 2 ,kuQ g X M u?? … ， m1?? 則可以認(rèn)為 ()*( )kXM 點(diǎn)已接近約束邊界，停止迭代。 5） 檢驗(yàn) ()kM ＞ R？ 若 ()kM ＞ R，再用靠近約束面附近的條件極值點(diǎn)的移動(dòng)距離作為迭代終止準(zhǔn)則來(lái)檢驗(yàn)，即當(dāng)