最优化理论与算法(第三章)

1、第三章 牛顿法3.1 最速下降法一、最速下降法在极小化算法中，若每次都以迭代点处的负梯度方向为搜索方向，产生的算法称为最速下降法，它是无约束最优化算法中最简单、最基本的算法。算法描述：1） 给出初始点，允许误差，；2） 计算，若，Stop 令 ；3） 由一维搜索确定步长因子，使得 4） 令，go to 2).二、最速下降算法的收敛性定理3.1 设，则最速下降算法产生的点列的每个聚点均为驻点。证明：设是的一个聚点，则存在子序列，使得 令，由，知是收敛序列，故有界，且 由定理2.6有 故有 。定理3.2 设二次连续可微，且，则对任何给定的初始点，最速下降算法或有限终止，或，或。证明：不妨设，。由定

2、理2.5有 于是 令，由为单调下降序列，则要么，要么 。最速下降算法若采用不精确一维搜索，仍有下列总体收敛性定理。定理3.3 设，则采用不精确一维搜索得到的点列的每个聚点均为驻点。证明：直接由定理2.14可得。注：1) 最速下降算法的收敛性也可由前述关于模式算法收敛性结果定理2.7直接获得；2）最速下降算法的主要优点是方法简单、直观，有好的总体收敛性，但收敛很慢。三、最速下降算法的收敛速度1. 先考虑二次函数情形定理3.4 对极小化问题，其中为对称正定矩阵，分别为的最大与最小特征值。设是最优解，则最速下降算法的收敛速度至少是线性的，且下面的界成立：，其中（为矩阵的条件数）。证明：由，有。故其中

3、使 ， 若设 ， 其中。则有 ，而， 利用这些，可知 ， （要求） 设是的特征值，而是对应得标准特征向量（两两正交的单位向量）。令，则上式可进一步表示为： （将作用到内每一项） （由是标准正交向量组）对，可适当选取，使。事实上，只须令即可求得 从而 。显然单调上升。由，及，即得。由 及 即得 . 再由 最后得 .由，并注意到是正定二次函数（）， 则有。再由为严格凸二次函数（正定二次型），故当且仅当时，由此可推得必有 . 再注意到，则有从而定理第一式得证。下面再证定理第二式，记，。由是对称正定的，故有由，则 故有 ， 注意到： 因而有 最后得 （其中）。 这表明：最速下降算法至少具有线性收敛速度

4、。定理3.5（Kantorovich不等式）设是阶对称正定矩阵，和分别为其最大和最小特征值，则，有。证明：参见袁亚湘等最优化理论与方法第三章附录，略。 以上对特殊形式的二次函数的收敛速度进行讨论，对一般的二次函数利用Kantorovich不等式可得类似的结论，其证明思路如下：设是极小点，则满足且可表示为 记 ，则与仅相差一个常数，它们有相同的最优解，且使用最速下降算法时，每次迭代方向产生的迭代序列均完全相同。现在考察对的极小化，这时最速下降算法的迭代公式为： （这里为最优步长因子）其中。直接计算可得：（由Kantorovich不等式）故有： （1）由（1）即得： （或）。由正定，当且仅当时，利

5、用一致凸性，可证必有：。这表明：算法产生的点列是整体收敛到的。由（1）有： （2）注意到： ，由（2）有 （3）再令（），则，注意到即有： ，从而有： ，（令）最后得： ，定理证毕。当目标函数为非二次函数时，最速下降算法的收敛速度依然是线性的。定理3.6 设满足定理2.8的假设条件，若最速下降算法产生的点列收敛于，则收敛速度至少是线性的。3.2 牛顿法一、牛顿算法的基本思路牛顿算法的基本思路是：利用目标函数在当前迭代点处的二次近似的极小点作为的近似极小点。设是当前迭代点，正定，则记 ，其中，极小化得进而得牛顿算法的迭代公式: .关于牛顿算法的若干评注 牛顿算法可视为椭球范数下的最速下降算法。

