无约束最优化概述

无约束最优化概述

无约束最优化的基本问题是要解决如下的问题：

$$argmin_x \; f(x)$$
在这里要求$f(x)$是连续且可导的。

优化的基本策略

如果优化问题不能够直接求解，那么解决问题的方法只有通过不停的迭代。迭代的基本方式如下：

1. 设置初始点 $x_0$，同时设置迭代计数器 $i = 0$ ;
2. 根据当前点 $x_i$ 的$Gradient，Hessian$ 或者是之前点的信息计算得优化方向$d_i$
3. 计算优化方向 $d_i$ 对应的步长 $\alpha_i$，然后获得下一个点 $x_{i+1} = x_i + \alpha_i d_i$
4. 计算当前点 $x_{i+1}$ 是否收敛，如果收敛则获得答案，否则转回步骤2。

在这样的计算框架中，基本可以分解成三部分，第一是是产生优化方向，第二是计算步长，第三是检查整个过程是否收敛。一个完成的优化算法就是由这三个部分组成的。计算步长的过程基本可以独立于第一步，第三步和第一步是整个算法最密切相关的。

对一个算法的评估包括以下几个方面，首先是算法的收敛速度如何，然后是算法的计算复杂度是多少，最后会考虑算法的稳定性。稳定性的考虑是因为算法的解决依赖于数值计算方法，如果算法不稳定，那么会导致一个理论可行的算法不能给出最优解甚至不能解决问题。

$Gradient Descent$

梯度下降法的推到特别简单，使用泰勒一阶展式即可：

$$f(x_k + d_k) = f(x_k) + \nabla f(x) ^ T d_k + o$$
在这里 $O$ 代表一个低阶项，先在足够近的情况下可以直接忽略。使用这样的近似，可以看出如果想要减小函数值，那么选择$\; d_k \;$为 $- \nabla f(x)$即可，当 $\nabla f(x)$ 为0时，函数值无法再减小，因此可以使用 $\nabla f(x)$ 作为终止条件。由于使用的是一阶展式，如果步长过大，那么这样的近似就可能是错误的。而且梯度下降法在问题的规模较大时需要花费很长的时间收敛，因此在现实中几乎不可用。

$Newton Method$

牛顿法可以使用泰勒二阶展式推到：

$$f(x_k + d_k) = f(x_k) + \nabla f(x) ^ T d_k + 1/2 \cdotp d_k ^ T H_k d_k + o$$
对这个二阶的问题优化，对右边的等式求导并令其倒数为0，可获得方向 $d_k = - H_k ^ {-1} \nabla f(x)$。迭代的停止条件可以选择是$\nabla f(x)$或者是 $\nabla f(x) ^ T H_k \nabla f(x)$，如果这两个数值小于一定的程度，那么可以考虑将算法收敛。牛顿法最大的问题就在于海森矩阵的计算，如果问题的规模较大，而且没有特殊的结构可以使用，牛顿法就是不可使用的。

$Quasi-Newton Method$

牛顿法具有二次收敛速度，但是需要计算 $H_k$，因此拟牛顿法的提出是为了解决这个问题。在拟牛顿法中不显示的计算海森矩阵，而且从每一步的迭代信息中构造海森矩阵的一个近似，替代真实的海森矩阵去计算优化方向。在牛顿法中迭代方向计算是 $d_k = - H_k ^ {-1} \nabla f(x_k)$，现在计算方法如下 $d_k = - B_k \nabla f(x_k)$。为了唯一的求得矩阵$B_k$，我们必须施加一定的限制。假设当前点为$x_k$，迭代方向是$\alpha_k d_k$，下一个迭代点 $x_{k+1} = x_k + \alpha_k d_k$，在点 $x_{k+1}$ 上构造近似如下：

$$f(p) = f(x_{k+1}) + \nabla f(x_{k+1}) ^ T p + 1/2 p ^ T B_{k+1} p$$
对这个函数求导可得 $\nabla f(p) = B_{k+1} p \; +\; \nabla f(x_{k+1})$，如果将$p = x_k - x_{k+1}$，那么近似函数的倒数应该等于函数$f(x)$ 在 $x_k$ 处的导数$\nabla f(x_k)$：
$$\nabla f(x_k) = B_{k+1}p +\nabla f(x_{k+1})$$
定义$s_k = x_{k+1} - x_k; y_k = \nabla f(x_{k+1}) - \nabla f(x_k)$，那么上述公式可以写成如下形式:
$$B_{k+1} s_k = y_k$$
事实上如果要求 $B_{k+1}$ 是 $H_k$ 的近似，那么应该满足如下的等式要求：
$$B_{k+1} s_i = y_i \quad (i =0, 1, ..., k)$$
因此为了获得$B_{k+1}$，我们需要优化如下的问题：
$$argmin_B \left|| B - B_k \right||$$
$$s.t. B = B ^ T ; B s_k = y_k$$
使用不同的范数，可以获得不同的由 $B_k$ 产生 $B_{k+1}$的方法。

$SR1 \; Update$

全称是Symmetric Rank 1 updae, 具有如下形式的迭代：

$$B_{k+1} = B_k + \alpha \beta \beta ^ T$$
这里主要的问题就在于如何计算这个修正项。 (skip )

$DFP & BFGS Update$

对应的是两个不同的更新规则，但是这里使用的是Rank 2更新。 Wikipedia

$L-BFGS \; Update$

在BFGS更新的基础上，只保留最近几个迭代的信息用于计算海森矩阵的近似。可以适用于大规模的数据优化。在这个算法中不需要显示的构造矩阵 $B_k$ 即可完成迭代方向的计算。

$Conjugate \; Gradient$

共轭梯度法本来是为解方程 $Ax = b$ 提出的，但是最后发现也可以使用到一般的函数优化中。
共轭梯度法就是在一组相互共轭的方向上优化目标函数，知道目标函数达到最优点。
两个向量共轭定义如下：

$$v ^ T H \mu = 0$$
其中矩阵H是正定矩阵。如果一组向量共轭，那么意味着这组向量中任意两个向量都是共轭向量。可以证明对于二次函数 $1/2 x ^ T A x + b ^ T x$来说，沿着一组有n个向量的方向优化，那么最终可以到达最优点。对于共轭梯度来来说，产生新的迭代方向使用如下的公式：
h $$d_{k+1} = - \nabla f(x_{k+1}) + \beta d_k$$ ，也就是实现当前点的梯度和之前的迭代方向来产生新的优化方向 $d_{k+1}$。相比于其他的方法，共轭梯度法使用更少的内存，这是很大的优势。

评价

从数值优化的角度，梯度下降法几乎不可用，因此对于实际的问题可能需要很长的时间去迭代。但是对于机器学习来说，这却不是问题，因为机器学习方法并不对解的精度有要求，唯一的要求是泛化性能。牛顿法具有二阶收敛速度，但是由于需要使用很多的内存，因此在实际中很少使用。拟牛顿法和L-BFGS方法，由于需要的内存较少，而且可以实现超线性的收敛，在实践中被广泛使用，特别是L-BFGS。