最优化计算方法(工程优化) 第4章

最优性条件最速下降法牛顿法及其阻尼牛顿法共轭方向法共轭梯度法变尺度法（DFP算法和BFGS算法）第4章无约束最优化方法

目的是找中的一点，使对，均有，称为(1)的全局极小点。

无约束最优化问题：求解(1)的计算方法称为无约束最优化方法。

无约束最优化方法应用广泛，理论也比较成熟；可将约束优化问题转化为无约束优化问题来处理；最优化方法中的基本方法---无约束优化方法：利用函数的一阶或二阶导数的方法收敛速度快，需要计算梯度或者Hesse矩阵：仅利用函数值的信息，寻找最优解不涉及导数，适用性强，但收敛速度慢可求得目标函数的梯度时使用解析法在不可能求得目标函数的梯度或偏导数时使用直接法本章介绍解析法最优性条件(OptimalityConditions)

所谓最优性条件，是指最优化问题的最优解所要满足的必要条件或充分条件。

这些条件对于最优化算法的建立和最优化理论的推导都是至关重要的。

解析法要用到目标函数的梯度或者Hesse矩阵，容易想到利用一阶必要条件将无约束优化问题转化成一个梯度为0确定的方程组。这里用到的一阶必要条件就是最优性条件。定理(一阶必要条件)

设，若为的局部极小点，且在内连续可微，则无约束优化的最优性条件----一阶必要条件

若为的局部极小点，且在内二次连续可微，则半正定。无约束优化的最优性条件----二阶必要条件定理（二阶必要条件）定理(二阶充分条件)

设，若在内二次连续可微，且正定，则为的严格局部极小点。

如果负定，则为的严格局部极大点。无约束优化的最优性条件----二阶充分条件定理(一阶充要条件)

设是凸函数且在处连续可微，则为的全局极小点的充要条件是无约束优化的最优性条件----凸优化的一阶条件定理(一阶必要条件)

设是严格凸函数且在处连续可微，若则为的唯一全局极小点。例：利用最优性条件求解下列问题：解：令即：得到驻点：无约束优化的最优性条件利用二阶条件判断驻点是否是极小点利用一阶条件求驻点函数的Hesse阵：在点处的Hesse阵依次为：无约束优化的最优性条件利用二阶条件判断驻点是否是极小点的行列式小于0；无约束优化的最优性条件是正定矩阵；是负定矩阵；是鞍点；是极小点；是极大点。对某些较简单的函数，这样做有时是可行的；但对一般n元函数f(x)来说，由条件

得到的是一个非线性方程组，解它相当困难。为此，常直接使用迭代法。(1)选定某一初始点，并令(2)确定搜索方向(3)从出发，沿方向求步长，以产生下一个迭代点(4)检查得到的新点是否为极小点或近似极小点。，转(2)继续进行迭代。

在以上步骤中，选取步长可选用精确一维搜索或者非精确一维搜索，下降方向的选取正是下面我们要介绍的，下降方向选取的不同，得到不同的算法。若是，则停止迭代。线搜索迭代法的步骤否则，令从而得到第k+1次迭代点，即步长由精确一维搜索得到。最速下降法负梯度方向这是函数值减少最快的方向假设f连续可微，最速下降法负梯度方向是函数值减少最快的方向？令是单位长度的向量，

P是什么方向时，函数值下降最快？也就是p是什么方向时，取得最小值？

当时，最小，最小值为，此时由可得

最速下降法是求多元函数极值的最古老的数值算法，早在1847年法国数学家Cauchy提出该算法，后来Curry作了进一步的研究。

该方法直观，简单，计算方便，而且后来的一些新的有效的方法大多数是对它的改进，或受它的启发而得到的。最速下降法(1)选定某一初始点，并令(2)若，否则转（3）；

由精确一维搜索确定步长步长，即由一个极小化问题求得最佳步长最速下降法的迭代格式(3)令转（2）。算法框图x1,ε>0,k=1||▽f(xk)

||<ε?Yesstop.xk–解Nodk=－▽f(xk

)解minf(xk+λdk)s.t.λ>0得xk+1=x(k)+λkdkk=k+1最速下降法框图

例利用最速下降法求解令解：函数的梯度为第1次迭代：取得令得第2次迭代：令得第3次迭代：继续迭代可得到函数的近似最优解。最速下降法的收敛性分析

设目标函数f(x)连续可微，且水平集有界，则最速下降法或者在有限迭代步后终止；或者得到点列，它的任何聚点都是f(x)的驻点。

