工优第四章

1第四章无约束最优化方法本章主要内容：§1最速下降法§2牛顿法§3共轭方向法§4共轭梯度法§5变尺度法——DFP法和BFGS法2目的是找中的一点，使对，均有，称为(1)的全局极小点。min():(1)nfxfRR无约束最优化问题：*()()fxfxnR*xnxR求解(1)的计算方法称为无约束最优化方法。*x3(),min()min(),(),.nxDxRfxxDfxFxFxothers其中无约束最优化方法应用广泛，理论也比较成熟；可将约束优化问题转化为无约束优化问题来处理；最优化方法中的基本方法---无约束优化方法解析法无约束优化方法直接法本章介绍解析法4在以上步骤中，选取步长可选用精确一维搜索或者非精确一维搜索，下降方向的选取正是下面我们要介绍的，下降方向选取的不同，得到不同的算法。线搜索迭代法的步骤步1：选定初始点0x，误差精度0，置0;k步2：确定搜索方向kd；步3：判断是否收敛.若满足kd，停止迭代，*kxx；否则，从kx出发，沿方向kd计算步长k，以产生下一个迭代点1kx；步4：置:1kk，转步2继续进行迭代.5最速下降法是求多元函数极值的最古老的数值算法，早在1847年法国数学家Cauchy提出该算法，后来Curry作了进一步的研究。该方法直观，简单，计算方便，而且后来的一些新的有效的方法大多数是对它的改进，或受它的启发而得到的。最速下降法6从而得到第k+1次迭代点，即步长k最速下降法负梯度方向这是函数值减少最快的方向假设f连续可微，()kkdfx0()min()kkkkkfxdfxd1+()kkkkkkkxxdxfx由精确一维搜索得到。7最速下降法x(k)x*d(k)=－f(x(k))x(k+1)d(k+1)=－f(x(k+1))瞎子下山：？向，再下降一步。由于他看不到哪里是山谷，不可能沿直接指向山谷的路线走，他只能在当前位置上，靠手杖作局部探索，哪里最陡就往哪里前进一步，然后在新的位置上再用手杖寻找最陡方8步1：选定初始点0x，误差精度0，置0;k步2：计算()kkdfx；步3：判断是否收敛.若满足kd，停止迭代，*kxx；否则，由一维搜索计算步长k0argmin()kkkfxd；最速下降法的迭代格式步4：令1kkkkxxd，置:1kk，转步2.9算法框图x1,ε0,k=1||▽f(xk)||ε?Yesstop.x*=xkNodk=－▽f(xk)解minf(xk+λdk)s.t.λ0得xk+1=x(k)+λkdkk=k+1最速下降法框图102212121min()224,fxxxxxx001+4+=12xd，00()=+=1+4,12fxdf'0=()8020,例利用最速下降法求解令22=1+421221+41241+4解：函数的梯度为1212224(),2+4xxfxxx第1次迭代：取01,1,=0.5.Tx04,2fx0004=,||||=250.52dfxd2=402030=1/4,得11112++=1/2+2xd，11()=+=2+,1/2+2fxdf'0=()105,令22=2+21/2+222+1/2+242+,1111=,||||50.5,2dfxd2=5511/20=1/4,得04=,2d1000142=+=+1/4=121/2xxd，第2次迭代：11,2fx1=1/2,2111215/2=+=+1/2=1/223/2xxd，22,1fx1212224(),2+4xxfxxx12225/2+2+=3/2xd，22()=+=5/2+2,3/2fxdf'0=()205,令22=5/2+223/225/2+23/245/2+22222=,||||50.5,1dfxd2=10527/4得第3次迭代：2=1/4,32225/223=+=+1/4=3/215/4xxd，31/2,1fx25/2=3/2x，22,1fx继续迭代可得到函数的近似最优解。13最速下降法的收敛性分析设目标函数f(x)连续可微，且水平集有界，则最速下降法或者在有限迭代步后终止；或者得到点列，它的任何聚点都是f(x)的驻点。在收敛定理的假设下，若f(x)为凸函数，则最速下降法或在有限迭代步后达到最小点；或得到点列，它的任何聚点都是f(x)的全局最小点。0()()Lxfxfxkxkx收敛性定理：推论：14最速下降法在两个相邻点之间的搜索方向是正交的。最速下降法向极小点逼近是曲折前进的，这种现象称为锯齿现象。除特殊的目标函数和极特殊的初始点外，这种现象都会发生。令利用精确一维搜索，可得由此得出1.相邻两次迭代的方向互相垂直最速下降法的两个特征()(),kkfxd'()()0kkTkkkfxdd0=()kkTkkfxdd()kkfxd+1=()kTkdd+1=()kTkfxd15最速下降法的两个特征x(0)x(1)x(2)在最速下降法中，利用精确一维搜索求最佳步长，使得相邻两次迭代的搜索方向总是垂直的，从而逼近极小点过程是“之”字形，这样从任何一个初始点开始，都可以很快到达极小点附近，但是越靠近极小点步长越小，移动越慢，导致最速下降法的收敛速度很慢。实际运用中，在可行的计算时间内得不到需要的结果。最速下降法收敛速度慢162.对正定二次函数，用最速下降法产生的点列：偶数项点列均在一条直线上，奇数项点列也均在一条直线上，且都过最优点.最速下降法的两个特征17对正定二次函数，用最速下降法产生的点列：偶数项点列均在一条直线上，奇数项点列也均在一条直线上，且都过最优点.则：12TfxxQx分析：因为相邻方向正交，0242//////...//kdddd20kQxtQx(())kkkdfxQx因为20,ktdtd20.kxtx18优点：理论明确，程序简单，每次的计算量小，所需的存储量小，对初始点要求不严格。缺点：收敛速度并不快，因为最速下降方向仅仅是指某点的一个局部性质。最速下降法相邻两次搜索方向的正交性，决定了迭代全过程的搜索路线呈锯齿状，远快近慢。最速下降法的优缺点最速下降法不是好的实用算法，但是一些有效算法是通过对它的改进或利用它与其他收敛快的算法结合而得到的，因此它是无约束优化的方法之一。192212min()25fxxx02,2Tx04,100,Tfx'0()8(24)5000(2100),为了清除最佳步长最速下降法中两个搜索方向正交的不良后果，提出了许多改进的方法，如：(1)选择不同初始点例令最速下降法的改进取初始点22()=(24,2100)=24252100f00=4,100Tdfx第1次迭代00+=24,2100Txd06260.0200307231252得10020+1.919877,0.307178510Txxd20然后再从开始新的迭代，经过10次迭代，得最优解计算中可以发现，开始几次迭代，步长比较大，函数值下降将较快，但当接近最优点时，步长很小，目标函数值下降很慢。1x*(0,0)Tx121.919877,0.307178510Tx21如果不取初点为而取0(2,2)Tx0(100,0)Tx*(0,0)Tx000122,50200,0,Tfxxx一步就得到了极小点。可见：造成锯齿现象与初始点的选择有关，但怎样选一个初始点也是一件困难的事。01,20(100,0),Tx00==200,0,Tdfx220='1002002500400100200dd22(100200,00)=1002002500,f1000+100,0+1/2200,0=0,0TTTxxd第1次迭代虽然后一初始点较前一初始点离最优点远，但迭代中不含上面出现的锯齿现象。22采用非精确一维搜索求步长,可使相邻两个迭代点处的梯度不正交，从而改变收敛性。对于最速下降法，有时为了减少计算工作量，采用固定步长，称为固定步长最速下降法。但到底取多大，没有统一的标准，取小了，收敛太慢，而取大了，又会漏掉极小点。（2）采用不精确的一维搜索：最速下降法的改进232kkkdxx（3）采用加速梯度法：由于最速下降法在极小点附近成“锯齿”状，因此下降过程中的搜索方向可取下两步继续用最速下降方向即负梯度方向。Shah等人于1964年提出了一种“平行切线法”（简记为PARTAN法），又称加速梯度法。最速下降法的改进负梯度方向和结合2kkkdxx这两种方向交替使用，效用要比最速下降法好的多。24用于二次函数时的收敛速度分析0x{}kx0k21211,0.kx则定理：二次函数Q为对称正定，分别为其最小和最大特征值，从任意初点出发，对二次函数，用最速下降法产生的序列，对于有()1/2,TfxxQx12,由于而函数的极小点恰好是。故最速下降法对于二次函数关于任意初点均收敛，而且是线性收敛的。1()2TfxxQx122121()()(),kkfxfx0221121kkxx*0x25下面说明最速下降法收敛性的几何意义。考虑具有对称正交矩阵的函数12,,0,fxxcc函数的等值线为其中用于二次函数时的收敛速度分析22112211()22TfxxQxxx1200Q210改写为：22122212122xxcc2612c22c121222c22c0x1x这是以和为半轴的椭圆从下面的分析可见两个特征值的相对大小决定最速下降法的收敛性。（1）当时，等值线变为圆此时因而由上述定理知：212101100||||0xx即只需迭代一步就到了极小点，这表明最速下降法用于等值线为圆的目标出发时，只需迭代一步就到了极小点。1x2x1x2x（2）当时,等值线为椭圆。此时对于一般的初始点将产生锯齿现象。2210121kkxx27（3）当，等值线是很扁的椭圆此时，对于一般的初始点,收敛速度可能十分缓慢，锯齿现象严重。21211120x1x2x用于二次函数时的收敛速度分析28第四章无约束最优化方法本章主要内容：§1最速下降法§2牛顿法§3共轭方向法§4共轭梯度法§5变尺度法——DFP法和BFGS法29Newton法前面介绍精确一维搜索时介绍了牛顿法，即用目标函数的二次泰勒多项式近似代替函数本身，用二次多项式的极小点近似函数的极小点。这种方法可以推广到多维的情形。求解无约束极小化问题的最古老的算法之一，现在已经发展成一类算法-----Newton型方法。301+12kkkkxxfxfxNewton法1'()=''()kkkkfxxxfx一维