【正文】 2,1(0)(),2,1(0)(..),(m i nnpvXhmuXgtsRXXfvun????????(61) 求解上述問(wèn)題的方法稱為 約束優(yōu)化方法。 根據(jù)約束條件處理方法的不同，約束優(yōu)化方法可分為以下類型： ?直接法 ? 即直接從可行域中尋找它的約束最優(yōu)解。如： 約束坐標(biāo)輪換法、 隨機(jī)方向搜索法、復(fù)合形法 及可行方向法等等。 ? 特點(diǎn)： ? 優(yōu)點(diǎn)：算法簡(jiǎn)單、直觀性強(qiáng)、對(duì)函數(shù)無(wú)特殊要求。 ? 缺點(diǎn)：計(jì)算量大、收斂慢，因而效率低。 ? 適用場(chǎng)合：維數(shù)低、函數(shù)復(fù)雜、精度要求不高的問(wèn)題。 ?間接法 ? 即將復(fù)雜的原優(yōu)化問(wèn)題轉(zhuǎn)化為一系列簡(jiǎn)單的容易解決的子問(wèn)題，用這一系列子問(wèn)題的解去逼近原問(wèn)題的解。如： 簡(jiǎn)約梯度法、 懲罰函數(shù)法 等等。 本章主要介紹幾種常用的約束優(yōu)化方法： 隨機(jī)方向搜索法、復(fù)合形法。 圖 約束隨機(jī)方向搜索法 ?基本原理 約束隨機(jī)方向搜索法是解決小型約束最優(yōu)化問(wèn)題的一種常用的直接求解方法。其基本原理如下： 。0X一個(gè)初始點(diǎn)在約束可行域內(nèi)，選取?。)(10010SXXS???????探索點(diǎn)，求得產(chǎn)生的隨機(jī)方向以某種形式沿隨機(jī)方向以一初始定步長(zhǎng)）要求。（和可行性性檢驗(yàn)該點(diǎn)是否滿足下降0)())()(( 0???XgXfXfu；另一隨機(jī)方向進(jìn)行探索重新產(chǎn)生棄去該方向若不能同時(shí)滿足，則應(yīng) ,1S?。為方向的最終成功點(diǎn)，記成功點(diǎn)作為個(gè)時(shí)放棄該點(diǎn)，并將前一可行性要求時(shí)停止。這和點(diǎn)不能同時(shí)滿足下降性成功點(diǎn)，直到所探索的方向上繼續(xù)探索新的在新的起始點(diǎn)，即為點(diǎn)探索成功，然后以它若能同時(shí)滿足，則表示1110,XSSXXX??。成功點(diǎn)重復(fù)上述過(guò)程，得最終以原定步長(zhǎng)方向然后再產(chǎn)生另一隨機(jī)為新的起點(diǎn)而后以22101,XSXXX???。約束最優(yōu)點(diǎn)必最終逼近點(diǎn)列　　經(jīng)過(guò)若干次循環(huán)，*)},2,1({XkX k ??點(diǎn)。點(diǎn)）為所求的最優(yōu)約束圖中的以最后一個(gè)成功點(diǎn)（如方向都探索失敗時(shí)。個(gè)隨機(jī)），且沿以下（即已縮減到預(yù)定精度直至進(jìn)行探索可將步長(zhǎng)減半，以要求），可行性不能同時(shí)滿足下降性和進(jìn)行探索均失敗時(shí)（即以步長(zhǎng)個(gè)隨機(jī)方向點(diǎn)），沿中的圖　當(dāng)在某個(gè)轉(zhuǎn)折點(diǎn)（如3m a xm a x2 XNNX????????????以提高解題的成功率。的值性態(tài)不好的，應(yīng)選較大對(duì)目標(biāo)函數(shù)最大數(shù)目，一般點(diǎn)處產(chǎn)生隨機(jī)方向的為預(yù)先給定的某個(gè)轉(zhuǎn)折　說(shuō)明：, .500~50 m a xm a x?NN ),2,1( 0nibxaXiii??????　　　　　　　　　　計(jì)上下限：需要輸入設(shè)計(jì)變量的估。來(lái)選擇可行初始點(diǎn)計(jì)算機(jī)產(chǎn)生的偽隨機(jī)數(shù)，即利用，則采取隨機(jī)選擇方法當(dāng)約束條件比較復(fù)雜時(shí)初始點(diǎn)。為地確定一個(gè)，可在約束可行域內(nèi)人當(dāng)約束條件比較簡(jiǎn)單時(shí)? 約束隨機(jī)方向搜索法中的兩個(gè)關(guān)鍵問(wèn)題 　　　　　　　　全部約束條件：必須滿足必須是一個(gè)可行點(diǎn)，即初始點(diǎn)　　隨機(jī)方向搜索法的),2,1(0)(0muXgXu ???? 初始點(diǎn)的選擇 。即可調(diào)用隨機(jī)函數(shù)語(yǔ)言偽隨機(jī)數(shù)，如用區(qū)間內(nèi)服從均勻分布的為式中，　　　　　　　　　則初始點(diǎn)的各分量為)0(]1,0[),2,1()( 0R N DB A S I Crniabraxiiiiii ?????(42) 點(diǎn)。則應(yīng)重新隨機(jī)選取初始驗(yàn)，若不滿足，須經(jīng)過(guò)可行性條件的檢這樣產(chǎn)生的初始點(diǎn)還必 ? 隨機(jī)搜索方向的產(chǎn)生 。區(qū)間內(nèi)的偽隨機(jī)數(shù)將其轉(zhuǎn)換為　　　　　　　　　　可按下式后，區(qū)間內(nèi)的偽隨機(jī)數(shù)　　利用計(jì)算機(jī)產(chǎn)生),2,1(]1,1[12),2,1(]1,0[niyryniriiii???????(43) 其原因分析如下：圖 二維隨機(jī)向量 找不到最優(yōu)解。向限制而約束優(yōu)化問(wèn)題因隨機(jī)方能，致使在整個(gè)圓周上取值的可隨機(jī)向量均勻分布，從而限制了象限）內(nèi)至第整個(gè)象限（第象限內(nèi)，而不可能在分布在第只可能上的分量所構(gòu)成的向量坐標(biāo)軸、則以它們分別作為上的兩隨機(jī)數(shù)，是在、若所示的二維問(wèn)題為例，　　以圖411]1,0[2121Sxxyy? ?隨機(jī)數(shù)。個(gè)區(qū)間內(nèi)的個(gè)隨機(jī)單位向量在為形成第式中，　　　　　　　　　　用下式表示為維隨機(jī)方向單位向量可個(gè)維的情況下，　　在ＴnjyyyNjniyyyyenNnnnnii]1,1[39。,39。,39。),2,1。,2,1(39。,39。,39。)39。(139。212112??????????? ?周上?！　〉亩它c(diǎn)位于單位圓的圓　　這個(gè)隨機(jī)單位向量　　　　　則其隨機(jī)單位向量為機(jī)數(shù)，上均勻分布的兩個(gè)偽隨是在區(qū)間、　　對(duì)于二維問(wèn)題，設(shè)Ｔeyyyyeyy21222121,1]1,1[???(44) 　度為半徑的球面上；　的端點(diǎn)應(yīng)位于以單位長(zhǎng)　　對(duì)于三維問(wèn)題， e? 迭代步驟 。 ,),2,1( ,)1(m a x0Nniban ii隨機(jī)方向最大次數(shù)，產(chǎn)生步長(zhǎng)收斂精度初始步長(zhǎng)、初始變量估計(jì)的上下限給定設(shè)計(jì)變量數(shù)目????? ?，直至可行為止；點(diǎn)否則重新隨機(jī)產(chǎn)生初始有的約束條件，則轉(zhuǎn)可行性條件，若滿足所的，檢驗(yàn)得的分量產(chǎn)生初始點(diǎn)隨機(jī)產(chǎn)生初始點(diǎn)：隨機(jī)Ｔ0000201000 )。3( ,)( )2(XXxxxXabraxXniiiii?????。),(,)3( 000 ?? ??? XffXX0,1)4( ?? jjk置。 )46(),2,1(]1,1[)5(0 eXXeeniy i???????方向迭代得迭代新點(diǎn)，沿得單位隨機(jī)向量按式區(qū)間隨機(jī)產(chǎn)生隨機(jī)數(shù)在 ?)。9(),7( ),2,1(0)()6(否則轉(zhuǎn)則轉(zhuǎn)的可行性，若滿足檢驗(yàn)新點(diǎn) muXgX u ???)。9(),8(,),()7( 0 否則轉(zhuǎn)則轉(zhuǎn)若的下降性：檢驗(yàn)新點(diǎn) ffXffX ??)。6(, )(1,)8(000然后轉(zhuǎn)方向迭代得新點(diǎn)繼續(xù)沿，方向找到了成功點(diǎn)標(biāo)志置eXXeejjffXX???????)。4( )。10(,1)(0)9(否則轉(zhuǎn)轉(zhuǎn)，則置標(biāo)記轉(zhuǎn)折點(diǎn)若 ??? kkjj)。5()。11(,)10( m a x 否則轉(zhuǎn)則轉(zhuǎn)若 Nk ?繼續(xù)迭代?！≡俎D(zhuǎn)將步長(zhǎng)減半，即　可終止迭代；否則，則輸出最優(yōu)解：若),4(,),()(,)11( **???????? XfXfXX 復(fù)合形法 ? 基本原理 體）的頂點(diǎn)。作為初始復(fù)合形（多面通常取個(gè)設(shè)計(jì)點(diǎn)維空間的可行域中選取在　 )21( nknkn ????函數(shù)值總是小于壞點(diǎn)。映射點(diǎn)的目標(biāo)的映射點(diǎn)，一般來(lái)說(shuō)此為映射中心，尋找壞點(diǎn)（即形心）點(diǎn)之外其余各點(diǎn)的中心最大的點(diǎn)為壞點(diǎn)，以壞中目標(biāo)函數(shù)值目標(biāo)函數(shù)值的大小，其然后比較復(fù)合形各頂點(diǎn) ?個(gè)頂點(diǎn)的新的復(fù)合形。其余各點(diǎn)構(gòu)成與原復(fù)合形除壞點(diǎn)之外以映射點(diǎn)替換壞點(diǎn)，并k ?作為近似最優(yōu)點(diǎn)。目標(biāo)函數(shù)值最小的頂點(diǎn)輸出復(fù)合形各頂點(diǎn)中的精度要求時(shí)為止。最后心非常接近，滿足迭代到復(fù)合形的各頂點(diǎn)與形移動(dòng)和收縮，直至收縮使復(fù)合形不斷向最優(yōu)點(diǎn)，構(gòu)成新復(fù)合形，從而目標(biāo)函數(shù)值最大的壞點(diǎn)函數(shù)最小的新點(diǎn)代替在可行域中不斷以目標(biāo)　如此反復(fù)迭代計(jì)算，圖 復(fù)合形法的基本原理 。題為例，來(lái)進(jìn)一步說(shuō)明所示的二維約束優(yōu)化問(wèn)現(xiàn)以圖 (45) 。4244321作為初始復(fù)合形的頂點(diǎn)）個(gè)點(diǎn)（、在可行域內(nèi)，先選定???nkXXXX；函數(shù)值最小的好點(diǎn)函數(shù)值最大的壞點(diǎn)并作比較?？梢源_定：個(gè)點(diǎn)的目標(biāo)函數(shù)值，計(jì)算這ＬＨ31 ,4XXXX???。通常取為映射系數(shù)，一般式中，：的映射點(diǎn)為映射中心，尋找壞點(diǎn)點(diǎn)的形心和、以ＨＣＣＲＲＨＣ,1)(3432?????????? XXXXXXXXXX　的可行性和下降性檢查映射點(diǎn) Ｒ :X?完成一次迭代?！。▓D中虛線所示），點(diǎn)，并組成新的復(fù)合形替換時(shí)，則用點(diǎn)在可行域之內(nèi)，且若　ＨＲＨＲＲ )()(XXXfXfX ??件。　　再檢查是否滿足上述條，迭代，重新取新的仍按式　即半，足，則應(yīng)將映射系數(shù)減若上述兩條件得不到滿　Ｒ )54( , X??? ??　　迭代過(guò)程。組成新的進(jìn)行映射，代替則用次壞點(diǎn)仍然達(dá)不到上述要求，）時(shí)，（如：減半，當(dāng)減至很少　?。Ψ粗瑒t繼續(xù)將構(gòu)成新的復(fù)合形；替換　?。θ粢褲M足，則用ＨＨＲ 10 25XXXX????直至逼近最優(yōu)解。方向移動(dòng)和收縮，向著目標(biāo)函數(shù)值減小的　　如此，可使復(fù)合形? 初始復(fù)合形的產(chǎn)生 內(nèi)。個(gè)頂點(diǎn)都必須在可行域　初始復(fù)合形的全部 k復(fù)合形的頂點(diǎn)；個(gè)可行設(shè)計(jì)點(diǎn)作為初始決定地先按實(shí)際情況雜的優(yōu)化問(wèn)題，可人為對(duì)于維數(shù)較低、不很復(fù)　k ?產(chǎn)生初始復(fù)合形?！　☆}，則多采用隨機(jī)方法對(duì)于維數(shù)較高的優(yōu)化問(wèn)　?為可行點(diǎn)。，直到　點(diǎn)產(chǎn)生隨機(jī)，則調(diào)用隨機(jī)數(shù)，重新是否可行。若非可行點(diǎn)　　　檢驗(yàn)　　　　　　　　　的分量：區(qū)間產(chǎn)生第一個(gè)隨機(jī)點(diǎn)在　數(shù)列　服從均勻分布的隨機(jī)區(qū)間內(nèi)或調(diào)用上給定一個(gè)點(diǎn)　　　在區(qū)間個(gè)頂點(diǎn)。作為初始復(fù)合形的第一確定一個(gè)可行點(diǎn)　　下：始復(fù)合形的過(guò)程簡(jiǎn)介如　現(xiàn)將隨機(jī)方法產(chǎn)生初Ｔ11111121111),2,1,1()(],[]1,0[,],[],[)1(XXXnijabraxXbarxxxXbaXiijiijiiijinii????????為可行點(diǎn)。，直到　點(diǎn)產(chǎn)生隨機(jī)，則調(diào)用隨機(jī)數(shù)，重新是否可行。若非可行點(diǎn)　　　檢驗(yàn)　　　　　其分量為　　　　，產(chǎn)生隨機(jī)點(diǎn)數(shù)隨機(jī)點(diǎn)。繼續(xù)調(diào)用隨機(jī)產(chǎn)生其他　　　11132),2,1。,3,2()(,)1()2(XXXnikjabraxXXXrkiijiijikji?????????　　可行域，其步驟為：點(diǎn)調(diào)入先將不在可行域內(nèi)，則應(yīng)首個(gè)點(diǎn)若第頂點(diǎn)；們均作為初始復(fù)合形的依次都在可行域內(nèi)，它過(guò)程中若是否在可行域內(nèi)。檢查次檢查，構(gòu)成初始復(fù)合形。依將非可行點(diǎn)調(diào)入可行域　　1132321,,)3(???qqqkXXqXXXXXX ??(46) ??? qjjDD XqXXq 11:)1 　個(gè)點(diǎn)的點(diǎn)集中心求出已在可行域內(nèi)　　 (47) )(:)211111DqDqqDqDqXXXXXXXXX??? ?????　　點(diǎn)　　新的的中點(diǎn)，即按下式產(chǎn)生與點(diǎn)推進(jìn)，移到向?qū)Ⅻc(diǎn)　　(48) 圖 非可行點(diǎn)如何調(diào)入可行域示意圖 圖 非可行點(diǎn)如何調(diào)入可行域示意圖 成為可行點(diǎn)為止。點(diǎn)，直到產(chǎn)生新的所示圖再次推移個(gè)頂點(diǎn)；否則繼續(xù)按式作為初始復(fù)合形的第，則將所示圖已進(jìn)入可行域　　如果推移后的1111),()84(1)(??????qqqqXXbqXaX內(nèi)的初始復(fù)合形。點(diǎn)，從而構(gòu)成了可行域　　直到全部成為可行，處理，將其調(diào)入可行域不可行點(diǎn)則按上述方法　　的頂點(diǎn)；一旦遇到為初始復(fù)合形一旦遇到可行點(diǎn)，即作繼續(xù)依次檢查　　 ,)3 2 kq XX ??? 迭代步驟 ：復(fù)合形法的具體步驟為問(wèn)題，采用式約束的非線性最優(yōu)化個(gè)設(shè)計(jì)變量、僅有不等　　對(duì)于 n；　　，精度要求數(shù)目復(fù)合形頂點(diǎn)變量界限范圍給定設(shè)計(jì)變量維數(shù)　　??kniban ii ),2,1(,)1( ??　　個(gè)頂點(diǎn)產(chǎn)生初始復(fù)合形，得　　 )。,2,1()2( kjXk j ??? ?? ?)。8(),2,1)((m i n)(),2,1)((m a x)()3(　然后，轉(zhuǎn)：　?。骸　。鹤詈命c(diǎn)和最壞點(diǎn)標(biāo)函數(shù)值，找出其中的計(jì)算復(fù)合形各頂點(diǎn)的目　?。蹋蹋龋龋蹋萲jXfXfXkjXfXfXXXjj??????)(11: )4(1HjXkXXXkj