优化算法（二）——最速下降法
首先考虑使得目标函数值下降最快的方式，也即最速下降法（steepest descent）。定义
由于函数在点处的变化率可以由其对应的方向导数表达，
https://www.zhihu.com/equation?tex=f%27%28x_k%3Bd_k%29%3D%5Clim_%7B%5Calpha%5Crightarrow0%7D%5Cfrac%7Bf%28x_k%2B%5Calpha+d_k%29-f%28x_k%29%7D%7B%5Calpha%7D%3D%5Cnabla+f%5ET%28x_k%29d_k%5C%5C
因此，为了保证函数在处下降最快，可以将问题转化为优化问题：
https://www.zhihu.com/equation?tex=%5Cbegin%7Bgather%7D+%5Cmin+~~%5Cnabla%5ETf%28x_k%29d_k%5C%5C+s.t.~~~~%5C%7Cd_k%5C%7C%5Cleq1%5C%5C+%5Cend%7Bgather%7D+%5C%5C+
由Cauchy-Schwarz不等式，可以得到，
https://www.zhihu.com/equation?tex=%7C%5Cnabla%5ET+f%28x_k%29d_k%7C%5Cleq%5C%7C%5Cnabla+f%28x_k%29%5C%7C%5Ccdot%5C%7Cd_k%5C%7C%5Cleq%5C%7C%5Cnabla+f%28x_k%29%5C%7C%5C%5C
然后去掉绝对值符号，可以得到
https://www.zhihu.com/equation?tex=%5Cnabla%5ET+f%28x_k%29d_k%5Cgeq-%5C%7C%5Cnabla+f%28x_k%29%5C%7C%5C%5C
这就说明了最速的下降方向是负梯度方向，这一方向可以使得目标函数的变化率最大，https://www.zhihu.com/equation?tex=%5Carg%5Cmin_%7B%5C%7Cd%5C%7C%5Cleq1%7Df%27%28x_k%3Bd_k%29%3D-%5Cfrac%7B%5Cnabla+f%28x_k%29%7D%7B%5C%7C%5Cnabla+f%28x_k%29%5C%7C%7D%5C%5C
以上的假设是基于Euclidean范数得到的，若采用其他范数，结果可能有部分差异。如使用对称正定矩阵所度量的范数 https://www.zhihu.com/equation?tex=%5C%7C%5Ccdot%5C%7C_A ，最速下降方向则变为
https://www.zhihu.com/equation?tex=%5Carg%5Cmin_%7B%5C%7Cd%5C%7C%5Cleq1%7Df%27%28x_k%3Bd_k%29%3D-%5Cfrac%7BA%5E%7B-1%7D%5Cnabla+f%28x_k%29%7D%7B%5Cleft%28%5Cnabla+%5ETf%28x_k%29A%5E%7B-1%7D%5Cnabla+f%28x_k%29%5Cright%29%5E%7B%5Cfrac%7B1%7D2%7D%7D%5C%5C
收敛性
接下来讨论最速下降法的收敛性。
如之前所说，考虑线性收敛速度 https://www.zhihu.com/equation?tex=O%281%2Fk%29 ，目标是寻找一个收敛率 https://www.zhihu.com/equation?tex=%5Crho%3C1，使得 https://www.zhihu.com/equation?tex=%5C%7Cx_%7Bk%2B1%7D-x%5E%5Cstar%5C%7C%5Cleq%5Crho%5C%7Cx_%7Bk%7D-x%5E%5Cstar%5C%7C 成立。
先使用二次函数 https://www.zhihu.com/equation?tex=f%28x%29%3D%5Cfrac%7B1%7D2x%5ETAx%2Bb%5ETx 作为例子（是一个正定矩阵），对于固定的step size，在迭代最终收敛时，满足
https://www.zhihu.com/equation?tex=x_%7Bk%2B1%7D-x%5E%5Cstar%3D%28I-%5Calpha+A%29%28x_k-x%5E%5Cstar%29%5C%5C
因此，需要相应的选取合适的步长，从而保证 https://www.zhihu.com/equation?tex=%5C%7Cx_%7Bk%2B1%7D-x%5E%5Cstar%5C%7C 相较 https://www.zhihu.com/equation?tex=%5C%7Cx_k-x%5E%5Cstar%5C%7C 一定是在收缩的。
首先计算出的全部特征值，分三种情况进行讨论。
[*]矩阵的全部特征值都非负，也即它的最小特征值 https://www.zhihu.com/equation?tex=1-%5Calpha%5Clambda_%7Bmax%7D%5Cgeq0 。因此有 https://www.zhihu.com/equation?tex=1%2F%5Clambda_%7Bmax%7D%5Cgeq%5Calpha ，进而得到 https://www.zhihu.com/equation?tex=%5C%7CI-%5Calpha+A%5C%7C%3D1-%5Calpha%5Clambda_%7Bmin%7D%5Cgeq%5Cfrac%7B%5Clambda_%7Bmax%7D-%5Clambda_%7Bmin%7D%7D%7B%5Clambda_%7Bmax%7D%7D 。（矩阵的norm是它的最大特征值）
[*]完全类似，矩阵的全部特征值都非正，也即它的最大特征值 https://www.zhihu.com/equation?tex=1-%5Calpha%5Clambda_%7Bmin%7D%5Cleq0，可得 https://www.zhihu.com/equation?tex=1%2F%5Clambda_%7Bmin%7D%5Cleq%5Calpha 。同样地， https://www.zhihu.com/equation?tex=%5C%7CI-%5Calpha+A%5C%7C%3D%5Calpha%5Clambda_%7Bmax%7D-1%5Cgeq%5Cfrac%7B%5Clambda_%7Bmax%7D-%5Clambda_%7Bmin%7D%7D%7B%5Clambda_%7Bmin%7D%7D 。
[*]对于矩阵特征值有正有负的情况， https://www.zhihu.com/equation?tex=%5C%7CI-%5Calpha+A%5C%7C%3D%5Cmax%5C%7B%7C1-%5Calpha%5Clambda_%7Bmax%7D%7C%2C%7C1-%5Calpha%5Clambda_%7Bmin%7D%7C%5C%7D ，为了使得它最小，令 https://www.zhihu.com/equation?tex=%7C1-%5Calpha%5Clambda_%7Bmax%7D%7C%3D%7C1-%5Calpha%5Clambda_%7Bmin%7D%7C ，可以解出 ，因此。
三种情况相比，显然最优选择为 ，进而可以计算得到 https://www.zhihu.com/equation?tex=%5Crho%3D%5Cfrac%7B%5Clambda_%7Bmax%7D-%5Clambda_%7Bmin%7D%7D%7B%5Clambda_%7Bmax%7D%2B%5Clambda_%7Bmin%7D%7D 。
因此
https://www.zhihu.com/equation?tex=%5C%7Cx_%7Bk%2B1%7D-x%5E%5Cstar%5C%7C%3D%5Crho%5Ek%5C%7Cx_0-x%5E%5Cstar%5C%7C%5C%5C
由于 https://www.zhihu.com/equation?tex=0%3C%5Crho%3C1 ，当 https://www.zhihu.com/equation?tex=k%5Crightarrow%5Cinfty 时，将会收敛至 https://www.zhihu.com/equation?tex=x%5E%5Cstar 。因此要想确定一个不精确的bound，至多需要经过
https://www.zhihu.com/equation?tex=%5Cfrac%7B%5Clog%28%5C%7Cx_0-x%5E%5Cstar%5C%7C%2F%5Cepsilon%29%7D%7B%5Clog%281%2F%5Crho%29%7D%5C%5C
次迭代即可实现 https://www.zhihu.com/equation?tex=%5Cepsilon 的误差。
缺陷
由于在每一步都要相应选取在 https://www.zhihu.com/equation?tex=d_k 方向上的极小点，因此 https://www.zhihu.com/equation?tex=f%28x_k%2B%5Calpha+d_k%29 对step size的导数应该也是 https://www.zhihu.com/equation?tex=0+ 。进而可以得到 https://www.zhihu.com/equation?tex=%5Cnabla+f%28x_k%2B%5Calpha+d_k%29d_k%3D0 ，由最速下降的定义，可以判定得到 https://www.zhihu.com/equation?tex=%5Cnabla%5ET+f%28x_%7Bk%2B1%7D%29%5Cnabla+f%28x_k%29%3D0 。
因此相邻两个搜索方向是正交的，路径是呈“之”字形不断下降，这会大幅影响收敛速度。
此外，当的Hessian矩阵是奇异的或不存在时，若结果能收敛，它的收敛率也会大于线性收敛率。
和特征值之间的关系：
在二次函数中，目标函数的等值面可以被视为一个椭球面，由于收敛率为，最大最小特征值就对应了最长轴和最短轴的长度。当两特征值相差越大，椭球面越扁，这会使得搜索方向沿着扁平且较长的方向不断搜索，这时候它们会在两个相互正交的方向上交替迭代，如果没有一个能够恰好指向最小值的方向，迭代速度会比较缓慢。
从数值角度分析， https://www.zhihu.com/equation?tex=%5Clambda_%7Bmax%7D%2F%5Clambda_%7Bmin%7D 被称为条件数，当它越接近于 https://www.zhihu.com/equation?tex=1+ 时， 越靠近 https://www.zhihu.com/equation?tex=0 ，接近超线性的收敛速度。而反之，如果条件数越大， 越靠近 https://www.zhihu.com/equation?tex=1，收敛速度会越慢。
同样地，对于一般的凸函数，在近似收敛点的位置，目标函数也可以粗略地视为一个椭球面，只需要计算它的Hessian矩阵的最大最小特征值，可以以同样的方式理解。
对于非凸函数，需要找到它Hessian矩阵的上下界，也即一组参数 https://www.zhihu.com/equation?tex=%28m%2CM%29 ，来替代最大最小特征值的的位置， https://www.zhihu.com/equation?tex=mI%5Cpreceq%5Cnabla%5E2f%28x%29%5Cpreceq+MI 。
所以说，尽管最速下降法每轮都可以取到最快的下降方向，但是从全局上讲，它不一定能够使得找到总体上更靠近最优值，会走一定的弯路，因此不是最快的收敛方法。
下一步会继续讨论Inexact的线搜索方式。
页:
[1]