1、工程優(yōu)化設計內容提要 工程優(yōu)化問題建模工程優(yōu)化問題建模 優(yōu)化數(shù)學理論優(yōu)化數(shù)學理論 一維搜索方法一維搜索方法 無約束問題直接搜索方法無約束問題直接搜索方法 無約束問題間接接搜索方法無約束問題間接接搜索方法 約束問題直接搜索方法約束問題直接搜索方法 線性規(guī)劃與二次規(guī)劃問題求解線性規(guī)劃與二次規(guī)劃問題求解 約束問題間接搜索方法約束問題間接搜索方法 啟發(fā)式算法啟發(fā)式算法 優(yōu)化軟件系統(tǒng)優(yōu)化軟件系統(tǒng)無約束間接搜索方法一一. .梯度法梯度法( (最速下降法最速下降法) )間接法間接法: : 利用函數(shù)的性態(tài)利用函數(shù)的性態(tài), ,通過函數(shù)微分或變分求優(yōu)。通過函數(shù)微分或變分求優(yōu)。梯度法梯度法, ,牛頓法牛頓法, ,共

2、軛梯度法共軛梯度法, ,變尺度法變尺度法( (擬牛頓法擬牛頓法) )(1) (1) 算法思想算法思想梯度的負方向代表目標函數(shù)下降最快的方向梯度的負方向代表目標函數(shù)下降最快的方向, ,以負梯度方向作為一維搜索方向。以負梯度方向作為一維搜索方向。f(x)=f(x0)+(x-x0)T f(x0)+O(x-x0)2) f(x0)+(x-x0)T f(x0)設設 x=x0+ d, |d|=1f(x) f(x0)+ dT f(x0)由于由于| dT f(x0) | |d|*| f(x0) |, 或或|ab|=|a|b|cos( ) |a|b|所以所以 d= f(x0)/| f(x0) |時時, | dT

3、f(x0) |最大最大.即即:如果如果 一定一定, 在在d=- f(x0)/| f(x0) |時時, f(x)下降最快下降最快 f(x0)df(x)=2f(x)=1x0f(x)=0無約束間接搜索方法一一. .梯度法梯度法( (最速下降法最速下降法) )(2) (2) 算法算法無約束間接搜索方法一一. .梯度法梯度法( (最速下降法最速下降法) )(3) (3) 算法分析算法分析1.1.開始下降較快開始下降較快, ,當接近最優(yōu)點時當接近最優(yōu)點時, ,下降速度變慢下降速度變慢, ,呈鋸齒路線呈鋸齒路線. .2.2.優(yōu)點是算法簡單優(yōu)點是算法簡單. .局部下降最快不等于整體下降最快局部下降最快不等于整

4、體下降最快!無約束間接搜索方法二二. .牛頓法牛頓法(1) (1) 算法思想算法思想梯度法基于一次逼近梯度法基于一次逼近, ,牛頓法基于二次逼近牛頓法基于二次逼近, ,可以提高收斂速度可以提高收斂速度. .= (X)=0牛頓法迭代公式牛頓法迭代公式廣義牛頓法中一維搜索廣義牛頓法中一維搜索無約束間接搜索方法二二. .牛頓法牛頓法(2) (2) 算法算法( (廣義牛頓法廣義牛頓法) )無約束間接搜索方法二二. .牛頓法牛頓法(3) (3) 算法分析算法分析收斂階定義收斂階定義:1-1-牛頓方向牛頓方向,2-,2-梯度方向梯度方向牛頓法在現(xiàn)有算法中收斂速度最快牛頓法在現(xiàn)有算法中收斂速度最快; ;但要

