[所有分類]第五章約束優化方法(完整版)

　　

【正文】 射。 按照這個方法 ， 同樣使 X (q+2)、 X (q+3)、 …… X (K)都變為可行點 ， 這 K個點就構成了初始復合形 。 同樣，產生其它的隨機點 X (2)、 X (3)、 ……X (K)。 最小值 ， 記為最好點 X(L)。 例如： 設有一約束優化問題的數學模型是 該目標函數的等值線和可行域的幾何圖形如圖 53所示。 缺點： 1 對于嚴重非線性函數 ， 只能得近似解； 2 當 m不夠大時 ， 解的近似程度大； 3 對于非凸函數 ， 有可能收斂于局部解 。 入口 X← X(0)， a← a0 F0← F(X) K?1 j← 0 在 （ ?1， 1） 區間產生隨機數 yi X← X (0)+aS Y gu(X)≤ 0 F← F(X) FF0 ? 更換初始點 X (0)← X， F0← F j← 1 (x) X← X (0)+aS 給定： X(0)， a0， m， e j=0 ? Km ? a≤ e ? K← K+1 X*← X F*← F 出口 a← Y Y Y Y N N N N N ? ?T2112 1 nni iyyyy ????S圖 52隨機方向法程序框圖 三 舉例 例：用約束隨機方向法求解 解：人工選取一初始點 X0=[5， 5]T，初始點在可行域內。重復上述步驟，迭代點可沿 S (1)方向前進。 一 、 隨機方向的構成 在計算機語言所適用的函數庫中 ， 都有一種隨機函數 ，可以產生 0~1之間的均勻分布的隨機數 ， 利用產生的隨機數構成隨機方向 。可行性條件是指新迭代點X(K+1)必須在可行域內，即滿足 適用性條件是指新迭代點 X(K+1)的目標函數值較前一點是下降的，即滿足 特點： ① 在可行域內進行； ② 若可行域是凸集 ， 目標函數是定義在凸集上的凸函數 ， 則收斂到全局最優點；否則 ， 結果與初始點有關 。在這種情況下，探索結果經常與初始點的選擇有關。 55 內懲罰函數法 167。 52 隨機方向法 167。 與無約束問題不同，約束問題目標函數的最小值必須是滿足約束條件，即是由約束條件所限定的可行域內的最小值。 根據求解方式的不同，約束優化設計問題可分為 :直接解法、間接解法。 52 隨機方向法 基本思想： 隨機產生初始點 X (0) ， 隨機產生搜索方向 S(k) ， 進行搜索 。 進而 ， 將 X(1)作為新的始點 X (0) ← X (1) ， 再產生另一隨機方向 S(2) ， 重復以上過程 ， 得到沿 S(2)方向的最終成功點 X(2) 。 (3) m是預先規定在某轉折點處產生隨機方向所允許的最大數目。 第一個迭代點為： 3） 檢驗 X1點是否滿足約束條件 g(X1)=2*+=1412， X1滿足約束條件 ， 是可行點 。 53 復合形法 比較復合形各頂點目標函數值的大小 ， 去掉目標函數值最大的頂點 (稱 最壞點 )， 以壞點以外其余各點的形心為 映射中心 ， 用壞點的 映射點 替換該點 ， 構成新的復合形頂點 。如此反復迭代直到找到最優解。最終使 K個隨機點都成為可行點而構成初始復合形。 將產生的 K個隨機點進行判斷是否在可行域內，重新排列，將可行點依次排在前面，如有 q個頂點 X (1)、 X (2)、 ……X (q)是可行點 ,其它 Kq個為非可行點。若 X(R)為非可行點，將映射系數減半后再按上式改變映射點，直到 X(R)進入可行域內為止。 經檢驗 4個頂點均在可行域內。 但復合形各頂點的選擇和替換 ， 不僅要滿足目標函數值下降的要求 ， 還應當滿足所有的約束條件 。 迭代點沿著一系列適用可行方向移動，從而得到一系列的逐步改進的可行點 X(K)，此搜索方法稱為 可行方向法。 ? 初始的搜索方向取 X(0) 點的目標函數的最速下降方向，即 。若取 a (K) 是在 S (K) 方向上的一個適當大小的步長，則有 ? 使點 X (K+1) 仍在可行域內，且目標函數值下降。 圖 56 適用性條件的幾何意義 可行性條件 所謂滿足可行性條件 是指沿該方向一定有可行點存在。適用可行方向 必須是在 的情況， X(K) 點起作用的約束是 g1(X) 與 g2(X)。 0x1x2x0xkdkxk + 1g2( x ) =0g1( x ) =0g3( x ) =00()f?? x圖 59邊界反彈法 貼邊搜索法： 第一次搜索為負梯度方向，終止于邊界。使新點 xk+1恰好位于約束面上的步長稱為最大步長 。 m in ( ) ,. . ( ) 0 1 , 2 , ,( ) 0 1 , 2 , ,njkfRs t g j mh k l??????? ???xxxx 構成一個新的目標函數 ， 稱為懲罰函數 。 由 “ 懲罰項” 的函數形式可知 ， 當迭代點靠近某一約束邊界時， 其值趨近于 0， 而 “ 懲罰項 ” 的值陡然增加 ， 并趨近于無窮大 ， 好像在可行域的邊界上筑起了一道 “高墻 ” ， 使迭代點始終不能越出可行域 。 對于不同的問題 ， 都要經過多次試算 ， 才能決定一個適當 r0 3 、 懲罰因子的縮減系數 c的選取 在構造序列懲罰函數時 ， 懲罰因子 r(k)是一個逐次遞減到 0的數列 ， 相鄰兩次迭代的懲罰因子的關系為 : 式中的 c稱為懲罰因子的縮減系數 ， c為小于 1的正數 。從而設計者可以主動靈活地從迭代點序列中選取一個合適的點，作為工程的實用解。 初始懲罰因子 r(0) 和遞增系數 c的選取 在外點法中，初始懲罰因子 r(0) 選的是否恰當對算法的成敗和計算速度仍有著顯著的影響，因此選取時要謹慎。為了解決這一問題，在約束邊界的可行域一側加一條容差帶。 x1+x210=0直線是該約束優化問題的可行域，這條直線以外的整個平面為非可行域。隨著 r(K) 的增大，其懲罰項的懲罰作用也越大。為使最終的迭代點落入可行域，必須設置約束容差帶。對于等式約束的部分只有外懲罰函數一種形式，而對于不等式約束部分可以用內懲罰函數或外懲罰函數的形式。選擇無約束優化方法進行求解，即可獲得其結果。 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。需要和有效的無約束優化方法結合使用。 內點形式的混合法 不等式約束部分按照內點法形式處理的混合法，其懲罰函數的形式為 初始點必須是滿足諸不等式約束條件的可行點 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）（可得：由?的最優解。在可行域上，懲罰函數與原目標函數值相等，即 ；在非可行域上，由于懲罰項的值恒為正，將使 。 按外點法構造懲罰函數 ?????qvvKK XhrXFrX12)()( )]([)() ,( x1 x2 X h1( X )= 0 F* o F ( X ) 等式約束優化問題 該懲罰函數是由原目標函數及懲罰項組成。 終止條件 與內點法相同。 遞增系數 c的取值，一般影響不太顯著，但也不宜取得過大。 167。 4) 收斂條件 * * 1 11* 1 1[ ( ) , ] [ ( ) , ][ ( ) , ]k k k kkkr r r rrr??e???????xxx* * 12( ) ( )kkrr e???xx1?? kk crr算法步驟： 1） 選擇可行域內初始點 X(0)。 0kr ? 懲罰因子的作用 ： 由于內點法只能在可行域內迭代 ， 而最優解很可能在可行域內靠近邊界處或就在邊界上 ， 此時盡管泛函的值很大 ， 但懲罰因子是不斷遞減的正值 ，經多次迭代 ， 接近最優解時 ， 懲罰項已是很小的正值 。 按一定的法則改變懲罰因子 r