最速下降法
无约束极值问题的一般形式为
$$ \min f(X),X\in E^{(n)} $$
函数$f(X)$是一阶或者二阶可微的。
定义
最速下降法又称梯度法，是求解无约束极值问题其他解析法的基础。
如果在$X^0\in E^{(n)}$ 处，$\nabla f(X^0)\neq0$ ,所有使
$$ \nabla f(X^0)^TP<0 $$
成立的非0向量$P\in E^n$ ,都是$f(X)$ 在$X^0$ 处的下降方向，这时对于充分小的$\lambda>0$,必有$$f(X^0+\lambda P)<f(X^0） $$ 若记$X^1=X^0+\lambda P$ ，那么上式可写为$f(X^1)<f(X^0)$ 。
这表明，只要选取适当的方向$P$和$\lambda$ ,使之满足上式，便可保证函数值$f(X^0)$有所下降，其中$\lambda$ 称之为步长。现在的问题是应该如何选取方向$P^0$ 和$\lambda_0$ ,使得$\lambda_0\nabla f(X^0)^TP^0$ 尽可能地小。从而使$$f(X^0+\lambda_0P^0)=f(X^0)+\lambda_0\nabla f(X^0)^TP^0+O(\lambda_0)$$ 可能地小。首先。由向量代数知道$$\nabla f(X^0)^TP^0=\Vert \nabla f(X^0)\Vert_2\cdot\Vert P^0\Vert_2\cdot \cos\theta$$ 其中$\theta$是$\nabla f(X^0)$ 与$P^0$ 间的夹角。由此可以看出，当$\theta=\pi$ ,即$P^0=-\nabla f(X^0)$ 时，$\nabla f(x^0)P^0$ 取最小值，也就是说，在$X^0$ 处，沿着负梯度方向，是$f(X)$ 下降最快的方向。所以当取$P^0=-\nabla f(X^0)$ 时，算法称为最速下降法或者梯度法。
步长的确定方法
- 定长法
每次迭代都取$\lambda_k$ 为相同的值$\lambda$ .不过这里的搜索方向$P^k$ 都是单位向量，即$$P^K=\frac{\nabla f(X^k)}{\Vert\nabla f(X^k)\Vert_2}$$ - 最优步长法
在迭代过程中，每次$\lambda_k$ 是一个与$X^k$ 有关的变量，即由$$\min f(X^k-\lambda\nabla f(X^k)),\lambda\geq0$$ 来确定$\lambda_k$ ,这样的$\lambda_k$ 成为最优步长。
计算步骤：
首先给定初始近似点$x^0$和精度$\epsilon>0$ ,令$k=0$ .
- 计算$\nabla f(X^K)$ ,若$\Vert\nabla f(X^0)\Vert^2<\epsilon$ ,则称$X^0$ 即为所求近似极小点，结束；否则转入下步。
- 求$\min f(X^0-\lambda\nabla f(X^0)),\lambda\geq0$ 得$\lambda_0$ ,并计算$X^0-\lambda_0\nabla f(X^0)$ ,$K\Rightarrow1$ .
- 一般地，若求得$X^k$ ,则计算$\nabla f(X^k)$ ,若$\Vert\nabla f(X^k)\Vert^2\leq\epsilon$ ,则$X^k$ 为所求近似极小点，否则转入下步。
求$\min f(X^k-\lambda\nabla f(X^k))$ ,得$\lambda_k$ 并计算
$X^{k+1}=X^k-\lambda_k\nabla f(X^k),k\Rightarrow k+1$
转第3步继续迭代，直至满足精度要求为止。参考文献
运筹学高级教程 沈荣芳 第二版
