使用导数的最优化方法

使用导数的最优化方法第1页，课件共74页，创作于2023年2月一.无约束最优化问题

无约束非线性规划问题的求解方法分为解析法和直接法两类。解析法需要计算函数的梯度，利用函数的解析性质构造迭代公式使之收敛到最优解。本节介绍最速下降法、共轭梯度法、牛顿法、变尺度法等解析方法

直接法仅通过比较目标函数值的大小来移动迭代点。下一章主要介绍模式搜索法等直接方法。第2页，课件共74页，创作于2023年2月

无约束非线性规划问题的求解方法分为解析法和直接法两类。

一般来说，无约束非线性规划问题的求解是通过一系列一维搜索来实现。因此，如何选择搜索方向是解无约束非线性规划问题的核心问题，搜索方向的不同选择，形成不同的求解方法。本章主要介绍解析法;另一类只用到目标函数值,不必计算导数,通常称为直接方法,放在第11章讨论.第3页，课件共74页，创作于2023年2月本章考虑如下的下降算法：主要介绍最速下降法、牛顿法，共轭梯度法，拟牛顿法等第4页，课件共74页，创作于2023年2月10.1最速下降法10.1.1最速下降方向

考虑无约束问题(6.1.2)其中函数具有一阶连续偏导数.

人们在处理这类问题时,总希望从某一点出发,选择一个目标函数值下降最快的方向,以利于尽快达到极小点.正是基于这样一种愿望,早在1847年法国著名数学家Cauchy提出了最速下降法.后来,Curry等人作了进一步的研究.现在最速下降法已经成为众所周知的一种最基本的算法,它对其他算法的研究也很有启发作用,因此在最优化方法中占有重要地位.下面我们先来讨论怎样选择最速下降方向.

第5页，课件共74页，创作于2023年2月人们在处理这类问题时,总希望从某一点出发,选择一个目标函数值下降最快的方向,以利于尽快达到极小点.正是基于这样一种愿望,早在1847年法国著名数学家Cauchy提出了最速下降法.后来,Curry等人作了进一步的研究.现在最速下降法已经成为众所周知的一种最基本的算法,它对其他算法的研究也很有启发作用,因此在最优化方法中占有重要地位.下面我们先来讨论怎样选择最速下降方向.

我们知道,函数在点处沿方向的变化率可用方向导数来表达,对于可微函数,方向导数等于梯度与方向的内积,即(6.1.2)因此,求函数在点处的下降最快的方向,可归结为求解下列非线性规划:(6.1.3)第6页，课件共74页，创作于2023年2月根据Schwartz不等式,有去掉绝对值符号,可以得到(6.1.4)由上式可知,当(6.1.5)时等号成立.因此,在点处沿(6.1.5)所定义的方向变化率最小,即负梯度方向为最速下降方向.

这里要特别指出,在不同尺度下最速下降方向是不同的.前面定义的最速下降方向,是在向量的殴氏范数不大于1的限制得到的,属于殴氏度量意义下的最速下降方向.如果改用其他度量,比第7页，课件共74页，创作于2023年2月如,设为对称正定矩阵,在向量的范数不大于1的限制下,极小化,则得到的最速下降方向与前者不同.

10.1.2最速下降算法

最速下降法的迭代公式是(10.1.6)其中是从出发的搜索方向,这里取在点处的最速下降方向,即

是从出发沿方向进行一维搜索的步长,即满足(10.1.11)第8页，课件共74页，创作于2023年2月

计算步骤如下:1.给定初点,允许误差,置.2.计算搜索方向3.若,则停止计算;否则,从出发,沿进行一维搜索,求,使4.令,置,转步2..

例10.1.1

