《第五章約束優(yōu)化方法ppt課件.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《第五章約束優(yōu)化方法ppt課件.ppt（68頁(yè)珍藏版）》請(qǐng)?jiān)趨R文網(wǎng)上搜索。

1、1,第五章 約束優(yōu)化方法,5.1 約束優(yōu)化問(wèn)題的最優(yōu)解 5.2 約束優(yōu)化問(wèn)題極小點(diǎn)的條件 5.3 常用的約束優(yōu)化方法 5.3.1 約束坐標(biāo)輪換法 5.3.2 約束隨機(jī)方向法5.3.3 復(fù)合形法5.3.5 懲罰函數(shù)法,2,概述,約束優(yōu)化問(wèn)題,約束最優(yōu)解和無(wú)約束最優(yōu)解無(wú)論是在數(shù)學(xué)模型上還是幾何意義上均是不同的概念,3,等值線,等值線族的中心,無(wú)約束最優(yōu)解解：等值線的共同中心.,數(shù)學(xué)模型:,4,數(shù)學(xué)模型:,可行域,約束最優(yōu)解,5,無(wú)約束最優(yōu)點(diǎn),約束最優(yōu)點(diǎn),6,約束優(yōu)化問(wèn)題的類型,1. 不等式約束優(yōu)化問(wèn)題(IP型),2. 等式約束優(yōu)化問(wèn)題(EP型),3. 一般約束優(yōu)化問(wèn)題(GP型),7,約束優(yōu)化方法分

2、類,約束優(yōu)化方法,約束坐標(biāo)輪換法直接法：約束隨機(jī)方向法 復(fù)合形法,間接法：懲罰函數(shù)法,直接法：設(shè)法使每一次迭代產(chǎn)生的新迭代點(diǎn)限制在可行域內(nèi)， 且一步一步的降低目標(biāo)函數(shù)值，直至最后獲得一個(gè) 可行域內(nèi)的約束最優(yōu)解。間接法：將約束優(yōu)化問(wèn)題通過(guò)一定形式的變換，轉(zhuǎn)化為無(wú)約 束優(yōu)化問(wèn)題，然后采用約束優(yōu)化方法進(jìn)行求解。,8,5.3.1 約束坐標(biāo)輪換法,基本思想: 與無(wú)約束坐標(biāo)輪換法類似, 依此沿坐標(biāo)軸 方向?qū)?yōu), 逐步逼近最優(yōu)點(diǎn)。,9,任取一個(gè)初始點(diǎn),取初始步長(zhǎng)0,沿e1方向,檢查,可行性:,適用性:,檢查 .,加速步長(zhǎng),檢查,可行性:,適用性:,10,沿e2方向,檢查,可行性:,適用性:,檢查,可行性:,

