无约束最优化(二) 共轭方向法与共轭梯度法

作者: 小小何先生 | 来源:发表于2019-11-03 14:14 被阅读0次

无约束最优化(二) 共轭方向法与共轭梯度法
最优化方法
梯度优化算法
共轭梯度法&QR分解法
[ML]《ML导论》十一：优化方法
共轭梯度法
2019-04-10
2018-12-15逻辑回归高级优化
共轭梯度法——CG法FR法和PRP法
第十章共轭方向法

基本思想

之前文章最速下降法、Newton法、修正Newton法介绍的最速下降法存在锯齿现象，Newton法需要计算目标函数的二阶导数。接下来介绍的共轭方向法是介于最速下降法和Newton法之间的一种方法，它克服了最速下降法的锯齿现象，从而提高了收敛速度；它的迭代公式也比较简单，不必计算目标函数的二阶导数，与Newton法相比，减少了计算量和存储量。它是比较实用而有效的最优化方法。

我们先将其在正定二次函数 $f(x)=\frac{1}{2} x^{T} Q x+b^{T} x+c$ 上研究，然后再把算法用到更一般的目标函数上。首先考虑二维的情形。

任选初始点 $x_{0}$ ，沿它的某个下降方向，例如向量 $p_{0}$ 的方向，作直线搜索，如上图所示。由下面这个定理：

定理：设目标函数 $f(x)$ 具有一阶连续偏导数，若 $z=ls(x,p)$ ,则 $\nabla f(z)^{T}p=0$ 。

知 $\nabla f(x_{1})^{T}p_{0}=0$ 。如果按照最速下降法选择的就是负梯度方向为搜索方向(也就是 $-g_{1}$ 方向)，那么将要发生锯齿现象。于是一个设想是，干脆选择下一个迭代的搜索方向 $p_{1}$ 就从 $x_{1}$ 直指极小点 $x^{*}$ ，也就是找到上图所示的 $p_{1}$ 方向。

因为 $p_{1}$ 从 $x_{1}$ 直指极小点 $x^{*}$ ,所以 $x^{*}$ 可以表示为：
$x^{*}=x_{1}+t_{1}p_{1}$
其中 $t_{1}$ 是最优步长因子。显然，当 $x^{*} \neq x_{1}$ 时， $t_{1} \neq 0$ 。到这里，我们还有一个已知条件没用，就是目标函数为二次正定，所以我们对目标函数求导，得到：
$\nabla f(x)=Qx+b$
因为 $x^{*}$ 是极小点，所以有:
$\nabla f(x^{*})=Qx^{*}+b=0$
将 $x^{*}=x_{1}+t_{1}p_{1}$ 带入上述方程式，有：
$\nabla f(x_{1}) + t_{1}Qp_{1}=0$
上式两边同时左乘 $p_{0}^{T}$ ，并注意到 $p_{0}^{T} \nabla f(x_{1})=0$ 和 $t \neq 0$ ，得到 $p_{0}^{T}Qp_{1}=0$ 。这就是为使 $p_{1}$ 直指极小点 $x^{*}$ ， $p_{1}$ 所必须满足的条件。并且我们将两个向量 $p_{0}$ 和 $p_{1}$ 称为 $Q$ 共轭向量或称 $p_{0}$ 和 $p_{1}$ 是 $Q$ 共轭方向。

由上面共轭梯度法那张图可以设：
$p_{1}=-\nabla f(x_{1})+\alpha_{0}p_{0}$
上式两边同时左乘 $p_{0}^{T}Q$ ,得：
$-p_{0}^{T} Q \nabla f\left(x_{1}\right)+\alpha_{0} p_{0}^{T} Q p_{0}=0$
由此解出：
$\alpha_{0} = \frac{p_{0}^{T} Q \nabla f\left(x_{1}\right)}{p_{0}^{T} Q p_{0}}$
代回 $p_{1}=-\nabla f(x_{1})+\alpha_{0}p_{0}$ 得：
$p_{1}=-\nabla f(x_{1})+\frac{p_{0}^{T} Q \nabla f\left(x_{1}\right)}{p_{0}^{T} Q p_{0}}p_{0}$
从而求到了 $p_{1}$ 的方向。

