[所有分類]第五章約束優化方法(已改無錯字)

　　

【正文】 求解該新目標函數的無約束極小值 ， 以期得到原問題的約束最優解 。 按一定的法則改變懲罰因子 r1(k) 和 r2(k)的值 ， 求得一序列的無約束最優解 ， 不斷地逼近原約束優化問題的最優解 。 根據約束形式和定義及懲罰因子的遞推方法等不同 ， 罰函數法可分為 內懲罰函數法 、 外懲罰函數法和混合懲罰函數法三種 。 這種方法是 1968年由美國學者 A． V． Fiacco和 G． P． Mcormick提出的 ， 把不等式約束引入數學模型中 ， 為求多維有約束非線性規劃問題開創了一個新局面 。 二、內懲罰函數法 (內點法 ) 這種方法將新目標函數定義于可行域內 ， 其初始點和產生的迭代點必然也在可行域內 ， 此法稱為 內懲罰函數法 。 此法是求解不等式約束最優化問題的一種十分有效的方法 。 m in ( )s . t . ( ) 0 ( 1 , 2 , , )jfg j m?? ???xx對于只具有不等式約束的優化問題： 轉化后的懲罰函數形式為： ()11( , ) ( )()mki ir f r g???? ?xx x()1( , ) ( ) l n [ ( ) ]mkiir f r g??? ? ??x x x或： 說明： ”公式中“ 0)(??xg j? rk是懲罰因子 ， 它是一個由大到小且趨近于 0的正數列 ， 即 : 0 1 2 1 0kkr r r r r ?? ? ? ? ? ? 由于內點法的迭代過程在可行域內進行 ， “ 懲罰項 ” 的作用是阻止迭代點越出可行域 。 由 “ 懲罰項” 的函數形式可知 ， 當迭代點靠近某一約束邊界時， 其值趨近于 0， 而 “ 懲罰項 ” 的值陡然增加 ， 并趨近于無窮大 ， 好像在可行域的邊界上筑起了一道 “高墻 ” ， 使迭代點始終不能越出可行域 。 顯然， 只有當懲罰因子 時 ， 才能求得在約束邊界上的最優解 。 0kr ? 懲罰因子的作用 ： 由于內點法只能在可行域內迭代 ， 而最優解很可能在可行域內靠近邊界處或就在邊界上 ， 此時盡管泛函的值很大 ， 但懲罰因子是不斷遞減的正值 ，經多次迭代 ， 接近最優解時 ， 懲罰項已是很小的正值 。 例 51 用內點法求 2212m i n ( )f x x??x1s . t . ( ) 1 0gx? ? ?x的約束最優解。 解 : 用內點法求解該問題時，首先構造內點懲罰函數 : 221 2 1( , ) l n ( 1 )kr x x r x? ? ? ? ?x用解析法求函數的極小值 ， 運用極值條件： 1112220120krxxxxx????? ? ??????????? ??聯立求解得： 121 1 2()2( ) 0kkkrxrxr? ??? ??? ??11 1 2()2rxr ??? 時不滿足約束條件 1( ) 1 0g x x? ? ?應舍去 。 無約束極值點為 *1*21 1 2()2( ) 0kkkrxrxr? ??? ??? ??當 0 4r ? *0( ) [ 2 0 ] Txr ? *0( ( ) ) 4f x r ?0 ? *0( ) [ 1 . 4 2 2 0 ] Txr ? *0( ( ) ) 2 . 0 2 2f x r ?0 0 .3 6r ? *0( ) [ 1 . 1 5 6 0 ] Txr ? *0( ( ) ) 1 . 3 3 6f x r ?0 0r ? *0( ) [1 0 ] Txr ? *0( ( ) ) 1f x r ?例 52：用內罰函數法求解下列約束優化問題 解 :構造內罰函數為 用解析法求極值 γk → 0 f(x) →1 初始點 x0的選取 使用內點法時 ， 初始點應選擇一個離約束邊界較遠的可行點 。 如太靠近某一約束邊界 ， 構造的懲罰函數可能由于障礙項的值很大而變得畸形 ， 使求解無約束優化問題發生困難 . 懲罰因子初值 r0的選取 懲罰因子的初值應適當 ， 否則會影響迭代計算的正常進行 。 一般而言 ， 太大 ， 將增加迭代次數；太小 ， 會使懲罰函數的性態變壞 ， 甚至難以收斂到極值點 。 對于不同的問題 ， 都要經過多次試算 ， 才能決定一個適當 r0 3 、 懲罰因子的縮減系數 c的選取 在構造序列懲罰函數時 ， 懲罰因子 r(k)是一個逐次遞減到 0的數列 ， 相鄰兩次迭代的懲罰因子的關系為 : 式中的 c稱為懲罰因子的縮減系數 ， c為小于 1的正數 。 一般的看法是 ， c值的大小在迭代過程中不起決定性作用 ， 通常的取值范圍在 ~ 。 4) 收斂條件 * * 1 11* 1 1[ ( ) , ] [ ( ) , ][ ( ) , ]k k k kkkr r r rrr??e???????xxx* * 12( ) ( )kkrr e???xx1?? kk crr算法步驟： 1） 選擇可行域內初始點 X(0)。 2） 選取初始罰因子 r(0)與罰因子降低系數 c， 并置 K← 0； 3） 求 minφ(x(K),r(K))解出最優點 xK*； 4） 當 K=0轉步驟 5） ， 否則轉步驟 6） ； 5） K←K+ 1， r(K+1)←r (K)， xK+10←x K* ， 并轉步驟 3） ； 6） 按終止準則判別 ， 若滿足轉步驟 7） ， 否則轉步驟 5） ； 7） 輸出最優解 （ X*， F*） ， 停止計算 。 內點法特點 ? 內點法只適用不等式約束優化問題。由于內點法是在可行域內部進行搜索，所以初始點必須是可行域內部的可行點。 ? 內點法的突出優點在于每個迭代點都是可行點，當迭代到一定的階段時，盡管迭代點還沒有達到最優點，但也可以被接受為一個較好的近似解。在機械優化設計問題中，這種近似解雖非最優點，但比初始方案已經有很大的改進，如果已能較好地符合工程設計的要求，則可以被接受作為一種最優設計。從而設計者可以主動靈活地從迭代點序列中選取一個合適的點，作為工程的實用解。 例 :用內點法求下面問題的最優解： (課堂練習 ) 并作圖畫出目標函數的等值線、可行域 。 167。 56 外懲罰函數法 外點法是從可行域的外部構造一個點序列去逼近原約束問題的最優解。外點法可以用來求解含不等式和等式約束的優化問題。 對于約束的優化問題 ： 構造外懲罰函數的常見形式如下 ???????? lj jKpu uKK XhrXgrXFrX12)(12)()( )]([)]}(,0{ m i n [)(),( 式中，懲罰因子 r(K)規定取正，與內點法不同的是在優化過程中 r(K) 取為遞增序列 即 由原目標函數與懲罰項組成。在可行域的內部及邊界上有 ；在非可行域則有 ，將原目標函數加大，使等值面抬高，懲罰因子 r(K) 愈大，增加愈烈，抬高的愈顯著。 對幾個問題的討論 初始點 的選取 由上述外點法的特點不難看出，外點法的初始點 x(0)可 以任意選取，即在可行域或非可行域上選取皆可。 初始懲罰因子 r(0) 和遞增系數 c的選取 在外點法中，初始懲罰因子 r(0) 選的是否恰當對算法的成敗和計算速度仍有著顯著的影響，因此選取時要謹慎。當選r(0) 取過小，求解的次數將增多，收斂速度慢；若 r(0) 選的過大，則在非可行域中，罰函數比原目標函數要大得多，特別在起作用約束邊界處產生尖點，函數性態變壞，從而限制了某些約束優化方法的使用，使計算失敗。 遞增系數 c的取值，一般影響不太顯著，但也不宜取得過大。通常 c=5~10。 在實際計算中， r(0)、 c的選取經常是通過若干次試算而選取的。 約束容差帶 如前所述，用外點法求解時，由于懲罰函數的無約束最優點列 是從可行域外部向約束最優點逼近的，所以最終取得的最優點一定是在邊界的非可行域一側。嚴格地說，它是一個非可行點。這對某些工程問題是不允許的。為了解決這一問題，在約束邊界的可行域一側加一條容差帶。 這就相當于將約束條件改為 式中， δu是容差量，一般取 δu =103~104。 終止條件 與內點法相同。 算法步驟及流程圖 1)在 n維空間任取初始點 x(0) ； 2)選取初始懲罰因子 r(0)，遞增系數 c，并置 K?0； 3)求 ，取得最優點 ； 4)當 K=0轉步驟（ 5），否則轉步驟（ 6）； 5)K?K+1， ， ；并轉步驟（ 3）； 6)按終止準則判別，若滿足則轉步驟（ 7），否則轉步驟（ 5）； 7)輸出最優解 ，停止計算。 入口 給定： 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 ?