精华内容
下载资源
问答
  • 二阶收敛性
    千次阅读 多人点赞
    2019-06-22 16:04:47

    查了很多地方说牛顿法是二阶算法,一直没找到二阶项在哪。花了大半天的时间才弄明白。记录一下。
    牛顿法一般应用场景:

    1. 求方程的根;
    2. 求解最优化方法;

    比如要求 f ( x ) = 0 f(x)=0 f(x)=0的根。
    首先,选择一个接近函数 f ( x ) f(x) f(x)零点的 x 0 x_0 x0,计算相应的 f ( x 0 ) f(x_0) f(x0)和切线斜率 f ′ ( x 0 ) f ' (x_0) f(x0)(这里 f ′ f ' f表示函数 f f f的导数)。然后我们计算穿过点 ( x 0 , f ( x 0 ) ) (x_0, f (x_0)) (x0,f(x0))并且斜率为 f ′ ( x 0 ) f '(x0) f(x0)的直线和 x x x 轴的交点的 x x x坐标,也就是求如下方程的解:
    f ( x 1 ) − f ( x 0 ) = f ′ ( x 0 ) ⋅ ( x 1 − x 0 ) f(x_1)-f(x_0) = f^{\prime}\left(x_{0}\right) \cdot (x_1-x_0) f(x1)f(x0)=f(x0)(x1x0)
    通常x1会比x0更接近方程f (x) = 0的解。因此我们现在可以利用x1开始下一轮迭代。迭代公式可化简为如下所示:
    x n + 1 = x n − f ( x n ) f ′ ( x n ) x_{n+1}=x_{n}-\frac{f\left(x_{n}\right)}{f^{\prime}\left(x_{n}\right)} xn+1=xnf(xn)f(xn)
    已经证明,如果f ’ 是连续的,并且待求的零点x是孤立的,那么在零点x周围存在一个区域,只要初始值x0位于这个邻近区域内,那么牛顿法必定收敛。 并且,如果f ’ (x)不为0, 那么牛顿法将具有平方收敛的性能. 粗略的说,这意味着每迭代一次,牛顿法结果的有效数字将增加一倍。下图为一个牛顿法执行过程的例子。

    由于牛顿法是基于当前位置的切线来确定下一次的位置,所以牛顿法又被很形象地称为是"切线法"。牛顿法的搜索路径(二维情况)如下图所示:

    牛顿法搜索动态示例图:
     牛顿法搜索示意图关于牛顿法和梯度下降法的效率对比:

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

    根据wiki上的解释,从几何上说,牛顿法就是用一个二次曲面去拟合你当前所处位置的局部曲面,而梯度下降法是用一个平面去拟合当前的局部曲面,通常情况下,二次曲面的拟合会比平面更好,所以牛顿法选择的下降路径会更符合真实的最优下降路径。
      在这里插入图片描述
      注:红色的牛顿法的迭代路径,绿色的是梯度下降法的迭代路径。

    牛顿法的优缺点总结:
      优点:二阶收敛,收敛速度快;
      缺点:牛顿法是一种迭代算法,每一步都需要求解目标函数的Hessian矩阵的逆矩阵,计算比较复杂。


    当我们将牛顿法用作优化算法的时候,它就是二阶的。
    假设我们有一个凸优化问题
    min ⁡ x f ( x ) \min _{x} f(x) xminf(x)
    也就是说我们要找一个x来最小化f(x)。对于凸优化问题,f(x)的最小值点就是f(x)的极值点,也就是导数为0的点。那么我们上面的优化问题就转换为了如下的求根问题:
    f ′ ( x ) = 0 f^{\prime}(x)=0 f(x)=0
    利用牛顿法求解上面的式子,我们先选取初始点x0,然后进行如下迭代
    x n + 1 = x n − f ′ ( x n ) f ′ ′ ( x n ) x_{n+1}=x_{n}-\frac{f^{\prime}\left(x_{n}\right)}{f^{\prime \prime}\left(x_{n}\right)} xn+1=xnf(xn)f(xn)
    直到 ∣ x n + 1 − x n ∣ &lt; ϵ | x_{n+1}-x_{n} |&lt;\epsilon xn+1xn<ϵ
    综上,牛顿法求根是一阶算法,我们将优化问题转为求根问题需要一阶导数,所以用牛顿法进行最优化是二阶算法。

    参考资料
    http://sofasofa.io/forum_main_post.php?postid=1000966
    https://www.cnblogs.com/shixiangwan/p/7532830.html

    更多相关内容
  • 最优化中的牛顿法,二阶收敛性

    万次阅读 2016-11-17 02:05:35
    最近偶尔翻阅一本写的不错的最优化理论教材,该书讲得很详细,很透彻。我对非线性规划理论又有了全新的认识,发现牛顿法...适用对象:二阶可微函数 牛顿法的几何意义本质: 在原函数的某一点处用一个二次函数近似

    最近偶尔翻阅一本写的不错的最优化理论教材,该书讲得很详细,很透彻。我对非线性规划理论又有了全新的认识,发现牛顿法可以说是是无约束优化中最重要的方法,其他方法:LM方法,高斯牛顿,拟牛顿法,共轭梯度法可以说是对牛顿法的扩展。准备闲来无事时将牛顿法的原理以及求解过程用数例好好再过一遍。
     

    适用对象:二阶可微函数

     

    1. 牛顿法的几何意义本质

           在原函数的某一点处用一个二次函数近似原函数,然后用这个二次函数的极小值点作为原函数的下一个迭代点。

    上面这句话也说明,若原函数本身是一个二次函数,则牛顿法一步就能到达极小点或鞍点。若原函数本身是一个二次正定函数,则牛顿法一步到达最小值点。

     

    2. 牛顿法的代数意义

     

    梯度与黑塞矩阵分别由下列符号表示:

      

      

    设任意点为 Xk,下个一迭代点位 Xk+Sk, 该迭代点在 Xk 处的泰勒展开式为:

    用下个迭代点的值代替改点的值,即:

    因此:

    所以,迭代方向为:

    该方向又称作牛顿方向。

     

    3. 牛顿法的二阶收敛性

    若初始点 x0 充分靠近极值点 x*,并且极值点 x* 的黑塞矩阵非奇异,并且黑塞矩阵在极值点附近 Lipschitz 连续,则牛顿法具有二阶收敛性。

    注:Lipschitz 连续是一种比普通连续性更强的连续,它限制了函数的改变速度。对于函数可行域的任意两点,存在一个常数 K,使得:

    证明:

    由黑塞矩阵的非奇异性与连续性知道,在 x*附近,存在一个常数 M,对于任意的 k,使得

    而:

    上式右端成立,是因为 g(x*)=0。继续:

    上式是因为:

    继续,再利用到 Lipstchitz 连续,得到:

    因此,牛顿迭代法二阶收敛。

    展开全文
  • 【最优化】二阶收敛算法

    千次阅读 2020-11-28 13:29:55
    给出了无约束优化问题中的二阶收敛算法,如共轭方向(梯度)算法,Powell算法和拟牛顿法。

    二阶收敛算法

    不管是前面的最速下降法还是最优梯度法,他们都是线性(一阶)收敛的;而在本章中我们要讨论二阶收敛的优化算法。
    该类算法不仅收敛速度加快,并且可以保证在有限步内找到最优解。

    从理解的角度,如果一个算法可以在有限步内找到二次函数的最优解的话,我们就说这个算法是二阶收敛的。


    相关背景概念

    最优步长算法性质

    《【最优化】无约束梯度算法》这一篇博文中,我们先是讲述了梯度算法的一般框架,然后确定了最速下降法的迭代形式;接着为了让步长k的选择具有自适应,我们引入了最优步长的思想(每一轮迭代都关于步长k进行一次一维搜索)得到了最优梯度法。

    文末,我们给出了结论“最优梯度法相邻两个点的搜索方向一定是正交的”。

    该结论在后续的算法中还会用到,且我们需要对其进行推广:

    • 使用了【最优步长】思想的算法,其本次迭代点的梯度方向一定与上一次的搜索方向是相互正交的。

    【证明】
    在这里插入图片描述

    二次函数及其概念

    1. 定义
    ——常数项、一次项及二次项的组合
    (1)标准形式
    在这里插入图片描述
    (2)矩阵向量形式
    在这里插入图片描述

    或者说矩阵A总是可以写成对称的形式,因为通过“矩阵向量形式-标准形式”的转换,总能把矩阵A化成对称阵的形式:
    在这里插入图片描述

    2. 性质

    (1)如果矩阵A是正定的,那么就称对应的二次函数f(x)是正定二次函数。

    p.s. 此处可以类比二次型的定义和分类。

    (2)对于二次函数,按照矩阵求导法则,可以得到其梯度向量;如果A是正定矩阵,那么正定二次函数f(x)就有一个唯一的最小值解
    在这里插入图片描述

    【证明】
    在这里插入图片描述

    共轭方向

    1. 共轭的定义
    (1)向量的正交
    如果两个向量的内积运算结果为0,则说该两个向量是相互正交的。
    u T v = < u , v > = 0 u^Tv = <u,v> = 0 uTv=<u,v>=0

    (2)相互共轭
    定义一个正定阵A,如果两个向量u和v满足u和Av是正交的,则说向量u和v关于矩阵A是共轭的。
    u T A v = < u , A v > = 0 u^TAv = <u,Av> = 0 uTAv=<u,Av>=0
    特殊地,如果给定一组向量u1,u2,…,un,且有uiTAuj = 0(i≠j),则成这一组向量u1,u2,…,un是关于矩阵A相互共轭的;显然,关于同一矩阵共轭的一组向量一定是线性无关的。

    正交可以看做是共轭的一种特殊形式,当矩阵A取单位阵I时,uTAv = uTv.

    对于任意给定的一个正定阵A,一定可以找到关于其相互共轭的两个向量;在本章二阶收敛算法的讨论下,我们会使用该类特殊向量的方向作为搜索方向,不再使用梯度方向。

    2. 算法思想
    整体算法的框架与【最优梯度法】保持一致,只不过用共轭搜索方向来替换前者内部的梯度方向。

    3. 结论与定理

    • 定理:在最优化的每一步采用共轭方向作为搜索方向得到的算法是二阶收敛的。

    我们在最开始就说过,讨论【二阶收敛】,只需要验证该算法是否可以在有限步内找到一个正定二次函数的最优解
    在这里插入图片描述

    • 结论:通过上述的证明,不难发现,【初始点的选择】、【共轭搜索方向的排列顺序】对于算法都没有影响。

    4. 示例
    在这里插入图片描述

    本例中共轭的两个向量都是给出的,我们只是通过给出的条件,利用算法进行计算;后续会讲解如何求解出关于某一矩阵共轭的两个向量。


    共轭方向法

    共轭方向法是一类算法的总称,用于描述那些其所有搜索方向都是相互共轭的方法。我们可以通过对前面所讨论的算法诸如【最优梯度法】进行修改得到共轭方向法。
    共轭方向法的关键就是找到关于给定矩阵共轭的两个向量。

    1. 评价
    共轭梯度法介于最速下降法和牛顿法之间,仅需要利用一阶导数信息;客服了最速下降法“收敛速度慢”的缺点,同时也规避了牛顿法“存储和计算二阶导数,开销大”的缺点,是求解大型(非)线性最优化问题的最有效算法之一。

    • 无需矩阵存储
    • 有较快收敛速度
    • 二阶收敛性

    2. 一般共轭方向法
    在这里插入图片描述

    共轭梯度法

    共轭梯度算法是一个典型的共轭方向算法,它的每一个搜索方向是互相共轭的。而这些搜索方向dk是负梯度方向-gk与上一次迭代的搜索方向dk-1的组合。因此,存储量少,计算方便。
    d k = − g k + β k − 1 d k − 1 , 其 中 β 为 组 合 系 数 d_k = -g_k +β_{k-1}d_{k-1},其中β为组合系数 dk=gk+βk1dk1β

    1. FR共轭梯度算法(Fletcher-Reeves)
    在这里插入图片描述

    p.s. 之前我们讨论了共轭方向法针对正定二次函数是可以在有限步收敛到最优解的,但是上述的算法不仅适用于二次函数;
    因此第三步【用当前找到的点xn再替换原先的点x0,然后重新开始新的迭代】是必要的。

    这些算法在借助计算机实现的时候,会存在计算误差,因此即使求解一个正二次函数的优化问题,也可能存在“无法在有限步收敛”的可能性,因此上述算法的第三步是完全必要的。

    2. 简要理解
    上述算法对于任意函数都是可行的,我们可以借助正二次函数的特例对其中的共轭方向求解思想进行验证:
    在这里插入图片描述
    在上文的算法中,我们使用FR公式计算得到关于给定矩阵相互共轭的两个向量,也就是FR共轭梯度算法。

    3. 示例
    在这里插入图片描述
    4. 评价
    在每一轮迭代,虽然只用到了一阶导数的相关信息,但仍然需要对梯度进行计算,计算量依然较为复杂。


    Powell算法

    Powell算法的核心是希望:不求解梯度就能找到相互共轭的两个向量。

    它认为:如果两个点x1和x2是在不同的初始点沿着相同的搜索方向进行一维搜索找到两个向量,那么在二次函数的优化问题中,向量x2-x1就应该和向量v相互正交。

    1. 算法思想与框架
    在这里插入图片描述
    综上所述:对于一个n维的无约束优化问题,在给定的循环终止条件未满足的情况下,会持续进行轮次的迭代,每一轮迭代会进行n+1次一维优化搜索,第n+1次搜索会沿着xn-x0的方向进行,且用该新的方向【xn-x0】替换初始的v0搜索方向。

    2. 算法过程图解

    图源《深度理解Powell优化算法》

    在这里插入图片描述

    上面链接给出的博文对于Powell算法的理论以及优化过程都讨论得很详尽,需要深度理解Powell算法的读者可以戳进原博文中进行了解。

    3. 示例
    在这里插入图片描述


    拟牛顿法

    1. 算法思想概述

    牛顿法对于优化问题的成功应用是在于其利用了Hessan矩阵的曲率信息,但是计算Hessan矩阵的工作量很大,且不是所有目标函数都有Hessan矩阵,因此我们联想——
    能否仅仅利用目标函数值和一阶导数的信息,构造出目标函数的曲率近似值,从而加快【类牛顿法】的收敛速度。

    在这里插入图片描述
    2. FP拟牛顿法
    在这里插入图片描述

    展开全文
  • 二阶收敛算法

    2019-05-05 19:53:00
    1.2 什么叫二阶收敛 如果在有限步内找到二次函数的最优解,则该算法就称为二阶收敛。 1.3 什么叫共轭方向 2 共轭梯度法 2.1 引入 2.2 特点 举个例子体会: 2.3 Fletcher-Reeves 算法 举个例子体会: 这个例子...

    1预备知识

    1.1 什么叫二次函数

    1414369-20190505193010883-4866117.png

    1.2 什么叫二阶收敛

    如果在有限步内找到二次函数的最优解,则该算法就称为二阶收敛。

    1.3 什么叫共轭方向

    1414369-20190505193257141-143027340.jpg

    2 共轭梯度法

    2.1 引入

    1414369-20190505193409245-643227944.jpg

    1414369-20190505193450229-171609056.jpg

    2.2 特点

    1414369-20190505193616986-986053878.jpg

    举个例子体会:

    1414369-20190505193809421-1930648325.jpg

    2.3 Fletcher-Reeves 算法

    1414369-20190505193926355-1610930905.jpg

    举个例子体会:

    1414369-20190505194059193-1515911470.jpg

    这个例子是想说明:按照前边的理论来说,对于二次函数,最多迭代n次(维数),必然达到最优点,而此例题是因为中间有计算的误差,所以没有达到最优点。解决办法是:执行步骤3。

    2.4 Powell 算法

    1414369-20190505194443975-869597546.jpg

    1414369-20190505194513780-1620182379.jpg

    举个例子体会:

    1414369-20190505194607227-1911618402.jpg

    这个例子想说明:有计算误差,所以最后的结果不为0。

    3 变尺度算法

    3.1 引入

    1414369-20190505194825620-2034455666.jpg

    3.2 Fletcher-Powell 变尺度算法

    1414369-20190505194941656-91501574.jpg

    举个例子体会:

    1414369-20190505195026003-1077127745.jpg

    1414369-20190505195159397-114703614.png

    转载于:https://www.cnblogs.com/Terrypython/p/10815844.html

    展开全文
  • 从带一个参数的三阶迭代族(其中包括 Halley迭代 ,Chebyshev迭代和超 Halley迭代)...在 Newton-Kantorovich型的假设条件下 ,通过用一个递推关系证明了此迭代族的三阶收敛性 ,并给出了非线性算子方程解的存在惟一性定理.
  • 对于一致算法的学习,还需要有图论基础知识作为先导内容学习,这里不加赘述,符号完全按照规定去写,如果有看到的朋友觉得写的不清楚,我再加一下图论内容。 二阶状态方程如下: ξ˙i=ζiζ˙i=uii=1,...,n\dot{\...
  • 把二维二阶椭圆问题的格林函数的双线性矩形元的逐点误差估计与一般二阶椭圆问题的一次线性元的超收敛性结合起来,对二维二阶椭圆问题的格林函数的双线性矩形元的超收敛性进行了研究,得到了相应的逐点误差估计.
  • 收敛性和收敛速度 对Newton法的迭代函数即公式(1)取导数,有: φ′(x)=f(x)f′′(x)[f′(x)]2 \varphi'(x)=\frac{f(x)f''(x)}{[f'(x)]^2} φ′(x)=[f′(x)]2f(x)f′′(x)​ 假定x∗x^*x∗是f(x)=0f(x)=0f(x)=0的...
  • 数学中正负开方术的收敛性讨论 运用数学原理论证了其二阶收敛性
  • 面试中一直以来有个热门问题就是:「xgboost 二阶泰勒展开为什么收敛快?」一般来说网上的背诵答案为:「一阶导数可以找到当前最陡峭的方向,二阶导数可以掌握一阶导数未来的变化信息,等于说二阶导数有更长远的规划...
  • 利用MATLAB验证样条插值的收敛性

    千次阅读 2021-04-28 04:58:34
    理论上证明样条插值的收敛性是比较困难的,但通过本实验可以验证这一理论结果。.实验内容请按一定的规则分别选择等距或者非等距的插值节点,并不断增加插值节点的个数。考虑实验2.1中的函数或选择其他你有兴趣的函数...
  • 研究二阶非线性差分方程xn+1=f(xn,xn-1) n=0,1,2,…的正解的收敛性,其中初始值x-1,x0∈(0,+∞).通过改变方程的条件,可得到每个非振荡的正解都收敛于平衡解x,每个振荡的正解都收敛于唯一的二周期解或每个...
  • 针对二阶积分器多智能体系统,提出了一类非光滑一致协议设计方法。首先,基于反步设计方法,将速度看成虚拟控制量,并设计虚拟速度,使得状态一致可以渐近达到。然后,基于有限时间控制方法设计控制律使得真实...
  • 给出一种新的,具有较大收敛域的 Newton迭代法和 Newton下山法...它不要求函数 f( x)存在二阶导数,只需要函数 f( x)存在一阶导数,便可根据文中定理对其收敛性进行判别,弥补了以往相关定理的不足,并通过数值例子给予验证.
  • 本文的目的是使用MATLAB进行数值实验,以支持和验证Wang用L2投影方法求解二阶椭圆问题的有限元方法(CFEM)的超收敛性。 MATLAB代码已发布在https://github.com/annaleeharris/Superconvergence-CFEM,供任何人使用...
  • 为了提高传统二阶终端滑模控制的全局收敛性,提出一种快速二阶终端滑模控制算法.设计一种二阶趋近律,将绝对值函数隐藏在积分项里,并增加线性项以提高全局收敛性.当系统状态未到达滑模面时,采用二阶趋近律,并通过调整...
  • 然后通过三自由度分离质量模型的模拟,验证了该方法的收敛性和其他算法性能。理论分析和数值模拟结果表明,该方法具有良好的稳定性和二阶精度,与直接积分方法相比更适合用于复杂结构的实时子结构试验及类似的并行
  • 在此基础上运用线性系统理论与矩阵论,提出了二阶连续时间线性多智能体系统优化的一致协议,并利用图的代数连通度性质说明了协议的有效。数值仿真验证了该优化协议可使多智能体系统的状态快速达到一致,说明提出的...
  • 该方法不需要PV节点转化为PQ节点的过程,也不需要将环路解列及复杂的节点编号,没有对Jacobian矩阵进行简化和近似,具有二阶收敛性。算例表明,所提方法计算速度快,能够处理所有常见的分布式电源,具有较强环路处理...
  • 例如由二阶线性常微分方程与二阶线性椭圆型方程的边值问题所得到的差分方程的收敛性与误差估计一般是利用极值原理或差分格林函数来处理的([1][2])。又如对线性偏微分方程初值问题的差分方程的收敛性一般是通过了稳定...
  • 为了提高多点切触加工算法的计算效率,对其中的Hermite算法进行了改进,并且对改进后的Hermite算法的收敛性进行了理论分析,推导了改进后算法的局部收敛条件,同时给出算法的Steffensen加速迭代公式并新提出了一种...
  • 文章目录无约束优化---牛顿法1牛顿法牛顿法求根2收敛速度3牛顿法的二次收敛性4 Modifified Newton method修正牛顿法例子参考资料 无约束最优化问题: (P)   min⁡   f(x)s.t. &...
  • 基于比SCFO更复杂的特征方程(即二阶)证明了ECFO的收敛性差分方程。 用离散时间线性系统的稳定性理论进行分析粒子的运动方程。 稳定性条件将其特征值限制在复杂平面的单位周期内,并推导与ECFO参数有关的相应收敛...
  • 给出了该方法的通用迭代过程,利用可靠度指标在标准正态空间中的几何意义,分别对极限状态面为凸、凹、平坦的情况,进行了该方法收敛性的证明,并提出了确定迭代步长的建议算法.通过实例,分析验证了该迭代方法的...
  • 讨论了无约束优化的伪Newton-δ秩1校正公式,证明了伪Newton-δ秩1校正公式是满足伪牛顿方程的唯一最优解和在目标函数满足二阶连续可微,其Hessian矩阵满足Lipschitz条件和在最优...δ秩1的线性收敛性和超线性收敛性
  • 斯蒂芬森的

    2015-09-20 15:51:04
    欢迎来的新博客 广东南穗精神康复研究院来了
  • 关注公众号,发现CV技术之美本文分享 CVPR 2022 论文『SC^2-PCR: A Second Order Spatial Compatibility for Efficient and Robust Point Cloud Registration』,二阶相似测度,让传统配准方法取得比深度学习更好...
  • 正则假设或拟一致条件是进行有限元理论分析的基本假设,本文在不满足该假设的条件下,采用一种更简便的方法给出了双线元在求解二阶问题时的超逼近结果;在此基础上,又得到了其在中心点的点态超收敛结果;最后的数值...
  • 介绍了一类不可微优化的次梯度算法,并结合文献[9],给出了次梯度算法的简化形式;通过引进二阶方向导数的概念,证明了不可微函数的...利用这些中值定理,借助文献[9]的证明方法,证明了一般的次梯度算法都具有线性收敛性.
  • 求解NSOCP的增广拉格朗日方法的局部收敛性分析,张思雨,刘陶文,本文研究求解非线性二阶锥规划问题(NSOCP)的增广拉格朗日函数方法, 证明了该方法在约束非退化条件和强二阶充分条件下具有局部收敛性

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 11,293
精华内容 4,517
热门标签
关键字:

二阶收敛性