无约束优化问题求解（3）：共轭梯度法

4. 共轭梯度法

4.1 共轭方向

最速下降法的线搜索采取精确线搜索时，由精确线搜索需要满足的条件：迭代点列 $x_{k+1}=x_k+{\alpha }_k{d}_k$ ，$?f(x_{k+1}{)}^T{d}_k=0$，其中 ${\alpha }_k$ 是第 $k$ 次迭代的最优步长，$d_k$是第 $k$ 次迭代的负梯度方向 $??f(x_k)$，可以得到$$\begin{array}{r}?f(x_{k+1}{)}^T?f(x_k)=??f(x_{k+1}{)}^T{d}_k/\Vert ?f(x_k){\Vert }_2=0.\end{array}\text{\hspace{1em}?}$$

该式的含义即相邻两次的搜索方向是垂直的，如果我们考虑目标函数为二次多项式的形式，即
$$\begin{array}{r}f(x)=\frac{1}{2}{x}^{T}Ax+b^{T}x,b=(b_1,?,b_n{)}^T\in {\mathbb{R}}^n,\end{array}\text{\hspace{1em}?}$$其中 $A:=\mathbf{diag}({\lambda }_1,?,{\lambda }_n)$ 是一个对角矩阵，${\lambda }_i>0,i=1,?,n.$ 此时，函数的等高面为一椭球(圆)，基于精确线搜索的最速下降法的迭代点列以锯齿方向前进，如图 4.1的黑色实线所示，这使得其收敛速度变得缓慢.也就是说尽管最速下降法采用当前点梯度下降最快的方向作为搜索方向， 但该方向未必是较大范围内下降最快的方向，也就是说该方向不一定是较大范围内函数值幅度变化最大方向，而如果我们按照平行于坐标轴的方向进行精确搜索，如图 4.1左边的红色虚线所示， 在二维情形只需要两次就达到了最小值点，那么我们可以断言：对 $n$ 维的二次函数优化问题(2)，最多经过 $n$ 次迭代就可以达到最小值点，上面的断言就是共轭方向法的想法.

图 4.1：最速下降法的搜索方向 (黑色实线)

对形如(2)的目标函数，由于 $A:=\mathbf{diag}({\lambda }_1,?,{\lambda }_n),{\lambda }_i>0,i=1,?,n$. 我们有$$f(x)=\sum _{i=1}^n(\frac{1}{2}{\lambda }_i{x}_i^2+b_i{x}_i).$$也就是说对于每一个 $i$ 而言，都是二次函数，根据二次函数的性质，$\frac{1}{2}{\lambda }_i{x}_i^2+b_i{x}_i$ 在无约束的情况下必然可以取到最值，$x=(x_1,?,x_n)$ 使得 $f(x)$ 达到最小值当且仅当对 $i=1,?,n,x_i$ 使得 $f_i(x_i):={\lambda }_i{x}_i^2+b_i{x}_i$ 达到最小.

根据解析几何的知识，函数 $f(x)$ 是二次曲面，且其等高面是一个椭球 (圆). 对$i=1,?,n$，记$e_i$ 表示 ${\mathbb{R}}^n$ 中第 $i$个坐标向量.$?x_0\in {\mathbb{R}}^n$,沿方向 $d_i=e_i$ 作精确搜索时，将搜索到 $f_i(x_i)$ 的最小值点，而其余项不变，也就是说每次搜索只改变一个方向而保持其他方向不变，那么如此搜索最多 $n$ 次后达到函数的最小值点，这也就是前面我们断言的内容.

但是这个时候可能又有疑问了，并不是所有的椭圆的轴都是和坐标轴平行的呀，那么如果这个时候还是以平行于坐标轴的方向来作为每次的搜索方向不一定会达到最快的效果呀。事实上确实如此，沿着坐标轴来搜索确实只是一种特殊的情况，如下图所示：

图 4.2：正交和共轭

如图 4.2所示，当我们还以坐标轴的方向来作为搜索方向的时候，沿着等高线移动的时候并不是最快的.但是如果我们旋转一下坐标轴会发现，我们可以用适当的旋转角度，旋转坐标轴后，使得坐标轴和椭圆的轴平行，实际上由线性代数的知识我们可以知道，旋转坐标轴本质上是做了一种线性变换.

简单地说共轭方向其实就是线性变化后的坐标轴和椭圆的轴平行的方向.下面我们用线性代数的知识来推导一下这个过程.

一般地，若二次函数
$$\begin{array}{r}f(x)=\frac{1}{2}{x}^{T}Ax+b^{T}x\end{array}\text{\hspace{1em}?}$$ (3) 中 $A$ 为 $n$ 阶正定矩阵，但未必是对角矩阵，此时函数曲面的等高面仍是椭球，但主轴未必平行于坐标轴，如图 4.3(右) 所示. 这时，可以通过坐标变换将 $A$ 对角化：取可逆矩阵 $D$,做坐标变换 $x=Dy$,记 $c=D^{T}b$,则
$$f(x)=\frac{1}{2}{y}^T(D^{T}AD)y+c^{T}y.$$因此，当 $D^{T}AD$ 是一个对角矩阵时(并且对角线的元素均大于0)，在 $y$ 坐标系里沿坐标方向 $e_i,i=1,?,n$, 做精确搜索，便可以在有限次内达到 $f(x)$ 的最小值点.

