1、工程優(yōu)化設(shè)計(jì)黃正東二0一一年九月內(nèi)容提要 工程優(yōu)化問題建模工程優(yōu)化問題建模 優(yōu)化數(shù)學(xué)理論優(yōu)化數(shù)學(xué)理論 一維搜索方法一維搜索方法 無約束問題直接搜索方法無約束問題直接搜索方法 無約束問題間接接搜索方法無約束問題間接接搜索方法 約束問題直接搜索方法約束問題直接搜索方法 線性規(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) 算法思想算法思想梯度的負(fù)方向代表目標(biāo)函數(shù)下降最快的方向梯度的負(fù)方向代表目標(biāo)函數(shù)下降最快的方向, ,以負(fù)梯度方向作為一維搜索方向。以負(fù)梯度方向作為一維搜索方向。f(x)=f(x0)+(x-x0)T f(x0)+O(x-x0)2) f(x0)+(x-x0)T f(x0)設(shè)設(shè) 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)

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

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

5、斂速度最快; ;但要求二階可微但要求二階可微, ,計(jì)算逆矩陣計(jì)算逆矩陣, ,計(jì)算量大計(jì)算量大, ,另外收斂與否依賴于另外收斂與否依賴于初始點(diǎn)的選擇初始點(diǎn)的選擇. .無約束間接搜索方法三三. .共軛梯度法共軛梯度法(1) (1) 算法思想算法思想結(jié)合共軛方向法和梯度法的優(yōu)點(diǎn)結(jié)合共軛方向法和梯度法的優(yōu)點(diǎn), ,將相互共軛的搜索方向?qū)⑾嗷ス曹椀乃阉鞣较? ,同時(shí)取為與當(dāng)前點(diǎn)同時(shí)取為與當(dāng)前點(diǎn)梯度方向相關(guān)方向梯度方向相關(guān)方向. .一般共軛梯度法一般共軛梯度法: :1.1. 初始化初始化. . g g0 0= = f(xf(x0 0), ), 選擇選擇d d0 0使使 d d0 0T Tg g0 00.0.

6、2.2. 如果如果| |g gk k|epseps, , 結(jié)束結(jié)束. .3.3. 一維搜索一維搜索 x xk+1k+1= =x xk k+ +ak d dk k :min :min f(xf(xk k+ +ak d dk k).).4.4. 選擇選擇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) )5.5. k=k+1,k=k+1,轉(zhuǎn)步轉(zhuǎn)步2.2.無約束間接搜索方法無約束間接搜索方法三三. .共軛梯度法共軛梯度法性質(zhì)性質(zhì)1:1: 設(shè)設(shè)x x0 0,x,x1 1,x,x2 2, , ,x x

7、k 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.gi+1= f(xi+1)xidixi+1已知一般情況下，有：已知一般情況下，有： gi+1Tdi=0; 實(shí)際上當(dāng)實(shí)際上當(dāng)d di i之間共扼時(shí)，有：之間共扼時(shí)，有： gi+1Tdi=0， gi+1Tdi-1=0，即，即，g gi+1i+1垂直垂直d di i, d, di-1i-1, ,，d d1 1 張成的子空間（或平面

8、）。張成的子空間（或平面）。xi-1di-1無約束間接搜索方法三三. .共軛梯度法共軛梯度法性質(zhì)性質(zhì)1:1: 設(shè)設(shè)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)=aHd

