优化设计第5次课

第三节牛顿型方法最速下降法在迭代过程中由于存在锯齿状搜索路径，使得最初几步迭代数值下降很快，但是总体下降得并不快，而且愈接近极值点下降得越慢，其主要原因是梯度法在确定搜索方向时只考虑目标函数在迭代点的局部性质．即利用一阶偏导数(梯度)信息。而牛顿法进一步利用了目标函数的二阶偏导数，考虑了梯度的变化趋势，因而更为全面地确定合适的搜索方向，以便很快地搜索到极小点。这里所介绍的牛顿型方法主要包括牛顿法和阻尼牛顿法。一、牛顿法的基本原理牛顿法是一种收敛速度很快的方法，其基本思路是利用二次曲线来逐点近似原目标函数，以二次曲线的极小点来近似原目标函数的极小点并逐渐逼近该点。设已知一维目标函数的初始点，过点作一与原目标函数相切的二次曲线——抛物线，求抛物线的极小点的坐标，将代入原目标函数，求得得到点。过点再作一个与相切的二次函数，得到下一个最小点,解得点。重复做下去直到找到原目标函数的极小点的坐标值为止，如下图所示。在逼近的过程中所用的二次函数是以原目标函数在迭代点附近的泰勒展开式的二次项，一维目标函数在点，逼近所用二次函数为此二次函数的极小点，可由极值存在的必要条件求得,也即求得。

下一次逼近原目标函数的二次曲线即用在点的泰勒展开式二次项。

把上述过程推广到维问题，即是当时，可求得二次函数的极值点，对上式矩阵方程求导，可得到若为可逆矩阵，从而得到这次逼近的二次函数的最小点

由于是的一个近似表达式，所求得的极小点并不是目标函数真正的极小点。只有当目标函数本身是二次函数时，所求的极小点才是目标函数的真正极小点,这种情况一次迭代就可求出目标函数的最优点。二、牛顿法的迭代公式或者写成其中称牛顿搜索方向，。在一般情况下，不一定是二次函数，则不能通过一次迭代就求出极小点，即极小点不在方向上，但由于在点附近，函数与是近似的，所以这个方向可以作为近似方向，为了求得极小值，可以把由上式求得的作为下一个迭代点，通过反复地循环迭代，不断逼近到的极小点。于是得到牛顿法的迭代格式为牛顿法就是通过这种迭代，逐次向极小点逼近。例：函数的初始点取，用牛顿法求它的极值点。三、阻尼牛顿法从牛顿法迭代公式的推导过程可以看出，迭代点的位置是按照极值条件确定的，其中并未强调含有沿下降方向搜素的概念。因此对于非二次函数，如果采用上述牛顿法迭代计算，有时可能会使函数值上升，即出现的现象，这就有可能导致迭代结果收敛于极大点或者不收敛等情况。基于这种原因需对上述牛顿法进行改进，于是便出现了“阻尼牛顿法”。其具体的修正方法是，用求时不是直接利用原来的迭代公式计算，而是沿着点处的牛顿方向进行一维搜索，将该方向上的最优点作为，于是牛顿法迭代公式可以改写成其中搜索方向取牛顿方向，即式中为沿牛顿方向进行一维搜素的最优步长，可称之为阻尼因子。可通过如下极小化过程求得这种阻尼牛顿法通常又称为广义牛顿方法，或称修正牛顿法。原来的牛顿法相当于阻尼牛顿法的搜索步长恒取1的情况。虽然相对于原来的牛顿法，阻尼牛顿法的计算工作量多了一些，但是在目标函数的诲色矩阵为正定的情况下，它能保证每次迭代都能使函数值有所下降。即使初始点选择不当，用这种搜索方法也会成功，同时，它还保留了古典牛顿法收敛快的优点。四、阻尼牛顿法的计算步骤(1)给定初始点，给定精度，置；(2)计算点的梯度及其梯度模；(4)计算海色矩阵并求其逆矩阵，确定牛顿向并沿牛顿方向做一维搜索，求出在方向上的最优步长；(5)计算第个迭代点；(3)检查收敛精度。若，则迭代停止，输出最优解，；否则，转下一步；(6)置，返回到(2)继续进行搜索。

(2)对目标函数性态有较严格的要求。除了函数具有连续的一、二阶偏导数以外，为了保证函数的稳定下降，海色矩阵必须正定。同时，为了能求逆矩阵形成牛顿方向，又要求海色矩阵必须非奇异。(3)计算较为复杂。除了求梯度以外，还要计算二阶偏导数矩阵和它的逆矩阵，占用机器的储存量也很大。(1)阻尼牛顿法具有二阶收敛速度，即对于正定二元二次函数，应用阻尼牛顿法只要一次迭代就可以达到极小点。五、阻尼牛顿法的特点同最速下降法一样，牛顿型方法也是求解无约束优化问题的一种古老的算法。由于阻尼牛顿法存在上述(2)、(3)所述的缺点，限制了其在解决实际问题中的应用。近年来，人们研究了很多改进的算法，比如后面将要介绍的变尺度法就是在阻尼牛顿法的基础上形成的一种新的无约束优化方法。牛顿法和阻尼牛顿法统称牛顿型方法，这类方法的主要缺点每次迭代过程都要计算函数二阶导数矩阵，并要对该矩阵求逆。这样工作量相当大。特别是矩阵求逆计算，当设计变量维数较高时工作量更大。因此，牛顿法很少被直接采用，但是对于那些容易计算一阶导数和海色矩阵及其逆的二次函数采用牛顿法还是很方便的。第四节共轭方向与共轭方向法一、共轭方向的概念和性质1.问题的提出