在 $y$ 坐标系中的迭代 $y_{k+1}=y_k+\alpha e_k$ ，根据坐标变换，等价于在原 $x$ 坐标系中的迭代 $x_{k+1}=$ $x_k+\alpha D{e}_k,k=0,1,...,n?1$.记 $d_k:=D{e}_k,k=0,1,...,n?1$,那么
$$[d_0,...,d_{n?1}]=D,$$即 $d_0,...,d_{n?1}$ 是矩阵 $D$的列向量.此时，迭代公式为$x_k+1=x_k+\alpha d_k$.这说明，只要我们在原坐标系中依次沿着$d_0,?,d_{n?1}$做精确搜索，便可在有限次达到 $f(x)$ 的最小值点

为此，我们需要先求得方向 $d_0,d_1,?,d_{n?1}$ 使得 $D^{T}AD$ 为对角矩阵.这等价于
$$\begin{array}{r}{d}_i^{T}A{d}_j=0,i,j=0,1,?,n?1;i\ne j.\end{array}$$由此，下面我们看看共轭方向的数学形式的定义。

定义 4.1 设 $A\in {\mathbb{R}}^{n\times n}$ 是一个正定矩阵，非零向量 $d_0,?,d_{k?1}\in {\mathbb{R}}^n$ 称为是彼此 $(A)$ 共轭的，如果它们满足
$$\begin{array}{r}{d}_i^{T}A{d}_j=0,i,j=0,1,?,k?1;i\ne j.\end{array}$$显然，向量 $d_i$ 与 $d_j$ 共轭其实就是它们在内积 $?x,y?:=x^{T}Ay$ 下为正交，由此两两 (A) 共轭的向量组是在上述内积意义下两两正交的向量组，所以必定线性无关.除此此外，如果
$d_0,???,d_k?1\in {\mathbb{R}}^n$ 是彼此 (A) 共轭的，那么改变这些向量的符号仍然是彼此 (A) 共轭的.所以每一个 $d_i$ 未必是目标函数 $f(x)$ 下降的方向，这是因在沿着该方向进行搜索时需要同时考虑其反方向.

命题 4.1 设 $A$ 是 $n$ 阶正定矩阵，$f$ 如(3) 所述，$k\ge 1,d_0,?,d_{k?1}\in {\mathbb{R}}^n$ 是一组是彼此 $(A)$ 共轭的向量.任取 $x_0\in {\mathbb{R}}^n$,记 $x_{j+1}=x_j+{\alpha }_j{d}_j,j=0,1,?,k?1$,为精确搜索的点列 (由于不能保证 $d_j$ 为下降方向，故搜索时允许 ${\alpha }_j$ 为负数), 那么

$(i)?f(x_k{)}^T{d}_j=0,j=0,1,?,k?1;$

$(ii)x_k={\mathrm{argmin}}_{x\in X_k}f(x)$,其中 X k : = x 0 + s p a n { d 0 , ? ? , d k ? 1 } ; X_k:=x_0+\mathbf{span}\{d_0,\cdots,d_{k-1}\}; Xk?:=x0?+span{d0?,?,dk?1?};

$(iii)$ 当$k=n$ 时，$x_n$ 是 $f$在${\mathbb{R}}^n$ 上的全局极小点.

首先不加证明，我们先看看这个命题说了个什么事情.由上述的命题我们可以看出? $X_k$ 是?由向量组 { d 0 , ? ? , d k ? 1 } \{d_0,\cdots,d_{k-1}\} {d0?,?,dk?1?} 张成的线性空间。从上述命题我们可以简述一下共轭方向法的基本流程：从初始点 $x_0$开始，根据精确线搜索找到最优步长 ${\alpha }_0$，根据迭代式 $x_1=x_0+{\alpha }_0{d}_0,j=0,1,?,k?1$ 以及条件 $x_1={\mathrm{argmin}}_{x\in X_1}f(x)$，计算得到 $x_1$，其中 X 1 = x 0 + s p a n { d 0 } X_1 = x_0 + \mathbf{span}\{d_0\} X1?=x0?+span{d0?}，这样就完成了一维的情况 $\mathbb{R}$ .类似地从一维的情况 $\mathbb{R}$ 逐步推广到 ${\mathbb{R}}^n$，由于每一个“新添加”的维度都是与之前维度共轭的(这一性质由命题的条件给出，后续证明)，所以自然线性无关，于是这样便能逐步地从初始点找到整个空间 ${\mathbf{R}}^n$的共轭序列点.下面我们再看看命题是怎么样证明的.

证. $(i)$ 根据精确搜索条件，有 $?f(x_{j+1}{)}^T{d}_j=0,?j=0,1,?,k?1.$ 于是， $?f(x_k{)}^T{d}_{k?1}=0$.而对于 $j=0,1,?,k?2$,有
$$\begin{array}{rl}?f(x_k)& \begin{array}{rl}& =A{x}_k+b=A(x_{k?1}+{\alpha }_{k?1}{d}_{k?1})+b=?f(x_{k?1})+{\alpha }_{k?1}A{d}_{k?1}\end{array}\\ & =?\\ & =?f(x_{j+1})+{\alpha }_{j+1}A{d}_{j+1}+?+{\alpha }_{k?1}A{d}_{k?1},\end{array}$$上式两边取转置后再同时右乘 $d_j$ ，利用 $?f(x_{j+1}{)}^T{d}_j=0,?j=0,1,?,k?1.$ 可以得到 $?f(x_k{)}^T{d}_j=?f(x_{j+1}{)}^T{d}_j=0$，$(i)$ 得证.

