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

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

k

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

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具體有后頁的細節(jié)處理。帶有圓約束的線性規(guī)劃問題可通過修改單純形法求解。為DV之一約束問題間接求解方法算法分析約束問題間接求解方法五。梯度投影法（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當計算得S=0時，程序不一定停止，因為去掉一個取作用約束g，f(x)還可以下降。﹥0S=0需要對所有取作用g，有：梯度投影法（Rosen’sGradientProjectionMethod）1.該方法適合線性不等式約束；2.對非線性不等式約束優(yōu)化問題效果不佳。六。簡約梯度法算法思想將一般非線性約束優(yōu)化問題轉(zhuǎn)化為目標函數(shù)為非線性，約束函數(shù)為線性的優(yōu)化問題。通過求解線性約束，分離出因變量和自變量，對自變量求導(dǎo)得出簡約梯度，并沿負簡約梯度方向進行搜索?；舅枷胧蔷€性規(guī)劃中單純形法的推廣（Wolfe）。分

簡約梯度法（ReducedGradientMethod）--約束線性

廣義簡約梯度法（GeneralizedReducedGradientMethod）

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

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

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

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

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）；

否則，對某下標j,xjB,k+1=0,將該分量與xN,k+1最大分量

xiN,k+1

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