最速下降法的核心思想

最速下降法是梯度下降法的⼀种实现形式，每⼀步都是沿着负梯度的⽅向迭代前进，但是同上⼀讲⾥介绍的⽅法不同之处在 于学习率的选择⽅式。

在基础的梯度下降法当中，学习率$\lambda_k$是固定的，即$p_{k+1} = p_k - \nabla f(p_k) \lambda_k$。

但是最速下降法则不然，搜索⽅向仍然是当前点$p_k$的负梯度⽅向$- \nabla f(p_k)$，但是迭代的⽬标点是需要满⾜在这个搜索⽅向上使得函数$f$取得该⽅向上的极小值，即：

使得函数取值$f(p_{k+1})$在搜索的一维方向上取得极小值。

更进⼀步地，在$p_k$点进⾏迭代时，由于此时$p_k$和$\nabla f(p_k)$都是已知的，实际上的⼯作就是锁定$\alpha_k$的取值，使得函数$f(p_k - \alpha_k \nabla f(p_k))$取得极小值。此时在寻找函数极小值的过程中，仅仅只有⼀个未知数，那就是$\alpha_k$，因此我们⾯对的问题实际上就是⼀个⼀元函数极值点的搜索问题。

思考： 怎么求这个$\alpha_k$？

每次迭代的过程都是在当前迭代点的负梯度⽅向上寻找使得函数取得极小值点的$\alpha_k$值， 然后依次迭代处下一个迭代点， 最终直至满足预设阈值条件， 迭代停止。

算法步骤

• 首先，我们从一个初始的迭代点$p_0$开始；
• 每一轮迭代， 对于当前点$p_k$， 计算当前点的梯度$\nabla f(p_k)$， 如果梯度的模长$\mid \nabla f(p_k) \mid$小于预设的阈值$\epsilon$， 则停止迭代， 当前点$p_k$即为函数的极小值点；
• 否则， 寻找使得$f(p_k - \alpha_k \nabla f(p_k))$取得极小值$\alpha_k$， 然后迭代出新的取值点： $p_{k+1} = p_k - \alpha_k \nabla f(p_k)$

循环往复地进行上述迭代过程。

迭代路径的特性分析

迭代点$p_k p_{k+1}$的连线与$p_{k+1}p_{k+2}$的连线是垂直的，也就是说相邻两次的迭代搜索⽅向保持相互间的垂直关系。

其实这是最速下降法中的必然结果，我们简单证明⼀下。

首先由：

我们令$\phi_k = f(p_k - \alpha \nabla f(p_k))$， 由于$\alpha_k$的选取， 使得$\phi(\alpha_k) = f(p_k - \alpha_k \nabla f(p_k))$取得最小值， 因此我们让$\phi_k$对变量$\alpha$进行求导， 按照求导的链式法则：

且当$\alpha = \alpha_k$时， $\frac{d \phi_k}{d \alpha}(\alpha_k) = 0$。

这个式⼦看上去有点⿇烦，实际上抓住两个关键点就好了：

• 第一， 在这个求导的表达式中$p_k$和$\nabla f(p_k)$都是常数， 变量只有一个， 那就是$\alpha$。 因此后面一个表达式化简为： $\frac{d(p_k - \alpha \nabla f(p_k))}{d \alpha} = - \nabla f(p_k)$
• 第二， 当$\alpha = alpha_k$时， 我们可以将前面一部分中的$p_k - \alpha_k \nabla f(p_k)$整体替换成$p_{k+1}$， 而此时$\frac{d f(p_k - \alpha \nabla f(p_k))}{d(p_k - \alpha \nabla f(p_k))} = \frac{d f(p_{k+1})}{d(p_{k+1})}$， 这不就是迭代点$p_{k+1}$处的梯度$\nabla f(p_{k+1})$吗？

这样⼀来，我们可以把$\frac{d \phi_k}{d \alpha}(\alpha_k)$进⼀步化简成为上述两个梯度向量点积的形式：

我们得到$\nabla f(p_{k+1})·\nabla f(p_k) = 0$。

由于我们每次搜索的⽅向都是当前位置的负梯度⽅向，因此就证明了相邻两次的搜索⽅向满⾜相互正交。