約束優(yōu)化方法已排講義

約束優(yōu)化方法已排講義2可行搜索方向

可行搜索方向:當(dāng)設(shè)計點沿該方向作微量移動時，目標(biāo)函數(shù)值將下降，且不會越出可行域。間接解法的基本思路是將約束優(yōu)化問題中的約束函數(shù)進(jìn)行特殊的加權(quán)處理后，和目標(biāo)函數(shù)結(jié)合起來，構(gòu)成一個新的目標(biāo)函數(shù)，即將原約束優(yōu)化問題轉(zhuǎn)化成為一個或一系列的無約束優(yōu)化問題。再對新的目標(biāo)函數(shù)進(jìn)行無約束優(yōu)化計算，從而間接地搜索到原約束問題的最優(yōu)解。3進(jìn)行迭代計算,迭代點既不超出可行域,又使目標(biāo)函數(shù)的值有所下降。在不斷調(diào)整可行方向的過程中，使迭代點逐步逼近約束最優(yōu)點。1.可行方向法的搜索策略第一步迭代都是從可行的初始點出發(fā)，沿點的負(fù)梯度方向，將初始點移動到某一個約束面（只有一個起作用的約束時）上,或約束面的交集（有幾個起作用的約束時）上。5.1可行方向法可行方向是求解大型約束優(yōu)化問題的主要方法之一。這種方法的基本原理是在可行域內(nèi)選擇一個初始點，當(dāng)確定了一個可行方向d和適當(dāng)?shù)牟介L后，按式:4然后根據(jù)約束函數(shù)和目標(biāo)函數(shù)的不同性狀，分別采用以下幾種策略繼續(xù)搜索。1新點在可行域內(nèi)的情況52新點在可行域外的情況63沿線性約束面的搜索74沿非線性約束面的搜索8可行方向是指沿該方向作微小移動后，所得到的新點是可行點，且目標(biāo)函數(shù)值有所下降。

可行方向應(yīng)滿足兩個條件:(1)可行;(2)下降。1）可行條件方向的可行條件是指沿該方向作微小移動后，所得到的新點為可行點。2.產(chǎn)生可行方向的條件9方向的下降條件是指沿該方向作微小移動后，所得新點的目標(biāo)函數(shù)值是下降的。2）下降條件10位于約束曲面在點xk的切線和目標(biāo)函數(shù)等值線在點xk的切線所圍成的扇形區(qū)內(nèi)，該扇形區(qū)稱為可行下降方向區(qū)。滿足可行和下降條件，即式:同時成立的方向稱可行方向.11滿足可行、下降條件的方向位于可行下降扇形區(qū)內(nèi)，在扇形區(qū)內(nèi)尋找一個最有利的方向作為本次迭代的搜索方向。（1）優(yōu)選方向法由條件：求一個以搜索方向d為設(shè)計變量的約束優(yōu)化問題s.t.各函數(shù)均為設(shè)計變量d的線性函數(shù)，因此該式為一個（線性）規(guī)劃問題。3.可行方向的產(chǎn)生方法12xkdkg1(x)=0g2(x)=0g3(x)=0g4(x)=0P——投影算子，為nXn階矩陣G——起作用約束函數(shù)的梯度矩陣，nXJ階矩陣；（2）梯度投影法當(dāng)xk點目標(biāo)函數(shù)的負(fù)梯度方向不滿足可行條件時，可將方向投影到約束面（或約束面的交集）上，得到投影向量dk。13確定的步長應(yīng)使新的迭代點為可行點，且目標(biāo)函數(shù)具有最大的下降量?！s束一維搜索1）取最優(yōu)步長從xk點出發(fā)，沿dk方向進(jìn)行一維最優(yōu)化搜索，取得最優(yōu)步長，計算新點x的值。4.步長的確定14改變步長，使新點x返回到約束面上來。使新點x恰好位于約束面上的步長稱為最大步長。取到約束邊界的最大步長從xk點出發(fā)，沿dk方向進(jìn)行一維最優(yōu)化搜索，得到的新點x為不可行點。150x1x2xkdkxk+1g2(x)=0g1(x)=0a*dkaMdkx約束一維搜索：與以前所講過的一維搜索相比，約束一維搜索的特點在于：確定初始區(qū)間時，對產(chǎn)生的每一個探測點都進(jìn)行可行性判斷，如違反了某個或某些約束條件，就必須減少步長因子，以使新的探測點落在最近的一個約束曲面上或約束曲面的一個容許的區(qū)間內(nèi)。16f(a1)f(a2)f(a1)f(a2)a1

