機(jī)械優(yōu)化設(shè)計五約束優(yōu)化方法

機(jī)械優(yōu)化設(shè)計五約束優(yōu)化方法2024/3/202第五章約束優(yōu)化方法一.約束坐標(biāo)輪換法二.約束隨機(jī)方向法三.復(fù)合形法四.可行方向法五.罰函數(shù)法六.拉格朗日乘子法七.簡約梯度法及廣義簡約梯度法2024/3/203§5-1優(yōu)化方法的類型2）間接法1）直接法---將迭代點限制在可行域內(nèi)(可行性),步步降低目標(biāo)函數(shù)值(下降性),直至到達(dá)最優(yōu)點.

常用方法有:約束坐標(biāo)輪換法,約束隨機(jī)方向法,復(fù)合形法,可行方向法,線性逼近法等.---通過變換,將約束優(yōu)化問題轉(zhuǎn)化為無約束優(yōu)化問題求解.

常用方法有:罰函數(shù)法,拉格朗日乘子法等.（可解IP型問題）（可解各類問題）(按對約束條件的處理方法分)2024/3/204§5-2約束坐標(biāo)輪換法一.基本思路①可取定步長、加速步長和收縮步長,但不能取最優(yōu)步長;1.依次沿各坐標(biāo)軸方向---e1,e2,…,en方向搜索;2.將迭代點限制在可行域內(nèi).②對每一迭代點均需進(jìn)行可行性和下降性檢查.2024/3/205二.迭代步驟2024/3/206三.存在問題有時會出現(xiàn)死點,導(dǎo)致輸出“偽最優(yōu)點”.*為辨別真?zhèn)?要用K-T條件進(jìn)行檢查.2024/3/207§5-3約束隨機(jī)方向法基本思路②若該方向適用、可行，則以定步長前進(jìn)；坐標(biāo)輪換法有時會輸出“偽最優(yōu)點”

,用隨機(jī)方向法可克服這一缺點.①

若該方向不適用、可行，則產(chǎn)生另一方向；③若在某處產(chǎn)生的方向足夠多，仍無一適用、可行，則采用收縮步長；④若步長小于預(yù)先給定的誤差限則終止迭代。搜索方向----采用隨機(jī)產(chǎn)生的方向2024/3/208二.隨機(jī)方向的構(gòu)成1.用RND(X)產(chǎn)生n個隨機(jī)數(shù)2.將(0,1)中的隨機(jī)數(shù)變換到(-1,1)中去;3.構(gòu)成隨機(jī)方向變換得:于是例:對于三維問題:2024/3/209X0=X,F0=Fα=α0,F0=F(X0)F=F（X）j=1K=K+1三.隨機(jī)方向法的迭代步驟是K=0,j=0產(chǎn)生隨機(jī)方向α=0.5α否F<F0j=0K<mα≤ε結(jié)束X*=X0,F*=F0是否是否是否X∈D是否2024/3/2010§5-4復(fù)合形法基本思路

在可行域內(nèi)選取若干初始點并以之為頂點構(gòu)成一個多面體(復(fù)合形),然后比較各頂點的函數(shù)值,去掉最壞點,代之以好的新點,并構(gòu)成新的復(fù)合形,以逼近最優(yōu)點.有兩種基本運算:1)映射---在壞點的對側(cè)試探新點:先計算除最壞點外各頂點的幾何中心,然后再作映射計算.2)收縮---保證映射點的“可行”與“下降”X1為最壞點---映射系數(shù)常取

若發(fā)現(xiàn)映射點不適用、可行,則將減半后重新映射.2024/3/2011二.初始復(fù)合形的構(gòu)成1.復(fù)合形頂點數(shù)K的選擇建議:

小取大值,大取小值2)為避免降維,K應(yīng)取大些;但過大,計算量也大.*1)為保證迭代點能逼近極小點,應(yīng)使2024/3/20122.初始復(fù)合形頂點的確定1)用試湊方法產(chǎn)生---適于低維情況;2)用隨機(jī)方法產(chǎn)生①用隨機(jī)方法產(chǎn)生K個頂點