5、求二階可微但要求二階可微, ,計算逆矩陣計算逆矩陣, ,計算量大計算量大, ,另外收斂與否依賴于另外收斂與否依賴于初始點的選擇初始點的選擇. .無約束間接搜索方法三三. .共軛梯度法共軛梯度法(1) (1) 算法思想算法思想結合共軛方向法和梯度法的優(yōu)點結合共軛方向法和梯度法的優(yōu)點, ,將相互共軛的搜索方向將相互共軛的搜索方向, ,同時取為與當前點同時取為與當前點梯度方向相關方向梯度方向相關方向. .一般共軛梯度法一般共軛梯度法: :初始化初始化. . g g0 0= = f(xf(x0 0), ), 選擇選擇d d0 0使使 d d0 0T Tg g0 00.0.如果如果| |g gk k|e

6、ps, |eps, 結束結束. .一維搜索一維搜索 x xk+1k+1=x=xk k+ +ak d dk k :min f(x:min f(xk k+ +ak d dk k).).選擇選擇d dk+1k+1, ,使使d dk+1k+1T THd dj j=0, j=0,1,=0, j=0,1,k. ,k. H= 2 2f(xf(xk k) )k=k+1,k=k+1,轉步轉步2.2.無約束間接搜索方法無約束間接搜索方法三三. .共軛梯度法共軛梯度法性質性質1:1: 設設x x0 0,x,x1 1,x,x2 2, ,x,xk k, g, gi i= = f(xf(xi i), d), di i為為

7、共軛共軛搜索方向搜索方向, ,即即 x xi+1i+1=x=xi i+ +aid di i, , 則則 g gi+1i+1T Td dj j=0, j=0,1,=0, j=0,1,i.,i.gi+1= f(xi+1)xidixi+1已知一般情況下，有：已知一般情況下，有： gi+1Tdi=0; 實際上當實際上當d di i之間共扼時，有：之間共扼時，有： gi+1Tdi=0， gi+1Tdi-1=0，即，即，g gi+1i+1垂直垂直d di i, d, di-1i-1, ,，d d1 1 張成的子空間（或平面）。張成的子空間（或平面）。xi-1di-1無約束間接搜索方法三三. .共軛梯度法共

8、軛梯度法性質性質1:1: 設設x x0 0,x,x1 1,x,x2 2, ,x,xk k, g, gi i= = f(xf(xi i), d), di i為為共軛共軛搜索方向搜索方向, ,即即 x xi+1i+1=x=xi i+ +aid di i, , 則則 g gi+1i+1T Td dj j=0, j=0,1,=0, j=0,1,i.,i.證明證明: :f(x)=0.5xTHx-bTx, gi= f(xi)=Hxi-b, 使使ri=gi= Hxi-bgk+1-gk=H(xk+1-xk)=aHdk在一維精確搜索時在一維精確搜索時,0 , 0)()(1kTkkTkkkkdgddxfdxf當當

9、jij g2Tg1=g1Tg1+a1g1THd1=g1Tg1-a1(-g1T+ 11d0 )Hd1=g1Tg1-a1d1THd1由由g2Td1=0, 得得(g1+a1Hd1)Td1=0, a1=-g1Td1/d1THd1由由g1Td0=0, 得得a1=g1Tg1/d1THd1所以，所以， g2Tg1=0。g g2 2T Tg g0 0=(g=(g1 1+ +a1 1HdHd1 1)g)g0 0=g=g1 1T Tg g0 0+ +a1 1d d1 1T THgHg0 0=-g=-g1 1T Td d0 0- -a1 1d d1 1T THdHd0 0=0=0所以：所以：d0THg2=（g2Tg

10、1-g2Tg0)/a0=0 21=0其余類推其余類推f(x)=0.5xTHx-bTx, gi= f(xi)=Hxi-b, 配一個零項配一個零項無約束間接搜索方法三三. .共軛梯度法共軛梯度法性質性質3:3: 設設x x0 0,x,x1 1,x,x2 2, ,x,xk k是是一維精確搜索一維精確搜索產生的點列產生的點列, g, gi i= = f(xf(xi i), d), di i為為共軛共軛搜索方向搜索方向, ,x xi+1i+1=x=xi i+ +aid di i, ,則則 g gi+1i+1T Tg gj j=0, j=0,1,=0, j=0,1,i.,i.f(x)=0.5xTHx-bT

