第二章无约束优化问题的算法.

沈阳大学教案课程名称优化理论与方法编写时间：20年月日第二章第1页授课章节第二章无约束优化问题的算法目的要求常用的线性搜索法；无约束最优化方法重点难点常用的线性搜索法；无约束最优化方法第一节常用线性搜索法在算法的迭代格式)()()1(kkkkdxx中，在假设迭代点)(kx和下降搜索方向)(kd为已知的情况下，求步长k，使)()()()()()()1(kkkkkxfdxfxf成立。下面介绍几种求步长k的算法。一、直接法（0.618法）（求步长）单谷函数（下单峰函数）：设*t为一元函数)(t的极小点，若21tt，当*2tt时，必有)()(21tt；当*1tt时，必有)()(21tt，则称)(t为单谷函数（一个谷）。１搜索区间的确定：搜索区间的选取采取如下算法—进-退算法：给定初始点t，初始步长h。(1)计算)(),(htt；(2)若)()(htt，搜索成功，歩长加倍，若)3()(htht，则]3,[],[htaba，否则步长继续加倍；(3)若)()(htt，搜索失败，后退4h步长，若)4()(htt，则],4[],[hthtba，否则继续加倍后退步长。２0.618算法的原理沈阳大学教案课程名称优化理论与方法编写时间：20年月日第二章第2页规定nnll1020010212llllllabtbatl解得618.0。由此可得))(1(1abat)(2abat３0.618算法Step1确定)(t的初始搜索区间],[ba（进-退搜索法）、精度；Step2计算))(1(1abat，)(11t；Step3计算)(2abat，)(22t；Step4若21，则令,1ta如果ab，取2*bat，停止计算。否则令21tt，21，转Step3，（此时,1ta21tt，在新的],[ba区间计算2t）；Step5若21，则令2tb，如果ab，取2*bat，停止计算。否则令12tt，12，计算))(1(1abat，)(11t，转Step4。注意：21tt与12tt在计算机语言中不是一回事，是一个赋值的过程。二、精确线性搜索法（解析法）求步长k，满足)(min)()()(0)()(kkkkkdxfdxf。令)()()()(kkdxf，0)()()()()(kTkkddxf设包含)(t的极小值点*t的搜索区间为],[ba，即],[*bat，在搜索区间内给定三点210ttt，且满足)()()(210ttt，不妨取btbatat210,2,。沈阳大学教案课程名称优化理论与方法编写时间：20年月日第二章第3页令2210)(tataatp是三点)2,1,0))((,(ittii的拟合抛物线，且设3t是抛物线的极小点，即（如图）2132aat)()()()()()(21210102021221201202202221tttttttttttttttttt结束条件：（1）13tt（2）)()(13tt（3）若)(1t较大，)()()(113ttt上述三条中的任意一条都可以作为终止准则。如果不满足终止条件，取三点310ttt，或213ttt，继续搜索。三、不精确线性搜索法618法或解析法都可以取到)(t精确近似极小点，每次迭代都可以保证使目标函数是下降的，但计算量大。不精确线性搜索法不够精确但计算量较小。为确保目标函数下降，步长不能太大，同时步长又不能太小，所以给一个限定范围。1Goldstein准则取步长满足下式)()()()()()()()()()()(0kTkkkkkkkTkkdxftdtxfxfdxft上式等价于下述两个不等式沈阳大学教案课程名称优化理论与方法编写时间：20年月日第二章第4页)()()()()()()()(kkkkkTkkdtxfxfdxft（2.6）)()()()()()()()(kTkkkkkkdxftdtxfxf（2.7）等价于kkTkktdgt)()0()(kkTkktdgt)()0()(等价于kktt)0()0()(kktt)0()0()(注：对上式的理解，可以当)(xf是一元函数时的特殊情况去理解。夹在两直线tt)0()0()(和tt)0()0()(与曲线)()()()(kktdxft相交两点之间的t满足条件式(2.6)和(2.7)，称其为可接受区间。2Wolfe准则在Goldstein准则中，)(t的极小点在可接受区间以外，为克服这一缺点，Wolfe准则提出一个式(2.7)的替补条件，即)()()()()()()(kTkkTkkkdxfddtxf(2.9)沈阳大学教案课程名称优化理论与方法编写时间：20年月日第二章第5页可接受区间是切线l的切点、直线tt)0()0()(与曲线的交点之间的t的取值区间。说明：越小，线性搜索越精确，但计算量大。第二节最速下降法对下降方向的确定。条件：目标函数)(xf连续可微，0)()(kxf。分析：)(xf在)(kx点处的一阶泰勒展开为)()()()()()()()()()(kkTkktktdodxftxftdxf由函数梯度反方向是函数下降最快的方向（由二元函数可以看出），所以令Tkkxfd)()()(则)()()()())(()()()()()()(kkTkkxktdoxfxftxfxftxf当0t满足一定条件时可以保证)())(()()()(kxkxfxftxf。说明：（1）0)()()1(kTkdd这是由于))(()()()(kkxftxft，求步长t，使)(min0tt。令0)(t，即0)()()())(()()()1()()()(kTkkTkkxfxfxfxftxft即0)()()1(kTkdd。（2）最速下降法收敛速度慢。这是由于0)()()1(kTkdd，所以相邻两下降方向是相互垂直的，即下降是锯沈阳大学教案课程名称优化理论与方法编写时间：20年月日第二章第6页齿形状，越接近极小点，锯齿现象越严重，影响收敛速度。（3）该方法易实现，简单，适用于一次逼近的算法，适用于距离极小点较远时使用，在接近极小点时使用其它有效算法。第三节共轭梯度法利用梯度设为下降方向，建立迭代公式，求最优解的方法。说明：该方法易实现，且储存需求小，适用于大规模优化问题的算法。一、两变量正定二次函数的极小化问题设RRf2:，且cxbAxxxfTT21)(其中A为正定矩阵。下面讨论从任意初值点)0(x出发，最多经过两步迭代可达到其极小点（最优解(*)x）。思路：选取与)()0()0(xfd线性无关的向量)1(d，且保证0)()0((*)dxfT和0)()1((*)dxfT（这里)1(1)1()2((*)dxxx），推出0)((*)xf。分析：任意初值点)0(x，令下降方向为)(*)0(xfd，迭代公式)0(00)1(dxx，有线性搜索法确定0，且满足0)()()0()1(0dxfT。假若)1(1)1()2((*)dxxx（最优解(*)x），则必有0)((*)(*)bAxxf0)()1(1)1(bdxA0)1(1)1(AdbAx0)()1(1)1(Adxf左乘Td)0(0)()1()0(1)1()0(AddxfdTT这里要求0)1()0(AddT。沈阳大学教案课程名称优化理论与方法编写时间：20年月日第二章第7页由于0)()0()1(dxfT，得)()1(xf与)0(d是线性无关的，所以向量)1(d可由)()1(xf和)0(d线性表示（因为是二维空间），设)0()1()1()(tdxfd左乘AdT)0(得0)()0()0()1()0()1()0(AdtdxAfdAddTTT由于A是正定矩阵，所以0)0()0(AddT，即得)0()0()1()0()(AddxAfdtTT则)0()0()0()1()0()1()1()()(dAddxAfdxfdTT。可以证明)0()1(,dd是线性无关的，因为如果线性相关，)1(d可由)0(d线性表示，)0()0()1(dd，)0()0()0()1()0()1(])([)(dAddxAfdxfTT，得)()1(xf和)0(d线性相关，矛盾。由线性搜索法得1，且满足0)()()1((*)1dxfT，由于0)()1()0(1)1()0(AddxfdTT)1(d，可得0)()0((*)dxfT，即0),()()1()0((*)ddxfT故0)((*)xf，即(*)x是最优解。以下讨论的是n个变量的二次型问题的最优化的问题二、共轭方向的概念与性质１概念：共轭向量组：（１）A为nn阶正定矩阵；（２）mppp,,,21为nR中m个非零向量。若),,2,1,,(0mjijjAppjTi则称mppp,,,21为A共轭向量组（或为A沈阳大学教案课程名称优化理论与方法编写时间：20年月日第二章第8页正交向量组）。注：当IA时，共轭性即为通常的正交性。２性质：定理２.２设A为A为nn阶正定矩阵，mppp,,,21为nR中m个非零向量，且关于A两两共轭向量组，则mppp,,,21线性无关。证明：设存在一组数m,,,21，使得mmppp2211成立，用),,2,1(mjApTj左乘，得),,2,1(0mjAppjTjj，由于A是正定的，0jp，即0jTjApp，所以0j，故mppp,,,21线性无关。引理２.１（n维直交定理）设mppp,,,21为线性无关的n维向量，若nRx，且),,2,1(0mjpxjT，则0x。定理２.３设cxbAxxxfTT21)(，mppp,,,21为任意一组关于A两两共轭向量组，则从任意初始点)1(x出发，依次沿mppp,,,21执行线性搜索，到达)(mx至多n步迭代得到极小最优解*x。证明思路：（１）设迭代公式设为),2,1,(*)()1(knmpxxkkkk；（２）证明0)(1nxf。kkkkpxx*)()1(kkkkkppx*1*1)1(＝…kkkkjjjjjppppx*1*11*1*)(bAxxfkk)1()1()(kkkkjjjjjApApApApbAx*1*11*1*)(沈阳大学教案课程名称优化理论与方法编写时间：20年月日第二章第9页kkkkjjjjjApApApApxf*1*11*1*)(kTjkkTjkjTjjjTjjjTjkTjAppAppAppAppxfpxfp1*11*111*11*1)1(1)()(0)()(1*11*111*11*1)1(1nTjnnTjnjTjjjTjjjTjnTjAppAppAppAppxfpxfp这里nj2。0)(1jTjxfp是由于在搜索步长时满足0)()()(kTkkppxf，即0)()()1(*kTkkpxf；)(01*nkjAppkTjn是由于mppp,,