先用隨機(jī)函數(shù)產(chǎn)生

個隨機(jī)數(shù)

,然后變換到預(yù)定的區(qū)間

中去.這便得到了一個頂點,要連續(xù)產(chǎn)生K個頂點.2024/3/2013②將非可行點調(diào)入可行域內(nèi)ⅰ)檢查已獲得的各頂點的可行性,若無一可行,則重新產(chǎn)生隨機(jī)點;若有q個可行,則轉(zhuǎn)下步.ⅱ)計算q個可行點點集的幾何中心ⅲ)將非可行點逐一調(diào)入可行域內(nèi).

若仍不可行,則重復(fù)此步驟,直至進(jìn)入可行域為止.2024/3/2014三.終止判別條件各頂點與好點函數(shù)值之差的均方根應(yīng)不大于誤差限

不是十分可靠,可改變重作,看結(jié)果是否相同.2024/3/2015比較復(fù)合形各頂點的函數(shù)值，找出好點XL，壞點XHXH=XRα=0.5α找出次壞點XSH

，XH=XSH滿足終止條件？X*=XL,F*=F(XL)結(jié)束四.復(fù)合形法的迭代步驟是否給定K，δ，α，ε，ai,bi

i=1,2,…n產(chǎn)生初始復(fù)合形頂點Xj,j=1,2,…,K計算復(fù)合形各頂點的函數(shù)值F(Xj),j=1,2,…,K是是是否否否XR∈DFR<F(XH)2024/3/2016§5-5可行方向法*其特點是注意到約束最優(yōu)點通常在約束邊界上：為此，可先找出一個邊界點，然后沿邊界搜索;---是求解大型約束優(yōu)化問題的主要方法.一.尋找邊界點的方法1.在D內(nèi)取一初始點,然后沿負(fù)梯度方向搜索,直至使迭代點超越D或落在邊界上;2.若迭代點在D外,則將它調(diào)回到邊界上.2024/3/2017二.產(chǎn)生適用可行方向的辦法(一)適用可行方向的數(shù)學(xué)條件1.適用(下降)性條件在迭代點處,目標(biāo)函數(shù)沿該方向的方向?qū)?shù)應(yīng)小于0:與負(fù)梯度方向的夾角應(yīng)小于900.2024/3/20182.可行性條件

在邊界迭代點處,實時約束函數(shù)沿該方向的方向?qū)?shù)應(yīng)不小于0:與實時約束函數(shù)梯度方向的夾角應(yīng)不大于900.(1)可行方向迭代公式:只要取適當(dāng)?shù)?/p>

,能使

仍在D內(nèi),則

稱可行方向.(2)可行性條件2024/3/2019*若迭代點處于J個約束邊界的相交處,應(yīng)同時成立:綜上所述,適用可行方向的數(shù)學(xué)條件為:幾何解釋:2024/3/2020(二)最有利的適用可行方向

在滿足上述適用可行方向的數(shù)學(xué)條件的同時，使目標(biāo)函數(shù)的方向?qū)?shù)為負(fù)且達(dá)到最?。ㄌ幚頌榫€性規(guī)劃問題）：D:使求*1)---條件余度(>0,一般取為0.01—0.001);2)---方向偏離系數(shù)(>=0,對線性約束取為0,其余取為1).--規(guī)格化條件2024/3/2021三.步長因子的確定1.最優(yōu)步長因子(迭代點為內(nèi)點時使用)

下一迭代點如仍為內(nèi)點,繼續(xù)進(jìn)行,直至迭代點到邊界或域外時止.迭代公式:2.試驗步長因子將在處作泰勒展開,僅取到線性項:(1)

定義目標(biāo)函數(shù)相對下降量:(2)迭代公式(3)(4)將(2)、(3)代入(1)后整理得:

