运筹学（1）
多维无约束优化算法——梯度法之最速下降法

最近学习运筹学开始学习一些优化的算法，之后的一系列博客我会分享一些我学到的运筹学方法。这次我总结了我学习的最速下降法。

1. 原理
最速下降法是一个优化算法，用于求解多维无约束问题。最速下降法由于只考虑到当前下降最快而不是全局，所以最速下降法又叫做瞎子爬山法。最速下降法属于求解非线性规划问题的迭代法。它的关键是得到每步迭代的方向 $p^{(k)}$ 和步长 $t$ 。

(1)搜索方向 $p^{(k)}$ 的确定
方向$p$为单位向量， $||p||=1$ ,从 $x^{(k)}$ 按方向 $p$ ,步长 $t$ 进行搜索得到下一点 $x^{(k+1)}=x^{(k)}+tp$ 。在这里我们用到泰勒展开式得：

$$f(x^{(k)}+tp)=f(x^{(k)})+t\Delta f(x^{(k)})^Tp+o(t)$$
可以得到在 $x^{(k)}$处的变化率：
$$\lim_{t \to 0} \frac{f(x^{(k)}+tp)-f(x^{(k)})}{t}=\lim_{t \to 0} \frac{t\Delta f(x^{(k)})^Tp+o(t)}{t}=\Delta f(x^{(k)})^Tp$$
从上式可以得到要使在 $x^{(k)}$ 下降速度最快就要使在 $x^{(k)}$ 的变化率最小，所以就要使 $\Delta f(x^{(k)})^Tp$ 最小。然而 $\Delta f(x^{(k)})^Tp=||\Delta f(x^{(k)})||\cdot||p||\cdot cos\theta=||\Delta f(x^{(k)})||\cdot cos\theta$ . 要使其最小就要使 $cos\theta=-1$ .可以得到 $p=-\frac{f(x^{(k)})}{||\Delta f(x^{(k)})||}$ .
从上述就可以确定最速下降法的搜索方向为 $p=-f(x^{(k)})$ .

(2)求解搜索步长 $t$
最速下降法所采取的搜索步长的策略有两种：
一种是最优步长搜索法，即 $f(x^{(k)}+tp)=\min{f(x^{(k)}+tp)}$ .通过求最小值求得步长。

另一种是近似最佳步长

$$f(x^{k}-t\Delta f(x^{(k)}))\approx f(x^{(k)})-t\Delta f(x^{(k)})^T\Delta f(x^{(k)})+\frac{1}{2}t\Delta f(x^{(k)})^TH(x^{(k)})t\Delta f(x^{(k)}).$$
对上式求导并等于零，可以得到步长 $t=\frac{\Delta f(x^{(k)})^T\Delta f(x^{(k)})}{\Delta f(x^{(k)})^TH(x^{(k)})\Delta f(x^{(k)})}$ 。

2.算法步骤
(1).选取初始点 $x^{(0)}$ ,设置终止误差 $\epsilon>0$ ，$k=0$
(2).计算$\Delta f(x^{(k)})$,如果$\Delta f(x^{(k)})<\epsilon$搜索迭代终止，否则继续下一步。
(3).计算搜索方向$p$
(4).计算搜索步长t,可以得到$x^{(k+1)}=x^{(k)}+tp$.接着进行第(2)步。

3.例子

用最速下降法求解无约束非线性规划问题

$$\min f(x)=x_1^2+2x_2^2-2x_1x_2-2x_2$$
其中 $x=(x_1,x_2)^T$,要求选取初始点 $x^{(0)}=(0,0)^T$.

解:(1)$\Delta f(x)=(2x_1-2x_2,4x_2-2x_1-2)^T$
(2)$\Delta f(x^{(0)})=(0,-2)^T$
(3)$p=-\Delta f(x^{(0)})=(0,2)^T$
(4)求步长$t$,用最优步长策略：
$f(x^{(1)})=f(x^{(0)}+tp)=\min{f(x^{(0)}+tp)}$
得步长$t=\frac {1}{4}$
(5)$x^1=x^0+tp=(0,\frac{1}{2})^T$
按照上述方法继续迭代直到达到迭代终止条件，$x^*=1$

4.优缺点

优点：
（1）每一步迭代简单，对初始点要求少
缺点：
（1）由于是对每一步进行最优迭代，但是整体的收敛下降速度不一定最快。
（2）用最速下降法求最优问题，迭代路径呈直角锯齿形如下图，开始的几步迭代很快，但越接近最优点收敛速度越慢。

这是我第一次写博客，如有写的不好的地方希望大家提提建议，谢谢哈！！！