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

　　

【正文】 懲罰函數法原理簡單，算法易行，且分內點法、外點法和混合法三種，各有特點，適用范圍廣。 ? 課堂練習 例 55 用外點法求解下列有約束優化問題 解：懲罰函數為： 對上式求偏導 ， 得 可行域內 可行域外 無約束目標函數極小化問題的最優解系列為： 當懲罰因子漸增時 ， 由下表可看出收斂情況 。目標函數的等值線與直線 x1+x210=0的切點是該問題的最優點。當選r(0) 取過小，求解的次數將增多，收斂速度慢；若 r(0) 選的過大，則在非可行域中，罰函數比原目標函數要大得多，特別在起作用約束邊界處產生尖點，函數性態變壞，從而限制了某些約束優化方法的使用，使計算失敗。 一般的看法是 ， c值的大小在迭代過程中不起決定性作用 ， 通常的取值范圍在 ~ 。 ( ) ( ) ( ) ( )1 2 1 211( , , ) ( ) [ ( ) ] [ ( ) ]mlk k k kjkijr r f r G g r H h???? ? ???x x x x? 從而有 ()11l im [ ( ) ] 0mkikir G g????? x()21l i m [ ( ) ] 0lkjkjr H h????? x( ) ( ) ( )12l im ( , , ) ( ) 0k k kk r r f??? ??xx懲罰項必須具有以下極限性質： 求解該新目標函數的無約束極小值 ， 以期得到原問題的約束最優解 。以后各次搜索貼邊（約束面）進行。 由 X (K) 點出發，沿 S(K) 方向，取適當步長 a(K)，則 該點必須在可行域內。對于域內任一可行點來說，負梯度方向總是一種適用可行方向。 計算簡單 ， 不必求導 ， 占內存小； 隨著維數的增加 ， 效率大大下降 。 （ 5）構造新的復合形 計算映射點的函數值 F(X(R))，并與壞點的函數值 F(X(H))比較，可能存在兩種情況： 1）映射點優于壞點 : F(X(R)) F(X(H)) 在此情況，用 X(R)代替 X(H)，構成新的復合形。 復合形的產生可以： （ 1） 人工選擇初始復合形 （ 2） 隨機產生初始復合形 xi= ai +ξi (bi ai) i=1,2,….,n 用這 n個隨機數 xi作為坐標的點 X就是一個隨機點。 一 、 復合形法基本思想 : 在 n 維空間中，由 n+1≤ k≤2n 個點組成的多（邊）面體稱為復合形。對于性態不好的目標函數或可行域有狹長彎道的問題， m應取較大的值，以提高解題的成功率。 但要確保： ① 新迭代點在可行域中； ② 目標函數值的下降性 。 只要由約束條件所決定的可行域是一個凸集，目標函數是凸函數，其約束最優解就是全域最優解。 54 可行方向法 167。 其迭代過程中，每一次的新迭代點 X(K+1)都要經過可行性 和 適用性 條件的檢驗。 若兩者均滿足， X作為新的起點， 繼續按上述迭代式在 S(1)方向上取得新點。 （以下過程略） 目標函數值下降 隨機方向法 方法評價： 優點： 1 對目標函數無性態要求； 2 收斂快 （ 當 隨機方向限定數 m 足夠大時 ） ； 3不受維數影響 ， 維數愈高 ， 愈體現優點 。 計算各個頂點函數值 F(X(1))、 F(X(2))、 F(X(3))， 找出最大值 ， 記為壞點 X(H)。若新的 X(q+1)點仍為非可行點 ， 按上式再產生 X(q+1)， 使它更向 X(s)靠攏 ， 最終使其成為可行點 。 求 4個點的目標函數值： 知 . 計算除壞點外所有頂點的中心 XC： 經檢驗 XC在可行域內。 具體算法由兩部分組成： 1 確定一個適當的步長； 2 選擇 一 個可行方向。 由上述可行方向法的基本搜索過程可知，如何尋求 適用可行方向 和 適當的步長 ， 使迭代點逼近約束最優點，這是可行方向法要解決的兩個基本問題。 圖 58 適用可行方向的幾何解釋 三 .可行方向法的搜索策略 第一步迭代都是從可行的初始點 出發 ， 沿點的負梯度 方向 ， 將初始點移動 到某一個約束面 （ 只有一個起作用的約束時 ） 上 , 或約束面的交集 （ 有幾個起作用的約束時 ） 上 。 ?0 x 1 x 2 x k d k x k+1 g 2 ( x )=0 g 1 ( x )=0 a* d k a M d k x ??圖 513容許的區間 收斂條件 2[ ( ) ]k T kfs e?e? ???????x2） 設計點 xk滿足庫恩 塔克條件 1[ ( ) ( ) 00 ( 1 , 2 , , )jkkjjjjfgjJ????? ? ? ???? ????xx 1） 設計點 xk及約束允差 滿足 ? 例 :已知約束優化問題 (課堂練習 ) 試從第 k次的迭代點 Xk=[1 2]T出發，沿由 (1,1)區間隨機數 ，完成一次迭代，獲取一個新的迭代點 Xk+1，并作圖畫出目標函數的等值線、可行域和本次迭代的搜索路線。 0kr ? 懲罰因子的作用 ： 由于內點法只能在可行域內迭代 ， 而最優解很可能在可行域內靠近邊界處或就在邊界上 ， 此時盡管泛函的值很大 ， 但懲罰因子是不斷遞減的正值 ，經多次迭代 ， 接近最優解時 ， 懲罰項已是很小的正值 。 167。 終止條件 與內點法相同。在可行域上，懲罰函數與原目標函數值相等，即 ；在非可行域上，由于懲罰項的值恒為正，將使 。 內點形式的混合法 不等式約束部分按照內點法形式處理的混合法，其懲罰函數的形式為 初始點必須是滿足諸不等式約束條件的可行點 x(o) ,初始罰因子 r(0)、降低系數 c的選取均應參照內點法。 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。對于等式約束的部分只有外懲罰函數一種形式，而對于不等式約束部分可以用內懲罰函數或外懲罰函數的形式。隨著 r(K) 的增大，其懲罰項的懲罰作用也越大。為了解決這一問題，在約束邊界的可行域一側加一條容差帶。從而設計者可以主動靈活地從迭代點序列中選取一個合適的點，作為工程的實用解。 由 “ 懲罰項” 的函數形式可知 ， 當迭代點靠近某一約束邊界時， 其值趨近于 0， 而 “ 懲罰項 ” 的值陡然增加 ， 并趨近于無窮大 ， 好像在可行域的邊界上筑起了一道 “高墻 ” ， 使迭代點始終不能越出可行域 。使新點 xk+1恰好位于約束面上的步長稱為最大步長 。適用可行方向 必須是在 的情況， X(K) 點起作用的約束是 g1(X) 與 g2(X)。若取 a (K) 是在 S (K) 方向上的一個適當大小的步長，則有 ? 使點 X (K+1) 仍在可行域內，且目標函數值下降。 迭代點沿著一系列適用可行方向移動，從而得到一系列的逐步改進的可行點 X(K)，此搜索方法稱為 可行方向法。 經檢驗 4個頂點均在可行域內。 將產生的 K個隨機點進行判斷是否在可行域內，重新排列，將可行點依次排在前面，如有 q個頂點 X (1)、 X (2)、 ……X (q)是可行點 ,其它 Kq個為非可行點。如此反復迭代直到找到最優解。 第一個迭代點為： 3） 檢驗 X1點是否滿足約束條件 g(X1)=2*+=1412， X1滿足約束條件 ， 是可行點 。 進而 ， 將 X(1)作為新的始點 X (0) ← X (1) ， 再產生另一隨機方向 S(2) ， 重復以上過程 ， 得到沿 S(2)方向的最終成功點 X(2) 。 根據求解方式的不同，約束優化設計問題可分為 :直接解法、間接解法。 52 隨機方向法 167。在這種情況下，探索結果經常與初始點的選擇有關。 一 、 隨機方向的構成 在計算機語言所適用的函數庫中 ， 都有一種隨機函數 ，可以產生 0~1之間的均勻分布的隨機數 ， 利用產生的隨機數構成隨機方向 。 入口 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 iy