迭代點在邊界附近偏域內(nèi)一側(cè)時使用,采用最有利的適用可行方向.2)按此法,直至使迭代點進(jìn)入約束容差帶或至域外為止.*1)為保證是的一個鄰近點,的值不能取得太大.通常2024/3/20222.調(diào)整步長因子(將已出界的迭代點調(diào)回到邊界上)(1)約束邊界容差帶

在實際計算中,應(yīng)給約束邊界一個允許的誤差限:式中,通常取0.01-0.001;只要迭代點進(jìn)入容差帶,即認(rèn)為達(dá)到了邊界.(2)調(diào)整步長因子因與很接近,可認(rèn)為在這兩點間按線性變化:(1)為使新迭代點落在容差帶中部,取(2)于是有(3)*還需檢驗該點是否在容差帶內(nèi).若不滿足,則ⅰ)若

,則ⅱ)若

,則

重復(fù)以上步驟,直至滿足時止.2024/3/2023滿足K-T條件？

給定：內(nèi)點X（0），β，θ，δ，ΔfK=0，M=0

沿負(fù)梯度方向一維搜索得極小點X（K+1）求最有利的適用可行方向求試驗步長因子αtM=0K=K+1X*=X(K),F*=F(X*)結(jié)束是是是否否否求求調(diào)整步長因子否四.終止迭代準(zhǔn)則

采用K-T條件,對J個起作用約束,求解線性方程組:M=1應(yīng)為非負(fù)五.迭代步驟是2024/3/2024§5-6懲罰函數(shù)法一.概述1.基本思想將約束問題

轉(zhuǎn)化成無約束問題

求解懲罰函數(shù)可調(diào)參數(shù)*構(gòu)造懲罰函數(shù)的基本要求:①懲罰項用約束條件構(gòu)造;②到達(dá)最優(yōu)點時,懲罰項的值為0;③當(dāng)約束不滿足或未到達(dá)最優(yōu)點時,懲罰項的值大于0.2.分類①內(nèi)點法----將迭代點限制在可行域內(nèi);②外點法----迭代點一般在可行域外;③混合法----將外點法和內(nèi)點法結(jié)合起來解GP型問題.2024/3/2025二.SUMT內(nèi)點法1.懲罰函數(shù)的構(gòu)造原問題:s.t.可取式中,1)*當(dāng)X趨于D的邊界時,B(X)趨于無窮大,故又稱為障礙(圍墻)函數(shù);2024/3/20262)罰因子為使

與原問題同解,應(yīng)使*對于一個,求解一個無約束優(yōu)化問題.前一問題的結(jié)果為后一問題的初值,故為系列無約束極小化方法(SequentialUnconstrainedMinimizationTechnique).2024/3/2027

輸出X*，F(xiàn)*=F（X*）結(jié)束是2.SUMT內(nèi)點罰函數(shù)法迭代步驟用無約束方法求的極小點X*輸入X0，r0,c,ε否k=k+1,Xk=X*，rk=crkK=0,Xk=X0,2024/3/2028例:解:懲罰函數(shù)在D內(nèi)

,對于固定的

,令得r(k)x*f(x*)B(x*)1/22111.51/101.44720.72362.23610.94721/501.20.650.7…1/62501.01790.508955.90170.5179…010.50.52024/3/2029r(k)x*f(x*)B(x*)1/22111.51/101.44720.72362.23610.94721/501.20.650.7…1/62501.01790.508955.90170.5179…010.50.52024/3/20301)初始點X0的確定(必須為內(nèi)點)*用現(xiàn)有機(jī)器參數(shù)作初值;*用圖解法;*用隨機(jī)方法;*

用內(nèi)點法求內(nèi)點.3.應(yīng)用內(nèi)點法應(yīng)注意的問題---X0,r(0),c的確定2024/3/2031k=0,X(k)=X0,r(k)=r0I2為空集計算指標(biāo)集以X(K)為初始點,求解得X*。輸出是否任取X0,給定r0,c,