9、k在一維精確搜索時(shí)在一維精確搜索時(shí),0 , 0)()(1kTkkTkkkkdgddxfdxf當(dāng)當(dāng)jij g2Tg1=g1Tg1+a1g1THd1=g1Tg1-a1(-g1T+ 11d0 )Hd1=g1Tg1-a1d1THd1由由g2Td1=0, 得得(g1+a1Hd1)Td1=0, a1=-g1Td1/d1THd1由由g1Td0=0, 得得 g1Td1=g1T(-g1+ 11d0)=-g1Tg1, 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 1

10、d d1 1T THgHg0 0=-g=-g1 1T Td d0 0- -a1 1d d1 1T THdHd0 0=0=0所以：所以：d0THg2=（g2Tg1-g2Tg0)/a0=0 21=0其余類推其余類推f(x)=0.5xTHx-bTx, gi= f(xi)=Hxi-b, 配一個(gè)零項(xiàng)配一個(gè)零項(xiàng)無約束間接搜索方法三三. .共軛梯度法共軛梯度法性質(zhì)性質(zhì)3:3: 設(shè)設(shè)x x0 0,x,x1 1,x,x2 2, , ,x xk k是是一維精確搜索一維精確搜索產(chǎn)生的點(diǎn)列產(chǎn)生的點(diǎn)列, , g gi i= = f(xf(xi i), ), d di i為為共軛共軛搜索方向搜索方向, ,x xi+1i+

11、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-bTx, gi= f(xi)=Hxi-b, d1d2d3g1g2g3g gi+1i+1不僅垂直以前的不僅垂直以前的d dj j, ,同時(shí)垂直以前的同時(shí)垂直以前的g gj j. .無約束間接搜索方法三三. .共軛梯度法共軛梯度法性質(zhì)性質(zhì)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

12、+aHdidiTgi+1=diTgi+adiTHdi=0, 由由di=-gi+i-1di-1，a=giTgi /diTHdigi+1Tgj=giTgj+adiTHgj=giTgj+adiTH(-dj+ j-1dj-1) = giTgj-adiTHdj當(dāng)當(dāng)j=ij=i時(shí)時(shí)， gi+1Tgi= giTgi-adiTHdi=0當(dāng)當(dāng)jiji時(shí)時(shí)，用歸納法，假設(shè)用歸納法，假設(shè) giTgj=0, ji.得：得： gi+1Tgj= (gi +aHdi)Tgj=giTgj+adiTH(-dj+j-1dj-1)=giTgj=0無約束間接搜索方法三三. .共軛梯度法共軛梯度法由梯度構(gòu)建共軛方向由梯度構(gòu)建共軛方向:

13、 :在在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=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 , (前面性質(zhì)前面性質(zhì))-dk-1Tgk-1=-(-gk-1+ k-2dk-2)Tgk-1=gk-1Tgk-1-