6、事实上，欧氏空间中一般范数下的方向导数定义为： （它显然与范数有关）显然，的最优解就是函数在处对应于范数的最速下降方向。容易理解，这个解与所取的范数有关。a) 当取欧氏范数（2范数）时，可证是最速下降方向；b) 若取椭球范数，最速下降方向则为。事实上，即 ，有（意味着为方向导数下界）另一方面，若取时方向导数达到下界，故是对于椭球范数的最速下降方向。 牛顿算法实际上就是非线性方程组的牛顿迭代法。由于等价于求解非线性方程组 设是当前迭代点，若，则是方程组的解，否则将在处线性化，得 将上述线性方程组的解作为 的近似解，得 故有 ，这恰好就是牛顿迭代公式。二、牛顿法的收敛性定理3.7 设，充分靠近极小

7、点，而，正定，若进一步假设Hessian矩阵满足Lipschitz条件。则由牛顿法产生的序列收敛于，且具有二阶的收敛速度。证明：由 及满足Lipschitz条件，可得故有 （*）由于，正定，故当充分靠近时，正定，且有上界。事实上，设是的特征值，且最大，最小，则的特征值为，且，（这里矩阵范数取谱范数）。又特征值是特征多项式系数的连续函数（参见蒋尔雄线性代数P39定理10），故当时，存在m, M使得 ， （相当于特征值一致有界）因而当时 （这里分别表示的最小、最大特征值）。由以上分析及（*）式，则有 （*）只要，则有，即，迭代点列收敛，且由（*）式知，算法具有二阶收敛的速度。 关于算法的评价1）优

8、点：当初始点离最优解很近时，收敛速度快；算法简单；不需要用一维搜索。2) 缺点：局部收敛，不正定时，不能保证牛顿方向是下降方向。事实上，当为正定时，牛顿方向满足：（下降方向），但若非正定，则不能保证是下降方向。由以上分析可知，固定的步长因子不能保证目标函数有合理的改善，甚至不能保证算法下降，因此有必要对牛顿算法作一些改进，一个最直接的改进是：在牛顿算法中加入一维搜索。三、带步长因子的牛顿法阻尼牛顿法1算法1）取初始点，允许误差，置；2）计算，若，停止迭代，；否则 go to 3)；3) 构造牛顿方向：从求出；4）沿进行一维搜索，使得满足：；5）令， 转2）。2总体收敛性定理3.8 设二阶连续可

9、微，且对任意的，存在常数，使得在水平集上满足， ，则在精确一维搜索条件下，带步长因子的牛顿法产生的迭代点列满足：1） 当为有穷点列时，对某个，有；2） 当为无穷点列时，收敛到的唯一极小点。证明：由定理条件知，在上一致凸。故在中若有极小点，则必唯一，且在中的稳定点必是的极小点。下证收敛到的稳定点。由在上一致凸，知是有界闭凸集，再由单调下降，可知，故是有界点列，于是存在极限点及子列使.再由单调有界（有界性是由于：闭有界，且在上连续）可知： （这里是指整个序列）且 （这里是子序列）由精确一维搜索的极小化算法的收敛定理2.7，有 （整个序列） （*）从而 ，即是的稳定点，它也是极小点。现在实际上还只证

10、明了的子序列收敛到，下证整体收敛到。事实上，若不收敛到，则存在一个子序列使（，是给定的正数）注意到是有界点列，故存在收敛子列 ，使 （由闭有界）从而 由（*）式进一步得 从而也是的平稳点,也是极小点，但显然，这与的极小点唯一矛盾，故必有 。在上面证明过程中，直接引用了精确一维搜索的极小化算法的收敛定理2.7，因此必须指出定理2.7的条件是满足的。事实上，1）由有界闭，故在上一致连续，且；2）由 得：。3.3 修正的牛顿法 上面带步长因子的牛顿法实际上还不能克服牛顿算法的全部缺陷，因为还有可能出现：1) 不存在；2）不正定，故可能不是下降方向。为此人们对牛顿法提出了多种方式的修改。一、Golds

