第四章 第四节

§2.4无约束优化法

梯度法牛顿法

共轭方向法变尺度法

共轭梯度法一、梯度法

1.基本思想梯度方向是函数增加最快的方向，而负梯度方向是函数下降最快的方向；梯度法以负梯度方向为搜索方向，每次迭代都沿着负梯度方向一维搜索，直到满足精度要求为止；因此，梯度法又称为最速下降法。

设在某次迭代中已取得迭代点，从该点出发，取负梯度方向：式中，这样，第k+1次迭代计算所得的新点为：梯度法迭代公式

因为为已知，故和易求出，只要知道步长后，就可以得到新点，且能保证如此反复计算，直到达到最优点。为了使目标函数值在搜索方向上获得最多的下降，沿负梯度方向一维搜索，从而求得最优步长。2.迭代步骤步骤一

任选初始点，计算精度ε，令k=0；步骤二计算点的梯度及梯度的模，并令步骤三判断是否满足精度指标若，则为近似最优点，迭代停止，输出最优解和若不满足，转下一步步骤四以为出发点，沿负梯度方向求最优步长，即沿进行一维搜索，求能使函数值下降最多的步长因子；步骤五确定新的近似点，此点就是下次迭代的出发点，即步骤六令k=k+1转步骤二，直到满足精度要求为止。给定、k=0