在收敛定理的假设下，若f(x)为凸函数，则最速下降法或在有限迭代步后达到最小点；或得到点列，它的任何聚点都是f(x)的全局最小点。收敛性定理：推论：

最速下降法在两个相邻点之间的搜索方向是正交的。最速下降法向极小点逼近是曲折前进的，这种现象称为锯齿现象。除特殊的目标函数和极特殊的初始点外，这种现象都会发生。令利用精确一维搜索，可得由此得出1.相邻两次迭代的方向互相垂直最速下降法的两个特征注：在最速下降法中，利用精确一维搜索求最佳步长，使得相邻两次迭代的搜索方向总是垂直的，使得逼近极小点过程是“之”字形，

这样从任何一个初始点开始，都可以很快到达极小点附近，但是越靠近极小点步长越小，移动越慢，导致最速下降法的收敛速度很慢。实际运用中，在可行的计算时间内得不到需要的结果。最速下降法收敛速度慢最速下降法的两个特征对正定二次函数，用最速下降法产生的点列：偶数项点列均在一条直线上，奇数项点列也均在一条直线上，且都过最优点.最速下降法的两个特征

对正定二次函数，用最速下降法产生的点列：偶数项点列均在一条直线上，奇数项点列也均在一条直线上，且都过最优点.

则：分析：因为相邻方向正交，t与k有关

优点：理论明确，程序简单，每次的计算量小，所需的存储量小，对初始点要求不严格。缺点：收敛速度并不快，因为最速下降方向仅仅是指某点的一个局部性质。最速下降法相邻两次搜索方向的正交性，决定了迭代全过程的搜索路线呈锯齿状，远快近慢。最速下降法的优缺点

最速下降法不是好的实用算法，但是一些有效算法是通过对它的改进或利用它与其他收敛快的算法结合而得到的，因此它是无约束优化的方法之一。

为了清除最佳步长最速下降法中两个搜索方向正交的不良后果，提出了许多改进的方法，如：(1)选择不同初始点

例令最速下降法的改进取初始点第1次迭代得然后再从开始新的迭代，经过10次迭代，得最优解计算中可以发现，开始几次迭代，步长比较大，函数值下降将较快，但当接近最优点时，步长很小，目标函数值下降很慢。如果不取初点为而取一步就得到了极小点。

可见：造成锯齿现象与初始点的选择有关，但怎样选一个初始点也是一件困难的事。第1次迭代

虽然后一初始点较前一初始点离最优点远，但迭代中不含上面出现的锯齿现象。

采用非精确一维搜索求步长,

可使相邻两个迭代点处的梯度不正交，从而改变收敛性。

对于最速下降法，有时为了减少计算工作量，采用固定步长，称为固定步长最速下降法。

但

到底取多大，没有统一的标准，

取小了，收敛太慢，而取大了，又会漏掉极小点。（2）采用不精确的一维搜索：最速下降法的改进（3）采用加速梯度法：

由于最速下降法在极小点附近成“锯齿”状，因此下降过程中的搜索方向可取

下两步继续用最速下降方向即负梯度方向。

Shah等人于1964年提出了一种“平行切线法”（简记为PARTAN法），又称加速梯度法。最速下降法的改进负梯度方向和结合这两种方向交替使用，效用要比最速下降法好的多。

用于二次函数时的收敛速度分析定理：二次函数 A为对称正定，分别为其最小和最大特征值，从任意初点出发，对二次函数，用最速下降法产生的序列，对于有由于

而函数的极小点恰好是。故最速下降法对于二次函数关于任意初点均收敛，而且是线性收敛的。

下面说明最速下降法收敛性的几何意义。考虑具有对称正交矩阵的函数函数的等值线为其中

用于二次函数时的收敛速度分析改写为：

这是以和为半轴的椭圆从下面的分析可见两个特征值的相对大小决定最速下降法的收敛性。

（1）当时，等值线变为圆此时因而由上述定理知：

即只需迭代一步就到了极小点，这表明最速下降法用于等值线为圆的目标出发时，只需迭代一步就到了极小点。（2）当时,等值线为椭圆。此时对于一般的初始点将产生锯齿现象。

（3）当，等值线是很扁的椭圆

此时，对于一般的初始点,收敛速度可能十分缓慢，锯齿现象严重。

用于二次函数时的收敛速度分析Newton法

前面介绍精确一维搜索时介绍了牛顿法，即用目标函数的二次泰勒多项式近似代替函数本身，用二次多项式的极小点近似函数的极小点。这种方法可以推广到多维的情形。求解无约束极小化问题的最古老的算法之一，现在已经发展成一类算法-----Newton型方法。Newton法一维优化的Newton迭代公式多维优化的Newton迭代公式

