简述dfp算法的算法步骤

1. 梯度下降法与牛顿法

梯度下降和牛顿法的推导均与泰勒公式有关，所以先介绍泰勒展开公式：
基本形式：

上面这个迭代形式将应用到下面的梯度下降和牛顿法中。

梯度下降法应用一阶泰勒展开，假设 L (θ)代表损失函数，目标：最小化损失函数，θ是需要更新的模型参数。下面公式中alpha是步长(学习率)，可以直接赋值一个小的数，也可以通过line search。

牛顿法应用二阶泰勒展开，目标：最小化损失函数

g定义为雅克比矩阵，矩阵中各元素对应一阶偏导数
Hessian矩阵中各元素对应二阶偏导数。Hessian矩阵的逆同比于梯度下降法的学习率参数alpha，Hessian的逆在迭代中不断减小，起到逐渐缩小步长的效果。

1.梯度下降法： 通过梯度方向和步长，直接求解目标函数最小值时的参数。
越接近最优值时，步长应该不断减小，否则会在最优值附近来回震荡。
2.牛顿法：
优点：通过求解目标函数的一阶导数为0时的参数，进而求出目标函数最小值时的参数。收敛速度很快。海森矩阵的逆在迭代过程中不断减小，可以起到逐步减小步长的效果。
缺点：海森矩阵的逆计算复杂，代价比较大，因此有了拟牛顿法。

解决牛顿法计算比较复杂的问题，使用正定矩阵近似Hessian矩阵的逆，简化了运算的复杂度。
常用的拟牛顿算法：DFP算法和BFGS算法

2. 非线性规划的深入解析

例1（投资决策问题）某企业有n个项目可供选择投资，并且至少要对其中一个项目投资。已知该企业拥有总资金A元，投资于第i个项目需花资金ai元，并预计可收益bi元。试选择最佳投资方案。
解:设投资决策变量为

则投资总额为∑aixi，投资总收益为∑bixi。因为该公司至少要对一个项目投资，并且总的投资金额不能超过总资金 ，故有限制条件

另外，由于 xi只取值0或1，所以还有

最佳投资方案应是投资额最小而总收益最大的方案，所以这个最佳投资决策问题归结为总资金以及决策变量（取0或1）的限制条件下，极大化总收益和总投资之比。因此，其数学模型为：
上面例题是在一组等式或不等式的约束下，求一个函数的最大值（或最小值）问题，其中目标函数或约束条件中至少有一个非线性函数，这类问题称之为非线性规划问题，简记为（NP）。可概括为一般形式

