[所有分類]第五章約束優(yōu)化方法-免費閱讀

　　

【正文】 58擴(kuò)展內(nèi)懲罰函數(shù)法（新） 這種方法的實質(zhì)是將懲罰函數(shù)在可行域內(nèi)和可行域外，分別給出定義，這樣一旦遇上非可行初始點，也能立即為極小化的程序所接受，自動為下一次求懲罰函數(shù)的極小化提供一個可行的初始點，這是一種比較成功的替換方法。 二、算法步驟及流程圖 例 54： 設(shè)有二維一般約束優(yōu)化問題，數(shù)學(xué)模型為 解：目標(biāo)函數(shù)的等值線和約束曲線見圖所示，最優(yōu)點 X* 既要落在 [gu(X) ， u=1~4] 所包圍的區(qū)域內(nèi)，同時必須在等式約束 h(X)=0的直線上。 57 混合懲罰函數(shù)法 用懲罰函數(shù)法解含有不等式約束和等式約束的一般約束優(yōu)化問題的方法稱為混合懲罰函數(shù)法，簡稱混合法。 罰函數(shù)解等式約束優(yōu)化問題的求解過程及基本參數(shù)的選擇與前述用外點法解不等式約束優(yōu)化問題相同。 隨著懲罰因子 r(K) 的增大過程，求出懲罰函數(shù)的無約束最優(yōu)點列 ，在 的過程中，則點列將趨于原約束優(yōu)化的最優(yōu)解 X*。 解：構(gòu)成懲罰函數(shù) 對于任意給定的懲罰因子 r(k)0，用解析法求 的無約束極小點，即： ),( kRX?由上面可知，當(dāng)逐漸增大 r(k)值，直至趨近于無窮大時，X*(r(k))逼近原約束問題的最優(yōu)解。 約束容差帶 如前所述，用外點法求解時，由于懲罰函數(shù)的無約束最優(yōu)點列 是從可行域外部向約束最優(yōu)點逼近的，所以最終取得的最優(yōu)點一定是在邊界的非可行域一側(cè)。 對于約束的優(yōu)化問題 ： 構(gòu)造外懲罰函數(shù)的常見形式如下 ???????? lj jKpu uKK XhrXgrXFrX12)(12)()( )]([)]}(,0{ m i n [)(),( 式中，懲罰因子 r(K)規(guī)定取正，與內(nèi)點法不同的是在優(yōu)化過程中 r(K) 取為遞增序列 即 由原目標(biāo)函數(shù)與懲罰項組成。由于內(nèi)點法是在可行域內(nèi)部進(jìn)行搜索，所以初始點必須是可行域內(nèi)部的可行點。 無約束極值點為 *1*21 1 2()2( ) 0kkkrxrxr? ??? ??? ??當(dāng) 0 4r ? *0( ) [ 2 0 ] Txr ? *0( ( ) ) 4f x r ?0 ? *0( ) [ 1 . 4 2 2 0 ] Txr ? *0( ( ) ) 2 . 0 2 2f x r ?0 0 .3 6r ? *0( ) [ 1 . 1 5 6 0 ] Txr ? *0( ( ) ) 1 . 3 3 6f x r ?0 0r ? *0( ) [1 0 ] Txr ? *0( ( ) ) 1f x r ?例 52：用內(nèi)罰函數(shù)法求解下列約束優(yōu)化問題 解 :構(gòu)造內(nèi)罰函數(shù)為 用解析法求極值 γk → 0 f(x) →1 初始點 x0的選取 使用內(nèi)點法時 ， 初始點應(yīng)選擇一個離約束邊界較遠(yuǎn)的可行點 。 二、內(nèi)懲罰函數(shù)法 (內(nèi)點法 ) 這種方法將新目標(biāo)函數(shù)定義于可行域內(nèi) ， 其初始點和產(chǎn)生的迭代點必然也在可行域內(nèi) ， 此法稱為 內(nèi)懲罰函數(shù)法 。 167。 取最優(yōu)步長 因子 x *: 從 xk點出發(fā)，沿 sk方向進(jìn)行一維最優(yōu)化搜索，取得最優(yōu)步長，計算新點 xk+1的值 。反復(fù)以上兩步，直至得到最優(yōu)點 x*。 函數(shù)的梯度矢量 圖 57 可行性條件的幾何意義 適用可行方向的數(shù)學(xué)條件 綜上所述，為使搜索方向成為適用可行方向，其數(shù)學(xué)條件 為同時滿足不等式 這一條件的幾何解釋見圖 58。即 式中， cosa cosa …… 、 cosan是矢量 S(K) 與各坐標(biāo)軸夾角的余弦，即方向余弦。 ? 如果 X(1) 點是在可行域的內(nèi)部，則 下一次迭代仍沿X(1) 點的負(fù)梯度方向進(jìn)行 。 ② 必須是目標(biāo)函數(shù)值下降的適用方向， 即必須與目標(biāo)函數(shù)的梯度方向成鈍角。對于問題 基本思 想： 167。 12211 [ ( ) ( ) ] 4 . 2 3k jLjf X f Xke???? ? ??????3 檢驗迭代終止條件 用各頂點與好點的目標(biāo)函數(shù)之差的均方根小于誤差作為終止迭代條件，即 若滿足以上條件， XL為最優(yōu)解。 (6)判斷終止條件 1) 各頂點與好點函數(shù)值之差的均方根值小于誤差限，即 1( ) ( ) 2 211{ [ ( ) ( ) ] }K jLjF X F XK e????2）各頂點與好點的函數(shù)值之差的平方和小于誤差限，即 3）各頂點與好點函數(shù)值差的絕對值之和小于誤差限，即 如果不滿足終止迭代條件，則返回步驟 2繼續(xù)進(jìn)行下一次迭代；否則，可將最后復(fù)合形的好點 X(L)及其函數(shù)值 F(X(L))作為最優(yōu)解輸出 ( ) ( )1( ) ( )KjLjF X F X e????( ) ( ) 21[ ( ) ( ) ]KjLjF X F X e????例：用復(fù)合形法求解約束優(yōu)化問題，迭代精度為 。選出好點 X(L) 和壞點 X(H)。利用該隨機(jī)數(shù)可產(chǎn)生變量 xi在給定界 限 aixibi內(nèi)的隨機(jī)數(shù) 因每產(chǎn)生一個隨機(jī)點，需要 n個隨機(jī)數(shù)，因此，產(chǎn)生 k個隨機(jī)點總共需要連續(xù)發(fā)生 K n個隨機(jī)數(shù)。 二、初始復(fù)合形的構(gòu)成 復(fù)合形的頂點 K≥n+1個。 取次好點和好點連線的中點為 X(S)。 不需計算目標(biāo)函數(shù)的梯度 ， 而是 靠選取復(fù)合形的頂點井比較各頂點處目標(biāo)函數(shù)值的大小 ，來尋找下一步的探索方向 的 。 第一次迭代 1) 產(chǎn)生兩個偽隨機(jī)數(shù)，求出第一個隨機(jī)方向。試探成功就前進(jìn)，試探失敗再重新產(chǎn)生新的隨機(jī)方向。 把隨機(jī)數(shù) ， 轉(zhuǎn)化為另一區(qū)間 （ 1， 1） 之間的隨機(jī)數(shù) 然后由隨機(jī)數(shù) yi構(gòu)成以下隨機(jī)方向 由于隨機(jī)數(shù) yi在區(qū)間（ 1， 1）內(nèi)產(chǎn)生，所構(gòu)成的隨機(jī)方向 矢量 S一定是在超球面空間里均勻分布且模等于 1的單位矢量。 通過不斷調(diào)整加權(quán)因子 ， 產(chǎn)生一系列 Φ函數(shù)的極小點序列 xk* (r1k,r2k) k= 0,1,2… ， 逐漸收斂到原目標(biāo)函數(shù)的約束最優(yōu)解 。 ) （ 1）直接法 直接解法通常適用于 僅含不等式約束 的問題。 57 混合懲罰函數(shù)法 167。第五章 約束優(yōu)化方法 167。 58 擴(kuò)展內(nèi)懲罰函數(shù)法 167。 思路 :是在 m個不等式約束條件所確定的可行域內(nèi)，選擇一個初始點，然后決定可行搜索方向 sk且以適當(dāng)?shù)牟介L αk ，進(jìn)行搜索，得到一個使目標(biāo)函數(shù)值下降的可行的新點，即完成一次迭代。 間接法主要包括：內(nèi)點罰函數(shù)法 、 外點罰函數(shù)法和混合罰函數(shù)法 、 擴(kuò)展內(nèi)懲罰函數(shù)法 。 如圖 51所示的二維問題 。 (2) 當(dāng)在某個轉(zhuǎn)折點處沿 m個（預(yù)先限定的次數(shù)）隨機(jī)方向試探均失敗，如圖中點 X (2)，則說明以此點為中心， h0 為半徑的圓周上各點都不是適用、可行的。 生成兩個偽隨機(jī)數(shù) 由此得第一個隨機(jī)方向為： 2) 求第一個迭代點 第一個迭代點表達(dá)式為： 式中 a為步長 。 在用于求解約束問題的復(fù)合形法中 ， 復(fù)合形各頂點的選擇和替換 ， 不僅要滿足目標(biāo)函數(shù)值的下降 ， 還應(yīng)當(dāng)滿足所有的約束條件 。 一般情況下，映射點的函數(shù)值比壞點的函數(shù)值要小，即 F(X(R)) F(X(H))。對于維數(shù)較低的優(yōu)化問題，由于頂點數(shù)目較少，可試湊幾個可行點作為復(fù)合形的頂點。 將非可行點調(diào)入可行域 用上述方法產(chǎn)生的 K個隨機(jī)點，并不一定都是可行的。 （ 3）計算壞點外的其余各頂點的中心點 X(s)。 (課堂練習(xí) ) 解： n=2,取復(fù)合形頂點數(shù) k=2n=4。對于本題， 不滿足迭代終止條件，需繼續(xù)迭代。 54 可行方向法 從任一可行點 X (K) 出發(fā)，尋找一個恰當(dāng)?shù)姆较?S(K) 和 一個合適的步長因子 a(K)，于是產(chǎn)生的新迭代點為 使其滿足 即在每次迭代中都保證搜索方向是在可行域內(nèi)進(jìn)行（ 稱為可行方向 ），并且目標(biāo)函數(shù)值必須穩(wěn)步地下降方向（ 稱為適用方向 ）。 同時滿足以上兩個條件的方向，稱為 適用可行方向。一般地，對于不在約束邊界上的域內(nèi)點 X(K)，下一次迭代總沿該點的負(fù)梯度方向進(jìn)行一維搜索， a (K) 取為最優(yōu)步長 a*，即 a (K) ? a*，其迭代式為 直至迭代點落在約束邊界上或越出某約束邊界為止 。 或簡記為 這說明，凡與目標(biāo)函數(shù)負(fù)梯度矢量 成銳角的方向 都能滿足適用性要求（圖 56 ）。 圖 58（ a）是 J=1的情況，適用可行方向 必須在一個既與 又與 成銳角的扇形空間 x 內(nèi)。 0x1x2x0xkdkxk + 1g2( x ) =0g1( x ) =00()f?? x圖 59最優(yōu)步長法 邊界反彈法 ： 第一次搜索為負(fù)梯度方向，終止于邊界。 0x1x2xkskxk + 1g2( x ) = 0g1( x ) = 0a * sk圖 511迭代點為可行點 取到約束邊界的最大步長 從 xk點出發(fā)，沿 sk方向進(jìn)行一維最優(yōu)化搜索， 得到的新點 x為不可行點 。 55內(nèi)懲罰函數(shù)法 將有約束的優(yōu)化問題轉(zhuǎn)化為無約束優(yōu)化問題來求解 。 此法