请问拟牛顿算法中的下降算法是否都是收敛的

当然要满足一定的要求，比如函数 f 要满足一定的光滑性，拟Hessian矩阵 B_k 要满足（一致）正定性（比如BFGS公式）， 迭代过程中的下降条件要充分（比如Wolfe条件之类的），从而保证全局收敛。

正常。

问题解决

利用迭代算法解决问题，需要做好以下三个方面的工作：

一、确定迭代变量

在可以用迭代算法解决的问题中，至少存在一个可直接或间接地不断由旧值递推出新值的变量，这个变量就是迭代变量。

二、建立迭代关系式

所谓迭代关系式，指如何从变量的前一个值推出其下一个值的公式（或关系）。迭代关系式的建立是解决迭代问题的关键，通常可以使用递推或倒推的方法来完成。

三、对迭代过程进行控制

在什么时候结束迭代过程？这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地执行下去。迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。

对于前一种情况，可以构建一个固定次数的循环来实现对迭代过程的控制；对于后一种情况，需要进一步分析得出可用来结束迭代过程的条件。

百度百科-牛顿迭代法

《数学规划》（Mathematical Programming）是一本由黄红选编写的教程，数学规划学科的内容十分丰富，包括许多研究分支。

如：线性规划、非线性规划、多目标规划、动态规划、参数规划、组合最佳化和整数规划、随机规划、模糊规划、非光滑最佳化、多层规划、全局最佳化、变分不等式和互补问题等。广泛套用于各领域，特别是金融领域。