2024/3/20322）罰因子的初值*過大,會使的最優(yōu)點比X0

離真正的最優(yōu)點更遠(yuǎn);過小,在域內(nèi)的懲罰作用小,在接近邊界時則突然加大使性態(tài)變壞,且有可能使迭代點越出可行域.

Fox推薦3）遞減系數(shù)C本書推薦0.1—0.5.2024/3/2033三.SUMT外點法1.懲罰函數(shù)的構(gòu)造考慮非線性規(guī)劃問題:s.t.懲罰函數(shù)可取為2)罰因子*1)時,懲罰項為0,不懲罰;時,懲罰項大于0,有懲罰作用.因

邊界時,懲罰項中大括號中的值趨于0,為保證懲罰作用,應(yīng)取2024/3/20342.SUMT外點法的迭代步驟給定X0，c,r0,ε1,ε2,ε3k=0,r(k)=r0,X(K)=X0輸出X*，F(xiàn)*=F（X*）結(jié)束是是是否否否求解

得極小點X*k=k+1r(k)=cr(k)X(k)=X*---初始點,對凸規(guī)劃可任意給定;*---外點法點距精度;---等式約束允許的誤差限;---不等式約束允許的誤差限;---罰因子的放大系數(shù);**為使迭代點進(jìn)入可行域,可設(shè)約束容差帶:2024/3/2035例:解:懲罰函數(shù)在D外

,對于固定的,令得r(k)x*f(x*)11.50.250.5101.909090.826540.909091001.990990.9802960.99009910001.9990010.9980030.999001…2112024/3/20363.外點法與內(nèi)點法的比較1)外點法可解各類問題,內(nèi)點法僅適于IP型問題;2)外點法的初始點可任選,內(nèi)點法的初始點必須為內(nèi)點;3)外點法的極小點系列一般在D外,內(nèi)點法的極小點系列在D內(nèi)(全為可行點);2024/3/2037四.SUMT混合法

有等式約束時內(nèi)點法不能用,要求迭代點始終滿足不等式約束時外點法不能用.此時可將外點法和內(nèi)點法結(jié)合起來解GP型問題.*1)迭代點應(yīng)始終滿足2)Fiacco等人建議2024/3/2038§5-7拉格朗日乘子法一.等式約束問題的拉格朗日乘子法s.t.1.建立拉氏函數(shù)2.在最優(yōu)點處有如下n+q個方程成立其解為2024/3/2039s.t.二.含不等式約束問題的拉格朗日乘子法1.建立拉氏函數(shù)

再用前述方法建立拉氏函數(shù)

對不等式約束引入松弛變量,使之成為等式約束:2024/3/20402.在最優(yōu)點處有如下

n+q+2p個方程成立其解為2024/3/2041三.增廣拉格朗日乘子法

采用拉格朗日乘子法時求解有難度,而罰函數(shù)法當(dāng)?shù)c接近邊界時函數(shù)常有病態(tài),此法的思路是把兩者結(jié)合起來.其增廣拉格朗日函數(shù)為:特點:1.初始點可為非可行點;2.因增加了可調(diào)參數(shù),其收斂速度和穩(wěn)定性都優(yōu)于罰函數(shù)法.2024/3/2042§5-8簡約梯度法及廣義簡約梯度法思路：利用約束條件消去非獨立變量，使問題簡化，再沿簡化后的目標(biāo)函數(shù)的負(fù)梯度方向搜索.一簡約梯度法1.問題

s.t.2.簡約梯度1）將問題降維基向量（狀態(tài)）式中將X分成兩部分：2024/3/2043非基向量（決策)對應(yīng)的系數(shù)矩陣也分成兩部分式中，B為對應(yīng)于XB的m階方陣，且必須為滿秩矩陣；C為對應(yīng)于X