一文看懂无约束优化中的下降方法：直观了解梯度下降、最速 ...
1. 下降方法（Descent Methods）大部分实际优化问题并不能像极少数条件十分好的函数一样（ f(x)=x^2-5x+2 ）求出解析解（ x^*=\frac{5}{2} ），更多的是使用迭代的方式逐步优化，逼近最优值 p^* 及其最优点 x^* 。下降方法是这中间非常常见的一种解决方法。
下降算法
迭代优化过程
形象地理解，下降方法的每次迭代包含两个部分：
[*]确定使得目标值下降的更新方向 \Delta x \in \mathbb{R}^n
[*]确定更新步长 t
这两个值确定了每一步优化的方向和幅度。其中步长搜索一般有两种方法
1.1 精确直线搜索 Exact line search
精确直线搜索比较精准，每一步搜索步长都沿着下降方向射线（ \{ x+t \Delta x \mid t\geq 0 \} ）搜索，找到最优的步长 t^{(k)} 使得目标函数最大限度的降低，即：
t = \mathop{argmin}_{t \geq 0} f(x+t \Delta x)
1.2 回溯直线搜索 Backtracking line search
回溯直线搜索的步长相对比较简单，只要目标有足够的减少即可，并不要求步长值使得当前一步下降幅度最大。
Backtracking line search
在 x 处的泰勒展开是对于严格凸的目标函数的一个下界估计：
f(x+t\Delta x) \geq f(x) +t \nabla f(x)^T \Delta x
因而对于取定的 \alpha \in (0,1/2) ，有 t_0 使得 f(x+t\Delta x)=f(x)+\alpha t \nabla f(x)^T \Delta x
每一步搜索初始 t=1 ：
[*]如果 f(x+t\Delta x) \leq f(x) +t \nabla f(x)^T \Delta x ，则直接取 t=1 ，目标函数值至少减少 \alpha\nabla f(x)^T \Delta x
[*]如果 f(x+t\Delta x) > f(x) +t \nabla f(x)^T \Delta x ，则引入因子 \beta \in (0,1) ，更新 t:=\beta t ，直至 f(x+t\Delta x) \leq f(x) +t \nabla f(x)^T \Delta x
一般地，回溯直线搜索中的参数 \alpha=0.01 \sim 0.3,~\beta=0.1\sim 0.8 。
1.3 下降方向
根据不同的下降方向确定方式，下降方法分为了梯度下降、最速下降、牛顿法。
2. 梯度下降法（Gradient Descent Method）
顾名思义，梯度下降的更新方向由目标函数的负梯度方向（ -\nabla f(x) ）确定。
梯度下降方法
梯度下降方法的思路十分简单，但也存在问题。对于以下情形，显然梯度下降方法在优化后期存在问题，说白了就是按照负梯度方向更新总是在最优点附近徘徊，收敛很慢。
not well conditioned optimization process
实际上在优化理论中，有一个指标条件数（conditional number） \textbf{cond} C/\textbf{cond} H 被用来描述凸集 C 或函数的Hessian矩阵 H 的条件的好坏。一方面对于凸集， \textbf{cond} C 描述了凸集的最大宽度与最小宽度的平方比值；对于凸函数 f(x),H= \nabla^2f(x) ， \textbf{cond} H 描述了Hessian矩阵最大的特征值与最小特征值的比值。后续方法正是使优化过程中问题的条件数更接近1来获得优化这一方法。
3. 最速下降法（Steepest Descent Method）
最速下降法
最速下降法在寻找下降方向过程中引入了一个约束，即通过引入不同的范数（norm）来约束优化方向的选取，使得优化方向能够按照一定的意义或是意愿更新，而不仅仅按照负梯度方向。规范化的最速下降（normalized steepest descent）更新步长为:
\Delta x_{nst}= \textbf{argmin} \{ \nabla f(x)^T \Delta x\mid \Vert \Delta x \Vert =1\} , \Vert \cdot \Vert 可以是各类范数。
这里选择使用P-norm（二次范数）的最速下降法讲解他的原理与应用。对于P \in S^n_{++} n阶正定矩阵， P-norm 可以表示为\Vert x \Vert_{P}=（x^TPx）^{1/2}=\Vert P^{1/2}x \Vert_{2} 。
结合上节中梯度下降法遇到的问题，主要从两个角度解释一下最速下降法相对梯度下降在优化方向选取上的优势：
一种解释是从几何意义角度上来理解，一般地 \Vert x \Vert_{P}=（x^TPx）^{1/2}=1 在 \mathbb{R}^n 中表示了一个椭球面，具体地以二元优化目标为例，椭圆约束了优化方向 \Delta x 的选取， P 决定的椭球的主方向（ P 最大特征值对应的特征向量方向）与目标函数的下水平集（等高线分布）的最大宽度方向接近时，能够主导优化方向，避免红色箭头完全按照梯度更新的徘徊式缓慢的优化过程。
P norm最速下降方法
坐标变换后梯度下降优化过程
另一种解释类似，矩阵 P^{1/2} 可以看作对于原坐标 x 的一个线性变换，记 \bar{x} = P^{1/2}x 。这样的坐标变换相当于将函数的下水平集（等高线分布）进行了一个变形，使得其条件数更加接近1。这时候采用梯度下降方法也能较快地收敛，两种解释的本质是一致的（ \Vert x \Vert_{P}=（x^TPx）^{1/2}=\Vert P^{1/2}x \Vert_{2} ）。
对于一些问题，可以通过适当地选择 P 可以极大地减少迭代次数，提升优化效率。但同时也要注意到，对于复杂的下水平集（目标函数等高线分布），一成不变的 P 并不能保证在收敛的过程中都保证良好的收敛条件，牛顿法的改进正是解决了这一问题。
除此之外还有其他的约束下的最速下降方法（详细可以参考Stanford University, Stephen Boyd. Convex Optimization）：
[*]使用Euclidean norm（ \Vert x \Vert_{Euclid}=（x^Tx）^{1/2} ），此时最速下降法等价于梯度下降法
[*]使用 l_1 norm（ \Vert x \Vert_{1}=\sum\limits_{i}{\vert x_i \vert} ）
4. 牛顿法（Newton's Method）
牛顿法
牛顿法在P-norm最速下降的基础上将矩阵 P 替换为目标函数在当前点 x\in \mathbb{R}^n 的Hessian矩阵 \nabla^2f(x) ，即 \nabla^2f(x)-norm ：
\Vert u \Vert_{\nabla^2f(x)}=(u^T\nabla^2f(x)u)^{1/2}
相当于引入了自适应的P-norm，直观的理解，可以看下图中不同位置的椭球约束不一样。牛顿法在P-norm最速下降的基础上进一步优化了用每一步优化方向的选择，同时保证较快的收敛速度。
牛顿法快速收敛过程
<hr/>后记：需要指出的是，这里只是给出了一些结合了简单优化知识的形象化的理解，帮助大家区分几种方法，更好地理解其中区别与优缺点。如果需要了解详细的推导和分析，可以参考Stephen Boyd这本书的Ch9。
页:
[1]