a1

a2a0a0

a2f(a’3)f(a’3)a’3a’3f(a3)f(a3)a3a3

如得到的相鄰三個探測點都是可行點，而且函數(shù)值呈“大－?。蟆弊兓?，則與前面一維搜索相同，兩端點所決定的區(qū)間就是初始區(qū)間，接著縮小區(qū)間的到一維最小點。如最后得到的探測點落在約束曲面的一個容限之內(nèi)，而且函數(shù)值比前一點的小，則該點就是一維極小點。17收斂條件2）設(shè)計點xk滿足庫恩-塔克條件1）設(shè)計點xk及約束允差滿足18解:(1)取初始點，則取作用約束集:Jk={1}例題5-1用可行方向法求約束優(yōu)化問題191d1d2用圖解法：最優(yōu)方向：(2)尋找最優(yōu)方向，即解一個以可行方向為設(shè)計變量的規(guī)劃問題：20x1在約束邊界g3(x)=0上:g3(x1)=0(4)第二次迭代，用梯度投影法確定可行方向,迭代點x的目標(biāo)函數(shù)負(fù)梯度不滿足方向的可行條件，將投影到約束邊界g3(x)=0上。投影算子：由上式可求得：(3)沿d0方向進(jìn)行一維搜索21本次迭代方向D為沿約束邊界g3(x)=0的方向，求最佳步長求得：22x2g5(x)=068x1g4(x)=0g3(x)=0g2(x)=0g1(x)=0x0d023由于Jk={3，5}代入K—T條件：（4）收斂判斷：2425

將有不等式約束的優(yōu)化問題轉(zhuǎn)化為無約束優(yōu)化問題來求解。前提：一是不能破壞約束問題的約束條件，二是使它歸結(jié)到原約束問題的同一最優(yōu)解上去。構(gòu)成一個新的目標(biāo)函數(shù)，稱為懲罰函數(shù)求解該新目標(biāo)函數(shù)的無約束極小值，以期得到原問題的約束最優(yōu)解。按一定的法則改變權(quán)因子r1

和r2的值，求得一序列的無約束最優(yōu)解，不斷地逼近原約束優(yōu)化問題的最優(yōu)解。5.2懲罰函數(shù)法26懲罰項必須具有以下極限性質(zhì)：根據(jù)懲罰項得不同構(gòu)成形式，懲罰函數(shù)法又可分為外點懲罰函數(shù)法，內(nèi)點懲罰函數(shù)法和混合懲罰函數(shù)法。從而有27對于只具有不等式約束的優(yōu)化問題：轉(zhuǎn)化后的懲罰函數(shù)形式為：或：1.內(nèi)點法1.這種方法將新目標(biāo)函數(shù)定義于可行域內(nèi)，序列迭代點在可行域內(nèi)逐步逼近約束邊界上的最優(yōu)點。內(nèi)點法只能用來求解具有不等式約束的優(yōu)化問題。28rk是懲罰因子，它是一個由大到小且趨近于0的正數(shù)列，即:

