[所有分類]第五章 約束優化方法(文件)

　

【正文】 , ) l n ( 1 )kr x x r x? ? ? ? ?x用解析法求函數的極小值 ， 運用極值條件： 1112220120krxxxxx????? ? ??????????? ??聯立求解得： 121 1 2()2( ) 0kkkrxrxr? ??? ??? ??11 1 2()2rxr ??? 時不滿足約束條件 1( ) 1 0g x x? ? ?應舍去 。 對于不同的問題 ， 都要經過多次試算 ， 才能決定一個適當 r0 3 、 懲罰因子的縮減系數 c的選取 在構造序列懲罰函數時 ， 懲罰因子 r(k)是一個逐次遞減到 0的數列 ， 相鄰兩次迭代的懲罰因子的關系為 : 式中的 c稱為懲罰因子的縮減系數 ， c為小于 1的正數 。 內點法特點 ? 內點法只適用不等式約束優化問題。從而設計者可以主動靈活地從迭代點序列中選取一個合適的點，作為工程的實用解。外點法可以用來求解含不等式和等式約束的優化問題。 初始懲罰因子 r(0) 和遞增系數 c的選取 在外點法中，初始懲罰因子 r(0) 選的是否恰當對算法的成敗和計算速度仍有著顯著的影響，因此選取時要謹慎。 在實際計算中， r(0)、 c的選取經常是通過若干次試算而選取的。為了解決這一問題，在約束邊界的可行域一側加一條容差帶。 入口 給定： X( 0), r( 0 ), c , e1? e2 K ? 0 min ? ( X , r( K )) 得最優點*KX ， )(*KXFF ? K = 0 ？ 200e??FFF ？ r( K + 1)? cr( K ) F ? F0 *)0(1 KKXX ?? K ? K +1 **KXX ? )(**KFF x? 出口 Y Y N N 外點法流程圖 例 53用外點法求解 st. 的最優解。 x1+x210=0直線是該約束優化問題的可行域，這條直線以外的整個平面為非可行域。懲罰因子 r(K) 越大，則懲罰的作用越大。隨著 r(K) 的增大，其懲罰項的懲罰作用也越大。為使罰因子 r(K) 是遞增數列，令 ， c是懲罰因子的遞增系數， c1。為使最終的迭代點落入可行域，必須設置約束容差帶。就是所求原問題的最優，*** 2121l i m)(l i mxxrrrxrr?????????內點法和外點法的簡單比較 內點法的特點： （ 1）始點必須為嚴格內點 （ 2）不適于具有等式約束的數學模型 （ 3）迭代過程中各個點均為可行設計方案 （ 4）一般收斂較慢 （ 5）初始罰因子要選擇得當 （ 6）罰因子為遞減，遞減率 c有 0c1 外點法的特點： （ 1）初始點可以任選 （ 2）對等式約束和不等式約束均可適用 （ 3）僅最優解為可行設計方案 （ 4）一般收斂較快 （ 5）初始罰因子要選擇得當 （ 6）罰因子為遞增，遞增率 c有 c1 167。對于等式約束的部分只有外懲罰函數一種形式，而對于不等式約束部分可以用內懲罰函數或外懲罰函數的形式。 對于設計點 x, 不滿足的等式約束和不等式約束部分按照外點法處理，而對于 x滿足不等式約束用內點法形式處理，其懲罰函數的形式為 初始點必須是滿足諸不等式約束條件的可行點 x(o) ,初始罰因子 r(0)、降低系數 c的選取均應參照內點法。選擇無約束優化方法進行求解，即可獲得其結果。 167。 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。 二次擴展內懲罰函數 ?????miiKK XZrXfrX1)()(),(?)( XZ i)(1Xgi ))(( 0gXg i ? ]3))((3))([(10200?? gXggXgg ii －可行域內，內點法。需要和有效的無約束優化方法結合使用。 首先寫出罰函數 。 內點形式的混合法 不等式約束部分按照內點法形式處理的混合法，其懲罰函數的形式為 初始點必須是滿足諸不等式約束條件的可行點 x(o) ,初始罰因子 r(0)、降低系數 c的選取均應參照內點法。 一、混合懲罰函數法的形式及其特點 一般約束優化問題的數學模型 由前述可知，懲罰函數是由原目標函數和懲罰項組成的。 *1x *2x *()r? *()frr 1 10 1000 ∞ 1 0 8/3 8/3 22 }2,0m a x {1)()(???? xrxxxkk）（如下：構造函數解：????????????2)2(12)1(222xxrxxx）（????????)2(21212)(xrxxdxxd k）（）（?0)2(2120)(?????xrxdxxd k）（可得：由?的最優解。 外點法特點 : 外懲罰函數法既可解不等式約束優化問題，也可解等式約束優化問題，這是其重要優點；另外一個優點是其初始點 X(0) 可以任選，即在可行域中或非可行域均可。在可行域上，懲罰函數與原目標函數值相等，即 ；在非可行域上，由于懲罰項的值恒為正，將使 。 此例可以推廣到一般具有等式約束優化的問題 )(m in XFqvXhts v ,2 ,1 0)(. ???：構成外懲罰函數如下 ?????qvvKK XhrXFrX12)()( )]([)() ,( 式中，懲罰因子 r(K)，規定為正，且是遞增數列，即 r(0)r(1)r(2)…… 。 按外點法構造懲罰函數 ?????qvvKK XhrXFrX12)()( )]([)() ,( x1 x2 X h1( X )= 0 F* o F ( X ) 等式約束優化問題 該懲罰函數是由原目標函數及懲罰項組成。 x2 x1 例 54： 用外點法求解 st. 的最優解 解 構成懲罰函數 得到約束極值點， 即： 得： 無約束極值點沿直線 從約束區域外向最優點 收斂。 終止條件 與內點法相同。嚴格地說，它是一個非可行點。 遞增系數 c的取值，一般影響不太顯著，但也不宜取得過大。在可行域的內部及邊界上有 ；在非可行域則有 ，將原目標函數加大，使等值面抬高，懲罰因子 r(K) 愈大，增加愈烈，抬高的愈顯著。 167。 ? 內點法的突出優點在于每個迭代點都是可行點，當迭代到一定的階段時，盡管迭代點還沒有達到最優點，但也可以被接受為一個較好的近似解。 4) 收斂條件 * * 1 11* 1 1[ ( ) , ] [ ( ) , ][ ( ) , ]k k k kkkr r r rrr??e???????xxx* * 12( ) ( )kkrr e???xx1?? kk crr算法步驟： 1） 選擇可行域內初始點 X(0)。 如太靠近某一約束邊界 ， 構造的懲罰函數可能由于障礙項的值很大而變得畸形 ， 使求解無約束優化問題發生困難 . 懲罰因子初值 r0的選取 懲罰因子的初值應適當 ， 否則會影響迭代計算的正常進行 。 0kr ? 懲罰因子的作用 ： 由于內點法只能在可行域內迭代 ， 而最優解很可能在可行域內靠近邊界處或就在邊界上 ， 此時盡管泛函的值很大 ， 但懲罰因子是不斷遞減的正值 ，經多次迭代 ， 接近最優解時 ， 懲罰項已是很小的正值 。 此法是求解不等式約束最優化問題的一種十分有效的方法 。 按一定的法則改變懲罰因