二、梯度下降法

1. 梯度下降法是求解无约束最优化问题的一种常见方法，优点是实现简单。

2. 对于函数： ，假设输入 ，则定义梯度：

   

   函数的驻点满足： 。

3. 沿着方向 的方向导数directional derivative定义为：

   

   其中 为单位向量。

   方向导数就是 。根据链式法则，它也等于 。

1. 为了最小化 ，则寻找一个方向：沿着该方向，函数值减少的速度最快（换句话说，就是增加最慢）。即：

   

   假设 与梯度的夹角为 ，则目标函数等于： 。

   考虑到 ，以及梯度的大小与 无关，于是上述问题转化为：

   

   于是： ，即 沿着梯度的相反的方向。即：梯度的方向是函数值增加最快的方向，梯度的相反方向是函数值减小的最快的方向。

   因此：可以沿着负梯度的方向来降低 的值，这就是梯度下降法。

2. 根据梯度下降法，为了寻找 的最小点，迭代过程为： 。其中： 为学习率，它是一个正数，决定了迭代的步长。

   迭代结束条件为：梯度向量 的每个成分为零或者非常接近零。

3. 选择学习率有多种方法：

   • 一种方法是：选择 为一个小的、正的常数。

   • 另一种方法是：给定多个 ，然后选择使得 最小的那个值作为本次迭代的学习率（即：选择一个使得目标函数下降最大的学习率）。

     这种做法叫做线性搜索line search 。

   • 第三种方法是：求得使 取极小值的 ，即求解最优化问题：

     

     这种方法也称作最速下降法。

     • 在最速下降法中，假设相邻的三个迭代点分别为： ，可以证明： 。即相邻的两次搜索的方向是正交的！

       证明：

       

       根据最优化问题，有：

       

       将 代入，有：

       

       为求 极小值，则求解： 。

       根据链式法则：

       

       即： 。则有： 。

     • 此时迭代的路线是锯齿形的，因此收敛速度较慢。

4. 某些情况下如果梯度向量 的形式比较简单，则可以直接求解方程： 。

   此时不用任何迭代，直接获得解析解。

5. 梯度下降算法：

   • 输入：

     • 目标函数
     • 梯度函数
     • 计算精度

   • 输出： 的极小点

   • 算法步骤：

     • 选取初始值 ，置 。

     • 迭代，停止条件为：梯度收敛或者目标函数收敛。迭代步骤为：

       • 计算目标函数 ，计算梯度 。

       • 若梯度 ，则停止迭代， 。

       • 若梯度 ，则令 ，求 ： 。

         通常这也是个最小化问题。但是可以给定一系列的的值，如：[10,1,0.1,0.01,0.001,0.0001] 。然后从中挑选使得目标函数最小的那个。

       • 令 ，计算 。

         • 若 或者 时，停止迭代，此时 。
         • 否则，令 ，计算梯度 继续迭代。

     

6. 当目标函数是凸函数时，梯度下降法的解是全局最优的。通常情况下，梯度下降法的解不保证是全局最优的。

7. 梯度下降法的收敛速度未必是最快的。