？转出k=k+1梯度法的程序框图3.举例用梯度法求函数的极小值，初始点，计算精度。解(1)计算梯度：(2)计算函数在点的梯度及梯度的模：(3)因为，不满足精度指标，转入第(4）步；(4)从出发，沿着方向一维搜索，将代入目标函数并求其极小值式中为单变量α的一维函数，令

所以求得一维优化的最优步长(5)新点(6)计算目标函数在点的梯度及梯度的模

由于已满足精度要求，故停止迭代下去，得到最优解为：二、牛顿法

1.基本思想设目标函数是连续二阶可微的，将函数在点按泰勒级数展开，并取到二次项：将其展开为：对x求导，其极值点必满足一阶导数为零，所以，得到上式与一维搜索公式比较，则有搜索方向，步长因子牛顿法的迭代算式其中称为牛顿方向。2.迭代步骤步骤一给定初始点，计算精度ε，令k=0；步骤二计算点的梯度、二阶导数矩阵及其逆矩阵。步骤三构造搜索方向步骤四沿方向进行一维搜索，得迭代点步骤五收敛判断：若，则为近似最优点，迭代停止，输出最优解和终止计算。若不满足，令k=k+1，转第二步继续迭代。3.举例用牛顿法求函数的极小值。解：(1)取初始点(2)计算牛顿方向故(3)极小值

数学分析表明，牛顿法具有很好的局部收敛性质，对二次函数来说，仅一步就达到优化点，但对一般函数来说，在一定条件下，当初始点的选取充分接近目标函数的极小点时，有很快的收敛速度，但若初始点选取离最小点比较远，就难保证收敛；牛顿法必须求一阶、二阶导数及求逆阵，这对较复杂的目标函数来说，是较困难的。三、共轭方向法椭圆的共轭方向共轭方向的基本思想1.椭圆的共轭方向如图所示的椭圆中，任意一组平行弦的中点的连线必位于过椭圆中心O的直线S上，这些平行弦所组成的直线族的方向S1与中点连线方向S互称为共轭方向，即S1与S互为共轭方向。

椭圆中的平行弦的极限情况是与椭圆相切的弦S0，根据一维搜索观点，该弦S0与椭圆的切点就是沿S0方向的一维搜索的优化点。共轭方向的代数含义是：设有两个向量Si与Sj及n×n阶对称正定矩阵A，若满足则称两向量Si与Sj对于矩阵A共轭。2.共轭方向的基本思想设二元函数的极值点为，将函数在展开成泰勒级数，并取其二次项，若其海色矩阵为正定矩阵，则其目标函数的等值线的极值点附近是近似的同心椭圆族，根据椭圆的共轭方向，只要沿两个相互平行的方向S1进行一维搜索，找出目标函数沿该两个方向的极小点，然后沿与S共轭的方向进行一维搜索，就可以求得目标函数的优化点，也就是说共轭方向法是以椭圆的共轭方向作为搜索方向的。

在n维空间中，用数学归纳法可以证明，对n维二次目标函数，从任意点出发，可以找到n个共轭的向量。依次对这些向量分别进行一维搜索，就可以找到n维二次目标函数f(X)的极小点，即应用这种算法通过有限次（即n步），可以得到目标函数的极小点。

如果一种算法，从理论上讲经过有限步的搜索可以求出二次目标函数的极小点，则称这种算法具有二次收敛性，因此，共轭方向法具有二次收敛性。基于共轭方向的思想，发展起来了多种共轭方向法，在此介绍比较成熟的三种方法：变尺度法、共轭梯度法和Powell法。四、变尺度法

变尺度法是优化方法在最近二十几年来发展起来的最有影响的研究成果之一，它被公认为是求解无约束极值问题的最有效的算法之一，这种方法是在牛顿法基础上发展起来的一种共轭方向法，用得较多的是DFP变尺度法。1.DFP(Davidon-Fletcher-Powell)

牛顿法虽比梯度法收敛的快，但必须求目标函数的二阶导数及逆阵，不仅困难且工作量大，因此在牛顿法基础上Davidon-Fletcher-Powell提出了用一个近似矩阵代替求二阶导数及逆阵，而且该矩阵在每一次迭代中都不同，所以称为变尺度矩阵。一维搜索中最优步长因子:变尺度法的搜索方向为:迭代公式为:2.迭代步骤步骤一

取初始点，计算精度ε；步骤二令k=0,,I为单位阵，搜索方向；步骤三一维搜索(梯度法）；步骤四计算(k+1)步梯度，步骤五判别精度指标：如果，则为极小点；否则转下一步。步骤六计算近似矩阵，构造新的搜索方向；所以令k=k+1，转步骤三，直到满足精度要求为止。3.举例用变尺度法求函数的极小值。解：(1)取初始点：(2)一维搜索(3)如何求？(4)搜索方向

与牛顿法比较其结果非常接近，从本例中可以看出用近似矩阵代替二阶导数及逆阵是可行的。如何判断搜索结束？五.共轭梯度法

1.基本思想从初始点出发，沿着该点负梯度方向一维搜索到，如图所示。然后从出发，按照与上一次搜索方向相共轭的方向进行搜索，也就是，A为对称正定矩阵。根据共轭方向原理，沿着方向一维搜索，就可以直接达到优化点。2.共轭梯度的递推公式设梯度用g表示，k+1点的梯度可以由k点的梯度推算出来；设目标函数是n维二次函数：式中A——n×n对称正定矩阵；梯度为：现从出发，沿方向一维搜索得：由一维搜索的几何描述可知，搜索方向是处等值线的切线，而点的梯度与该切点切线方向垂直，所以：

和的梯度由式可得以上两式相减得递推公式为：当已知时，可计算。若目标函数是非二次函数，则可将函数按泰勒级数展开，忽略三次方以上的项，然后用二次函数来逼近3.共轭梯度方向共轭梯度法的关键是如何构造梯度的共轭方向。由图可以看出，的方向可以看成是和的线性组合，即式中只要求出，则可求出：由梯度递推公式两边乘以得：因为根据共轭方向的含义：所以把代入得：

展开该式得：因为，代入：可得：则有：4.迭代步骤(以二维为例)步骤一取初始点，计算精度ε；步骤二计算梯度，从出发，沿方向一维搜索到；步骤三由式计算；

由式计算；则步骤四从出发，沿方向一维搜索，就可以达到优化点。5.举例用共轭梯度法求函数的极小值。解：(1)第一步是梯度法，取初始点沿方向一维搜索得：(2)计算点的梯度：

由计算(3)计算搜索方向(4)从出发，沿着的方向一维搜索，其最优步长由此可得：(5)判断是否达到精度ε=0.01要求：则为极小点。

从以上可以看出，对同一个