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