工程優(yōu)化約束直接法

工程優(yōu)化設(shè)計(jì)黃正東二0一二年九月內(nèi)容提要工程優(yōu)化問(wèn)題建模優(yōu)化數(shù)學(xué)理論一維搜索方法無(wú)約束問(wèn)題直接搜索方法無(wú)約束問(wèn)題間接接搜索方法約束問(wèn)題直接搜索方法線性規(guī)劃與二次規(guī)劃問(wèn)題求解約束問(wèn)題間接搜索方法啟發(fā)式算法優(yōu)化軟件系統(tǒng)約束直接搜索方法直接法:直接沿一序列方向、在滿足約束條件下的一維搜索，最后達(dá)到優(yōu)化解。主要適用于僅含不等式約束的優(yōu)化問(wèn)題.新的迭代點(diǎn)必須限制在不等式約束構(gòu)成的可行域內(nèi),且保證目標(biāo)函數(shù)的穩(wěn)定下降.隨機(jī)實(shí)驗(yàn)法隨機(jī)方向法復(fù)合形法可行方向法梯度投影法簡(jiǎn)約梯度法約束直接搜索方法一.隨機(jī)實(shí)驗(yàn)法(Monte-Carlo法)(1)算法思想通過(guò)逐步隨機(jī)取樣,逼近最優(yōu)解.每步隨機(jī)取樣得到一組點(diǎn)上的函數(shù)值,通過(guò)比較確定最優(yōu)解的較小范圍.下一步在上一步確定的范圍內(nèi)再隨機(jī)取樣,確定更小的最優(yōu)解范圍,如此下去,不斷逼近最優(yōu)解.不斷縮小最優(yōu)解的范圍隨機(jī)實(shí)驗(yàn)法(Monte-Carlo法)(2)算法隨機(jī)實(shí)驗(yàn)法(Monte-Carlo法)(3)算法分析約束直接搜索方法算法簡(jiǎn)單,容易實(shí)現(xiàn).依概率收斂,即以概率為1收斂到最優(yōu)解,但采樣點(diǎn)需要無(wú)窮多.采樣點(diǎn)多,運(yùn)算量大,效率低.約束直接搜索方法二.隨機(jī)方向法(1)算法思想通過(guò)在當(dāng)前點(diǎn)的附近隨機(jī)采樣，確定最速下降方向，進(jìn)行有約束的一維搜索，找到新的點(diǎn)。約束直接搜索方法二.隨機(jī)方向法(2)算法-初始點(diǎn)生成約束直接搜索方法二.隨機(jī)方向法(2)算法-搜索方向生成約束直接搜索方法二.隨機(jī)方向法(2)算法-步驟約束直接搜索方法三.復(fù)合形法(1)算法思想對(duì)于n維變量空間,單純形是n+1個(gè)頂點(diǎn).復(fù)合形法是多個(gè)單純形合并成的超多面體,頂點(diǎn)數(shù)

n+1.復(fù)合形法與單純形無(wú)約束直接搜索法極為相似,其不同之處:1.復(fù)合形法不限制頂點(diǎn)個(gè)數(shù)為n+1,復(fù)合形法頂點(diǎn)個(gè)數(shù)是k,2n

k

n+1.2.復(fù)合形法需要檢查頂點(diǎn)的可行性,即是否滿足約束.初始復(fù)合形法生成1.隨機(jī)測(cè)試找到一個(gè)可行點(diǎn)2.隨機(jī)生成其它點(diǎn)3.計(jì)算可行點(diǎn)的中心點(diǎn)4.中心點(diǎn)不可行時(shí),不計(jì)最遠(yuǎn)點(diǎn)重新計(jì)算中心5.將不可行點(diǎn)向中心拉靠6.初始復(fù)合形初始復(fù)合形法生成復(fù)合形法(2)算法XhXgXlXcXhXgXlXcXrXhXgXlXcXr1.Xc是可行點(diǎn)時(shí),在可行域內(nèi)找反射點(diǎn)2.Xc是非可行點(diǎn)時(shí),重新構(gòu)造復(fù)合形,并轉(zhuǎn)步驟(1)XhXgXlXcXhXgXlXc此情況還需分子情況處理復(fù)合形法(2)算法XcXl轉(zhuǎn)（3）f(Xr)<f(Xh)XhXgXlXcXrf(Xr)>f(Xh)XhXgXlXcXr對(duì)第1種情況，即Xc可行時(shí)此情況還需分子情況處理f(Xr)>f(Xh)的子情況XhXgXlXcXrXhXgXlXcXrf(Xc)>f(Xh)XhXgXcXr由Xg替代Xh在可行域內(nèi)找反射點(diǎn)Xr,代替Xh.如果仍然找不到小的反射點(diǎn),將復(fù)合形向Xl收縮.f(Xc)<f(Xh)將Xr向Xc拉靠復(fù)合形法(2)算法約束直接搜索方法三.復(fù)合形法(3)算法分析1.適應(yīng)性強(qiáng),無(wú)需導(dǎo)數(shù).2.程序較簡(jiǎn)單.3.當(dāng)變量與約束較多時(shí),計(jì)算效率顯著降低.4.當(dāng)n5時(shí),可取k=2n,當(dāng)n>5時(shí),可取k<2n.約束問(wèn)題間接求解方法四?？尚蟹较蚍ǎ╖outendijk’sMethod）算法思想針對(duì)不等式約束問(wèn)題，在線性化約束的限制下，求解線性規(guī)劃問(wèn)題確定最速可行下降方向。minf(x)s.t.gi(x)≤0,i=1,2,…,pFeasibleDomaing1(x)g2(x)dx0gi(x)為取作用的約束可行方向法（Zoutendijk’sMethod）s.t.可行方向法（Zoutendijk’sMethod）可行方向法（Zoutendijk’sMethod）可行方向法（Zoutendijk’sMethod）可行方向法（Zoutendijk’sMethod）可行方向法（Zoutendijk’sMethod）可行方向法（Zoutendijk’sMethod）可行方向法（Zoutendijk’sMethod）可行方向法（Zoutendijk’sMethod）約束問(wèn)題間接求解方法改進(jìn)可行方向法（ModifiedMethodofFeasibleDirections）minf(x)s.t.gi(x)≤0,i=1,2,…,pFeasibleDomaing1(x)g2(x)dx0gi(x)為取作用的約束約束問(wèn)題間接求解方法算法初始化x=x0,k=0;計(jì)算