3、適用性:,檢查,可行性:,適用性:,檢查,可行性:,適用性:,11,沿e1方向,檢查,可行性:,適用性:,檢查,可行性:,適用性:,沿e2方向,檢查,可行性:,適用性:,檢查.,12,沿坐標(biāo)軸方向找不到合適的點(diǎn):縮減初始步長(zhǎng) 00.50 繼續(xù)迭代終止準(zhǔn)則: 0,約束坐標(biāo)輪換法與無(wú)約束坐標(biāo)輪換法的區(qū)別： 步長(zhǎng) 無(wú)約束: 最優(yōu)步長(zhǎng) 約 束: 加速步長(zhǎng) 對(duì)每一個(gè)迭代點(diǎn)的檢查 無(wú)約束: 檢查適用性 約 束: 檢查適用性和可行性 終止準(zhǔn)則 無(wú)約束: 點(diǎn)距準(zhǔn)則 約 束: 步長(zhǎng)準(zhǔn)則,13,特點(diǎn):,約束坐標(biāo)輪換法具有算法明了、迭代簡(jiǎn)單、便于設(shè)計(jì)者掌握運(yùn)用等優(yōu)點(diǎn)。但是，它的收斂速度較慢，對(duì)于維數(shù)較高的優(yōu)化問(wèn)題(

4、例如10維以上)很費(fèi)機(jī)時(shí)。另外，這種方法在某些情況下還會(huì)出現(xiàn)“死點(diǎn)”的病態(tài)，導(dǎo)致輸出偽最優(yōu)點(diǎn)。 避免輸出偽最優(yōu)點(diǎn)的辦法:1、輸入不同的初始點(diǎn)2、用不同的不長(zhǎng)多次計(jì)算,14,基本原理：典型的“瞎子爬山”式的數(shù)值選代解法。在可行域內(nèi)，任選初始點(diǎn) x(0)， 以給定的步長(zhǎng) a=a0 ，沿按某方法產(chǎn)生的隨機(jī)方向 S(1)取探索點(diǎn) x = x(0) + a S(1），若該點(diǎn)同時(shí)符合下降性（F(x)F(x (0) )和可行性（xD)則表示x 點(diǎn)探索成功。并以它為新的起始點(diǎn)，繼續(xù)按上面的迭代公式在 S(1）方向上獲取新的成功探索點(diǎn).,5.3.2 約束隨機(jī)方向法,15,5.3.2 約束隨機(jī)方向法,任取一個(gè)初始

5、點(diǎn),取初始步長(zhǎng)0,利用隨機(jī)函數(shù)構(gòu)成隨機(jī)方向S (1),檢查,可行性:,適用性:,檢查,若m個(gè)方向都不行,則減小步長(zhǎng):00.50,終止準(zhǔn)則: 0,16,說(shuō)明當(dāng)在某個(gè)轉(zhuǎn)折點(diǎn)處沿m個(gè)(預(yù)先限定的次數(shù))隨機(jī)方向試探均失敗，則說(shuō)明以此點(diǎn)為中心，0為半徑的圓周上各點(diǎn)都不是適用、可行點(diǎn)。此時(shí)，可將初始步長(zhǎng)0縮半后繼續(xù)試探。直到0，且沿m個(gè)隨機(jī)方向都試探失敗時(shí)，則最后一個(gè)成功點(diǎn)(如圖中的x(3)就是達(dá)到預(yù)定精度要求的約束最優(yōu)點(diǎn)，迭代即可結(jié)束。m是預(yù)先規(guī)定在某轉(zhuǎn)折點(diǎn)處產(chǎn)生隨機(jī)方向所允許的最大數(shù)目。一般可在50500范圍內(nèi)選取。約束隨機(jī)方向法的搜索方向比坐標(biāo)輪換法要靈活得多。當(dāng)預(yù)定的隨機(jī)方向限定數(shù)m足夠大時(shí)，它不

6、會(huì)像約束坐標(biāo)輪換法那樣出現(xiàn)“病態(tài)”而導(dǎo)致輸出偽最優(yōu)點(diǎn)。,17,隨機(jī)搜索方向的產(chǎn)生,在（a,b）之間的隨機(jī)數(shù)： yi= ai + ( bi ai)（-1,1）之間的隨機(jī)數(shù)： yi= 2 - 1,設(shè) 是在區(qū)間(一l，1)上的兩個(gè)隨機(jī)數(shù)。將它們分別作為坐標(biāo)軸上的分量所構(gòu)成的向量即為相應(yīng)的二維隨機(jī)向量，其單位向量：,同理，n維問(wèn)題,隨機(jī)方向的單位向量：,在算法語(yǔ)言所使用的函數(shù)庫(kù)中，有一種隨機(jī)函數(shù)RND(X)。利用這一隨機(jī)函數(shù)可在程序運(yùn)行過(guò)程中產(chǎn)生一個(gè)0到1之間的隨機(jī)數(shù)。,(il，2，n),18,約束隨機(jī)方向搜索法的特點(diǎn)： 對(duì)目標(biāo)函數(shù)的性態(tài)無(wú)特殊要求，程序設(shè)計(jì)簡(jiǎn)單，使用方便。在維數(shù)較少的情況下是一種十分

7、有效的方法，適用于小型問(wèn)題。,19,5.3.3 復(fù)合形法,基本思想：在可行域中選取K個(gè)點(diǎn)作為一復(fù)合形（多面體）的K個(gè)頂點(diǎn)。比較各點(diǎn)函數(shù)值的大小，去掉函數(shù)值最大所對(duì)應(yīng)的最壞點(diǎn)，而代之最壞點(diǎn)的映射點(diǎn)構(gòu)成新的復(fù)合形。不斷重復(fù)上述過(guò)程，使復(fù)合形不斷向最優(yōu)點(diǎn)移動(dòng)和收縮，直至滿足選代精度為止。,1,3,2,X0,X(R),n+lk2n,20,引例 設(shè)有一約束優(yōu)化問(wèn)題的數(shù)學(xué)模型,21,一、復(fù)合形法的基本思想,步驟：第一步：初始復(fù)合形的構(gòu)成 頂點(diǎn)X(1)、 X(2)、 X(3)第二步：對(duì)復(fù)合形進(jìn)行 調(diào)優(yōu)迭代計(jì)算頂點(diǎn) X(1)、 X(2)、 X(3) F1 F2 F3 X(H) X(L) 壞點(diǎn) 好點(diǎn)先求出除壞點(diǎn)

8、外，其余各點(diǎn)構(gòu)成的圖形的形心點(diǎn)X0再求壞點(diǎn)X(H)相對(duì)于形心點(diǎn)X0的映射點(diǎn) X(R),1,3,2,X0,X(R),22,步驟：第一步：初始復(fù)合形的構(gòu)成 第二步：對(duì)復(fù)合形進(jìn)行調(diào)優(yōu)迭代計(jì)算 形心點(diǎn)X0 映射點(diǎn) X(R) :反射系數(shù)， 一般開(kāi)始是取=1.3,1,3,2,檢查,可行性:,適用性:,新復(fù)合形,4,點(diǎn)的映射復(fù)合形的收縮,23,二、初始復(fù)合形的構(gòu)成,方法一:試湊法方法二:隨機(jī)產(chǎn)生(1)產(chǎn)生K個(gè)隨機(jī)點(diǎn),隨機(jī)數(shù) (il，2，n),(2) 將非可行點(diǎn)調(diào)入可行域,1,2,3,4,24,終止條件:,25,例: 用復(fù)合形法求解下例約束最優(yōu)化問(wèn)題，迭代精度取,解：取復(fù)合形的頂點(diǎn)數(shù):,(1)獲得初始復(fù)合形:

9、 本例采用人為給定四個(gè)點(diǎn),檢驗(yàn)各點(diǎn)是否可行：將各點(diǎn)的坐標(biāo)值代入以上三個(gè)約束方程，均滿足約束要求，這四個(gè)點(diǎn)為可行點(diǎn)，用作初始復(fù)合形的四個(gè)頂點(diǎn),26,(2)迭代計(jì)算獲得新復(fù)合形,計(jì)算復(fù)合形各頂點(diǎn)目標(biāo)函數(shù)值， 定出最壞點(diǎn) 最好點(diǎn) 計(jì)算除壞點(diǎn)外其余各頂點(diǎn)的中心,將 代入諸約束條件均滿足，可知 在可行城內(nèi)。,取 ，求壞點(diǎn) 的映射點(diǎn),在可行域內(nèi),27,計(jì)算 并與 比較：,用 替換 ，亦即替換構(gòu)成新的復(fù)合形：,比較各點(diǎn)目標(biāo)函數(shù)值，定出最壞點(diǎn): 最好點(diǎn):,（3）檢驗(yàn)迭代終止條件,28,29,復(fù)合形法的特點(diǎn): 對(duì)目標(biāo)函數(shù)及約束函數(shù)無(wú)特殊要求，適應(yīng)性強(qiáng)，計(jì)算量一般，收斂較快，適用中小型問(wèn)題。是現(xiàn)有解不等式約束優(yōu)化

10、問(wèn)題的一種重要的直接法。,30,5.3.5 懲罰函數(shù)法,將約束優(yōu)化問(wèn)題通過(guò)一定形式的變換，轉(zhuǎn)化為無(wú)約束優(yōu)化問(wèn)題，然后采用約束優(yōu)化方法進(jìn)行求解轉(zhuǎn)化必須滿足條件：1、不破壞原約束問(wèn)題的約束條件， 2、最優(yōu)解必須歸結(jié)到原約束問(wèn)題的最優(yōu)解上去。約束優(yōu)化問(wèn)題的間接法有: 消元法、拉格朗日乘子法、 懲罰函數(shù)法等.,31,min(x，r(k)，m(k)(5.56)xRn,式中，(x，r(k)，m(k)為增廣函數(shù)，稱為懲罰函數(shù)，簡(jiǎn)稱罰函數(shù),將一般約束優(yōu)化問(wèn)題數(shù)學(xué)模型minF(x)x,Rn,：gu(x)0， ul，2，p,hv(x)=0，v=1，2，q,轉(zhuǎn)化成為一個(gè)如下的無(wú)約束優(yōu)化問(wèn)題,構(gòu)造的新目標(biāo)函數(shù)一般形式

11、為,懲罰函數(shù)法,懲罰項(xiàng),32,按照懲罰函數(shù)構(gòu)成的形式不同，懲罰函數(shù)法又分為三種：1、內(nèi)點(diǎn)懲罰函數(shù)法2、外點(diǎn)懲罰函數(shù)法3、混合懲罰函數(shù)法,33,一、內(nèi)點(diǎn)懲罰函數(shù)法,基本思想：將新目標(biāo)函數(shù)定義于可行域內(nèi)，序列迭代點(diǎn)在可 行域內(nèi)逐步逼近原目標(biāo)函數(shù)約束邊界上的最優(yōu)點(diǎn)。將約束優(yōu)化問(wèn)題： minF(x) x : gu(x)0 (u=1 2 m)轉(zhuǎn)化為無(wú)約束優(yōu)化問(wèn)題 其中： r(1)r(2) r(3) r(k) 0 是一個(gè)遞減的正值數(shù)列： r(k)Cr(k-1)， 0C1 (k) =0,34,內(nèi)點(diǎn)懲罰函數(shù)法的思路:當(dāng)X由可行域內(nèi)靠近任一約束邊界時(shí),懲罰項(xiàng)值趨于無(wú)窮大,所以它就像圍墻一樣阻止迭代點(diǎn)越出約束邊界

12、.,條件1：不破壞原約束問(wèn)題的約束條件,35,min(x, r(k)=minF(x)+ r(k) （1/gu(x)）,條件2：最優(yōu)解必須歸結(jié)到原約束問(wèn)題的最優(yōu)解上去,36,解：若用內(nèi)點(diǎn)法求解此約束最優(yōu)化問(wèn)題，由式知懲罰函數(shù)為,將函數(shù) 對(duì) 求導(dǎo)，得:,令: 解得 無(wú)約束極小值的點(diǎn)列為 :,例: 用內(nèi)點(diǎn)法求解,的約束最優(yōu)化問(wèn)題。,無(wú)約束極小值點(diǎn)列相應(yīng)的懲罰函數(shù)值為,37,38,序列極小點(diǎn)都在可行域內(nèi),39,初始點(diǎn)x(0)的確定 自定法 :搜索法 先任取一個(gè)設(shè)計(jì)點(diǎn)x(k)；計(jì)算x(k)點(diǎn)的諸約束函數(shù)值gu(x(k)，u1，2，p,若：,構(gòu)造：,按照該數(shù)學(xué)模型解出的最優(yōu)點(diǎn)x*，至少比原設(shè)計(jì)點(diǎn)x(k)多

13、滿足一個(gè)約束條件 重復(fù)數(shù)次，直到所有的約束條件都得到滿足，最終可取得在可行域內(nèi)部的初始點(diǎn)x(0)。,40,關(guān)于幾個(gè)參數(shù)的選擇(1) 初始罰因子r(0)的選取,一般可取初始罰因子r(0)150也有建議取：,(2) 遞減系數(shù)C的選擇 通常建議取C0.10.5,41,內(nèi)點(diǎn)懲罰函數(shù)法的特點(diǎn):在給定一個(gè)可行初始方案后，能求出一系列逐步得到改進(jìn)的可行的設(shè)計(jì)方案。但只適用于解不等式約束優(yōu)化問(wèn)題，且初始點(diǎn)須在可行域內(nèi)。,42,=,已知約束優(yōu)化問(wèn)題:,試寫(xiě)出內(nèi)點(diǎn)罰函數(shù),并選出初始迭代點(diǎn).,內(nèi)點(diǎn)罰函數(shù):,例：,43,例：桁架設(shè)計(jì)問(wèn)題： minF(x)=1.57x1 x=x1 x2T,44,設(shè)有不等式約束優(yōu)化問(wèn)題：

14、,構(gòu)造外點(diǎn)法懲罰函數(shù)的常見(jiàn)形式如下：,懲罰因子r(k)規(guī)定取正。且在優(yōu)化過(guò)程中r(k)取為遞增數(shù)列 r(k)=Cr(k-1)， C1 則將保證 (k)=,二、外點(diǎn)懲罰函數(shù)法,基本思想：將新目標(biāo)函數(shù)定義于可行域外，序列迭代點(diǎn)在可 行域外逐步逼近原目標(biāo)函數(shù)約束邊界上的最優(yōu)點(diǎn)。,45,式中:,外點(diǎn)懲罰函數(shù)法的思路：可行域內(nèi)時(shí),新目標(biāo)函數(shù)就是原目標(biāo)函數(shù),當(dāng)X位于可行域外時(shí),懲罰項(xiàng)為正值,新目標(biāo)函數(shù)值增大, 就構(gòu)成了對(duì)不滿足約束條件時(shí)的一種”懲罰”.且離可行域越遠(yuǎn),懲罰就越嚴(yán)厲.當(dāng)r(k）不夠大時(shí)，罰函數(shù)（新目標(biāo)函數(shù)）的極小值在可行域外，即懲罰不夠，可加大r(k） ，隨著r(k）的增大，使新目標(biāo)函數(shù)）的

15、極小點(diǎn)越來(lái)越逼近原目標(biāo)函數(shù)極小點(diǎn)。,可行域外可行域內(nèi),46,對(duì)于解不等式約束優(yōu)化問(wèn)題min F(x)xx R1 ：g1(x)=x10用外點(diǎn)法構(gòu)造懲罰函數(shù)，具體構(gòu)造形式如下：,寫(xiě)成另一種形式,例,47,令: 解得 無(wú)約束極小值的點(diǎn)列為 :,無(wú)約束極小值點(diǎn)列相應(yīng)的懲罰函數(shù)值為,求懲罰函數(shù)極小點(diǎn):,48,由此可見(jiàn)，當(dāng)懲罰因子為一遞增正值數(shù)列時(shí)，其極值點(diǎn) 離約束最優(yōu)點(diǎn) 愈來(lái)愈近， 的差值與 愈來(lái)愈小。當(dāng) 時(shí)， ， 亦即逼近于真正的約束最優(yōu)解。無(wú)約束極值點(diǎn)列 隨 值遞增從可行域外向最優(yōu)點(diǎn)收斂。,49,對(duì)幾個(gè)問(wèn)題的討論初始點(diǎn)x(0)的選取:外點(diǎn)法的初始點(diǎn)x(0)可以任選，即在可行域 與非可行域選取均可。(

16、2) 初始罰因子r(0)和遞增系數(shù)C的選取 初始罰因子r(0)選得是否恰當(dāng)，對(duì)算法的成敗和計(jì)算速度仍有著顯著的影響。因此，選取時(shí)要謹(jǐn)慎。遞增系數(shù)C的取值，一般影響不太顯著，但也不宜取得過(guò)大。通常取C510。(3) 約束容差帶 用外點(diǎn)法求解時(shí)，由于罰函數(shù)的無(wú)約束最優(yōu)點(diǎn)列是從可行域外部向約束最優(yōu)點(diǎn)逼近的，所以最終取得的最優(yōu)點(diǎn)一定是在邊界的非可行域一側(cè)。嚴(yán)格地說(shuō)，它是一個(gè)非可行點(diǎn)。這對(duì)某些工程問(wèn)題可能是不允許的。為了解決這一問(wèn)題?？稍诩s束邊界的可行域一側(cè)加一條容差帶，如圖5.21。這就相當(dāng)于將約束條件改為gu(x)u0，u=1，2，p式中的u是容差量，一般可取u=103104。,50,約束容差帶。,51,外點(diǎn)法不但可以解不等式約束優(yōu)化問(wèn)題，而且還可以解等式約束優(yōu)化問(wèn)題 用外點(diǎn)法求解二維等式約束優(yōu)化問(wèn)題：,按外點(diǎn)法的基本思想，構(gòu)造懲罰函數(shù),52,外點(diǎn)法的特點(diǎn)外點(diǎn)法既可解不等式約束優(yōu)化問(wèn)題，也能解等式約束優(yōu)化問(wèn)題， 且其初始點(diǎn)x(0)可任選，即在可行域中或非可行域中均可。其缺點(diǎn)是序列無(wú)約束最優(yōu)點(diǎn)是一系列的非可行點(diǎn)，對(duì)于工程設(shè)計(jì) 一般是不可取的。為使最終的迭代點(diǎn)能落入可行域，必須設(shè)置約 束容差帶。