换个角度理解无约束数值优化

先剧透，我认为常见的无约束的数值优化方法不是在解算二次型就是在转换为二次型再进行解算的路上。至于有约束的方法，也通常利用某些手段变为无约束方法。本文就不讨论KKT那些东西了。

引言

由于计算机硬件的限制，虽然我们用各种漂亮的数学模型去解释我们的工作，但是最后都不得不使用数值优化这个工具。所以我们来讨论一下数值优化到底是怎么做的，至于它是用来做什么的不是这篇文章要讲的东西。

问题定义

在一个最优化问题中，我们通常都是要求解使得某个函数最小的变量，即

$x^* = \text{arg}\min_x f(x)$

你要问为什么不是最大，因为我们通常都是希望误差最小。

一次的情况

我们首先来分析下$f(x)$的情况。从我们最熟悉的线性方程开始吧，如果$f(x)$是一个一次的函数，即

$f(x) = ax + b$

这个时候你问$f(x)$的最小值是什么其实是没有意义的对吧。应该说，对于所有奇次的函数$f(x)$而言，这个问题都是没有意义的。

二次的情况

看完了最熟悉的线性我们来看看二次的吧，即

$f(x) = \frac{1}{2} ax^2 - bx +c$

众所周知，当$a > 0$的时候，满足$ax = b$的$x$使得$f(x)$最小。如果我们写成矩阵形式的话，则有

$f(\mathbf{x}) = \frac{1}{2} \mathbf{x}^T A \mathbf{x} - \mathbf{b}^T \mathbf{x} + c$

在这种情况下我们就有，当$A$正定时，满足$A \mathbf{x} = \mathbf{b}$的$\mathbf{x}$使得函数$f(\mathbf{x})$最小。此时内容已经初显端倪了。

将高次函数转为二次函数

上面我们讨论了一次和二次的情况，那么对于更高次的情况呢？高次函数的最小值目前还没有通解形式，所以就必须从初始值一点点迭代了。在这种方法中，每次迭代直接求得的结果并不是自变量$x$本身，而是要叠加在$x$上的一个变化$\Delta x$。

梯度下降法

梯度是函数在局部上升最快的方法，也就是说梯度的反方向是函数下降最快的方向。因此我们每次都往函数的负梯度方向迭代，即

$\mathbf{x}_{k+1} = \mathbf{x}_k - \alpha \mathbf{J}_{k}$

其中$\mathbf{J}_k$是函数$f(x)$在$\mathbf{x}_k$处的导数，$\alpha$是步长。现在问题来了，步长$\alpha$多大的时候这次迭代是最优的？答案是和这次迭代的终点$\mathbf{x}_{k+1}$处的导数$\mathbf{J}_{k+1}$垂直的时候。如果这两个方向不是垂直的，那么表示这次迭代还没有到达最优的结果或者说已经超过了最优的结果。想求证的同学可以自己尝试画图。接下来这个问题就变成了

$\langle \mathbf{J}_k, \mathbf{J}_{k+1} \rangle = 0$

其中

$\mathbf{J}_{k+1} = \nabla f(\mathbf{x}_k - \alpha \mathbf{J}_{k}) \approx \mathbf{J}_k - H_k \cdot \alpha \mathbf{J}_{k}$

这其中$H_k$为$\mathbf{x}_k$处的Hessian矩阵，那么我们求解的问题变成了

$\mathbf{J}_k^T \mathbf{J}_k - \mathbf{J}_k^T H_k \mathbf{J}_k \alpha = 0$

也就是说这个问题变成了

$\alpha^* = \text{arg}\min_\alpha \frac{1}{2} \mathbf{J}_k^T H_k \mathbf{J}_k \alpha^2 - \mathbf{J}_k^T \mathbf{J}_k \alpha + c$

这也太刺激了吧！（虽然一般在实际操作的时候大家都不会用这种方法计算步长）

牛顿型方法

牛顿型跟二次函数的关系就更明确，因为牛顿型方法就是将函数近似为二次函数再求解的。为了证实这个说法我们还是简单推导一下。

原始的牛顿法就是直接将高次函数泰勒展开到二次，即

$f(\mathbf{x} + \Delta \mathbf{x}) \approx f(\mathbf{x}) + \nabla f(\mathbf{x}) \Delta \mathbf{x} + \frac{1}{2} \Delta\mathbf{x}^T H \Delta\mathbf{x}$

高斯牛顿是解决Frobenius范数下的最优化问题，它直接在范数中泰勒展开到一阶，即

$f(\mathbf{x} + \Delta\mathbf{x}) \approx \| f(\mathbf{x}) + \nabla f(\mathbf{x}) \Delta \mathbf{x} \|_F^2$

以上内容，请大家自己展开，我懒得写了。

其实很明显，牛顿法的核心就是将问题局部变为一个二次型的问题进行迭代。

求解二次型问题

对于常见的二次型的问题，形式前面已经给出了，最终就是求解一个形如

$A \mathbf{x} = \mathbf{b}$

的线性系统。

在这个线性系统中，通常我们都要求矩阵$A$是对称正定的（当然能稀疏是最好）。对称性通常都很容易满足，一旦$A$不对称的话$A^TA$总该对称了吧。关于正定的问题应该是有很多讨论的，这里不多写。不过关于正定的问题可以提供一次思考方向，对于对称矩阵$A$而言，如果主对角轴上的值$a_{ii}$为正数且$a_{ii} > \sum_{j \neq i} \| a_{ij} \|$，那么矩阵$A$是正定的。以下内容我们都默认$A$是对称正定的，不再赘述。

直接法

这东西大家应该都很熟悉了。各种矩阵分解方法，什么QR、LU、SVD、Cholesky等等，都是在考虑如何计算矩阵$A$的逆$A^{-1}$。反正都是变着花样进行高斯消元，我甚至想不出有什么好写的。

共轭梯度

由于众所周知的原因，也就是直接矩阵分解求逆的计算量太大了，所以大家都在想办法找一些计算量更小的方法。

前面说到梯度下降法每次迭代都是往梯度的附方向迭代，并且相邻两次的迭代方向在最优的情况下是互相垂直的。也就是会造成大家熟知的“之”字形迭代路径。为了避免这种情况，共轭梯度法考虑每次迭代方向都是共轭的，这样就可以在有限次内得到最优解。

共轭梯度法是用来求解对称正定二次型的方法。应该还是要解释下什么叫共轭，非零向量$\mathbf{x}$和$\mathbf{y}$关于对称正定矩阵$A$共轭，也就是说

$\mathbf{x}^T A \mathbf{y} = 0$

于是共轭梯度法选择$n$个共轭且线性独立的方向作为迭代方向，这样最多只需要迭代$n$次。具体的算法细节很多资料都有写，我这里就不多赘述了。

虽然共轭梯度比梯度下降快很多了，但是有时还不是那么快。共轭梯度和梯度下降一样，收敛速度受到矩阵$A$最大特征值和最小特征值之比$\lambda_{\max} / \lambda_{\min}$（条件数）的影响。因此又出现了预处理共轭梯度法，主要思想是通过某些预处理子（也就是某个矩阵乘上这个系统）使得新系统中矩阵$\hat{A}$的条件数比矩阵$A$的小。

总结

一般情况下，一个有约束问题通常会想办法先变成无约束问题，一个无约束问题通常会转换为某个二次型计算，最终都要回到一个线性方程求解。

本文是希望从一个不一样的角度来看看数值优化，希望能给大家的工作带来一些不一样的思路。