用最速下降法解下列问题:第9页，课件共74页，创作于2023年2月解：第二次迭代：第10页，课件共74页，创作于2023年2月第三次迭代：第11页，课件共74页，创作于2023年2月第12页，课件共74页，创作于2023年2月在最速下降法的一位搜素中即在最速下降法中相邻两次搜索方向是正交的。第13页，课件共74页，创作于2023年2月对于二次严格凸函数其中A为n维对称正定矩阵可以求出步长因子k（本章习题7）第14页，课件共74页，创作于2023年2月锯齿现象

最速下降法的迭代点在向极小点靠近的过程中，走的是曲折的路线：后一次搜索方向d(k+1)与前一次搜索方向d(k)总是相互垂直的，称它为锯齿现象。这一点在前面的例题中已得到验证。除极特殊的目标函数（如等值面为球面的函数）和极特殊的初始点外，这种现象一般都要发生。最速下降法的收敛性第15页，课件共74页，创作于2023年2月

从直观上可以看到，在远离极小点的地方，每次迭代都有可能使目标函数值有较多的下降，但在接近极小点的地方，由于锯齿现象，每次迭代行进的距离开始逐渐变小。因而收敛速度不快。

已有结论表明，最速下降法对于正定二次函数关于任意初始点都是收敛的(定理10.1.2)，而且恰好是线性收敛的。第16页，课件共74页，创作于2023年2月第17页，课件共74页，创作于2023年2月第18页，课件共74页，创作于2023年2月§10.2牛顿法

6.2.1牛顿法

设是二次可微实函数,.又设是的极小点的一个估计,我们把在展成Taylor级数,并取二阶近似:其中是在处的Hessian矩阵.为求的平稳点,令即(10.2.1)第19页，课件共74页，创作于2023年2月设可逆,有(10.2.1)得到牛顿法的迭代公式(10.2.2)其中是Hessian矩阵的逆矩阵.这样,知道后,算出在这一点处目标函数的梯度和Hessian矩阵的逆,代人(10.2.2),便得到后继点,用代替,再用(10.2.2)计算,又得到的后继点.依此类推,产生序列.在适当的条件下,这个序列收敛.

第20页，课件共74页，创作于2023年2月则牛顿法产生的序列收敛于.

实际上,当牛顿法收敛时,有下列关系:其中C是某个常数.因此,牛顿法至少2级收敛,参看文献[19].可见牛顿法的收敛速率是很快的.第21页，课件共74页，创作于2023年2月例10.2.1

用牛顿法解下列问题:

我们取初点解：第2次迭代：第22页，课件共74页，创作于2023年2月第2次迭代：继续迭代，得到最终收敛到最优解x*=(1,0)T第23页，课件共74页，创作于2023年2月我们先用极值条件求解.令下面用牛顿法求解.任取初始点x(1)

,根据牛顿法的迭代公式：特别地,对于二次凸函数,用牛顿法求解,经1次迭代即达极小点.设有二次凸函数其中A是对称正定矩阵。求迭代点x(2)

即1次迭代达到极小点.第24页，课件共74页，创作于2023年2月不一定是下降方向,经迭代,目标函数值可能上升.此外,即使目标函数值下降,得到的点也不一定是沿牛顿方向的最好点或极小点.因此,人们对牛顿法进行修正,提出了阻尼牛顿法.

值得注意,当初始点远离极小点时,牛顿法可能不收敛.原因之一,牛顿方向

以后还会遇到一些算法,把它们用于二次凸函数时,类似于牛顿法,经有限次迭代必达到极小点.这种性质称为二次终止性.对于二次凸函数,用牛顿法求解,经1次迭代即达极小点第25页，课件共74页，创作于2023年2月10.2.2阻尼牛顿法

阻尼牛顿法与原始牛顿法的区别在于增加了沿牛顿方向的一维搜索,其迭代公式是(6.2.6)其中为牛顿方向,是由一维搜索得到的步长,即满足

阻尼牛顿法的计算步骤如下:1.给定初始点,允许误差,置.2.计算第26页，课件共74页，创作于2023年2月3.若,则停止迭代;否则,令4.从出发,沿方向作一维搜索:令.5.置,转步2..