由于內(nèi)點法的迭代過程在可行域內(nèi)進(jìn)行，“障礙項”的作用是阻止迭代點越出可行域。由“障礙項”的函數(shù)形式可知，當(dāng)?shù)c靠近某一約束邊界時，其值趨近于0，而“障礙項”的值陡然增加，并趨近于無窮大，好像在可行域的邊界上筑起了一道“高墻”，使迭代點始終不能越出可行域。顯然，只有當(dāng)懲罰因子時，才能求得在約束邊界上的最優(yōu)解。29例5-2用內(nèi)點法求的約束最優(yōu)解。解:用內(nèi)點法求解該問題時，首先構(gòu)造內(nèi)點懲罰函數(shù):用解析法求函數(shù)的極小值，運用極值條件：聯(lián)立求解得：30時不滿足約束條件應(yīng)舍去。無約束極值點為當(dāng)31使用內(nèi)點法時，初始點應(yīng)選擇一個離約束邊界較遠(yuǎn)的可行點。如太靠近某一約束邊界，構(gòu)造的懲罰函數(shù)可能由于障礙項的值很大而變得畸形，使求解無約束優(yōu)化問題發(fā)生困難.2）

懲罰因子初值r0的選取懲罰因子的初值應(yīng)適當(dāng)，否則會影響迭代計算的正常進(jìn)行。一般而言，太大，將增加迭代次數(shù)；太小，會使懲罰函數(shù)的性態(tài)變壞，甚至難以收斂到極值點。無一般性的有效方法。對于不同的問題，都要經(jīng)過多次試算，才能決定一個適當(dāng)r0

3）懲罰因子的縮減系數(shù)c的選取在構(gòu)造序列懲罰函數(shù)時，懲罰因子r是一個逐次遞減到0的數(shù)列，相鄰兩次迭代的懲罰因子的關(guān)系為:1）

初始點x0的選取32式中的c稱為懲罰因子的縮減系數(shù)，c為小于1的正數(shù)。一般的看法是，c值的大小在迭代過程中不起決定性作用，通常的取值范圍在0.1~0.7之間。4)收斂條件33外點懲罰函數(shù)的形式為：r是懲罰因子,外點法的迭代過程在可行域之外進(jìn)行，懲罰項的作用是迫使迭代點逼近約束邊界或等式約束曲面。由懲罰項的形式可知，當(dāng)?shù)cx

不可行時，懲罰項的值大于0。2.

外點法外點法是從可行域的外部構(gòu)造一個點序列去逼近原約束問題的最優(yōu)解。外點法可以用來求解含不等式和等式約束的優(yōu)化問題。34解：懲罰函數(shù)為：=對上式求偏導(dǎo)，得例5-3用外點法求解下列有約束優(yōu)化問題35無約束目標(biāo)函數(shù)極小化問題的最優(yōu)解系列為：當(dāng)懲罰因子漸增時，由下表可看出收斂情況。36r0.01-0.80975-50.00000-24.9650-49.99770.1-0.45969-5.00000-2.2344-4.947410.23607-0.500000.96310.1295100.83216-0.050002.30682.000110000.99800-0.000502.66242.6582∞108/38/337對于

相對應(yīng)的拉格朗日函數(shù)為：

在xk點作泰勒展開，取二次近似表達(dá)式5.3序列二次規(guī)劃法序列二次規(guī)劃法的基本原理是將原問題轉(zhuǎn)化為一系列二次規(guī)劃子問題。38令,拉格朗日函數(shù)的一階導(dǎo)數(shù)為Hk用變尺度矩陣Bk來代替

將等式約束函數(shù)在xk作泰勒展開，取線性近似式:39

構(gòu)成二次規(guī)劃子問題求解上述二次規(guī)劃子問題，得到的d就是搜索方向。沿搜索方向進(jìn)行一維搜索確定步長，最終得到原問題的最優(yōu)解。對具有不等式約束的非線性規(guī)劃問題：

構(gòu)成二次規(guī)劃子問題為:40求解時，在每次迭代中應(yīng)對不等式約束進(jìn)行判斷，保留其中的起作用約束，除掉不起作用的約束，將起作用的約束納入等式約束中。這樣，其中不等式約束的子問題和只具有等式約束的子問題保持了一致。4