11、teinPrice修正方案当非正定时，采用最速下降方向替代牛顿方向。若进一步将搜索方向与负梯度方向的角度准则结合起来，则有这样搜索方向总满足注：按照这种方法选取搜索方向，再加上一维搜索（精确或非精确）可以保证算法的总体收敛性，但也可能失去牛顿法快速收敛的特点。 二、Goldfeld修正方案若不正定，则用来修正。通过适当选取，可以使正定。事实上，只要将取得稍大于的最小特征值的模即可。利用特征值的圆盘定理可以求得最小特征值的模： 注：用此方法可求出，但通常得到的远大于最小特征值的模，导致与相差甚远，这是一个缺陷。而实际求出的全部特征值计算量又太大，因此，这个方法更多的是理论的价值。 三、基于的Ch

12、olesky分解的方案先作的Cholesky分解 然后令 ，其中而，为中对角元，为给定的小正数。注：这种处理方法简单，但有下列缺陷：1） 当不可逆或的主子式为零时，的Cholesky分解不存在（分解过程将进行不下去）。如， 其Cholesky分解不存在。2） 即使的分解存在，其计算过程也可能数值不稳定。如，当时，与均无界，计算过程中小的误差会导致结果的巨大差别。因而数值不稳定，同时还可能出现与的差别很大。如的Cholesky分解为， 由的处理方式得 可见与（从而与）相差甚远。四、Gill 和Murray修正方案GillMurray修正法也称为强迫矩阵正定的Cholesky分解法，它在的分解过程

13、中进行适当修正，使总为正，从而分解过程可以持续下去，但最终得到的分解式不是真正的，而是的近似。其要点在于：1）在分解过程中，增加了保证分解得到的因子矩阵元素一致有界的措施。在过程完成时，得到： （其中是非负对角阵）2）在整个计算过程中，为了保证及因子矩阵元素一致有界，必须对的元素进行调整，否则算法进行不下去，但必须指出的是，所有调整都只涉及的对角元（通常是将其增大），这就保证了： ，即与仅差一个对角阵。3）可以证明，当充分正定时，有。可参阅席少霖著非线性最优化P80，或徐成贤等著近代优化方法P62。定理3.9 设在上二阶连续可微，且存在使为有界闭凸集，若初始点，则由GillMurray修正牛顿

14、法产生的点列满足：1) 若是有限点列时，它的最后一个点必为的平稳点；2) 若是无穷点列时，它必有聚点，且任一聚点均为的平稳点。证明：参阅邓乃扬著无约束最优化计算方法。注：一般.用到的GillMurray修改牛顿法除了强迫正定的Cholesky分解法外，在鞍点处还用到负曲率方向，因而它是一个对牛顿法改造的最彻底、最具有实用价值的方法。3.4 负曲率方向法一、负曲率方向负曲率方向法是修正牛顿法的又一种形式。当不正定时，利用负曲率方向可找到下降方向，尤其在鞍点处，即： ， 而不是半正定时（当然也不是正定的）此时若采用负曲率方向作为搜索方向，可以使目标函数下降。定义3.10 设在开集上二阶连续可微，1

15、）若至少有一个负特征值，则称为不定点；2）设是一个不定点，若方向满足：，则称为在 处的负曲率方向； （若是负曲率方向，显然也是）3）如果，则称向量对为不定点处的下降对； 若不是一个不定点，则称满足：，的向量对 为点处的下降对。下降对的例子 令 ，其中是对应于的负特征值的特征向量。注：1） 由定义可见：当且仅当，时，处不存在下降对。因此，一旦在该点不存在下降对，那么该点必满足极小点的二阶必要条件（但仍不一定是极小点）。2）若是鞍点，则负曲率方向必为下降方向。事实上，设为负曲率方向，由容易看出：当很小时，。3）若为一般点，且负曲率方向满足，则与均为下降方向。4）若，则是下降方向；若，则是下降方向。

