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

　　

【正文】 1(k) 和 r2(k)的值 ， 求得一序列的無約束最優解 ， 不斷地逼近原約束優化問題的最優解 。 ?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，并作圖畫出目標函數的等值線、可行域和本次迭代的搜索路線。 若適時約束面是切面，每次搜索到約束面的交集時，移至另一個約束面，直至收斂到最優點。 圖 58 適用可行方向的幾何解釋 三 .可行方向法的搜索策略 第一步迭代都是從可行的初始點 出發 ， 沿點的負梯度 方向 ， 將初始點移動 到某一個約束面 （ 只有一個起作用的約束時 ） 上 , 或約束面的交集 （ 有幾個起作用的約束時 ） 上 。實際上，可行點與非可行點的標志 是該點的約束函數值。 由上述可行方向法的基本搜索過程可知，如何尋求 適用可行方向 和 適當的步長 ， 使迭代點逼近約束最優點，這是可行方向法要解決的兩個基本問題。沿 S(0)方向進行一維搜索，得最優步長為 a(0)，則第一個迭代點為 X(1) 所在的位置可能是下述三種情況之一 : ? ① 在可行域的內部； ? ② 在容許的約束邊界上； ? ③ 已越出可行域，即落入非可行域。 具體算法由兩部分組成： 1 確定一個適當的步長； 2 選擇 一 個可行方向。 （ 2）復合形法適用于僅含不等式約束的問題。 求 4個點的目標函數值： 知 . 計算除壞點外所有頂點的中心 XC： 經檢驗 XC在可行域內。 2）映射點次于壞點 : F(X(R)) ＞ F(X(H)) 這種情況由于映射點過遠引起的，減半映射系數，若有F(X(R)) F(X(H))，這又轉化為第一種情況。若新的 X(q+1)點仍為非可行點 ， 按上式再產生 X(q+1)， 使它更向 X(s)靠攏 ， 最終使其成為可行點 。這第一個點記作 X (1)。 計算各個頂點函數值 F(X(1))、 F(X(2))、 F(X(3))， 找出最大值 ， 記為壞點 X(H)。 以新的復合形頂點 , 代替原復合形中的最壞點 ， 組 成新的復合形 ， 以不斷的迭代 ， 使新復合形逐漸逼近 最優點 。 （以下過程略） 目標函數值下降 隨機方向法 方法評價： 優點： 1 對目標函數無性態要求； 2 收斂快 （ 當 隨機方向限定數 m 足夠大時 ） ； 3不受維數影響 ， 維數愈高 ， 愈體現優點 。 約束隨機方向法的搜索方向比較靈活 ， 當預定的隨機方向限定數 m足夠大時 ， 無 “ 病態 ”問題出現 ， 一般都能求出最優點 。 若兩者均滿足， X作為新的起點， 繼續按上述迭代式在 S(1)方向上取得新點。 隨機方向法 ， 是約束最優化問題的一種常用的 直接求解方法 。 其迭代過程中，每一次的新迭代點 X(K+1)都要經過可行性 和 適用性 條件的檢驗。否則，將由于所選擇的初始點的不同，而探索到不同的局部最優解上。 54 可行方向法 167。 53 復合形法 167。 只要由約束條件所決定的可行域是一個凸集，目標函數是凸函數，其約束最優解就是全域最優解。 直接法主要包括：隨機方向法 、 復合形法和可行 方向法 。 但要確保： ① 新迭代點在可行域中； ② 目標函數值的下降性 。 如此循環 ， 點列 X (1)、 X (2)、 …… 必將逼近于約束最優點 X*。對于性態不好的目標函數或可行域有狹長彎道的問題， m應取較大的值，以提高解題的成功率。 相應的目標函數值為 : 第二次迭代 以 X1為初始點，繼續使用 e1方向直到不滿足可行性和適用性條件，再重新生成隨機搜索方向 e2。 一 、 復合形法基本思想 : 在 n 維空間中，由 n+1≤ k≤2n 個點組成的多（邊）面體稱為復合形。 在可行域內任選三個初始點 X(1)、 X(2)、 X(3)， 連接這三點形成一個三角形 ， 此三角形稱為初始復合形 。 復合形的產生可以： （ 1） 人工選擇初始復合形 （ 2） 隨機產生初始復合形 xi= ai +ξi (bi ai) i=1,2,….,n 用這 n個隨機數 xi作為坐標的點 X就是一個隨機點。對 X (q+1)，將其調入可行域的步驟是： （ 1）計算 q個點集的中心 X (s)； （ 2）將第 q+1點朝著點 X (s)的方向移動，按下式產生新的 X (q+1) 即 X(q+1)= X(s)+ (X(q+1)X(s)) 這個新點 X(q+1)實際就是 X(s)與原 X(q+1)兩點連線的中點 ， 如圖 。 （ 5）構造新的復合形 計算映射點的函數值 F(X(R))，并與壞點的函數值 F(X(H))比較，可能存在兩種情況： 1）映射點優于壞點 : F(X(R)) F(X(H)) 在此情況，用 X(R)代替 X(H)，構成新的復合形。 ?1 2 3 4( ) 1 0 . 2 5 , ( ) 8 , ( ) 1 4 . 7 6 , ( ) 1 1 . 1 7f X f X f X f X? ? ? ?32,HLX X X X??0 . 5 1 0 . 9 0 . 81 ()2 2 2 . 6 2 . 23CX ? ? ? ? ? ? ? ?? ? ? ?? ? ? ? ? ? ? ?? ? ? ? ? ? ? ?2 進行迭代，獲得新的復合形。 計算簡單 ， 不必求導 ， 占內存小； 隨著維數的增加 ， 效率大大下降 。 該方法的關鍵是在迭代過程中不斷尋找既適用又可行的方向。對于域內任一可行點來說，負梯度方向總是一種適用可行方向。一般情況，這種搜索是沿著起作用約束的邊界以割線方式逐步逼近最優點。 由 X (K) 點出發，沿 S(K) 方向，取適當步長 a(K)，則 該點必須在可行域內。 x1 是既與 兩個扇形空間 x x2 的公共區域 x（即 x1）之內。以后各次搜索貼邊（約束面）進行。 圖 512新點 x為不可行點 ? 約束一維搜索： 與以前所講過的一維搜索相比 ， 約束一維搜索的特點在于：對產生的每一個探測點都進行可行性判斷， 如違反了某個或某些約束條件 ， 就必須減少步長因子 ， 以使新的探測點落在最近的一個約束曲面上或約束曲面的一個容許的區間 內 。 ( ) ( ) ( ) ( )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懲罰項必須具有以下極限性質： 求解該新目標函數的無約束極小值 ， 以期得到原問題的約束最優解 。 顯然， 只有當懲罰因子 時 ， 才能求得在約束邊界上的最優解 。 一般的看法是 ， c值的大小在迭代過程中不起決定性作用 ， 通常的取值范圍在 ~ 。 例 :用內點法求下面問題的最優解： (課堂練習 ) 并作圖畫出目標函數的等值線、可行域 。當選r(0) 取過小，求解的次數將增多，收斂速度慢；若 r(0) 選的過大，則在非可行域中，罰函數比原目標函數要大得多，特別在起作用約束邊界處產生尖點，函數性態變壞，從而限制了某些約束優化方法的使用，使計算失敗。 這就相當于將約束條件改為 式中， δu是容差量，一般取 δu =103~104。目標函數的等值線與直線 x1+x210=0的切點是該問題的最優點。 懲罰函數是由原目標函數與懲罰項組成。 ? 課堂練習 例 55 用外點法求解下列有約束優化問題 解：懲罰函數為： 對上式求偏導 ， 得 可行域內 可行域外 無約束目標函數極小化問題的最優解系列為： 當懲罰因子漸增時 ， 由下表可看出收斂情況 。按照對不等式約束處理的方法不同，混合懲罰函數法具有兩種不同的形式。 懲罰函數法原理簡單，算法易行，且分內點法、外點法和混合法三種，各有特點，適用范圍廣