精华内容
下载资源
问答
  • 最速下降法收敛速度

    千次阅读 2019-07-31 16:54:13
    \qquad已知 设步长为α\alphaα,下降方向为ddd,f(xk+αd)f(x_{k}+\alpha d)f(xk​+αd)在xkx_{k}xk​的TaylorTaylorTaylor展示为 f(xk+1)=f(xk+αd)=f(xk)+αgkTd+O(∣∣αd∣∣2) f(x_{k+1})=f(x_{k}+\alpha d)=f...

    摘自《数值最优化方法》
    \qquad已知 设步长为α\alpha,下降方向为ddf(xk+αd)f(x_{k}+\alpha d)xkx_{k}TaylorTaylor展示为
    f(xk+1)=f(xk+αd)=f(xk)+αgkTd+O(αd2) f(x_{k+1})=f(x_{k}+\alpha d)=f(x_{k})+\alpha g_{k}^{T}d+O(||\alpha d||^{2}) 为使函数值下降,下降方向满足
    gkTd<0 g_{k}^{T}d<0
    \qquad收敛性和收敛速度 收敛性 算法产生的点阵{xk}\{x_{k}\}在某种范数||\cdot||意义下满足
    limkxkx=0 \mathop{lim}\limits_{k\to\infty}||x_{k}-x^{*}||=0 称算法是收敛的,当从任意初始点出发时,都能收敛到xx^{*}称为具有全局收敛性,仅当初始点与xx_{*}充分接近时才能收敛到xx^{*}称算法具有局部收敛性
    \qquad收敛速度(已知收敛):若
    limkxk+1xxkx=a \mathop{lim}\limits_{k\to\infty}\frac{||x_{k+1}-x^{*}||}{||x_{k}-x^{*}||}=a \qquad0<a<10<a<1时,迭代点列{xk}\{x_{k}\}的收敛速度是线性的,这时算法称为线性收敛。当a=0a=0时,{xk}\{x_{k}\}的收敛速度是超线性的,称为超线性收敛
    \qquad二阶收敛:若
    limkxk+1xxkx2=a \mathop{lim}\limits_{k\to\infty}\frac{||x_{k+1}-x^{*}||}{||x_{k}-x^{*}||^{2}}=a \qquadaa为任意常数,迭代点列{xk}\{x_{k}\}的收敛速度是二阶的,这时算法称为二阶收敛。超线性收敛和二阶收敛的收敛速度较快,是理想的收敛速度
    \qquad负梯度法和牛顿(Newton)(Newton)型方法 NewtonNewton型方法特殊情形的一种负梯度方法—最速下降法。首先下降方向满足gkTd<0g_{k}^{T}d<0,为使gkd|g_{k}d|达到最大值,则由CauchySchwarzCauchy-Schwarz不等式
    gkTdgkd |g_{k}^{T}d|\leq||g_{k}||||d|| 知当且仅当d=dk=gk/gkd=d_{k}=-g_{k}/||g_{k}||时,等式成立,gkTdg_{k}^{T}d达到最小。考虑在dkd_{k}方向上的步长,取其负梯度方向dk=gkd_{k}=-g_{k}
    \qquad收敛性分析 1. 给定GG度量下的范数定义,给出KantorovichKantorovich不等式。定义GRn×nG\in\mathbb{R}^{n\times n}对称正定,u,vRnu,v\in\mathbb{R}^{n}uuvvGG度量意义下的内积(uTv)G(u^{T}v)_{G}的定义为
    (uTv)G=uTGv (u^{T}v)_{G}=u^{T}Gv uuGG度量下的范数定义为uG2||u||_{G}^{2}定义为
    uG2=uTGu ||u||_{G}^{2}=u^{T}Gu GG度量下的CauchySchwarzCauchy-Schwarz不等式
    uTGuuGvG |u^{T}Gu|\leq||u||_{G}||v||_{G} 成立,当且仅当u,vu,v共线时等号成立。
    \qquad 2.KantorovichKantorovich不等式 对于xRn\{0}x\in\mathbb{R}^{n} \verb|\| \{0\},有
    (xTx)2(xTGx)(xTG1x)4λmaxλmin(λmax+λmin)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}} λmaxλmin\lambda_{max}、\lambda_{min}分别为矩阵GG的最大、最小特征值。GG度量的定义下xkx_{k}的误差等价于它的目标函数值f(xk)f(x_{k})的误差
    \qquad最速下降法在GG度量定义下的收敛速度 给定正定二次函数
    f(x)=12xTGx+bTx f(x)=\frac{1}{2}x^{T}Gx+b^{T}x 由负梯度方向为dk=gkd_{k}=-g_{k}则求解最速下降法步长为
    αmin=argminα>0f(xkαgk) \alpha_{min}=arg\mathop{min}\limits_{\alpha>0}f(x_{k}-\alpha g_{k}) 其中
    f(xkαgk)=12(xkαgk)TG(xkαgk)+bT=f(xk)+12gkTGgkα2+gkT(Gxk+b)α=f(xk)gkTgkα+12gkTGgkα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} α\alpha求导,由凸函数性质,极小值必要条件,得最优步长
    αk=gkTgkgkTGgk \alpha_{k}=\frac{g_{k}^{T}g_{k}}{g^{T}_{k}Gg_{k }} \qquad将最优步长带上式中,得到迭代方程(二分之一的来历!!!!,使用泰勒展开为一阶没有二分之一,直接带入原方程中有二分之一,有无受泰勒展开的精度影响)
    f(xk+1)=f(xk)12(gkTgk)2gkTGgk f(x_{k+1})=f(x_{k})-\frac{1}{2}\frac{(g_{k}^{T}g_{k})^{2}}{g_{k}^{T}Gg_{k}} \qquadGx=bGx^{*}=-bf(x)=12bTG1bf(x^{*})=-\frac{1}{2}b^{T}G^{-1}b得到
    f(xk+1)f(x)f(xk)f(x)=1(gkTgk)2gkTGgkxkTGxk+2bTxk+bTG1b=1(gkTgk)2gkTGgk(Gxk+b)TG1(Gxk+b)=1(gkTgk)2(gkTGgk)(gkTG1gk) \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})} \qquadGG度量的定义下xkx_{k}的误差等价于它的目标函数值f(xk)f(x_{k})的误差。得:
    xk+1xG2xkxG2=1(gkTgk)2(gkTGgk)(gkTG1gk) \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})} \qquadKantorovichKantorovich不等式得到
    xk+1xG2xkxG2(λmaxλminλmax+λmin)2 \frac{||x_{k+1}-x^{*}||^{2}_{G}}{||x_{k}-x^{*}||^{2}_{G}}\leq(\frac{\lambda_{max}-\lambda_{min}}{\lambda_{max}+\lambda_{min}})^{2} 得到最速下降法得收敛速度是线性的,这个速度依赖于G的最大、最小特征值
    \qquad条件数 线性方程组Gx+b=0Gx+b=0是由GGbb确定的(求解xx^{*}),当GGbb中的数据带有误差时(产生扰动),则两个参数扰动对线性方程组的求解影响由条件数反映\color{#F00}{条件数的定义!!!}
    cond(G)=G G1 cond(G)=||G||\ ||G||^{-1} \qquad称为矩阵GG的条件数,条件数与范数有关,如
    G2G12=λmaxλmin ||G||_{2}||G^{-1}||_{2}=\frac{\lambda_{max}}{\lambda_{min}} 若矩阵GG的条件数很大,扰动对解的影响就可能很大,这种问题称为病态的
    \qquad由最速下降法收敛速度式得:
    λmax+λminλmaxλmin=cond(G)1cond(G)+1=Δμ \frac{\lambda_{max}+\lambda_{min}}{\lambda_{max}-\lambda_{min}}=\frac{cond(G)-1}{cond(G)+1}\mathop{=}\limits^{\Delta}\mu \qquad最速下降法收敛速度依赖于GG得条件数,当条件数接近1时,收敛速度接近超线性收敛,条件数越大,收敛速度越慢

    展开全文
  • 文章目录无约束优化-----最速下降法最速下降法思想最速下降法的目标函数最速下降法步骤最速下降法的两个命题二次型函数的最速下降法收敛速度与收敛性最速下降法的缺点最速下降法的本质最速下降法与梯度下降法的差异...

    无约束优化-----最速下降法


    最优化知识笔记整理汇总,超级棒

    最速下降法思想

    无约束最优化问题:
    (P)   min   f(x)s.t.   xXRn \begin{aligned} (P) ~ ~ ~ \min &~ ~ ~ f(x)\\ \text{s.t.} &~ ~ ~x ∈ X ⊆ R^n \end{aligned}

    其中f(x)是可微的。如果x=xˉx = \bar{x}是一个给定的点,在d\|d\|足够小的时候,f(x)可近似为:
    f(xˉ+d)f(xˉ)+f(xˉ)Td(1) f(\bar{x}+d) \approx f(\bar{x}) + \triangledown f(\bar{x})^Td\tag{1}
    现在请注意,如果上面表达式的近似是好的,那么我们要选择dd使得内积f(xˉ)Td\triangledown f(\bar{x})^Td 也是足够小的。

    函数 f(x)f(x) 在点x处沿方向d的变化率可用方向导数表 示,当函数可微时有,方向导数
    Df(x,d)=f(x)Td(2) D f(x, d)=\nabla f(x)^{T} d\tag{2}
    求函数f(x)f(x)在点xx处下降最快的方向,归结为求
    minf(x)Td s.t d1(3) \begin{array}{l} \min \quad \nabla f(x)^{T} d \\ \text { s.t } \quad\|d\| \leq 1 \end{array}\tag{3}
    由Schwartz不等式,
    f(x)Tdf(x)df(x) \left|\nabla f(x)^{T} d\right| \leq\|\nabla f(x)\|\|d\| \leq\|\nabla f(x)\|
    f(x)Tdf(x) \Rightarrow \nabla f(x)^{T} d \geq-\|\nabla f(x)\|

    让我们把d标准化d=1\|d\|=1。在所有方向标椎化d=1\|d\|=1,所以当方向为:
    d~=f(xˉ)f(xˉ)(4) \tilde{d}=\frac{- \triangledown f(\bar{x})}{\|\triangledown f(\bar{x})\|}\tag{4}
    时(4)的等号成立,使其与梯度f(xˉ)\triangledown f(\bar{x})的内积最小。这一事实源自下列不等式:
    f(xˉ)Tdf(xˉ)d=f(xˉ)T(f(xˉ)f(xˉ))=f(xˉ)Td~(5) \triangledown f(\bar{x})^Td \geq -\|\triangledown f(\bar{x})\|\|d\| =\triangledown f(\bar{x})^T\left (\frac{- \triangledown f(\bar{x})}{\|\triangledown f(\bar{x})\|} \right ) = -\triangledown f(\bar{x})^T\tilde{d}\tag{5}

    因此未归一化方向为:
    dˉ=f(xˉ)(6) \bar{d}=-\triangledown f(\bar{x})\tag{6}
    称为xˉ\bar{x}处的最速下降方向。

    注意,dˉ=f(xˉ)\bar{d}=-\triangledown f(\bar{x})是一个只要f(xˉ)0\triangledown f(\bar{x}) \neq0的下降方向。可以看出,dˉTf(xˉ)=(f(xˉ))Tf(xˉ)<0\bar{d}^T\triangledown f(\bar{x})=-(\triangledown f(\bar{x}))^T\triangledown f(\bar{x})<0,只要f(xˉ)0\triangledown f(\bar{x}) \neq0

    最速下降法的目标函数

    所谓的最速下降法,就是在确定下降方向后,从下降方向中找到下降程度最大的一点进行下降。

    梯度下降法是先求出梯度,再根据预先设定的learning rate完成下降,那么就完成了一轮的优化;

    而最速下降法在求出梯度之后,要进行另外一个\large\color{#70f3ff}{\boxed{\color{green}{最小化优化问题}}}的求解过程,那就是选择最合适的learning rate,使得函数值最小,如果待求的函数为f(x)f(x),当前的迭代轮数为kk,那么当前函数的优化的参数解是xk{x}^k,这一点的梯度为f(xk)∇f({x}^k),于是我们\large\color{#70f3ff}{\boxed{\color{green}{最小化优化问题}}}就变成了:
    αk=arg  minαkf(xkαkf(xk))(7) \alpha_k=arg~~\min_{\alpha_k}f(x^k-\alpha_k∇f({x}^k))\tag{7}
    迭代公式:xk+1=xkαkf(xk)x^{k+1} = x^k -\alpha_k ∇f({x}^k)

    最速下降法步骤

    方向d=f(xˉ)d = −∇f(\bar{x}),是xˉ\bar{x}点处下降方向,注意,f(xˉ)Td<0∇f(\bar{x})^T d < 0只要f(x)0∇f(x) \neq 0。所以有f(xk+1)<f(xk)f({x}^{k+1})<f({x}^k)

    算法流程:

    给定起始点x0dom f,k=0x_0\in dom \ f,k=0,精度 ϵ>0\epsilon >0,

    1. 计算方向dk=f(xk)d^k=− ∇f({x}^k)
    2. 停止条件:如果 dk=0,(dk)2/2<ϵd^k=0,或者(d^k)^2/2<\epsilon则退出。
    3. 直线搜索:用精确性搜索或者非精确性搜索选择步长 αkα_k,用 αkα_k求出minα   f(xk+αkdk)\min_α ~ ~ ~ f(x^k + α_kd^k)
    4. 迭代: xk+1=xk+αkdk,k=k+1x^{k+1} = x^k + α_kd^k, k = k + 1. 转到步骤1。

    最速下降法的两个命题

    1\large\color{magenta}{\boxed{\color{brown}{命题1} }} 利用最速下降法搜索函数 f:R2Rf: \mathbb{R}^{2} \rightarrow \mathbb{R} 的极小值点, 迭代过程产生的序列为 {xk}k=0,\left\{x^{k}\right\}_{k=0}^{\infty}, 那么. xkxk1x^{k}-x^{k-1}xk2xk1x^{k-2}-x^{k-1} 正交对所有 k0k \geq 0 都成立。

    2\large\color{magenta}{\boxed{\color{brown}{命题2} }} 利用最速下降法搜索函数 f:RnRf: \mathbb{R}^{\mathrm{n}} \rightarrow \mathbb{R} 的极小值点, 迭代过程产生的序列为 {xk}k=0,\left\{x^{k}\right\}_{k=0}^{\infty}, 如果 f(xk)0,\nabla f\left(x^{k}\right) \neq 0, \quad 那么 f(xk+1)<f(xk)f\left(x^{k+1}\right)<f\left(x^{k}\right)

    命题1说明在迭代过程中,每产生一个新点, 对应的目标函数值都会下降。命题2说明了最速下降 法的下降特性:只要 f(xk)0,\nabla f\left(x^{k}\right) \neq 0, \quad 就有 f(xk+1)<f(xk)f\left(x^{k+1}\right)<f\left(x^{k}\right) 对于某个 k,k, 如果 f(xk)=0\nabla f\left(x^{k}\right)=0, 说明 xkx^{k} 满足局部极小点的一阶必要条件, 此时 xk+1=xk,x^{k+1}=x^{k}, 这可以作为停止规则的基础。

    证明命题一:

    因为xk+1=xk+αkdkx^{k+1} = x^k + α_kd^k ,则在xkx^k处的函数值为 f(xk)=f(xk1αk1f(xk1))f({x}^{k})=f(x^{k-1}-\alpha_{k-1}∇f({x}^{k-1}))
    df(xk)dα=df(xk1αk1f(xk1))dα=f(xk1αk1f(xk1))Tf(xk1)=f(xk)Tf(xk1)=0 \begin{aligned} &\frac{d f\left(x^k\right)}{d \alpha }=\frac{d f(x^{k-1}-\alpha_{k-1}\nabla f({x}^{k-1})) }{d \alpha}=\nabla f(x^{k-1}-\alpha_{k-1}\nabla f({x}^{k-1})) ^{T} \nabla f({x}^{k-1})\\ &=\nabla f({x}^{k})^{T} \nabla f({x}^{k-1})=0 \end{aligned}
    f(xk),f(xk1)\nabla f({x}^{k}), \nabla f({x}^{k-1}) 正交。

    下图是一个很直观的例子,在当前点,沿着不同的方向走,函数值的变化速度是不同的,但是在等高线的切线的垂直方向,是变化最快的。

    image-20201222102628502

    也就是说,我们得去找平行于该点梯度的方向,沿着这个方向(当为max问题)或者沿着这个方向的反方向(当为min问题)去更新当前位置。因此, 最优步长规则下的最速下降法在相邻两迭代点的搜索方向是正交的,也就是说迭代点列呈现锯齿形“zig-zag” ,故其收敛速度是很慢的。

    image-20201222104128675

    就像上图一样呈现锯齿形,一步一步,最终走到最优解对应的点。

    二次型函数的最速下降法

    二次型函数最小化问题:
    min   f(x)=12xTAxbTx(8) min~~~ f \left( x \right) = \frac{1}{2} x^TA x - b^T x \tag{8}
    如果对该函数求导,并令导数为零,我们得到
    f(x)=Axb=0(9) \begin{aligned} \nabla f \left( x \right) = A x - b = 0 \end{aligned} \tag{9}
    如何得到f(x)f(x)的最小值? 最优解很容易计算如下:x=A1bx^* =A^{-1} b

    有一个形象的方法,从任意一点x(0)x^{(0)}出发,每次沿着当前位置下降最快的方向走,也就是该点处的负梯度方向。从而得到一系列的解序列:x(1),x(2),x^{(1)},x^{(2),}…直到两次下降的差小于给定的误差限为止。

    由公式(9),每次迭代的梯度记为f(x(i))=Ax(i)bf^′(x^{(i)})=Ax^{(i)}−b,下面记误差(error)为e(i)=x(i)xe^{(i)}=x^{(i)}−x,负梯度方向为r(i)=bAx(i)r^{(i)}=b−Ax^{(i)}.

    于是有
    r(i)=f(x(i))x(i+1)=x(i)+α(i)r(i)(10) \begin{array}{lr} r^{(i)}=-f'(x^{(i)})\\ x^{(i+1)}=x^{(i)}+\alpha_{(i)}r^{(i)} \end{array}\tag{10}

    其中α(i)\alpha_{(i)}为第ii步沿着方向r(i)r^{(i)}的步长.

    如何选取步长α(i)\alpha_{(i)}呢?朴素的想法是选取的步长尽量要让f(xi+1)f(x^{i+1})的值最小,这样才能更快的到达f(x)f(x)的全局最小值。

    我们把f(xi+1)f(x^{i+1})看作含有α(i)\alpha_{(i)}的函数,要使得步长最合适,也就相当于导数=0:
    ddα(i)f(x(i+1))=0 \frac{d}{d\alpha_{(i)}}f(x^{(i+1)})=0
    根据链式法则和公式(10)有
    ddα(i)f(x(i+1))=f(x(i+1))Tddα(i)x(i+1)=r(i+1)Tr(i) % <![CDATA[ \begin{aligned} \frac{d}{d\alpha_{(i)}}f(x^{(i+1)})&=f'(x^{(i+1)})^T\frac{d}{d\alpha_{(i)}}x^{(i+1)}\\ &=-{r^{(i+1)}}^Tr^{(i)} \end{aligned} %]]>

    也就是说,r(i)r^{(i)}r(i+1)r^{(i+1)}正交
    r(i+1)Tr(i)=0(bAx(i+1))Tr(i)=0(bA(x(i)+α(i)r(i)))Tr(i)=0(bAx(i))Tr(i)α(i)(Ar(i))Tr(i)=0(bAx(i))Tr(i)=α(i)(Ar(i))Tr(i)α(i)=r(i)Tr(i)r(i)TAr(i). % <![CDATA[ \begin{aligned} {r^{(i+1)}}^Tr^{(i)}&=0\\ (b-Ax^{(i+1)})^Tr^{(i)}&=0\\ (b-A(x^{(i)}+\alpha_{(i)}r^{(i)}))^Tr^{(i)}&=0\\ (b-Ax^{(i)})^Tr^{(i)}-\alpha_{(i)}(Ar^{(i)})^Tr^{(i)}&=0\\ (b-Ax^{(i)})^Tr^{(i)}&=\alpha_{(i)}(Ar^{(i)})^Tr^{(i)}\\ \alpha_{(i)}&=\frac{{r^{(i)}}^Tr^{(i)}} {{r^{(i)}}^TAr^{(i)}}. \end{aligned} %]]>
    也就是说,每一步的步长都可以根据当前的负梯度方向r(i)r^{(i)}来确定.

    或者f(xi+1)=f(x(i)+α(i)r(i))f(x^{i+1})=f(x^{(i)}+\alpha_{(i)}r^{(i)}) ,AA对称,AT=AA^T=A.有
    ddα(i)f(x(i+1))=f(x(i+1))Tddα(i)x(i+1)={A(x(i)+α(i)r(i))b}Tr(i)=f(x(i))Tr(i)+α(i)(r(i))TAr(i) \begin{aligned} \frac{d}{d\alpha_{(i)}}f(x^{(i+1)})&=f'(x^{(i+1)})^T\frac{d}{d\alpha_{(i)}}x^{(i+1)}\\ &= \{A( x^{(i)}+\alpha_{(i)}r^{(i)}) - b\}^T r^{(i)}\\ &=\nabla f \left( x^{(i)} \right) ^T r^{(i)} + \alpha_{(i)}(r^{(i)})^T Ar^{(i)} \end{aligned}
    ddα(i)f(x(i+1))=0\frac{d}{d\alpha_{(i)}}f(x^{(i+1)})=0 ,得到
    α(i)=f(x(i))Tr(i)r(i)TAr(i). \alpha_{(i)}=\frac{-\nabla f \left( x^{(i)} \right) ^T r^{(i)}} {{r^{(i)}}^TAr^{(i)}}.
    总结一下,最速下降法就是:
    r(i)=bAx(i)α(i)=r(i)Tr(i)r(i)TAr(i)x(i+1)=x(i)+α(i)r(i). % <![CDATA[ \begin{aligned} r_{(i)}&=b-Ax_{(i)}\\ \alpha_{(i)}&=\frac{r_{(i)}^Tr_{(i)}}{r_{(i)}^TAr_{(i)}}\\ x_{(i+1)}&=x_{(i)}+\alpha_{(i)}r_{(i)}. \end{aligned} %]]>
    这样迭代下去,直到达到事先给定的最小误差限制ϵϵ为止

    当然,有的时候,出于减小复杂度的考虑,我们会换用这种手段来求r(i)r^{(i)}
    r(i+1)=r(i)α(i)Ar(i) r^{(i+1)}=r^{(i)}-\alpha_{(i)}Ar^{(i)}

    这个公式是在x(i+1)=x(i)+α(i)r(i)x^{(i+1)}=x^{(i)}+\alpha_{(i)}r^{(i)}的两边左乘A−A再加上b得到的。

    这样每次迭代过程我们只需要算一次矩阵乘法,可以减少运算。

    收敛速度与收敛性

    • 线性收敛:

    f(xk+1)f(x)f(xk)f(x)δ \frac{f\left(x^{k+1}\right)-f\left(x^{*}\right)}{f\left(x^{k}\right)-f\left(x^{*}\right)} \leq \delta
    其中δ\delta被称为收敛常数。我们希望它更小,而不是更大。

    1\large\color{magenta}{\boxed{\color{brown}{定理1} }}f(x)f(x) 是连续可微的实函数, 解集合Ω={xˉf(xˉ)=0},\Omega=\{\bar{x} \mid \nabla f(\bar{x})=0\}, 最速下降法产生的序列 {x(k)}\left\{x^{(k)}\right\} 含于
    某个紧集, 则序列 {x(k)}\left\{x^{(k)}\right\} 的每个聚点 x^Ω.\hat{x} \in \Omega .

    证明:最速下降算法A可表示为合成映射
    A=MD \mathrm{A}=\mathrm{MD}
    其中 D(x)=(x,f(x)),\mathrm{D}(x)=(x,-\nabla f(x)),EnEn×EnE^{\mathrm{n}} \rightarrow E^{\mathrm{n}} \times E^{\text {n}}的映射.
    每给定一点 xx,经算法D作用,得到点 xx 和在 xx 处的 负梯度(从 xx 出发的方向 dd ).算法M是 En×EnEnE^{\mathrm{n}} \times E^{\mathrm{n}} \rightarrow E^{\mathrm{n}}

    映射.每给定一点x及方向 d=f(x)d=-\nabla f(x), 经M作用,即 一维搜索,得到一个新点,在这一点,与前面的迭代 点相比,具有较小的目标函数值,当 f(x)0\nabla f(x) \neq 0 时,M是闭映射.由于 f(x)f(x) 是连续可微实函数, 故D连续,A在 x(f(x)0)x(\nabla f(x) \neq 0) 处是闭的.

    其次,当 xΩx \notin \Omega 时, d=f(x)0,d=-\nabla f(x) \neq 0,f(x)Td<0,\nabla f(x)^{\mathrm{T}} \mathrm{d}<0, 因此对于 yA(x),y \in \mathrm{A}(x),f(y)<f(x),f(y)<f(x), 由此知 f(x)f(x) 是关于A和 Ω\Omega 的下降函数,
    最后,按假设, {x(k)}\left\{x^{(k)}\right\} 含于紧集,因此算法收签。

    2\large\color{magenta}{\boxed{\color{brown}{定理2} }} 当精确线搜索的最速下降法应用于凸二次函数时,有
    xk+1x2(λnλ1λn+λ1)2xkx2 \left\|x^{k+1}-x^{*}\right\|^{2} \leq\left(\frac{\lambda_{n}-\lambda_{1}}{\lambda_{n}+\lambda_{1}}\right)^{2}\left\|x^{k}-x^{*}\right\|^{2}
    其中 0λ1λn0 \leq \lambda_{1} \leq \cdots \leq \lambda_{n}AA. 特征值。

    3\large\color{magenta}{\boxed{\color{brown}{定理3} }} 假设 f:RnRf: R^{n} \rightarrow R 是两次连续可微的,采用精确直线搜索的最速下降法生成的迭代序列 {x(k)}\left\{x^{(k)}\right\}收敛于点xx^{*},其中Hessian矩阵2f(x)\nabla^{2} f\left(x^{*}\right)是正定的。然后,将直线搜索最速下降法应用于凸二次函数,有
    f(xk+1)f(x)(λnλ1λn+λ1)2[f(xk)f(x)] f\left(x^{k+1}\right)-f\left(x^{*}\right) \leq\left(\frac{\lambda_{n}-\lambda_{1}}{\lambda_{n}+\lambda_{1}}\right)^{2} \left[f\left(x^{k}\right)-f\left(x^{*}\right)\right]
    其中 0λ1λn0 \leq \lambda_{1} \leq \cdots \leq \lambda_{n}2f(x)\nabla^{2} f\left(x^{*}\right) 特征值。

    上面讲的是目标函数序列 {f(x(k))}\left\{f\left(x^{(k)}\right)\right\} 以不大于 (λnλ1λn+λ1)2\left(\frac{\lambda_{n}-\lambda_{1}}{\lambda_{n}+\lambda_{1}}\right)^{2} 的收签比线性的收签于 f(x)f(x^{*})

    在上述定理中,若令r=λn/λ1r=\lambda_{n}/\lambda_{1},则
    (λnλ1λn+λ1)2=(r1r+1)2<1 \left(\frac{\lambda_{n}-\lambda_{1}}{\lambda_{n}+\lambda_{1}}\right)^{2}=\left(\frac{r-1}{r+1}\right)^{2}<1
    rr 是对称正定矩阵 2f(x)\nabla^{2} f(x) 的条件数.

    :\Large\color{violet}{注:} 一个矩阵最大特征值与最小特征值之比称为该矩阵的条件数。条件数在矩阵A的理论和计算中起着极其重要的作用。

    非二次函数呢?大多数函数在最优解的邻域内表现为近二次函数。非二次情形的分析非常复杂;幸运的是,通过对二次情况的分析,得到了关键的直觉。

    最速下降法的缺点

    需要指出的是,某点的负梯度方向,通常只是在该点附近才具有这种最速下降的性质。

    在一般情况下,当用最速下降法寻找极小点时,其搜索路径呈直角锯齿状(如下图), 在开头 几步,目标函数下降较快;但在接近极小点时,收敛速度长久不理想了。特别适当目标函数的等值 线为比较扁平的椭圆时,收敛就更慢了。

    img

    因此,在实用中常用最速下降法和其他方法联合应用,在前期使用最速下降法,而在接近极小值点时,可改用收敛较快的其他方法。

    最速下降法的本质

    梯度法直观地认为,负梯度方向就是目标函数值下降最快的方向,即 Δx=f(x)\Delta x = - \nabla f(x) ,所以每次将变量沿着负梯度方向移动单位步长,目标函数值就会逐渐收敛。方法简单,但是收敛速度非常大程度地依赖于其Hessian矩阵的条件数(Condition Number)。

    而最速下降法的初衷,是找泰勒一阶展开式 f(x+v)f(x)+f(x)Tdf(x+v)\approx f(x)+\nabla f(x)^Td 中,能使方向导数(Directional Derivative)最小的dd,方法本身的定义也比梯度法要复杂。

    定义标准化最速下降方向Δxnsd\Delta x_{nsd}(Normalized Steepest Descent Direction),即在单位范数(Unit Norm)步长内能够使目标函数下降最多的方向:Δxnsd=argmin{f(x)Td   d1}\Delta x_{nsd}=argmin\left\{ \nabla f(x)^Td \lvert~~~\lVert d \rVert\leq1 \right\}。也可以表示为非标准化的形式,即 Δxsd=f(x)Δxnsd\Delta x_{sd}=\lVert \nabla f(x)\rVert_*\Delta x_{nsd} ,其中 .\lVert .\rVert_*为对偶范数。

    最速下降法与梯度下降法的差异

    由上式可得,最速下降法的下降方向受到范数的限制,如果这里的范数取欧式范数(Euclidean Norm),则最速下降法就可以简单地理解为梯度法,即 Δxsd=f(x)\Delta x_{sd} = - \nabla f(x) ,也可以说梯度法是最速下降法使用欧式范数的特殊情况。但如果这里取其它范数,因为要满足“下降方向上移动的单位步长在范数集合内”这一条件,则会得到不同的结果,比如取向量1-范数( 1norm\ell_1-norm )或者矩阵2-范数(Quadratic Norm),他们的单位球(Unit Ball)分别是正菱形体和椭圆体,标准下降方向就如图1所示。

    欧式范数不一定是最好的

    原因其实很简单,因为使用欧式范数的最速下降法(也就是梯度下降法)得到下降方向并非永远都是下降最快的方向。因为梯度是变化的,而梯度下降在一次迭代的过程中假设梯度是固定不变的,所谓的梯度方向只是起始点(xkx_k)的梯度方向,并不一定是起始点和终点之间其他点的梯度方向(axk+(1a)xk+1,0<a<=1ax_k+(1−a)x_k+1,0<a<=1),所以梯度方向不一定是下降最快的方向(如最速下降法的迭代过程(矩阵2-范数)所示),所以为了得到更快的下降方向,我们有时并不适用欧式范数。

    当采用矩阵2-范数 zP=(zTPz)1/2=P1/2z2\lVert z \rVert P = (z^TPz)^{1/2}=\lVert P^{1/2}z\rVert_2 时,最速下降方向为关于矩阵PΔxsd=P1f(x)\Delta x_{sd}=-P^{-1}\nabla f(x),从下文的图中可以看出,在点 x 处的标准最速下降方向 Δxnsd\Delta x_{nsd} 在满足在椭圆体中的条件下,尽可能地在 f(x)- \nabla f(x) 方向上延伸。Boyd 在书中还给了一种坐标变换的解释,即矩阵2-范数的最速下降法也可以看作是,梯度法在坐标进行了 xˉ=P1/2x\bar{x}=P^{1/2}x 变换之后的应用。当采用向量1-范数时,Δxnsd=sign(f(x)/x)ei\Delta x_{nsd}=-sign({\partial f(x)}/{\partial x})e_i ,其中 eie_i 是标准基向量,所以当选取向量1-范数时,沿着坐标轴下降是最快的方向。

    负梯度方向与矩阵2-范数下的标准最速下降方向
    2 负梯度方向与矩阵2-范数下的标准最速下降方向

    负梯度方向与向量1-范数下的标准最速下降方向
    1 负梯度方向与向量1-范数下的标准最速下降方向

    最速下降法的迭代过程(矩阵2-范数)
    2 最速下降法的迭代过程(矩阵2-范数)

    收敛速度影响因素

    我们知道梯度是函数对每个因子求偏导得到的列向量,表示着函数的变化趋势,
    f(x)=[fx1,fx2,,fxn]T\nabla_{\boldsymbol{}}f(x) \overset{\underset{\mathrm{}}{}}{=} \left[ \frac{\partial f}{\partial x_1}, \frac{\partial f}{\partial x_2},\cdots,\frac{\partial f }{\partial x_n} \right]^T,向量中元素的相对大小决定了梯度的方向。我们前面提到,梯度下降的方向不是最快的方向的原因正是由于梯度方向的变化,那的梯度的方向变化由什么来决定呢?
    提到梯度的变化,很自然的想到了函数的二阶导数,对于多变量函数,也就是函数的Hessian矩阵。
    H=[2fx122fx1x22fx1xn2fx2x12fx222fx2xn2fxnx12fxnx22fxn2] {\displaystyle \mathbf {H} ={\begin{bmatrix}{\frac {\partial ^{2}f}{\partial x_{1}^{2}}}&{\frac {\partial ^{2}f}{\partial x_{1}\,\partial x_{2}}}&\cdots &{\frac {\partial ^{2}f}{\partial x_{1}\,\partial x_{n}}}\\\\{\frac {\partial ^{2}f}{\partial x_{2}\,\partial x_{1}}}&{\frac {\partial ^{2}f}{\partial x_{2}^{2}}}&\cdots &{\frac {\partial ^{2}f}{\partial x_{2}\,\partial x_{n}}}\\\\\vdots &\vdots &\ddots &\vdots \\\\{\frac {\partial ^{2}f}{\partial x_{n}\,\partial x_{1}}}&{\frac {\partial ^{2}f}{\partial x_{n}\,\partial x_{2}}}&\cdots &{\frac {\partial ^{2}f}{\partial x_{n}^{2}}}\end{bmatrix}}\,} \\
    这里首先讨论一个简单的情况,就是f(x)的各个变量相互独立,此时Hessian矩阵是一个对角阵,
    2fx1x12fx2x22fxnxn \left|\begin{array}{cccc} \frac{\partial^{2} f}{\partial x_{1} \partial x_{1}} & & & \\ & \frac{\partial^{2} f}{\partial x_{2} \partial x_{2}} & & \\ & & \ddots & \\ & & & \frac{\partial^{2} f}{\partial x_{n} \partial x_{n}} \end{array}\right|

    • 如果 2fxixii=1,2n\frac{\partial^{2} f}{\partial x_{i} \partial x_{i}} i=1,2 \ldots n 相差不多, 也就是 f(x)f(x) 梯度在各个方向的变化基本一致,那么梯度方向基本不会发生变化,此时梯度下降法会得到很好的结果,
    • 如果 2fxixii=1,2n\frac{\partial^{2} f}{\partial x_{i} \partial x_{i}} i=1,2 \ldots n 相差很大, 那么梯 亨方向变化就会较大, 当然梯度下降的方向便不再是最好的方向。

    如果,Hessian矩阵不是对角阵,那么我们需要求出矩阵的特征值,最大特征值和最小的特征值之比(这个值叫做condition number)如果不大,则梯度下降法会有很好的效果。

    范数的选取

    范数的选取对于最速下降法的收敛效率有很大的影响,上面提到的选取矩阵2-范数的情况,在进行 xˉ=P1/2x\bar{x}=P^{1/2}x 变换后得到比梯度法要小的条件数,有更高的效率。另外,在矩阵2-范数的情况下,选取能够使计算效率提高的矩阵P 也是重要的一点。Hessian矩阵就是一个很好的选择,当最速下降法在点 x 处,选取由Hessian矩阵 2f(x)\nabla^2f(x) 定义的矩阵2-范数时,就是另一个著名的无约束极值求解方法 - 牛顿法(Newton’s Method)了,牛顿法虽然计算较为复杂,但有比梯度法更高的收敛效率。

    综上,从概念的意义上来讲, 负梯度方向不一定总是某点上下降最快的方法,因此这两个方法在当不满足负梯度方向为最快下降方向的条件时,是不同的;从数学的意义上, 当范数为欧式范数时,两种方法可以得到相同的下降过程,反之,当选取其它类型的范数时,会得到不同的下降方向;从坐标的角度来讲,欧式范数对应的是欧式距离,也就是两点的直线距离,但是当采用矩阵2-范数时,可以看作是坐标发生了变化,因此,其对应的步长也就不是根据欧式距离进行计算的了。

    例子

    1\Large\color{violet}{例1}

    用最速下降法求解
    minf(x)=(x11)2+(x21)2 \min f(x)=\left(x_{1}-1\right)^{2}+\left(x_{2}-1\right)^{2}
    开始点x0=(0,0)T,ε=0.01x^{0}=(0,0)^{T}, \varepsilon=0.01

    解决方案:
    f(x)=(2x12,2x22)T,f(x0)=(2,2)T,f(x0)>ε\nabla f(x)=\left(2 x_{1}-2,2 x_{2}-2\right)^{T}, \nabla f\left(x^{0}\right)=(-2,-2)^{T},\left\|\nabla f\left(x^{0}\right)\right\|>\varepsilon
    所以,我们有
    d0=f(x0)=(2,2)T,x0+αd0=(2α,2α)Tφ(α)=f(x0+αd0)=2(2α1)2,φ(α)=8(2α1)=0α0=12,x1=x0+α0d0=(1,1)T,f(x1)=0 \begin{array}{c} d^{0}=-\nabla f\left(x^{0}\right)=(2,2)^{T}, x^{0}+\alpha d^{0}=(2 \alpha, 2 \alpha)^{T} \\ \varphi(\alpha)=f\left(x^{0}+\alpha d^{0}\right)=2(2 \alpha-1)^{2}, \varphi^{\prime}(\alpha)=8(2 \alpha-1)=0 \\ \alpha_{0}=\frac{1}{2}, x^{1}=x^{0}+\alpha_{0} d^{0}=(1,1)^{T}, \nabla f\left(x^{1}\right)=0 \end{array}
    所以x1x^{1}是局部最小值.

    2\Large\color{violet}{例2}
    minf(x)=2x12+x22 min f(x)=2x_1^2+x_2^2

    初始化 x(1)=(1,1)Tx^{(1)}=(1,1)^T , ε=110=0.1\varepsilon=\frac{1}{10}=0.1

    第一次迭代:
    f(x)=4x1+2x2=[4x12x2]d(1)=f(x(1))=[42]d=16+4=25>110=ε \nabla f(x)=4x_1+2x_2=\begin{bmatrix} 4x_1 \\ 2x_{2} \end{bmatrix}\\ d^{(1)}=\nabla f(x^{(1)})=\begin{bmatrix}-4\\-2\end{bmatrix}\\ ||d||=\sqrt{16+4}=2\sqrt{5}>\frac{1}{10}=\varepsilon

    x(1)=(1,1)Tx^{(1)}=(1,1)^T 出发,沿方向 d(1)d^{(1)} 进行一维搜索,求步长 λ1\lambda_1 ,即
    minλ>=0φ(λ)=f(x(1)+λd(1))x(1)+λd(1)=[11]+λ[42]=[14λ12λ] \min_{\lambda>=0}\varphi(\lambda)=f(x^{(1)}+\lambda d^{(1)})\\ x^{(1)}+\lambda d^{(1)}=\begin{bmatrix}1\\1\end{bmatrix}+\lambda\begin{bmatrix}-4\\-2\end{bmatrix}=\begin{bmatrix}1-4\lambda\\1-2\lambda\end{bmatrix}

    φ(λ)=2(14λ)2+(12λ)2φ(λ)=16(14λ)4(12λ)=0λ1=518 \varphi(\lambda)=2(1-4\lambda)^2+(1-2\lambda)^2\\ \varphi^{'}(\lambda)=-16(1-4\lambda)-4(1-2\lambda)=0\\ \lambda_1=\frac{5}{18}

    更新迭代点:
    x(2)=x(1)+λd(1)=[1949] x^{(2)}=x^{(1)}+\lambda d^{(1)}=\begin{bmatrix}-\frac{1}{9}\\-\frac{4}{9}\end{bmatrix}
    第二次迭代:
    d(2)=f(x(2))=[4989]d=1681+6181=779>110=ε d^{(2)}=-\nabla f(x^{(2)})=\begin{bmatrix}-\frac{4}{9}\\\frac{8}{9}\end{bmatrix}\\ ||d||=\sqrt{\frac{16}{81}+\frac{61}{81}}=\frac{\sqrt{77}}{9}>\frac{1}{10}=\varepsilon\\
    x(2)=(19,49)Tx^{(2)}=(-\frac{1}{9},\frac{4}{9})^T 出发,沿方向 d(2)d^{(2)} 进行一维搜索,求步长 λ2\lambda_2
    minλ>=0φ(λ)=f(x(2)+λd(2))x(2)+λd(2)=[1949]+λ[4989]=[19λ4949+λ89]φ(λ)=2(19λ49)2+(49+λ89)2φ(λ)=169(19λ49)+169(49+λ89)=0 \min_{\lambda>=0}\varphi(\lambda)=f(x^{(2)}+\lambda d^{(2)})\\ x^{(2)}+\lambda d^{(2)}=\begin{bmatrix}-\frac{1}{9}\\\frac{4}{9}\end{bmatrix}+\lambda \begin{bmatrix}-\frac{4}{9}\\\frac{8}{9}\end{bmatrix}=\begin{bmatrix}-\frac{1}{9}-\lambda \frac{4}{9}\\\frac{4}{9}+\lambda \frac{8}{9}\end{bmatrix}\\ \varphi(\lambda)=2(-\frac{1}{9}-\lambda\frac{4}{9})^2+(\frac{4}{9}+\lambda\frac{8}{9})^2\\ \varphi^{'}(\lambda)=-\frac{16}{9}(-\frac{1}{9}-\lambda\frac{4}{9})+\frac{16}{9}(\frac{4}{9}+\lambda\frac{8}{9})=0\\
    解得: λ2=2792\lambda_2=-\frac{27}{92}
    x(3)=x(2)+λd(2)=[65207130207] x^{(3)}=x^{(2)}+\lambda d^{(2)}=\begin{bmatrix}-\frac{65}{207}\\\frac{130}{207}\end{bmatrix}
    第三次迭代:
    d(3)=f(x(3))=[260207260207] d^{(3)}=-\nabla f(x^{(3)})=\begin{bmatrix}\frac{260}{207}\\-\frac{260}{207}\end{bmatrix}

    d=2260207=1.776>110 ||d||=\sqrt{2}\frac{260}{207}=1.776>\frac{1}{10}

    最终结果展示:

    image-20201224212528959

    image-20201224212538248

    3\Large\color{violet}{例3}

    典型的行为,考虑下面的问题
    minf(x)=5x12+x22+4x1x214x16x2+20 \min f(x)=5 x_{1}^{2}+x_{2}^{2}+4 x_{1} x_{2}-14 x_{1}-6 x_{2}+20
    这个函数在x=(1,1)Tf(x)=10x^{*}=(1,1)^{T}, f\left(x^{*}\right)=10处有其最优解。

    在最速下降法的第一步中,我们需要计算
    dk=f(xk)=(10x1k4x2k+142x2k4x1k+6)=(d1kd2k) d^{k}=-\nabla f\left(x^{k}\right)=\left(\begin{array}{c} -10 x_{1}^{k}-4 x_{2}^{k}+14 \\ -2 x_{2}^{k}-4 x_{1}^{k}+6 \end{array}\right)=\left(\begin{array}{c} d_{1}^{k} \\ d_{2}^{k} \end{array}\right)
    在第二步,我们需要解
    αk=argminφ(α)=f(xk+αdk) \alpha_{k}=\operatorname{argmin} \quad \varphi(\alpha)=f\left(x^{k}+\alpha d^{k}\right)
    在这个例子中,我们将能够推导出αk\alpha_{k}的解析表达式。请注意,
    φ(α)=f(xk+αdk)=5(x1k+αd1k)2+(x2k+αd2k)2+4(x1k+αd1k)(x2k+αd2k)14(x1k+αd1k)6(x2k+αd2k)+20 \begin{aligned} \varphi(\alpha)=& f\left(x^{k}+\alpha d^{k}\right) \\ =& 5\left(x_{1}^{k}+\alpha d_{1}^{k}\right)^{2}+\left(x_{2}^{k}+\alpha d_{2}^{k}\right)^{2}+4\left(x_{1}^{k}+\alpha d_{1}^{k}\right)\left(x_{2}^{k}+\alpha d_{2}^{k}\right)-\\ &-14\left(x_{1}^{k}+\alpha d_{1}^{k}\right)-6\left(x_{2}^{k}+\alpha d_{2}^{k}\right)+20 \end{aligned}
    通过设置φ(α)=0\varphi^{\prime}(\alpha)=0,得到
    αk=(d1k)2+(d2k)22(5(d1k)2+(d2k)2+4d1kd2k) \alpha_{k}=\frac{\left(d_{1}^{k}\right)^{2}+\left(d_{2}^{k}\right)^{2}}{2\left(5\left(d_{1}^{k}\right)^{2}+\left(d_{2}^{k}\right)^{2}+4 d_{1}^{k} d_{2}^{k}\right)}
    使用最速下降法最小化f(x)f(x)x1=(0,10)Tx^{1}=(0,10)^{T} 开始,并使用容许误差ε=106\varepsilon=10^{-6},我们计算得表1和图1所示的迭代数:

    image-20201222114507066
    1 表1 迭代示例

    image-20201222114542898

    1 图1 最陡下降算法的行为

    对于凸二次函数 f(x)=12xTAxcTx,f(x)=\frac{1}{2} x^{T} Ax-c^{T} x, 函数值的轮廓将被塑造成椭球形,梯度向量f(x)\nabla f(x)在任意点xx将垂直于通过xx的等高线,见图2.2 .

    image-20201222115133952

    2 图2 凸二次函数的轮廓是椭球。

    4\Large\color{violet}{例4}

    • 花饰线迹

    考虑下面的问题
    minf(x)=12xTQxcTx+10 \min f(x)=\frac{1}{2} x^{T} Q x-c^{T} x+10
    其中
    Q=(20552),c=(146) Q=\left(\begin{array}{cc} 20 & 5 \\ 5 & 2 \end{array}\right), c=\left(\begin{array}{c} 14 \\ 6 \end{array}\right)
    对于这个问题,λnλ1=30.234\frac{\lambda_{n}}{\lambda_{1}}=30.234,则最速下降算法的线性收敛速率δ\delta有上界:
    δ=(λnλ1λn+λ1)2=0.8760 \delta=\left(\frac{\lambda_{n}-\lambda_{1}}{\lambda_{n}+\lambda_{1}}\right)^{2}=0.8760
    如果我们应用最速下降算法从x1=(40100)x^{1}=(40,-100)开始最小化f(x)f(x),我们得到的迭代值如表3所示,如图3所示。

    image-20201222115730344

    3  Hemstitching 表3 ~~Hem-stitching 迭代值

    image-20201222115625814

    3  Hemstitch<