第四章 无约束最优化方法-大学课件-阅读-

第四章无约束最优化方法§

4.1

最速下降法问题提出下降最快?时，

取极小值．问题：在点

处，沿什么方向分析：考查：显然当因此：下降最快，亦即最速结论：负梯度方向使下降方向．最速下降法算法Step1:给出停．Step2:

计算

如果Step3:

计算下降方向Step4:

计算步长因子Step5:

令转步２.是正定二次函数,分析：设由精确的线搜索确定的特别当：例1：用最速下降法求解：解：分析：(1)因此：最速下降法是整体收敛的，且是线性收敛的．(2)两个相邻的搜索方向是正交的．收敛性分析定理1:设在上存在且一致连续，则最速下降法产生的序列满足或者对某个

有

或者证明：对于最速下降法，由以上定理立得．收敛性分析定理2:

设

二次连续可微，且其中

是个正常数，对任何给定的初始点最速下降算法或有限终止，或者或者证明：用以上的结论：最速下降法优点程序设计简单，计算量小，存储量小，对初始点没有特别要求．有着很好的整体收敛性，即使对一般的目标函数，它也整体收敛．最速下降法缺点(1)最速下降法是线性收敛的，并且有时是很慢的线性收敛．原因：①仅反映

在

处的局部性质．②相继两次迭代中搜索方向是正交的．小结(1)最速下降法是基本算法之一，而非有效的实用算法．最速下降法的本质是用线性函数来近似目标函数，要想得到快速算法，需要考虑对目标函数的高阶逼近．§

4.2

牛顿法基本思想利用目标函数

在点

处的二阶Taylor展开式去近似目标函数，用二次函数的极小点去逼近目标函数的极小点．算法构造设海色阵二阶连续可微，正定．问题：如何从有唯一极小点，用这个因为

正定，则极小点作为所以要求：即：因此：这就是牛顿法迭代公式．注：这里牛顿法算法停．Step1:给出

Step2:计算Step3:否则计算Step4:令如果并且求解方程得出转步２.例1：用牛顿法求解：解：牛顿法收敛定理定理1:设部极小点，二次连续可微，

是正定．假定的局的海色阵满足Lipschitz条件，即存在使得对于所有

有：元素．则当

牛顿迭代有意义，其中

是海色阵

的充分靠近

时，对于一切迭代序列收敛到

并且具有二阶收敛速度．牛顿法优点(1)如果正定且初始点选取合适，算法二阶收敛．(2)对正定二次函数，迭代一次就可以得到极小点．牛顿法缺点对多数问题算法不是整体收敛的．每次都需要计算

计算量大．每次都需要解方程组有时奇异或病态的，无法确定或

不是下降方向．收敛到鞍点或极大点的可能性并不小．阻尼牛顿法算法Step1:给出停．Step2:计算

Step3:否则计算如果并且求解方程得出Step4:沿

Step5:令进行线搜索，得出转Step2.阻尼牛顿法收敛定理二阶连续可微，又设对任意的使得

在定理2:设存在常数上满足：则在精确线搜索条件下，阻尼牛顿法产生的点列满足：当

是有限点列时，其最后一个点为的唯一极小点．当

是无限点列时，收敛到

的唯一极小点阻尼牛顿法收敛定理二阶连续可微，又设对任意的使得

在定理3:设存在常数上满足：则在Wolfe不精确线搜索条件下，阻尼牛顿法产生的点列

满足：且收敛到的唯一极小点．例2：用阻尼牛顿法求解：解：显然

不是正定的，但：于是，沿方向

进行线搜索，得其极小点

从而迭代不能继续下去．带保护的牛顿法算法为奇异的，转Step8，否则，给出

Step1:若Step2:令

Step3:若Step4:若则转Step8，否则，则转Step9，否则，进行线搜索，求出Step5:沿方向并令Step6:若

Step7:令

Step8:令

Step9:令停；转Step1；转Step5；转Step5.例3：用带保护的牛顿法求解：解：显然

不是正定的，但：于是，因为，

故令，沿

进行线搜索得：第二次迭代：而：使

故令沿

进行线搜索，得出于是:此时:Gill-Murray稳定牛顿法当

正定时，总有Cholesky分解：当

不是正定时，Gill-Murray(1974)提出了强迫正定的修改Cholesky分解，使得：其中

是对角阵．然后解：问题1:如何建立有效的算法？从二次模型到一般模型问题2:什么样的算法有效呢？二次终止性§

4.3

共轭方向法与共轭梯度法算法特点（１）建立在二次模型上，具有二次终止性．（２）有效的算法，克服了最速下降法的慢