下面证 $(ii)$，首先对于 $x_k$，将其写开可以得到 $$x_k=x_{k?1}+{\alpha }_{k?1}{d}_{k?1}=?=x_0+\sum _{j=0}^{k?1}{\alpha }_j{d}_j\in X_k$$

对任意的 $x=x_0+{\sum }_{j=0}^{k?1}{\beta }_j{d}_j\in X_k$，根据 Taylor 展开,由于目标函数式二次函数，因此可以利用 Taylor展开得到
$$\begin{array}{rl}f(x)& =f(x_k)+?f(x_k{)}^T(x?x_k)+\frac{1}{2}(x?x_k{)}^{T}A(x?x_k)\\ & \ge f(x_k)+?f(x_k{)}^T(x?x_k)\\ & =f(x_k)+?f(x_k{)}^T[\sum _{j=0}^{k?1}({\beta }_j?{\alpha }_k)d_j]=f(x_k).\end{array}$$上式中的不等号利用了结论：若矩阵 $A$ 正定矩阵，则对于任意 $x\in {\mathbb{R}}^n$，都有 $x^{T}Ax＞0$；第二个等号将 $x?x_k$展开计算即得.

所以，$x_k$是 $f(x)$ 在 $X_k$ 中的最小值点.

$(iii)$ 当 $k=n$ 时，因为$d_0,?,d_n?1$ 线性无关，所以 $X_{n?1}={\mathbb{R}}^n$.从而 $x_n$ 是 $f$在${\mathbb{R}}^n$ 上的全局极小点.

基于给定的共轭方向的搜索方法称为共轭方向法. 如何快速地构造共轭方向组
$d_0,?,d_{n?1}$ 是该方法的关键所在. 虽然通过对矩阵 $A$ 的特征分解可以得到共轭方向， 但其计算量为$O(n^3)$.实际上，若$x_0$取得好，我们只需要少数几次迭代即可达到函数的极小值点.那么接下来我们就要看看一种在迭代过程中即时生成 $d_k$ 的方法，称为共轭梯度法.

4.2 共轭梯度法

共轭梯度法是一种在迭代过程中利用梯度向量来逐步生成共轭向量组的方法，对于
目标函数 $f(x)=\frac{1}{2}{x}^{T}Ax+b^{T}x$ ,共轭梯度法按如下算法来生成共轭向量组.

首先，取充分小的数 $?>0$. 任取初始点 $x_0\in {\mathbb{R}}^n$,若不满足终止条件 $\Vert ?f(x_0){\Vert }_2<?$，令 $d_0:=??f(x_0)$，则 $?f(x_0{)}^T{d}_0=?\Vert ?f(x_0){\Vert }_2^2<0$，因而可以通过精确搜索得到该次迭代的最优步长 ${\alpha }_0>0$，使得 $x_1=x_0+{\alpha }_0{d}_0$ 满足 $?f(x_1{)}^T{d}_0=0.$

一般地，如果已经构造出了彼此 (A) 共轭的向量组 $d_0,?,d_{k?1}$ 和通过精确搜索所得迭代点列 $x_{j+1}=x_j+{\alpha }_j{d}_j,j=0,1,...,k?1$, 其中
$${\alpha }_j>0,?f(x_j{)}^T{d}_j<0,j=0,1,...,k?1$$若 $\Vert ?f(x_k){\Vert }_2\ge ?,$令$$\begin{array}{r}{d}_k:=??f(x_k)+\sum _{i=0}^{k?1}{\beta }_i{d}_i\end{array}\text{\hspace{1em}?}$$，并希望选取合适的参数 ${\beta }_0,...,{\beta }_{k?1}$ 使得 $d_0,?,d_{k?1},d_k$ 彼此 (A) 共轭.也就是说这个过程是利用已知的彼此 (A) 共轭的向量组 $d_0,?,d_{k?1}$，通过待定系数法来求解合适的参数，最终得到一个 $d_k$，使得 $d_k$与 向量组 $d_0,?,d_{k?1}$两两共轭.

下面看看待定系数应该怎么求解，$d_0,?,d_{k?1},d_k$ 彼此 (A) 共轭当且仅当 $d_k^{T}A{d}_j=0,j=0,1,?,k?1$, 即
$$(??f(x_k)+\sum _{i=0}^{k?1}{\beta }_i{d}_i{)}^{T}A{d}_j=0,j=0,1,?,k?1.$$$t?0$
由于 $d_0,?,d_{k?1}$是彼此$(A)$ 共轭的，所以上式等价于 ${\beta }_j{d}_j^{T}A{d}_j=?f(x_k{)}^{T}A{d}_j$，即
$$\begin{array}{r}{\beta }_j=\frac{?f(x_k{)}^{T}A{d}_j}{d_j^{T}A{d}_j},j=0,1,?,k?1.\end{array}\text{\hspace{1em}?}$$因此，只要按(5)取值 { β j } j = 0 k ? 1 \{\beta_j\}_{j=0}^{k-1} {βj?}j=0k?1?,向量组 $d_0,?,d_{k?1},d_k$ 就是彼此 (A) 共轭的.而且，根据命题 4.1中的$(i)$, 有 $?f(x_k{)}^T{d}_j=0,j=0,1,?,k?1$. 从而
$$?f(x_k{)}^T{d}_k=?\Vert ?f(x_k){\Vert }_2^2<0.$$因而，通过精确搜索可得 ${\alpha }_k>0$, 使得 $x_{k+1}=x_k+{\alpha }_k{d}_k$ 满足 $?f(x_{k+1}{)}^T{d}_k=0.$