由于阻尼牛顿法含有一维搜索,因此每次迭代目标函数值一般有所下降(决不会上升).可以证明,阻尼牛顿法在适当的条件下具有全局收敛性,且为2级收敛.第27页，课件共74页，创作于2023年2月10.3、共轭梯度法第28页，课件共74页，创作于2023年2月10.3.1共轭方向法1.共轭方向和共轭方向法共轭是正交的推广。第29页，课件共74页，创作于2023年2月几何意义第30页，课件共74页，创作于2023年2月几何意义第31页，课件共74页，创作于2023年2月第32页，课件共74页，创作于2023年2月第33页，课件共74页，创作于2023年2月第34页，课件共74页，创作于2023年2月第35页，课件共74页，创作于2023年2月第36页，课件共74页，创作于2023年2月推论：第37页，课件共74页，创作于2023年2月共轭方向法第38页，课件共74页，创作于2023年2月对于上述正交方向法，它是下降算法吗？不难得到：故正交方向法，它是下降算法。第39页，课件共74页，创作于2023年2月可由一组线性无关向量组，类似于schmidt正交化过程，第40页，课件共74页，创作于2023年2月第41页，课件共74页，创作于2023年2月§10.3共轭梯度法

10.3.2共轭梯度法

共轭梯度法最初由Hesteness和Stiefel于1952年为求解线性方程组而提出.后来,人们把这种方法用于求解无约束最优化问题,使之成为一种重要的最优化方法.

下面,重点介绍Fletcher-Reeves共轭梯度法,简称FR法.

共轭梯度法的基本思想是把共轭性与最速下降方法相结合,利用已知点处的梯度构造一组共轭方向,并沿这组方向进行搜索,求出目标函数的极小点.根据共轭方向的基本性质,这种方法具有二次终止性.

我们先讨论对于二次凸函数的共轭梯度法,然后再把这种方法推广到极小化一般函数的情形.第42页，课件共74页，创作于2023年2月10.3.2.共轭梯度法

如何选取一组共轭方向？以下分析算法的具体步骤。我们先讨论对于二次凸函数的共轭梯度法,然后再把这种方法推广到极小化一般函数的情形第43页，课件共74页，创作于2023年2月初始搜索方向为最速下降方向第44页，课件共74页，创作于2023年2月第45页，课件共74页，创作于2023年2月第46页，课件共74页，创作于2023年2月第47页，课件共74页，创作于2023年2月常用两个公式:著名的FR和PPR公式第48页，课件共74页，创作于2023年2月求解二次凸规划的FR共轭梯度法求解二次凸规划的FR共轭梯度法迭代多少次才可以达到最优解？第49页，课件共74页，创作于2023年2月第50页，课件共74页，创作于2023年2月第51页，课件共74页，创作于2023年2月第52页，课件共74页，创作于2023年2月10.3.3.用于一般函数的共轭梯度法第53页，课件共74页，创作于2023年2月10.3.3.用于一般函数的共轭梯度法第54页，课件共74页，创作于2023年2月第55页，课件共74页，创作于2023年2月§10.3共轭梯度法

10.3.2共轭梯度法

共轭梯度法最初由Hesteness和Stiefel于1952年为求解线性方程组而提出.后来,人们把这种方法用于求解无约束最优化问题,使之成为一种重要的最优化方法.

下面,重点介绍Fletcher-Reeves共轭梯度法,简称FR法.

共轭梯度法的基本思想是把共轭性与最速下降方法相结合,利用已知点处的梯度构造一组共轭方向,并沿这组方向进行搜索,求出目标函数的极小点.根据共轭方向的基本性质,这种方法具有二次终止性.

我们先讨论对于二次凸函数的共轭梯度法,然后再把这种方法推广到极小化一般函数的情形.

