多变量无约束非线性优化问题

回顾单变量形式中的问题 Formulation，其中的 search direction $\bold s^{(q)}$ 通常由当前的函数值 $f(\bold x)$ 和当前的 Gradient Vector $\nabla f(\bold x)$

有的方法使用到了 $f(\bold x)$ 的一阶导数，被称为 First-order methods; 有的只使用函数值，不用导数，称为 Zeroth-order methods.

Steepest Descent Method

易于理解，每一次迭代的搜索向量就是当前梯度向量的负数

\bold s^{(q)}=-\nabla f\Big(\bold x^{(q)}\Big)

那么我们什么时候停止呢？我们可以检查连续两次迭代函数值的差值，只要小于一定误差即认为收敛。

\Big| f(\bold x^{(q+1)}) - f(\bold x^{(q)}) \Big| \le \epsilon_f

然而通常不能取得很好的效果，一是因为 steepest descent 在 local context 上表现良好，但不一定在 global context 上表现良好；二是因为这个方法有个性质，下一步迭代的方向与上一次正交，这导致搜索路径变成了 zig-zag，而且通常在前几步迭代下降的快，后续迭代中速度变慢，进而引发 (1) 迭代次数增多 (2) 收敛慢。

为什么会正交？从 $\bold x^{(q-1)}$ 到 $\bold x^{(q)}$ 的过程中，总有变量的梯度在 $\bold x^{(q)}$ 处变成 $0$ ， $\nabla f(\bold x^{(q)})$ 对这些变量的导数为 $0$ ，转而通过其他变量的梯度降低函数值，导致了连续两次迭代的 search vector 正交。

Conjugate Gradient Method

可以看成是 Improved Steepest Descent Method，区别在于用 Exponential Moving Average 的方式改进了下一步迭代的 search vector.

\begin{array}{rll} \bold s^{(0)} &= &-\nabla f(\bold x^{(0)})\\ \bold s^{(q+1)} &= &-\nabla f(\bold x^{(q+1)})+\beta^{(q+1)}\cdot \bold s^{(q)}\\ \end{array}

其中 $\beta^{(q+1)}$ 表示前后两次迭代梯度 magnitude 的比值，即

\beta^{(q+1)}=\frac{\Big|-\nabla f(\bold x^{(q+1)})\Big|^2}{\Big|-\nabla f(\bold x^{(q)})\Big|^2}

Hooke and Jeeves Method

Hooke-Jeeves 法不使用导数，只使用函数值进行迭代。在上面两种方法里，每一步迭代的步长由梯度向量决定，而在 Hooke-Jeeves 法里，每一步迭代的步长是 pre-determined on prescribed value 的.

算法流程

我们需要先选择初始点 base point $\bold x^{(0)}$ 和对应的函数值 $f(\bold x^{(0)})$

接着，我们需要对每一个变量定义初始步长 $\Delta_i$ 和失败衰减 $d_i$ . 然后交替进行 Exploratory Search 和 Pattern Move.

我们先进行 Exploratory Search. 对于每个 variable $x_i$ 都进行两次尝试，我们先检查 $x_i+\Delta_i$ （其他变量不变）能否减小 $f()$ ，不能话尝试 $x_i-\Delta_i$ （其他变量不变）。

如果能够减小，那么我们固定下 $x_i\plusmn \Delta_i$ 然后继续检查下一个 $x_{i+1}$
- 如果不能，则先跳过。
如果在所有方向上都不能减小 $f()$ ，则缩小步长，即令 $\Delta_i\gets \Delta_i \times d_i$ .
- 如果对于所有变量，缩小前的步长大于给定误差，那么就继续；否则直接结束。

在尝试完所有的 $x_i$ 后，我们得到一个新的 base point $\bold x^{(q)}$ ，然后尝试 Pattern Move. Pattern Move 可以理解为：尝试复制 $\bold x^{(q-1)}\to \bold x^{(q)}$ 的走法.

\bold x^{(q)}_{\text{pattern}} = \bold x^{(q)}+\Big( \bold x^{(q)} - \bold x^{(q-1)} \Big)

$\bold x^{(q)}_{\text{pattern}}$ 称为 Pattern Point，

如果这个点更好，那么我们以这个点为新的起点（然而并不算作 base point），在其基础上重新开始 Exploratory Search.
如果这个点并不优，我们直接忽略，在上一个 base point 的基础上进行 Exploratory Search.

终止条件是，某次迭代中，所有变量的步长都小于等于某个给定的误差，即 $\Delta x_i\le \epsilon_{\Delta i}$

最终的结果就是最后一个 base point.

我们可以把 Exploratory Search 看作是确定 search vector $\bold s^{(q)}$ ，Pattern Move 可以看作是 $\bold x^{(q+1)}\gets \bold x^{(q)} + \bold s^{(q)}$ 的转移。