归纳一下，对于正定二元二次函数，从任意初始点 $x_{0}$ 出发，沿任意下降方向 $p_{0}$ 做直线搜索得到 $x_{1}$ 再从 $x_{1}$ 出发，沿 $p_{0}$ 的共轭方向 $p_{1}$ 作直线搜索，所得到的 $x_{2}$ 必是极小点 $x^{*}$ 。到目前为止的共轭梯度法依旧是假设了目标函数是二次正定矩阵。

上面的结果可以推广到 $n$ 维空间中，即在 $n$ 维空间中，可以找出 $n$ 个互相共轭的方向，对于 $n$ 元正定二次函数从任意初始点出发，顺次沿着这 $n$ 个共轭方向最多作 $n$ 次直线搜索，就可以求到目标函数的极小点。

对于 $n$ 元正定二次目标函数，如果从任意初始点出发经过有限次迭代就能够求到极小点，那么称这种算法具有二次终止性。例如，Newton法对于二次函数只须经过一次迭代就可以求到极小点，因此是二次终止的；而最速下降法就不具有二次终止性。共轭方向法（如共轭梯度法、拟Newton法等）也是二次终止的。

一般说来，具有二次终止性的算法，在用于一般函数时，收敛速度是较快的。

共轭向量及其性质

定义：设 $Q$ 是 $n \times n$ 对称正定矩阵。若 $n$ 维向量空间中的非零向量 $p_{0},p_{1},···，p_{m-1}$ 满足 $p_{i}^{T}Qp_{j}=0$ ， $i,j=0,1,···，m-1(i \neq j)$ 则称 $p_{0},p_{1}，···，p_{m-1}$ 是 $Q$ 共轭向量或称向量 $p_{0},p_{1},···，p_{m-1}$ 是 $Q$ 共轭的（简称共轭）。

当 $Q=E$ (单位矩阵)时 $p_{i}^{T}Qp_{j}=0$ 变为 $p_{i}^{T}p_{j}=0$ ， $i,j=0,1,···，m-1(i \neq j)$ 。即向量 $i,j=0,1,···，m-1(i \neq j)$ 互相正交。由此看到，“正交”是“共轭”的一种特殊情形，或说，“共轭”是“正交”的推广。

下面介绍几个定理：

定理：若非零向量 $p_{0},p_{1}，···，p_{m-1}$ 是 $Q$ 共轭的，则线性无关。

推论：在 $n$ 维向量空间中， $R^{n}$ 非零的共轭向量的个数不超过 $n$ 。

定义设 $p_{0},p_{1}，···，p_{m-1}$ 是 $R$ 中的线性无关向量， $x_{0} \in R$ 。那么形式为：
$z=x_{0}+\sum_{i=0}^{m-1} \alpha_{i} p_{i}, \forall \alpha_{1}, \alpha_{2}, \cdots, \alpha_{m-1} \in R$
的向量构成的集合，记为 $L \left [ x_{0};p_{0},p_{1},···，p_{m-1} \right ]$ 。称为由点 $x_{0}$ 和向量 $p_{0},p_{1}，···，p_{m-1}$ 所生成的线性流形。

共轭方向法

共轭方向法的理论基础是下面的定理。

定理假设

(1) Q为 $n \times n$ 对称正定矩阵;

(2) 非零向量 $p_{0},p_{1}，···，p_{m-1}$ 是 $Q$ 共轭向量;

(3) 对二次目标函数 $f(x)=\frac{1}{2} x^{T} Q x+b^{T} x+c$ 顺次进行 $m$ 次直线搜索:
$x_{i_1} = ls(x_{i},p_{i}) , i=0,1，···，m-1$
其中 $x_{0} \in R$ 是任意选定的初始点，则有：

