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

摘自《数值最优化方法》 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​) αgkT​d O(∣∣αd∣∣2)为使函数值下降，下降方向满足 g k T d &lt; 0 g_{k}^{T}d&lt;0 gkT​d<0 qquad 收敛性和收敛速度 收敛性 算法产生的点阵 { x k } {x_{k}} { xk​}在某种范数 ∣ ∣ ⋅ ∣ ∣ ||cdot|| ∣∣⋅∣∣意义下满足 l i m k → ∞ ∣ ∣ x k − x ∗ ∣ ∣ = 0 mathop{lim}limits_{ktoinfty}||x_{k}-x^{*}||=0 k→∞lim​∣∣xk​−x∗∣∣=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_{ktoinfty}frac{||x_{k 1}-x^{*}||}{||x_{k}-x^{*}||}=a k→∞lim​∣∣xk​−x∗∣∣∣∣xk 1​−x∗∣∣​=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_{ktoinfty}frac{||x_{k 1}-x^{*}||}{||x_{k}-x^{*}||^{2}}=a k→∞lim​∣∣xk​−x∗∣∣2∣∣xk 1​−x∗∣∣​=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 gkT​d<0，为使 ∣ g k d ∣ |g_{k}d| ∣gk​d∣达到最大值，则由 C a u c h y − S c h w a r z Cauchy-Schwarz Cauchy−Schwarz不等式 ∣ g k T d ∣ ≤ ∣ ∣ g k ∣ ∣ ∣ ∣ d ∣ ∣ |g_{k}^{T}d|leq||g_{k}||||d|| ∣gkT​d∣≤∣∣gk​∣∣∣∣d∣∣知当且仅当 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 gkT​d达到最小。考虑在 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 Ginmathbb{R}^{ntimes n} G∈Rn×n对称正定， u , v ∈ R n u,vinmathbb{R}^{n} u,v∈Rn则 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} ∣∣u∣∣G2​定义为 ∣ ∣ u ∣ ∣ G 2 = u T G u ||u||_{G}^{2}=u^{T}Gu ∣∣u∣∣G2​=uTGu G G G度量下的 C a u c h y − S c h w a r z Cauchy-Schwarz Cauchy−Schwarz不等式 ∣ u T G u ∣ ≤ ∣ ∣ u ∣ ∣ G ∣ ∣ v ∣ ∣ G |u^{T}Gu|leq||u||_{G}||v||_{G} ∣uTGu∣≤∣∣u∣∣G​∣∣v∣∣G​成立，当且仅当 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 } xinmathbb{R}^{n} verb|| {0} x∈Rn{ 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)}gefrac{4lambda_{max}lambda_{min}}{ (lambda_{max} lambda_{min})^{2}} (xTGx)(xTG−1x)(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)=21​xTGx 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}=argmathop{min}limits_{alpha&gt;0}f(x_{k}-alpha g_{k}) αmin​=argα>0min​f(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​) 21​gkT​Ggk​α2 gkT​(Gxk​ b)α=f(xk​)−gkT​gk​α 21​gkT​Ggk​α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​=gkT​Ggk​gkT​gk​​ 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​)−21​gkT​Ggk​(gkT​gk​)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∗)=−21​bTG−1b得到 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∗)​=1−xkT​Gxk​ 2bTxk​ bTG−1bgkT​Ggk​(gkT​gk​)2​​=1−(Gxk​ b)TG−1(Gxk​ b)gkT​Ggk​(gkT​gk​)2​​=1−(gkT​Ggk​)(gkT​G−1gk​)(gkT​gk​)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})} ∣∣xk​−x∗∣∣G2​∣∣xk 1​−x∗∣∣G2​​=1−(gkT​Ggk​)(gkT​G−1gk​)(gkT​gk​)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} ∣∣xk​−x∗∣∣G2​∣∣xk 1​−x∗∣∣G2​​≤(λ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∣∣ ∣∣G∣∣−1 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}} ∣∣G∣∣2​∣∣G−1∣∣2​=λ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...