我的网站

共轭梯度法

2022-01-26 02:33分类:企业融资 阅读:

概述

共轭梯度法是用来解决无收敛凸二次规划题目的一栽手法。其思路为,对于一个目标函数 \mathop\min_xf(x) ,找到一组偏向向量 d_1,\ldots,d_n\in\mathbb{R}^n ,顺序按此偏向组中的偏向对迭代点 x_i\in\mathbb{R}^n 进动更新,对每一个更新偏向 d_i ,找到合法的步长 \lambda_i ,使得 f(x) 在该偏向上取得最小值。请求是,在每一个新的更新偏向 d_k 对迭代点 x_k 进动更新时,不会影响在之前偏向 d_j(j\le k-1) 上的更新凶果,即 x_{k+1} 不光使 f(x)d_k 偏向上取得最小值,且在 d_j(j\le k-1) 偏向上均保持最小值。伪如能找到云云一组偏向 d_1,\ldots,d_n\in\mathbb{R}^n ,那么简略保证在迭代 n 次之后找到 f(x) 的全局极小点。

基本概念A.无收敛凸二次规划题目

1、题目描述

云云的题目称为无收敛凸二次规划题目: \mathop{min}_xf(x)=\frac{1}{2}x^TQx+q^Tx ,其中 Q\in\mathbb{R}^{n\times n} 为对称正定矩阵, q\in \mathbb{R}^n

2、为何称为“凸”

Q 为正定矩阵的条件使得 f(x) 为凸函数,这涉及到凸函数辨识的二阶充要条件:设 f(x):S\rightarrow\mathbb{R} 是定义在 n 维向量空间 \mathbb{R}^n 内的凸集 S 上的函数,且简略二次微分。当且仅当其 Hessian 矩阵正定 H_xf(x)=\frac{\partial^2f(x)}{\partial x\partial x^T}\succ0,\forall x\in S ,则称 f(x) 为厉格凸函数。

对于 f(x)=\frac{1}{2}x^TQx+q^Tx 而言, H_xf(x)=Q ,已知 Q 为正定矩阵,故 f(x) 为厉格凸函数。

3、最优解的充要条件

有云云一个定理:无收敛凸函数 f(x) 的任何部门极小点 x^* 都是该函数的一个全局极小点,若该函数是可微的,则已足 \frac{\partial f(x)}{\partial x}=0 的安定点 x^*f(x) 的一个全局极小点。因此, x^* 为之上无收敛凸二次规划题目的最优解的充要条件为: \nabla f(x^*)=0

B.共轭偏向组

1、定义

Q\in \mathbb{R}^{n\times n} 为对称正定矩阵, d_1,\ldots,d_m\in \mathbb{R}^n ,若对于 i,j=1,\ldots ,m ,有云云的联系: d_i^TQd_j=0,i\ne j 。则称 d_1,\ldots,d_m 关于 Q 相互共轭,称为 Q- 共轭偏向组。

2、共轭偏向组同时也是线性无关偏向组

定理:设 Q\in \mathbb{R}^{n\times n} 为对称正定矩阵,非零向量组 d_1,\ldots,d_mQ- 共轭偏向组,则 d_1,\dots,d_m 也是线性无关偏向组。

说明:设有一组实数 \alpha_1,\ldots,\alpha_m 使得: \alpha_1d_1+\cdots+\alpha_md_m=0 。用 d_i^TQ,(i=1,\ldots,m) ,离异左乘上式,得到 m 个等式。由 d_i^TQd_j=0,(i\ne j) ,得到这 m 个等式等号左侧只有一项,为: d_i^TQd_i ;等号右侧为:0。即:

\alpha_id_i^TQd_i=0,(i=1,\ldots,m) 。由于 Q 为正定的,由于正定矩阵的二次型大于零,故 d_i^TQd_i>0 ,于是得到: \alpha_i=0,(i=1,\ldots,m) 。由线性无关偏向组的定义,找不到一组非零实数 \alpha_i(i=1,\ldots,m) 使得 \alpha_1d_1+\cdots+\alpha_md_m=0 ,则 d_i,\ldots,d_m 为线性无关偏向组。

共轭梯度法描述