算法的基本思路：考虑从到的迭代过程，在点处对函数Tayloy展开：Newton法令

，有略去高阶项若Hesse矩阵正定，则存在，由此求出二次函数的极小点为：以此作为极小点的一个新的近似。此公式即为多元函数求极值的Newton迭代公式。Newton法步骤1.

选定初始点,计算已知目标函数,给定误差限.步骤2.

如果，算法停止，，否则转步骤3。步骤3.

计算搜索方向Newton法的计算步骤步骤4.

令，转步骤2.

步骤3中的Newton迭代公式，可以换成通过方程组求得，这样可以减少计算工作量，而且解线性方程组已有标准程序。注意：此时步长取常数1称为牛顿方向x1,ε>0,k=1▽2f(xk)d=-▽f(xk)

得dk,xk+1=xk+dk||dk||<ε?STOP.xk+1极小点YesNok=k+1注：若▽2f(xk)非正定时进行相应处理Newton法框图则:解：取初始点代入Newton迭代公式得：此即为问题的最优点例：用Newton法求的极小点。一步即达到最优解Newton法----算例

当f(x)为正定二次函数时，用Newton法从任意初始点可一步迭代达到最优解。

二次收敛性：从任意初始点出发，经有限次迭代总可以达到正定二次函数的极小点，这样的算法称为具有二次收敛性。Newton法具有二次收敛性设其中f(x)的极小点即是正定二次函数的中心，下面用Newton法求解f(x)的极小点。一步即达到最优解

牛顿法比最速下降法收敛快。

当初始点靠近极小点时，Newton法的收敛速度很快。

当初始点远离极小点时，Newton法可能不收敛，甚至连下降性都保证不了。

Newton法：局部二次收敛Newton法的优缺点优点：当初始点离最优解很近时，算法收敛速度快；

算法简单，不需要进行一维搜索；

对正定二次函数，迭代一次就可得到最优解。Newton法的优缺点缺点：(1)对多数算法不具有全局收敛性：

(2)每次迭代都要计算Hesse矩阵，计算量大；

(3)每次迭代都要计算或者求解方程组可能不存在或者方程组是奇异的或病态的(有时非正定)，可能不是下降方向。

(4)收敛于鞍点或极大点的可能性并不小。当Hesse矩阵正定时Newton法的改进Newton法的缺点和优点都很突出，本身并不实用；在保留优点的同时，对Newton法加以改进，克服部分缺点所得到的改进方法是求解无约束优化问题的有效方法之一。针对Newton法的缺点(1)对多数算法不具有全局收敛性：

和(4)收敛于鞍点或极大点的可能性并不小，步长不取固定值1，而是采用精确一维搜索找最佳步长，这就是阻尼Newton法。在Newton迭代中，取,

加入精确一维搜索：求得最佳步长

,得到下个迭代点

这样修正之后通常可改进Newton法的缺点(1)和(4)。Newton法的改进----阻尼Newton法每次迭代目标函数值一定有所下降设f(x)存在连续二阶偏导数，函数的Hesse矩阵正定。且水平集有界，则阻尼Newton法或者在有限步迭代后终止；或者得到的无穷点列有如下性质(1)为严格单调下降序列；(2)有唯一聚点，它是f(x)的最小点。Newton法的改进----阻尼Newton法特点：可改善局部收敛性；当dk为函数上升方向时，可向其负方向搜索，但可能出现±dk

均非下降方向的情况。收敛性定理：例：用阻尼牛顿法求解下列无约束优化问题，已知解故计算令得此即为问题的最优点一步即达到最优解Newton法的进一步修正

阻尼Newton法改进了Newton法，但还是存在缺点:

(2)每次迭代都要计算Hesse矩阵，计算量大；

(3)可能不存在，即使存在，也未必正定，因而牛顿方向不一定是下降方向。为此人们对牛顿法提出了多种方式的修改。为减小工作量，取m（正整数），使每m次迭代使用同一个Hesse阵，迭代公式变为：

Newton法的改进---针对缺点(2)每次计算Hesse矩阵特点：收敛速度随m的增大而下降

m=1时即Newton法，m→∞即线性收敛。(2)Goldstein-Price方法(G-P法)：取采用下列非精确一维搜索（Armijo-Goldstein准则）：求，使

Newton法的改进---针对缺点(3)非正定和奇异的情况其中特点：在一定条件下，G-P法全局收敛。但当

