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

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

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

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

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

若該方向不適用、可行，則產(chǎn)生另一方向；③若在某處產(chǎn)生的方向足夠多，仍無一適用、可行，則采用收縮步長(zhǎng)；④若步長(zhǎng)小于預(yù)先給定的誤差限則終止迭代。搜索方向----采用隨機(jī)產(chǎn)生的方向2024/3/208二.隨機(jī)方向的構(gòu)成1.用RND(X)產(chǎn)生n個(gè)隨機(jī)數(shù)2.將(0,1)中的隨機(jī)數(shù)變換到(-1,1)中去;3.構(gòu)成隨機(jī)方向變換得:于是例:對(duì)于三維問題: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)選取若干初始點(diǎn)并以之為頂點(diǎn)構(gòu)成一個(gè)多面體(復(fù)合形),然后比較各頂點(diǎn)的函數(shù)值,去掉最壞點(diǎn),代之以好的新點(diǎn),并構(gòu)成新的復(fù)合形,以逼近最優(yōu)點(diǎn).有兩種基本運(yùn)算:1)映射---在壞點(diǎn)的對(duì)側(cè)試探新點(diǎn):先計(jì)算除最壞點(diǎn)外各頂點(diǎn)的幾何中心,然后再作映射計(jì)算.2)收縮---保證映射點(diǎn)的“可行”與“下降”X1為最壞點(diǎn)---映射系數(shù)常取

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

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

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

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

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

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

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

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

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

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

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

,能使

仍在D內(nèi),則

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

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

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

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

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

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

,則ⅱ)若

,則

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

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

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

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

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

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

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

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

,對(duì)于固定的

,令得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)初始點(diǎn)X0的確定(必須為內(nèi)點(diǎn))*用現(xiàn)有機(jī)器參數(shù)作初值;*用圖解法;*用隨機(jī)方法;*

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

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

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

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

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

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

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

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

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

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

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

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

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