[所有分類]第五章 約束優化方法-預覽頁

　

【正文】 i=1,2,….,n 用這 n個隨機數 xi作為坐標的點 X就是一個隨機點。利用該隨機數可產生變量 xi在給定界 限 aixibi內的隨機數 因每產生一個隨機點，需要 n個隨機數，因此，產生 k個隨機點總共需要連續發生 K n個隨機數。對 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)兩點連線的中點 ， 如圖 。選出好點 X(L) 和壞點 X(H)。 （ 5）構造新的復合形 計算映射點的函數值 F(X(R))，并與壞點的函數值 F(X(H))比較，可能存在兩種情況： 1）映射點優于壞點 : F(X(R)) F(X(H)) 在此情況，用 X(R)代替 X(H)，構成新的復合形。 (6)判斷終止條件 1) 各頂點與好點函數值之差的均方根值小于誤差限，即 1( ) ( ) 2 211{ [ ( ) ( ) ] }K jLjF X F XK e????2）各頂點與好點的函數值之差的平方和小于誤差限，即 3）各頂點與好點函數值差的絕對值之和小于誤差限，即 如果不滿足終止迭代條件，則返回步驟 2繼續進行下一次迭代；否則，可將最后復合形的好點 X(L)及其函數值 F(X(L))作為最優解輸出 ( ) ( )1( ) ( )KjLjF X F X e????( ) ( ) 21[ ( ) ( ) ]KjLjF X F X e????例：用復合形法求解約束優化問題，迭代精度為 。 ?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 進行迭代，獲得新的復合形。 12211 [ ( ) ( ) ] 4 . 2 3k jLjf X f Xke???? ? ??????3 檢驗迭代終止條件 用各頂點與好點的目標函數之差的均方根小于誤差作為終止迭代條件，即 若滿足以上條件， XL為最優解。 計算簡單 ， 不必求導 ， 占內存小； 隨著維數的增加 ， 效率大大下降 。對于問題 基本思 想： 167。 該方法的關鍵是在迭代過程中不斷尋找既適用又可行的方向。 ② 必須是目標函數值下降的適用方向， 即必須與目標函數的梯度方向成鈍角。對于域內任一可行點來說，負梯度方向總是一種適用可行方向。 ? 如果 X(1) 點是在可行域的內部，則 下一次迭代仍沿X(1) 點的負梯度方向進行 。一般情況，這種搜索是沿著起作用約束的邊界以割線方式逐步逼近最優點。即 式中， cosa cosa …… 、 cosan是矢量 S(K) 與各坐標軸夾角的余弦，即方向余弦。 由 X (K) 點出發，沿 S(K) 方向，取適當步長 a(K)，則 該點必須在可行域內。 函數的梯度矢量 圖 57 可行性條件的幾何意義 適用可行方向的數學條件 綜上所述，為使搜索方向成為適用可行方向，其數學條件 為同時滿足不等式 這一條件的幾何解釋見圖 58。 x1 是既與 兩個扇形空間 x x2 的公共區域 x（即 x1）之內。反復以上兩步，直至得到最優點 x*。以后各次搜索貼邊（約束面）進行。 取最優步長 因子 x *: 從 xk點出發，沿 sk方向進行一維最優化搜索，取得最優步長，計算新點 xk+1的值 。 圖 512新點 x為不可行點 ? 約束一維搜索： 與以前所講過的一維搜索相比 ， 約束一維搜索的特點在于：對產生的每一個探測點都進行可行性判斷， 如違反了某個或某些約束條件 ， 就必須減少步長因子 ， 以使新的探測點落在最近的一個約束曲面上或約束曲面的一個容許的區間 內 。 167。 ( ) ( ) ( ) ( )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懲罰項必須具有以下極限性質： 求解該新目標函數的無約束極小值 ， 以期得到原問題的約束最優解 。 二、內懲罰函數法 (內點法 ) 這種方法將新目標函數定義于可行域內 ， 其初始點和產生的迭代點必然也在可行域內 ， 此法稱為 內懲罰函數法 。 顯然， 只有當懲罰因子 時 ， 才能求得在約束邊界上的最優解 。 無約束極值點為 *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的選取 使用內點法時 ， 初始點應選擇一個離約束邊界較遠的可行點 。 一般的看法是 ， c值的大小在迭代過程中不起決定性作用 ， 通常的取值范圍在 ~ 。由于內點法是在可行域內部進行搜索，所以初始點必須是可行域內部的可行點。 例 :用內點法求下面問題的最優解： (課堂練習 ) 并作圖畫出目標函數的等值線、可行域 。 對于約束的優化問題 ： 構造外懲罰函數的常見形式如下 ???????? lj jKpu uKK XhrXgrXFrX12)(12)()( )]([)]}(,0{ m i n [)(),( 式中，懲罰因子 r(K)規定取正，與內點法不同的是在優化過程中 r(K) 取為遞增序列 即 由原目標函數與懲罰項組成。當選r(0) 取過小，求解的次數將增多，收斂速度慢；若 r(0) 選的過大，則在非可行域中，罰函數比原目標函數要大得多，特別在起作用約束邊界處產生尖點，函數性態變壞，從而限制了某些約束優化方法的使用，使計算失敗。 約束容差帶 如前所述，用外點法求解時，由于懲罰函數的無約束最優點列 是從可行域外部向約束最優點逼近的，所以最終取得的最優點一定是在邊界的非可行域一側。 這就相當于將約束條件改為 式中， δu是容差量，一般取 δu =103~104。 解：構成懲罰函數 對于任意給定的懲罰因子 r(k)0，用解析法求 的無約束極小點，即： ),( kRX?由上面可知，當逐漸增大 r(k)值，直至趨近于無窮大時，X*(r(k))逼近原約束問題的最優解。目標函數的等值線與直線 x1+x210=0的切點是該問題的最優點。 隨著懲罰因子 r(K) 的增大過程，求出懲罰函數的無約束最優點列 ，在 的過程中，則點列將趨于原約束優化的最優解 X*。 懲罰函數是由原目標函數與懲罰項組成。 罰函數解等式約束優化問題的求解過程及基本參數的選擇與前述用外點法解不等式約束優化問題相同。 ? 課堂練習 例 55 用外點法求解下列有約束優化問題 解：懲罰函數為： 對上式求偏導 ， 得 可行域內 可行域外 無約束目標函數極小化問題的最優解系列為： 當懲罰因子漸增時 ， 由下表可看出收斂情況 。 57 混合懲罰函數法 用懲罰函數法解含有不等式約束和等式約束的一般約束優化問題的方法稱為混合懲罰函數法，簡稱混合法。按照對不等式約束處理的方法不同，混合懲罰函數法具有兩種不同的形式。 二、算法步驟及流程圖 例 54： 設有二維一般約束優化問題，數學模型為 解：目標函數的等值線和約束曲線見圖所示，最優點 X* 既要落在 [gu(X) ， u=1~4] 所包圍的區域內，同時必須在等式約束 h(X)=0的直線上。 懲罰函數法原理簡單，算法易行，且分內點法、外點法和混合法三種，各有特點，適用范圍廣。 58擴展內懲罰函數法（新） 這種方法的實質是將懲罰函數在可行域內和可行域外，分別給出定義，這樣一旦遇上非可行初始點，也能立即為極小化的程序所接受，自動為下一次求懲罰函數的極小化提供一個可行的初始點，這是一種比較成功的替換方法