工程优化设计-无约束间接法.ppt

《工程优化设计-无约束间接法.ppt》由会员分享，可在线阅读，更多相关《工程优化设计-无约束间接法.ppt（33页珍藏版）》请在三一办公上搜索。

1、工程优化设计,黄正东二0一一年九月,内容提要,工程优化问题建模优化数学理论一维搜索方法无约束问题直接搜索方法无约束问题间接接搜索方法约束问题直接搜索方法线性规划与二次规划问题求解约束问题间接搜索方法启发式算法优化软件系统,无约束间接搜索方法,一.梯度法(最速下降法),间接法:利用函数的性态,通过函数微分或变分求优。梯度法,牛顿法,共轭梯度法,变尺度法(拟牛顿法),(1)算法思想,梯度的负方向代表目标函数下降最快的方向,以负梯度方向作为一维搜索方向。,f(x)=f(x0)+(x-x0)Tf(x0)+O(x-x0)2)f(x0)+(x-x0)Tf(x0)设 x=x0+d,|d|=1f(x)f(x0

2、)+dTf(x0)由于|dTf(x0)|d|*|f(x0)|,或|ab|=|a|b|cos()|a|b|所以 d=f(x0)/|f(x0)|时,|dTf(x0)|最大.即:如果 一定,在d=-f(x0)/|f(x0)|时,f(x)下降最快,f(x0),d,f(x)=2,f(x)=1,x0,f(x)=0,无约束间接搜索方法,一.梯度法(最速下降法),(2)算法,无约束间接搜索方法,一.梯度法(最速下降法),(3)算法分析,1.开始下降较快,当接近最优点时,下降速度变慢,呈锯齿路线.2.优点是算法简单.,局部下降最快不等于整体下降最快!,无约束间接搜索方法,二.牛顿法,(1)算法思想,梯度法基于一

3、次逼近,牛顿法基于二次逼近,可以提高收敛速度.,=(X)=,=0,牛顿法迭代公式,广义牛顿法中一维搜索,无约束间接搜索方法,二.牛顿法,(2)算法(广义牛顿法),无约束间接搜索方法,二.牛顿法,(3)算法分析,收敛阶定义:,1-牛顿方向,2-梯度方向,牛顿法在现有算法中收敛速度最快;但要求二阶可微,计算逆矩阵,计算量大,另外收敛与否依赖于初始点的选择.,无约束间接搜索方法,三.共轭梯度法,(1)算法思想,结合共轭方向法和梯度法的优点,将相互共轭的搜索方向,同时取为与当前点梯度方向相关方向.,一般共轭梯度法:,初始化.g0=f(x0),选择d0使 d0Tg00.如果|gk|eps,结束.一维搜索

4、 xk+1=xk+ak dk:min f(xk+ak dk).选择dk+1,使dk+1THdj=0,j=0,1,k.H=2f(xk)k=k+1,转步2.,无约束间接搜索方法,无约束间接搜索方法,三.共轭梯度法,性质1:设x0,x1,x2,xk,gi=f(xi),di为共轭搜索方向,即 xi+1=xi+aidi,则 gi+1Tdj=0,j=0,1,i.,gi+1=f(xi+1),xi,di,xi+1,已知一般情况下，有：gi+1Tdi=0;实际上当di之间共扼时，有：gi+1Tdi=0，gi+1Tdi-1=0，即，gi+1垂直di,di-1,，d1 张成的子空间（或平面）。,xi-1,di-1,

5、无约束间接搜索方法,三.共轭梯度法,性质1:设x0,x1,x2,xk,gi=f(xi),di为共轭搜索方向,即 xi+1=xi+aidi,则 gi+1Tdj=0,j=0,1,i.,证明:,f(x)=0.5xTHx-bTx,gi=f(xi)=Hxi-b,使ri=gi=Hxi-bgk+1-gk=H(xk+1-xk)=aHdk在一维精确搜索时,当ji时,gi+1Tdj=gj+1Tdj+,gi+1Tdj=gj+1Tdj+(gj+2Tdj-gj+1Tdj)+(gj+3Tdj-gj+2Tdj)+(gi+1Tdj-giTdj),d1,d2,d3,g1,g2,g3,无约束间接搜索方法,三.共轭梯度法,性质2:

6、设x0,x1,x2,xk是一维精确搜索产生的点列,gi=f(xi),di为共轭搜索方向,即 xi+1=xi+aidi,如果令则 i=0,i=0,1,k-2.即：dk=-gk+k-1dk-1,d0=-g0.,f(x)=0.5xTHx-bTx,gi=f(xi)=Hxi-b,d1,d2,d3,g1,g2,g3,性质2证明:设d0=-g0,d1=-g1+11d0,d2=-g2+21d0+22d1,要证明21=0。由d0THd2=0,得21=-d0THg2/d0THd0.设xi+1=xi+aidi,则：g1-g0=(Hx1+b)-(Hx0+b)=H(x1-x0)=a0Hd0d0THg2=g2THd0=g

7、2T(g1-g0)/a0.归结为证明g2Tg1=0,g2Tg0=0由g2-g1=a1Hd1-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。g2Tg0=(g1+a1Hd1)g0=g1Tg0+a1d1THg0=-g1Td0-a1d1THd0=0所以：d0THg2=（g2Tg1-g2Tg0)/a0=0 21=0其余类推,

8、f(x)=0.5xTHx-bTx,gi=f(xi)=Hxi-b,配一个零项,无约束间接搜索方法,三.共轭梯度法,性质3:设x0,x1,x2,xk是一维精确搜索产生的点列,gi=f(xi),di为共轭搜索方向,xi+1=xi+aidi,则 gi+1Tgj=0,j=0,1,i.,f(x)=0.5xTHx-bTx,gi=f(xi)=Hxi-b,d1,d2,d3,g1,g2,g3,gi+1不仅垂直以前的dj,同时垂直以前的gj.,无约束间接搜索方法,三.共轭梯度法,性质3证明：,d1,d2,d3,g1,g2,g3,f(x)=0.5xTHx-bTx,gi=f(xi)=Hxi-b,使ri=gi=Hxi-b

9、gi+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=giTgj+adiTH(-dj+j-1dj-1)=giTgj-adiTHdj当j=i时，gi+1Tgi=giTgi-adiTHdi=0当ji时，用归纳法，假设 giTgj=0,ji.得：gi+1Tgj=(gi+aHdi)Tgj=giTgj+adiTH(-dj+j-1dj-1)=giTgj=0,无约束间接搜索方法,三.共轭梯度法,由梯度构建共轭方向:,在x=xk处,取搜索方向

10、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,(前面性质)-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-Fletc

11、her-Reeves,无约束间接搜索方法,三.共轭梯度法,(2)算法,初始化.g0=f(x0),选择d0=-g0.如果|gk|eps,结束.一维搜索 xk+1=xk+ak dk:min f(xk+ak dk).k=gk+1Tgk+1/gkTgk,选择dk+1=-gk+1+kdk.k=k+1,转步2.,(3)算法分析,1.程序简单.2.仅需一次导数,计算量比牛顿法小,效率比梯度法高.3.适用于维数较高(50以上),易于求一阶导数的目标函数.,无约束间接搜索方法,四.变尺度方法(拟牛顿法),(1)算法思想,牛顿法具有较高的收敛速度,问题是计算Hesse矩阵的逆,需要大的计算量,特别是变量数目较大时

12、是这样的.变尺度方法(拟牛顿法)就是用一种迭代的方法近似计算Hesse矩阵的逆,减小了牛顿法的计算量.,Xk+1=Xk+a dk,dk=-H-1(Xk)f(Xk),算法迭代形式:,f(X)f(Xk+1)+f(Xk+1)T(X-Xk+1)+(1/2)(X-Xk+1)T2f(Xk+1)(X-Xk+1),f(X)f(Xk+1)+2f(Xk+1)(X-Xk+1),无约束间接搜索方法,四.变尺度方法(拟牛顿法),f(X)f(Xk+1)+2f(Xk+1)(X-Xk+1),g(X)gk+1+Hk+1(X-Xk+1)g(Xk)gk+1+Hk+1(Xk-Xk+1)Hk+1(Xk+1-Xk)=gk+1-gk拟牛顿