11、x, gi= f(xi)=Hxi-b, d1d2d3g1g2g3g gi+1i+1不僅垂直以前的不僅垂直以前的d dj j, ,同時垂直以前的同時垂直以前的g gj j. .無約束間接搜索方法三三. .共軛梯度法共軛梯度法性質性質3 3證明：證明：d1d2d3g1g2g3f(x)=0.5xTHx-bTx, gi= f(xi)=Hxi-b, 使使ri=gi= Hxi-bgi+1-gi=H(xi+1-xi)=aHdigi+1=gi+aHdidiTgi+1=diTgi+adiTHdi=0, 由由di=-gi+i-1di-1，a=giTgi /diTHdigi+1Tgj=giTgj+adiTHgj=g

12、iTgj+adiTH(dj- j-1dj-1) = giTgj+adiTHdj當當j=ij=i時時， gi+1Tgi= giTgi+adiTHdi=0當當jiji時時，用歸納法，用歸納法，giTgj=0, ji.得：得： gi+1Tgj= giTgj=0無約束間接搜索方法三三. .共軛梯度法共軛梯度法由梯度構建共軛方向由梯度構建共軛方向: :在在x=xk處處, 取搜索方向取搜索方向 dk=-gk+ k-1dk-1由由dk-1THdk=0, 得得dk-1TH(-gk+ k-1dk-1)=0, k-1=gkTHdk-1/dk-1THdk-1 -Hestenes-Stiefel 由由gk-gk-1=

13、aHdk-1, 得得 k-1=gkT(gk-gk-1)/dk-1T(gk-gk-1) -Crowder-Wolfe 由由gkTgk-1= gkT(-dk-1+ k-2dk-2)= -gkTdk-1+ k-2gkTdk-2=0 , (前面性質前面性質)-dk-1Tgk-1=-(-gk-1+ k-2dk-2)Tgk-1=gk-1Tgk-1- k-2dk-2Tgk-1= gk-1Tgk-1. k-1=gkTgk/gk-1Tgk-1 -Fletcher-Reeves 無約束間接搜索方法三三. .共軛梯度法共軛梯度法(2) (2) 算法算法初始化初始化. . g g0 0= = f(xf(x0 0),

14、), 選擇選擇d d0 0=-=-g g0 0. .如果如果| |g gk k|eps, | Ak+1yk=sk, Ak+1=Hk+1-1, dk=-Akgk設設Ak+1=Ak+auuT+ bvvT, 有有Akyk+auuTyk+ bvvTyk=sk, 選選u=sk, v=Akyk無約束間接搜索方法四四. .變尺度方法變尺度方法( (擬牛頓法擬牛頓法) )設設Ak+1=Ak+auuT+ bvvT, 有有Akyk+auuTyk+ bvvTyk=sk, 選選u=sk, v=AkykAkyk+askskTyk+ bAkykykTAkTyk=sk, 選選u=sk, v=Akyk取取a=1/skTyk,

15、 b=-1/ykTAkTyk=-1/ykTAkyk 時時, (Ak對稱正定對稱正定) 上面擬牛頓方程成立上面擬牛頓方程成立.于是于是, Ak+1=Ak+skskT/skTyk - AkykykTAk/ykTAkyk, -DFP方法方法( (Davidon-Fletcher-Powell)Davidon-Fletcher-Powell) 19591959年年 1963 1963年年無約束間接搜索方法四四. .變尺度方法變尺度方法( (擬牛頓法擬牛頓法) )另一種解擬牛頓方程的方法另一種解擬牛頓方程的方法: :Hk+1sk=yk 設設Hk+1=Hk+auuT+ bvvT, 有有Hksk+aykyk