非正定情况较多时，收敛速度降为接近线性。(3)Levenberg-Marguardt法（L-M法）：主要思想：找到尽可能小的

使

正定。用

取代

进行迭代，其中I为单位矩阵。特点：全局二阶收敛。Newton法的改进---针对缺点(3)非正定的情况作业：

P994.1--4.5

最速下降法，计算步骤简单，但收敛速度慢。共轭方向法计算效果好，应用广泛；共轭方向法和共轭梯度法这就是要讨论的共轭方向法和共轭梯度法。Newton法和阻尼Newton法都有一个优点：收敛速度快，但需要计算Hesse矩阵和Hesse矩阵的逆矩阵，计算量和存储量都很大。

需要寻找一种好的算法，这种算法能够兼有这两种方法的优点，又能克服它们的缺点，即收敛速度快同时计算简单。函数的系数矩阵有关的共轭方向。共轭梯度法是最著名的共轭方向法，其搜索方向是与正定二次

设是对称正定矩阵，如果则称向量p和q是A共轭的(或称为A正交)。

如果对有限个向量，有共轭方向法---共轭方向及其性质若

则p与q是正交的。定义1

定义2

则称这个向量组是A-共轭(或A正交)向量组，也称它们是一组A共轭方向。共轭是正交的推广共轭向量组是正交向量组的推广。假设f(x)是n元正定二次函数对二维情况（n=2）任选取初始点x1沿某个下降方向d1作精确一维搜索，得共轭方向法---共轭方向及其性质如果按最速下降法，选取

如果希望下次迭代就得到最优解，α0d0x0x1x*11α1d1d1由精确一维搜索的性质，可知共轭方向法---共轭方向及其性质则将发生锯齿现象。共轭方向法---共轭方向及其性质

如果能够选定这样的搜索方向，那么对于二元二次函数只需依次沿搜索方向d

1,d

2两进行次精确一维搜索就可以求到极小点x*，即x*是f(x)的极小点，故x*是f(x)的驻点，将等式两边同时左乘得：2次迭代要得到二元二次函数的极小点，d1必须满足的条件是：搜索方向d1和d2是A共轭的。即d1是某个下降方向性质2

若Rn中的非零向量p1,p2,…,pm是A共轭向量组，则这m

个向量是线性无关的。性质3

在n维空间中互相共轭的非零向量的个数不超过n。

性质4

设n元函数f(x)=1/2xTAx+bTx+c,A=AT正定，又设n维非零向量组p1,p2,…,pn是A共轭向量组，从任意点x1出发，依次以p1,p2,…,pn

为搜索方向进行精确一维搜索，则

(1)▽f(xk+1)与p1,p2,…,pk(k=1,2,…,n)正交；

(2)最多n次迭代必达到二次函数f(x)的极小点。

性质1

在n维空间中与n个线性无关的向量都正交的一定是零向量。

共轭方向法---共轭方向的性质因为共轭方向法---共轭方向及其性质存在一组实数证明：假设线性无关，向量与正交，证线性无关，所以可作为空间中的一组基，故可由线性表出，即故性质1

在n维空间中与n个线性无关的向量都正交的一定是零向量。

因为共轭方向法---共轭方向及其性质因为A正定，证明：假设要证线性无关,是A共轭向量组，两边同乘得证。性质2

若Rn中的非零向量p1,p2,…,pm是A共轭向量组，则这m

个向量是线性无关的。只需证明所以故共轭方向法---共轭方向及其性质证明：利用性质2即可。性质2

若Rn中的非零向量p1,p2,…,pm是A共轭向量组，则这m

个向量是线性无关的。性质3

在n维空间中互相共轭的非零向量的个数不超过n。

Rn中线性无关的非零向量最多有n个。性质4

设n元函数f(x)=1/2xTAx+bTx+c,A=AT正定，又设n维非零向量组p1,p2,…,pn是A共轭向量组，从任意点x1出发，依次以p1,p2,…,pn

为搜索方向进行精确一维搜索，则

(1)▽f(xk+1)与p1,p2,…,pk(k=1,2,…,n)正交；

(2)最多n次迭代必达到二次函数f(x)的极小点。

共轭方向法---共轭方向的性质性质4中(1)▽f(xk+1)与p1,p2,…,pk(k=1,2,…,n)正交；

是按照精确一维搜索得到的，所以有共轭方向法---共轭方向及其性质下证证明：共轭方向法---共轭方向及其性质P1,P2,…,

Pn