以下必要说明,以一个 Q- 共轭偏向组为更新偏向顺序更新,简略终极找到全剧最小值。

A.按某一偏向进动更新的最优步长

在迭代点 x_k\in \mathbb{R}^n 处,沿非零偏向 d_k 进动一维搜索,步长为 \lambda_k ,方针是找到在 d_k 偏向上 f(x) 的极小值。则必要已足: \lambda_k=\mathop{argmin}_tf(x_k+\lambda_kd_k)。由于 x_{k+1}=x_k+\lambda_kd_k 使得 f(x)d_k 偏向取到最小值,因此有:

\frac{df(x_k+\lambda d_k)}{d\lambda}|_{\lambda=\lambda_k}=0

d_k^T\times \nabla f(x_{k+1})=0

其中 \nabla f(x_{k+1})=Qx_{k+1}+q=Q(x_{k+1}-x_k)+\nabla f(x_k)

d_k^T\times (Q(x_{k+1}-x_k)+\nabla f(x_k))=0

d_k^T\times (Q(\lambda_kd_k)+\nabla f(x_k))=0

\Rightarrow\qquad\lambda_k=\frac{-d_k^T\nabla f(x_k)}{d_k^TQd_k}

B.以一组共轭向量为更新偏向终极会得到全局最小值

说明:在以 Q- 共轭偏向组为更新偏向时, \nabla f(x_k) 与更新偏向 d_0,\ldots,d_{k-1} 均正交。

x_0 出发,顺序沿 d_0,\ldots,d_{k-1} 进动一维搜索,点的更新步长为上一步求出的最优步长\lambda_0,\ldots,\lambda_{k-1}

x_k=x_{i+1}+\sum_{j=i+1}^{k-1}\lambda_jd_j,\qquad(i=0,\ldots,k-1)

\Rightarrow\qquad \nabla f(x_k)=Qx_k+q=Qx_{i+1}+\sum_{j=i+1}^{k-1}\lambda_jQd_j+q=\nabla f(x_{i+1})+\sum_{j=i+1}^{k-1}\lambda_jQd_j

\Rightarrow\qquad d_i^T\nabla f(x_k)=d_i^T\nabla f(x_{i+1})+\sum_{j=i+1}^{k-1}\lambda_jd_i^TQd_j

\frac{df(x_i+\lambda d_i)}{d\lambda}|_{\lambda=\lambda_i}=0\qquad\Rightarrow\qquad d_i^T\nabla f(x_{i+1})=0

d_0,\ldots,d_{k-1}Q- 共轭偏向组 \qquad\Rightarrow\qquad\sum_{j=i+1}^{k-1}\lambda_jd_i^TQd_j=0

因此 d_i^T\nabla f(x_k)=0,(i=0,\ldots,k-1)

即对于 Q- 共轭偏向组来说, d_i(i=0,\ldots,k-1)\nabla f(x_k) 是正交的。当 k=n 时, \nabla f(x_n)d_i(i=0,\ldots,n-1) 正交,而 d_i(i=0,\ldots,n-1) 之间是线性无关的。 \nabla f(x_n),x\in \mathbb{R}^nn 个线性无关向量正交,故 \nabla f(x_n)=0x_n 是该无收敛凸二次规划题目的最优解。

C.在每一个迭代点处如何产生下一个共轭偏向

先说凶果再说明。令 d_{k+1}=-\nabla f(x_{k+1})+\gamma_kd_k

d_k^TQd_{k+1}=0

\Rightarrow\qquad d_k^TQ(-\nabla f(x_{k+1})+\gamma_kd_k)=0

\Rightarrow\qquad\gamma_k=\frac{d_k^TQ\nabla f(x_{k+1})}{d_k^TQd_k}

按这栽方式由现在迭代点梯度 \nabla f(x_{k+1}) 和上一个更新偏向 d_k ,来确定新的更新偏向 d_{k+1}

说明:必要说明的是, d_{k+1} 和之前所有的更新偏向 d_0,\ldots,d_k 之间已足 Q- 共轭联系。

d_k^TQd_{k+1}=0 是已经已足了的。下面计算 d_i^TQd_{k+1}=0,(i=0,\ldots,k-1)