16、由上述分析，一旦找到负曲率方向，则总存在一个下降方向。而唯一难找到下降方向的情形是：且时。二、Gill-Murray稳定牛顿法基本思想：将修改Cholesky分解与负曲率方向相结合。当不正定时，采用修改Cholesky分解强迫矩阵正定；而当时，采用负曲率方向使函数值下降。1）负曲率方向的求法（与修改的Cholesky分解相联系，计算相对容易）2）Gill-Murray稳定牛顿法算法步骤（参阅袁亚湘等著最优化理论与方法）。3）收敛性定理（证明参阅邓乃扬著无约束最优化计算方法）。三、Fiacco-Mccormick方法Fiacco-Mccormick是最早利用负曲率方向修正牛顿法的学者，他们利用精

17、确一维搜索以及Cholesky分解。1）当正定时，产生下降方向（牛顿方向）；2）当不定时，通过求解，其中获得 ，然后令，得负曲率方向（也是下降方向）。该方法的主要缺陷是：可能存在数值不稳定，甚至分解不存在。四、二阶Armijo步长准则Mccormick方法设是当前迭代点，是下降方向对，迭代格式为：这不是沿一个方向进行线搜索，也不是与的组合方向，而是一种曲线搜索策略。算法终止：不存在下降方向对时，算法终止。此时，意味着且，故是一个满足二阶必要条件的点。若产生无穷点列，则在对下降方向对附加较强条件时，算法总体收敛。在该方法中使用的非精确步长准则实际上属于简单步长准则，但不是Armijo一阶准则，而

18、是Armijo二阶步长准则。令 求，它是使下式满足的最小整数。令。五、二阶Armijo步长准则Goldfarb方法设是当前迭代点，是处的下降方向对。令这实际上是Mccormick方法的一种特殊形式。仍然采用Armijo简单步长准则，选择最小的正整数,使得，其中，与是预先给定的常数。六、二阶Wolfe-Powell步长准则More-Sorensen方法形式：。采用非精确搜索确定步长，步长准则采用Wolfe-Powell准则的推广形式，即所谓二阶Wolfe-Powell准则。关于上述内容的详细讨论可参阅袁亚湘等著最优化理论与方法的相应章节。3.6 信赖域方法一、信赖域算法1牛顿法的基本思想 在当前

19、迭代点附近用二次函数逼近，并以地极小点修正，得。如果不限定的范围，实际上是用在全空间逼近，而用的极小点代替地极小点。容易理解，这样得到的迭代点往往不能使有较大的改进，有时不仅不能得到改进，反而变得更糟。2信赖域方法的基本思想 信赖域方法是上世纪70年代提出的一种重要的优化方法，它针对上面提及的牛顿方法的缺陷，在子问题中，明确要求必须位于当前迭代点的邻域（信赖域）内。在算法每次迭代中，求解下述信赖域子问题：注: 1) 由于从信赖域子问题求出的必须满足，故称为有限步长方法；2）范数没有特别限制，可根据需要随意选取，但多数情形用或两种范数；3）可用有限差分近似，也可用后面即将介绍的拟牛顿方法构造其近

20、似。在信赖域算法中，信赖域半径采用自适应方式调整，若与近似程度好，则尽可能取大，否则将其缩小。而通常采用下述方式评价与的逼近程度：在算法迭代的第步，定义 称实际下降量 称预估下降量定义比值： 越接近1，表明近似程度好，应加大，否则相反。3信赖域算法（算法模式）1）初始步：给出初始点，令2）第步：给出和，计算和 解信赖域模型（子问题），求出 求和的值 如果，令 （缩减信赖域半径） 如果且，令 （增大信赖域半径） 否则，置 （信赖域半径不变） 若，置；否则置。注：求解信赖域子问题得到的称为试探步。由可见，求出的试探步最后是否移动，取决是否大于0。在有些信赖域算法中，将中的替换成了。二、信赖域算法的

