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

最优化理论与方法Chapter5拟牛顿法

牛顿太伟大了，我们只能模拟他5.1拟牛顿法及其性质5.2BFGS算法及其Matlab实现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做了报告。机器学习算法中经常碰到非线性优化问题，如SparseFiltering算法，其主要工作在于求解一个非线性极小化问题。在具体实现中，大多调用的是成熟的软件包做支撑，其中最常用的一个算法是L-BFGS。拟牛顿法(Quasi-NewtonMethods)是求解非线性优化问题最有效的方法之一，于20世纪50年代由美国Argonne国家实验室的物理学家W.C.Davidon所提出来。Davidon设计的这种算法在当时看来是非线性优化领域最具创造性的发明之一。不久R.Fletcher和M.J.D.Powell证实了这种新的算法远比其他方法快速和可靠，使得非线性优化这门学科在一夜之间突飞猛进。在之后的20年里，拟牛顿方法得到了蓬勃发展，出现了大量的变形公式以及数以百计的相关论文。中国也有一些学者在这方面做出很好的结果。方法总结:基本思想:牛顿法收敛很快，但需要计算Hesse矩阵，而此矩阵可能非正定，可能导致搜索方向不是下降方向。

拟牛顿法就是利用目标函数值f和一阶导数g的信息,构造出目标函数的曲率近似，而不需要明显形成Hesse矩阵，同时具有收敛速度快的优点。拟牛顿法具有超线性收敛速度。

用不包含二阶导数的矩阵近似Hesse矩阵的逆。同共轭梯度法相比，拟牛顿法不需要重新开始策略。保优去劣5.1拟牛顿法及其性质

Quasi-NewtonMethodandItsProperties牛顿法的迭代公式为5.1拟牛顿法及其性质5.1拟牛顿法及其性质记则5.1拟牛顿法及其性质(A1)称为拟牛顿条件(方程)，也称为割线方程。怎样确定满足这个条件的H

k+1?校正矩阵欠定方程自由度？5.1拟牛顿法及其性质如何逼近Hesse矩阵或其逆矩阵？？？对称秩1校正5.1拟牛顿法及其性质

Hk称为校正矩阵.

确定

Hk的一个方法是令秩为1r(AB)≤min{r(A),r(B)}从而(A2)利用上面的式子，得---秩1校正公式5.1拟牛顿法及其性质得新信息的嵌入原先信息的继承可直接验证拟牛顿条件

Bk称为校正矩阵。确定

Bk的一个方法是令5.1拟牛顿法及其性质5.1拟牛顿法及其性质利用秩1校正极小化函数f(x),在第k次迭代中,令搜索方向5.1拟牛顿法及其性质确定后继点算法

对称秩1算法5.1拟牛顿法及其性质其它更好的近似5.1拟牛顿法及其性质5.1拟牛顿法及其性质5.1拟牛顿法及其性质5.1拟牛顿法及其性质5.1拟牛顿法及其性质5.1拟牛顿法及其性质5.1拟牛顿法及其性质5.1拟牛顿法及其性质点评在一定条件下，对称秩1校正算法收敛且具有二次终止性。无法保证Hk和Bk的正定性。具体而言，有以下三种情况：5.1拟牛顿法及其性质5.1拟牛顿法及其性质5.1拟牛顿法及其性质5.2BFGS算法及其Matlab实现

BFHSMethodandItsMatlabCode

BFGS校正是目前最流行也是最有效的拟牛顿校正,它是由Broyden,Fletcher,Goldfarb和Shanno在1970年各自独立提出的拟牛顿法,故称为BFGS算法。5.2BFGS算法及其Matlab实现考虑拟牛顿条件对称形式其对称形式其中Bk+1为Hesse矩阵的近似。下面用迭代法求Bk+1使其满足(A2)。记取△Bk为秩2校正矩阵，即5.2BFGS算法及其Matlab实现于是由拟牛顿方程(A2)得即满足上式的uk和vk不唯一。下面令uk和vk分别平行于Bksk和yk,

即令uk=γBksk,vk=θyk,其中γ和θ为待定参数。r(A+B)≤r(A)+r(B)秩为2于是有5.2BFGS算法及其Matlab实现将uk和vk代入(A4)得整理得令上式显然成立。从而得到BFGS秩2校正公式如下5.2BFGS算法及其Matlab实现显然，若Bk对称，则校正后的Bk+1也对称。同时可以证明BFGS校正公式有如下性质。曲率条件5.2BFGS算法及其Matlab实现5.2BFGS算法及其Matlab实现容易实现吗？？？容易，比如严格凸5.2BFGS算法及其Matlab实现5.2BFGS算法及其Matlab实现5.2BFGS算法及其Matlab实现要求线性方程组5.2BFGS算法及其Matlab实现基于Armijo搜索的BFGS算法的Matlab程序。5.2BFGS算法及其Matlab实现5.2BFGS算法及其Matlab实现对利用一次该定理，得5.2BFGS算法及其Matlab实现记则那么5.2BFGS算法及其Matlab实现于是对于线性方程组我们没有必要解它，而只需要根据H0,x0,x1,g0,g1,求出s0,y0,进而根据上面的迭代公式求出H1,进而的求出d1,然后一步一步的进行即可。5.3DFP算法及其Matlab实现

