最优化方法第二章-线搜索算法-最速下降法

下降算法Newton法最速下降法一维搜索三四二共轭梯度法一五多尺度法（拟Newton法）二、最速下降法从而得到第k+1次迭代点，即步长由精确一维搜索得到。k假设f连续可微，取()kkdfx0()min()kkkkkfxdfxd1+()kkkkkkkxxdxfx负梯度方向是函数值减少最快的方向。()kkdfx线搜索方向()()cos((),)Tkkkfxdfxdfxd单位向量0x:0k(),*kkfxxx()kkdfx(1)选定某一初始点，并令(2)若，否则转（3）；(4)由精确一维搜索确定步长步长，即由一个极小化问题求得最佳步长最速下降法的计算流程0(3)kmin()kkfxd1,1,kkkkxxdkk令转（2）。二、最速下降法最速下降法可以用来求解系数矩阵正定线性方程组。1()2TfxxAxbx()0fxAxb2212121min()224,fxxxxxx001+4+=12xd，00()=+=1+4,12fxdf'0=()8020,例1.利用最速下降法求解令22=1+421221+41241+4解：函数的梯度为1212224(),2+4xxfxxx第1次迭代：取初始向量01,1.Tx04,2fx004=,2dfx2=402030=1/4,得二、最速下降法112++=1/2+2xd，11()=+=2+,1/2+2fxdf'0=()105,令22=2+21/2+222+1/2+242+,111=,2dfx2=5511/2得1000142=+=+1/4=121/2xxd，第2次迭代：11,2fx1=1/2,2111215/2=+=+1/2=1/223/2xxd，22,1fx继续迭代可得到函数的近似最优解……二、最速下降法最速下降法的收敛性分析(收敛性定理)设目标函数f(x)连续可微，且水平集有界，则最速下降法或者在有限迭代步后终止；或者得到点列，它的任何聚点都是f(x)的驻点。(推论)在收敛定理的假设下，若f(x)为凸函数，则最速下降法或在有限迭代步后达到最小点；或得到点列，它的任何聚点都是f(x)的全局最小点。0()()Lxfxfxkxkx二、最速下降法最速下降法在两个相邻点之间的搜索方向是正交的。最速下降法向极小点逼近是曲折前进的，这种现象称为锯齿现象。令利用精确一维搜索，可得由此得出最速下降法特征：相邻两次迭代的方向互相垂直。()(),kkfxd'()()0kkTkkkfxdd0=()kkTkkfxdd()kkfxd+1=()kTkdd+1=()kTkfxd影响收敛速度！！二、最速下降法0x1x2x0d1d2d在最速下降法中，利用精确一维搜索求最佳步长，使得相邻两次迭代的搜索方向总是垂直的，使得逼近极小点过程是“之”字形，这样从任何一个初始点开始，都可以很快到达极小点附近，但是越靠近极小点步长越小，移动越慢，导致最速下降法的收敛速度很慢。实际运用中，在可行的计算时间内可能得不到需要的结果。最速下降法收敛速度慢！二、最速下降法用于二次函数时的收敛速度分析0x{}kx0k212110.kx定理：二次函数A为对称正定，分别为其最小和最大特征值，从任意初点出发，对二次函数，用最速下降法产生的序列，对于有1(),2TfxxAx12,由于而函数的极小点恰好是。故最速下降法对于二次函数关于任意初始点均收敛，而且是线性收敛的。1()2TfxxAx122121()()(),kkfxfx0221121kkxx*0x二、最速下降法对正定二次函数，用最速下降法产生的点列：偶数项点列均在一条直线上，奇数项点列也均在一条直线上，且都过最优点。分析：因为相邻搜索方向正交，0242//////...//kdddd20,ktdtdt与k有关20kAxtAx(())kkkdfxAx20.kxtx-1.5-1-0.500.511.5-15-10-50510152212()10fxxx二、最速下降法最速下降法收敛性的几何意义（对二次函数）考虑具有对称正定矩阵的函数12,,0,fxxcc函数的等值线为其中22112211()22TfxxAxxx1200A210改写为：22122212122xxcc二、最速下降法12c22c121222c22c0x1x这是以和为半轴的椭圆从下面的分析可见两个特征值的相对大小决定最速下降法的收敛性。（1）当时，等值线变为圆此时因而由上述定理知：212101100||||0xx即只需迭代一步就到了极小点。1x2x（2）当时,等值线为椭圆。此时对于一般的初始点将产生锯齿现象。二、最速下降法（3）当，等值线是很扁的椭圆此时，对于一般的初始点,收敛速度可能十分缓慢，锯齿现象严重。21211120x1x2x优点：理论明确，程序简单，每次的计算量小，所需的存储量小，对初始点要求不严格。缺点：收敛速度并不快，因为最速下降方向仅仅是指某点的一个局部性质。最速下降法的优缺点一些有效算法是通过对它的改进或利用它与其他收敛快的算法结合而得到的，因此它是无约束优化的方法之一。二、最速下降法最速下降法的改进选择不同初始点2212min()25fxxx02,2Tx取初始点，经过10次迭代，得最优解。0(100,0)Tx若取，仅需迭代1次即得最优解。造成锯齿现象与初始点的选择有关，但选取困难！采用不精确的一维搜索采用非精确一维搜索求步长,可使相邻两个迭代点处的梯度不正交，从而改变收敛性。二、最速下降法采用加速梯度法负梯度方向和结合。2kkkdxx由于最速下降法在极小点附近成“锯齿”状，因此下降过程中的搜索方向可适时改变搜索方向的正交特性。开始取负梯度方向，每两步用产生新的搜索方向，然后继续使用最速下降方向。两种方向交替使用，实践效果优于单纯使用最速下降方向。2kkkdxx可以利用最速下降法初期搜索效率高的特性，首先使用最速下降法，然后使用其它局部收敛速度快的计算方式。二、最速下降法三、Newton法算法的基本思路kx1kxfx22()()1()2TkkkTkkkkfxfxfxxxxxfxxxoxx令，有kx略去高阶项21()()()2TTkkkkkkfxQxfxfxxxxxfxxx20kkkQxfxfxxx考虑从到的迭代过程，在点处对函数Tayloy展开：若Hesse矩阵正定，则存在，由此求出二次函数的极小点为：以此作为极小点的一个新的近似。此公式即为多元函数求极值的Newton迭代公式。Qx1kx*xfx2=kkkfxxxfx2kfx12kfx1+12kkkkxxfxfxNewton法Newton法的几何意义目标函数等值线二次函数的等值线为椭圆族。为椭圆中心。椭圆等值线逼近目标函数等值线！Qx1kx三、Newton法fx0x00,:0ffxk12kkkdfxfx步骤1.选定初始点,计算已知目标函数,给定误差限.步骤2.如果，算法停止，，否则转步骤3。步骤3.计算搜索方向kfx*kxxNewton法的计算步骤1,1kkkxxdkk步骤4.令，转步骤2.2=-kkkfxdfx线性方程组步长确定三、Newton法牛顿法收敛性定理设fx二次连续可微，*x是fx的局部极小点，*0fx正定，假定2*fx且海赛阵满足Lipschitz条件，即存在0,使得对于所有1,ijn有：,,nijijGxGyxyxyR其中ijGx是海赛阵的,ij元素．则当0x充分靠近*x时，对于一切,k牛顿迭代有意义，迭代序列kx收敛到*,x并且具有二阶收敛速度。三、Newton法02,2Tx0102022420|,50100050xxfxfxx110200102402121000050xxfxfx*1xx则:221,21225fxxxx解：取初始点代入Newton迭代公式得：此即为问题的最优点例1：用Newton法求的极小点。三、Newton法()=1/2++,TTfxxAxbxc*1.xAb121211()()xxfxfx11(),fxAxb21(),fxA1,nxR111()xAAxb1.Ab当f(x)为正定二次函数时，用Newton法从任意初始点一步迭代可达到最优解。三、Newton法Newton法的优点当初始点离最优解很近时，算法收敛速度快；算法简单，不需要进行一维搜索(确定步长=1)；对正定二次函数，迭代一次就可得到最优解。Newton法的缺点对多数算法不具有全局收敛性，对初值依赖；每次迭代都要计算Hesse矩阵，计算量大；可能不存在或者对应方程组奇异(或病态);可能非正定，可能不是下降方向，算法也可能收敛于最大值点或者鞍点。2-1(())kfx2()kfxkd21()()(())()0kTkkTkkfxdfxfxfx正定：局部逼近三、Newton法Newton法的改进----阻尼Newton法在Newton迭代中，取,加入精确一维搜索：求得最佳步长,得到下个迭代点。12kkkdfxfxminkkfxdk1kkkkxxd设f(x)存在连续二阶偏导数，函数的Hesse矩阵正定。且水平集有界，则阻尼Newton法或者在有限步迭代后终止；或者得到的无穷点列有如下性质(1)为严格单调下降序列；(2)有唯一聚点，它是f(x)的最小点。2()fx0L()()xfxfxkx()kfxkx*x阻尼Newton法的收敛性初值要求三、Newton法例：用阻尼牛顿法求解下列问题：其中取初始点为允许误差222121min()(1)2(),fxxxx12(,),Txxx0(0,0),Tx0.1.解：212112212(1)8()(),4()xxxxfxxx22212111168()28(),84xxxxfxx故00()(2,0),()2,Tfxfx2210020120(),[()].04014fxfx第一次迭代，牛顿方向为21000[()]()(1,0),Tdfxfx从初始点出发沿方向作一维搜索，即求0d24000min()min(1)2,fxd的最优解，得到01.2令1000(12,0).Txxd三、Newton法第二次迭代：10()(0,1),()1,Tfxfx2211184111(),[()].44124fxfx