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

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

2、+d, |d|=1 f(x)f(x0)+ 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.优点是算法简单.,局部下降最快

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

4、共轭梯度法:,初始化. g0= f(x0), 选择d0使 d0Tg00. 如果|gk|eps, 结束. 一维搜索 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之间共扼时

5、，有： gi+1Tdi=0， gi+1Tdi-1=0， 即，gi+1垂直di, di-1,，d1 张成的子空间（或平面）。,xi-1,di-1,无约束间接搜索方法,三.共轭梯度法,性质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-b gk+1-gk=H(xk+1-xk)=aHdk 在一维精确搜索时,当ji时, gi+1Tdj= gj+1Tdj+,gi+1Tdj= gj+1Tdj+ (gj+2T

6、dj-gj+1Tdj)+ (gj+3Tdj-gj+2Tdj)+(gi+1Tdj-giTdj),d1,d2,d3,g1,g2,g3,无约束间接搜索方法,三.共轭梯度法,性质2: 设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,

7、要证明21=0。 由d0THd2=0, 得21=-d0THg2/d0THd0. 设xi+1=xi+aidi , 则： g1-g0=(Hx1+b)-(Hx0+b)=H(x1-x0)=a0Hd0 d0THg2=g2THd0=g2T(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)

8、=-g1Tg1, a1=g1Tg1/d1THd1, 所以， g2Tg1=0。 g2Tg0=(g1+a1Hd1)g0=g1Tg0+a1d1THg0=-g1Td0-a1d1THd0=0 所以：d0THg2=（g2Tg1-g2Tg0)/a0=0 21=0 其余类推,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(x

9、i)=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 gi+1-gi=H(xi+1-xi)=aHdi gi+1=gi+aHdi diTgi+1=diTgi+adiTHdi=0, 由di=-gi+i-1di-1，a=giTgi /diTHdi gi+1Tgj=giTgj+adiTHgj=giTgj+adiTH(-dj+ j-1dj-1) = giTgj-adiTHdj

10、 当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处, 取搜索方向 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-

11、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) 算法,初始化. g0= f(x0), 选择d0=-g0. 如果|gk|eps, 结束. 一维搜索 xk+1=xk+ak dk :min f(xk+ak dk). k=gk+1Tgk+

12、1/gkTgk, 选择dk+1=-gk+1+ kdk. k=k+1,转步2.,(3) 算法分析,1.程序简单. 2.仅需一次导数,计算量比牛顿法小,效率比梯度法高. 3.适用于维数较高(50以上),易于求一阶导数的目标函数.,无约束间接搜索方法,四.变尺度方法(拟牛顿法),(1) 算法思想,牛顿法具有较高的收敛速度,问题是计算Hesse矩阵的逆, 需要大的计算量,特别是变量数目较大时是这样的. 变尺度方法(拟牛顿法)就是用一种迭代的方法近似计算 Hesse矩阵的逆,减小了牛顿法的计算量.,Xk+1= Xk+a dk, dk=-H-1(Xk) f(Xk),算法迭代形式:,f(X)f(Xk+1)+

13、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 拟牛顿方程 Hk+1sk=yk , sk= Xk+1- Xk, yk=gk+1- gk 由Hk+1-1yk=sk - Ak+1yk=sk, Ak+1=Hk+1-1,

14、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=Akyk Akyk+askskTyk+ bAkykykTAkTyk=sk, 选u=sk, v=Akyk 取a=1/skTyk, b=-1/ykTAkTyk=-1/ykTAkyk 时, (Ak对称正定) 上面拟牛顿方程成立. 于是, Ak+1=Ak+skskT/skTyk - AkykykTAk/yk

15、TAkyk, -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-Fletcher-Goldfarb-Shanno) 1970年各自

16、独立完成,上述公式需要进一步求逆.,无约束间接搜索方法,四.变尺度方法(拟牛顿法),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的正定性.,一般来说,希望如果原目

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