Armijo-Wolfe 准则笔记

设函数 $f(x)$ 为二次函数，使用线搜索来求解最小值。在线搜索中需要对当前迭代点进行更新：

$$ x^{k+1} = x^{k} + \alpha d^k\;, $$

其中 $\alpha \ge 0$ 是迭代的步长，$d^k$ 是迭代方向，设 $d^k$ 满足 $\nabla f(x^k)^\top d^k < 0$，即 $d^k$ 是下降方向。我们用一个辅助函数 $\Phi$ 来描述步长 $\alpha$：

$$ \Phi(\alpha) = f(x^{k} + \alpha d^k)\;, $$

则有：

$$ \nabla \Phi(\alpha) = \nabla f(x^{k} + \alpha d^k)^\top d^k\;, $$

Armijo 准则

$$ f(x^k + \alpha d^k) \le f(x^k) + c_1 \alpha \nabla f(x^k)^\top d^k\;, $$

即

$$ \Phi(\alpha) \le \Phi(0) + c_1 \alpha (\nabla \Phi(0))\;. $$

其中 $c_1$ 是一个常数，满足 $c_1 \in (0, 1)$。

Armijo 准则主要是为了约束每次迭代下降的步长能够确保其能够充分下降，避免下降步长太大导致函数值没有下降甚至上升。

弱 Wolfe 准则

Wolfe 准则又称为 Armijo-Wolfe 准则，这里给出弱 Wolfe 准则条件，内容如下：

$$ \begin{aligned} f(x^k + \alpha d^k) \le f(x^k) + c_1 \alpha \nabla f(x^k)^\top d^k\;, &\qquad\text{(Armijo 准则)}\\ \nabla f(x^k + \alpha d^k)^\top d^k \ge c_2 \nabla f(x^k)^\top d^k\;. &\quad \end{aligned} $$

Wolfe 准则第一条是 Armijo 准则，用来确保下降充分。第二条是为了让下降的步长足够大，如果使用 $\Phi$ 函数表示为：

$$ \nabla \Phi(\alpha) \ge c_2 \nabla \Phi(0)\;. $$

其中 $c_2$ 是一个常数，$c_1$、$c_2$ 满足 $0 < c_1 < c_2 < 1$。Wolfe 准则的第二条是为了确保步长足够大，使用 $c_2$ 控制曲率的变化量。

本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可。This work is licensed under the Creative Commons Attribution-NonCommercial 4.0 International License.