【正文】 ? K ? K +1 **KXX ? )(**KFF x? 出口 Y Y N N 外點法流程圖 例 53用外點法求解 st. 的最優(yōu)解。 解：構(gòu)成懲罰函數(shù) 對于任意給定的懲罰因子 r(k)0，用解析法求 的無約束極小點，即： ),( kRX?由上面可知，當(dāng)逐漸增大 r(k)值，直至趨近于無窮大時，X*(r(k))逼近原約束問題的最優(yōu)解。 x2 x1 例 54： 用外點法求解 st. 的最優(yōu)解 解 構(gòu)成懲罰函數(shù) 得到約束極值點， 即： 得： 無約束極值點沿直線 從約束區(qū)域外向最優(yōu)點 收斂。 *x用外懲罰函數(shù)法解等式約束優(yōu)化問題 設(shè)有二維等式約束優(yōu)化問題 54)(m i n 2221 ??? xxXF010)(. 211 ???? xxXhts ： 函數(shù)圖形見圖。 x1+x210=0直線是該約束優(yōu)化問題的可行域，這條直線以外的整個平面為非可行域。目標(biāo)函數(shù)的等值線與直線 x1+x210=0的切點是該問題的最優(yōu)點。 按外點法構(gòu)造懲罰函數(shù) ?????qvvKK XhrXFrX12)()( )]([)() ,( x1 x2 X h1( X )= 0 F* o F ( X ) 等式約束優(yōu)化問題 該懲罰函數(shù)是由原目標(biāo)函數(shù)及懲罰項組成。在可行域上，懲罰項的值為零，懲罰函數(shù)的值與原目標(biāo)函數(shù)的值相同；而在非可行域上懲罰項的值恒為正，懲罰函數(shù)大于原目標(biāo)函數(shù)，即在可行域外懲罰項起到了懲罰作用。懲罰因子 r(K) 越大，則懲罰的作用越大。 隨著懲罰因子 r(K) 的增大過程，求出懲罰函數(shù)的無約束最優(yōu)點列 ，在 的過程中，則點列將趨于原約束優(yōu)化的最優(yōu)解 X*。 此例可以推廣到一般具有等式約束優(yōu)化的問題 )(m in XFqvXhts v ,2 ,1 0)(. ???：構(gòu)成外懲罰函數(shù)如下 ?????qvvKK XhrXFrX12)()( )]([)() ,( 式中，懲罰因子 r(K)，規(guī)定為正，且是遞增數(shù)列，即 r(0)r(1)r(2)…… 。懲罰項 ，在可行域上懲罰項為零；在非可行域上懲罰項恒為正。隨著 r(K) 的增大，其懲罰項的懲罰作用也越大。 懲罰函數(shù)是由原目標(biāo)函數(shù)與懲罰項組成。在可行域上，懲罰函數(shù)與原目標(biāo)函數(shù)值相等，即 ；在非可行域上，由于懲罰項的值恒為正，將使 。隨著 r(K) 的增大，致使 。為使罰因子 r(K) 是遞增數(shù)列，令 ， c是懲罰因子的遞增系數(shù)， c1。 罰函數(shù)解等式約束優(yōu)化問題的求解過程及基本參數(shù)的選擇與前述用外點法解不等式約束優(yōu)化問題相同。 外點法特點 : 外懲罰函數(shù)法既可解不等式約束優(yōu)化問題，也可解等式約束優(yōu)化問題，這是其重要優(yōu)點；另外一個優(yōu)點是其初始點 X(0) 可以任選，即在可行域中或非可行域均可。其確定是系列無約束最優(yōu)點是非可行點，對于工程設(shè)計一般是不可取的。為使最終的迭代點落入可行域，必須設(shè)置約束容差帶。 ? 課堂練習(xí) 例 55 用外點法求解下列有約束優(yōu)化問題 解：懲罰函數(shù)為： 對上式求偏導(dǎo) ， 得 可行域內(nèi) 可行域外 無約束目標(biāo)函數(shù)極小化問題的最優(yōu)解系列為： 當(dāng)懲罰因子漸增時 ， 由下表可看出收斂情況 。 *1x *2x *()r? *()frr 1 10 1000 ∞ 1 0 8/3 8/3 22 }2,0m a x {1)()(???? xrxxxkk）（如下：構(gòu)造函數(shù)解：????????????2)2(12)1(222xxrxxx）（????????)2(21212)(xrxxdxxd k）（）（?0)2(2120)(?????xrxdxxd k）（可得：由?的最優(yōu)解。，問題這就是對于固定的所以)(m i n121)(*xrrrrxxkRxkn??????解。就是所求原問題的最優(yōu)，*** 2121l i m)(l i mxxrrrxrr?????????內(nèi)點法和外點法的簡單比較 內(nèi)點法的特點： （ 1）始點必須為嚴(yán)格內(nèi)點 （ 2）不適于具有等式約束的數(shù)學(xué)模型 （ 3）迭代過程中各個點均為可行設(shè)計方案 （ 4）一般收斂較慢 （ 5）初始罰因子要選擇得當(dāng) （ 6）罰因子為遞減，遞減率 c有 0c1 外點法的特點： （ 1）初始點可以任選 （ 2）對等式約束和不等式約束均可適用 （ 3）僅最優(yōu)解為可行設(shè)計方案 （ 4）一般收斂較快 （ 5）初始罰因子要選擇得當(dāng) （ 6）罰因子為遞增，遞增率 c有 c1 167。 57 混合懲罰函數(shù)法 用懲罰函數(shù)法解含有不等式約束和等式約束的一般約束優(yōu)化問題的方法稱為混合懲罰函數(shù)法，簡稱混合法。 一、混合懲罰函數(shù)法的形式及其特點 一般約束優(yōu)化問題的數(shù)學(xué)模型 由前述可知，懲罰函數(shù)是由原目標(biāo)函數(shù)和懲罰項組成的。由于該問題的約束條件包含不等式約束與等式約束兩部分，因此，懲罰項也由對應(yīng)的兩部分組成。對于等式約束的部分只有外懲罰函數(shù)一種形式，而對于不等式約束部分可以用內(nèi)懲罰函數(shù)或外懲罰函數(shù)的形式。按照對不等式約束處理的方法不同，混合懲罰函數(shù)法具有兩種不同的形式。 內(nèi)點形式的混合法 不等式約束部分按照內(nèi)點法形式處理的混合法，其懲罰函數(shù)的形式為 初始點必須是滿足諸不等式約束條件的可行點 x(o) ,初始罰因子 r(0)、降低系數(shù) c的選取均應(yīng)參照內(nèi)點法。 外點形式的混合法 不等式約束部分按外點法處理的混合法，其懲罰函數(shù)的形式為 初始點可以在空間內(nèi)任選，初始罰因子 r(0)、遞增系數(shù) c可以參照外點法選取。 對于設(shè)計點 x, 不滿足的等式約束和不等式約束部分按照外點法處理，而對于 x滿足不等式約束用內(nèi)點法形式處理，其懲罰函數(shù)的形式為 初始點必須是滿足諸不等式約束條件的可行點 x(o) ,初始罰因子 r(0)、降低系數(shù) c的選取均應(yīng)參照內(nèi)點法。 二、算法步驟及流程圖 例 54： 設(shè)有二維一般約束優(yōu)化問題，數(shù)學(xué)模型為 解：目標(biāo)函數(shù)的等值線和約束曲線見圖所示，最優(yōu)點 X* 既要落在 [gu(X) ， u=1~4] 所包圍的區(qū)域內(nèi)，同時必須在等式約束 h(X)=0的直線上。 首先寫出罰函數(shù) 。 用內(nèi)點形式的混合法的罰函數(shù)為 用外點形式的混合法的罰函數(shù)為 將已知條件代入上式中，選取初始點 X(0)，初始罰因子r(0)，遞減系數(shù) c（對于內(nèi)點形式的混合法）或遞增系數(shù) c（對于外點形式的混合法）。選擇無約束優(yōu)化方法進行求解，即可獲得其結(jié)果。 懲罰函數(shù)法原理簡單，算法易行，且分內(nèi)點法、外點法和混合法三種，各有特點，適用范圍廣。需要和有效的無約束優(yōu)化方法結(jié)合使用。因此該方法也是應(yīng)用較多的有約束優(yōu)化方法。 167。 58擴展內(nèi)懲罰函數(shù)法（新） 這種方法的實質(zhì)是將懲罰函數(shù)在可行域內(nèi)和可行域外，分別給出定義，這樣一旦遇上非可行初始點，也能立即為極小化的程序所接受，自動為下一次求懲罰函數(shù)的極小化提供一個可行的初始點，這是一種比較成功的替換方法。 二次擴展內(nèi)懲罰函數(shù) ?????miiKK XZrXfrX1)()(),(?)( XZ i)(1Xgi ))(( 0gXg i ? ]3))((3))([(10200?? gXggXgg ii －可行域內(nèi)，內(nèi)點法。 ))(( 0gXg i ?G0－轉(zhuǎn)換點，一般取 約束裕量，將約束面放寬 采用一維搜索 H1－懲罰函數(shù) 在 Xk點的二階導(dǎo)數(shù)逆矩陣。 KKKK SXX a??? 1 )(1 KXHS ???? ? ),(KrZ?g0 F(X) X g(X)=X1 01 0 ??? gX g0 F(X) X g(X)=X1 01 0 ??? gX