AAA最优化理论与方法课件(第5章-马昌凤版).ppt

最优化理论与方法

模拟

Chapter5拟牛顿法

牛顿太伟大了，我们只能模拟他

5.1拟牛顿法及其性质

算法及其实现

5.2BFGSMatlab模拟了哪部分？

5.3DFP算法及其Matlab实现模拟的就是牛顿

5.4Broyden族算法及其Matlab实现法中的搜索方向

5.5拟牛顿法的收敛性（可以叫作“牛

顿方向”）的生

成方式。

在著名数学家斯米尔给出的本世纪18个数学难题中，其

中以下4个就与运筹学相关：

（1）“P是否等于NP”，也被列为本世纪的7个数学难

题之一；

（2）单变量多项式整解的个数；

（3）可描述价格调整的一般均衡理论的数学模型；

（4）实系数线性规划是否多项式时间可解。

以下12个问题是运筹学相关方向具有一定代表性的未解难

题：

（1）凸多面体的d-步猜想；

（2）有限多个二次函数最大值的极小化问题；

（3）推广的Lax猜想；

（4）DFP拟牛顿法的收敛性；(OpenProblem)

（5）最小阻力凸体问题；

（6）是否存在求解性线性规划的强多项式时间算法？

（7）组合优化反问题的计算复杂性；

（8）求解旅行商问题的更好的近似算法；

（9）k-服务器猜想；

（10）装箱问题是否存在绝对近似算法；

（11）随机排队网络的遍历性；

（12）PH-分布的最小表示。

其中凸多面体的d-步猜想--Hirschconjecture已经被解决了。

该数学家找到了一个反例并证否了该猜想，发在了当年的

AnnalsofMathematics上，并且被邀请到了ICM做了报告。

机器学习算法中经常碰到非线性优化问题，如Sparse

Filtering算法，其主要工作在于求解一个非线性极小

化问题。在具体实现中，大多调用的是成熟的软件包

做支撑，其中最常用的一个算法是L-BFGS。

拟牛顿法(Quasi-NewtonMethods)是求解非线性优化

问题最有效的方法之一，于20世纪50年代由美国

Argonne国家实验室的物理学家W.C.Davidon所提出

来。Davidon设计的这种算法在当时看来是非线性优

化领域最具创造性的发明之一。不久R.Fletcher和M.J.

D.Powell证实了这种新的算法远比其他方法快速和可

靠，使得非线性优化这门学科在一夜之间突飞猛进。

在之后的20年里，拟牛顿方法得到了蓬勃发展，出现

了大量的变形公式以及数以百计的相关论文。中国也

有一些学者在这方面做出很好的结果。

方法总结:

xk+1xkkHk(gk)





收敛极慢(线性)

一维搜索步长最速下降

HkI,k

全局收敛(非凸)



收敛极快(二阶)

牛顿法

HkGk,k=1

局部收敛(严格凸)

HG,一维搜索步长阻尼/修正牛顿法

kkk

收敛较快



全局收敛(一致凸/严格凸)

基本思想:

牛顿法收敛很快，但需要计算Hesse矩阵，而此矩

阵可能非正定，可能导致搜索方向不是下降方向。

拟牛顿法就是利用目标函数值f和一阶导数保g优的去信劣息,

构造出目标函数的曲率近似，而不需要明显形成

Hesse矩阵，同时具有收敛速度快的优点。

拟牛顿法具有超线性收敛速度。

用不包含二阶导数的矩阵近似Hesse矩阵的逆。

同共轭梯度法相比，拟牛顿法不需要重新开始策略。

5.1拟牛顿法及其性质

Quasi-Newto