i) $p_{j}^{T} \nabla f(x_{m})=0$ ， $0 \leqslant j \leqslant m$ ;

ii) $x_{m}$ 是二次函数 $f(x)=\frac{1}{2} x^{T} Q x+b^{T} x+c$ 在线性流形 $L \left [ x_{0};p_{0},p_{1},···，p_{m-1} \right ]$ 上的极小点。

这个定理看来较繁，但可借用直观的几何图形来帮助理解。 $n=3$ ， $m=2$ 的情形为例，如图示。

$p_{0}$ 和 $p_{1}$ 是Q共轭向量，张成了二维空间 $R^{2}$ ，这是过坐标原点的一个平面。现在，过点 $x_{0}$ 沿 $p_{0}$ 方向作直线搜索得到 $x_{1}$ ，再过点 $x_{1}$ 沿 $p_{1}$ 方向作直线搜索得到 $x_{2}$ 过点 $x_{0}$ 由向量 $p_{0}$ 和 $p_{1}$ 张成的平面就是线性流形 $L \left [ x_{0};p_{0},p_{1} \right ]$ 。它是 $R^{2}$ 的平行平面。

定理的论断是，最后一个迭代点 $x_{2}$ 处的梯度 $\nabla f(x_{2})$ 必与 $p_{0}$ 和 $p_{1}$ 垂直。并且 $x_{2}$ 是三元二次目标函数 $f(x)$ 在线性流形 $L \left [ x_{0};p_{0},p_{1} \right ]$ (即过 $x_{0}$ 由 $p_{0}$ 和 $p_{1}$ 张成的平面)上的极小点。

共轭方向法算法的大体流程就是：选定初始点 $x_{0}$ 和下降方向向量 $p_{0}$ ，做直线搜索 $x_{k+1}=ls(x_{k},p_{k})$ 。提供的梯度方向 $p_{k+1}$ 使得 $p_{j}^{T}Qp_{k+1}=0$ ， $j=0,1,···，k$ 。提供共轭方向的方法有多种。不同的提供方法将对应不同的共轭方法。每种方法也因产生共轭方向的特点而得名。

那么这里做直线搜索 $x_{k+1}=x_{k}+tp_{k}$ 中的 $t$ 是如何确定的呢？这里我们先回顾一下在最速下降法中是如何计算这个 $t$ 的。最速下降法：

依据定理设目标函数 $f(x)$ 具有一阶连续偏导数，若 $z=ls(x,p)$ ,则 $\nabla f(z)^{T}p=0$ 。，我们可以得到 $g_{k+1}·g_{k}=0$ 。由此有：
$\begin{aligned} g_{k+1}·g_{k} & = [Q(x_{k}-t_{k}g_{k})+b]^{T}g(k)=0 \\ & = [Qx_{k}+b - t_{k}Qg_{k}]^{T}g(k)=0 \\ & = [g_{k}-t_{k}Qg_{k}]^{T}g(k)=0 \end{aligned}$
由此，可求解出 $t_{k}$ :
$t_{k}=\frac{g_{k}^{T}g_{k}}{g_{k}^{T}Qg_{k}}$
这里还可以采用另外一种种方式计算 $t_{k}$ ，下面对另外一种方式进行公式推导：

由 $x_{k+1}=x_{k}+tp_{k}$ ，用 $Q$ 左乘上式两边，然后再同时加上 $b$ ，利用 $\nabla f(x)=Qx+b$ 能够得到：
$\nabla f(x_{k+1})=\nabla f(x_{k}) + t Q p_{k}$
左乘 $p_{k}$ 有
$p_{k}^{T} \nabla f(x_{k}+tp_{k})=p_{k}^{T} \nabla f(x_{k}) + t p_{k}^{T} Q p_{k} = 0$
由此解出：
$t=- \frac{p_{k}^{T} \nabla f(x_{k})}{p_{k}^{T} Q p_{k}}$
在最速下降法中 $x_{k+1}=x_{k} - t_{k}g_{k}$ ，在共轭方向法中 $x_{k+1}=x_{k} + t_{k}g_{k}$ 。