（NP)
其中x=[x1 ... xn]称为模型（NP）的决策变量，f称为目标函数，gi和hj 称为约束函数。另外，gi(x)=0称为等式约束，hj(x)<=0称为不等式约束。 对于一个实际问题，在把它归结成非线性规划问题时，一般要注意如下几点：
（i）确定供选方案：首先要收集同问题有关的资料和数据，在全面熟悉问题的基础上，确认什么是问题的可供选择的方案，并用一组变量来表示它们。
（ii）提出追求目标：经过资料分析，根据实际需要和可能，提出要追求极小化或极大化的目标。并且，运用各种科学和技术原理，把它表示成数学关系式。
（iii）给出价值标准：在提出要追求的目标之后，要确立所考虑目标的“好”或“坏”的价值标准，并用某种数量形式来描述它。
（iv）寻求限制条件：由于所追求的目标一般都要在一定的条件下取得极小化或极大化效果，因此还需要寻找出问题的所有限制条件，这些条件通常用变量之间的一些不等式或等式来表示。 对实际规划问题作定量分析，必须建立数学模型。建立数学模型首先要选定适当的目标变量和决策变量，并建立起目标变量与决策变量之间的函数关系，称之为目标函数。然后将各种限制条件加以抽象，得出决策变量应满足的一些等式或不等式，称之为约束条件。非线性规划问题的一般数学模型可表述为求未知量x1，x2，…，xn，使满足约束条件：
gi(x1，…，xn）≥0i=1，…，m
hj(x1，…，xn)=0j=1，…，p
并使目标函数f(x1，…，xn）达到最小值（或最大值）。其中f，诸gi和诸hj都是定义在n维向量空间Rn的某子集D（定义域）上的实值函数，且至少有一个是非线性函数。
上述模型可简记为：
min f(x)
s.t. gi(x）≥0i=1，…，m
hj(x)=0 j=1，…，p
其中x=(x1，…，xn）属于定义域D，符号min表示“求最小值”，符号s.t.表示“受约束于”。
定义域D 中满足约束条件的点称为问题的可行解。全体可行解所成的集合称为问题的可行集。对于一个可行解x*，如果存在x*的一个邻域，使目标函数在x*处的值f(x*）优于 （指不大于或不小于）该邻域中任何其他可行解处的函数值，则称x*为问题的局部最优解（简称局部解）。如果f(x*）优于一切可行解处的目标函数值，则称x*为问题的整体最优解（简称整体解）。实用非线性规划问题要求整体解，而现有解法大多只是求出局部解。 指寻求一元函数在某区间上的最优值点的方法。这类方法不仅有实用价值，而且大量多维最优化方法都依赖于一系列的一维最优化。常用的一维最优化方法有黄金分割法、切线法和插值法。
①黄金分割法又称0.618法。它适用于单峰函数。其基本思想是：在初始寻查区间中设计一列点，通过逐次比较其函数值，逐步缩小寻查区间，以得出近似最优值点。
②切线法又称牛顿法。它也是针对单峰函数的。其基本思想是：在一个猜测点附近将目标函数的导函数线性化，用此线性函数的零点作为新的猜测点，逐步迭代去逼近最优点。
③插值法又称多项式逼近法。其基本思想是用多项式（通常用二次或三次多项式）去拟合目标函数。
此外，还有斐波那契法、割线法、有理插值法、分批搜索法等。 指寻求 n元实函数f在整个n维向量空间Rn上的最优值点的方法。这类方法的意义在于：虽然实用规划问题大多是有约束的，但许多约束最优化方法可将有约束问题转化为若干无约束问题来求解。
无约束最优化方法大多是逐次一维搜索的迭代算法。这类迭代算法可分为两类。一类需要用目标函数的导函数，称为解析法。另一类不涉及导数，只用到函数值，称为直接法。这些迭代算法的基本思想是：在一个近似点处选定一个有利搜索方向，沿这个方向进行一维寻查，得出新的近似点。然后对新点施行同样手续，如此反复迭代，直到满足预定的精度要求为止。根据搜索方向的取法不同，可以有各种算法。属于解析型的算法有：①梯度法：又称最速下降法。这是早期的解析法，收敛速度较慢。②牛顿法：收敛速度快，但不稳定，计算也较困难。③共轭梯度法：收敛较快，效果较好。④变尺度法：这是一类效率较高的方法。其中达维登-弗莱彻-鲍威尔变尺度法，简称 DFP法，是最常用的方法。属于直接型的算法有交替方向法（又称坐标轮换法）、模式搜索法、旋转方向法、鲍威尔共轭方向法和单纯形加速法等。 这是一类特殊的非线性规划。在前述非线性规划数学模型中，若f是凸函数，诸gi都是凹函数，诸hj都是一次函数，则称之为凸规划。所谓f是凸函数，是指f有如下性质：它的定义域是凸集，且对于定义域中任意两点x和y及任一小于1的正数α，下式都成立：
f(（1-α）x +αy）α≤（1-α）f(x)+αf(y)
将上述不等式中的不等号反向即得凹函数的定义。所谓凸集，是指具有如下性质的集合：连结集合中任意两点的直线段上的点全部属于该集合。
对于一般的非线性规划问题，局部解不一定是整体解。但凸规划的局部解必为整体解，而且凸规划的可行集和最优解集都是凸集。 几何规划一类特殊的非线性规划。它的目标函数和约束函数都是正定多项式（或称正项式）。几何规划本身一般不是凸规划，但经适当变量替换，即可变为凸规划。几何规划的局部最优解必为整体最优解。求解几何规划的方法有两类。一类是通过对偶规划去求解；另一类是直接求解原规划，这类算法大多建立在根据几何不等式将多项式转化为单项式的思想上。

3. 几种常用最优化方法

学习和工作中遇到的大多问题都可以建模成一种最优化模型进行求解，比如我们现在学习的机器学习算法，大部分的机器学习算法的本质都是建立优化模型，通过最优化方法对目标函数（或损失函数）进行优化，从而训练出最好的模型。常见的优化方法(optimization)有梯度下降法、牛顿法和拟牛顿法、共轭梯度法等等。

1. 梯度下降法（Gradient Descent）

梯度下降法是最早最简单，也是最为常用的最优化方法。梯度下降法实现简单，当目标函数是凸函数时，梯度下降法的解是全局解。一般情况下，其解不保证是全局最优解，梯度下降法的速度也未必是最快的。 梯度下降法的优化思想是用当前位置负梯度方向作为搜索方向，因为该方向为当前位置的最快下降方向，所以也被称为是”最速下降法“。最速下降法越接近目标值，步长越小，前进越慢。

梯度下降 法的缺点：

（1）靠近极小值时收敛速度减慢;

（2）直线搜索时可能会产生一些问题；

（3）可能会“之字形”地下降。

在机器学习中，基于基本的梯度下降法发展了两种梯度下降方法，分别为随机梯度下降法和批量梯度下降法。

比如对一个线性回归（Linear Logistics）模型，假设下面的h(x)是要拟合的函数，J( )为损失函数， 是参数，要迭代求解的值，求解出来了那最终要拟合的函数h( )就出来了。其中m是训练集的样本个数，n是特征的个数。

1）批量梯度下降法（Batch Gradient Descent，BGD）

（1）将J( )对 求偏导，得到每个theta对应的的梯度：

(2）由于是要最小化风险函数，所以按每个参数 的梯度负方向，来更新每个 ：

        （3）从上面公式可以注意到，它得到的是一个全局最优解，但是每迭代一步，都要用到训练集所有的数据，如果m很大，那么可想而知这种方法的迭代速度会相当的慢。所以，这就引入了另外一种方法——随机梯度下降。

对于批量梯度下降法，样本个数m，x为n维向量，一次迭代需要把m个样本全部带入计算，迭代一次计算量为m*n2。

2）随机梯度下降（Stochastic Gradient Descent，SGD）

        （1）上面的风险函数可以写成如下这种形式，损失函数对应的是训练集中每个样本的粒度，而上面批量梯度下降对应的是所有的训练样本：

（2）每个样本的损失函数，对 求偏导得到对应梯度，来更新 ：

（3）随机梯度下降是通过每个样本来迭代更新一次，如果样本量很大的情况（例如几十万），那么可能只用其中几万条或者几千条的样本，就已经将

迭代到最优解了，对比上面的批量梯度下降，迭代一次需要用到十几万训练样本，一次迭代不可能最优，如果迭代10次的话就需要遍历训练样本10次。但是，SGD伴随的一个问题是噪音较BGD要多，使得SGD并不是每次迭代都向着整体最优化方向。

随机梯度下降每次迭代只使用一个样本，迭代一次计算量为n2，当样本个数m很大的时候，随机梯度下降迭代一次的速度要远高于批量梯度下降方法。 两者的关系可以这样理解：随机梯度下降方法以损失很小的一部分精确度和增加一定数量的迭代次数为代价，换取了总体的优化效率的提升。增加的迭代次数远远小于样本的数量。

对批量梯度下降法和随机梯度下降法的总结：

批量梯度下降---最小化所有训练样本的损失函数，使得最终求解的是全局的最优解，即求解的参数是使得风险函数最小，但是对于大规模样本问题效率低下。

随机梯度下降---最小化每条样本的损失函数，虽然不是每次迭代得到的损失函数都向着全局最优方向， 但是大的整体的方向是向全局最优解的，最终的结果往往是在全局最优解附近，适用于大规模训练样本情况。

2. 牛顿法和拟牛顿法（Newton's method & Quasi-Newton Methods）

1）牛顿法（Newton's method）

牛顿法是一种在实数域和复数域上近似求解方程的方法。方法使用函数 f  ( x )的泰勒级数的前面几项来寻找方程 f  ( x ) = 0的根。牛顿法最大的特点就在于它的收敛速度很快。

具体步骤：

首先，选择一个接近函数 f  ( x )零点的x0，计算相应的 f  ( x 0)和切线斜率 f  '  ( x 0)（这里 f '  表示函数 f   的导数）。然后我们计算穿过点( x 0, f   ( x 0))并且斜率为 f  '( x 0)的直线和 x  轴的交点的 x 坐标，也就是求如下方程的解：

我们将新求得的点的 x  坐标命名为 x 1，通常 x 1会比 x 0更接近方程 f   ( x ) = 0的解。因此我们现在可以利用 x 1开始下一轮迭代。迭代公式可化简为如下所示：

已经证明，如果 f   '是连续的，并且待求的零点 x 是孤立的，那么在零点 x 周围存在一个区域，只要初始值 x 0位于这个邻近区域内，那么牛顿法必定收敛。 并且，如果 f   ' ( x )不为0, 那么牛顿法将具有平方收敛的性能. 粗略的说，这意味着每迭代一次，牛顿法结果的有效数字将增加一倍。下图为一个牛顿法执行过程的例子。

由于牛顿法是基于当前位置的切线来确定下一次的位置，所以牛顿法又被很形象地称为是"切线法"。

关于牛顿法和梯度下降法的效率对比：

从本质上去看，牛顿法是二阶收敛，梯度下降是一阶收敛，所以牛顿法就更快。如果更通俗地说的话，比如你想找一条最短的路径走到一个盆地的最底部，梯度下降法每次只从你当前所处位置选一个坡度最大的方向走一步，牛顿法在选择方向时，不仅会考虑坡度是否够大，还会考虑你走了一步之后，坡度是否会变得更大。所以，可以说牛顿法比梯度下降法看得更远一点，能更快地走到最底部。（牛顿法目光更加长远，所以少走弯路；相对而言，梯度下降法只考虑了局部的最优，没有全局思想。）

根据wiki上的解释，从几何上说，牛顿法就是用一个二次曲面去拟合你当前所处位置的局部曲面，而梯度下降法是用一个平面去拟合当前的局部曲面，通常情况下，二次曲面的拟合会比平面更好，所以牛顿法选择的下降路径会更符合真实的最优下降路径。

注：红色的牛顿法的迭代路径，绿色的是梯度下降法的迭代路径。

牛顿法的优缺点总结：

优点：二阶收敛，收敛速度快；

缺点：牛顿法是一种迭代算法，每一步都需要求解目标函数的Hessian矩阵的逆矩阵，计算比较复杂。

2）拟牛顿法（Quasi-Newton Methods）

拟牛顿法是求解非线性优化问题最有效的方法之一，于20世纪50年代由美国Argonne国家实验室的物理学家W.C.Davidon所提出来。Davidon设计的这种算法在当时看来是非线性优化领域最具创造性的发明之一。不久R. Fletcher和M. J. D. Powell证实了这种新的算法远比其他方法快速和可靠，使得非线性优化这门学科在一夜之间突飞猛进。

拟牛顿法的本质思想是改善牛顿法每次需要求解复杂的Hessian矩阵的逆矩阵的缺陷，它使用正定矩阵来近似Hessian矩阵的逆，从而简化了运算的复杂度。 拟牛顿法和最速下降法一样只要求每一步迭代时知道目标函数的梯度。通过测量梯度的变化，构造一个目标函数的模型使之足以产生超线性收敛性。这类方法大大优于最速下降法，尤其对于困难的问题。另外，因为拟牛顿法不需要二阶导数的信息，所以有时比牛顿法更为有效。如今，优化软件中包含了大量的拟牛顿算法用来解决无约束，约束，和大规模的优化问题。

具体步骤：

拟牛顿法的基本思想如下。首先构造目标函数在当前迭代xk的二次模型：

这里Bk是一个对称正定矩阵，于是我们取这个二次模型的最优解作为搜索方向，并且得到新的迭代点：

其中我们要求步长ak 满足Wolfe条件。这样的迭代与牛顿法类似，区别就在于用近似的Hesse矩阵Bk 代替真实的Hesse矩阵。所以拟牛顿法最关键的地方就是每一步迭代中矩阵Bk的更新。现在假设得到一个新的迭代xk+1，并得到一个新的二次模型：

我们尽可能地利用上一步的信息来选取Bk。具体地，我们要求

从而得到

这个公式被称为割线方程。常用的拟牛顿法有DFP算法和BFGS算法。

原文链接： [Math] 常见的几种最优化方法 - Poll的笔记 - 博客园