非线性优化算法 (待续)
- Newton’s method (牛顿迭代法)
- Gradient descent (梯度下降法)
- Conjugate gradient method (共轭梯度法)
- Powell’s method (鲍威尔法)
- Gauss–Newton algorithm (高斯牛顿法)
- Levenberg–Marquardt algorithm (列文伯格 - 马夸尔特法)
Newton’s method
牛顿迭代法 用于求一元函数 $f(x)$ 零点 $x^*$, 基于初始值 $x_0$ 和迭代公式 $x_{n+1} = x_{n} - \frac{f(x_n)}{f’(x_n)}$ 来逐步逼近目标解.
其中 $(x_{n+1}, 0)$ 是曲线 $y = f(x)$ 在 $(x_n, f(x_n))$ 处的切线与 x- 轴的交点.
Gradient descent
梯度下降法 (Gradient descent), 又称最速下降法(steepest descent) 是一种用于求可微函数的局部极值点的一阶迭代优化算法.
对于多元函数 $f(\mathbf{x})$, 如果它在点 $\mathbf{x}$ 的邻域内可微, 则 $f(\mathbf{x})$ 的值在沿着该点处的梯度向量的反方向 ($-\nabla f(\mathbf{x})$) 下降得最快.
从而按照迭代公式 $\mathbf{x_{n+1}} = \mathbf{x_{n}} - \gamma \nabla f(\mathbf{x_n})$, 且选择一个足够小的步长 (学习率) $\gamma\in R^+$ 时, 有 $f(\mathbf{x_{n}}) \ge f(\mathbf{x_{n+1}})$. 基于初始值 $x_0$ 和该迭代公式, 可以得到单调序列 $f(\mathbf{x_{0}}) \ge f(\mathbf{x_{1}}) \ge f(\mathbf{x_{2}}) \ge \cdots$, 这样 序列 $(\mathbf{x_{n}})$ 就 有可能 收敛到局部极值点.
注意:
- 在不断迭代的过程中, 步长 $\gamma$ 是可以改变的, 太小则收敛过慢, 太大则可能无法收敛, 因此需要选取合适的步长序列 $\gamma_{n}$.
- 迭代更新的方向向量 $\mathbf{p_{n}}$, 并不一定要沿着梯度的反方向, 尽管偏离最速下降的方向有点反直觉, 但“小斜率”可以通过“大步长”来得到补偿.
- 综上两点, 可以考虑一个更加通用的迭代公式:
$\mathbf{x_{n+1}} = \mathbf{x_{n}} - \gamma_{n} \mathbf{p_{n}}$
求解线性方程
对于如下方程 $$ A\mathbf{x} - \mathbf{b} = 0 $$
构造目标函数 $f(\mathbf{x}) = || A\mathbf{x} - \mathbf{b} ||^2 = (A\mathbf{x} - \mathbf{b})^{\top}(A\mathbf{x} - \mathbf{b})$,
其梯度为 $\nabla f(\mathbf{x}) = 2 A^{\top} (A\mathbf{x} - \mathbf{b})$
实际上对于线性方程的求解, 共轭梯度法 是一个比梯度下降法更好的选择.
求解非线性方程
考虑如下的非线性方程组
$$
\begin{cases}
3 x_1-\cos \left(x_2 x_3\right)-\frac{3}{2}=0 \\
4 x_1^2-625 x_2^2+2 x_2-1=0 \\
\exp \left(-x_1 x_2\right)+20 x_3+\frac{10 \pi-3}{3}=0
\end{cases}
$$
构造函数
$$
G(\mathbf{x}) =
\begin{bmatrix}
3 x_1-\cos \left(x_2 x_3\right)-\frac{3}{2} \\
4 x_1^2-625 x_2^2+2 x_2-1 \\
\exp \left(-x_1 x_2\right)+20 x_3+\frac{10 \pi-3}{3}
\end{bmatrix},
$$
其中 $\mathbf{x} = [x_1, x_2, x_3]^{\top}$ 为列向量.
从而可以定义目标函数 $f(\mathbf{x}) = \frac{1}{2}G^{\top}(\mathbf{x})G(\mathbf{x})$.
基于初始值 $x^{(0)} = \mathbf{0} = \begin{bmatrix}0\\ 0 \\ 0 \end{bmatrix}$, 和迭代公式 $\mathbf{x}^{(n+1)} = \mathbf{x}^{(n)} - \gamma_{n}\nabla f(\mathbf{x}^{(n)}) = \mathbf{x}^{(n)} - \gamma_{n} J_{G}(\mathbf{x}^{(n)})^{\top}G(\mathbf{x}^{(n)}) $,
其中 $J_{G}(\mathbf{x})$ 为 $G(\mathbf{x})$ 的 Jacobian 矩阵, 遵循 分子布局, 具体为
$$
J_G(\mathbf{x})=\left[\begin{array}{ccc}
3 & \sin \left(x_2 x_3\right) x_3 & \sin \left(x_2 x_3\right) x_2 \\
8 x_1 & -1250 x_2+2 & 0 \\
-x_2 \exp \left(-x_1 x_2\right) & -x_1 \exp \left(-x_1 x_2\right) & 20
\end{array}\right] .
$$
然后只需要选择足够小的步长序列 $\gamma_{n}$ 确保目标函数随着迭代过程单调递减, 即可收敛到局部极值点.
Conjugate gradient method
共轭梯度法
Powell’s method
鲍威尔法又称方向加速法，它由 Powell 于 1964 年提出，是利用共轭方向可以加快收敛速度的性质形成的一种搜索方法。该方法不需要对目标函数进行求导，当目标函数的导数不连续的时候也能应用，因此，鲍威尔算法是一种十分有效的直接搜索法。
Powell 法可用于求解一般无约束优化问题，对于维数 n<20 的目标函数求优化问题，此法可获得较满意的结果。
不同于其他的直接法，Powell 法有一套完整的理论体系，故其计算效率高于其他直接法。该方法使用一维搜索，而不是跳跃的探测步。同时，Powell 法的搜索方向不一定为下降方向。