考虑问题第56页，课件共74页，创作于2023年2月其中,是对称正定矩阵,是常数.

具体求解方法如下:

首先,任意给定一个初始点,计算出目标函数在这点的梯度,若,则停止计算;否则,令(10.3.12)沿方向搜索,得到点.计算在处的梯度,若,则利用和构造第2个搜索方向,再沿搜索.

一般地,若已知点和搜索方向,则从出发,沿进行搜索,得到(10.3.14)第57页，课件共74页，创作于2023年2月其中步长满足我们可以求出的显式表达.令求的极小点,令(10.3.15)根据二次函数的梯度的表达式,(6.3.15)即(10.3.16)第58页，课件共74页，创作于2023年2月由(6.3.16)得到(10.3.17)

计算在处的梯度.若,则停止计算;否则,用共轭.按此设想,令(10.3.18)上式两端左乘,并令由此得到(10.3.19)第59页，课件共74页，创作于2023年2月

再从出发,沿方向搜索.综上分析，在第１个搜索方向取负梯度的前提下,重复使用公式(10.3.14),(10.3.17),(10.3.18)和(10.3.19),就能伴随计算点的增加,构造出一组搜索方向.下面将要证明,这组方向是关于共轭的.因此,上述方法具有二次终止性.

定理10.3.3

对于正定二次函数(10.3.12),具有精确一维搜索的Fletcher-Reeves法在次一维搜索后即终止，并且对所有,下列关系成立:第60页，课件共74页，创作于2023年2月

例6.3.1

考虑下列问题：

取初始点和初始搜索方向分别为

在FR法中，初始搜索方向必须取最速下降方向，这一点绝不可忽视。

对于二次凸函数，FR法的计算步骤如下：1.给定初始点,置.第61页，课件共74页，创作于2023年2月2.计算,若,则停止计算,得点;否则,进行下一步.3.构造搜索方向,令其中,当时,,当时,按公式计算因子.4.令其中按公式(6.3.17)计算步长第62页，课件共74页，创作于2023年2月5.若,则停止计算,得点;否则,置,返回步2..

由第63页，课件共74页，创作于2023年2月§10.4拟牛顿法

6.4.1拟牛顿条件前面介绍了牛顿法,它的突出优点是收敛很快.但是,运用牛顿法需要计算二阶便导数,而且目标函数的Hessian矩阵可能非正定.为了克服牛顿法的缺点,人们提出了拟牛顿法.它的基本思想是用不包含二阶导数的矩阵近似牛顿法中的Hessian矩阵的逆矩阵.第64页，课件共74页，创作于2023年2月Newton法的优缺点都很突出。

优点：高收敛速度（二阶收敛）；

缺点：对初始点、目标函数要求高，计算量、存储量大（需要计算、存储Hesse矩阵及其逆）。

拟Newton法是模拟Newton法给出的一个保优去劣的算法

拟Newton法是效果很好的一大类方法。它当中的DFP算法和BFGS算法是直到目前为止在不用Hesse矩阵的方法中的最好方法。第65页，课件共74页，创作于2023年2月第66页，课件共74页，创作于2023年2月第67页，课件共74页，创作于2023年2月由于构造近似矩阵的方法不同,因而出现不同的拟牛顿法.经理论证明和实践检验,拟牛顿法已经成为一类公认的比较有效的算法下面分析怎样构造近似矩阵并用它取代牛顿法中的Hessian矩阵的逆.前面已经给出牛顿法的迭代公式,即

k是从xk出发沿牛顿方向搜索的最优步长.第68页，课件共74页，创作于2023年2月

设在第次迭代后,得到点,我们将目标函数在点展成Taylor级数,并取二阶近似,得到由此可知,在附近有令,则记作第69页，课件共74页，创作于2023年2月(10.4.3)(10.4.4)则有(10.4.5)又设Hessian矩阵可逆,则(10.4.6)这样,计算出后,可以根据(10.4.6)估计在