Question

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

2. 对于函数： $ MathJax-Element-70 $ ，假设输入 $ MathJax-Element-71 $ ，则定义梯度：

   $ \nabla _{\mathbf{\vec x}} f(\mathbf{\vec x})=\left(\frac{\partial}{\partial x_1}f(\mathbf{\vec x}),\frac{\partial}{\partial x_2}f(\mathbf{\vec x}),\cdots,\frac{\partial}{\partial x_n}f(\mathbf{\vec x})\right)^{T} $

   函数的驻点满足： $ MathJax-Element-103 $ 。

3. 沿着方向 $ MathJax-Element-84 $ 的方向导数directional derivative定义为：

   $ \lim_{\alpha\rightarrow 0}\frac{f(\mathbf{\vec x}+\alpha\mathbf{\vec u})-f(\mathbf{\vec x})}{\alpha} $

   其中 $ MathJax-Element-84 $ 为单位向量。

   方向导数就是 $ MathJax-Element-75 $ 。根据链式法则，它也等于 $ MathJax-Element-76 $ 。

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

   $ \min_{\mathbf{\vec u}} \mathbf{\vec u}^{T}\nabla _{\mathbf{\vec x}} f(\mathbf{\vec x})\\ s.t.\quad ||\mathbf{\vec u}||_2=1 $

   假设 $ MathJax-Element-84 $ 与梯度的夹角为 $ MathJax-Element-82 $ ，则目标函数等于： $ MathJax-Element-80 $ 。

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

   $ \min_\theta \cos\theta $

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

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

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

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

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

   • 一种方法是：选择 $ MathJax-Element-383 $ 为一个小的、正的常数。

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

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

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

     $ \epsilon^{*}=\arg\min_{\epsilon,\epsilon \gt 0 }f(\mathbf{\vec x}-\epsilon\nabla _{\mathbf{\vec x}} f(\mathbf{\vec x})) $

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

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

       证明：

       $ \mathbf{\vec x}^{}=\mathbf{\vec x}^{}-\epsilon^{}\nabla _{\mathbf{\vec x}} f(\mathbf{\vec x}^{})\\ \mathbf{\vec x}^{}=\mathbf{\vec x}^{}-\epsilon^{}\nabla _{\mathbf{\vec x}} f(\mathbf{\vec x}^{}) $

       根据最优化问题，有：

       $ \epsilon^{}=\arg\min_{\epsilon,\epsilon \gt 0 }f(\mathbf{\vec x}^{}) $

       将 $ MathJax-Element-97 $ 代入，有：

       $ f(\mathbf{\vec x}^{})=f(\mathbf{\vec x}^{}-\epsilon\nabla _{\mathbf{\vec x}} f(\mathbf{\vec x}^{})) $

       为求 $ MathJax-Element-98 $ 极小值，则求解： $ MathJax-Element-99 $ 。

       根据链式法则：

       $ \frac{\partial f(\mathbf{\vec x}^{}-\epsilon\nabla _{\mathbf{\vec x}} f(\mathbf{\vec x}^{})) }{\partial \epsilon}= \nabla _{\mathbf{\vec x}} f(\mathbf{\vec x}^{}-\epsilon\nabla _{\mathbf{\vec x}} f(\mathbf{\vec x}^{}))\cdot[- \nabla _{\mathbf{\vec x}} f(\mathbf{\vec x}^{})] = 0 $

       即： $ MathJax-Element-100 $ 。则有： $ MathJax-Element-101 $ 。

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

6. 某些情况下如果梯度向量 $ MathJax-Element-102 $ 的形式比较简单，则可以直接求解方程： $ MathJax-Element-103 $ 。

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

7. 梯度下降算法：

   • 输入：

     • 目标函数 $ MathJax-Element-433 $
     • 梯度函数 $ MathJax-Element-105 $
     • 计算精度 $ MathJax-Element-300 $

   • 输出： $ MathJax-Element-433 $ 的极小点 $ MathJax-Element-340 $

   • 算法步骤：

     • 选取初始值 $ MathJax-Element-341 $ ，置 $ MathJax-Element-343 $ 。

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

       • 计算目标函数 $ MathJax-Element-111 $ ，计算梯度 $ MathJax-Element-344 $ 。

       • 若梯度 $ MathJax-Element-345 $ ，则停止迭代， $ MathJax-Element-124 $ 。

       • 若梯度 $ MathJax-Element-347 $ ，则令 $ MathJax-Element-116 $ ，求 $ MathJax-Element-363 $ ： $ MathJax-Element-118 $ 。

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

       • 令 $ MathJax-Element-120 $ ，计算 $ MathJax-Element-121 $ 。

         • 若 $ MathJax-Element-122 $ 或者 $ MathJax-Element-123 $ 时，停止迭代，此时 $ MathJax-Element-124 $ 。
         • 否则，令 $ MathJax-Element-360 $ ，计算梯度 $ MathJax-Element-344 $ 继续迭代。

     

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

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