21、收敛性定理3.11 设是中的一个有界集，信赖域算法产生的点列。若进一步假设且在上满足：。则存在一个满足一阶和二阶必要条件的聚点。证明：由算法分析可知，算法产生的点列必存在一个子序列，要么满足：1），（因而）；要么满足 2），（表示相应子列的下确界）。设是这样子序列的任一聚点，并设，下面证明就是满足定理要求的点。a) 若此序列满足条件1）用反证法，设，对中的任何，考虑该点的最速下降方向，有1）当时，注意到是信赖域子问题的可行解，因而有 （*） 注意到且时，从而有 。故有 。2）当时，由（*）式仍然有：故当且时（此时），有 （由）再由Taylor展开式 进而得： ，这与时，矛盾，从而有（即一阶必要

22、条件满足）。再证半正定。若不然，设是的最小特征值，则。设其对应的单位特征向量为，且满足（否则可取）。显然是信赖域子问题的可行解，故 从而有 （注意）再由Taylor公式， 得到 ，又与矛盾。从而是半正定的，即满足极小点的一阶和二阶必要条件。b) 若子序列是第二种情形注意到下降算法的特点，有故级数收敛。因而 （*）对应于，定义 并设满足 又设是下述信赖域子问题 的解。注意到时，因而满足（）。从而 取，注意，以及，因而有。 （由（*）式，）这说明也是的最优解。注意到，此时约束不起作用。因而相当于无约束问题的极值。因而有，半正定，由此即知，半正定。即在处满足一、二阶必要条件。定理证毕。关于定理3.1

23、1中两类子序列必出现一类的补充证明设算法产生的点列为，相应的有序列与。1）若充分大时，均有，则显然存在满足第一类条件的子列；2）若充分大时，均有，则显然存在满足第二类条件的子列；因而下面仅考虑与总是相间出现的情形。这种情形下，必存在一个子序列，当时，有（这里可取为使成立的指标的全体）。若时，不大于零，则存在的一个子列使得 。再从中如下构造子列：先选出的首项，设为；由于与总是相间出现。故必有，使，又一定有使得，对应得到，仿此得到的一个子序列。显然具有如下特点：1），有且；2）中任两个相邻项之间，必定存在一个指标，使。设与是中相邻两项。是两项对应的下标。设是从出发回溯得到的第一个使的下标，由信赖域

24、半径的自适应调整规则，显然有（见下图），图中箭头表示的升降趋势。由及，立即可得。这恰好表明由这样的构成的子列满足： 且 即若时，不大于零，则可构造出一个子序列使得且。这正好是第一种情形，故两种情形至少会出现一种。若进一步加上较强的条件，可得到信赖域算法的二阶收敛结果。定理3.11 若进一步假定在定理3.10中的聚点处，有正定，那么算法产生的序列整体有：，对充分大的，总有；并且收敛速度是二阶的。证明：假设算法产生的子序列属于第一种情形，即 考虑牛顿方向。由正定，因此当充分大时，有定义且为下降方向。1）若，则（即牛顿步为信赖域子问题的最优解） 其中，是的最小特征值。2）若，则是信赖域子问题的可行解

25、。 综合1）与2）可知，在任何情况下，都有。又由 得 （*）这与矛盾，从而子序列不属于第一种情形，而属于第二种情形。故 （注：到现在为止，结论还仅限于子序列）若对子序列中的某个充分大的，有这里由牛顿收敛定理中要求初始点充分靠近的条件：所确定。注意到牛顿法收敛定理的条件现在全部满足，为初始点。由于 满足 （由牛顿收敛定理的证明）而且由 知在信赖域中，因而此时信赖域算法蜕变为牛顿算法。故而对整个序列有。注意到：及（*）式知。由信赖域半径的自适应调整规则，当充分大时，始终有单调增，故有 （注意这里是对整个序列，而不仅指子序列）。而且充分大时，总有。此时，信赖域算法完全蜕变为牛顿算法，故有二阶收敛速度

