最速下降法收敛速度快还是慢_最速下降法是全局收敛算法吗

最速下降法收敛速度快还是慢_最速下降法是全局收敛算法吗\qquad已知设步长为α\alphaα,下降方向为ddd,f(xk+αd)f(x_{k}+\alphad)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}+\alphad)=f(x_{k})+\alphag_{k}^{T}d+O(||\…

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全家桶1年46,售后保障稳定

摘自《数值最优化方法》
\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时,收敛速度接近超线性收敛,条件数越大,收敛速度越慢

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/234469.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • html制作网页案例代码 大学生_完整html网页代码

    html制作网页案例代码 大学生_完整html网页代码+前言完成一个网页的制作其实本质上是很简单的,本实例适合于初学HTML的同学。该实例里面有设置了css的样式设置,采用了有div+css布局。+主题《登录·枫叶》+图摘+目录+代码

  • 程序员的最炫民族风[通俗易懂]

    程序员的最炫民族风[通俗易懂]最近公司其它项目组加班比较多,自然bug也是海海的,同事有感而发,写下了这首程序员的最炫民族风苍茫的Bug是我的爱绵绵的Bug票起出来什么样的Bug是最呀最难改什么样的变更才是最开怀长长的代码写出来前台的Check到底改不改火辣辣的RedMine是我们的期待改成解决状态才是最自在我们要改就要改得最痛快你是我心中最难的Bug让我用心把你改出来(

  • 计算机中为什么会用补码运算符号_负数求补码

    计算机中为什么会用补码运算符号_负数求补码总所周知,计算机内部的所有数都是以二进制的形式存在的。而二进制在计算机里又有多种编码方式——原码、反码、补码等。而在这些编码方式里面用得最多的不是最简单、最直接的原码而是补码。这是为什么呢?想搞懂这个问题首先得明白什么是原码、反码以及补码,如果你对他们还不太了解,那就先看看我另一篇博客——原码、反码、补码其实很简单。如果你对他们已经很熟悉,那么我们继续往下看。A、B、C三种相似的东西,

  • hashmap or array

    hashmap or array

  • 判断一个数是否为素数c#(判断一个数是否为素数的算法)

    C++判断一个数是否为素数算法C++判断一个数是否为素数算法完整源码(定义,实现,main函数测试)C++判断一个数是否为素数算法完整源码(定义,实现,main函数测试)#include<cassert>#include<iostream>template<typenameT>boolis_prime(Tnum){boolresult=true;if(num<=1){return0;

  • 使用BoundsChecker「建议收藏」

     BoundsChecker是一个Run-Time错误检测工具,它主要定位程序在运行时期发生的各种错误。              BoundsChecker能检测的错误包括:3sNews.Net——3S社区&资讯平台tbU^N@i7pwMVBe    1)指针操作和内存、资源泄露错误,比如:内存泄露;资源泄露;对指针变量的错误操作。   

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号