引言

上一节介绍了共轭方向法的朴素思想与几何意义。本节将继续介绍共轭方向法的重要特征以及相关证明。

回顾：共轭方向法的思想与几何解释

共轭方向法的基本思想是：针对凸二次函数的优化问题：$\begin{array}{r}\min f(x)=\frac{1}{2}{x}^T\mathcal{Q}x+{\mathcal{C}}^{T}x,\mathcal{Q}\succ 0\end{array}$，基于正定矩阵$\mathcal{Q}$，构建一个由两两共轭的向量组成的向量组 D = { d 0 , d 1 , ⋯ , d n − 1 } \mathcal D = \{d_0,d_1,\cdots,d_{n-1}\} D={d0​,d1​,⋯,dn−1​}：
$$\forall d_i,d_j\in \mathcal{D};i\ne j\Rightarrow (d_i{)}^T\mathcal{Q}{d}_j=0$$
并令：
$$x_{k+1}=x_k+\sum _{i=0}^{n-1}{\alpha }_i\cdot d_i$$
其中${\alpha }_i(i=0,1,2,\cdots ,n-1)$满足：
$${\alpha }_i=\underset{\alpha }{\mathrm{argmin}}\varphi (\alpha )=\underset{\alpha }{\mathrm{argmin}}f(x_k+\alpha \cdot d_i)$$
从而通过坐标轴交替下降法执行$n$次迭代，完成一次线搜索过程。

