优化算法之——最速下降法_顺盈平台官方指定注册站

优化算法之——最速下降法

信息来源：网络时间：2024-04-07 23:07

引言：在解决无约束问题时，经常用到的一类算法是最速下降法，在求解机器学习算法的模型参数，即无约束优化问题时，梯度下降（Gradient Descent）是最常采用的方法之一，另一种常用的方法是最小二乘法。在求解损失函数的最小值时，可以通过梯度下降法来一步步的迭代求解，得到最小化的损失函数和模型参数值。反过来，如果我们需要求解损失函数的最大值，这时就需要用梯度上升法来迭代了。在机器学习中，基于基本的梯度下降法发展了两种梯度下降方法，分别为随机梯度下降法和批量梯度下降法。本节主要介绍一下最速下降法。

本篇主要讨论如下的优化模型：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? $緻set{x\epsilon R^{2}}{min}f(x)$

其中 $f$ 是 $x$ 的实值连续函数，通常假定其具有二阶连续偏导数，对于 $maxf(x)$ 可以等价的转化为 $min(-f(x))$ ,所以下面仅讨论极小化问题。

? ? ? ?最速下降法由于只考虑当前下降最快而不是全局下降最快，在求解非线性无约束问题时，最重要的是得到每一步迭代的方向 $d^{(k)}$ 和每一步下降的长度 $\lambda ^{_{(k)}}$ 。考虑到函数 $f(x)$ 在点 $x^_{(k)}$ 处沿着方向 $d$ 的方向导数 $f_{d}(x^{(k)})= riangledown f(x^{(k)})^{T}d$ ,其意义是 $f(x)$ 在点 $x^{(k)}$ 处沿 $d$ 的变化率。当 $f$ 连续可微时，方向导数为负，说明函数值沿着该方向下降；方向导数越小（负值），表明下降的越快，因此确定搜索方向 $d^{(k)}$ 的一个想法就是以 $f(x)$ 在点 $x^{(k)}$ 方向导数最小的方向作为搜索方向。

1.1 搜索方向 $d^{(k)}$ 的确定

? ? ? ? ?设方向 $d$ 为单位向量， $\left \| d \right \|=1$ ,从点 $x^{(k)}$ 按方向 $d$ ,步长 $\lambda$ 进行搜索得到下一点 $x^{(k+1)}=x^{(k)}+\lambda_{k}d^{(k)}$ ，对该式进行泰勒展开得到：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? $f(x^{(k)}+\lambda_{k} d^{(k)})=f(x^{(k)})+\lambda_{k} riangledown f(x^{(k)})^{T}+o(\lambda )$

可以得到 $x^{(k)}$ 处的变化率：

? ? ? ? ? ? ? ? ? ? ? ? ? $\lim_{t\rightarrow 0}\frac{f(x^{(k)}+\lambda_{k} d^{(k)})-f(x^{(k)}))}{\lambda_{k} }=\lim_{t\rightarrow 0}\frac{\lambda_{k} riangledown f(x^{(k)})^{T}d^{(k)}+o(\lambda )}{\lambda_{k} }= riangledown f(x^{(k)})^Td^{(k)}$

容易看出来在 $x^{(k)}$ 下降最快就是要在 $x^{(k)}$ 出的变化率最大，所以就是要使 $riangledown f(x^{(k)})^Td^{(k)}$ 最小（ $riangledown f(x^{(k)})^Td^{(k)}<0$ ）,而对于

$riangledown f(x^{(k)})^Td^{(k)}=\left \| riangledown f(x^{(k)}) \right \|\cdot \left \| d^{(k)} \right \|\cdot cos heta$ ，要使其最小就是当 $cos heta =-1$ 时，

$d^{(k)}=-\frac{ riangledown f(x^{(k)})}{ riangledown \left \| f(x^{(k)}) \right \|}$ ，即可以确定最速下降方向为 $- riangledown f(x^{(k)})$ ,这也是最速下降法名字的由来。

1.2 步长 $\lambda^{(k)}$ 的确定

最速下降法采用的搜索步长通常采取的策略是精确步长搜索法，即： $\lambda_{k}=argminf(x^{(k)}+\lambda_{k}d^{(k)})$ ,通过求该式子的最小值点来求取步长，一般有：

? ? $\frac{df(x^{(k)}+\lambda d^{(k)})}{d\lambda}=d^{(k)} riangledown f(x^{(k)})=0$ ，该式表明 $d^{(k)}$ 和 $d^{(k+1)}$ 是正交的。在这里我没有用该方法，而是用一维搜索方法（黄金分割法<0.618法>）来近似找到最小值点，通过自己编程实现一维搜索更好的理解这个过程，最终的结果与精确搜索几乎一致。