是A共轭向量组故▽f(xk+1)与p1,p2,…,pk

(k=1,2,…,n)正交。性质4中(1)▽f(xk+1)与p1,p2,…,pk(k=1,2,…,n)正交；性质4中(2)

最多n次迭代必达到二次函数f(x)的极小点。假设都不是0，下证共轭方向法---共轭方向及其性质

利用(1)的结果，与A共轭向量组P1,P2,…,

Pn

都正交，由性质1可知，证明：性质1

在n维空间中与n个线性无关的向量都正交的一定是零向量。

性质4

设n元函数f(x)=1/2xTAx+bTx+c,A=AT正定，又设n维非零向量组p1,p2,…,pn是A共轭向量组，从任意点x1出发，相继以p1,p2,…,pn

为搜索方向进行精确一维搜索，则

(1)▽f(xk+1)与p1,p2,…,pk

(k=1,2,…,n)正交；

(2)最多n次迭代必达到二次函数f(x)的极小点。

共轭方向法---共轭方向的性质定义：一个算法若能在有限步内求得正定二次函数的极小点，则称该算法具有二次收敛性(又称二次终止性)。

由性质4可知，若能找到一组A共轭向量，则前面提到的结合最速下降法和Newton法优点的算法就找到了，就是共轭方向法，这个算法具有二次收敛性。

在下降迭代法中，若取下降方向是共轭方向，所得到的方法我们称为共轭方向法。怎么选取共轭方向？共轭方向的生成与共轭梯度法

共轭方向的选取有很大任意性，而一组不同的共轭方向就对应着不同的共轭方向法。作为一种迭代算法，我们自然希望共轭方向能在迭代过程中逐次生成。

下面先以正定二次函数为例，介绍一种生成共轭方向的方法，再将这种方法推广到非二次函数上。这种方法中每一个共轭向量都是依赖于迭代点处的负梯度而构造出来，所以称为共轭梯度法，它是共轭方向法中的一种。令(2)若，停止，成的正交锥中找一个向量，即令使得与共轭，即由共轭梯度法(1)从任取初始点x1

出发，沿负梯度方向进行精确一维搜索:可得否则在和张(5)若，停止，成的正交锥中找一个向量，即令使得与共轭，即由共轭梯度法(3)在x2

处沿p2方向进行精确一维搜索，可得(4)以此类推，否则在和张共轭梯度法这样便构造了一组向量

实际上，这组向量是一个A共轭向量组。相邻两个向量是共轭的共轭梯度法定理1：设向量组是由上述方法产生的向量组，向量组是由各点的梯度生成的向量组，

()则

(1)是正交向量组；

(2)是A共轭向量组。证明：提示用归纳法。共轭梯度法定理1：设向量组是由上述方法产生的向量组，向量组是由各点的梯度生成的向量组，()则

(1)是正交向量组；

(2)是A共轭向量组。证明：归纳法：由的构造过程知，是A共轭的，即结论(2)成立；利用精确一维搜索的性质知，而故结论(1)成立。由假设可知，要证明时结论成立，只需证明(a)证明所以结论(a)成立，进而结论(1)成立。与正交，与A共轭。与正交;是A共轭向量组，利用性质4(1)可知，性质4

设n元函数f(x)=1/2xTAx+bTx+c,A=AT正定，又设n维非零向量组p1,p2,…,pn是A共轭向量组，从任意点x1出发，相继以p1,p2,…,pn

为搜索方向进行精确一维搜索，则

(1)▽f(xk+1)与p1,p2,…,pk

(k=1,2,…,n)正交；因为(b)证明结论(b)成立，进而结论(2)成立。与是A共轭的;由的构造过程知，与是A共轭的;下证与是A共轭的;共轭梯度法定理1：设向量组是由上述方法产生的向量组，向量组是由各点的梯度生成的向量组，

()则

(1)是正交向量组；

(2)是A共轭向量组。注：为保证方向的共轭性，初始方向取负梯度方向。共轭梯度法性质4

设n元函数f(x)=1/2xTAx+bTx+c,A=AT正定，又设n维非零向量组p1,p2,…,pn是A共轭向量组，从任意点x1出发，相继以p1,p2,…,pn

为搜索方向进行精确一维搜索，则

(1)▽f(xk+1)与p1,p2,…,pk

(k=1,2,…,n)正交；

(2)最多n次迭代必达到正定二次函数f(x)的极小点。

是一个A共轭向量组每一个搜索方向都依赖迭代点处的负梯度构造出来，对应的算法称为共轭梯度法。共轭梯度法存在问题：计算量、存储量都很大

