【正文】 的要求 ， 還應(yīng)當(dāng)滿足所有的約束條件 。 （ 2） 復(fù)合形法適用于僅含不等式約束的問題 。 可 行方向是求解大型不等式約束優(yōu)化問題的主要方法之一 。 基本思想：這種方法的基本原理是在可行域內(nèi)選擇一個(gè)初始點(diǎn) ， 當(dāng)確定了一個(gè)可行方向 d和適當(dāng)?shù)牟介L后 ， 按式 : 0x167。 54 可行方向法 1 ( 0 , 1 , 2 , )k k kk k?? ? ? ?x x d 進(jìn)行迭代計(jì)算 ,迭代點(diǎn)既不超出可行域 ,又使目標(biāo)函數(shù)的值有所下降。在不斷調(diào)整可行方向的過程中，使迭代點(diǎn)逐步逼近約束最優(yōu)點(diǎn)。 可行方向法的搜索策略？ 即： 11( ) 0( ) ( )kukkgFF???????xxxO x1 x2 O x1 x2 a) 極值點(diǎn)處于多角形的某一頂點(diǎn)上 b) 極值點(diǎn)處于等值線的中心 c) 極值點(diǎn)處于約束曲線與等值線的切點(diǎn)上 d) 極值點(diǎn)處于兩個(gè)約束曲線的交點(diǎn)上 x﹡ g1 (x)＝ 0 g2 (x)＝ 0 g3 (x)＝ 0 x﹡ g2(x)＝ 0 g3(x)＝ 0 g4(x)＝ 0 g1(x)＝ 0 g2(x)＝ 0 O x1 x2 O x1 x2 x﹡ g2(x)＝ 0 x﹡ g1(x)＝ 0 g1(x)＝ 0 圖 110 關(guān)于設(shè)計(jì)約束的若干概念 可行域 所有滿足全部約束條件的點(diǎn)的集合。 ? ?? ?0 , 1 , 2 , ,0 , 1 , 2 ,uvg X u mDXh X v p n????? ??? ? ??? 可行點(diǎn) 可行域中的點(diǎn)，即滿足所有約束條件的點(diǎn)。 邊界點(diǎn) 在可行域邊界上的點(diǎn)。 若有點(diǎn) Xk 使得 則 Xk 為一個(gè)邊界點(diǎn)。 內(nèi)點(diǎn) 除邊界點(diǎn)以外的所有可行點(diǎn)。 若有點(diǎn) Xk 滿足 則 Xk 為一個(gè)內(nèi)點(diǎn)。 ? ? ? ?miXg ki ,2,1,0 ???? ? miXg ki ,2,1,0 ???非可行域 可行域以外的區(qū)域。 非可行點(diǎn) 非可行域中的點(diǎn)，即不滿足所有約束條件的點(diǎn)。 適時(shí)約束 若有點(diǎn) X k 使某個(gè)不等式約束 gu(X) ≤ 0 的等號 成立，即 則稱 g i(X) ≤ 0 為點(diǎn) X k 的一個(gè)適時(shí)約束。 等式約束始終是適時(shí)約束。 ? ? ? ? , , ,ikg X 0 i 1 2 m??1. 可行方向法的搜索策略 第一步迭代都是從可行的初始點(diǎn) 出發(fā)，沿點(diǎn)的負(fù)梯度 方向，將初始點(diǎn)移動(dòng)到某一個(gè)約束面（只有一個(gè)起作用的約束時(shí)）上 , 或約束面的交集（有幾個(gè)起作用的約束時(shí)）上。 0x00()f? ??dx 根據(jù)約束函數(shù)和目標(biāo)函數(shù)的不同性狀，分別采用以下幾種策略繼續(xù)搜索。 0x1x2x0xkdkxk + 1g2( x ) =0g1( x ) =00()f?? x1 新點(diǎn)在可行域內(nèi)的情況 0x1x2x0xkdkxk + 1g2( x ) =0g1( x ) =0g3( x ) =00()f?? x2 新點(diǎn)在可行域外的情況 0x1x2x0xkxk + 1g2( x ) =0g1( x ) =0g3( x ) =00()f?? x 3 沿線性約束面的搜索 0x1x2x0xkxk + 1g2( x ) =0g1( x ) =0g3( x ) =00()f?? x1()f?? xx? 4 沿非線性約束面的搜索 ? 可行方向是指沿該方向作微小移動(dòng)后，所得到的新點(diǎn)是可行點(diǎn)，且目標(biāo)函數(shù)值有所下降。 可行方向應(yīng)滿足兩個(gè)條件 : (1)可行 。 (2)下降 。 1）可行條件 方向的可行條件是指沿該方向作微小移動(dòng)后，所得到的新點(diǎn)為可行點(diǎn)。 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）下降條件 方向的下降條件是指沿該方向作微小移動(dòng)后，所得新點(diǎn)的目標(biāo)函數(shù)值是下降的。 [ ( ) ] 0k T kf??xddkxk?g1( x ) =0g2( x ) =00()f? x? 滿足可行和下降條件，即式 : [ ( ) ] 0 ( 1 , 2 , , )k T kj jJ? ? ?g x d[ ( ) ] 0k T kf??xddkxk1()k? gx1?2?2()k? gxg1( x ) =0g2( x ) =0可行下降方向區(qū)0()f? x 位于約束曲面在點(diǎn) xk的切線和目標(biāo)函數(shù)等值線在點(diǎn) xk的切線所圍成的扇形區(qū)內(nèi)，該扇形區(qū)稱為可行下降方向區(qū) 。 同時(shí)成立的方向稱可行方向 。 ? 滿足可行、下降條件的方向位于可行下降扇形區(qū)內(nèi)，在扇形區(qū)內(nèi)尋找一個(gè)最有利的方向作為本次迭代的搜索方向。 （ 1）優(yōu)選方向法 [ ( ) ] 0 ( 1 , 2 , , )k T kj jJ? ? ?g x d[ ( ) ] 0k T kf??xd由條件： 求一個(gè)以搜索方向 d為設(shè)計(jì)變量的約束優(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è)計(jì)變量 dk的線性函數(shù)，因此該式為一個(gè)（線性）規(guī)劃問題。 當(dāng) xk點(diǎn)目標(biāo)函數(shù)的負(fù)梯度方向不滿足可行條件時(shí)， 可將 方向投影到約束面 （ 或約束面的交集） 上 ， 得到投影向量 dk。 ()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)使新的迭代點(diǎn)為可行點(diǎn)，且目標(biāo)函數(shù)具有最大的下降量 —— 約束一維搜索。 1）取最優(yōu)步長 從 xk點(diǎn)出發(fā)，沿 dk方向進(jìn)行一維最優(yōu)化搜索，取得最優(yōu)步長，計(jì)算新點(diǎn) x的值 。 0x1x2xkdkxk + 1g2( x ) =0g1( x ) =0a* dk? 2） 取到約束邊界的最大步長 ? 從 xk點(diǎn)出發(fā)，沿 dk方向進(jìn)行一維最優(yōu)化搜索，得到的新點(diǎn) x為不可行點(diǎn) 。 0x1x2xkdkxk + 1g2( x ) =0g1( x ) =0a* dkaMdkx 改變步長，使新點(diǎn) x返回到約束面上來。使新點(diǎn) x恰好位于約束面上的步長稱為最大步長 。 ? 約束一維搜索： 與以前所講過的一維搜索相比 ， 約束一維搜索的特點(diǎn)在于：確定初始區(qū)間時(shí) ， 對產(chǎn)生的每一個(gè)探測點(diǎn)都進(jìn)行可行性判斷 ， 如違反了某個(gè)或某些約束條件， 就必須減少步長因子 ， 以使新的探測點(diǎn)落在最近的一個(gè)約束曲面上或約束曲面的一個(gè)容許的區(qū)間 內(nèi) 。 ?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è)計(jì)點(diǎn) xk滿足庫恩 塔克條件 1[ ( ) ( ) 00 ( 1 , 2 , , )jkkjjjjfgjJ????? ? ? ???? ????xx?1） 設(shè)計(jì)點(diǎn) 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)取初始點(diǎn) ， 則取作用約束集 : Jk={1} 0 [0,1 ]T?x120122 10 11()24 2xxfxx?? ??? ??? ? ??? ??? ? ? ?????x011()0g?????????x(2)尋找最優(yōu)方向 ， 即解一個(gè)以可行方向?yàn)樵O(shè)計(jì)變量 的規(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方向進(jìn)行一維搜索 1 0 0000 0. 98 41 0. 17 9?? ? ? ? ?? ? ? ?? ? ? ?? ? ? ?x x d1( ) ( )f ???xx1在約束邊界 g3(x)=0上 : g3(x1)=0 (4) 第二次迭代 ， 用梯度投影法確定可行方向 , 迭代點(diǎn) x的目標(biāo)函數(shù)負(fù)梯度 1( ) [ 0 . 0 9 2 5 . 8 1 8 ] Tf? ? ?x不滿足方向的可行條件 ， 將 投影到約束邊界 g3(x)=0上 。 1()f?? x投影算子： 11 1 1 1 13 3 3 3[]( ) { [ ( ) ] ( )