进一步，若 $\Vert ?f(x_{k+1}){\Vert }_2\ge ?$, 重复上述过程，直至满足停止条件. 此算法利用梯度向量构造共轭向量组，故称之为共轭梯度法.

实际上，我们可以化简 { β j } \{\beta_{j}\} {βj?}的计算，首先根据目标函数的二次性可以知道:

$$\begin{array}{r}?f(x_{j+1})=?f(x_j)+{\alpha }_{j}A{d}_j,j=0,?,k?1.\end{array}\text{\hspace{1em}?}$$所以, 对 $0\le j\le k?2$，因为 $?f(x_j)=d_j$，有 A d j = α j ? 1 [ ? f ( x j + 1 ) ? ? f ( x j ) ] ∈ s p a n { d 0 , ? ? , d k ? 1 } . Ad_{j}=\alpha_{j}^{-1}[\nabla f(x_{j+1})-\nabla f(x_{j})]\in\mathbf{span}\{d_{0},\cdots,d_{k-1}\}. Adj?=αj?1?[?f(xj+1?)??f(xj?)]∈span{d0?,?,dk?1?}.再根据命题$命题4.1(i)$ 即$?f(x_k{)}^T{d}_j=0,j=0,?,k?1$，便可以得到 ? f ( x k ) ⊥ s p a n { d 0 , ? ? , d k ? 1 } \nabla f(x_k) \perp \mathbf{span}\{d_{0},\cdots,d_{k-1}\} ?f(xk?)⊥span{d0?,?,dk?1?},从而有 $?f(x_k{)}^{T}A{d}_j=0$，于是${\beta }_j=\frac{?f(x_k{)}^{T}A{d}_j}{d_j^{T}A{d}_j}=0$.

类似地，根据 $d_{k?1}$的定义式(4) $d_k:=??f(x_k)+{\sum }_{i=0}^{k?1}{\beta }_i{d}_i$，可以知道 ? f ( x k ? 1 ) = ? d k ? 1 + ∑ i = 0 k ? 1 β i d i = A x k ? 1 + b ∈ s p a n { d 0 , ? ? , d k ? 1 } \nabla f(x_{k-1})=-d_{k-1}+\sum_{i=0}^{k-1}\beta_id_i=Ax_{k-1}+b \in \mathbf{span}\{d_{0},\cdots,d_{k-1}\} ?f(xk?1?)=?dk?1?+∑i=0k?1?βi?di?=Axk?1?+b∈span{d0?,?,dk?1?}，所以有
A d k ? 1 = α k ? 1 ? 1 [ ? f ( x k ) ? ? f ( x k ? 1 ) ] ∈ α k ? 1 ? 1 ? f ( x k ) + s p a n { d 0 , ? ? , d k ? 1 } . Ad_{k-1}=\alpha_{k-1}^{-1}[\nabla f(x_k)-\nabla f(x_{k-1})]\in\alpha_{k-1}^{-1}\nabla f(x_k)+\mathbf{span}\{d_0,\cdots,d_{k-1}\}. Adk?1?=αk?1?1?[?f(xk?)??f(xk?1?)]∈αk?1?1??f(xk?)+span{d0?,?,dk?1?}.即 $?f(x_k{)}^{T}A{d}_{k?1}={\alpha }_{k?1}^{?1}\Vert ?f(x_k){\Vert }_2^2$，从而$${\beta }_{k?1}=\frac{\Vert ?f(x_k){\Vert }_2^2}{{\alpha }_{k?1}{d}_{k?1}^{T}A{d}_{k?1}}.$$根据最速下降法中的精确搜索公式即 ${\alpha }_k:=\underset{\alpha >0}{\mathrm{argmin}}f(x_k+\alpha d_k)=?\frac{(A{x}_k+b{)}^T{d}_k}{d_k^{T}A{d}_k}=?\frac{?f(x_k{)}^T{d}_k}{d_k^{T}A{d}_k}$，可以得到$${\alpha }_{k?1}=?\frac{?f(x_{k?1}{)}^T{d}_{k?1}}{d_{k?1}^{T}A{d}_{k?1}}$$ 又因为有 $?f(x_{k?1}{)}^T{d}_{k?1}=?\Vert ?f(x_{k?1}){\Vert }_2^2$，所以$${\beta }_{k?1}=\frac{\Vert ?f(x_k){\Vert }_2^2}{\Vert ?f(x_{k?1}){\Vert }_2^2}$$以上便是 { β j } \{\beta_j\} {βj?}的一种简化方法，这种方法称为Flecther-Reeves方法，简称为 F-R方法，实际上还有很多的关于待定系数 { β j } \{\beta_j\} {βj?}的求法，在此不加证明指出各种求解待定系数的方法在函数为二次型，且使用精准线搜时完全等价.当然这里也列举一些，供读者查阅，各种方法如下所示（一般情况下，很多文章会以记号 $g_k$ 来代替 $f(x_k)$）
$$\begin{array}{rl}{\beta }_{k?1}^{HS}& =\frac{?f(x_k{)}^{T}A?f(x_{k?1})}{d_{k?1}^{T}A{d}_{k?1}}\text{(Hestenes}?\text{Stiefel公式)}\\ {\beta }_{k?1}^{CW}& =\frac{?f(x_k{)}^T(?f(x_k)??f(x_{k?1}))}{d_{k?1}^T(?f(x_k)??f(x_{k?1}))}(\text{Crowder}?\text{Wolfe公式})\\ {\beta }_{k?1}^{FR}& =\frac{?f(x_k{)}^T?f(x_k)}{?f(x_{k?1}{)}^T?f(x_{k?1})}(\mathbf{F}\text{letcher}?\mathbf{R}\text{eeves公式})\\ {\beta }_{k?1}^D& =?\frac{?f(x_k{)}^T?f(x_k)}{d_{k?1}^T?f(x_{k?1})}\text{(Dixon公式)}\\ {\beta }_{k?1}^{PRl}& {}^P=\frac{?f(x_k{)}^T(?f(x_k)??f(x_{k?1}))}{?f(x_{k?1}{)}^T?f(x_{k?1})}(\mathbf{Polak}?\mathbf{Ribiere}?\mathbf{Polyak}\text{公式})\\ {\beta }_{k?1}^{DY}& =\frac{?f(x_k{)}^T?f(x_k)}{d_{k?1}^T(?f(x_k)??f(x_{k?1}))}(\mathbf{Dai}?\mathbf{Yuan}\text{公式})\end{array}$$

