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

最速下降法收敛速度快还是慢_最速下降法是全局收敛算法吗\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)


相关推荐

  • phpstorm激活码2022linux【最新永久激活】2022.02.22

    (phpstorm激活码2022linux)本文适用于JetBrains家族所有ide,包括IntelliJidea,phpstorm,webstorm,pycharm,datagrip等。IntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,下面是详细链接哦~https://javaforall.cn/100143.html…

  • 什么是重载什么是覆盖_java覆盖和重载的关系

    什么是重载什么是覆盖_java覆盖和重载的关系java中的方法重载发生在同一个类里面两个或者多个方法的方法名相同但是参数不同的情况。与此相对,方法覆盖是说子类重新定义了父类的方法。方法覆盖必须有相同的方法名,参数列表和返回类型。覆盖者可能不会限

  • android开发之GPS定位详解

    一、LocationManagerLocationMangager,位置管理器。要想操作定位相关设备,必须先定义个LocationManager。我们可以通过如下代码创建LocationManger对象。LocationManger locationManager=(LocationManager)this.getSystemService(Context.LOCATION_SERVICE

  • Linux运维面试题2

    Linux运维面试题21.apache怎么实现负载均衡答案:多台机器跑apache,然后其中一台跑nginx,让nginx去代理多台apache实现负载均衡2.一台Linux服务器负载高,连接慢,怎么查看答案:先用w看负载多少,用top看哪个进程占用cpu高,同时用top按M看哪个进程占用内存多,用iotop看哪个进程读写频发,用sar命令或者nload命令查看网卡流量,是否跑满带宽3.现有A文件,编写shell…

  • poj1195(二维树状数组)

    poj1195(二维树状数组)

  • 钱柜 自助餐_常熟钱柜KTV是不是有自助餐

    钱柜 自助餐_常熟钱柜KTV是不是有自助餐今天去白石桥钱柜K歌,昔日的钱柜看来确实已老也。之前Javor就说钱柜条件越来越差,亲身体会果然不是一般的差。包房的设施很陈旧,点歌系统土到火星,什么按歌星姓名字数点歌,完全不具操作性。音响还勉强,电

发表回复

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

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