【正文】 的步長(zhǎng)后 ， 按式 : 0x167。 若經(jīng)過(guò)多次的映射系數(shù)減半，仍不能使映射點(diǎn)優(yōu)于壞點(diǎn)，則說(shuō)明該映射方向不利，此時(shí)，應(yīng)改變映射方向，取對(duì)次壞點(diǎn) ( ) ( ) ( ): ( ) m a x{ ( ) , 1 , 2 , , , }SH SH jX F X F X j K j H? ? ?的映射。 若新的 X(q+1)點(diǎn)仍為非可行點(diǎn) ， 按上式再產(chǎn)生X(q+1)， 使它更向 X(s)靠攏 ， 最終使其成為可行點(diǎn) 。 在迭代過(guò)程中 ， 按映射系數(shù) α= ， 不一定滿足適用性和可行性 ， 如出現(xiàn)此情況 ， 將映射系數(shù)減半 ， 重新取得 X(R)， 使它滿足適用性和可行性 。 取次好點(diǎn)和好點(diǎn)連線的中點(diǎn)為 X(0)。 它來(lái)源于用于求解無(wú)約束非線性最優(yōu)化問(wèn)題的單純形法 ， 實(shí)際上是單純形法在約束問(wèn)題中的發(fā)展 。 ）點(diǎn)的函數(shù)值 ， 找出其中的最小值 f（ X(l)） 及點(diǎn) X(l)。 間接解法的基本思路是按照一定的原則構(gòu)造一個(gè)包含原目標(biāo)函數(shù)和約束條件的新目標(biāo)函數(shù)，即將原約束優(yōu)化問(wèn)題轉(zhuǎn)化成為一個(gè)或一系列的無(wú)約束優(yōu)化問(wèn)題。在這種情況下，探索結(jié)果經(jīng)常與初始點(diǎn)的選擇有關(guān)。 53 復(fù)合形法 167。 54 可行方向法 167。為了能得到全局最優(yōu)解，在探索過(guò)程中最好能改變初始點(diǎn)，有時(shí)甚至要改換幾次。再對(duì)新的目標(biāo)函數(shù)進(jìn)行無(wú)約束優(yōu)化計(jì)算，從而間接地搜索到原約束問(wèn)題的最優(yōu)解。 若 f（ X(l)） ＜ f（ X(0)） ， 則繼續(xù)沿方向 （ X(l)X(0)） 以適當(dāng)?shù)牟介L(zhǎng) a向前跨步 ， 得到新點(diǎn) X(1)， 若 f（ X(1)） 老 f（ X(l)） ， 則將新的起點(diǎn)移至 X(1) ， 重復(fù)前面過(guò)程 。 如前所述 ， 在求解無(wú)約束問(wèn)題的單純形法中 ， 不需計(jì)算目標(biāo)函數(shù)的梯度 ， 而是靠選取單純形的頂點(diǎn)并比較各頂點(diǎn)處目標(biāo)函數(shù)值的大小 ， 來(lái)尋找下一步的探索方向的 。 一般情況下，映射點(diǎn)的函數(shù)值比壞點(diǎn)的函數(shù)值要小，即 F(X(R)) F(X(H))。 一、初始復(fù)合形的構(gòu)成 復(fù)合形的頂點(diǎn) K通常取 n+1≤K≤2n個(gè)。 按照這個(gè)方法 ， 同樣使 X (q+2)、 X (q+3)、 …… X (K)都變?yōu)榭尚悬c(diǎn) ， 這 K個(gè)點(diǎn)就構(gòu)成了初始復(fù)合形 。 ()01( ) ( 0 ) ( 0 ) ( )1,1()KjjR SHX X j SHkX X X X?????? ? ??再轉(zhuǎn)回本步驟的開(kāi)始處，直到構(gòu)成新的復(fù)合形。 54 可行方向法 1 ( 0 , 1 , 2 , )k k kk k?? ? ? ?x x d 進(jìn)行迭代計(jì)算 ,迭代點(diǎn)既不超出可行域 ,又使目標(biāo)函數(shù)的值有所下降。 ? ? ? ?miXg ki ,2,1,0 ???? ? miXg ki ,2,1,0 ???非可行域 可行域以外的區(qū)域。 (2)下降 。 ()kf?? xx k d k g 1 ( x )=0 g 2 ( x )=0 g 3 ( x )=0 g 4 ( x )=0 ()kf?? x( ) / ( )k k kff? ? ? ?d P x P xP—— 投影算子，為 nXn階矩陣 1[]TT???P I G G G GG —— 起作用約束函數(shù)的梯度矩陣， nXJ階矩陣； 12[ ( ) , ( ) , , ( ) ]k k kJg g g? ? ? ?G x x x（ 2） 梯度投影法 ? 1 ( 0 , 1 , 2 , )k k kk k?? ? ? ?x x d 確定的 步長(zhǎng) 應(yīng)使新的迭代點(diǎn)為可行點(diǎn)，且目標(biāo)函數(shù)具有最大的下降量 —— 約束一維搜索。 ( )01gg? ? ? ?? ? ? ?? ? ? ?? ? ? ?xx代入 K— T條件： **1*()()0 ( 1 , 2 , , )( ) 0 ( 1 , 2 , , )0 ( 1 , 2 , , )mjjjiijjjgfinxxg j mjm?????? ?? ? ???????????????? xxx123 1 100 0 1???? ? ? ? ? ?? ? ?? ? ? ? ? ?? ? ? ? ? ?123 , 0????**6, ( ) 115f????????xx* 可行下降方向 1 可行方向 定義 設(shè)點(diǎn) ，若對(duì)于方向 d ，存在任意小正數(shù) δ 0 ，使得 則稱 d 為 X (k) 點(diǎn)的一個(gè)可行方向。簡(jiǎn)稱為 SUMT法。 1. 內(nèi)點(diǎn)法 這種方法將新目標(biāo)函數(shù)定義于可行域內(nèi) ， 序列迭代點(diǎn)在可行域內(nèi)逐步逼近約束邊界上的最優(yōu)點(diǎn) 。 無(wú)約束極值點(diǎn)為 *1*21 1 2()2( ) 0kkkrxrxr? ??? ??? ??當(dāng) 0 4r ? *0( ) [ 2 0 ] Txr ? *0( ( ) ) 4f x r ?0 ? *0( ) [ 1 . 4 2 2 0 ] Txr ? *0( ( ) ) 2 . 0 2 2f x r ?0 0 .3 6r ? *0( ) [ 1 . 1 5 6 0 ] Txr ? *0( ( ) ) 1 . 3 3 6f x r ?0 0r ? *0( ) [1 0 ] Txr ? *0( ( ) ) 1f x r ?? 1） 初始點(diǎn) x0的選取 使用內(nèi)點(diǎn)法時(shí) ， 初始點(diǎn)應(yīng)選擇一個(gè)離約束邊界較遠(yuǎn)的可行點(diǎn) 。 2. 外點(diǎn)法 ? 外點(diǎn)法是從可行域的外部構(gòu)造一個(gè)點(diǎn)序列去逼近原約束問(wèn)題的最優(yōu)解。 ( ) ( ) 2()1111( , ) ( ) [ ( ) ]()mlkkjkijir f r hgr???? ? ???x x xx0 1 2 1 0kkr r r r r ?? ? ? ? ? ? 懲罰函數(shù)法原理簡(jiǎn)單，算法易行，且分內(nèi)點(diǎn)法、外點(diǎn)法和混合法三種，各有特點(diǎn)，適用范圍廣。 該法不僅利用了目標(biāo)函數(shù)和約束函數(shù)的一階導(dǎo)數(shù)信息 ， 而且利用了目標(biāo)函數(shù)的二階導(dǎo)數(shù)信息 ， 因而其收斂速度快 、 效率高 ， 被認(rèn)為是比較好的非線性約束優(yōu)化算法 。 隨機(jī)抽樣的可信程度取決于樣本點(diǎn)數(shù)量的大小 。 這時(shí) ， 可以先使用蒙特卡洛優(yōu)化方法找到較好的初始點(diǎn) ， 然后再改用其它優(yōu)化方法 。比較各頂點(diǎn)目標(biāo)函數(shù)值的大小，去掉目標(biāo)函數(shù)值最大的頂點(diǎn) (稱最壞點(diǎn) )，通過(guò)一些操作構(gòu)造新點(diǎn)代替最壞點(diǎn)構(gòu)成新的單純形。 復(fù)合形法 初始復(fù)合形的構(gòu)成 —— 將非可行點(diǎn)調(diào)入可行域 方法特點(diǎn) （ 1） 復(fù)合形法是求解約束非線性最優(yōu)化問(wèn)題的一種直接方法 ， 僅通過(guò)選取各頂點(diǎn)并比較各點(diǎn)處函數(shù)值的大小 ， 就可尋找下一步的探索方向 。 i. （ 1） X (k) 為可行域中的一個(gè)內(nèi)點(diǎn) ? ? DX k ?? ? ? ? ? ?11 ,k k kX X d X D???? ? ? ?? ?? ? ? ?? ? 01 ?? ?kk XfXf[ ( ) ] 0k T kf??xd（ 2） X (k) 點(diǎn)是可行域中若干約束面的交點(diǎn) 設(shè) X (k) 點(diǎn)在約束面 gj (X ) = 0 ， j=1,2,…, J 若 dK 是 X (k) 點(diǎn)的一個(gè)可行下降方向，則應(yīng)有 可行： 下降： ? ?? ? 0 1 , 2 , ,kjg X j J??[ ( ) ] 0 ( 1 , 2 , , )k T kj jJ? ? ?g x d[ ( ) ] 0k T kf??xdi. （ 3） X (k) 為可行域中的一個(gè)外點(diǎn) ， X (k) 的不存在可行下降方向 。 0x1x2x0xkdkxk + 1g2( x ) =0g1( x ) =00()f?? x1 新點(diǎn)在可行域內(nèi)的情況 0x1x2x0xkdkxk + 1g2( x ) =0g1( x ) =0g3( x ) =00()f?? x2 新點(diǎn)在可行域外的情況 0x1x2x0xkxk + 1g2( x ) =0g1( x ) =0g3( x ) =00()f?? x 3 沿線性約束面的搜索 0x1x2x0xkxk + 1g2( x ) =0g1( x ) =0g3( x ) =00()f?? x1()f?? xx? 4 沿非線性約束面的搜索 ? 可行方向的產(chǎn)生方法 （ 1）優(yōu)選方向法 m in [ ( ) ]k T kf? xd[ ( ) ] 0 ( 1 , 2 , , )k T kj jJ? ? ?g x d[ ( ) ] 0k T kf??xd. 1k ?d各函數(shù)均為設(shè)計(jì)變量 dk的線性函數(shù)，因此該式為一個(gè)（線性）規(guī)劃問(wèn)題。 （ 2） 復(fù)合形法適用于僅含不等式約束的問(wèn)題 。在單純形替換算法中，從一個(gè)單純形到另一個(gè)單純形的迭代主要通過(guò)反射、擴(kuò)張、收縮和縮邊這 4個(gè)操作來(lái)實(shí)現(xiàn)。 167。 因此 ， 能否迅速地取得大量樣本點(diǎn)就成了決定蒙特卡洛優(yōu)化方法是否有效的關(guān)鍵 。 57 其它方法 （一）蒙特卡洛優(yōu)化方法（介紹） 對(duì)于約束優(yōu)化問(wèn)題，最理想的當(dāng)然是得到嚴(yán)格意義上的真正全局最優(yōu)解。因此該方法也是應(yīng)用較多的有約束優(yōu)化方法。 外點(diǎn)懲罰函數(shù)的形式為： 2211( , ) ( ) m a x[ 0 , ( ) ] [ ( ) ]mlijijr f r g r h???? ? ???x x x xr是懲罰因子 , 0 1 2r r r? ? ? ? ? 外點(diǎn)法的迭代過(guò)程在可行域之外進(jìn)行 ， 懲罰項(xiàng)的作用是迫使迭代點(diǎn)逼近約束邊界或等式約束曲面 。 一般而言 ， 太大 ， 將增加迭代次數(shù)；太小 ， 會(huì)使懲罰函數(shù)的性態(tài)變壞 ， 甚至難以收斂到極值點(diǎn) 。 m in ( )s . t . ( ) 0 ( 1 , 2 , , )jfg j m?? ???xx對(duì)于只具有不等式約束的優(yōu)化問(wèn)題： 轉(zhuǎn)化后的懲罰函數(shù)形式為： ()11( , ) ( )()mki ir f r g???? ?xx x()1( , ) ( ) l n[ ( ) ]mkiir f r g??? ? ??x x x或： rk是懲罰因子 ， 它是一個(gè)由大到小且趨近于 0的正數(shù)列 ，即 : 0 1 2 1 0kkr r r r r ?? ? ? ? ? ? 由于內(nèi)點(diǎn)法的迭代過(guò)程在可行域內(nèi)進(jìn)行 ， “ 障礙項(xiàng)” 的作用是阻止迭代點(diǎn)越出可行域 。 55 懲罰函數(shù)法 將有約束的優(yōu)化問(wèn)題轉(zhuǎn)化為無(wú)約束優(yōu)化問(wèn)題來(lái)求解 。 ii. （ 2） X (k) 為可行域中的一個(gè)邊界點(diǎn)，設(shè) X (k) 在約束面 gi (X ) = 0 上。 0x1x2xkdkxk + 1g2( x ) =0g1( x ) =0a* dk? 2） 取到約束邊界的最大步長(zhǎng) ? 從 xk點(diǎn)出發(fā)，沿 dk方向進(jìn)行一維最優(yōu)化搜索，得到的新點(diǎn) x為不可