精华内容
下载资源
问答
  • 最速下降法收敛速度
    千次阅读
    2019-07-31 16:54:13

    摘自《数值最优化方法》
    \qquad 已知 设步长为 α \alpha α,下降方向为 d d d f ( x k + α d ) f(x_{k}+\alpha d) f(xk+αd) x k x_{k} xk T a y l o r Taylor Taylor展示为
    f ( x k + 1 ) = f ( x k + α d ) = f ( x k ) + α g k T d + O ( ∣ ∣ α d ∣ ∣ 2 ) f(x_{k+1})=f(x_{k}+\alpha d)=f(x_{k})+\alpha g_{k}^{T}d+O(||\alpha d||^{2}) f(xk+1)=f(xk+αd)=f(xk)+αgkTd+O(αd2)为使函数值下降,下降方向满足
    g k T d &lt; 0 g_{k}^{T}d&lt;0 gkTd<0
    \qquad 收敛性和收敛速度 收敛性 算法产生的点阵 { x k } \{x_{k}\} {xk}在某种范数 ∣ ∣ ⋅ ∣ ∣ ||\cdot|| 意义下满足
    l i m k → ∞ ∣ ∣ x k − x ∗ ∣ ∣ = 0 \mathop{lim}\limits_{k\to\infty}||x_{k}-x^{*}||=0 klimxkx=0称算法是收敛的,当从任意初始点出发时,都能收敛到 x ∗ x^{*} x称为具有全局收敛性,仅当初始点与 x ∗ x_{*} x充分接近时才能收敛到 x ∗ x^{*} x称算法具有局部收敛性
    \qquad 收敛速度(已知收敛):若
    l i m k → ∞ ∣ ∣ x k + 1 − x ∗ ∣ ∣ ∣ ∣ x k − x ∗ ∣ ∣ = a \mathop{lim}\limits_{k\to\infty}\frac{||x_{k+1}-x^{*}||}{||x_{k}-x^{*}||}=a klimxkxxk+1x=a \qquad 0 &lt; a &lt; 1 0&lt;a&lt;1 0<a<1时,迭代点列 { x k } \{x_{k}\} {xk}的收敛速度是线性的,这时算法称为线性收敛。当 a = 0 a=0 a=0时, { x k } \{x_{k}\} {xk}的收敛速度是超线性的,称为超线性收敛
    \qquad 二阶收敛:若
    l i m k → ∞ ∣ ∣ x k + 1 − x ∗ ∣ ∣ ∣ ∣ x k − x ∗ ∣ ∣ 2 = a \mathop{lim}\limits_{k\to\infty}\frac{||x_{k+1}-x^{*}||}{||x_{k}-x^{*}||^{2}}=a klimxkx2xk+1x=a \qquad a a a为任意常数,迭代点列 { x k } \{x_{k}\} {xk}的收敛速度是二阶的,这时算法称为二阶收敛。超线性收敛和二阶收敛的收敛速度较快,是理想的收敛速度
    \qquad 负梯度法和牛顿 ( N e w t o n ) (Newton) (Newton)型方法 N e w t o n Newton Newton型方法特殊情形的一种负梯度方法—最速下降法。首先下降方向满足 g k T d &lt; 0 g_{k}^{T}d&lt;0 gkTd<0,为使 ∣ g k d ∣ |g_{k}d| gkd达到最大值,则由 C a u c h y − S c h w a r z Cauchy-Schwarz CauchySchwarz不等式
    ∣ g k T d ∣ ≤ ∣ ∣ g k ∣ ∣ ∣ ∣ d ∣ ∣ |g_{k}^{T}d|\leq||g_{k}||||d|| gkTdgkd知当且仅当 d = d k = − g k / ∣ ∣ g k ∣ ∣ d=d_{k}=-g_{k}/||g_{k}|| d=dk=gk/gk时,等式成立, g k T d g_{k}^{T}d gkTd达到最小。考虑在 d k d_{k} dk方向上的步长,取其负梯度方向 d k = − g k d_{k}=-g_{k} dk=gk
    \qquad 收敛性分析 1. 给定 G G G度量下的范数定义,给出 K a n t o r o v i c h Kantorovich Kantorovich不等式。定义 G ∈ R n × n G\in\mathbb{R}^{n\times n} GRn×n对称正定, u , v ∈ R n u,v\in\mathbb{R}^{n} u,vRn u u u v v v G G G度量意义下的内积 ( u T v ) G (u^{T}v)_{G} (uTv)G的定义为
    ( u T v ) G = u T G v (u^{T}v)_{G}=u^{T}Gv (uTv)G=uTGv u u u G G G度量下的范数定义为 ∣ ∣ u ∣ ∣ G 2 ||u||_{G}^{2} uG2定义为
    ∣ ∣ u ∣ ∣ G 2 = u T G u ||u||_{G}^{2}=u^{T}Gu uG2=uTGu G G G度量下的 C a u c h y − S c h w a r z Cauchy-Schwarz CauchySchwarz不等式
    ∣ u T G u ∣ ≤ ∣ ∣ u ∣ ∣ G ∣ ∣ v ∣ ∣ G |u^{T}Gu|\leq||u||_{G}||v||_{G} uTGuuGvG成立,当且仅当 u , v u,v u,v共线时等号成立。
    \qquad 2. K a n t o r o v i c h 不 等 式 Kantorovich不等式 Kantorovich 对于 x ∈ R n \ { 0 } x\in\mathbb{R}^{n} \verb|\| \{0\} xRn\{0},有
    ( x T x ) 2 ( x T G x ) ( x T G − 1 x ) ≥ 4 λ m a x λ m i n ( λ m a x + λ m i n ) 2 \frac{(x^{T}x)^{2}}{(x^{T}Gx)(x^{T}G^{-1}x)}\ge\frac{4\lambda_{max}\lambda_{min}}{ (\lambda_{max}+ \lambda_{min})^{2}} (xTGx)(xTG1x)(xTx)2(λmax+λmin)24λmaxλmin λ m a x 、 λ m i n \lambda_{max}、\lambda_{min} λmaxλmin分别为矩阵 G G G的最大、最小特征值。 G G G度量的定义下 x k x_{k} xk的误差等价于它的目标函数值 f ( x k ) f(x_{k}) f(xk)的误差
    \qquad 最速下降法在 G G G度量定义下的收敛速度 给定正定二次函数
    f ( x ) = 1 2 x T G x + b T x f(x)=\frac{1}{2}x^{T}Gx+b^{T}x f(x)=21xTGx+bTx由负梯度方向为 d k = − g k d_{k}=-g_{k} dk=gk则求解最速下降法步长为
    α m i n = a r g m i n α &gt; 0 f ( x k − α g k ) \alpha_{min}=arg\mathop{min}\limits_{\alpha&gt;0}f(x_{k}-\alpha g_{k}) αmin=argα>0minf(xkαgk)其中
    f ( x k − α g k ) = 1 2 ( x k − α g k ) T G ( x k − α g k ) + b T = f ( x k ) + 1 2 g k T G g k α 2 + g k T ( G x k + b ) α = f ( x k ) − g k T g k α + 1 2 g k T G g k α 2 f(x_{k}-\alpha g_{k})=\frac{1}{2}(x_{k}-\alpha g_{k})^{T}G(x_{k}-\alpha g_{k})+b^{T}\\ = f(x_{k})+\frac{1}{2}g_{k}^{T}Gg_{k}\alpha^{2}+g_{k}^{T}(Gx_{k}+b)\alpha \\ = f(x_{k})-g_{k}^{T}g_{k}\alpha+\frac{1}{2}g_{k}^{T}Gg_{k}\alpha^{2} f(xkαgk)=21(xkαgk)TG(xkαgk)+bT=f(xk)+21gkTGgkα2+gkT(Gxk+b)α=f(xk)gkTgkα+21gkTGgkα2 α \alpha α求导,由凸函数性质,极小值必要条件,得最优步长
    α k = g k T g k g k T G g k \alpha_{k}=\frac{g_{k}^{T}g_{k}}{g^{T}_{k}Gg_{k }} αk=gkTGgkgkTgk \qquad 将最优步长带上式中,得到迭代方程(二分之一的来历!!!!,使用泰勒展开为一阶没有二分之一,直接带入原方程中有二分之一,有无受泰勒展开的精度影响)
    f ( x k + 1 ) = f ( x k ) − 1 2 ( g k T g k ) 2 g k T G g k f(x_{k+1})=f(x_{k})-\frac{1}{2}\frac{(g_{k}^{T}g_{k})^{2}}{g_{k}^{T}Gg_{k}} f(xk+1)=f(xk)21gkTGgk(gkTgk)2 \qquad G x ∗ = − b Gx^{*}=-b Gx=b f ( x ∗ ) = − 1 2 b T G − 1 b f(x^{*})=-\frac{1}{2}b^{T}G^{-1}b f(x)=21bTG1b得到
    f ( x k + 1 ) − f ( x ∗ ) f ( x k ) − f ( x ∗ ) = 1 − ( g k T g k ) 2 g k T G g k x k T G x k + 2 b T x k + b T G − 1 b = 1 − ( g k T g k ) 2 g k T G g k ( G x k + b ) T G − 1 ( G x k + b ) = 1 − ( g k T g k ) 2 ( g k T G g k ) ( g k T G − 1 g k ) \frac{f(x_{k+1})-f(x^{*})}{f(x_{k})-f(x^{*})}=1-\frac{\frac{(g_{k}^{T}g_{k})^{2}}{g_{k}^{T}Gg_{k}}}{x_{k}^{T}Gx_{k}+2b^{T}x_{k}+b^{T}G^{-1}b}\\ = 1-\frac{\frac{(g_{k}^{T}g_{k})^{2}}{g_{k}^{T}Gg_{k}}}{(Gx_{k}+b)^{T}G^{-1}(Gx_{k}+b)}\\ = 1-\frac{(g_{k}^{T}g_{k})^{2}}{(g_{k}^{T}Gg_{k})(g_{k}^{T}G^{-1}g_{k})} f(xk)f(x)f(xk+1)f(x)=1xkTGxk+2bTxk+bTG1bgkTGgk(gkTgk)2=1(Gxk+b)TG1(Gxk+b)gkTGgk(gkTgk)2=1(gkTGgk)(gkTG1gk)(gkTgk)2 \qquad G G G度量的定义下 x k x_{k} xk的误差等价于它的目标函数值 f ( x k ) f(x_{k}) f(xk)的误差。得:
    ∣ ∣ x k + 1 − x ∗ ∣ ∣ G 2 ∣ ∣ x k − x ∗ ∣ ∣ G 2 = 1 − ( g k T g k ) 2 ( g k T G g k ) ( g k T G − 1 g k ) \frac{||x_{k+1}-x^{*}||^{2}_{G}}{||x_{k}-x^{*}||^{2}_{G}}=1-\frac{(g_{k}^{T}g_{k})^{2}}{(g_{k}^{T}Gg_{k})(g_{k}^{T}G^{-1}g_{k})} xkxG2xk+1xG2=1(gkTGgk)(gkTG1gk)(gkTgk)2 \qquad K a n t o r o v i c h Kantorovich Kantorovich不等式得到
    ∣ ∣ x k + 1 − x ∗ ∣ ∣ G 2 ∣ ∣ x k − x ∗ ∣ ∣ G 2 ≤ ( λ m a x − λ m i n λ m a x + λ m i n ) 2 \frac{||x_{k+1}-x^{*}||^{2}_{G}}{||x_{k}-x^{*}||^{2}_{G}}\leq(\frac{\lambda_{max}-\lambda_{min}}{\lambda_{max}+\lambda_{min}})^{2} xkxG2xk+1xG2(λmax+λminλmaxλmin)2得到最速下降法得收敛速度是线性的,这个速度依赖于G的最大、最小特征值
    \qquad 条件数 线性方程组 G x + b = 0 Gx+b=0 Gx+b=0是由 G G G b b b确定的(求解 x ∗ x^{*} x),当 G G G b b b中的数据带有误差时(产生扰动),则两个参数扰动对线性方程组的求解影响由条件数反映 条 件 数 的 定 义 ! ! ! \color{#F00}{条件数的定义!!!}
    c o n d ( G ) = ∣ ∣ G ∣ ∣   ∣ ∣ G ∣ ∣ − 1 cond(G)=||G||\ ||G||^{-1} cond(G)=G G1 \qquad 称为矩阵 G G G的条件数,条件数与范数有关,如
    ∣ ∣ G ∣ ∣ 2 ∣ ∣ G − 1 ∣ ∣ 2 = λ m a x λ m i n ||G||_{2}||G^{-1}||_{2}=\frac{\lambda_{max}}{\lambda_{min}} G2G12=λminλmax若矩阵 G G G的条件数很大,扰动对解的影响就可能很大,这种问题称为病态的
    \qquad 由最速下降法收敛速度式得:
    λ m a x + λ m i n λ m a x − λ m i n = c o n d ( G ) − 1 c o n d ( G ) + 1 = Δ μ \frac{\lambda_{max}+\lambda_{min}}{\lambda_{max}-\lambda_{min}}=\frac{cond(G)-1}{cond(G)+1}\mathop{=}\limits^{\Delta}\mu λmaxλminλmax+λmin=cond(G)+1cond(G)1=Δμ \qquad 最速下降法收敛速度依赖于 G G G得条件数,当条件数接近1时,收敛速度接近超线性收敛,条件数越大,收敛速度越慢

    更多相关内容
  • 在一般问题的优化中,最速下降法和共轭梯度法都是非常有用的经典方法,但最速下降法往往以”之”字形下降,速度较慢,不能很快的达到优值,共轭梯度法则优于最速下降法,在前面的某个文章中,我们给出了牛顿法和...
  • 最速下降法与牛顿法的收敛速率

    万次阅读 2015-06-06 09:41:20
    在MIT的公开课[Introduction to Computer Science and Programming Using Python] 6.00.1x 中,Eric Grimson曾提到过迭代算法的思想就在于将当前迭代点向正确的方向...除此之外,我们还关心不同优化算法收敛速率(rat

    在MIT的公开课[Introduction to Computer Science and Programming Using Python] 6.00.1x 中,Eric Grimson曾提到过迭代算法的思想就在于将当前迭代点向正确的方向移动一定的“步长”,然后检验目标值是否满足一定要求。同时,“方向”和“步长”也是不同优化算法主要关心的两个方面。除此之外,我们还关心不同优化算法的收敛速率(rate of convergence),这表征了算法是否能在尽量少的迭代次数之外逼近最优解。本文以最速下降法(Steep Descent)和牛顿法(Netwon Method)为例,说明不同算法的收敛速率。本文主要参考了Jorge Nocedal 和 Stephen J. Wright 的 Numerical Optimization 一书(第二版)。

    最速下降法(Steep Descent)

    最速下降法的思路是以当前迭代点的导数方向的相反方向,也就是下降最快的方向(名字由来),为前进方向。步长选取的一种思路是选择相应的步长使得目标函数取在前进方向上取得最小值。

    这里我们以一个简单的二次规划命题为例进行说,即

    f(x)=12xTQx+cTx
    其中 Q 是对称正定阵。对于目标函数 f(x) ,记当前的迭代点为 xk f(x) xk 处的一阶导数为 fk=Qx+c 。于是在 xk 处的前进方向即为 fk 。 要确定前进的步长,即要是的下面这个以 α 为决策变量的优化命题取得最小值:
    f(xαfk)=12(xαfk)TQ(xαfk)+cT(xαfk)
    令上式对 α 的导数为 0 即可求得对应步长为:
    αk=fTkfkfTkQfk
    因此,每一步更新迭代点的过程为:
    xk+1=xkfTkfkfTkQfkfk

    因此,最速下降法的迭代轨迹可以用下图描述。

    这里写图片描述

    图片来源:Nocedal, Jorge, and Stephen J. Wright. “Numerical Optimization 2nd.” (2006).

    通过仿真,可以看出,如下图这样一个二次函数

    这里写图片描述

    在二维投影上的迭代过程如下图:
    这里写图片描述


    在Numerical Optmization一书中,证明了最速下降法是线性收敛的(一阶收敛)。首先,针对二次函数有下式成立:

    12xxQ=f(x)f(x)
    其中, xQ=xTQx x 是最优点。同时可以证明:
    xk+1xQ(λnλ1λn+λ1)2xkxQ
    其中 λ1λ2λn Q 的特征值。

    对于一般性的二阶可导的函数,在满足一定要求的前提下,也有下面的收敛速率的描述:

    f(xk+1)f(x)r2f(x)f(x)
    其中,
    r(λnλ1λn+λ1,1)
    这里, λ1λ2λn 2f(x) 的特征值。

    从这个结论可以看出,通常意义下,我们可以用条件数作为一个优化命题难解程度的衡量,如果条件数越大,在上图等高线中的圆圈就越扁,相应的收敛速度就越慢。而当条件数较小时,尤其在极端情况下,矩阵的特征值都全等时,上图的等高线就呈现完美的圆形,因此一步就可以收敛。

    Numerical Optmization一书中对这一结果的评论是=“the steepest descent method can have an unacceptably slow rate of convergence, even when the Hessian is reasonably well conditioned.”并举例说,一个条件数为800的对象, f(x1)=1 f(x)=0 。那么根据上面的定理,在1000次迭代之后目标函数的值仍然还是0.08。

    但是利用上面的结论,如果我们提前知道目标函数的最优值 f(x) ,我们可以对最速下降法的迭代次数做出估计,通过随机生成100个二次规划的命题,我在这里比较了上式给出的迭代次数上界和实际迭代次数,结果如下图:

    这里写图片描述

    从图中可以看出,并不能说这里给出的上界是“紧”还是“不紧”。

    牛顿法(Newton Method)

    相对于最速下降法,牛顿法的下降方向并不是迭代点的导数方向,而是在迭代点出Taylor展开到二阶后取得最小值的方向。即对于一般性的连续二阶可到的函数 f(x) ,在 xk 处展开到二阶为

    f(xk+p)fk+pTfk+12pT2fk
    对上求极小值(即令一阶导等于0),可以得到在当前点的Newton方向为
    pNk=2f1kfk

    因为Newton法是求二阶近似后的最小值,因此对于无约束的二次规划,Newton法可以一步收敛到最小值,如图:

    这里写图片描述

    对于一般性的函数,上面的Newton Step并不能保证目标函数单调下降,但在满足一定条件的情况下,并在最优点附近的邻域内,可以证明牛顿法是二阶收敛的,也就是说收敛速度要快于最速下降法。具体的证明在这里不加赘述,这里只给出推导的结论:

    xk+pNkxL2f(x)1xkx2
    其中, L 是证明过程中用到的 Lipschitz 常数。

    Ref.
    Nocedal, Jorge, and Stephen J. Wright. “Numerical Optimization 2nd.” (2006).

    展开全文
  • 最速下降法最速下降法特征最速下降法的优缺点3. Newton法算法基本思想牛顿法和梯度下降法的效率对比 1. 一维搜索 优化问题一般选择某一组变量,然后在满足一定的限制条件下,求出使目标值达到最优(最大或最小)...

    1. 一维搜索

    最优化问题一般选择某一组变量,然后在满足一定的限制条件下,求出使目标值达到最优(最大或最小)的变量值。大部分时候,最优化问题都采用迭代计算的方式来求解。而大多数迭代下降算法都具有的共同点是在得到某次迭代点 x k x^k xk后,需要按照一定规则来确定一个方向 d k d^k dk,沿着该方向在直线上求函数的极小点得到下一个迭代点 x x xk+1
    这样不断在一维的目标函数上,求其在各迭代点的直线方向上的极小点,直到求出问题最优解的方式就被称为一维搜索,或者线搜索。其一般过程可用如下公式表示:
    在这里插入图片描述

    其中 d k d^k dk 表示在这一步的搜索方向,步长因子 λ λ λ 决定了沿着该方向前进多远,这两者共同决定了该搜索算法的好坏。一维搜索的算法有好多种,以下介绍几种常见的。

    2. 最速下降法

    上文中的一维搜索( x x xk+1 = x k x^k xk + λ d k λd^k λdk)可归结为单变量函数的最优化问题,也是最速下降法的基础。其迭代过程中最重要的就是为下次迭代选择一个合适的方向 d k d^k dk
    人们利用了梯度方向是函数值增长最快的方向的思想,来让迭代点沿着负梯度方向前进,保证函数的“最速”下降。
    以下直接给出公式:
    在这里插入图片描述
    在最速下降法中,步长 λ λ λ 由式子求出,是一种精确步长的搜索方式。其与梯度下降法的区别也在于此,梯度下降中的步长往往是由工程师自己预先设置好的一个固定值,因此梯度下降法只是最速下降法中的一种特殊形式。
    在这里插入图片描述
    补充:梯度下降法容易陷入局部极小值(如下图所示)。
    在这里插入图片描述

    形象点地说,假设有一小球要从山顶滚到山脚,那么每次沿最陡峭(梯度)的方向向下滚是最快的。
    在确定了每次下降的方向的同时也需要小心地选择一个合适的步长。若是过大,可能导致迭代点发散,过小则导致收敛太慢。

    最速下降法在极小化目标函数时的相邻两个搜索方向是正交的。
    在这里插入图片描述
    【例】利用最速下降法求 m i n f ( x ) = x 1 2 + 2 x 2 2 − 2 x 1 x 2 − 4 x 1 minf(x) = x_1^2 + 2x_2^2 - 2x_1x_2 - 4x_1 minf(x)=x12+2x222x1x24x1 ,取初始向量 x 0 = ( 1 , 1 ) T x_0 = (1,1)^T x0=(1,1)T
    在这里插入图片描述
    在这里插入图片描述

    最速下降法特征

    相邻两次迭代的方向互相垂直。
    在这里插入图片描述

    • 最速下降法在两个相邻点之间的搜索方向是正交的。
    • 最速下降法向极小点逼近是曲折前进的,这种现象称为锯齿现象,锯齿现象会影响收敛速度!
      在这里插入图片描述
      缺点:最速下降法收敛速度慢!
    • 在最速下降法中,利用精确一维搜索求最佳步长,使得相邻两次迭代的搜索方向总是垂直的,使得逼近极小点过程是“之”字形。
      在这里插入图片描述
      这样从任何一个初始点开始,都可以很快达到极小点附近,但是越靠近极小点步长越小,移动越慢,导致最速下降法的收敛速度很慢。实际运用中,在可行的计算时间内可能得不到需要的结果。

    最速下降法的优缺点

    • 优点:理论明确,程序简单,每次的计算量小,所需的存储量小,对初始点要求不合格。
    • 缺点:收敛速度并不快,因为最速下降方向仅仅是指某点的一个局部性质。

    【补充】一些有效算法是通过对它的改进或利用它与其他收敛快的算法结合而得到的,因此它是无约束优化的方法之一。在计算的前中期使用梯度下降,而在接近极小点时使用其他算法进行迭代会是更理想的方案。

    3. Newton法

    此处介绍的牛顿法是其在一维搜索中的推广形式。与最速下降法一样可用于求解一般无约束的多元优化问题。其基本思想还是采用泰勒二阶展开来拟合极小点附近的函数来进行迭代
    在这里插入图片描述

    算法基本思想

    考虑从 x k x^k xk x x x k+1 的迭代过程,在 x k x^k xk 点处对函数 f ( x ) f(x) f(x) 泰勒展开:
    在这里插入图片描述
    略去高阶项,得到
    在这里插入图片描述
    f ( x ) f(x) f(x) 求梯度得(第三项求导后是高阶可以省略):
    在这里插入图片描述
    移项得:
    在这里插入图片描述
    两边同时乘二阶导数项的逆矩阵,然后移项可得极小点:
    在这里插入图片描述
    Newton法的计算步骤如下:
    在这里插入图片描述
    【例】用Newton方法求 f ( x 1 , x 2 ) = x 1 2 + 25 x 2 2 f(x_1,x_2) = x_1^2 + 25x_2^2 f(x1,x2)=x12+25x22 的极小点。
    在这里插入图片描述
    由于牛顿法是基于当前位置的切线来确定下一次的位置,所以牛顿法又被很形象地称为是"切线法"。牛顿法的搜索路径(二维情况)如下图所示:

    在这里插入图片描述

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

    从本质上去看,牛顿法是二阶收敛,梯度下降是一阶收敛,所以牛顿法就更快。
    如果更通俗地说的话,比如你想找一条最短的路径走到一个盆地的最底部,梯度下降法每次只从你当前所处位置选一个坡度最大的方向走一步,牛顿法在选择方向时,不仅会考虑坡度是否够大,还会考虑你走了一步之后,坡度是否会变得更大。所以,可以说牛顿法比梯度下降法看得更远一点,能更快地走到最底部。(牛顿法目光更加长远,所以少走弯路;相对而言,梯度下降法只考虑了局部的最优,没有全局思想。)
    根据wiki上的解释,从几何上说,牛顿法就是用一个二次曲面去拟合你当前所处位置的局部曲面,而梯度下降法是用一个平面去拟合当前的局部曲面,通常情况下,二次曲面的拟合会比平面更好,所以牛顿法选择的下降路径会更符合真实的最优下降路径。
    在这里插入图片描述
    图中红色的是牛顿法的迭代路径,绿色的是梯度下降法的迭代路径。

    4. 共轭梯度法

    共轭梯度法是基于共轭方向的一种算法。针对目标函数为二次函数的问题,其搜索方向是与二次函数系数矩阵相关的共轭方向。 用这类方法求解n元二次正定函数的极小问题,最多进行n次一维搜索。
    在这里插入图片描述
    几何意义:
    假设 f ( x ) f(x) f(x) n n n 元正定二次函数:
    在这里插入图片描述
    对于二维情况 n = 2 n=2 n=2,任任取初始点 x 0 x^0 x0 沿某个下降方向 d 0 d^0 d0 作精确一维搜索,得 x 1 = x 0 + l a m d a 0 d 0 x^1 = x^0 + lamda_0d^0 x1=x0+lamda0d0
    由精确一维搜索的性质,可知:
    在这里插入图片描述
    在这里插入图片描述
    这里参考了西北工业大学的PPT:最优化方法第二章:线搜索算法

    【参考资料】CSDN博客:@https://blog.csdn.net/zxxxxxxy/article/details/103850557

    展开全文
  • MATLAB最速下降法求解函数极小值

    千次阅读 多人点赞 2021-04-11 16:48:19
    MATLAB最速下降法求解函数极小值1.题目2.matlab代码2.1主函数2.2调用函数2.3运行结果3.分析 写在前面:最速下降法求解函数极小值的理论部分已经写在上一篇文章中,这篇文章直接进行具体问题的求解并附上matlab代码。...


    写在前面:最速下降法求解函数极小值的理论部分已经写在上一篇文章中,这篇文章直接进行具体问题的求解并附上matlab代码。

    1.题目

    在这里插入图片描述
    设初始点为[x1 x2]=[-2.5 4.5] ,ε≤0.01,求目标函数的极小值。

    2.matlab代码

    2.1主函数

    syms x1 x2 s; %声明符号变量
    
    f1 =  x1^4 - 2*x1^2*x2 - 2*x1*x2 + x1^2 + 2*x2^2 + 4.5*x1 - 4*x2 + 4;%设定目标函数
    
    k=steepest_descent(f1,x1,x2,s,[-2.5,4.25],10^(-2));  %设定起始点[x1 x2]=[-2.5,4.25]和精度10^(-2)
    
    result_string=sprintf('在 %d 次迭代后求出极小值\n',k);%在迭代多少次之后求出极小值
    disp(result_string);
    

    2.2调用函数

    function   k = steepest_descent(f,x1,x2,s,start_point,thereshold) 
        
        k = 0;%迭代次数赋值初始化
        
        grad_f = [diff(f,x1) diff(f,x2)]; %计算f的梯度
        
        delta = subs(grad_f,[x1,x2],[start_point(1),start_point(2)]);
        %计算起点的梯度
        
        step=1; %设置初始步长为1
        
        current_point = start_point;%起点值赋给当前点
        
        %最速下降法的主循环,判断条件为:梯度的模与所给精度值进行比较
        while norm(delta) > thereshold  
            
            k = k + 1;%迭代次数+1
            
            %一维探索 求最优步长(此时方向已知,步长s为变量)
            x_next = [current_point(1),current_point(2)] - s* delta/norm(delta);% 计算x(k+1)点,其中步长s为变量 
            f_val = subs(f,[x1,x2],[x_next(1),x_next(2)]);% 将x值带入目标函数中
            step = abs(double(solve(diff(f_val,s)))); % 对s求一阶导,并加绝对值符号,得到最优步长的绝对值
            step = step(1);%更新步长
            
            %计算x(k+1)点
            current_point = double([current_point(1),current_point(2)] - step * delta/norm(delta));
            
            %计算x(k+1)点的梯度值
            delta = subs(grad_f,[x1,x2],[current_point(1),current_point(2)]);
            
            %计算函数值
            f_value = double(subs(f,[x1,x2],[current_point(1),current_point(2)]));
            
            %输出迭代计算过程
            result_string=sprintf('k=%d, x1=%.6f, x2=%.6f, step=%.6f f(x1,x2)=%.6f',...
            k,current_point(1),current_point(2),step,f_value);
            disp(result_string);
            
        end
    end
    

    (使用代码时,只需要把主函数中目标函数 ;起始点; 精度,重新设置成你所需要的就可运行。)

    2.3运行结果

    在这里插入图片描述

    3.分析

    将收敛条件由ε≤0.01改为ε≤10^(-6),运行结果如下:
    在这里插入图片描述
    可以看出,利用最速下降法求函数极小值时,在最初几步迭代中函数值下降很快,但当函数值越接近理论极小值时,函数值下降的越慢,同时,越接近理论极小值时,步长也越小,因此最速下降法的收敛速度并不快,这是因为函数在x(k)点处的负梯度方向为其最速下降方向仅仅是针对该点处而言,,一旦离开该点,原先方向就不是最速下降方向了。

    最速下降方向只是针对当前的计算点而言,并非是全局的最速下降方向

    最速下降法优点:对初始点选择要求低,远离极值点时收敛速度快
         缺点:越逼近理论极小值,收敛速度越慢

    展开全文
  • 本文中就两种方法来探究一下,哪种收敛方法速度快“牛顿下降法的递推公式: xn+1=xn−f′(xn)/f″(xn){x}_{n+1}={x}_{n}-f'({x}_{n})/f''({x}_{n})梯度下降算法的递推公式: xn+1=xn−μ∗f′(xn){x}_{n+1}={x}_{
  • main为主函数 fun gfun ggfun分别为输入的...分别为最速下降法 牛顿法(阻尼)共轭梯度法 以及 拟牛顿法 F1-4为下降的图示 可以看到牛顿法和拟牛顿法收敛速度最快 但是牛顿法需要求矩阵的逆 在实际中 运算量可能较大
  • 松弛因子和预处理技术两种手段,同时把松弛因子引入原来的最速下降法中,使传统的最速下降法也具有了实用性和较好的收敛速度。设计两个算例分别验证了改进型最速下降法引入松弛因子和预处理两种手段以及对最速下降法...
  • 本章讨论无约束优化问题minf(x)minf(x)minf(x)的最速下降法和牛顿法及其改进算法,前者简单而古老,虽不再具有实用性,却是研究其他无约束优化算法的基础;后者也是一种经典的无约束优化算法,具有收敛速度快和自...
  • 最速下降法以及代码实现

    千次阅读 2021-04-23 06:46:53
    由于最近复习优化考试,为了防止考完即忘,这里做个笔记用于备忘,本文讲解一下无约束优化问题中的最速下降法。一、解决的问题速梯度下降法解决的问题是无约束优化问题,而所谓的无约束优化问题就是对目标函数的...
  • 基于最速下降法在解决无约束非线性规划问题中的重要性,对其原理与算法予以讨论。论文主要是参阅大量数学分析和运筹学书籍以及一些学术资料,结合自己在平时学习中掌握的知识,并在指导老师的建议下,针对最速下降法...
  • 最速下降法是以负梯度方向最为下降方向的极小化算法,相邻两次的搜索方向是互相直交的。牛顿法是利用目标函数在迭代点处的Taylor展开式作为模型函数,并利用这个二次模型函数的极小点序列去逼近目标函数的极小点。...
  • 最速下降法

    万次阅读 2019-09-08 21:42:00
    最速下降法作为求解无约束优化问题的入门算法,其思想是很多其他优化算法的基础。之前我一直对梯度下降法和最速下降法之间的关系和差异理解不清楚,只知道他们都是一阶方法,都沿负梯度方向迭代降低目标函数值,查...
  • Matlab 最速下降法 实列及代码实现

    多人点赞 2022-05-21 10:57:57
    本文主要带大家回顾了一下梯度概念,并讲解了最速下降法的有趣点,最后教如何利用matlab 构建代码模块完成最速下降法的代码编写。本文与其他文章的对比的创新点就是提供了一个可视化的动态寻优图,还有就是本文的...
  • 今天小天就对梯度下降法做一个完整的总结。一、梯度‍‍在微积分里面,对多元函数的参数求∂偏导数,把求得的各个参数的偏导数以向量的形式写出来,就是梯度。‍‍比如函数:分别对x,y求偏导数,求得的梯度向量就是,...
  • 优化Armijo算法确定步长的最速下降法.doc
  • 优化算法之——最速下降法

    万次阅读 多人点赞 2019-03-15 22:33:25
    引言:在解决无约束问题时,经常用到的一类算法最速下降法,在求解机器学习算法的模型参数,即无约束优化问题时,梯度下降(Gradient Descent)是常采用的方法之一,另一种常用的方法是小二乘法。在求解损失...
  • 本文介绍了无约束问题中常用的两种算法最速下降法和BFGS算法, 并通过matlab编程实现了以上两种算法,并对实际问题进行求解。
  • 最速下降法PPT及MATLAB程序.pptx 最速下降法,最速下降法,也称为梯度下降法,是由... 最速下降法是用负梯度方向为搜索方向,算法非常简单,并且通常对凸解析函数也有良好的收敛性。,最速下降法的基本思想,从任意一点...
  • 非线性方程组最速下降法(梯度法)梯度法(又名,最速下降法)(该法总可以收敛,但是,在接近真解时收敛速度会放慢。)梯度法又称为最速下降法,用于求解实系数非线性方程组(7-15)的一组根。梯度法首先是定义一个目标...
  • 最速下降是迭代的一种,可以用于求解最小二乘问题(线性和非线性都可以)。在求解机器学习算法的模型参数,即无约束优化问题时,梯度下降(Gradient Descent)是常采用的方法之一,另一种常用的方法是小二乘法。...
  • 前言 优化方法应用广泛,但在实现原理上大同小异。作者在学习高翔博士的视觉SLAM十四讲的过程中对其第六章非线性最小二乘求解所涉及到的优化方法(梯度下降、牛顿法、...梯度下降(最速下降法/一阶导数法) ...
  • 1 下降算法中的搜索方向 1.1 下降方向的判定 根据泰勒展开f(xk+αkdk)=f(xk)+αkgkTdk+o(∣∣αkdk∣∣2)f(x_k+\alpha_kd_k)=f(x_k)+\alpha_kg^T_kd_k+o(||\alpha_kd_k||^2)f(xk​+αk​dk​)=f(xk​)+αk​gkT​dk...
  • 最速下降法/梯度下降法

    万次阅读 多人点赞 2017-11-03 17:20:30
    锯齿现象梯度下降法在机器学习中是经常用到的一种方法,很多人也把梯度下降法看作是最速下降法,但是这两种方法好像还有一些细微差别,wikipedia中Gradient descent的描述中有这么一句:Gradient descent is also ...
  • 梯度下降法(Gradient Descent)或最速下降法(Steepest Descent)是求解无约束优化问题的一种常用的方法,有实现简单的有点。梯度下降法是迭代算法,每一步需要求解目标函数的梯度向量。 设f(x)f(x)f(x)是RnR^...
  • 文章目录无约束优化算法下降迭代算法前言要求收敛准则(criterion)线搜索基本无约束优化算法最速下降法(梯度)优缺点牛顿法 无约束优化算法 下降迭代算法 前言 可能有很多刚开始学优化的同学还对一些知识还不太...
  • Matlab实现 最速下降法&&共轭梯度法

    万次阅读 多人点赞 2019-07-09 19:22:57
    盲人下山法: 在山顶上,小盲人拿着小拐棍,...最速下降法 function [er,k]=FastDown(A) %定义最速下降法函数文件 %er:表示停机时实际绝对误差 %k:表示停机时实际迭代次数 tol=1e-6; [n,m]=size(A); if n~=m %判断输...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 4,963
精华内容 1,985
关键字:

最速下降法收敛速度