Numerical Optimization Line Search

线性搜索简介

数值优化是迭代式的优化方法，从一个初始点$x_0$开始，然后产生一个迭代方向$\nabla d_0$，在这个方向上选择一个步长$\alpha_0$，下一个点就是$x_0 + \alpha_0 * \nabla d_0$。
按照这样的方法不停的迭代下去，直到找到最优点。在这个过程中有两步是非常重要的。第一步就是计算出迭代方向$\nabla d_k$，第二步是在这个方向上选择合适的步长 $\alpha_k$，获得下一个点$x_{k+1}$。
第一步产生迭代方向 $\nabla d_k$ 是各种优化方法产生差别的地方，不同的方法有不同的方法生成迭代方向。但是对于不同的迭代方法都有一个最基本的要求，那就是这个方向必须是一个下降方向：$\nabla f(x_k) ^ T \cdotp \nabla d_k \lt 0$。其中$\nabla f(x_k)$ 是 $x_k$ 的梯度方向。

第二步称为线性搜索。在这个步骤上不同的方法基本都是相同的。在线性搜索方法中有两个比较重要的部分，首先是停止条件，第二个是步长选择算法。之所以要求满足停止条件而不是仅仅要求函数值有下降，是为了确保优化算法能够正常的收敛。
线性搜索问题可以如下形式化：

$$argmin_x \; f(x_{k+1}) = f(x_k + \alpha \cdotp \nabla x )$$
$$s.t. \quad \alpha \ge 0$$

终止条件

首先假设当前点 $x_k$ 的梯度是 $\nabla f(x_k)$，当前的迭代方向是 $\nabla d_k$，并且满足 $\nabla f(x_k) ^ T \cdotp \nabla d_k \lt 0$，并且当前的选择的步长为 $\alpha_0$。

Sufficient Descreasement Condition

这个条件也称为Armijo Condition，描述如下：

$$f(x_k + \alpha_0 \nabla d_k) \le f(x_k) + \alpha_0 \cdotp \rho g(x_k) ^T \nabla d_k$$
$$0 \lt \rho \lt 1/2$$
其中 $\rho$ 是用户指定的参数，一般来说这个参数的数量级大概为$1e-3$ 或者更低。但是仅仅使用这个条件并不能确保优化过程收敛。
但是当这个条件配合backtracking搜索方法的时候可以确保优化过程收敛。

Curvature Condition

$$\nabla f(x_k + \alpha_0 \nabla d_k) ^ T \nabla d_k \ge \delta \nabla f(x_k) ^ T \nabla d_k$$
$$s.t \quad \rho \lt \delta \lt 1$$
对于$delta$的取值一般比较大，比如0.8，0.9等等。这个值越大，对应的搜索越不精确。

Wolfe Condition

Wolfe Condition就是把Sufficient Decreasement Condition和curvature condition合并在一起，表述如下：

$$f(x_k + \alpha_0 \cdotp \nabla d_k) \le f(x_k) + \rho \; \alpha_0 f(x_k) ^ T \nabla d_k$$
$$\nabla f(x_k + \alpha_0 \nabla d_k) ^ T \nabla d_k \ge \delta \nabla f(x_k) ^ T \nabla d_k$$
$$s.t \quad 0 \lt \rho \lt \delta \lt 1$$
一般来说Wolfe Condition是用于拟牛顿方法。

Strong Wolfe Condition

$$f(x_k + \alpha_0 \cdotp \nabla d_k) \le f(x_k) + \rho \; \alpha_0 f(x_k) ^ T \nabla d_k$$
$$\left| \nabla f(x_{k+1}) ^ T \nabla d_k \right| \le \delta \left| \nabla f(x_k) ^ T \nabla d_k \right|$$
$$s.t \quad 0 \lt \rho \lt \delta \lt 1$$

Goldstein Condition

$$f(x_k + \alpha_0 \nabla d_k ) \le f(x_k) + \alpha_0 \cdotp \rho g(x_k) ^T \nabla d_k$$
$$f(x_k + \alpha_0 \nabla d_k ) \ge f(x_k) + \alpha_0 \cdotp (1-\rho ) g(x_k) ^ T \nabla d_k$$
$$s. t. 0 \lt \rho \lt 1/2$$

步长选择

这个一般可以使用多种不同的方法来选择，对于我来说还是喜欢用backtracking方法，主要的原因是这个方法比较简单且容易实现。而且可以配合多种不同的终止条件。

backtracking

backtracking基本来说是从某个步长开始，然后不停的缩小步长。知道找到满足终止条件的步长。

function [retval] = backtrack(x0, d0, f, c1, c2)
%line search algorithm based on backtracking to find point satisfy strong wolfe condition
% x0 : current point
% d0 : search direction
% f  : function will return value and gradient, [f, g] = f(x);
% 0 < c1 < c2 < 1

[f0, grad] = f(x0);
slope = grad' * d0;

if slope >= 0
   error('must be a descent direction')
end

alpha0 = 0;
alphaMax = 1e2;

alpha = 1;
dec = 0.5;
inc = 2.1;

while 1

      [current_val, current_grad] = f( x0 + alpha * d0);
      factor = 1;

     if current_val > ( f0 + alpha * c1 * slope)
        factor = dec;
     else
      current_slope = current_grad' * d0;

      if current_slope < c2 * slope
        factor = inc;
      else
          if current_slope > -c2*slope
         factor = dec;
          else
          break;
          end
      end
      end

      if alpha < 1e-15
        warning('too small step size')
      end

      if alpha > alphaMax
     warning('too large step size')
      end

      alpha = alpha * factor;
end
retval = alpha;
end

总结

线性搜索的性能对优化问题至关重要，简单且可靠的线性搜索方法可以解决很多的问题。一般来说，Goldstein条件适用于牛顿饭，Wolfe和strong Wolfe条件适用于拟牛顿法