【文章內(nèi)容簡介】 第 12 頁 共 36 頁 2． 2． 1． 2 懲罰函數(shù) 內(nèi)點法的迭代步驟： 1) 取初始懲罰因子 (0)r ＞ 0(例如取 (0)r ＝ 1)，允許誤差 c＞ 0； 2) 在可行域內(nèi)選取初始點 (0)X ，令 k＝ l； 3) 從 ( 1)kX ? 點出發(fā)用無約束最優(yōu)化方法求解： minx??()( , )kXr? 的極值點 X*( ()kr )； 4) 檢驗迭代終止準則：如果滿足 ( ) ( 1 ) 1* ( ) * ( )kkX r X r ???? 和 ( ) ( 1 )2( 1 )( * , ) ( * , )( * , )kkkX r X rXr?? ?? ??? ? 則停止迭代計算，并以 X*( ()kr )為原目標函數(shù) ()fX的約束最憂解，否則轉(zhuǎn)入下一步； 5) 取 ( 1)kr ? ＝ C ()kr ， (0)X ＝ X*( ()kr )， k＝ k+1，轉(zhuǎn)向步驟 3）。 遞減系數(shù) C＝ 0． 1一 0． 5，常取 0． 1，亦可取 0． 02。 內(nèi)點法的計算程序框圖如圖 22所示： 第 13 頁 共 36 頁 圖 22 內(nèi)點法程序框圖 2． 2． 1． 3 應(yīng)注意的問題： 1） 初始點 (0)X 的選擇 因為內(nèi)點法將懲罰函數(shù)定義于可行域內(nèi)，故要求 (0)X 嚴格滿足全部約束條件，且應(yīng)避免 (0)X 位于邊界上，即應(yīng)使 ( ) 0 ( 1 , 2 ,ug X u?? … ， m)。在機械最優(yōu)化設(shè)計中，只要不顧及函數(shù)值的大小，這種點還是容易取得的。但當(dāng)約束條件多而復(fù)雜時，要確定一個初始可行點也并不十分容易。為此可先對設(shè)計問題估計 第 14 頁 共 36 頁 一 個 初 始 點 ， 這 一 點 (0)X 可 能 已 滿 足 s 個 不 等 式 約 束 條 件( ) 0 ( 1 , 2 ,ug X u?? … ， s)，而剩下的 (s1)個約束條件未滿足，即 ( ) 0 ( 1 , 2 ,ug X u?? … ， s) ( ) 0 ( 1 , 2 ,ug X u s s? ? ? ? … ， s) 先求 (0 )( ) maxkgX ? { ( ) 0 ( 1 , 2 ,ug X u s s? ? ? ? … ， s) } 然后將 ()kgX作為目標函數(shù)，求 X 使 ( ) minkgX? 受約束于 ( ) 0ugX? （ u=1， 2，?， s） ( 0 )( ) ( ) 0uug X g X?? （ u=s+1， s+2，?， m） 由此構(gòu)造懲罰函數(shù)并利用程序自身的懲罰函數(shù)法求它的極值點。在計算中一旦取得 ( ) 0ugX? 即可以停機以節(jié)省時間，這樣得到的點作為初始點至少比原初始點要多滿足一個約束條件。如此反復(fù)進行下去，直到所有約束條件均滿足為止。 求初始可行點的另一種常用方法，可按下述迭代計算步驟進行： I） 任取一點 (0) nXE? ， (0) 0r ? （例如取 (0) 1r ? ），令 k=0； II） 定出下標集 kT 與 kS ： ? ?()| ( ) 0 , 1 , 2 ,kkuT u g X u? ? ? … ， s ? ?()| ( ) 0 , 1 , 2 ,kkuS u g X u s s? ? ? ? ? … ， m III） 檢查 kS 是否為空集，若是則停止迭代，并取塞 ()kX 為初始內(nèi)點，否則進行下一步； IV) 以 ()kX 為初始點，解問題 第 15 頁 共 36 頁 () 1m in ( ) ()kkkuuu S u Tg X r gX??????????? 受約束于 ( ) 0ugX? kuT? 令所得的這個問題的最優(yōu)解為 ( 1)kX ? ，轉(zhuǎn)下一步； V） 令 ()kr ＝ ( 1)kr ? (C可取為 0． 1一 0． 5，常取 0． 1亦可取 0． 02)，令k＝ k+1，轉(zhuǎn)向步驟 II）。 還可以采用隨機選擇初始點的方法來尋找可行的初始點。 2） 初始懲罰參數(shù) (0)r 的選擇 (0)r 的選擇對 SUMT 法的計算效率影響很大，在 SUMT 法中是個比較重要的環(huán)節(jié)，選擇時需有一定的技巧和經(jīng)驗。 若 (0)r 值選得太小，則在新目標函數(shù)即懲罰函數(shù) ()( , )kXr? 中懲罰項的作用就會很小，這時求 ()( , )kXr? 的無約束極值，猶如求原目標函數(shù) ()fX本身的無約束極值，而這個極值點又不大可能接近 ()fX的約束極值點，且有跑出可行域的危險。相反，若 (0)r 值取得太大，則 開始幾次構(gòu)造的懲罰函數(shù) ()( , )kXr? 的無約束極值點就會離約束邊界很遠，將使計算效率降低。可取 (0)r ? l 一 50，但多數(shù)情況是取 (0)r =1。 通 常 ， 當(dāng) 初 始 點 (0)X 是 一 個 嚴 格 的 內(nèi) 點 時 ， 則 應(yīng) 使 懲 罰 項( 0) ( 0)11 ()muur gX????????在新目標函數(shù) (0)( , )Xr? 中所起的作用與原目標函數(shù)()fX的作用相當(dāng)，于是得 ( 0 )( 0 )( 0 )1()1()mu ufXrgX??? 第 16 頁 共 36 頁 倘若約束區(qū)域是非凸的且初始點 (0)X 亦不靠近約束邊界，則 (0)r 的取值可更小些，約為上式算得值的 0． 1—— 0． 5倍。 當(dāng)初姑點 (0)X 是一個接近 邊界的點時，按上式所求得的 (0)r 就會過小。這時應(yīng)當(dāng)加大 (0)r 值。但如果 (0)r 值又取得太大，則又會發(fā)生上述毛病。所以在求解時，應(yīng)對 (0)r 做幾次試算，以取得最合適值。 2． 2． 2 DFP 變尺度法 懲罰函數(shù)內(nèi)點法步驟 3）中用到的無約束優(yōu)化算法為 DFP變尺度法。 變尺度法是無約束最優(yōu)化方法在最近二十多年來發(fā)展中最有影響的研究 成果之一，它被公認為求解無約束極值問題最有效的算法之一，這種方法是在牛頓法的基礎(chǔ)上發(fā)展起來的。 2． 2． 2． 1 DFP 變尺度法的原理 牛頓法以及修正牛頓法雖然收斂很快，但是計算較繁，需要計算二階偏導(dǎo)數(shù)矩陣 (Hessian 矩陣 )的逆矩陣，即 1[ ( )]kHX? ，才能求得探索方向即牛頓方向： ()ks ? 1[ ( )]kHX? ()()kfX? 如果能設(shè)法構(gòu)造出一個對稱正定矩陣 ()kA 來代替 1[ ( )]kHX? ，并在迭代過程中使()kA 逐漸逼近 1[ ( )]kHX? ，那末就簡化了牛頓法的計算，且保持丁牛頓法收斂快的優(yōu)點，這就是變尺度法的基本思想。由于這一類方法的迭代形式與牛頓法類似。 變尺度法的法代公式為 ( 1 ) ( ) ( ) ( ) ( ) ( ) ( ) ( )()k k k k k k k kX X A f X X S??? ? ? ? ? ? 式中： ()k? —— 步長，可由式 ( ) ( ) ( ) ( ) ( )( ) m i n ( )k k k k kf X S f X S???? ? ? 第 17 頁 共 36 頁 求得； ()kS —— 探索方向 ( ) ( ) ( )[ ] ( )k k kS A f X? ? ? ()kA —— nxn 階對稱正定矩陣。因為它是用來代替 1[ ( )]kHX? 的，而且從一次迭代到另一次迭代是變化的，故稱為變尺度矩陣。其遞推形式為 ( 1 ) ( ) ( )k k kA A E? ?? 式中： E—— 校正矩陣，它應(yīng)只依賴于本次迭代的 ( 1)kX ? ， ()kX 和相應(yīng)的梯度( 1)()kfX?? ， ()()kfX? 向量。 在迭代過程中 ()kA 應(yīng)逐漸地逼近 1[ ( )]kHX? 。 如果能利用變尺度條件構(gòu)造出一個矩陣 ()kA 來代替 1[ ( )]kHX? ，再如果 ()kA 能用 ( 1 ) ( ) ( )k k kA A E? ??來表示，而其中校正矩陣 ()kE 又可用一個統(tǒng)一的公式表示時，則只要知道 A (1)便可求出 A (2)，并依次求出 A (3)， A (4)?，或者若已知 ()kA ，則可利用上式求出 A (k+1)， A (k+2)，?。計算時可取 A (0)＝ I，即第 l步探索是用負梯度方向。 W． C． Davido 提出并經(jīng)過 R． F1etcher 和 M． J． D． Powell 修改的求校正矩陣 ()kE 的公式即所謂 DFP公式為 ( ) ( ) ( )( ) ( )( ) ( ) ( ) ( ) ( )[ ] [ ( ) ][][ ] [ ]() k k kkk TTTk k k k kTA g g A kXXX T g g A gEk ????? ? ? ?? ? 因 ()kA 為 n x n 階對稱正定矩陣，故上式可寫為 ( ) ( ) ( ) ( ) ( ) ( )( ) ( ) ( ) ( ) ( )[ ] [ ]() [ ] [ ]k k T k k k T kk T k k T k kX X A g g AEk X g g A g? ? ? ???? ? ? ? 式中 ( ) ( 1 ) ( )k k kX X X?? ? ? ( ) ( 1 ) ( )k k kg g g?? ? ? 第 18 頁 共 36 頁 利用上式求出校正矩陣 ()kE 后，便可按式 ( 1 ) ( ) ( )k k kA A E? ??求出下一輪迭代的 A (k+1)。求出 A (k+1)后，便可按式 ( ) ( ) ( )[ ] ( )k k kS A f X? ? ?的方法決定新的探索方向： ( 1 ) ( 1 ) ( 1 )()k k kS A f X? ? ?? ? ? 可以證明，這樣產(chǎn)生的方向也是共扼方向，而且對于非二次函數(shù)來說，它比用其它方法產(chǎn)生的共輛方向共扼性更好。 DFP 變尺度法在函數(shù) ()fX的梯度向量容易求出的情況下，是非常有效的。對于多維 (n＞ 100)問題，由于收斂快、效果亦佳，被認為是無約束極值問題最好的優(yōu)化方法之一。但是計算 ()kA 的程序較復(fù)雜，且需要較大的存貯量，特別是在有舍入誤差時，也存在數(shù)值穩(wěn)定性不夠理想的情況。 2． 2． 2． 2 DFP 變尺度法的計算步驟 1) 選定初始點 (0)X 并給定計算精度 ? ，維數(shù) n； 2) 置 k＝ 0， ()kA ＝ A (0)＝ I(單位矩陣 )，計算 ( ) ( ) ( 0 )( ) ( )k