收敛性，又避免了牛顿法的计算量大和局部收性的缺点．（３）算法简单，易于编程，需存储空间小等优点，是求解大规模问题的主要方法．共轭方向及其性质定义1:设非零向量，如果：则称是

中任一组是关于

共轭的．注：若

则是正交的，因此共轭是正交的推广．定理1:设为

阶正定阵，非零向量组关于

共轭，则必线性无关．推论1:

设

为

阶正定阵，非零向量组关于

共轭，则向量构成的一组基．推论2:设为

阶正定阵，非零向量组关于

共轭，若向量

与关于

共轭，则共轭方向法算法Step1:给出计算

Step2:如果Step3:计算和初始下降方向停止迭代．使得Step4:

采用某种共轭方向法计算

使得：Step5:

令

转Step2.共轭方向法基本定理定义2:

设

维向量组

线性无关，向量集合为

与

生成的维超平面．引理1:设维向量组则：是连续可微的严格凸函数，线性无关，是

在

上唯一极小点的充要条件是：证：构造：分析：(1)是

维严格凸函数．充要条件是(2)

是

在

上的极小点的是在

上的极小点．定理2:

设

为

阶正定阵，向量组关于

共轭，对正定二次函数由任意

开始，依次进行次精确线搜索：则：（１）（２）是在

上的极小点．时，

为正定二次函数在推论:当上的极小点．共轭梯度法记：左乘并使得：（Hestenes-Stiefel公式）取：共轭梯度法基本性质定理3:对于正定二次函数，采用精确线搜索的共轭梯度法在

步后终止，且对成立下列关系式：（共轭性）（正交性）（下降条件）系数的其他形式（１）FR公式（1964）（2）PRP公式（1969）FR共轭梯度法算法停．Step1:给出Step2:

计算

如果Step3:Step4:由精确线搜索求

Step5:转Step2.例4：用FR共轭梯度法求解：解：化成形式(1)(2)例5：用FR共轭梯度法求解：解：化成形式(1)(2)FR共轭梯度法收敛定理定理4:

假定

在有界水平集上连续可微，且有下界，那么采用精确线搜索下的FR共轭梯度法产生的点列 至少有一个聚点是驻点，即：(1)当(2)当是有穷点列时，其最后一个点是的驻点．是无穷点列时，它必有聚点，且任一聚点都是

的驻点．再开始FR共轭梯度法算法Step1:给出Step2:计算如果停，否则Step3:由精确线搜索求并令：若Step4:计算令如果转Step2;停.令转step2.Step5:若

Step6:计算令转step2,Step7:如果否则转step3.作业：FR共轭梯度法（上机）上机实现FR共轭梯度法．并求解Rosenbrock函数，初始点选线搜索分别采用黄金分割法与强Wolfe线搜索，并对比．§

4.4

拟牛顿法基本思想本质上是基于逼近牛顿法的方法．牛顿法每次都计算

1959年,Davidon提出设想仅用每次迭代中得到的梯度信息来近似海色阵，基于此导致了一类非常成功的拟牛顿法．本节介绍Broyden族拟牛顿法：

DFP算法和BFGS算法．算法原理最速下降法和阻尼牛顿法的迭代公式可统一为：思考：要使上面的算法比最速下降法快，比牛顿法计算简单，且整体收敛性好，关键在于构造矩阵列要求：

的选取既能逐步逼近

又无需计算二阶导数，且具备以下条件：C1：

是对称正定阵．C2：

由

经简单修正而得：C3：

满足下面的拟牛顿方程．（推导如下）设

是二次连续可微的，则：令：令：

因此：（对二次函数为等式）若

非奇异：设想：这样（拟牛顿方程）就可很好的近似拟牛顿算法Step1:给出

Step2:计算

Step3:Step4:精确线搜索求

Step5:若停；否则转Step7.使拟牛顿方程成立．Step6:计算

Step7:校正

Step8:转Step3.DFP校正公式是

维待定向量．要求：所以：令：得：因此：所以：（DFP校正公式）例6：用DFP算法求解：取解：

(1)(2)注:（１）DFP算法具有二次终止性．（２）搜索方向是共轭方向：DFP校正公式的正定继承性引理2:设为正定阵，且则：为正定阵的充要条件是定理5:

在DFP算法中，

如果

正定，则整个矩阵列

都正定．DFP算法的二次终止性推论:

在上面定理条件下：DFP算法至多经过

次迭代就可得到极小点，即存在

有：若

则BFGS校正公式(称为关于

的BFGS校正公式或互补DFP公式)由上式可得：对称秩一校正公式要求：因此：即：要求Hesse逆近似也是对称的，取：注:通常不能保证

的正定性．分母可能取零,修正公