16、Tsk+ bHkskskTHksk=yk, 選選u=yk, v=Hksk取取a=1/ykTsk, b=-1/skTHksk時時, 上面擬牛頓方程成立上面擬牛頓方程成立.于是于是, Hk+1=Hk+ykykT/ykTsk - HkskskTHk/skTHksk, -BFGS方法方法( (Broyden-Fletcher-Goldfarb-Shanno)Broyden-Fletcher-Goldfarb-Shanno) 19701970年各自獨立完成年各自獨立完成上述公式需要進一步求逆上述公式需要進一步求逆. .無約束間接搜索方法四四. .變尺度方法變尺度方法( (擬牛頓法擬牛頓法) )BFGS公

17、式公式: : Hk+1=Hk+ykykT/ykTsk - HkskskTHk/skTHksk,由線性代數(shù)中由線性代數(shù)中Sherman-Morrison公式公式可得可得: 這里這里AkBFGS=Hk-1 (BFGS中定義的中定義的Hk)uAvAuvAAuvATTT111111)(TkkkTkkTkkkkTkTkkkkTkkkkBFGSkBFGSkssysyyHsysyHsssgHsAA21)()()()(所以所以, , DFPDFP公式與公式與BFGSBFGS公式都能用于計算近似公式都能用于計算近似HesseHesse矩陣的逆矩陣的逆. .這里說這里說近似近似HesseHesse矩陣矩陣, ,意

18、指意指Hk只是從擬牛頓方程得來只是從擬牛頓方程得來, ,并非實際并非實際求導得來求導得來, ,而擬牛頓方程中而擬牛頓方程中Hk并不真正是并不真正是HesseHesse矩陣矩陣. .無約束間接搜索方法性質性質: :當且僅當當且僅當s sk kT Ty yk k00時時, ,D DFPFP法與法與BFGSBFGS法保證法保證Ak k的正定性的正定性. .一般來說一般來說, ,希望如果原目標函數(shù)是有局部最優(yōu)解希望如果原目標函數(shù)是有局部最優(yōu)解, ,逼近法也能產生逼近法也能產生局部最優(yōu)解局部最優(yōu)解. .HesseHesse正定是必要條件正定是必要條件. .DFGDFG法與法與BFGSBFGS法可以保證法

19、可以保證逼近正定逼近正定. .因為上述條件是可以滿足的因為上述條件是可以滿足的: :s sk kT Ty yk k= s= sk kT THsHsk k0,0,對于正定對于正定二次目標函數(shù)成立二次目標函數(shù)成立. . 對于一般函數(shù)對于一般函數(shù), , s sk kT Ty yk k= g= gk+1k+1T Ts sk k-g-gk kT Ts sk k, ,當當s sk k取取下降方向時下降方向時, ,g gk kT Ts sk k0, 0, 當采用精確一維搜索時當采用精確一維搜索時, , g gk+1k+1T Ts sk k=0.=0.所以所以, , s sk kT Ty yk k可以大于可以

20、大于0.0.XkXk+1skgk+12. 2. D DFPFP法與法與BFGSBFGS法具有二次終止性法具有二次終止性, , 即對于正定二次目標函數(shù)即對于正定二次目標函數(shù), ,它們產生的方向是共軛的它們產生的方向是共軛的, ,所以方法至多所以方法至多n n步終止步終止. .注意注意: :對于對于正定二次目標函數(shù)正定二次目標函數(shù), ,牛頓法一次終止牛頓法一次終止. .無約束間接搜索方法四四. .變尺度方法變尺度方法( (擬牛頓法擬牛頓法) )(2) (2) 算法算法初始化初始化X X0 0,A,A0 0, k=0, g, k=0, g0 0= = f(x0).如果如果| |g gk k|eps, |100n100時收斂效果也很好時收斂效果也很好. .2. 2. BFGSBFGS法比法比DFPDFP法更穩(wěn)定法更穩(wěn)定, ,是最好的變尺度方法是最好的變尺度方法. .3. 3. 缺陷是保存缺陷是保存A A需要較多的內存