共轭梯度法

在共轭方向法中，如果初始共轭向量 $p_{0}$ 恰好取为初始点 $x_{0}$ 处的负梯度 $- g_{0}$ ，而其余共轭向量 $p_{k}$$(k=1,2,···，n-1)$ 由第 $k$ 个迭代点 $x_{k}$ 处的负梯度 $- g_{k}$ 与已经得到的共轭向量 $p_{k-1}$ 的线性组合来确定，那么这个共轭方向法就称为共轭梯度法。

针对目标函数是正定二次函数来讨论：

(1) 第一个迭代点的获得：

选定初始点 $x_{0}$ ，设 $x_{0} \neq x^{*}$ (否则迭代终止)，因此 $\nabla f(x_{0}) \neq 0$ 。取 $p_{0} \neq -g_{0}$ ，（以下用 $g_{k}$ 表示 $\nabla f(x_{k})$ ）从 $x_{0}$ 出发沿 $p_{0}$ 方向做直线搜索，得到第1个迭代点 $x_{1}=x_{0}+t_{0}p_{0}$ ，其中 $t_{0}$ 可由下式确定：
$t_{0}=- \frac{p_{0}^{T} g_{0}}{p_{0}^{T} Q p_{0}} = \frac{g_{0}^{T}g_{0}}{p_{0}^{T}Qp_{0}}$
显然 $t_{0} \neq 0$

(2) 第二个迭代点的获得：

设 $x_{1} \neq x^{*}$ ，因此 $g_{1} \neq 0$ 。由 $p_{0}^{T}g_{1}=0$ 知 $p_{0}$ 与 $g_{1}$ 线性无关。取 $p_{1}=-g_{1} + \alpha _{0} p_{0}$ 其中 $\alpha_{0}$ 是使 $p_{1}$ 与 $p_{0}$ 共轭的待定系数，令：
$p_{1}^{T}Qp_{0}=-g_{1}^{T}Qp_{0} + \alpha_{0} p_{0}^{T}Qp_{0} = 0$
由此解出
$\alpha _{0} = \frac{g_{1}^{T}Qp_{0}}{p_{0}^{T}Qp_{0}}$
并代回确定 $p_{1}$ ，并获得第2个迭代点。
$x_{2}=x_{1}+t_{1}p_{1}$
由公式 $t=- \frac{p_{k}^{T} \nabla f(x_{k})}{p_{k}^{T} Q p_{k}}$ 可以求得 $t_{1}$ ，带入公式 $p_{1}=-g_{1} + \alpha _{0} p_{0}$ 可进一步优化得到：
$t_{1} = - \frac{p_{1}^{T} g_{1}}{p_{1}^{T} Q p_{1}} = \frac{g_{1}^{T} g_{1}}{p_{1}^{T} Q p_{1}} \neq 0$
(3) 第三个迭代点的获得：

设 $x_{2} \neq x^{*}$ ，因此 $g_{2} \neq 0$ 。由 $p_{1}^{T}g_{2}=0$ 知 $p_{1}$ 与 $g_{2}$ 线性无关。取 $p_{2}=-g_{2} + \alpha _{1} p_{1}$ 其中 $\alpha_{1}$ 是使 $p_{2}$ 与 $p_{1}$ 共轭的待定系数，令：
$p_{2}^{T}Qp_{1}=-g_{2}^{T}Qp_{1} + \alpha_{1} p_{1}^{T}Qp_{1} = 0$
由此解出
$\alpha _{1} = \frac{g_{2}^{T}Qp_{1}}{p_{1}^{T}Qp_{1}}$
并代回确定 $p_{2}$ ，并获得第3个迭代点。
$x_{3}=x_{2}+t_{2}p_{2}$
其中
$t_{2} = - \frac{p_{2}^{T} g_{2}}{p_{2}^{T} Q p_{2}} = \frac{g_{2}^{T} g_{2}}{p_{2}^{T} Q p_{2}} \neq 0$
上述过程仅表明 $p_{0}$ 与 $p_{1}$ ， $p_{1}$ 与 $p_{2}$ 共轭，现在问， $p_{0}$ 与 $p_{2}$ 也共轭吗？
$\begin{aligned} p_{2}^{T} Q p_{0} &=\left(-g_{2}+\alpha_{1} p_{1}\right)^{T} Q p_{0} \\ &=-g_{2}^{T} Q p_{0}+\alpha_{1} p_{1}^{T} Q p_{0} \\ &=-g_{2}^{T} Q p_{0}\left[\mathbb{L} | p_{1}^{T} Q p_{0}=0\right] \\ &=-g_{2}^{T}\left(g_{1}-g_{0}\right) / t_{0}\left(\mathrm{Hg}_{1+1}=g_{i}+t_{i} Q p_{i}, t_{i} \neq 0\right) \\ &=-\left(g_{2}^{T} g_{1}-g_{2}^{T} g_{0}\right) / t_{0} \end{aligned}$
(4) 第 $k$ 个迭代点的获得：

