第6章 无约束问题的优化方法

72第6章无约束问题的优化方法§6.1最速下降法和牛顿法6.1.1最速下降法的基本原理、计算步骤和特点基本原理：考虑无约束问题nRxxf),(min从某一点出发，选择一个目标函数值下降最快的方向，可以尽快达到极小点．1847年法国数学家Cauchy提出了最速下降法．后来，Curry等人作了进一步研究．最速下降方向是目标函数的负梯度方向：)(xfd最速下降法的迭代公式：)()()1(kkkkdxx)(kd取为在点)(kx处的最速下降方向：)()()(kkxfdk为进行一维搜索的步长，满足：)(min)()()(0)()(kkkkkdxfdxf计算步骤：(l)给定初点nRx)1(，允许误差0，置1k.(2)计算搜索方向)()()(kkxfd.(3)若)(kd，则停止计算；否则，从)(kx出发，沿)(kd进行一维搜索，求k，使)(min)()()(0)()(kkkkkdxfdxf(4)令)()()1(kkkkdxx,置1:kk，转步骤（2）.例1解问题22212)(minxxxf初点Tx)1,1()1(，10/1.（最优解Tx)0,0(*）第1次迭代：目标函数在点x处的梯度2124)(xxxf令搜索方向24)()1()1(xfd7352416)1(d从)1(x出发，沿方向)1(d进行一维搜索，求步长1，即22)1()1(0)21()41(2)()(mindxf令0)('(一般应采用不精确一维搜索求解)，解得18/51在直线上的极小点：9/49/1)1(1)1()2(dxx第2次迭代：9/89/4)()2()2(xfd5/54)2(d22)2()2(0)21(8116)41(812)()(mindxf解得12/5227/227/2)2(2)2()3(dxx第3次迭代：27/427/8)()3()3(xfd27/54)3(d2222)3()3(0)21(274)41(278)()(mindxf解得18/53412432)3(3)3()4(dxx这时有52438)4(d满足精度要求，得到近似解412432x最速下降算法的特点：最速下降算法在一定条件下是收敛的．最速下降法产生的序列是线性收敛的，而且收敛性质与极小点处Hesse矩阵)(2xf的特征值有关．74定理1:设)(xf存在连续二阶偏导数，x是局部极小点，Hesse矩阵)(2xf的最小特征值0a，最大特征值为A，算法产生的序列}{)(kx收敛于点x，则目标函数值的序列)}({)(kxf以不大于2aAaA的收敛比线性地收敛于)(xf.最速下降法存在锯齿现象：从局部看，最速下降方向确是函数值下降最快的方向．从全局看，由于锯齿现象的影响，即使向着极小点移近不太大的距离，也要经历不小的弯路，使收敛速率大为减慢．注1：最速下降法并不是收敛最快的方法，从全局看，它的收敛是比较慢的．注2：最速下降法一般适用于计算过程的前期迭代或作为间插步骤．当接近极小点时，使用最速下降法达到迭代终止，这样做并不有利．6.1.2牛顿法的基本原理、计算步骤和特点1.牛顿法)(xf在点)(kx的二阶Taylor展开为))(()(21)()()()()()()(2)()()()(kkTkkTkkxxxfxxxxxfxfxxf求)(x的平稳点，令0)('x,即0))(()()()(2)(kkkxxxfxf(1)设)()(2kxf可逆，得到牛顿法的迭代公式)()()(1)(2)()1(kkkkxfxfxx产生序列}{)(kx，在适当的条件下，这个序列收敛．例2：解问题：2241)1min(xx(最优解Tx)0,1()目标函数的梯度和Hesse矩阵分别为752312)1(4)(xxxf200)1(12)(212xxf取初点Tx)1,0()1(.第l次迭代:24)()1(xf20012)()1(2xf03/1242001210)()(1)1(1)1(2)1()2(xfxfxx第2次迭代:027/32)()2(xf2009/48)()1(2xf09/5)()()2(1)2(2)2()3(xfxfxx继续迭代，得到027/19)4(x,081/65)5(x,…注3：当牛顿法收敛时，有下列关系：2)()1(xxcxxkkc是某个常数．因此，牛顿法至少2级收敛，收敛速率是很快的．注4：对二次凸函数，用牛顿法求解经1次迭代即达极小点．设有二次凸函数:cxbAxxxfTT21)(用极值条件求解：令0)(bAxxf得到最优解bAx1用牛顿法求解：任取初始点)1(x，根据牛顿法的迭代公式有bAbAxAxxfAxx1)1(1)1()1(1)1()2()()(以后还会遇到一些算法，把它们用于二次凸函数时，类似于牛顿法，经有限次迭代必达到极小点．这种性质称为二次终止性．注5:当初始点远离极小点时，牛顿法可能不收敛．牛顿方向)()()(1)(2kkxfxfd不一定是下降方向，经迭代，目标函数值可能上升.即使目标函数值下降，得到的点)1(kx也不一定是沿牛顿方向的最好点或极小点．对牛顿法进行修正，提出了阻尼牛顿法．2.阻尼牛顿法阻尼牛顿法增加沿牛顿方向的一维搜索，迭代公式:76)()()1(kkkkdxx)()()(1)(2)(kkkxfxfd为牛顿方向.k由一维搜索得到:)(min)()()()()(kkkkkdxfdxf由于阻尼牛顿法含有一维搜索，因此每次迭代目标函数值一般有所下降（绝不会上升）．可以证明，阻尼牛顿法在适当的条件下具有全局收敛性，且为2级收敛．阻尼牛顿法的计算步骤：(l)给定初点)1(x，允许误差0，置1k.(2)计算)()(kxf，1)(2)(kxf.(3)若)()(kxf，则停止计算；否则，令)()()(1)(2)(kkkxfxfd（4）从)(kx出发，沿)(kd进行一维搜索，求k，使)(min)()()(0)()(kkkkkdxfdxf(5)令)()()1(kkkkdxx,置1:kk，转步骤（2）.3.牛顿法的进一步修正原始牛顿法和阻尼牛顿法有共同缺点：（1）可能出现Hesse矩阵奇异的情形，因此不能确定后继点；（2）即使)(2xf非奇异，也未必正定，因而牛顿方向不一定是下降方向，就可能导致算法失效．例3:用阻尼牛顿法求解：222141)1()(minxxxxxf取初始点Tx)0,0()1(.在点)1(x处，有20)()1(xf，2110)()1(2xf牛顿方向02202110)()(1)1(1)1(2)1(xfxfd从)1(x出发，沿)1(d作一维搜索．令116)()(4)1()1(dxf,则01.用阻尼牛顿法不能产生新点，而点Tx)0,0()1(并不是问题的极小点．原因在于Hesse矩阵)()1(2xf非正定．为使牛顿法从任一点开始均能产生收敛于解集合的序列}{)(kx，要做进一步修正,克服Hesse矩阵非正定．考虑（1）式，记搜索方向)()(kkxxd，得到77)()()()()(2kkkxfdxf(2)阻尼牛顿法所用搜索方向是上述方程的解：)()()(1)(2)(kkkxfxfd解决Hesse矩阵)()(2kxf非正定问题的基本思想：修正)()(2kxf，构造一个对称正定矩阵kG.在（2）中，用kG取代矩阵)()(2kxf,得到方程)()()(kkkxfdG(3)解此方程，得到在点)(kx处的下降方向)()(1)(kkkxfGd构造矩阵kG的方法之一:令IxfGkkk)()(2k是一个适当的正数．只要k选择得合适，kG就是对称正定矩阵．注6:当)(kx为鞍点时，有0)()(kxf及)()(2kxf不定此时（3）式不能使用．这时)(kd可取为负曲率方向：0)()()(2)(kkTkdxfd当)()(2kxf不定时，这样的方向必定存在，而且沿此方向进行一维搜索必能使目标函数值下降．§6.2共轭梯度法6.2.1共轭方向的基本原理和定理共轭梯度法是基于共轭方向的一种算法．定义1：设A是nn对称正定矩阵，若nR中的两个方向)1(d和)2(d满足0)2()1(AddT则称这两个方向关于A共轭，或称它们关于A正交．若)1(d，)2(d，…，)(kd是nR中k个方向，它们两两关于A共轭，即满足jiAddjTi,0)()(则称这组方向是A共轭的，或称它们为A的k个共轭方向．注1：如果A为单位矩阵，则两个方向关于A共轭等价于两个方向正交．共轭是正交概念的推广．78注2：如果A是一般的对称正定矩阵，)(id和)(jd关于A共轭，也就是方向)(id与方向)(jAd正交．共轭的几何意义（以正定二次函数为例）：二次函数)()(21)(xxAxxxfT函数)(xf的等值面cxxAxxT)()(21是以x为中心的椭球面，x是极小点.设)1(x是在某个等值面上的一点，该等值面在点)1(x处的法向量)()()1()1(xxAxf又设)1(d是这个等值面在)1(x处的一个切向量．记)1()2(xxd)1(d与)()1(xf正交，即0)()1()1(xfdT，因此有0)2()1(AddT即等值面上一点处的切向量与由这一点指向极小点的向量关于A共轭.依次沿着)1(d和)2(d进行一维搜索，则经两次迭代必达到极小点．共轭方向的重要性质:定理1:设A是n阶对称正定矩阵，)1(d，)2(d，…，)(kd是k个A共轭的非零向量，则这个向量组线性无关．定理2（扩张子空间定理）:设有函数cxbAxxxfTT21)(其中A是n阶对称正定矩阵，)1(d，)2(d，…，)(kd是A共轭的非零向量．以任意的)1(x为初始点，依次沿)1(d，)2(d，…，)(kd进行一维搜索，得到点)2(x，)3(x，…，)1(kx，则)1(kx是函数)(xf在线性流形kBx)1(上的惟一极小点．特别地，当nk时，)1(nx是函数)(xf的惟一极小点．其中79),(,|1)(ikiiikdxxB是)1(d，)2(d，…，)(kd生成的子空间．推论:在定理2的条件下，必有,0)()()1(jTkdxfkj定理2表明:对于二次凸函数，若沿一组共轭方向（非零向量）搜索，经有限步迭代必达到极小点．6.2.2用于正定二次函数的共轭梯度法共轭梯度法最初由Hesteness和Stiefel于1952年提出．本节重点介绍Fletcher-Reeves共轭梯度法(FR法)．共轭梯度法的基本思想:把共轭性与最速下降方法相结合，利用已知点处的梯度构造一组共轭方向，沿这组方向进行搜索，求出目标函数的极小点．根据共轭方向的基本性质，这种方法具有二次终止性．考虑如下正定二次函数优化问题的求解方法:cxbAxxxfTT21)(min令)(xfg.任意给定一个初始点)1(x,计算出目标函数)(xf在这点的梯度，01g,则停止计算；否则，令1)1()1()(gxfd沿方向)1(d搜索，得到