13、方程Hk+1sk=yk,sk=Xk+1-Xk,yk=gk+1-gk由Hk+1-1yk=sk-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,b=-1/ykTAkTyk=-1/ykTAkyk 时,(Ak对称正定)上面

14、拟牛顿方程成立.于是,Ak+1=Ak+skskT/skTyk-AkykykTAk/ykTAkyk,-DFP方法(Davidon-Fletcher-Powell)1959年 1963年,无约束间接搜索方法,四.变尺度方法(拟牛顿法),另一种解拟牛顿方程的方法:Hk+1sk=yk 设Hk+1=Hk+auuT+bvvT,有Hksk+aykykTsk+bHkskskTHksk=yk,选u=yk,v=Hksk取a=1/ykTsk,b=-1/skTHksk时,上面拟牛顿方程成立.于是,Hk+1=Hk+ykykT/ykTsk-HkskskTHk/skTHksk,-BFGS方法(Broyden-Fletche

15、r-Goldfarb-Shanno)1970年各自独立完成,上述公式需要进一步求逆.,无约束间接搜索方法,四.变尺度方法(拟牛顿法),BFGS公式:Hk+1=Hk+ykykT/ykTsk-HkskskTHk/skTHksk,由线性代数中Sherman-Morrison公式可得:,这里AkBFGS=Hk-1(BFGS中定义的Hk),所以,DFP公式与BFGS公式都能用于计算近似Hesse矩阵的逆.这里说近似Hesse矩阵,意指Hk只是从拟牛顿方程得来,并非实际求导得来,而拟牛顿方程中Hk并不真正是Hesse矩阵.,无约束间接搜索方法,性质:,当且仅当skTyk0时,DFP法与BFGS法保证Hk的

16、正定性.,一般来说,希望如果原目标函数是有局部最优解,逼近法也能产生局部最优解.Hesse正定是必要条件.DFG法与BFGS法可以保证逼近正定.因为上述条件是可以满足的:skTyk=skTHsk0,对于正定二次目标函数成立.对于一般函数,skTyk=gk+1Tsk-gkTsk,当sk取下降方向时,gkTsk0,当采用精确一维搜索时,gk+1Tsk=0.所以,skTyk可以大于0.,2.DFP法与BFGS法具有二次终止性,即对于正定二次目标函数,它们产生的方向是共轭的,所以方法至多n步终止.,注意:对于正定二次目标函数,牛顿法一次终止.,无约束间接搜索方法,四.变尺度方法(拟牛顿法),(2)算法

17、,初始化X0,A0,k=0,g0=f(x0).如果|gk|eps,停止.dk=-Akgk.一维搜索 Xk+1=Xk+akdk:min f(Xk+akdk).用DFP法或BFGS法更新Ak.k=k+1,转步2.,无约束间接搜索方法,四.变尺度方法(拟牛顿法),(3)算法分析,在一阶导数可求的情况下,变尺度方法是最好的方法之一,适合于多变量,收敛快.n100时收敛效果也很好.2.BFGS法比DFP法更稳定,是最好的变尺度方法.3.缺陷是保存A需要较多的内存.,总结,梯度法-需要一阶导数,适用于复杂目标函数初始搜索.牛顿法-需要二阶导数,Hesse阵非奇异,速度快,但维数不宜 太高.共轭梯度法-需要一阶导数.适用于维数较高(50以上),速度 远超过梯度法,但有效性比变尺度法差.变尺度法-需要一阶导数.适用于维数较高(一般10-50,最高 达到100以上),最好的无约束间接搜索方法.,无约束间接搜索方法,