工程优化第4章-2

最优性条件最速下降法牛顿法及其阻尼牛顿法共轭方向法共轭梯度法变尺度法（DFP算法和BFGS算法）第4章无约束最优化方法无约束最优化问题：从而得到第k+1次迭代点，即步长由精确一维搜索得到。最速下降法负梯度方向假设f连续可微，最速下降法向极小点逼近是曲折前进的，这种现象称为锯齿现象。除特殊的目标函数和极特殊的初始点外，这种现象都会发生。1.相邻两次迭代的方向互相垂直最速下降法的两个特征注：在最速下降法中，利用精确一维搜索求最佳步长，导致相邻两次迭代的搜索方向总是垂直的，使得逼近极小点过程是“之”字形，

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

优点：理论明确，程序简单，每次的计算量小，所需的存

储量小，对初始点要求不严格。缺点：收敛速度并不快，因为最速下降方向仅仅是指某点

的一个局部性质。最速下降法相邻两次搜索方向的正交性，决定了迭代全

过程的搜索路线呈锯齿状，远快近慢。最速下降法的优缺点Newton法

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

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

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

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

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

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

令，转步骤2.

步长取常数1牛顿方向步骤1.

选定初始点,计算步骤2.

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

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

令，转步骤2.

步骤3中的搜索方向，可以通过方程组求解，这样可以减少计算工作量，且解线性方程组已有标准程序。x1,ε>0,k=1▽2f(xk)d=-▽f(xk)

得dk,xk+1=xk+dk||▽f(xk+1)||<ε?STOP.xk+1驻点YesNok=k+1注：若▽2f(xk)非正定时进行相应处理Newton法框图计算解：取初始点代入Newton迭代公式，此即为问题的最优点例：用Newton法求的极小点。一步即达到最优解Newton法----算例设其中f(x)的极小点即是正定二次函数等值面的中心，下面用Newton法求解f(x)的极小点。一步即达到最优解

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

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

从任意初始点出发，经有限次迭代总可以达到正定二次函数的极小点，称这样的算法具有二次收敛性。Newton法具有二次收敛性

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

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

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

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

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

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

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

(3)每次迭代都要计算或者求解方程组可能不存在；

方程组是奇异的，病态的；非正定，

(4)收敛于鞍点或极大点的可能性并不小。当Hesse矩阵正定时，从而可能不是下降方向。Newton法的改进Newton法的缺点和优点都很突出，本身并不实用；Newton法的改进方法是求解无约束优化问题的有效方法之一。

保留Newton法的优点，克服部分缺点。针对Newton法的缺点(1)对多数算法不具有全局收敛性：

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

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

,得到下个迭代点

这样修正之后通常可改进Newton法的缺点(1)和(4)。Newton法的改进----阻尼Newton法每次迭代目标函数值一定有所下降缺点(1)对多数算法不具有全局收敛性：

(4)收敛于鞍点或极大点的可能性并不小；设f(x)存在连续二阶偏导数，函数的Hesse矩阵正定，且水平集有界，则阻尼Newton法或者在有限步迭代后终止；或者得到的无穷点列有如下性质：(1)为严格单调下降序列；(2)有唯一聚点，它是f(x)的最小点。Newton法的改进----阻尼Newton法特点：可改善局部收敛性。收敛性定理：例：用阻尼牛顿法求解下列无约束优化问题，已知解故计算令得此即为问题的最优点一步即达到最优解Newton法的进一步修正

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

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

(3)可能不存在，即使存在，也未必正定，因而牛

顿方向不一定是下降方向。牛顿法还有其他的修改方式。缺点（3）的改进方法之一：

当dk为函数上升方向时，可向其负方向搜索，

但可能出现±dk

均非下降方向的情况。为减小工作量，取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.2，4.3

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

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

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

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

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

定义2

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

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

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

1,d

2两进行次精确一维搜索就可以求到极小点x*，即x*是f(x)的极小点，故x*是f(x)的驻点，将等式两边同时左乘得：

两次迭代要得到二元二次函数的极小点，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