基本介绍 书名 ：数学规划 作者 ：黄红选 ISBN ：9787302121770 定价 ：45元 出版社 ：清华大学出版社 出版时间 ：2006-3-1 英文名 ：Mathematical Programming 图书简介,目录, 图书简介 本书以数学规划为对象, 从理论、算法和计算等方面介绍了分析和求解常见的最最佳化问题的一些方法 全书共分8章, 其中第1章介绍了数学规划的实例、模型以及在分析最最佳化问题时所涉及的基础知识, 第2章至第8章分别讨论了凸分析、线性规划、无约束最佳化、约束最佳化、多目标规划、组合最佳化和整数规划以及全局最佳化等七个方面的内容 此外,书中每章的最后一节给出了一些习题,书末列出了参考文献和索引 本书可作为套用数学、计算数学、运筹学与控制论、管理科学与工程、工业工程、系统工程等专业的研究生和高年级本科生学习数学规划的教材,也可以作为其他需要利用数学规划方法进行建模和求解实际问题的各个学科领域的科研人员、工程技术人员的参考书 目录 第1章 引论1 11 学科简介1 12 实例与模型4 13 预备知识9 131 线性空间9 132 范数12 133 集合与序列14 134 矩阵的分解与校正15 135 函式的可微性与展开17 14 习题20 第2章 凸分析22 21 仿射集22 22 凸集与锥25 23 凸集分离定理27 231 点与凸集分离28 232 凸集与凸集分离31 24 多面体理论32 241 多面体的维数33 242 择一定理34 243 多面体的面和最小不等式表示38 244 多面体的表示定理44 25 凸函式49 251 基本性质49 252 函式凸性的判定方法52 26 习题54 第3章 线性规划57 31 线性规划的基本定理57 311 基本定理与标准形式58 312 极点的代数特征61 32 单纯形算法64 321 基本原理64 322 算法步骤与单纯形表67 323 启动机制70 33 线性规划的最优性条件77 34 对偶理论79 341 对偶定理79 342 对偶单纯形法84 35 单纯形算法的改进与推广88 351 修正单纯形法88 352 原始-对偶算法91 353 退化与循环94 354 Dantzig-Wolfe分解算法99 355 灵敏度分析104 36 线性规划内点算法108 361 算法复杂性概念108 362 单纯形算法的复杂性111 363 Karmarkar投影尺度算法114 364 原始-对偶尺度算法124 365 原始-对偶路径跟踪算法130 366 内点算法的其他策略137 37 习题144 第4章 无约束最佳化150 41 无约束最佳化的最优性条件150 42 算法收敛性152 421 一维搜寻与收敛性152 422 算法映射与收敛性162 423 收敛速度与算法停止规则166 43 牛顿法170 431 叠代格式170 432 局部收敛性172 433 修正牛顿法174 434 非精确的牛顿法177 44 共轭方向与线性共轭梯度法179 441 共轭方向与扩张子空间定理179 442 线性共轭梯度法与二次终止性181 45 非线性共轭梯度法186 451 FR 共轭梯度法187 452 PRP共轭梯度法192 46 拟牛顿方法196 461 拟牛顿条件和算法步骤196 462 对称秩1校正公式197 463 对称秩2校正公式200 464 Broyden族208 47 习题213 第5章 约束最佳化220 51 一阶最优性条件与约束规格220 511 一阶必要条件220 512 约束规格226 513 一阶充分条件228 52 二阶最优性条件230 521 二阶必要条件231 522 二阶充分条件233 53 对偶理论235 531 对偶形式235 532 对偶定理237 533 鞍点定理240 54 二次规划242 541 基本性质244 542 等式约束的二次规划248 543 凸二次规划的积极约束集方法254 544 线性互补问题260 55 可行方向法265 551 Zoutendijk可行方向法266 552 Rosen梯度投影法268 553 Wolfe既约梯度法270 554 Frank-Wolfe线性化方法272 56 序列无约束化方法273 561 二次罚函式法275 562 对数障碍函式法280 563 乘子法284 57 逐次二次规划法289 571 Newton-Lagrange方法289 572 逐次二次规划的算法模型291 573 二次规划子问题的Hesse矩阵297 574 价值函式与搜寻方向的下降性299 58 信赖域法305 581 信赖域法的基本原理305 582 子问题的精确求解法308 583 子问题的近似求解法313 584 信赖域法的全局收敛性318 59 习题319 第6章 多目标规划325 61 引言325 62 向量集的有效点与弱有效点327 621 几何特征328 622 代数特征330 63 多目标规划的解及其性质333 631 Pareto最优解333 632 KT-有效解与G-有效解335 633 最优性条件338 64 多目标规划的解法338 641 基于一个单目标问题的方法339 642 基于多个单目标问题的方法343 65 习题345 第7章 组合最佳化与整数规划347 71 网路流问题与算法348 711 图论中的基本概念348 712 最短路问题350 713 最大流与最小割问题352 714 最小费用网路流问题355 715 最大森林问题356 72 匹配问题与算法357 721 匹配与最大基数匹配357 722 二部图匹配359 73 整数规划的基本性质362 731 整数规划的模型363 732 整数规划的性质366 74 割平面法371 741 Gomory割平面法371 742 构造有效不等式的方法379 75 分支定界法381 751 分支定界的基本原理381 752 分支定界的算法步骤383 76 分解算法388 761 基于Lagrange松弛的分解算法388 762 Benders分解算法392 77 习题397 第8章 全局最佳化401 81 全局最佳化的基本概念与性质401 811 凸集的性质401 812 函式的连续性与凹凸性403 813 凸包络405 814 Lipschitz函式409 815 D C 函式411 82 常见的全局最佳化模型413 821 二次规划413 822 凹极小化417 823 D C 规划419 824 Lipschitz最佳化425 83 外逼近与割平面算法426 831 外逼近的基本原理427 832 割平面算法429 833 求解松弛问题的方法431 84 凹性割方法433 841 有效割与凹性割434 842 凹性割方法的收敛性437 843 反向凸约束的凹性割439 85 分支定界法441 851 基本算法442 852 多面体剖分444 853 定下界方法446 854 有限性和收敛性447 86 习题449 参考文献452 索引455

学习和工作中遇到的大多问题都可以建模成一种最优化模型进行求解，比如我们现在学习的机器学习算法，大部分的机器学习算法的本质都是建立优化模型，通过最优化方法对目标函数（或损失函数）进行优化，从而训练出最好的模型。常见的优化方法(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个样本全部带入计算，迭代一次计算量为mn2。

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国家实验室的物理学家WCDavidon所提出来。Davidon设计的这种算法在当时看来是非线性优化领域最具创造性的发明之一。不久R Fletcher和M J D Powell证实了这种新的算法远比其他方法快速和可靠，使得非线性优化这门学科在一夜之间突飞猛进。

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

具体步骤：

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

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

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

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

从而得到

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

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

以上就是关于请问拟牛顿算法中的下降算法是否都是收敛的全部的内容，包括:请问拟牛顿算法中的下降算法是否都是收敛的、牛顿迭代法看不懂正常吗、数学规划详细资料大全等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！