针对

f(x)=1/2xTAx+bTx+c,A=AT正定，最多n次迭代达到极小点找到了一组共轭方向：针对一般的函数，将这组方向进行推广：直接对(*)式推广：在正定二次函数的前提下，将变形怎么解决呢？能否将中的A去掉？定理2：设，向量组

是由上述方法构造的A共轭向量组，，利用前面所得的公式，得到几个等价的计算公式：共轭梯度法利用定理1，可知

是正交向量组，因此(2)中

;并且

.共轭梯度法

对于正定二次函数，上面得到的5个计算公式是等价的；这5种共轭梯度法也是完全等价的；SW共轭梯度法DM共轭梯度法FR共轭梯度法PPR共轭梯度法介绍FR共轭梯度法Daniel共轭梯度法简洁，用的最多更好用

对于非二次函数，产生的搜索方向不再相同，利用公式(2)-(5),(1)中含有Hesse矩阵，通常不用作业：

P1004.9,4.10,4.12,4.13,4.14,4.17--4.19步骤1.选定初始点。步骤2.如果，算法停止，，否则转步骤3。步骤4.精确一维搜索找最佳步长，令FR共轭梯度法的计算步骤步骤3.取步骤5.如果，算法停止，否则转步骤6。步骤6.如果k=n,令

k=1，转步骤4;

否则转步骤7。步骤7.计算转步骤4。步骤4.精确一维搜索找最佳步长，令FR共轭梯度法的计算步骤步骤5.如果，算法停止，，否则转步骤6。步骤6.如果k=n,令

算法停止,k=1，转步骤4;

否则转步骤7。步骤7.计算转步骤4。

误差可能会使n步迭代得不到正定二次函数的极小点。

Rn中共轭方向最多有n个，n步后构造的搜索方向不再是共轭的，会降低收敛速度，步骤6：重新开始技术：xn+1作为新的x1FR共轭梯度法，已知初始点(1,1)T例题用FR共轭梯度法求下列问题的极值解：1）第一次迭代：沿负梯度方向搜寻计算初始点处的梯度

迭代精度。

FR共轭梯度法精确一维搜索求最佳步长，令FR共轭梯度法得不满足精度，继续迭代：2）第二次迭代：FR共轭梯度法精确一维搜索求最佳步长，因得到最优解:FR共轭梯度法令得

共轭梯度法对正定二次函数，具有二次收敛性；对非二次函数，由于目标函数的Hesse矩阵不再是常数矩阵，因而产生的方向不再是共轭方向；共轭梯度法在一定条件下也是收敛的，且收敛速度通常优于最速下降法，具有较高的求解效率。FR共轭梯度法

设f(x)存在连续一阶偏导数，且函数为凸函数，且水平集有界，则由共轭梯度法得到的点列有如下性质：(1)为严格单调下降序列，且存在；(2)的任意聚点都是f(x)的最优解。FR共轭梯度法

共轭梯度法在无约束优化方法中占有重要的地位，是目前最常用的方法之一。收敛性定理：(1)对凸函数全局收敛（下降算法）；

(2)计算公式简单，不用求Hesse矩阵或者逆矩阵，计算量小，存储量小，每步迭代只需存储若干向量，适用于大规模问题；

(3)具有二次收敛性；

