[所有分類]第五章約束優(yōu)化方法(編輯修改稿)

　

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