DPFMethodandItsMatlabCode

DFP校正是第一个拟牛顿校正,是1959年由Davidon提出的,后经Fletcher和Powell解释和改进,故名之为DFP算法,它也是求解无约束优化问题最有效的算法之一。5.3DFP算法及其Matlab实现考虑拟牛顿条件对称形式类似于BFGS校正公式的推导,可得DFP校正公式。定义校正矩阵秩为25.3DFP算法及其Matlab实现DFP(Davidon-Fletcher-Power)公式则BFGS公式DFP公式BFGS修正公式5.3DFP算法及其Matlab实现上一节，我们推导的BFGS校正公式的逆矩阵的迭代公式经验表明BFGS公式比DFP公式好。5.3DFP算法及其Matlab实现5.3DFP算法及其Matlab实现5.3DFP算法及其Matlab实现5.3DFP算法及其Matlab实现5.3DFP算法及其Matlab实现例5.1

用DFP方法求解下列问题初始点及初始矩阵分别取为5.3DFP算法及其Matlab实现第1次迭代令搜索方向得到5.3DFP算法及其Matlab实现令5.3DFP算法及其Matlab实现第2次迭代5.3DFP算法及其Matlab实现5.3DFP算法及其Matlab实现令5.3DFP算法及其Matlab实现得到于是5.3DFP算法及其Matlab实现得最优解DFP法具有二次终止性！5.3DFP算法及其Matlab实现5.3DFP算法及其Matlab实现5.3DFP算法及其Matlab实现拟牛顿法有关说明拟牛顿法中的两个重要算法DFP算法和BFGS算法，它们的迭代过程相同，区别仅在于校正矩阵选取不同。对于DFP法，由于一维搜索的不精确和计算误差的积累可能导致某一轮的奇异，而BFGS法对一维搜索的精度要求不高，并且由它产生的不易变为奇异矩阵。BFGS法比DFP法更具有好的数值稳定性，它比DFP法更具有实用性。5.3DFP算法及其Matlab实现5.4Broyden族算法及其Matlab实现

BroydenMethodandItsMatlabCode

前面讨论了两种秩2校正公式：BFGS校正与DFP校正，总结如下。5.4Broyden族算法及其Matlab实现定义------Broyden族5.4Broyden族算法及其Matlab实现Broyden族的所有成员均满足拟牛顿条件。5.4Broyden族算法及其Matlab实现显然成立证明：对k归纳。当k=1时有5.4Broyden族算法及其Matlab实现并且有于是当k=1时结论成立。5.4Broyden族算法及其Matlab实现下设k=l时命题成立,下证当k=l+1时结论也成立。由归纳假设有5.4Broyden族算法及其Matlab实现5.4Broyden族算法及其Matlab实现特点：不必计算Hesse矩阵；存储量较大；当Hk正定时，算法产生的方向均为下降方向，具有二次终止性；拟牛顿法是无约束最优化方法中最有效的一类算法。5.4Broyden族算法及其Matlab实现5.5拟牛顿法的收敛性

ConvergenceofQuasi-NewtonMethod

本节讨论拟牛顿法的收敛性,主要给出基于非精确线搜索的BFGS算法的全局收敛性和局部超线性收敛性定理。5.5拟牛顿法的收敛性5.5拟牛顿法的收敛性5.5拟牛顿法的收敛性5.5拟牛顿法的收敛性5.5拟牛顿法的收敛性5.5拟牛顿法的收敛性5.5拟牛顿法的收敛性5.5拟牛顿法的收敛性5.5拟牛顿法的收敛性5.5拟牛顿法的收敛性5.5拟牛顿法的收敛性5.5拟牛顿法的收敛性5.5拟牛顿法的收敛性5.5拟牛顿法的收敛性总结对称秩1校正(两项)总结对称秩2校正(三项)x(k+1)=x(k)+αkd(k)多变量最优化迭代解法的一般迭代公式最优(非精确)步长可用一维搜索技术解决不同的搜索方向d(k)构成不同的算法算法名称搜索方向p(k)Powell共轭方向法共轭方向最速下降法d(k)=－f(x(k)

)Newton法d(k)=

－

2f(x(k))－1

f(x(k))Marquart法d(k)

＝－[2f(x(k))

+

kI]－1

f(x(k))F-R法(共轭梯度法)d(0)=－

f(x(0)