第四章 无约束最优化方法

第四章无约束最优化方法第1页，共72页，编辑于2022年，星期二§

4.1

最速下降法第2页，共72页，编辑于2022年，星期二问题提出问题：在点处，沿什么方向下降最快?分析：考查：时，取极小值．显然当因此：下降最快，亦即最速第3页，共72页，编辑于2022年，星期二结论：负梯度方向使下降方向．最速下降法算法如果停．Step1:给出Step2:计算Step3:计算下降方向Step4:

计算步长因子Step5:令转步２.第4页，共72页，编辑于2022年，星期二分析：设是正定二次函数,由精确的线搜索确定的特别当：第5页，共72页，编辑于2022年，星期二例1：用最速下降法求解：解：第6页，共72页，编辑于2022年，星期二分析：(1)因此：最速下降法是整体收敛的，且是线性收敛的．(2)两个相邻的搜索方向是正交的．第7页，共72页，编辑于2022年，星期二第8页，共72页，编辑于2022年，星期二收敛性分析定理1:

设在则最速下降法产生的序列上存在且一致连续，满足或者对某个

有或者证明：对于最速下降法，由以上定理立得．第9页，共72页，编辑于2022年，星期二收敛性分析二次连续可微，且定理2:

设其中是个正常数，对任何给定的初始点最速下降算法或有限终止，或者或者证明：用以上的结论：第10页，共72页，编辑于2022年，星期二最速下降法优点第11页，共72页，编辑于2022年，星期二(1)程序设计简单，计算量小，存储量小，对初始点没有特别要求．(2)有着很好的整体收敛性，即使对一般的目标函数，它也整体收敛．最速下降法缺点(1)

最速下降法是线性收敛的，并且有时是很慢的线性收敛．原因：①仅反映在处的局部性质．②相继两次迭代中搜索第12页，共72页，编辑于2022年，星期二方向是正交的．小结第13页，共72页，编辑于2022年，星期二(1)最速下降法是基本算法之一，而非有效的实用算法．最速下降法的本质是用线性函数来近似目标函数，要想得到快速算法，需要考虑对目标函数的高阶逼近．§

4.2

牛顿法第14页，共72页，编辑于2022年，星期二基本思想在点

处的二阶Taylor第15页，共72页，编辑于2022年，星期二利用目标函数展开式去近似目标函数，用二次函数的极小点去逼近目标函数的极小点．算法构造设海色阵二阶连续可微，正定．问题：如何从因为正定，则有唯一极小点，第16页，共72页，编辑于2022年，星期二用这个极小点作为所以要求：即：因此：这就是牛顿法迭代公式．注：这里第17页，共72页，编辑于2022年，星期二牛顿法算法Step1:给出如果停．Step2:计算

Step3:否则计算Step4:令转步２.并且求解方程得出第18页，共72页，编辑于2022年，星期二例1：用牛顿法求解：解：第19页，共72页，编辑于2022年，星期二牛顿法收敛定理定理1:设是部极小点，二次连续可微，正定．假定的局的海色阵满足Lipschitz条件，即存在使得对于所有

有：元素．则当牛顿迭代有意义，其中

是海色阵

的充分靠近

时，对于一切

迭代序列收敛到并且具有二阶收敛速度．第20页，共72页，编辑于2022年，星期二牛顿法优点(2)对正定二次函数，迭代一次就可以得到极小点．(1)如果正定且初始点选取合适，第21页，共72页，编辑于2022年，星期二算法二阶收敛．牛顿法缺点(1)对多数问题算法不是整体收敛的．(2)每次都需要计算计算量大．(3)每次都需要解方程组有时奇异或病态的，无法确定或不是下降方向．第22页，共72页，编辑于2022年，星期二(4)收敛到鞍点或极大点的可能性并不小．阻尼牛顿法算法Step1:给出Step2:计算如果停．Step3:否则计算Step4:

沿并且求解方程得出Step5:令进行线搜索，得出转Step2.第23页，共72页，编辑于2022年，星期二阻尼牛顿法收敛定理定理2:设二阶连续可微，又设对任意的使得在阻尼牛顿法产生的点列存在常数上满足：则在精确线搜索条件下，满足：)(1

当是有限点列时，其最后一个点为的唯一极小点．(2)当是无限点列时，收敛到的唯一极小点．第24页，共72页，编辑于2022年，星期二阻尼牛顿法收敛定理定理3:设二阶连续可微，又设对任意的使得

在存在常数上满足：则在Wolfe不精确线搜索条件下，阻尼牛顿法产生的点列满足：且收敛到的唯一极小点．第25页，共72页，编辑于2022年，星期二例2：用阻尼牛顿法求解：解：显然不是正定的，但：于是，沿方向进行线搜索，得其极小点从而迭代不能继续下去．第26页，共72页，编辑于2022年，星期二带保护的牛顿法算法给出Step1:Step2:若令为奇异的，转Step8，否则，Step3:若Step4:若则转Step8，否则，则转Step9，否则，进行线搜索，求出Step5:沿方向并令第27页，共72页，编辑于2022年，星期二Step6:若停；转Step1；Step7:令Step8:令Step9:令转Step5；转Step5.第28页，共72页，编辑于2022年，星期二例3：用带保护的牛顿法求解：解：显然不是正定的，但：于是，因为，

故令，沿进行线搜索得：第29页，共72页，编辑于2022年，星期二第二次迭代：而：使故令沿进行线搜索，得出于是:此时:第30页，共72页，编辑于2022年，星期二Gill-Murray稳定牛顿法当正定时，总有Cholesky分解：当

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

使得：其中是对角阵．然后解：第31页，共72页，编辑于2022年，星期二问题1:第32页，共72页，编辑于2022年，星期二如何建立有效的算法？从二次模型到一般模型问题2:什么样的算法有效呢？二次终止性§

4.3

共轭方向法第33页，共72页，编辑于2022年，星期二与共轭梯度法算法特点第34页，共72页，编辑于2022年，星期二（１）建立在二次模型上，具有二次终止性．（２）有效的算法，克服了最速下降法的慢收敛性，又避免了牛顿法的计算量大和局部收性的缺点．（３）算法简单，易于编程，需存储空间小等优点，是求解大规模问题的主要方法．共轭方向及其性质定义1:设是中任一组非零向量，如果：则称是关于

共轭的．注：若

则是正交的，因此共轭是正交的推广．第35页，共72页，编辑于2022年，星期二定理1:设为

阶正定阵，

非零向量组关于

共轭，则必线性无关．为关于阶正定阵，非零向量组共轭，则向量构成推论1:设的一组基．推论2:设为

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

共轭，若向量关于

共轭，则第36页，共72页，编辑于2022年，星期二共轭方向法算法Step1:给出计算

Step2:如果Step3:计算和初始下降方向停止迭代．使得Step4:采用某种共轭方向法计算使得：Step5:令转Step2.第37页，共72页，编辑于2022年，星期二共轭方向法基本定理定义2:设维向量组线性无关，向量集合为与生成的维超平面．第38页，共72页，编辑于2022年，星期二引理1:设维向量组是连续可微的严格凸函数，线性无关，则：是在上唯一极小点的充要条件是：第39页，共72页，编辑于2022年，星期二证：构造：是分析：(1)维严格凸函数．(2)是在

上的极小点的充要条件是是在上的极小点．第40页，共72页，编辑于2022年，星期二定理2:

设为

阶正定阵，

向量组关于

共轭，对正定二次函数由任意开始，依次进行次精确线搜索：则：（１）（２）是在

上的极小点．时，为正定二次函数在推论:当上的极小点．第41页，共72页，编辑于2022年，星期二共轭梯度法左乘并使得：（Hestenes-Stiefel公式）取：记：第42页，共72页，编辑于2022年，星期二共轭梯度法基本性质定理3:对于正定二次函数，

采用精确线搜索的共轭梯度法在步后终止，且对成立下列关系式：（共轭性）（正交性）（下降条件）第43页，共72页，编辑于2022年，星期二系数的其他形式（１）FR公式（1964）（2）PRP公式（1969）第44页，共72页，编辑于2022年，星期二FR共轭梯度法算法如果停．Step1:给出Step2:

计算Step3:由精确线搜索求Step4:Step5:第45页，共72页，编辑于2022年，星期二转Step2.例4：用FR共轭梯度法求解：解：化成形式(1)第46页，共72页，编辑于2022年，星期二(2)第47页，共72页，编辑于2022年，星期二第48页，共72页，编辑于2022年，星期二例5：用FR共轭梯度法求解：解：化成形式(1)第49页，共72页，编辑于2022年，星期二(2)第50页，共72页，编辑于2022年，星期二FR共轭梯度法收敛定理定理4:假定在有界水平集上连续可微，且有下界，那么采用精确线搜索下的至少有一个聚点FR共轭梯度法产生的点列是驻点，即：(1)当是有穷点列时，其最后一个点是的驻点．(2)当是无穷点列时，它必有聚点，且任一聚点都是的驻点．第51页，共72页，编辑于2022年，星期二再开始FR共轭梯度法算法Step1:给出如果停，Step4:Step2:计算否则Step3:由精确线搜索求并令：计算若令如果转Step2;停.第52页，共72页，编辑于2022年，星期二Step5:若令转step2.Step6:计算Step7:如果令转step2,第53页，共72页，编辑于2022年，星期二否则转step3.作业：FR共轭梯度法（上机）上机实现FR共轭梯度法．并求解Rosenbrock函数，初始点选线搜索分别采用黄金分割法与强Wolfe线搜索，并对比．第54页，共72页，编辑于2022年，星期二§

4.4

拟牛顿法第55页，共72页，编辑于2022年，星期二基本思想本质上是基于逼近牛顿法的方法．牛顿法每次都计算1959年,Davidon提出第56页，共72页，编辑于2022年，星期二设想仅用每次迭代中得到的梯度信息来近似海色阵，基于此导致了一类非常成功的拟牛顿法．本节介绍Broyden族拟牛顿法：DFP算法和BFGS算法．算法原理最速下降法和阻尼牛顿法的迭代公式可统一为：思考：要使上面的算法比最速下降法快，比牛顿法计算简单，且整体收敛性好，关键在于构造

矩阵列要求：的选取既能逐步逼近又无需计算第57页，共72页，编辑于2022年，星期二二阶导数，且具备以下条件：是对称正定阵．C1：C2：由经简单修正而得：C3：

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

是二次连续可微的，第58页，共72页，编辑于2022年，星期二令：则：（对二次函数为等式）令：

因此：若非奇异：（拟牛顿方程）设想：这样就可很好的近似第59页，共72页，编辑于2022年，星期二拟牛顿算法给出计算精确线搜索求若计算校正停；否则转Step7.使拟牛顿方程成立．Step1:Step2:Step3:Step4:Step5:Step6:Step7:Step8:转Step3.第60页，共72页，编辑于2022年，星期二DFP校正公式是维待定向量．要求：所以：令：得：因此：所以：（DFP校正公式）第61页，共72页，编辑于2022年，星期二例6：用DFP算法求解：取解：(1)第62页，共72页，编辑于2022年，星期二(2)第63页，共72页，编辑于2022年，星期二注:（１）DFP算法具有二次终止性．（２）搜索方向是共轭方向：第64页，共72页，编辑于2022年，星期二DFP校正公式的正定继承性为引理2:设正定阵，且则：为正定阵的充要条件是定理5:在DFP