由 $p_{k-1}^{T}g_{k}=0$ 知 $p_{k-1}$ 与 $g_{k}$ 线性无关。取 $p_{k}=-g_{k} + \alpha _{k-1} p_{k-1}$ 其中 $\alpha_{k-1}$ 是使 $p_{k}$ 与 $p_{k-1}$ 共轭的待定系数，令：
$p_{k}^{T}Qp_{k-1}=-g_{k}^{T}Qp_{k-1} + \alpha_{k-1} p_{k-1}^{T}Qp_{k-1} = 0$
由此解出
$\alpha _{k-1} = \frac{g_{k}^{T}Qp_{k-1}}{p_{k-1}^{T}Qp_{k-1}}$
并代回确定 $p_{k}$ ，并获得第k+1个迭代点。
$x_{k+1}=x_{k}+t_{k}p_{k}$
其中
$t_{k} = - \frac{p_{k}^{T} g_{k}}{p_{k}^{T} Q p_{k}} = \frac{g_{k}^{T} g_{k}}{p_{k}^{T} Q p_{k}} \neq 0$
以上就是共轭梯度法得核心内容。

Fletcher-Reeves共轭梯度法

为使共轭梯度算法也适用于非二次函数，需要消去算法中的 $Q$ 对于正定二次函数，有 $Qp_{k}=\frac{1}{t_{k}}(g_{k+1}-g_{k})$ 代入到 $\alpha_{k}$ 中，得：
$\alpha_{k}=\frac{g_{k+1}^{T} Q p_{k}}{p_{k}^{T} Q p_{k}}=\frac{g_{k+1}^{T}\left(g_{k+1}-g_{k}\right)}{p_{k}^{T}\left(g_{k+1}-g_{k}\right)}$
此式中已不再出现矩阵 $Q$ ，将 $p_{k}=-g_{k} + \alpha _{k-1} p_{k-1}$ 两端转置运算，并同时右乘 $g_{k+1}$ 得：
$p_{k}^{T}g_{k+1}=-g_{k}^{T}g_{k+1} + \alpha _{k-1} p_{k-1}^{T}g_{k+1}$
将共轭方向法中的定理带入得到 $p_{k-1}^{T}g_{k+1}=0$ ，由直线搜索的性质有 $p_{k}^{T}g_{k+1}=0$ ，带入上式有 $g_{k+1}^{T}g_{k}=0$ 。此外：
$p_{k}^{T}g_{k}=-g_{k}^{T}g_{k} + \alpha _{k-1} p_{k-1}^{T}g_{k}=-g_{k}^{T}g_{k}$
带入 $\alpha_{k}$ ，得到：
$\alpha_{k}=\frac{g_{k+1}^{T} g_{k+1}}{g_{k}^{T} g_{k}}=\frac{\left\|g_{k+1}\right\|^{2}}{\left\|g_{k}\right\|^{2}}$
此式称为Fletcher－Reeves公式(1964年)。