第第10章章 使用导数的最优化方法使用导数的最优化方法 1.无约束最优化问题无约束最优化问题2. 最速下降法最速下降法4.共轭梯度法共轭梯度法5.拟牛顿法拟牛顿法3. 牛顿法牛顿法一一. 无约束最优化问题无约束最优化问题 无约束非线性规划问题的求解方法分为解析法和直接法两类。解析法解析法 需要计算函数的梯度，利用函数的解析性质构造迭代公式使之收敛到最优解。本节介绍最速下降法、共轭梯度法、牛顿法、变尺度法等解析方法 直接法直接法 仅通过比较目标函数值的大小来移动迭代点。下一章主要介绍模式搜索法等直接方法。 无约束非线性规划问题的求解方法分为解析法和直接法两类。 一般来说，无约束非线性规划问题的求解是通过一系列一维搜索来实现。因此，如何选择搜索方向是解无约束非线性规划问题的核心问题，搜索方向的不同选择，形成不同的求解方法。本章主要介绍解析法;另一类只用到目标函数值,不必计算导数,通常称为直接方法直接方法,放在第11章讨论.本章考虑如下的下降算法：本章考虑如下的下降算法：主要介绍最速下降法、牛顿法，共轭梯度法，拟牛顿法等10.1 最速下降法最速下降法 10.1.1 最速下降方向最速下降方向 考虑无约束问题(6.1.2)其中函数 具有一阶连续偏导数. 人们在处理这类问题时,总希望从某一点出发,选择一个目标函数值下降最快的方向,以利于尽快达到极小点.正是基于这样一种愿望,早在1847年法国著名数学家Cauchy提出了最速下降法最速下降法.后来,Curry等人作了进一步的研究.现在最速下降法已经成为众所周知的一种最基本的算法,它对其他算法的研究也很有启发作用,因此在最优化方法中占有重要地位.下面我们先来讨论怎样选择最最速下降方向速下降方向. 人们在处理这类问题时,总希望从某一点出发,选择一个目标函数值下降最快的方向,以利于尽快达到极小点.正是基于这样一种愿望,早在1847年法国著名数学家Cauchy提出了最速下降法最速下降法.后来,Curry等人作了进一步的研究.现在最速下降法已经成为众所周知的一种最基本的算法,它对其他算法的研究也很有启发作用,因此在最优化方法中占有重要地位.下面我们先来讨论怎样选择最最速下降方向速下降方向. 我们知道,函数 在点 处沿方向 的变化率可用方向导数来表达,对于可微函数,方向导数等于梯度与方向的内积,即(6.1.2)因此,求函数 在点 处的下降最快的方向,可归结为求解下列非线性规划:(6.1.3)根据Schwartz不等式,有去掉绝对值符号,可以得到(6.1.4)由上式可知,当(6.1.5)时等号成立.因此,在点 处沿(6.1.5)所定义的方向变化率最小,即负梯度方向为最速下降方向负梯度方向为最速下降方向. 这里要特别指出,在不同尺度下最速下降方向是不同的.前面定义的最速下降方向,是在向量 的殴氏范数 不大于1的限制得到的,属于殴氏度量意义下的最速下降方向.如果改用其他度量,比如,设 为对称正定矩阵,在向量 的 范数 不大于1的限制下,极小化 ,则得到的最速下降方向与前者不同. 10.1.2 最速下降算法最速下降算法 最速下降法的迭代公式是(10.1.6)其中 是从 出发的搜索方向,这里取在点 处的最速下降方向,即 是从 出发沿方向 进行一维搜索的步长,即 满足(10.1.11) 计算步骤计算步骤如下: 1.给定初点 ,允许误差 ,置 . 2.计算搜索方向 3.若 ,则停止计算;否则,从 出发,沿 进行一维搜索,求 ,使 4.令 ,置 ,转步2. 例例10.1.1 用最速下降法解下列问题:解：解：第二次迭代：第三次迭代：在最速下降法的一位搜素中即在最速下降法中相邻两次搜索方向是正交的。对于二次严格凸函数其中A为n维对称正定矩阵可以求出步长因子k（本章习题7）锯齿现象锯齿现象 最速下降法的迭代点在向极小点靠近的过程中，走的是曲折的路线：后一次搜索方向d(k+1)与前一次搜索方向 d(k)总是相互垂直的，称它为锯齿现象锯齿现象。这一点在前面的例题中已得到验证。除极特殊的目标函数（如等值面为球面的函数）和极特殊的初始点外，这种现象一般都要发生。 最速下降法的收敛性 从直观上可以看到，在远离极小点的地方，每次迭代都有可能使目标函数值有较多的下降，但在接近极小点的地方，由于锯齿现象，每次迭代行进的距离开始逐渐变小。因而收敛速度不快。 已有结论表明，最速下降法对于正定二次函数关于任意初始点都是收敛的(定理10.1.2)，而且恰好是线性收敛的。10.2 牛顿法牛顿法 6.2.1 牛顿法牛顿法 设 是二次可微实函数, .又设 是 的极小点的一个估计,我们把 在 展成Taylor级数,并取二阶近似:其中 是 在 处的Hessian矩阵.为求 的平稳点,令即(10.2.1)设 可逆,有(10.2.1)得到牛顿法的迭代公式(10.2.2)其中 是Hessian矩阵 的逆矩阵. 这样, 知道 后,算出在这一点处目标函数的梯度和Hessian矩阵的逆,代人(10.2.2),便得到后继点 ,用 代替 ,再用(10.2.2)计算,又得到 的后继点.依此类推,产生序列 .在适当的条件下,这个序列收敛. 则牛顿法产生的序列收敛于 . 实际上,当牛顿法收敛时,有下列关系:其中 C 是某个常数.因此,牛顿法至少2级收敛,参看文献19.可见牛顿法的收敛速率是很快的.例例10.2.1 用牛顿法解下列问题: 我们取初点解：第2次迭代：第2次迭代：继续迭代，得到最终收敛到最优解x*=(1,0)T我们先用极值条件求解.令下面用牛顿法求解. 任取初始点x(1) , 根据牛顿法的迭代公式：特别地,对于二次凸函数,用牛顿法求解,经1次迭代即达极小点.设有二次凸函数其中A是对称正定矩阵。求迭代点x(2) 即1次迭代达到极小点.不一定是下降方向,经迭代,目标函数值可能上升.此外,即使目标函数值下降,得到的点 也不一定是沿牛顿方向的最好点或极小点.因此,人们对牛顿法进行修正,提出了阻尼牛顿法. 值得注意,当初始点远离极小点时,牛顿法可能不收敛.原因之一,牛顿方向 以后还会遇到一些算法,把它们用于二次凸函数时,类似于牛顿法,经有限次迭代必达到极小点.这种性质称为二次终止性二次终止性. 对于二次凸函数,用牛顿法求解,经1次迭代即达极小点 10.2.2 阻尼牛顿法阻尼牛顿法 阻尼牛顿法与原始牛顿法的区别在于增加了沿牛顿方向的一维搜索,其迭代公式是(6.2.6)其中 为牛顿方向, 是由一维搜索得到的步长,即满足 阻尼牛顿法的计算步骤计算步骤如下: 1.给定初始点 ,允许误差 ,置 . 2.计算 3.若 ,则停止迭代;否则,令 4.从 出发,沿方向 作一维搜索:令 . 5.置 ,转步2. 由于阻尼牛顿法含有一维搜索,因此每次迭代目标函数值一般有所下降(决不会上升).可以证明,阻尼牛顿法在适当的条件下具有全局收敛性,且为2级收敛.10.310.3、共轭梯度法、共轭梯度法10.3.1 共轭方向法共轭方向法1. 共轭方向和共轭方向法共轭方向和共轭方向法共轭是正交的推广。共轭是正交的推广。几何意义几何意义几何意义几何意义推论：共轭方向法对于上述正交方向法，它是下降算法吗？不难得到：故正交方向法，它是下降算法。可由一组线性无关向量组，类似于schmidt正交化过程，10.3 共轭梯度法共轭梯度法 10.3.2 共轭梯度法共轭梯度法 共轭梯度法最初由Hesteness和Stiefel于1952年为求解线性方程组而提出.后来,人们把这种方法用于求解无约束最优化问题,使之成为一种重要的最优化方法. 下面,重点介绍Fletcher-Reeves共轭梯度法共轭梯度法,简称FR法法. 共轭梯度法的基本思想基本思想是把共轭性与最速下降方法相结合,利用已知点处的梯度构造一组共轭方向,并沿这组方向进行搜索,求出目标函数的极小点.根据共轭方向的基本性质,这种方法具有二次终止性. 我们先讨论对于二次凸函数的共轭梯度法,然后再把这种方法推广到极小化一般函数的情形.10.3.2. 共轭梯度法 如何选取一组共轭方向？如何选取一组共轭方向？以下分析算法的具体步骤。以下分析算法的具体步骤。我们先讨论对于二次凸函数的共轭梯度法,然后再把这种方法推广到极小化一般函数的情形初始搜索方向为最速下降方向常用两个公式:著名的FR和PPR公式求解二次凸规划的FR 共轭梯度法求解二次凸规划的FR 共轭梯度法迭代多少次才可以达到最优解？10.3.3. 用于一般函数的共轭梯度法10.3.3. 用于一般函数的共轭梯度法10.3 共轭梯度法共轭梯度法 10.3.2 共轭梯度法共轭梯度法 共轭梯度法最初由Hesteness和Stiefel于1952年为求解线性方程组而提出.后来,人们把这种方法用于求解无约束最优化问题,使之成为一种重要的最优化方法. 下面,重点介绍Fletcher-Reeves共轭梯度法共轭梯度法,简称FR法法. 共轭梯度法的基本思想基本思想是把共轭性与最速下降方法相结合,利用已知点处的梯度构造一组共轭方向,并沿这组方向进行搜索,求出目标函数的极小点.根据共轭方向的基本性质,这种方法具有二次终止性. 我们先讨论对于二次凸函数的共轭梯度法,然后再把这种方法推广到极小化一般函数的情形. 考虑问题其中 , 是对称正定矩阵, 是常数. 具体求解方法如下: 首先,任意给定一个初始点 ,计算出目标函数 在这点的梯度,若 ,则停止计算;否则,令(10.3.12)沿方向 搜索,得到点 .计算在 处的梯度,若 ,则利用 和 构造第2个搜索方向 ,再沿 搜索. 一般地,若已知点 和搜索方向 ,则从 出发,沿 进行搜索,得到(10.3.14)其中步长 满足我们可以求出 的显式表达.令求 的极小点,令(10.3.15)根据二次函数的梯度的表达式,(6.3.15)即(10.3.16)由(6.3.16)得到(10.3.17) 计算 在 处的梯度.若 ,则停止计算;否则,用共轭.按此设想,令(10.3.18)上式两端左乘 ,并令由此得到(10.3.19) 再从 出发,沿方向 搜索.综上分析，在第个搜索方向取负梯度的前提下, 重复使用公式(10.3.14),(10.3.17),(10.3.18)和(10.3.19),就能伴随计算点的增加,构造出一组搜索方向.下面将要证明,这组方向是关于 共轭的.因此,上述方法具有二次终止性. 定理定理10.3.3 对于正定二次函数(10.3.12),具有精确一维搜索的Fletcher-Reeves法在 次一维搜索后即终止，并且对所有 ,下列关系成立: 例例6.3.1 考虑下列问题： 取初始点和初始搜索方向分别为 在FR法中，初始搜索方向必须取最速下降方向初始搜索方向必须取最速下降方向，这一点绝不可忽视。 对于二次凸函数，FR法的计算步骤计算步骤如下： 1.给定初始点 ,置 . 2.计算 ,若 ,则停止计算,得点 ;否则,进行下一步. 3.构造搜索方向,令其中,当 时, ,当 时,按公式 计算因子 . 4.令其中按公式(6.3.17)计算步长 5.若 ,则停止计算,得点 ;否则,置 ,返回步2. 由10.4 拟牛顿法拟牛顿法 6.4.1 拟牛顿条件拟牛顿条件前面介绍了牛顿法,它的突出优点是收敛很快.但是,运用牛顿法需要计算二阶便导数,而且目标函数的Hessian矩阵可能非正定.为了克服牛顿法的缺点,人们提出了拟牛顿法.它的基本思想基本思想是用不包含二阶导数的矩阵近似牛顿法中的Hessian矩阵的逆矩阵. Newton法的优缺点都很突出。 优点：高收敛速度（二阶收敛）； 缺点：对初始点、目标函数要求高，计算量、存储量大（需要计算、存储Hesse矩阵及其逆）。 拟Newton法是模拟Newton法给出的一个保优去劣的算法 拟Newton法是效果很好的一大类方法。它当中的DFP算法和BFGS算法是直到目前为止在不用Hesse矩阵的方法中的最好方法。由于构造近似矩阵的方法不同,因而出现不同的拟牛顿法.经理论证明和实践检验,拟牛顿法已经成为一类公认的比较有效的算法下面分析怎样构造近似矩阵并用它取代牛顿法中的Hessian矩阵的逆.前面已经给出牛顿法的迭代公式,即 k是从 xk 出发沿牛顿方向搜索的最优步长. 设在第 次迭代后,得到点 ,我们将目标函数 在点 展成Taylor级数,并取二阶近似,得到由此可知,在 附近有令 ,则记作(10.4.3)(10.4.4)则有(10.4.5)又设Hessian矩阵 可逆,则(10.4.6)这样,计算出 后,可以根据(10.4.6)估计在 处的Hessian矩阵的逆.因此,为了用不包含二阶导数的矩阵 取代牛顿法中的Hessian矩阵 的逆矩阵,有理由令 满足(10.4.7)式(10.4.7)有时称为拟牛顿条件拟牛顿条件.下面旧来研究怎样确定满足这个条件的矩阵 . 10.4.3 DFP算法算法 著名的 DFP 方法方法是 Davidon 首先提出, 后来又被 Fletcher 和 Powell 改进的算法,又称为变尺度法变尺度法.在这种方法中,定义校正矩阵为(6.4.16) 容易验证,这样定义校正矩阵 ,得到的矩阵(6.4.17)(10.4.7)满足拟牛顿条件(6.4.7).(6.4.17)称为DFP公式公式. DFP方法计算步骤计算步骤如下: 1.给定初始点 ,允许误差 . 2.置 (单位矩阵),计算出在 处的梯度 3.令 4.从 出发,沿方向 搜索,求步长 ,使它满足令 5.检验是否满足收敛准则,若则停止迭代,得到点 ;否则,进行步6. 6.若 ,则令 ,返回步2.;否则,进行步7. 7.令利用公式(6.4.17)计算 置 ,返回步3. 例例10.4.1 用DFP方法求解下列问题: 初始点及初始矩阵分别取为