【正文】 F(X(R)) 〉 F(X(H)) 這種情況由于映射點(diǎn)過遠(yuǎn)引起的 ， 減半映射系數(shù) ，若有 F(X(R)) F(X(H))， 這又轉(zhuǎn)化為第一種情況 。 ( ) ( )1( ) ( )KjLjF X F X ?????( ) ( ) 21[ ( ) ( ) ]KjLjF X F X ?????方法特點(diǎn) （ 1） 復(fù)合形法是求解約束非線性最優(yōu)化問題的一種直接方法 ， 僅通過選取各頂點(diǎn)并比較各點(diǎn)處函數(shù)值的大小 ， 就可尋找下一步的探索方向 。 （ 2） 復(fù)合形法適用于僅含不等式約束的問題 。 基本思想：這種方法的基本原理是在可行域內(nèi)選擇一個(gè)初始點(diǎn) ， 當(dāng)確定了一個(gè)可行方向 d和適當(dāng)?shù)牟介L(zhǎng)后 ， 按式 : 0x167。在不斷調(diào)整可行方向的過程中，使迭代點(diǎn)逐步逼近約束最優(yōu)點(diǎn)。 ? ?? ?0 , 1 , 2 , ,0 , 1 , 2 ,uvg X u mDXh X v p n????? ??? ? ??? 可行點(diǎn) 可行域中的點(diǎn)，即滿足所有約束條件的點(diǎn)。 若有點(diǎn) Xk 使得 則 Xk 為一個(gè)邊界點(diǎn)。 若有點(diǎn) Xk 滿足 則 Xk 為一個(gè)內(nèi)點(diǎn)。 非可行點(diǎn) 非可行域中的點(diǎn)，即不滿足所有約束條件的點(diǎn)。 等式約束始終是適時(shí)約束。 0x00()f? ??dx 根據(jù)約束函數(shù)和目標(biāo)函數(shù)的不同性狀，分別采用以下幾種策略繼續(xù)搜索。 可行方向應(yīng)滿足兩個(gè)條件 : (1)可行 。 1）可行條件 方向的可行條件是指沿該方向作微小移動(dòng)后，所得到的新點(diǎn)為可行點(diǎn)。 [ ( ) ] 0k T kf??xddkxk?g1( x ) =0g2( x ) =00()f? x? 滿足可行和下降條件，即式 : [ ( ) ] 0 ( 1 , 2 , , )k T kj jJ? ? ?g x d[ ( ) ] 0k T kf??xddkxk1()k? gx1?2?2()k? gxg1( x ) =0g2( x ) =0可行下降方向區(qū)0()f? x 位于約束曲面在點(diǎn) xk的切線和目標(biāo)函數(shù)等值線在點(diǎn) xk的切線所圍成的扇形區(qū)內(nèi)，該扇形區(qū)稱為可行下降方向區(qū) 。 ? 滿足可行、下降條件的方向位于可行下降扇形區(qū)內(nèi)，在扇形區(qū)內(nèi)尋找一個(gè)最有利的方向作為本次迭代的搜索方向。 當(dāng) xk點(diǎn)目標(biāo)函數(shù)的負(fù)梯度方向不滿足可行條件時(shí)， 可將 方向投影到約束面 （ 或約束面的交集） 上 ， 得到投影向量 dk。 1）取最優(yōu)步長(zhǎng) 從 xk點(diǎn)出發(fā)，沿 dk方向進(jìn)行一維最優(yōu)化搜索，取得最優(yōu)步長(zhǎng)，計(jì)算新點(diǎn) x的值 。 0x1x2xkdkxk + 1g2( x ) =0g1( x ) =0a* dkaMdkx 改變步長(zhǎng)，使新點(diǎn) x返回到約束面上來。 ? 約束一維搜索： 與以前所講過的一維搜索相比 ， 約束一維搜索的特點(diǎn)在于：確定初始區(qū)間時(shí) ， 對(duì)產(chǎn)生的每一個(gè)探測(cè)點(diǎn)都進(jìn)行可行性判斷 ， 如違反了某個(gè)或某些約束條件， 就必須減少步長(zhǎng)因子 ， 以使新的探測(cè)點(diǎn)落在最近的一個(gè)約束曲面上或約束曲面的一個(gè)容許的區(qū)間 內(nèi) 。 1()f?? x投影算子： 11 1 1 1 13 3 3 3[]( ) { [ ( ) ] ( ) } [ ( ) ]TTTTg g g g????? ? ? ? ? ?P I G G G GI x x x x0 6 .0 9 8? ?由上式可求得： 11 1 1 1 13 3 3 3[]( ) { [ ( ) ] ( ) } [ ( ) ]TTTTg g g g????? ? ? ? ? ?P I G G G GI x x x x? ?11 0 1 1 0 0[ 1 0] 1 00 1 0 0 0 1???? ? ? ? ? ? ? ?? ? ???? ? ? ? ? ? ? ?? ? ? ? ? ? ? ???本次迭代方向 1110()1()PfPf????????? ??xdxD為沿約束邊界 g3(x)=0的方向 ， 求最佳步長(zhǎng) 2 1 111602. 09 1 1??? ? ? ?? ? ? ?? ? ? ?? ? ? ?x x d1 2 .9 0 9? ?求得： 265???????x? （ 4）收斂判斷： 由于 122122 10 3()24 0xxfxx?? ??? ??? ? ??? ??? ? ? ????xJk={3， 5} 223511( ) 。 i. （ 1） X (k) 為可行域中的一個(gè)內(nèi)點(diǎn)， X (k) 的任何方向均為可行方向。 ? ? DX k ?? ? ? ? ? ?11 ,k k kX X d X D???? ? ? ?? ?? ? 0Tkig X d??????i. （ 3） X (k) 為可行域中的一個(gè)外點(diǎn) ， X (k) 的不存在可行方向 。 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) 的不存在可行下降方向 。 可行方向法對(duì)線性規(guī)劃問題的啟示 —— 單純形法 基本思想：通過構(gòu)造罰函數(shù)把約束問題轉(zhuǎn)化為一系列無約束最優(yōu)化問題，進(jìn)而用無約束最優(yōu)化方法去求解，這類方法稱為序列無約束最小化方法。 167。前提：一是不能破壞約束問題的約束條件 ， 二是使它歸結(jié)到原約束問題的同一最優(yōu)解上去 。 按一定的法則改變罰因子 r1 和 r2的值 ，求得一序列的無約束最優(yōu)解 ， 不斷地逼近原約束優(yōu)化問題的最優(yōu)解 。 這種方法是 1968年由美國(guó)學(xué)者 A． V．Fiacco和 G． P． Mcormick提出的 ， 把不等式約束引入數(shù)學(xué)模型中 ， 為求多維有約束非線性規(guī)劃問題開創(chuàng)了一個(gè)新局面 。 內(nèi)點(diǎn)法只能用來求解具有不等式約束的優(yōu)化問題 。 由 “ 障礙項(xiàng) ” 的函數(shù)形式可知 ， 當(dāng)?shù)c(diǎn)靠近某一約束邊界時(shí) ， 其值趨近于 0， 而 “ 障礙項(xiàng) ” 的值陡然增加 ， 并趨近于無窮大 ， 好像在可行域的邊界上筑起了一道 “ 高墻 ” ，使迭代點(diǎn)始終不能越出可行域 。 0kr ? 罰因子的作用 是：由于內(nèi)點(diǎn)法只能在可行域內(nèi)迭代 ， 而最優(yōu)解很可能在可行域內(nèi)靠近邊界處或就在邊界上 ， 此時(shí)盡管泛函的值很大 ， 但罰因子是不斷遞減的正值 ， 經(jīng)多次迭代 ， 接近最優(yōu)解時(shí) ， 懲罰項(xiàng)已是很小的正值 。 解 : 用內(nèi)點(diǎn)法求解該問題時(shí)，首先構(gòu)造內(nèi)點(diǎn)懲罰函數(shù) : 221 2 1( , ) l n ( 1 )kr x x r x? ? ? ? ?x用解析法求函數(shù)的極小值 ， 運(yùn)用極值條件： 1112220120krxxxxx????? ? ??????????? ??聯(lián)立求解得： 121 1 2()2( ) 0kkkrxrxr? ??? ??? ??11 1 2()2rxr ??? 時(shí)不滿足約束條件 1( ) 1 0g x x? ? ?應(yīng)舍去 。 如太靠近某一約束邊界 ， 構(gòu)造的懲罰函數(shù)可能由于障礙項(xiàng)的值很大而變得畸形 ， 使求解無約束優(yōu)化問題發(fā)生困難 . 2） 懲罰因子初值 r0的選取 懲罰因子的初值應(yīng)適當(dāng) ， 否則會(huì)影響迭代計(jì)算的正常進(jìn)行 。 無一般性的有效方法 。一般的看法是 ， c值的大小在迭代過程中不起決定性作用 ， 通常的取值范圍在 ~ 。 2） 選取初始罰因子 r(0)與罰因子降低系數(shù) c， 并置 K← 0； 3） 求 minφ(x(K),r(K))解出最優(yōu)點(diǎn) xK*； 4） 當(dāng) K=0轉(zhuǎn)步驟 5） ， 否則轉(zhuǎn)步驟 6） ； 5） K←K+ 1， r(K+1)←r (K)， xK+10←x K* ， 并轉(zhuǎn)步驟 3） ； 6） 按終止準(zhǔn)則判別 ， 若滿足轉(zhuǎn)步驟 7） ， 否則轉(zhuǎn)步驟 5） ； 7） 輸出最優(yōu)解 （ X*， F*） ， 停止計(jì)算 。外點(diǎn)法可以用來求解含不等式和等式約束的優(yōu)化問題。 由懲罰項(xiàng)的形式可知 ， 當(dāng)?shù)c(diǎn) x 不可行時(shí) ， 懲罰項(xiàng)的值大于 0。 *1x *2x *()r? *()frr 1 10 1000 ∞ 1 0 8/3 8/3 用內(nèi)、外點(diǎn)法不同 2212m in ( )f x x??x1s . t . ( ) 1 0gx? ? ?x內(nèi)點(diǎn)法和外點(diǎn)法的簡(jiǎn)單比較 內(nèi)點(diǎn)法的特點(diǎn)： （ 1）始點(diǎn)必須為嚴(yán)格內(nèi)點(diǎn) （ 2）不適于具有等式約束的數(shù)學(xué)模型 （ 3）迭代過程中各個(gè)點(diǎn)均為可行設(shè)計(jì)方案 （ 4）一般收斂較慢 （ 5）初始罰因子要選擇得當(dāng) （ 6）罰因子為遞減，遞減率 c有 0c1 外點(diǎn)法的特點(diǎn)： （ 1）初始點(diǎn)可以任選 （ 2）對(duì)等式約束和不等式約束均可適用 （ 3）僅最優(yōu)解為可行設(shè)計(jì)方案 （ 4）一般收斂較快 （ 5）初始罰因子要選擇得當(dāng) （ 6）罰因子為遞增，遞增率 c’有 c’1 3. 混合法 ? 混合法是用內(nèi)點(diǎn)法處理不等式約束，用外點(diǎn)法處理等式約束。 混合懲罰函數(shù)的形式為： r是懲罰因子 , 混合法具有內(nèi)點(diǎn)法的特點(diǎn) ， 迭代過程在可行域之內(nèi)進(jìn)行 ， 參數(shù)的選擇同內(nèi)點(diǎn)法 。需要和有效的無約束優(yōu)化方法結(jié)合使用。 內(nèi)點(diǎn)法 ()11( , ) ( )()mki ir f r g???? ?xx x()1( , ) ( ) l n[ ( ) ]mkiir f r g??? ? ??x x x或 外點(diǎn)法 2211( , ) ( ) m a x[ 0 , ( ) ] [ ( ) ]mlijijr f r g r h???? ? ???x x x x0 1 2r r r? ? ? ? ? 罰因子