CS205A Lecture 12 Conjugate gradients I; Gradient descent, setup

课程主页:https://graphics.stanford.edu/courses/cs205a-13-fall/schedule.html

这次回顾第十二讲,这一讲介绍了迭代法求解线性系统的思路,引出了共轭梯度法的思想。

优化算法

序列二次规划

回顾之前介绍的优化问题:

现在讨论如何使用迭代算法求解,首先对目标函数和条件使用泰勒展开:

所以可以用如下方式更新$\vec x_{k+1}$:

如果只有等号约束,那么可以构造如下拉格朗日乘子:

其中

结合等号约束,得到如下线性系统:

Barrier Methods

另一种处理约束条件的方法是将约束项转化为能量项,例如

如果$\rho \to \infty$,那么$g(\vec x)\to 0$。

Chapter 10 Iterative Linear Solvers

回到线性系统的求解

这一讲将介绍如何利用迭代算法求解线性系统。

讨论之前,这里做如下三个假设:

  1. $A\in \mathbb R^{n\times n}$
  2. $A$是对称矩阵,$A^T=A$
  3. $A$是正定矩阵,即对$\vec x \neq 0$,$\vec x^T A\vec x >0$

梯度下降

在上述假设下,求解$A\vec x =\vec b$等价于最小化

特别的,对上式求梯度可得

令$\nabla f(\vec x) =\vec 0$即可得到

回顾梯度下降算法:

  1. $\vec{d}_{k} =-\nabla f\left(\vec{x}_{k-1}\right)=\vec{b}-A \vec{x}_{k-1}$
  2. 定义$\vec{x}_{k} = \vec{x}_{k-1}+\alpha_{k} \vec{d}_{k}$,其中选择$\alpha_k$使得$f\left(\vec{x}_{k}\right)<f\left(\vec{x}_{k-1}\right)$

决定$\alpha_k ​$的值是一维“线性搜索”问题,特别的,在这里我们有

关于$\alpha$求导可得

令上式为$0$可得

因为

所以

将上述内容总结,得到如下算法:

收敛性

下面讨论梯度下降的收敛问题,特别的,这里考虑

其中

如果

那么该算法一定收敛。

现在利用

计算$f(\vec x_k )$:

因此

接下来计算

带入$A\vec x’=\vec b​$可得

代回$R_k$的表达式可得

所以梯度下降的收敛速度取决于$A$的条件数,下图展示了两种情形:

(注意因为$\text{cond} A\ge 1$,所以收敛性是显然的)

共轭梯度法

前几章介绍的求解$A\vec x =\vec b $的算法都是在$O(n^3)$时间内计算出结果,梯度下降法每一轮需要的时间为$O(n^2)$(矩阵乘法),如果迭代超过$n$轮,那么时间就会超过$O(n^3)$,这一讲介绍的共轭梯度可以保证在$n$步内收敛,是一种非常强大的算法。

动机

稍作变形

所以最小化$f(\vec x)$等价于最小化$\vec x$到$\vec x’$的$A$范数:

为叙述方便,这里给出如下定义:

注意这里$A$是对称正定矩阵,所以可以使用Cholesky分解:

因此

如果定义

那么

如果我们计算出$L$,那么优化上述问题将非常简单,后面将介绍在不计算出$L$的情形下快速求解上述问题。

在讨论之前,注意我们有如下命题:

命题10.1

这个结论是显然的,假设最小值点为

那么只要依次计算出$\alpha_i$即可。

运用上述思路求解之前介绍的问题,这里只要考虑$L^T \vec x$即可,假设

为正交基,那么对于$i\neq j$,我们有

于是引出如下定义:

定义10.2

那么结合之前讨论,我们有如下命题:

命题10.2

本文标题:CS205A Lecture 12 Conjugate gradients I; Gradient descent, setup

文章作者:Doraemonzzz

发布时间:2019年04月23日 - 00:35:00

最后更新:2019年04月28日 - 16:43:43

原始链接:http://doraemonzzz.com/2019/04/23/CS205A Lecture 12 Conjugate gradients I; Gradient descent, setup/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。