大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新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(∣∣αd∣∣2)为使函数值下降，下降方向满足
g k T d < 0 g_{k}^{T}d<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 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_{k\to\infty}\frac{||x_{k+1}-x^{*}||}{||x_{k}-x^{*}||}=a k→∞lim∣∣xk−x∗∣∣∣∣xk+1−x∗∣∣=a \qquad 当 0 < a < 1 0<a<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 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 < 0 g_{k}^{T}d<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 Cauchy−Schwarz不等式
∣ g k T d ∣ ≤ ∣ ∣ g k ∣ ∣ ∣ ∣ d ∣ ∣ |g_{k}^{T}d|\leq||g_{k}||||d|| ∣gkTd∣≤∣∣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 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} G∈Rn×n对称正定， u , v ∈ R n u,v\in\mathbb{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 } x\in\mathbb{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)}\ge\frac{4\lambda_{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)=21xTGx+bTx由负梯度方向为 d k = − g k d_{k}=-g_{k} dk=−gk则求解最速下降法步长为
α m i n = a r g m i n α > 0 f ( x k − α g k ) \alpha_{min}=arg\mathop{min}\limits_{\alpha>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∗)=−21bTG−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−xkTGxk+2bTxk+bTG−1bgkTGgk(gkTgk)2=1−(Gxk+b)TG−1(Gxk+b)gkTGgk(gkTgk)2=1−(gkTGgk)(gkTG−1gk)(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})} ∣∣xk−x∗∣∣G2∣∣xk+1−x∗∣∣G2=1−(gkTGgk)(gkTG−1gk)(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} ∣∣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时，收敛速度接近超线性收敛，条件数越大，收敛速度越慢。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/234469.html原文链接：https://javaforall.net
