【文章內(nèi)容簡介】 的計算取得新的步長，使其迭代點返回至可行域的邊界上，見圖 55。 X( 0 ) X( 1 ) X( 2 ) X( 3 ) X( 4 ) X* X( 0 ) X( 1 ) g 1 ( X ) g 2 ( X ) X* )1(0X a （ a ） （ b ） 圖 55沿負梯度迭代的步長 于是上述三種情況就歸結(jié)為兩種情況：一種是 X(1) 點在可行域的內(nèi)部（而非邊界上）；另一種是 X(1) 點落在可行域的邊界上。 ? 如果 X(1) 點是在可行域的內(nèi)部，則 下一次迭代仍沿X(1) 點的負梯度方向進行 。一般地，對于不在約束邊界上的域內(nèi)點 X(K)，下一次迭代總沿該點的負梯度方向進行一維搜索， a (K) 取為最優(yōu)步長 a*，即 a (K) ? a*，其迭代式為 直至迭代點落在約束邊界上或越出某約束邊界為止 。 ? 如果 X(1) 點是在可行域邊界上或是由邊界以外調(diào)回到邊界上，則下一次不再采用負梯度為搜索方向，而采用一個適用可行方向 S (K)。若取 a (K) 是在 S (K) 方向上的一個適當(dāng)大小的步長，則有 ? 使點 X (K+1) 仍在可行域內(nèi)，且目標(biāo)函數(shù)值下降。一般情況，這種搜索是沿著起作用約束的邊界以割線方式逐步逼近最優(yōu)點。 由上述可行方向法的基本搜索過程可知，如何尋求 適用可行方向 和 適當(dāng)?shù)牟介L ， 使迭代點逼近約束最優(yōu)點，這是可行方向法要解決的兩個基本問題。 二、適用可行方向的數(shù)學(xué)條件 適用性條件 前面已經(jīng)指出，搜索方向 S(K) 滿足適用性條件是 指目標(biāo) 函數(shù) F(X) 沿該方向是下降的 。若用方向?qū)?shù)的概念來描述， 即目標(biāo)函數(shù) F(X) 在 X (K) 點沿 S(K) 的方向?qū)?shù)應(yīng)小于零。即 式中， cosa cosa …… 、 cosan是矢量 S(K) 與各坐標(biāo)軸夾角的余弦，即方向余弦。 或簡記為 這說明，凡與目標(biāo)函數(shù)負梯度矢量 成銳角的方向 都能滿足適用性要求（圖 56 ）。 。 圖 56 適用性條件的幾何意義 可行性條件 所謂滿足可行性條件 是指沿該方向一定有可行點存在。 由 X (K) 點出發(fā)，沿 S(K) 方向，取適當(dāng)步長 a(K)，則 該點必須在可行域內(nèi)。實際上，可行點與非可行點的標(biāo)志 是該點的約束函數(shù)值。若 X (K)點的所有約束函數(shù)值都小于零， 則它是可行域內(nèi)部的可行點；若 X (K) 點的某個約束函數(shù)值或 某幾個約束函數(shù)值等于零或接近于零，則該點是在邊界上的 可行點（這一個或幾個約束是 X (K) 點的起作用約束）。 起作用約束函數(shù)的負梯度為 ，則條件可用矩陣表示為 這說明，為滿足可行性要求，搜索矢量 與起作用約束 的夾角應(yīng)為銳角，如圖 57所示。 函數(shù)的梯度矢量 圖 57 可行性條件的幾何意義 適用可行方向的數(shù)學(xué)條件 綜上所述，為使搜索方向成為適用可行方向，其數(shù)學(xué)條件 為同時滿足不等式 這一條件的幾何解釋見圖 58。 圖 58（ a）是 J=1的情況，適用可行方向 必須在一個既與 又與 成銳角的扇形空間 x 內(nèi)。圖 58（ b）是 J=2 又與 成銳角構(gòu)成的扇形空間， x2 是既與 又與 成銳角而構(gòu)成的扇形空間。適用可行方向 必須是在 的情況， X(K) 點起作用的約束是 g1(X) 與 g2(X)。 x1 是既與 兩個扇形空間 x x2 的公共區(qū)域 x（即 x1）之內(nèi)。 圖 58 適用可行方向的幾何解釋 三 .可行方向法的搜索策略 第一步迭代都是從可行的初始點 出發(fā) ， 沿點的負梯度 方向 ， 將初始點移動 到某一個約束面 （ 只有一個起作用的約束時 ） 上 , 或約束面的交集 （ 有幾個起作用的約束時 ） 上 。 最優(yōu)步長法： 第一次搜索為負梯度方向，終止于邊界。第二次搜索沿適用可行方向作一維搜索以最優(yōu)步長因子求得最優(yōu)點。反復(fù)以上兩步，直至得到最優(yōu)點 x*。 0x1x2x0xkdkxk + 1g2( x ) =0g1( x ) =00()f?? x圖 59最優(yōu)步長法 邊界反彈法 ： 第一次搜索為負梯度方向，終止于邊界。以后各次搜索方向均為適用可行方向，以最大步長從一個邊界反彈到另一個邊界，直至滿足 KT 條件。 0x1x2x0xkdkxk + 1g2( x ) =0g1( x ) =0g3( x ) =00()f?? x圖 59邊界反彈法 貼邊搜索法： 第一次搜索為負梯度方向，終止于邊界。以后各次搜索貼邊（約束面）進行。 若適時約束面是切面，每次搜索到約束面的交集時，移至另一個約束面，直至收斂到最優(yōu)點。 0x1x2x0xkxk + 1g2( x ) =0g1( x ) =0g3( x ) =00()f?? x沿線性約束面的搜索 圖 510貼邊搜索法 若可行域是凸集，約束面是非線性時，從 xk點沿切線（面）方向 搜索，會進入非可行域 建立約束面的容差帶 +δ， 從 x(k) 出發(fā)，沿 s(k)方向搜索到 s(k) 方向與 g(x) +δ=0 的交點 x ′后，再沿適時約束的負梯度方向返回約束面的 x(k+1)點。 四 .步長因子的確定 1 ( 0 , 1 , 2 , )k k kk ska? ? ? ?xx 確定的 步長 應(yīng)使新的迭代點為可行點，且目標(biāo)函數(shù)具有最大的下降量 —— 約束一維搜索。 取最優(yōu)步長 因子 x *: 從 xk點出發(fā)，沿 sk方向進行一維最優(yōu)化搜索，取得最優(yōu)步長，計算新點 xk+1的值 。 0x1x2xkskxk + 1g2( x ) = 0g1( x ) = 0a * sk圖 511迭代點為可行點 取到約束邊界的最大步長 從 xk點出發(fā)，沿 sk方向進行一維最優(yōu)化搜索， 得到的新點 x為不可行點 。 0x1x2xkskxk + 1g2( x ) = 0g1( x ) = 0a * skaMskx 改變步長，使新點 x返回到約束面上來。使新點 xk+1恰好位于約束面上的步長稱為最大步長 。 圖 512新點 x為不可行點 ? 約束一維搜索： 與以前所講過的一維搜索相比 ， 約束一維搜索的特點在于：對產(chǎn)生的每一個探測點都進行可行性判斷， 如違反了某個或某些約束條件 ， 就必須減少步長因子 ， 以使新的探測點落在最近的一個約束曲面上或約束曲面的一個容許的區(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 ??圖 513容許的區(qū)間 收斂條件 2[ ( ) ]k T kfs e?e? ???????x2） 設(shè)計點 xk滿足庫恩 塔克條件 1[ ( ) ( ) 00 ( 1 , 2 , , )jkkjjjjfgjJ????? ? ? ???? ????xx 1） 設(shè)計點 xk及約束允差 滿足 ? 例 :已知約束優(yōu)化問題 (課堂練習(xí) ) 試從第 k次的迭代點 Xk=[1 2]T出發(fā)，沿由 (1,1)區(qū)間隨機數(shù) ，完成一次迭代，獲取一個新的迭代點 Xk+1，并作圖畫出目標(biāo)函數(shù)的等值線、可行域和本次迭代的搜索路線。 例 :已知約束優(yōu)化問題 (課堂練習(xí) ) 試以 X10=[2 1]T， X20=[4 1]T 和 X30=[3 3]T為復(fù)合形的初點，用復(fù)合形法進行兩次迭代計算。 一、懲罰函數(shù)法基本思想： 通過構(gòu)造懲罰函數(shù)把約束問題轉(zhuǎn)化為一系列無約束最優(yōu)化問題，進而用無約束最優(yōu)化方法去求解，這類方法稱為 序列無約束最小化方法(SUMT,sequential unconstrained minimization technique)。 167。 55內(nèi)懲罰函數(shù)法 將有約束的優(yōu)化問題轉(zhuǎn)化為無約束優(yōu)化問題來求解 。前提： 1 不能破壞約束問題的約束條件 ， 2 使它歸結(jié)到原約束問題的同一最優(yōu)解上去 。 m in ( ) ,. . ( ) 0 1 , 2 , ,( ) 0 1 , 2 , ,njkfRs t g j mh k l??????? ???xxxx 構(gòu)成一個新的目標(biāo)函數(shù) ， 稱為懲罰函數(shù) 。 ( ) ( ) ( ) ( )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懲罰項必須具有以下極限性質(zhì)：