f(xk)和

gi(xk),

gi為取作用約束;如果

f(xk)和gi(xk)滿足K-T條件,結(jié)束;否則,解min{dTf(xk)|dTgi(xk)<=0,dTd<=1},求d;一維搜索xk+1=xk+ak

d

:minf(xk+ak

d);k=k+1,轉(zhuǎn)步2.Step4具體有后頁(yè)的細(xì)節(jié)處理。帶有圓約束的線性規(guī)劃問(wèn)題可通過(guò)修改單純形法求解。為DV之一約束問(wèn)題間接求解方法算法分析約束問(wèn)題間接求解方法五。梯度投影法（Rosen’sGradientProjectionMethod）梯度向約束面或多約束面的交線上的投影

g1

g2d

fb設(shè)b=

f-d=x

g1+y

g2,則

g1Tb=

g1T

f=x

g1T

g1+y

g1T

g2

g2Tb=

g2T

f=x

g2T

g1+y

g2T

g2(x,y)T=[GTG]-1GT

fb=G(x,y)T=G[GTG]-1GT

f當(dāng)計(jì)算得S=0時(shí)，程序不一定停止，因?yàn)槿サ粢粋€(gè)取作用約束g，f(x)還可以下降。﹥0S=0需要對(duì)所有取作用g，有：梯度投影法（Rosen’sGradientProjectionMethod）1.該方法適合線性不等式約束；2.對(duì)非線性不等式約束優(yōu)化問(wèn)題效果不佳。六。簡(jiǎn)約梯度法算法思想將一般非線性約束優(yōu)化問(wèn)題轉(zhuǎn)化為目標(biāo)函數(shù)為非線性，約束函數(shù)為線性的優(yōu)化問(wèn)題。通過(guò)求解線性約束，分離出因變量和自變量，對(duì)自變量求導(dǎo)得出簡(jiǎn)約梯度，并沿負(fù)簡(jiǎn)約梯度方向進(jìn)行搜索?；舅枷胧蔷€性規(guī)劃中單純形法的推廣（Wolfe）。分

簡(jiǎn)約梯度法（ReducedGradientMethod）--約束線性

廣義簡(jiǎn)約梯度法（GeneralizedReducedGradientMethod）

--約束非線性簡(jiǎn)約梯度法簡(jiǎn)約梯度確定初步搜索方向minf(x)s.t.Ax=b,x≥0xN

為獨(dú)立變量minF(xN)s.t.B-1b-B-1CxN≥0

xN≥0由X>0,調(diào)整搜索方向由X>0,調(diào)整搜索步長(zhǎng)模型更新方法與線性規(guī)劃單純形法類似.1.選擇可行的初始點(diǎn)

x0=(xB,0,xN,0)>0,k=0,eps>0;2.計(jì)算

g(xN,k)和

dk;3.如果|dk|<eps,結(jié)束，得最優(yōu)解xk;

否則，作一維搜索：4.如果|xk+1-xk|<eps,結(jié)束，得最優(yōu)解xk+1；否則，轉(zhuǎn)下步；5.如果xB,k+1>0,則基本變量不變，k=k+1,轉(zhuǎn)（2）；

否則，對(duì)某下標(biāo)j,xjB,k+1=0,將該分量與xN,k+1最大分量

xiN,k+1

交換，形成新的基本變量與非基本變量，k=k+1,轉(zhuǎn)（2）；簡(jiǎn)約梯度法-算法步驟：一般非線性模型廣義簡(jiǎn)約梯度法引入松弛變量規(guī)范化的非線性模型廣義簡(jiǎn)約梯度法用泰勒展式將約束變?yōu)榫€性：分基本變量與非基本變量：廣義簡(jiǎn)約梯度法廣義簡(jiǎn)約梯度廣義簡(jiǎn)約梯度法-算法步驟：廣義簡(jiǎn)約梯度法-算法步驟：例子見(jiàn)課本P418約束問(wèn)題間接求解方法六。簡(jiǎn)約梯度法算法分析1。適合具有非線性約束的問(wèn)題；2。不太適合具有非光滑約束的問(wèn)題（需要線性逼近）；3。對(duì)于中小型，大型約束優(yōu)化問(wèn)題均適用，且計(jì)算穩(wěn)定性好