4.3 共轭梯度法的程序实现

现在总结一下，目标函数为二次型，基于F-R方法的共轭梯度算法如下：
算法 4.1 (共轭梯度法) 取充分小的数 $?>0.$

第 $1$ 步：任取 $x_0\in {\mathbb{R}}^n$,令 $k=0.$

第 $2$ 步：若$\Vert ?f(x_k)\Vert <?$,转第 $4$ 步；否则，令 $$d_k:=\begin{array}{r}\{\begin{array}{ll}??f(x_k)& k=0,\\ ??f(x_k)+{\beta }_{k?1}{d}_{k?1}& k\ge 1,\end{array}\text{其中}{\beta }_{k?1}:=\frac{\Vert ?f(x_k){\Vert }^2}{\Vert ?f(x_{k?1}){\Vert }^2}\end{array}\text{\hspace{1em}?}$$

第 $3$ 步：通过精确搜索计算 $x_{k+1}=x_k+{\alpha }_k{d}_k$,其中$${\alpha }_k=\frac{\Vert ?f(x_k){\Vert }_2^2}{d_k^{T}A{d}_k}$$并计算 $?f(x_{k+1}):=A{x}_{k+1}+b$.令 $k=k+1$,转第 $2$ 步.

第 $4$ 步：输出极小值点 $x_k$. 程序结束.

设需要最小化的目标二次函数如下：$$f(x)=\frac{1}{2}{x}^{T}Ax+b^{T}x,Q=\left(\begin{array}{cc}3& ?1\\ ?1& 1\end{array}\right),b=(2,0{)}^T$$即$$\min f(x)=\frac{3}{2}{x}_1^2+\frac{1}{2}{x}_2^2?x_1{x}_2?2x_1$$为了检验迭代过程的可靠性，我们可以解析地求出该优化问题的最优点：$$x^{?}=?A^{?1}b=(1,1{)}^T$$此外我们还需要定义目标函数中的 $A,b$ 还有原本的函数 $f$ 和函数梯度 $?f$ 的映射func和gradient.准备工作部分的代码如下：

# 准备工作
import numpy as np
import matplotlib.pyplot as plt

A = np.array([[3, -1], [-1, 1]], dtype="float32") # 定义矩阵 A
b = np.array([-2, 0], dtype="float32").reshape([-1, 1]) # 向量b
# function and its gradient defined in the question
func = lambda x: 0.5 * np.dot(x.T, np.dot(A, x)).squeeze() + np.dot(b.T, x).squeeze() # 函数
gradient = lambda x: np.dot(A, x) + b # 梯度
x_0 = np.array([1, 1]).reshape([-1, 1]) # 最优点x_0

准备工作完成后，编写基于精确搜索的最速下降法的函数实现：

# FGCG algorithm
def FGCG(start_point, func, gradient, epsilon=0.01):
    """
    :param start_point: start point of GD 初始值
    :param func: map of plain function 目标函数
    :param gradient: gradient map of plain function 梯度函数
    :param epsilon: threshold to stop the iteration 迭代终止的阈值
    :return: converge point, # iterations
    """
    assert isinstance(start_point, np.ndarray)  # assert that input start point is ndarray
    global Q, b, x_0  # claim the global varience
    x_k_1, iter_num, loss = start_point, 0, []
    xs = [x_k_1]  # xs是迭代点的序列，最后一个就是最后一次求的点

    # 初始化
    g_k_list = []  # g_k = delta f(x_k)，改变用来储存梯度向量
    g_k_list.append(gradient(start_point).reshape([-1, 1]))
    d_k_list = []  # 储存搜索方向的list
    d_k_list.append(-gradient(start_point).reshape([-1, 1]))

    while True:
        g_k = g_k_list[iter_num]
        d_k = d_k_list[iter_num]
        if np.sqrt(np.sum(g_k ** 2)) < epsilon:  # 终止条件(1)
            break
        if len(g_k) > 1:
            g_k_1 = g_k_list[iter_num-1]  # 取出delta f_x_{k-1}
            beta = np.sum(g_k ** 2) / np.sum(g_k_1 ** 2)
            d_current = -g_k + beta * d_k # 当前迭代的搜索方向d_k
            d_k = d_current
            d_k_list.append(d_k)
        alpha_k = np.dot(g_k.T, g_k).squeeze() / (np.dot(d_k.T, np.dot(A, d_k))).squeeze() # 精确搜索计算步长alpha_k
        x_k_2 = x_k_1 + alpha_k * d_k # 迭代式
        iter_num += 1
        xs.append(x_k_2) 
        g_k_list.append(gradient(x_k_2).reshape([-1, 1])) # 计算delta f(x_{k+1}=Ax_{k+1}+b)
        loss.append(float(np.fabs(func(x_k_2) - func(x_0))))
        if np.fabs(func(x_k_2) - func(x_k_1)) < epsilon:
            break
        if iter_num > 100: # 超过一定次数后停止迭代
            break
        x_k_1 = x_k_2
    return xs, iter_num, loss

假设此处的迭代初值为? $x_0=(4,5{)}^T$ ，进行梯度下降法，并可视化迭代过程：

x0 = np.array([4,5], dtype="float32").reshape([-1, 1]) # 定义初始值
xs, iter_num, loss = gradient_descent(start_point=x0,
                                     func=func,
                                     gradient=gradient,
                                     epsilon=1e-6) # 传入参数
print(xs[-1])	# last point of the sequence 输出迭代点列的最后一个值
plt.style.use("seaborn") # 样式
plt.figure(figsize=[12, 6]) # 图像大小
plt.plot(loss)
plt.xlabel("# iteration", fontsize=12)
plt.ylabel("Loss: $|f(x_k) - f(x^*)|$", fontsize=12)
plt.yscale("log")
plt.show()

def text_plot():
    # 画出点图
    print(xs[-1])	# last point of the sequence 输出迭代点列的最后一个值
    x = []
    y = []
    for i in xs:
        x.append( i[0]) 
        y.append( i[1]) 
    plt.style.use("seaborn") # 样式
    plt.figure(figsize=[12, 6]) # 图像大小
    plt.plot(x,y)
    plt.xlabel("x", fontsize=12)
    plt.ylabel("y", fontsize=12)
    # plt.yscale("log")
    plt.show()

运行结果：

[[0.9999299]
 [1.0005273]]

可以看到最终迭代点到达了最优点 $(1,1{)}^T$。当纵坐标取对数 $log$ 时，loss是在不断下降的。我们再更换几组初始点，并把相关的参数画在一个图像内看看效果.

我们再取四个迭代点：?$(0,0),(0.4,0),(10,0),(11,0)$

# create the list of all starting point x_0
starting_points = [np.array([num, 0]).astype(np.float).reshape([-1, 1]) for num in [0.0, 0.4, 10.0, 11.0]]

plt.figure(dpi=150)

xss = []
# implement FGCG
for idx, start_point in enumerate(starting_points):
    xs, iter_num, losses = gradient_descent(start_point, func, gradient, epsilon=1e-6)
    target_point = xs[-1]
    xss.append(xs)
    # plot the losses of $|f(x_k) - f(x^*)|$
    plt.plot(np.arange(len(losses)), np.array(losses), label=f"start point: ({start_point[0][0]}, {start_point[1][0]})")

    loss = np.fabs(func(target_point) - func(x_0))
    print(f"{idx + 1}: start point:{np.round(start_point, 5).tolist()}, "
          f"point after GD:{np.round(target_point, 5).tolist()}, "
          f"loss:{np.round(loss, 16)}, # iterations: {iter_num}")
    print("-" * 60)

plt.grid(True)
plt.legend()
plt.xlabel("# iteration", fontsize=12)
plt.ylabel("Loss: $|f(x_k) - f(x^*)|$", fontsize=12)
plt.yscale("log")
plt.title("Loss-iteration given to different starting points of GD", fontsize=18)
plt.show()

输出结果：

1: start point:[[0.0], [0.0]], point after FGCG:[[0.99964], [0.99972]], loss:1.324470967e-07, # iterations: 19
------------------------------------------------------------
2: start point:[[0.4], [0.0]], point after FGCG:[[0.99978], [0.99922]], loss:2.053100269e-07, # iterations: 17
------------------------------------------------------------
3: start point:[[10.0], [0.0]], point after FGCG:[[0.9998], [1.00051]], loss:2.990393975e-07, # iterations: 19
------------------------------------------------------------
4: start point:[[11.0], [0.0]], point after FGCG:[[0.9998], [1.00062]], loss:3.793825739e-07, # iterations: 19
------------------------------------------------------------

由上图可以看到可以看到不同的初值点，收敛速率并不像最速下降法一样显著不相同。也就是说不同的初始点到达最优点的所需的迭代次数基本是相同的.下面把上述过程在二维平面内可视化出来：

plt.figure(dpi=150)
X = np.linspace(-2, 12, 200)
Y = np.linspace(-2, 12, 200)
XX, YY = np.meshgrid(X, Y)
Z = [func(np.array([XX[i, j], YY[i, j]], dtype="float32").reshape([-1, 1])).tolist() for i in range(200) for j in range(200)]
Z = np.array(Z).reshape([200, 200])
plt.contourf(XX, YY, Z, cmap=plt.cm.BuGn)

plt.annotate(f"$(5.0, 6.0)$",
                 xy=(5, 6),
                 xytext=(5 - 2, 6 + 2),
                 arrowprops={
                     "color" : "black",
                     "shrink" : 0.1,
                     "width" : 0.6
                 })

# plot the scatter
for idx, start_point in enumerate(starting_points):
    xx = [xss[idx][i][0] for i, _ in enumerate(xss[idx])]
    yy = [xss[idx][i][1] for i, _ in enumerate(xss[idx])]
    plt.plot(xx, yy, "o--", label=f"start point: ({start_point[0][0]}, {start_point[1][0]})")
    # add some tips for start point
    plt.annotate(f"$({start_point[0][0]}, {start_point[1][0]})$",
                 xy=(start_point[0][0], start_point[1][0]),
                 xytext=(start_point[0][0] - 1.5, start_point[1][0] + idx + 2),
                 arrowprops={
                     "color" : "black",
                     "shrink" : 0.1,
                     "width" : 0.6
                 })

plt.grid(True)
plt.title("FGCG For Two-dimensional Diagrams", fontsize=18)
plt.xlabel("$x_1$", fontsize=12)
plt.ylabel("$x_2$", fontsize=12)
plt.legend()
plt.show()

运行结果：

这张图可以直观地感受四个迭代点的迭代步数并没有显著的差距。究其原因，由于共轭梯度法中关于搜索方向的选择基本是一致的，所以初始点的选择对于迭代过程的影响很小，接下来我们看看非二次函数的共轭梯度法的以及F-R方法收敛性的证明.

4.4 非二次函数的共轭梯度法

共轭梯度法的迭代公式
$$\begin{array}{r}{d}_0:=??f(x_0),d_k:=??f(x_k)+{\beta }_{k?1}{d}_{k?1},{\beta }_{k?1}:=\frac{\Vert ?f(x_k){\Vert }_2^2}{\Vert ?f(x_{k?1}){\Vert }_2^2}\end{array}\text{\hspace{1em}?}$$中不含有矩阵 $A$，这说明当目标函数不是二次函数时，形式上基于F-G方法的共轭梯度法仍然可用而且当线搜索采用精确搜索时，它具有二次终止性.下面我们研究共轭梯度法公式(8)对于非二次函数的收敛性.对于一般的目标函数 $f(x)$ 求精确搜索 $x_{k+1}=x_k+{\alpha }_k{d}_k$ 本身也是一个优化问题，且该优化问题具有较大的计算复杂性，所以，下面我们将步长的确定不限于精确搜索.

我们在之前的学习笔记中说到过，线搜索迭代方法的收敛的一个关键条件是所谓的一致锐角条件：记 $g_k:=?f(x_k)$，$g_k^T{d}_k=\Vert g_k{\Vert }_2\cos {\theta }_k\ge \Vert g_k{\Vert }_2\cos (\frac{\pi }{2}?\mu )=\Vert g_k{\Vert }_2\sin \mu$，于是 $g_k^T{d}_k\ge \Vert g_k{\Vert }_2\sin \mu$或较
弱一点的条件：若 $\Vert ?f(x_k){\Vert }_2\ne 0,?k\ge 0$, 且满足条件 ${\sum }_{k=1}^{\infty }{\cos }^2{\theta }_k=\infty .$

为此我们看看如下的引理

引理 4.2 设 $f\in C^1({\mathbb{R}}^n),x_0\in {\mathbb{R}}^n,\Vert ?f(x_0)\Vert \ne 0$. 设 $d_k$ 由共轭梯度法公式(8)求得，线搜索 $x_k=x_{k?1}+{\alpha }_{k?1}{d}_{k?1}$,满足
$$\begin{array}{r}\Vert ?f(x_j)\Vert \ne 0,|?f(x_j{)}^T{d}_{j?1}|\le ?\sigma ?f(x_{j?1}{)}^T{d}_{j?1},j=1,?,k,\end{array}\text{\hspace{1em}?}$$其中 $\sigma \in [0,1)$，那么$$\begin{array}{r}\frac{1?2\sigma }{1?\sigma }\Vert ?f(x_k){\Vert }^2\le ??f(x_k{)}^T{d}_k\le \frac{1}{1?\sigma }\Vert ?f(x_k){\Vert }^2,k=1,2,?\end{array}\text{\hspace{1em}?}$$且有$$\begin{array}{r}\frac{\Vert ?f(x_k){\Vert }^4}{\Vert d_k{\Vert }^2}\ge \frac{1?\sigma }{1+\sigma }(\sum _{j=0}^k\Vert ?f(x_j){\Vert }^{?2}{)}^{?1}.\end{array}\text{\hspace{1em}?}$$

证. 记 $g_k:=?f(x_k),k=0,1,?$. 先证(10). 不妨设 $\Vert g_k\Vert \ne 0$. 等式 $d_k=$ $?g_k+{\beta }_{k?1}{d}_{k?1}$ 两边与 $g_k$ 做内积，得$$|g_k^T{d}_k+g_k^T{g}_k|={\beta }_{k?1}|g_k^T{d}_{k?1}|\le ?\sigma {\beta }_{k?1}{g}_{k?1}^T{d}_{k?1}=?\sigma \frac{(g_k^T{g}_k)(g_{k?1}^T{d}_{k?1})}{g_{k?1}^T{g}_{k?1}}.$$即$$\left|\frac{g_k^T{d}_k}{g_k^T{g}_k}+1\right|\le ?\sigma \frac{g_{k?1}^T{d}_{k?1}}{g_{k?1}^T{g}_{k?1}}=\sigma ?\sigma \left(\frac{g_{k?1}^T{d}_{k?1}}{g_{k?1}^T{g}_{k?1}}+1\right)\le \sigma +\sigma \left|\frac{g_{k?1}^T{d}_{k?1}}{g_{k?1}^T{g}_{k?1}}+1\right|.$$据此递推关系，并注意到 $g_0^T{d}_0/(g_0^T{g}_0)+1=0$, 可得

$$\left|\frac{g_k^T{d}_k}{g_k^T{g}_k}+1\right|\le \sigma +{\sigma }^2+?+{\sigma }^k=\frac{\sigma }{1?\sigma }.$$将不等式(10)化简即发现和该式等价.

下面证明不等式$(11).k=0$ 时有 $d_0=??f(x_0)$, 不等式显然成立. 下面设 $k\ge 1$, 并假设不等式(11)对 $k?1$ 成立. 利用(8)得 (注意，由于未必是精确搜索，条件$g_k^T{d}_{k?1}=0$ 不一定成立)$$\begin{array}{rl}\Vert d_k{\Vert }_2^2& =\Vert g_k{\Vert }_2^2+{\beta }_{k?1}^2\Vert d_{k?1}{\Vert }_2^2?2{\beta }_{k?1}{g}_k^T{d}_{k?1}\\ & \le \Vert g_k{\Vert }_2^2+{\beta }_{k?1}^2\Vert d_{k?1}{\Vert }_2^2?2\sigma {\beta }_{k?1}{g}_{k?1}^T{d}_{k?1}\\ & =\Vert g_k{\Vert }_2^2+{\left(\frac{\Vert g_k{\Vert }_2}{\Vert g_{k?1}{\Vert }_2}\right)}^4\Vert d_{k?1}{\Vert }_2^2?2\sigma (\frac{\Vert g_k{\Vert }_2}{\Vert g_{k?1}{\Vert }_2}{)}^2{g}_{k?1}^T{d}_{k?1}.\end{array}$$利用 $k?1$ 情形的不等式(10),得 $g_{k?1}^T{d}_{k?1}\le \frac{1}{1?\sigma }\Vert g_{k?1}{\Vert }_2^2$.代入上式，有$$\Vert d_k{\Vert }_2^2\le \frac{1+\sigma }{1?\sigma }\Vert g_k{\Vert }_2^2+\Vert g_k{\Vert }_2^4?\frac{\Vert d_{k?1}{\Vert }_2^2}{\Vert g_{k?1}{\Vert }_2^4}.$$
根据 $k?1$ 情形的归纳假设，得
$$\Vert d_k{\Vert }_2^2\le \frac{1+\sigma }{1?\sigma }\Vert g_k{\Vert }_2^2+\Vert g_k{\Vert }_2^4\frac{1+\sigma }{1?\sigma }\sum _{j=0}^{k?1}\Vert g_j{\Vert }_2^{?2}=\frac{1+\sigma }{1?\sigma }\Vert g_k{\Vert }_2^4\sum _{j=0}^k\Vert g_j{\Vert }_2^{?2}.$$ 所以，不等式(11)对 $k$ 成立.引理证毕.
注：显然，精确搜索和强 Wolfe 搜索均满足条件
$$\begin{array}{r}|?f(x_k{)}^T{d}_{k?1}|\le ?\sigma ?f(x_{k?1}{)}^T{d}_{k?1},\sigma \in [0,1).\end{array}$$

命题 4.3 (F-R 方法的收敛性) 设 $f\in C^1({\mathbb{R}}^n)$ 有下界，$x_0\in {\mathbb{R}}^n$, 梯度向量 $?f(x)$ 在包含水平集 lev${}_{f(x_0)}(f)$ 的一个凸集 $D$ 上 $Lipschitz$ 连续. 设 $d_k$ 由共轭梯度法公式(8.4.8)求得，线搜索 $x_k=x_{k?1}+{\alpha }_{k?1}{d}_{k?1}$ 为精确搜索或参数 $\sigma \in [0,1/2)$ 的强 $Wolfe$ 搜索，那么，或者存在 $k\ge 0$,使得 $\Vert ?f(x_k){\Vert }_2=0$,或者 $\underline{{\lim }_{k\to \infty }\Vert ?f(x_k){\Vert }_2}=0.$

证. 若结论不成立，则存在 $\delta >0$,使得 $\Vert ?f(x_j){\Vert }_2\ge \delta ,?j\ge 0$. 对任意的 $k\ge 0$,利用引理 4.2之结论 (10)可知 $??f(x_k)$ 与 $d_k$ 的夹角余弦满足
$$\Vert ?f(x_k){\Vert }_2^2{\cos }^2{\theta }_k\ge {\left(\frac{1?2\sigma }{1?\sigma }\right)}^2\frac{\Vert ?f(x_k){\Vert }_2^4}{\Vert d_k{\Vert }_2^2}.$$进一步，利用(11)可得
$$\frac{\Vert ?f(x_k){\Vert }_2^4}{\Vert d_k{\Vert }_2^2}\ge \frac{1?\sigma }{1+\sigma }(\sum _{j=0}^k\Vert ?f(x_j){\Vert }_2^{?2}{)}^{?1}\ge \frac{1?\sigma }{1+\sigma }?\frac{{\delta }^2}{k+1}.$$所以 ${\sum }_{k=0}^{\infty }\Vert ?f(x_k){\Vert }_2^2{\cos }^2{\theta }_k=\infty .$

另一方面，由强 Wolfe 准则 $|?f(x_{k+1}{)}^T{d}_k|\le ?\sigma ?f(x_k{)}^T{d}_k$ 可知 $?f(x_k{)}^T{d}_k<0$.根据命题 2.2.4我们有 ${\sum }_{k=0}^{\infty }\Vert ?f(x_k){\Vert }_2^2{\cos }^2{\theta }_k<\infty$，矛盾.

Reference

本笔记内容的程序实现部分参考如下了文章：
最优化方法复习笔记（一）梯度下降法、精确线搜索与非精确线搜索（推导+程序）