二次函数是最简单的非线性函数，而二阶导数矩阵为正定的目标函数在极值点附近又都近似于二次函数。所以研究二次函数的无约束极值问题，可以推广到一般无约束问题。二次函数的一般矩阵表达式如下

(4-1)

如图所示，二元二次函数的等值线为一族椭圆，若按最速下降法搜索极小点,从初始点出发，沿方向作一维搜索，得到方向的极小点，再从出发向下搜索。如继续用最速下降法，这时应沿负梯度方向搜索，即，显然与正交，即。（4-2）

下面就来讨论一下直接指向极小点的搜索方向需要满足什么样的条件。若直接指向极小点，则迭代公式可写成式中是方向上的最佳步长因子。对前面式（4-1）二次函数的一般矩阵表达式进行求导，得（4-3）

当时，，因为是极小点，所以应满足极值点的必要条件，即将上面式（4-3）的迭代公式代入上式，得（4-4）

由于在点的梯度可以表示为于是式（4-4）可以简化为（4-5）

将式（4-5）左乘，并考虑式（4-2）和，则有式（4-6）即为从点出发直接指向目标函数的极小点的搜索方向所需满足的条件。（4-6）

从上述推导可知，在满足(4-6)的条件下，对正定的二元函数，可从任意初始点出发，沿和方向，经二次搜索即可达到极小点。把满足式(4-6)的向量和称为对的共轭向量，或者称与为的共轭方向。

2.共轭方向的概念由前面分析可知，设为阶实对称正定矩阵，如果在维欧氏空间中有两个维非零向量与满足（4-7）

则称向量与关于实对称正定矩阵是共轭的。或简称与关于共轭，或与为的共轭方向。（4-8）

如果非零向量组，且这个向量组中的任意两个向量关于阶实对称正定矩阵是共轭的，即满足式则称向量组关于矩阵是共扼的，或简称该向量组为的共轭方向。当(单位矩阵)时，式(4-8)变成另外，对于某一固定的矩阵来说，和也不是唯一的，即存在多于一对向量与满足式(4-7)。例如：若，，，则若，，同样可得3.共轭方向的性质性质1

设为阶对称正定矩阵，若非零向量组是对共轭的，则这n个向量是线性无关的。性质2

从任意初始点出发，顺次沿n个的共轭方向进行一维搜索．最多经过n次迭代就可以找到由式(4-1)所表示的二次函数的极小点。性质3

在n维空间中互相共轭的非零向量的个数不超过n。二、共轭梯度法采用共轭方向进行搜索的方法统称为共轭方向法。实际上，提供共轭向量组的方法有许多种，从而可以形成各种具体的共轭方向法。共轭梯度法就是共轭方向法的一种，它与其他共轭方向算法的区别，就在于在该方法中每一个共轭向量都是依赖于迭代点处的负梯度而构造出来的。1.共轭方向的构成

对于正定二次函数从任意沿

给定的初始点出发，先沿着负梯度方向进行一维搜索，求得极小点。然后每迭代一步就构成一个共轭方向，经过次迭代，产生个互相共轭方向，第个迭代点，就是极小点。如下图所示。考虑第步迭代，从迭代点出发，作一维搜索，求极小点，即式中最优步长因子，可由下式求得在和两点函数的梯度分别为由式上面两式相减得（4-9）

为了简便起见，令将上式左乘，得到（4-10）

根据极小点的迭代方程，可以将上面式（4-9）简化为为使次的搜索方向与共轭，应使将上式代入（4-10）中，得（4-11）上式表明了共轭方向与梯度之间的关系，同时也表明了沿着方向进行一维搜索，所得到的终点和起点的梯度之差与共轭方向正交。式中要使得求出的与共轭，故称为共轭系数，它可以根据共轭方向与梯度的关系求得。将上式代入式（4-11），得共轭梯度法在点构成一个新的共轭方向，是利用迭代点的负梯度与前一步迭代的搜索方向两者的线性组合而成的，即（4-12）（4-13）由于与正交，故有将以上两个关系代入，并展开式（4-13）得即

式中，分别为点，的梯度的模。

把上式代入式（4-12），就可利用相邻两个迭代点的梯度来求得共轭方向，所以这种方法称为共轭梯度法。综上所述得到一组共轭梯度法的计算公式为（4-14）

2.共轭梯度法的计算步骤(1)给定初始点，允许误差，输入维数n，计算函数在初始点处的梯度，即

(2)用一维搜索方法求