从几何意义的角度解释：记$\mathcal{S}=(d_0,d_1,\cdots ,d_{n-1}{)}_{n\times n}$。根据共轭方向的定义，必然有${\mathcal{S}}^T\mathcal{Q}\mathcal{S}$是一个对角矩阵：
$$\{\begin{array}{l}(d_i{)}^T\mathcal{Q}{d}_j=0\forall d_i,d_j\in \mathcal{S};i\ne j\\ \\ {\mathcal{S}}^T\mathcal{Q}\mathcal{S}=[(d_i{)}^T\mathcal{Q}{d}_j{]}_{n\times n}=\left[\begin{array}{cccc}(d_1{)}^T\mathcal{Q}{d}_1& 0& \cdots & 0\\ 0& (d_2{)}^T\mathcal{Q}{d}_2& \cdots & 0\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \cdots & (d_{n-1}{)}^T\mathcal{Q}{d}_{n-1}\end{array}\right]=\Lambda \end{array}$$
根据这个性质，可以对正定矩阵$\mathcal{Q}$进行对角化，从而将$f(x)$变成一个标准型。具体方法如下：

• 由于$d_0,d_1,\cdots ,d_{n-1}$向量两两共轭，必然也是两两线性无关。因而矩阵$\mathcal{S}$是一个可逆矩阵。对决策变量$x\in {\mathbb{R}}^n$使用$\mathcal{S}$进行投影，得到新的向量$\hat{x}$；从而将$f(x)$变成关于$\hat{x}$的函数形式$\hat{f}(\hat{x})$：
  $$\{\begin{array}{l}x=\mathcal{S}\cdot \hat{x}\iff \hat{x}={\mathcal{S}}^{-1}x\\ \\ \begin{array}{rl}f(x)& =\frac{1}{2}{x}^T\mathcal{Q}x+{\mathcal{C}}^{T}x\\ & =\frac{1}{2}[\hat{x}{]}^T{\mathcal{S}}^T\mathcal{Q}\mathcal{S}\cdot \hat{x}+({\mathcal{S}}^T\mathcal{C}{)}^{T}x=\hat{f}(\hat{x})\end{array}\end{array}$$
• 此时的$\hat{f}(\hat{x})$是一个标准型。对应的，将线搜索过程中的数值解使用$\mathcal{S}$进行投影，可以得到如下结果：
  $$\{\begin{array}{l}{\hat{x}}_k={\mathcal{S}}^{-1}{x}_k\\ \begin{array}{rl}{\hat{x}}_{k+1}& ={\mathcal{S}}^{-1}{x}_{k+1}\\ & ={\mathcal{S}}^{-1}\left(x_k+\sum _{i=0}^{n-1}{\alpha }_i\cdot d_i\right)\\ & ={\mathcal{S}}^{-1}{x}_k+\sum _{i=0}^{n-1}{\alpha }_i\cdot {\mathcal{S}}^{-1}{d}_i\end{array}\end{array}$$
  由于${\mathcal{S}}^{-1}\mathcal{S}=\mathcal{I}$，从而${\mathcal{S}}^{-1}{d}_i(i=0,1,\cdots ,n-1)$表示单位坐标向量$e_{i+1}$。将其代入有：
  $$x_{k+1}=x_k+\sum _{i=0}^{n-1}{\alpha }_i\cdot d_i\iff {\hat{x}}_{k+1}={\hat{x}}_k+\sum _{i=0}^{n-1}{\alpha }_i\cdot e_{i+1}$$
  最终可用坐标轴交替下降法对数值解序列进行求解。上述算法的关键在于：该算法必须在共轭方向$d_0,d_1,\cdots ,d_{n-1}$已知的条件下。本节将重点介绍：如何获取共轭方向$d_i$。

共轭方向法的重要特征(2023/9/12)

由于$\begin{array}{r}f(x)=\frac{1}{2}{x}^T\mathcal{Q}x+{\mathcal{C}}^{T}x,\mathcal{Q}\succ 0\end{array}$是凸二次函数，基于初始点$x_0$以及关于正交矩阵$\mathcal{Q}$的共轭方向$d_k(k=0,1,2,\cdots ,n-1)$，算法的线搜索过程以及各迭代步骤的最优步长${\alpha }_k(k=0,1,2,\cdots ,n-1)$表示如下：
$$\{\begin{array}{l}{x}_{k+1}=x_k+{\alpha }_k\cdot d_k\\ \\ \begin{array}{r}{\alpha }_k=-\frac{[\nabla f(x_k){]}^T{d}_k}{(d_k{)}^T\mathcal{Q}{d}_k}k=0,1,2,\cdots ,n-1\end{array}\end{array}$$
这里需要做一些说明。上面的描述是文章下面链接中视频的描述(37:25)。很明显，它将线搜索迭代过程的下标$k$与共轭方向迭代过程的下标$i$全部归为下标$k$,真实情况应该是下面描述：
$$\{\begin{array}{l}{x}_{k+1}=x_k+{\alpha }_i\cdot d_i\\ \\ \begin{array}{r}{\alpha }_i=-\frac{[\nabla f(x_k){]}^T{d}_i}{(d_i{)}^T\mathcal{Q}{d}_i}\end{array}\end{array}\{\begin{array}{l}i=0,1,2,\cdots ,n-1\\ k=0,1,2,\cdots ,\infty \end{array}$$
从这组公式可以看出：只有决策变量$x_k\in {\mathbb{R}}^n$各分量均迭代一次后，$x_k\Rightarrow x_{k+1}$。但视频中的写法也没有错，因为凸二次函数$f(x)$可以通过一步$k:0\Rightarrow 1$即可完成迭代。而这一步存在$n$次迭代，因而在该简单情况下，视频中将下标$i,k$合并，并描述成$n$次迭代。这样做的好处在于：第$k$次迭代描述的是共轭方向$d_k$的迭代过程。后续均使用视频中的方式进行描述。

基于上面描述产生的数值解序列 { x k } k = 1 n \{x_k\}_{k=1}^{n} {xk​}k=1n​具有如下特征：

• 在第$k(k=1,2,\cdots ,n)$次迭代产生的迭代结果$x_k$，其梯度方向$\nabla f(x_k)$与之前使用过的共轭方向$d_i(i=0,1,\cdots ,k-1)$均垂直：
  $$[\nabla f(x_k){]}^T{d}_i=0i=0,1,2,\cdots ,k-1$$
  对应示例图像表示如下：
  很明显，从初始点$x^{(0)}$开始，沿着共轭方向$d^{(1)}$更新至$x^{(1)}$;其中$\nabla f(x^{(1)})$描述方向与$d^{(1)}$描述方向相垂直;由于$x^{(2)}$是最优解，其$\nabla f(x^{(2)})=0$。从而与$d^{(1)},d^{(2)}$均垂直。
  

• 经过$k$次迭代得到的位置$x_k=x_0+{\sum }_{i=0}^{k-1}{\alpha }_i\cdot d_i$，可以将该结果描述为如下形式：
  $$\{\begin{array}{l}\begin{array}{rl}& x_k=\mathrm{argmin}\left\{\frac{1}{2}{x}^T\mathcal{Q}x+{\mathcal{C}}^{T}x\mid x\in {\mathcal{X}}_k\right\}\\ & {\mathcal{X}}_k=\left\{x_0+\sum _{i=0}^{k-1}{\alpha }_i\cdot d_i\mid {\alpha }_i\in \mathbb{R}\right\}\end{array}\end{array}$$
  说明：

  • 关于$x_k$对应的可选择范围${\mathcal{X}}_k$,其对应的共轭方向$d_0,\cdots ,d_{k-1}$并未出现调整，只是将对应的步长${\alpha }_0,\cdots ,{\alpha }_{k-1}$均作为变量，从而构成位置空间${\mathcal{X}}_k$,而$x_k$是位置空间中使目标函数$f(x)$最小的位置点。
  • 当$k=n$时，此时对应的位置空间${\mathcal{X}}_n$就是完整的特征空间${\mathbb{R}}^n$。当然，这里描述的完整特征空间是由共轭方向$d_0,d_1,\cdots ,d_n$构成的投影空间，而不是原始特征空间。
    $$\begin{array}{r}{x}_n=\mathrm{argmin}\left\{\frac{1}{2}{x}^T\mathcal{Q}x+{\mathcal{C}}^{T}x\mid x\in {\mathbb{R}}^n\right\}\end{array}$$

  根据上式可以看出，关于$f(x)$必然可以通过最多$n$步找到最优解。

共轭方向法重要特征的证明

关于$[\nabla f(x_k){]}^T{d}_i(i=1,2,\cdots ,k-1)$的证明：

• 当$i=k-1$时，对应迭代步骤的步长${\alpha }_{k-1}$可表示为：
  该式中仅包含$\alpha$一个变量，记作${\varphi }_{k-1}(\alpha )$。
  $${\alpha }_{k-1}=\underset{\alpha }{\mathrm{argmin}}f(x_{k-1}+\alpha \cdot d_{k-1})=\underset{\alpha }{\mathrm{argmin}}{\varphi }_{k-1}(\alpha )$$
  上式可等价为：
  根据线搜索公式：$x_k=x_{k-1}+{\alpha }_{k-1}\cdot d_{k-1}$可知$\nabla f(x_{k-1}+{\alpha }_{k-1}\cdot d_{k-1})$就是函数$f(\cdot )$在$x_k$处的梯度：$\nabla f(x_k)$。
  $$\begin{array}{rl}0& \triangleq \nabla {\varphi }_{k-1}({\alpha }_{k-1})\\ & =\frac{\partial {\varphi }_{k-1}(\alpha )}{\partial \alpha }{\mid }_{\alpha ={\alpha }_{k-1}}\\ & =[\nabla f(x_{k-1}+{\alpha }_{k-1}\cdot d_{k-1}){]}^T{d}_{k-1}\\ & =[\nabla f(x_k){]}^T{d}_{k-1}\end{array}$$
  可以看出：第$k-1$次迭代产生的输出位置$x_k$，其梯度$\nabla f(x_k)$与$k-1$次迭代使用的共轭方向$d_{k-1}$垂直。同理：当$k=1,2,\cdots ,n$时，该结论均成立。

• 上面仅仅是描述：同一次迭代，其产生的输出位置与共轭方向之间是垂直关系；若非同一次迭代，观察内积$[\nabla f(x_k){]}^T{d}_i(i=0,1,2,\cdots ,k-2)$：

  • 将$\nabla f(x_k)=\mathcal{Q}{x}_k+\mathcal{C}$代入。
  • 将$x_k$视作从第$i+1$次迭代开始，一直到$k-1$次迭代产生的输出位置。这里可能并没有取出所有的迭代步骤，仅选择从$i+1$到$k-1$这一迭代部分。对应线搜索过程表示如下：
    $$x_k=x_{i+1}+{\alpha }_{i+1}\cdot d_{i+1}+\cdots +{\alpha }_{k-1}\cdot d_{k-1}$$
  • 根据向量共轭的定义：$\forall d_i,d_j\in \mathcal{D};i\ne j\Rightarrow (d_i{)}^T\mathcal{Q}{d}_j=0$，消除掉展开式中的无关项;$i+1,\cdots ,k-1\ne i$恒成立；且${\mathcal{Q}}^T=\mathcal{Q}$。
    $$\begin{array}{rl}[\nabla f(x_k){]}^T{d}_i& =(\mathcal{Q}{x}_k+\mathcal{C}{)}^T{d}_i\\ & =[\mathcal{Q}(x_{i+1}+{\alpha }_{i+1}\cdot d_{i+1}+\cdots +{\alpha }_{k-1}{d}_{k-1})+\mathcal{C}{]}^T{d}_i\\ & =[\mathcal{Q}{x}_{i+1}+{\alpha }_{i+1}\mathcal{Q}\cdot d_{i+1}+\cdots +{\alpha }_{k-1}\mathcal{Q}\cdot d_{k-1}+\mathcal{C}{]}^T{d}_i\\ & =[\mathcal{Q}{x}_{i+1}{]}^T{d}_i+\underset{=0}{\underbrace{{\alpha }_{i+1}(d_{i+1}{)}^T{\mathcal{Q}}^T{d}_i}}+\cdots +\underset{=0}{\underbrace{{\alpha }_{k-1}(d_{k-1}{)}^T{\mathcal{Q}}^T{d}_i}}+{\mathcal{C}}^T{d}_i\\ & =[\mathcal{Q}{x}_{i+1}+\mathcal{C}{]}^T{d}_i\\ & =[\nabla f(x_{i+1}){]}^T{d}_i\end{array}$$

  当$i=k-1$时，上面已经证明过，因而有：$$[\nabla f(x_{i+1}){]}^T{d}_i=0$$
  从而得到结论：即便不是同一次迭代，其迭代产生位置的梯度$\nabla f(x_k)$与使用过的共轭方向$d_0,d_1,\cdots ,d_{k-1}$同样存在垂直关系。

关于$\{\begin{array}{l}\begin{array}{rl}& x_k=\mathrm{argmin}\left\{\frac{1}{2}{x}^T\mathcal{Q}x+{\mathcal{C}}^{T}x\mid x\in {\mathcal{X}}_k\right\}\\ & {\mathcal{X}}_k=\left\{x_0+\sum _{i=0}^{k-1}{\alpha }_i\cdot d_i\mid {\alpha }_i\in \mathbb{R},i=1,2,\cdots ,k-1\right\}\end{array}\end{array}$的证明：

• 将$x_k$使用线搜索公式进行表述：
  $$\begin{array}{rl}{x}_k& =\underset{x_2}{\underbrace{\underset{x_1}{\underbrace{x_0+{\alpha }_0\cdot d_0}}+{\alpha }_1\cdot d_1}}+\cdots +{\alpha }_{k-1}\cdot d_{k-1}\\ & =x_0+\sum _{i=0}^{k-1}{\alpha }_i\cdot d_i\end{array}$$
  如果${\alpha }_0,{\alpha }_1,\cdots ,{\alpha }_{k-1}$均视作各迭代步骤中的变量，并且$x_0,d_i(i=0,1,\cdots ,k-1)$均是已知项，从而可以将$f(x_k)$表示为仅关于${\alpha }_0,{\alpha }_1,\cdots ,{\alpha }_{k-1}$的函数$\varphi ({\alpha }_0,{\alpha }_1,\cdots ,{\alpha }_{k-1})$：
  $$\begin{array}{rl}f(x_k)& =\varphi ({\alpha }_0,{\alpha }_1,\cdots ,{\alpha }_{k-1})\\ & =\frac{1}{2}{\left(x_0+\sum _{i=0}^{k-1}{\alpha }_i\cdot d_i\right)}^T\mathcal{Q}\left(x_0+\sum _{i=0}^{k-1}{\alpha }_i\cdot d_i\right)+{\mathcal{C}}^T\left(x_0+\sum _{i=0}^{k-1}{\alpha }_i\cdot d_i\right)\end{array}$$
• 由于$x_k$是${\mathcal{X}}_k$内的最小点，这意味着：$x_k$在迭代过程中选择的步长：$a_1,a_2,\cdots ,a_{k-1}$;这些步长同样构成了$\varphi ({\alpha }_0,{\alpha }_1,\cdots ,{\alpha }_{k-1})$的最小解：
  两个事件是等价的~
  $$\begin{array}{rl}& x_k=x_0+\sum _{i=0}^{k-1}{a}_i\cdot d_i\Rightarrow \{\begin{array}{l}\begin{array}{r}{x}_k=\mathrm{argmin}\left\{\frac{1}{2}{x}^T\mathcal{Q}x+{\mathcal{C}}^{T}x\mid x\in {\mathcal{X}}_k\right\}\end{array}\\ \\ (a_0,a_2,\cdots ,a_{k-1})=\underset{{\alpha }_0,\cdots ,{\alpha }_{k-1}}{\mathrm{argmin}}\varphi ({\alpha }_0,{\alpha }_1,\cdots ,{\alpha }_{k-1})\end{array}\end{array}$$
  如何验证上述式子成立$?$即证：
  如果将变量视作一个向量：$\Lambda =({\alpha }_0,\cdots ,{\alpha }_{k-1}{)}^T$,关于最优解向量$\mathcal{A}=(a_0,\cdots ,a_{k-1}{)}^T$的梯度$\nabla \varphi (\Lambda ){\mid }_{\Lambda =\mathcal{A}}=0$向量;即对应各分量的偏导数均为$0$。
  $$\frac{\partial \varphi ({\alpha }_0,\cdots ,{\alpha }_{k-1})}{\partial {\alpha }_i}{\mid }_{{\alpha }_i=a_i}=0i=0,1,2,\cdots ,k-1$$
  计算$\begin{array}{r}\frac{\partial \varphi ({\alpha }_0,\cdots ,{\alpha }_{k-1})}{\partial {\alpha }_i}\end{array}$：
  注意复合函数求导~并且${\alpha }_0,\cdots ,{\alpha }_{i-1},{\alpha }_{i+1},\cdots ,{\alpha }_{k-1}$均视作常数。
  $$\begin{array}{rl}\frac{\partial \varphi ({\alpha }_0,\cdots ,{\alpha }_{k-1})}{\partial {\alpha }_i}& =2\cdot \frac{1}{2}\cdot {\left[\mathcal{Q}\left(\underset{x_k}{\underbrace{x_0+\sum _{i=0}^{k-1}{\alpha }_i\cdot d_i}}\right)+\mathcal{C}\right]}^T{d}_i\\ & =(\mathcal{Q}\cdot x_k+\mathcal{C}{)}^T{d}_i\\ & =[\nabla f(x_k){]}^T{d}_i\\ & =0\end{array}$$
  因而$i=0,1,\cdots ,k-1$均满足上述条件，得证。同理，当$k=n$时，可以在完整的特征空间中找到最小解。

$\text{Reference}$：
最优化理论与方法-第七讲-无约束优化问题（三）