【正文】 ?? ? ??x x x或： rk是懲罰因子 ， 它是一個由大到小且趨近于 0的正數(shù)列 ，即 : 0 1 2 1 0kkr r r r r ?? ? ? ? ? ? 由于內(nèi)點法的迭代過程在可行域內(nèi)進行 ， “ 障礙項” 的作用是阻止迭代點越出可行域 。 1. 內(nèi)點法 這種方法將新目標函數(shù)定義于可行域內(nèi) ， 序列迭代點在可行域內(nèi)逐步逼近約束邊界上的最優(yōu)點 。 根據(jù)約束形式和定義的泛函及罰因子的遞推方法等不同 ， 罰函數(shù)法可分為內(nèi)點法 、 外點法和混合罰函數(shù)法三種 。 m i n ( ) ,. . ( ) 0 1 , 2 , ,( ) 0 1 , 2 , ,njkfRs t g j mh k l??????? ???xxxx 構(gòu)成一個新的目標函數(shù) ， 稱為懲罰函數(shù) ( ) ( ) ( ) ( )1 2 1 211( , , ) ( ) [ ( ) ] [ ( ) ]mlk k k kjkijr r f r G g r H h???? ? ???x x x x? 從而有 ()11l i m [ ( ) ] 0mkikir G g????? x()21l i m [ ( ) ] 0lkjkjr H h????? x( ) ( ) ( )12l i m ( , , ) ( ) 0k k kk r r f??? ??xx懲罰項必須具有以下極限性質(zhì)： 求解該新目標函數(shù)的無約束極小值 ， 以期得到原問題的約束最優(yōu)解 。 55 懲罰函數(shù)法 將有約束的優(yōu)化問題轉(zhuǎn)化為無約束優(yōu)化問題來求解 。簡稱為 SUMT法。 線性規(guī)劃的圖解法 ? Min z=3x1+x2 ? . x1+ x2≤6 ? x1+2x2≤8 ? 2 x1x2 ≤0 ? x1 ≥0, x2≥0 可行域 目標函數(shù)等值線 最優(yōu)解 6 4 8 6 0 x1 x2 最優(yōu)解若存在，很可能就是可行域的頂點； 必須尋找一種代數(shù)方法，來解決高維的情況。 2 可行下降方向 定義 設(shè) d是 的一個可行方向，即 若對于上式中的 X (k) 、 X (k+1) 存在 則稱 d為 X (k) 點的一個可行下降方向。 ii. （ 2） X (k) 為可行域中的一個邊界點，設(shè) X (k) 在約束面 gi (X ) = 0 上。 ( )01gg? ? ? ?? ? ? ?? ? ? ?? ? ? ?xx代入 K— T條件： **1*()()0 ( 1 , 2 , , )( ) 0 ( 1 , 2 , , )0 ( 1 , 2 , , )mjjjiijjjgfinxxg j mjm?????? ?? ? ???????????????? xxx123 1 100 0 1???? ? ? ? ? ?? ? ?? ? ? ? ? ?? ? ? ? ? ?123 , 0????**6, ( ) 115f????????xx* 可行下降方向 1 可行方向 定義 設(shè)點 ，若對于方向 d ，存在任意小正數(shù) δ 0 ，使得 則稱 d 為 X (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 ??收斂條件 2[ ( ) ]k T kf ???? ???????xd2） 設(shè)計點 xk滿足庫恩 塔克條件 1[ ( ) ( ) 00 ( 1 , 2 , , )jkkjjjjfgjJ????? ? ? ???? ????xx?1） 設(shè)計點 xk及約束允差 滿足 ?? 例題 51：用可行方向法求約束優(yōu)化問題 221 2 1 2 1 2112231425 1 2m in ( ) 10 4 60. . ( ) 0( ) 0( ) 6 0( ) 8 0( ) 11 0f x x x x x xs t g xgxg x xg x xg x x x? ? ? ? ? ?? ? ?? ? ?? ? ?? ? ?? ? ? ?xxx解 : (1)取初始點 ， 則取作用約束集 : Jk={1} 0 [0,1 ]T?x120122 10 11()24 2xxfxx?? ??? ??? ? ??? ??? ? ? ?????x011()0g?????????x(2)尋找最優(yōu)方向 ， 即解一個以可行方向為設(shè)計變量 的規(guī)劃問題： 12[]Tdd?d0120110122212m i n ( ) [ ( ) ] 11 2. . [ ( ) ] 0[ ( ) ] 11 2 01TTTf d ds t g df d ddd? ? ? ? ? ???? ? ? ???? ? ? ? ??? ???x x dxdxd1 d1 d2 *d用圖解法： 最優(yōu)方向： [ 0 . 9 8 4 , 0 . 1 7 9 ] T?d? (3)沿 d0方向進行一維搜索 1 0 0000 0. 98 41 0. 17 9?? ? ? ? ?? ? ? ?? ? ? ?? ? ? ?x x d1( ) ( )f ???xx1在約束邊界 g3(x)=0上 : g3(x1)=0 (4) 第二次迭代 ， 用梯度投影法確定可行方向 , 迭代點 x的目標函數(shù)負梯度 1( ) [ 0 . 0 9 2 5 . 8 1 8 ] Tf? ? ?x不滿足方向的可行條件 ， 將 投影到約束邊界 g3(x)=0上 。使新點 x恰好位于約束面上的步長稱為最大步長 。 0x1x2xkdkxk + 1g2( x ) =0g1( x ) =0a* dk? 2） 取到約束邊界的最大步長 ? 從 xk點出發(fā)，沿 dk方向進行一維最優(yōu)化搜索，得到的新點 x為不可行點 。 ()kf?? xx k d k g 1 ( x )=0 g 2 ( x )=0 g 3 ( x )=0 g 4 ( x )=0 ()kf?? x( ) / ( )k k kff? ? ? ?d P x P xP—— 投影算子，為 nXn階矩陣 1[]TT???P I G G G GG —— 起作用約束函數(shù)的梯度矩陣， nXJ階矩陣； 12[ ( ) , ( ) , , ( ) ]k k kJg g g? ? ? ?G x x x（ 2） 梯度投影法 ? 1 ( 0 , 1 , 2 , )k k kk k?? ? ? ?x x d 確定的 步長 應(yīng)使新的迭代點為可行點，且目標函數(shù)具有最大的下降量 —— 約束一維搜索。 （ 1）優(yōu)選方向法 [ ( ) ] 0 ( 1 , 2 , , )k T kj jJ? ? ?g x d[ ( ) ] 0k T kf??xd由條件： 求一個以搜索方向 d為設(shè)計變量的約束優(yōu)化問題 m in [ ( ) ]k T kf? xd[ ( ) ] 0 ( 1 , 2 , , )k T kj jJ? ? ?g x d[ ( ) ] 0k T kf??xd. 1k ?d各函數(shù)均為設(shè)計變量 dk的線性函數(shù)，因此該式為一個（線性）規(guī)劃問題。 同時成立的方向稱可行方向 。 dkxk()k? gx?dkxk1()k? gx1?2?2()k? gxg1( x ) =0g2( x ) =0[ ( ) ] 0k T k??g x d[ ( ) ] 0 ( 1 , 2 , , )k T kj jJ? ? ?g x d? 2）下降條件 方向的下降條件是指沿該方向作微小移動后，所得新點的目標函數(shù)值是下降的。 (2)下降 。 0x1x2x0xkdkxk + 1g2( x ) =0g1( x ) =00()f?? x1 新點在可行域內(nèi)的情況 0x1x2x0xkdkxk + 1g2( x ) =0g1( x ) =0g3( x ) =00()f?? x2 新點在可行域外的情況 0x1x2x0xkxk + 1g2( x ) =0g1( x ) =0g3( x ) =00()f?? x 3 沿線性約束面的搜索 0x1x2x0xkxk + 1g2( x ) =0g1( x ) =0g3( x ) =00()f?? x1()f?? xx? 4 沿非線性約束面的搜索 ? 可行方向是指沿該方向作微小移動后，所得到的新點是可行點，且目標函數(shù)值有所下降。 ? ? ? ? , , ,ikg X 0 i 1 2 m??1. 可行方向法的搜索策略 第一步迭代都是從可行的初始點 出發(fā)，沿點的負梯度 方向，將初始點移動到某一個約束面（只有一個起作用的約束時）上 , 或約束面的交集（有幾個起作用的約束時）上。 適時約束 若有點 X k 使某個不等式約束 gu(X) ≤ 0 的等號 成立，即 則稱 g i(X) ≤ 0 為點 X k 的一個適時約束。 ? ? ? ?miXg ki ,2,1,0 ???? ? miXg ki ,2,1,0 ???非可行域 可行域以外的區(qū)域。 內(nèi)點 除邊界點以外的所有可行點。 邊界點 在可行域邊界上的點。 可行方向法的搜索策略？ 即： 11( ) 0( ) ( )kukkgFF???????xxxO x1 x2 O x1 x2 a) 極值點處于多角形的某一頂點上 b) 極值點處于等值線的中心 c) 極值點處于約束曲線與等值線的切點上 d) 極值點處于兩個約束曲線的交點上 x﹡ g1 (x)＝ 0 g2 (x)＝ 0 g3 (x)＝ 0 x﹡ g2(x)＝ 0 g3(x)＝ 0 g4(x)＝ 0 g1(x)＝ 0 g2(