优化理论之一维优化-步长控制-线搜索与置信域

步长控制-线搜索与置信域

注1：本文讨论需要优化的函数都是单峰函数（或单谷函数）。

在最优化(optimization)问题中，线搜索(line search)和置信域(trust region)方法是寻找局部最小值(local minimum)基本迭代方法(iterative approach)。

• 线搜索(Line search)
• 精确线搜索步长
• 非精确线搜索步长
  • Wolfe conditions
  • Armijo conditions

线搜索(Line search)

以f(x)为例，线搜索会先找一个使f(x)下降的方向，接着计算一个步长，步长决定了x改变的大小。

下降方向:可以通过梯度下降，牛顿法，拟牛顿法等计算。

步长:有精确(exact)和非精确(inexact)两种，精确方法就是找出导数为零的极值点，例如共轭梯度法conjugate gradient method;非精确方法没有找出导数为零的点，而是使f(x)有一个充分的下降(sufficient descent)，例如backtracking，wolfe conditions，goldstein conditions

线搜索流程:

1. 计算线搜索方向\(\vec{p}_k\)，使得该方向满足\(\nabla f^T_k\vec{p}_k<0，\nabla f_k\ne\vec{0}\)。（满足上述不等式则该方向为下降法向，因为\(\nabla f_k\)是方向上升方向，其夹角只有大于180度才会为负）
2. 计算步长\(\alpha_k>0\)，使得\(f(x_k+\alpha_k*p_k)<f(x_k)\)
3. 更新\(x:x_{k+1}=x_k+\alpha_k*p_k\)

(完全囊括了梯度算法和牛顿类算法的框架，如图1所示。)

精确线搜索步长

如何确定合适的步长呢？如果我们从表达式上来看，令步长\(\alpha\)为自变量： \[\phi(\alpha)=f(x_k+\alpha*p_k),\alpha>0\] 在方向\(\vec{p}_k\)已经确定的情况下，\(\alpha\)的最佳选择无疑是使\(\phi(\alpha)\)的值最小，即使得在给定方向上下降最大的距离。但是，这计算起来有些不切实际，因为计算\(\phi\)函数的最小值增加了大量计算量，尤其是\(\phi\)函数有不少局部最小值和稳定点的时候，如图2所示：

常见精确搜索方法（在导数不可求得情况下用的）：

1. 二分搜索
2. 斐波那契搜索
3. 黄金分割搜索
4. 二次插值法
5. 三次插值法
6. D.S.C.法

精确搜索法的核心是找到到达函数最小值的步长。但是一个实用的正常寻找合适步长的法子比找到\(\phi\)函数最小值要容易的多，只要使目标函数的值下降即可（不会震荡到函数值更高的点），用表达式来说就是： \[f(x_k+\alpha*p_k)<f(x_k)\] 该方法不能保证收敛到函数的最小值，因此我们可以添加两个条件，来要求在每次迭代过程中都要显著地减小目标函数。

非精确线搜索步长

Wolfe conditions

Wolfe conditions 由 Armijo conditions和Curvature conditions构成,先分别介绍Armijo conditions和Curvature conditions

Armijo conditions