d_i^TQd_{k+1}=d_i^TQ(-\nabla f(x_{k+1})+\gamma_kd_k)=d_i^TQ(-\nabla f(x_{k+1}))+\gamma_kd_i^TQd_k

d_0,\ldots,d_k 之间是已足 Q- 共轭联系的,从 d_0 结果赓续操纵该说明简略得到这层联系。

d_i^TQd_k=0\qquad\Rightarrow\qquad d_i^TQd_{k+1}=d_i^TQ(-\nabla f(x_{k+1}))

上式双方离异乘上最优更新步长 \lambda_i

\lambda_id_i^TQd_{k+1}=\lambda_id_i^TQ(-\nabla f(x_{k+1}))=(-\nabla f(x_{k+1}))^TQ\lambda_id_i

=(-\nabla f(x_{k+1}))^TQ(x_{i+1}-x_i)=(-\nabla f(x_{k+1}))^T(\nabla f(x_{i+1})-\nabla f(x_i))

d_{i+1}=-\nabla f(x_{i+1})+\gamma_id_i 以及 d_{i}=-\nabla f(x_{i})+\gamma_{i-1}d_{i-1}

\Rightarrow \qquad \nabla f(x_{i+1})-\nabla f(x_i)=(\gamma_id_i-d_{i+1})-(d_i-\gamma_{i-1}d_{i-1})

\Rightarrow\qquad d_i^TQd_{k+1}=(-\nabla f(x_{k+1}))^T(\nabla f(x_{i+1})-\nabla f(x_i))

\qquad=(-\nabla f(x_{k+1}))^T((\gamma_id_i-d_{i+1})-(d_i-\gamma_{i-1}d_{i-1}))

由上一末节已知, \nabla f(x_{k+1})d_{i-1},d_i,d_{i+1}(i=0,\ldots,k-1) 均正交,故上式等于零,即 d_i^TQd_{k+1}=0,(i=0,\ldots,k-1)

综上得证以这栽方式产生的新的更新偏向 d_{k+1} ,和之前的所有偏向 d_0,\ldots,d_k 已足 Q- 共轭联系。

D.总结共轭梯度法步骤

对无收敛凸二次规划题目 \mathop{min}_xf(x)=\frac{1}{2}x^TQx+q^Tx ,其中 Q\in\mathbb{R}^{n\times n} 为对称正定矩阵, q\in \mathbb{R}^nx\in\mathbb{R}^n

恣意选择初首点 x_0 ,初首更新偏向 d_0=\nabla f(x_0)

伪如 \nabla f(x_i)=0 ,说明已找到最优解,返回 x_i

伪如 \nabla f(x_i)\ne0 ,进动点的更新: x_{i+1}=x_i+\lambda_id_i ,其中:

\lambda_i=\frac{-d_i^T\nabla f(x_i)}{d_i^TQd_i}

d_{i}=-\nabla f(x_{i})+\gamma_{i-1}d_{i-1} ,这边 \gamma_{i-1}=\frac{d_{i-1}^TQ\nabla f(x_{i})}{d_{i-1}^TQd_{i-1}}

至众通过 n 轮迭代之后简略找到最优解。

PS:俺别国编制学过数值分析、最优化之类课程,只是遇到了共轭梯度法才稍微稳重的学习了一下,伪如有发现文中的误差还看不惜赐教。后来想把自身的这个理解过程体此刻知乎文章里,但是写首来之后发现仍然要损耗些功夫,比首写在纸上慢众了,文字和公式同等都是手打的,伪如有必要转载的还请注脚本出处。

不过很不安写了没人看,由于毕竟全是数学公式,别国图像那么直不益看,但是别国办法只能是这栽方法的。伪如有人也遇到了这栽手法简略参考一下,初衷是渴看首到一点点传播知识的作用。

参考书目

1. 《深入浅出深度学习》——黄安埠

2. 《矩阵分析与行使》——张贤能

郑重声明:文章来源于网络,仅作为参考,如果网站中图片和文字侵犯了您的版权,请联系我们处理!

上一篇:小俺私家征信如何进走查询?

下一篇:20个国际著名logo兴趣的故事

相关推荐

返回顶部