26、。注：这个定理的证明过程知，信赖域算法在迭代后期，将自动转化为牛顿算法，因而具有二阶收敛速度；而在算法的开始阶段，对初始点无特殊要求，因而具有全局收敛性质。三、关于信赖域子问题最优解的条件在下面的讨论中，均采用范数。定理3.12 考虑二次函数 其中为对称矩阵。则 （1）有极小点当且仅当为半正定，且属于矩阵的值空间，即；（2）有惟一极小点当且仅当正定；（3）若为半正定，则方程的每个解均为的全局极小点。证明：(1) 假定为半正定，且属于的值空间。即存在，使得，令 ， 则有 。显然， 有 （*）故是的（全局）极小点。反之若是的极小点，则满足极小点的二阶必要条件： ，且半正定，（1）得证。（2）注意到

27、：当且仅当正定时，（*）对一切，成为严格不等式。故有惟一极小点当且仅当正定。（3 再注意到（*）当及半正定时总成立，故当满足时，也是的极小点。定理3.13 考虑信赖域问题： （1）则为该问题解的充要条件是，且存在，使得： ， 且半正定。证明： 充分性： 设有及，使得 ，且半正定。由前一定理，可知是二次函数的极小点。因此，对一切，有 从而有 （2）由 及，由（2）知，当时，有 。即为信赖域问题的解，充分性得证； 必要性：设是（1）的解，(a) 若，则是的无约束极小，故半正定。取，即知 ，满足所有条件；(b) 若，则也是等式约束问题 （3）的解。因此，由条件极值的拉格朗日乘子法，存在，使得Lagr

28、ange函数的梯度在处为，即：可见，与满足： （4）下证：及半正定。由于是（1）的解，故当时，（2）式成立。由（4）式，在（2）中用代替，并整理得即对任意的，当时，有由此可证：，有从而半正定。现证。 假定，则由半正定，必正定，且其最小特征值。令 则为的唯一的无约束极小。由于满足故 。而的最大特征值为，又 故 即也是（1）的唯一极小点，这与为（1）的极小点矛盾。故必有。注：以上所说极小点均指全局最小点。推论 问题（1）没有满足的解，当且仅当为正定，且。证明：若正定，且，则是唯一的无约束极小点。而它又是（1）的可行解，故它也（1）唯一极小点，因而在边界上不再有其它解。反过来，若（1）在边界上无解，

29、故（1）的解均在约束域内部（因为（1）总是有解的），设是（1）的解，且，由定理3.13知：存在，使得 ， 且半正定。而由知，必有，且半正定。这时若为奇异的，则存在，使 ，且 于是满足。 取，则与满足定理3.13的充分性条件，故是(1)的解。但它在边界上，与其在边界上无解的条件矛盾，故非奇异。因而必正定。再由，因而也是的无约束极小，故有，即 或 因而有 。注：由以上分析可知：若正定，且，则为（1）的解。否则（1）必有一解在边界上，由定理3.13，应存在参数，使得半正定且使的解满足：。四、 Levenberg-Marquardt方法上面一般地讨论了信赖域方法的算法模式并证明了算法的收敛性定理。而关

30、于如何求解信赖域子问题尚未涉及，因而仅是算法模式而不是具体算法，下面给出几种具体的信赖域算法。根据上一段关于信赖域子问题解的最优性条件的讨论，我们知道对信赖域问题： 是其最优解的充要条件是，且存在使得： 且 半正定。基于上述结果，Levenberg-Marquardt算法的核心思想是每次确定一个，使正定，然后求解确定，并令信赖域半径 。Levenberg-Marquardt算法1）初始步：给出，置2）第次迭代(1) 对给出和，计算和，若，stop。(2) 检验是否正定。若不正定，置，重复这一过程直到正定。 (3) 由计算出。 (4) 求，和的值。 (5) 若，置；若，置； 否则，置。(6) 若 ，置；否则，置。(7) 令，go to (1)。注：1）在每次迭代中以试探的方式获取。2）信赖域子问题的最优解总在信赖域边界上达到，因为不是事先确定，而是以