(对于正定二次函数，至多n次迭代可达最优解）

(4)Crowder和Wolfe证明，共轭梯度法的收敛速率不坏于最速下降法。如果初始方向不用负梯度方向，则其收敛速率是线性收敛的；

(5)共轭梯度法是目前求解无约束优化问题最常用的方法之一。共轭梯度法的特点注：不同的αk公式，对于正定二次函数是等价的，对非正定二次函数，有不同的效果，经验上PPR效果较好。作业：

P1004.9,4.10,4.12,4.13,4.14,4.17--4.19Newton法和阻尼Newton法具有收敛速度快的优点，但需要计算Hesse矩阵的逆，计算量大，存储量也很大。变尺度法----一类特殊的拟Newton法

为减少计算量，用一个n阶对称正定矩阵Hk近似代替Hesse矩阵的逆，即，从而搜索方向是，由此搜索方向产生的方法称为变尺度法，Hk称为尺度矩阵，这是一种拟Newton法，被认为是无约束优化问题中最有效的方法之一。所谓拟Newton法是指由Newton法的思想出发产生的一类方法。变尺度法----一类特殊的拟Newton法变尺度法的计算步骤

步骤1.

任取初始点x1,初始尺度矩阵H1,令k=1.

步骤2.

计算

步骤3.

利用精确一维搜索找最佳步长，令

步骤4.

令，转步骤2。

其中称为修正矩阵。修正矩阵选取的不同，对应着不同的变尺度法。x1,H1对称ε>0,k=1dk=-Hk▽f(xk)一维搜索得λk

xk+1=xk+λkdk||xk+1-xk||<ε?修正Hk产生Hk+1Stop.xk+1----解k=k+1yN变尺度法的算法框架构造Hk的原则

变尺度法的关键在于如何构造Hk，为了使算法有较快的收敛速度，需要满足以下几个原则：拟牛顿性质，二次收敛性，稳定性。拟牛顿性质在点处对函数作二阶Tayloy展开：变尺度法----一类特殊的拟Newton法

略去高阶项在xk+1

附近，函数两端求导，得令

可得记Hesse矩阵对称正定，又有变尺度法----一类特殊的拟Newton法称(3)或(4)为拟Newton方程

为了利用不包含二阶导数的矩阵Hk取代

Hk+1满足构造Hk的原则----二次收敛性构造的搜索方向p1,p2,…,pn是一组A

共轭向量且Hn+1=A-1.把算法用于正定二次函数时，至多n次达到极小点。构造Hk的原则----拟牛顿性质变尺度法----一类特殊的拟Newton法拟牛顿方程（或条件）,Hk+1

不唯一。

一个算法若不计算过程的舍入误差，在迭代的每一步都能选择步长使函数单调下降，则称此算法是稳定的。变尺度法----一类特殊的拟Newton法构造Hk的原则----稳定性

若方向

是f(x)在点xk处的下降方向，则每一迭代步总可以找到一个充分小的正数使得函数值下降，即算法是稳定的。迭代方向是下降方向，是保证算法稳定性的一个充分条件。

若Hk对称正定，则

是f(x)在点xk处的下降方向。什么条件能使迭代方向是下降方向？

依据三个原则：拟Newton方程、二次收敛性和算法稳定性，要求Hk满足拟Newton方程、是对称正定矩阵，并且针对正定二次函数，

是一组共轭方向组。变尺度法----一类特殊的拟Newton法Hk构造的要求

构造这样一个对称正定的近似矩阵Hk的一般策略是：

(1)H1取为任意一个n阶对称正定矩阵，通常选取为n阶单位矩阵I;(2)然后通过修正Hk，给出Hk+1

，令变尺度法----一类特殊的拟Newton法Hk的构造策略

构造不同的Hk，也就是构造不同的修正矩阵

，得到不同的变尺度法。

下面介绍DFP变尺度法中Hk的构造过程。DFP算法(Davidon(1959),FletcherandPowell(1963))为保证Hk+1的对称性，令

是常数，

是n维列向量。

H1是对称正定的矩阵，上述方式定义的Hk+1自然是对称的。DFP算法中Hk的构造方法Hk+1满足拟牛顿方程，

，

根据构造Hk+1的三原则----拟牛顿性质、二次收敛性和稳定性，DFP算法构造这样的Hk:对称正定满足拟牛顿方程

DFP算法(Davidon(1959),FletcherandPowell(1963))令DFP算法中Hk的构造方法

简单的，取

满足的uk和

vk并不唯一。即现在对所以DFP算法DFP算法中Hk的构造方法中的未知量都给定了取值-------DFP公式定理1：若,则DFP方法构造的矩阵Hi(i=1,2,…,n)

为对称正定矩阵。证明：数学归纳法（Schwartz不等式，正定矩阵的性质，精确一维搜索的结果。）具体参见P92定理4.12的证明。注：此时搜索方向pk=-Hkgk一定是下降方向。DFP算法定理1：若,则DFP方法构造的矩阵Hk(k=1,2,…,n)

为对称正定矩阵。证明：数学归纳法DFP算法当时，是对称正定矩阵；假设是对称正定矩阵，证明是对称正定的。因为是对称正定矩阵，则由DFP公式可知

是对称的,下证是正定的：下证是正定的：任意给定非零x因为是正定的，所以存在矩阵B,使得先证再证当(1)=0时，线性相关，即存在，使得对称正定。定理2：设用DFP算法求解下列问题其中A为n阶对称正定矩阵。由DFP方法产生的搜索方向为，产生的矩阵为，则(1)

(2)

(3)

证明：参见P93定理4.14的证明DFP算法若H1是单位矩阵，则DFP方法也是一种共轭梯度法。(3)表明DFP方法也是一种共轭方向法。

若目标函数是正定二次函数，则DFP算法经过有限步迭代必达到极小点，既具有二次收敛性。步骤1.选定初始点,初始矩阵步骤2.如果，算法停止，，否则转步骤3。步骤4.精确一维搜索找最佳步长，令DFP算法的计算步骤步骤3.取步骤5.如果，算法停止，，否则转步骤6。步骤6.如果k=n,令

k=1，转步骤4;

否则转步骤7。DFP算法的计算步骤步骤7.令计算和令转步骤4.置k=1,H1=Ink=k+1||▽f(xk+1)||<ε?Stop.x1—解解

minf(xk+λpk)s.t.λ>0得λk,令xk+1=xk+λkpk

k=n?x1=xn+1,g1=gn+1利用DFP公式求得

Hk+1yNyN重新开始x1,ε>0令

pk=-Hk

gk||g1||

=||▽f(x1)

||<ε?Stop.xk+1—解yDFP算法框图：N，已知初始点(2,1)T例用DFP算法求下列问题的极值解：计算函数f的梯度函数：

迭代精度。

DFP算法的算例1）第一次迭代：在初始点x1处的梯度为：取精确一维搜索求最佳步长，令得不满足精度，继续迭代：DFP算法的算例2）第二次迭代：DFP算法的算例令DFP算法的算例精确一维搜索求最佳步长，令得得到最优解:DFP算法的算例定理3：

设f(x)存在连续一阶偏导数，且函数为凸函数，且水平集有界，则由DFP法得到的点列有如下性质

(1)为严格单调下降序列，且存在；

(2)的任意极限点都是f(x)的最优解，且有证明：参见P96定理4.15的证明。DFP算法的收敛性分析DFP算法具有二次收敛性。优点：对n元正定二次函数，当初始矩阵取单位矩阵时，由DFP算法产生的方向是关于其Hesse矩阵共轭的方向，因此，DFP算法最多n次就可得到正定二次函数的极小点，即DFP算法有二次收敛性。

DFP算法实质上是一种共轭方向法；(2)若f(x)是可微的严格凸函数，则DFP算法全局收敛；(3)对非二次函数，DFP算法的效果也很好，它比最速下降法和共轭梯度法要有效的多，收敛速度是超线性的。DFP算法的优缺点缺点：(1)DFP算法的计算量、存储量要比共轭梯度法大，因此，对大规模的优化问题，用共轭梯度法更方便；(2)实际运算中，由于舍入误差的存在以及一维搜索的不精确，算法的稳定性受到影响，从而使得DFP算法的效率受到很大的影响，但BFGS算法受到的影响要小得多。DFP算法的优缺点BFGS算法由前面的推导，我们知道

令

Bk+1满足公式(1)称为另一种拟牛顿条件(或称拟牛顿方程)。

上面的公式(1)只需要交换就可以得到前面的拟牛顿条件：该公式称为关于矩阵Bk的BFGS修正公式，有时也称为DFP的对偶公式。BFGS算法因此只需要在Hk的递推公式互换，并用Bk+1

,Bk

分别取代Hk+1

,Hk，就得到Bk的递推公式，设Bk+1可逆，则由(1)所以满足拟牛顿条件令BFGS算法可知对（2）两边求导，求导方法见文（陈宝林）,得到-------BFGS公式

这个重要公式是由Broyden,Fletcher,Goldfard和Shanno于1970年提出来的。它可以象DFP公式一样使用，数值计算实例表明，它比DFP要好，目前得到广泛的应用。

BFGS算法有变尺度法的全部优点，并且在一定条件下可以证明在BFGS法中使用不精确一维搜索时有全局收敛性。

BFGS算法Broyden（布洛伊登

）族变尺度法将DFP公式记为结合BFGS公式，引入参数，有Broyden族变尺度法将(4)和(5)代入(6)，得到其中将(6)或者(7)给出的修正公式的全体称为Broyden族。当时，即为DFP公式；当时，即为BFGS公式。Broyden族变尺度法

由于DFP和BFGS公式都满足拟Newton方程，因此Broyden族的所有成员也满足拟Newton方程。

Broyden族的任何一个成员都具有一般变尺度法的优点；

DFP算法所具有的许多性质，Broyden算法也有。

在拟Newton法的每次迭代中，可用Broyden族的一个成员作为修正公式。Broyden族只是给出一类拟Newton算法，这个族中包含一个参数。一些文献所介绍的Huang族包含三个参数，Broyden族是Huang族的一个子族。作业P994.