14、k-2dk-2Tgk-1= gk-1Tgk-1. k-1=gkTgk/gk-1Tgk-1 -Fletcher-Reeves 無約束間接搜索方法三三. .共軛梯度法共軛梯度法(2) (2) 算法算法1.1. 初始化初始化. . g g0 0= = f(xf(x0 0), ), 選擇選擇d d0 0=-=-g g0 0. .2.2. 如果如果| |g gk k| Ak+1yk=sk, Ak+1=Hk+1-1, dk=-Akgk設(shè)設(shè)Ak+1=Ak+auuT+ bvvT, 有有Akyk+auuTyk+ bvvTyk=sk, 選選u=sk, v=Akyk無約束間接搜索方法四四. .變尺度方法變尺度方法(

15、 (擬牛頓法擬牛頓法) )設(shè)設(shè)Ak+1=Ak+auuT+ bvvT, 有有Akyk+auuTyk+ bvvTyk=sk, 選選u=sk, v=AkykAkyk+askskTyk+ bAkykykTAkTyk=sk, 選選u=sk, v=Akyk取取a=1/skTyk, b=-1/ykTAkTyk=-1/ykTAkyk 時(shí)時(shí), (Ak對(duì)稱正定對(duì)稱正定) 上面擬牛頓方程成立上面擬牛頓方程成立.于是于是, Ak+1=Ak+skskT/skTyk - AkykykTAk/ykTAkyk, -DFP方法方法( (DavidonDavidon-Fletcher-Powell)-Fletcher-Powel

16、l) 19591959年年 1963 1963年年無約束間接搜索方法四四. .變尺度方法變尺度方法( (擬牛頓法擬牛頓法) )另一種解擬牛頓方程的方法另一種解擬牛頓方程的方法: :Hk+1sk=yk 設(shè)設(shè)Hk+1=Hk+auuT+ bvvT, 有有Hksk+aykykTsk+ bHkskskTHksk=yk, 選選u=yk, v=Hksk取取a=1/ykTsk, b=-1/skTHksk時(shí)時(shí), 上面擬牛頓方程成立上面擬牛頓方程成立.于是于是, Hk+1=Hk+ykykT/ykTsk - HkskskTHk/skTHksk, -BFGS方法方法( (Broyden-Fletcher-Goldfa

17、rb-ShannoBroyden-Fletcher-Goldfarb-Shanno) ) 19701970年各自獨(dú)立完成年各自獨(dú)立完成上述公式需要進(jìn)一步求逆上述公式需要進(jìn)一步求逆. .無約束間接搜索方法四四. .變尺度方法變尺度方法( (擬牛頓法擬牛頓法) )BFGS公式公式: : Hk+1=Hk+ykykT/ykTsk - HkskskTHk/skTHksk,由線性代數(shù)中由線性代數(shù)中Sherman-Morrison公式公式可得可得: 這里這里AkBFGS=Hk-1 (BFGS中定義的中定義的Hk)uAvAuvAAuvATTT111111)(TkkkTkkTkkkkTkTkkkkTkkkkkB

18、FGSkssysyyAsysyAsssyAsAA21)()()()(所以所以, , DFPDFP公式與公式與BFGSBFGS公式都能用于計(jì)算近似公式都能用于計(jì)算近似HesseHesse矩陣的逆矩陣的逆. .這里說這里說近似近似HesseHesse矩陣矩陣, ,意指意指Hk只是從擬牛頓方程得來只是從擬牛頓方程得來, ,并非實(shí)際并非實(shí)際求導(dǎo)得來求導(dǎo)得來, ,而擬牛頓方程中而擬牛頓方程中Hk并不真正是并不真正是HesseHesse矩陣矩陣. .無約束間接搜索方法性質(zhì)性質(zhì): :1.1. 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)s sk kT Ty yk k00時(shí)時(shí), ,D DFPFP法與法與BFGSBFGS法保證法保證Hk

19、k的正定性的正定性. .一般來說一般來說, ,希望如果原目標(biāo)函數(shù)是有局部最優(yōu)解希望如果原目標(biāo)函數(shù)是有局部最優(yōu)解, ,逼近法也能產(chǎn)生逼近法也能產(chǎn)生局部最優(yōu)解局部最優(yōu)解. .HesseHesse正定是必要條件正定是必要條件. .DFGDFG法與法與BFGSBFGS法可以保證法可以保證逼近正定逼近正定. .因?yàn)樯鲜鰲l件是可以滿足的因?yàn)樯鲜鰲l件是可以滿足的: :s sk kT Ty yk k= = s sk kT THsHsk k0,0,對(duì)于正定對(duì)于正定二次目標(biāo)函數(shù)成立二次目標(biāo)函數(shù)成立. . 對(duì)于一般函數(shù)對(duì)于一般函數(shù), , s sk kT Ty yk k= g= gk+1k+1T Ts sk k-g-gk kT Ts sk k, ,當(dāng)當(dāng)s sk k取取下降方向時(shí)下降方向時(shí), ,g gk kT Ts sk k0, 0, 當(dāng)采用精確一維搜索時(shí)當(dāng)采用精確一維搜索時(shí), , g gk+1k+1T Ts sk k=0.=0.所以所以, , s sk kT Ty yk k可以大于可以大于0.0.XkXk+1skgk+12. 2. D DFPFP法與法與BFGSBFGS法具有二次終止性法具有二次終止性, , 即對(duì)于正定二次目標(biāo)函數(shù)即對(duì)于正定二次目標(biāo)函數(shù), ,它們產(chǎn)生的方向是共軛的它們產(chǎn)生的