数值优化（五）——最速下降法实战

mastertravels77 · 发表于 2022-5-1 13:21

通过前几章节的学习，我们从数学理论上梳理了线搜索算法的基本概念，其求解的关键便是下式：

$x_{k+1} = x_k + \alpha_k p_k \quad (0)$
可以分解为两个问题：(1)如果确定搜索方向 $p_k$ ，(2)如何确定搜索步长 $\alpha_k$ 。对于第一个问题，有最速下降法、牛顿法等方向算法，而第二个问题可以通过Wolfe条件来确定步长。因此对于线搜索算法的整体流程，可以总结为下面的伪代码：
x = init()
while
v, g = f(x)
if g.norm() < epslion
      break
p = find_direction(x, g, v) // 1
alpha = step_search(x, g, v) // 2
x = x + alpha * p
核心便是每次迭代中计算(1)和(2)。
对于最速下降法来说，它的搜索方向便是梯度反方向，因此我们现在可以说是完全掌握了最速下降法的全部细节，正好可以实现一个最速下降算法来巩固加深。
完整的实现代码可以在github上的Chimes(https://github.com/BKHao/Chimes)中找到。
首先，对于线搜索这一类算法，其不同点便在与如何确定搜索方向，他们的搜索步长行为是相通的，因此可以抽象为一个基类，便于以后扩展。
首先抽象出一个基类LineSearchMethod，我们在基类中初始化参数和实现步长搜索。
line_search.h
int stepSearch(
Scalar& fval, Vector& iter_x, Vector& gradient, Scalar& step, const Vector& direction)
{
...
while (1)
      {
         iter_x = ix + step * direction;
         fval = fun_(iter_x, gradient);
         if (fval > ifval + step * idescent) // 1 充分下降条件
         {
            step_u = step;
         }
         else
         {
            if (parameter_.step_search_method_ == StepSearchMethod::SUFFICIENT_DECREASE)
            {
                  break;
            }
            ndg = gradient.dot(direction);
            if (ndg < parameter_.wolfe_ * idg) // 2 Wolfe 条件
            {
                  step_l = step;
            }
            else
            {
                  if (parameter_.step_search_method_ == StepSearchMethod::WOLFE)
                  {
                     break;
                  }
                  if (ndg > -parameter_.wolfe_ * idg) // 3 强Wolfe条件
                  {
                     step_u = step;
                     }
                  else
                  {
                     break;
                  }
            }
         }
         ++k;
         step = isinf(step_u) ? 2 * step : 0.5 * (step_l + step_u); // 4 放缩步长
      }
...
}
其核心也就在一个循环中，关键的三处地方分别判断充分下降条件(1)、Wolfe条件(2)和强Wolfe条件(3)，根据参数选择合适的条件终止循环。如果不符合条件，则在(4)出放缩步长，step_l和step_u分别是步长的上界和下界，初始是从0到无穷大。
然后我们在子类SteepestDescent中实现伪代码中的求解过程，因为最速下降法的方向就是梯度负方向，因此实现也就主要是调用步长搜索确定步长。
steepest_descent.h
virtual void solve()
{
...
Vector gradient(n); // 1 初始化变量
gradient.setZero();
Vector iter_x = init_x_;
Scalar fval = fun_(iter_x, gradient);
Scalar step = Scalar(1.0) / direction.norm();
while (1)
{
      if (gradient.norm() < parameter_.epsilon_) // 2 判断是否达到停止条件
         break;
      int num_step_search = Base::stepSearch(
         fval, iter_x, gradient, step, direction); // 3 搜索步长
      direction = -gradient; // 4 准备下一轮迭代
      step = Scalar(1.0) / direction.norm();
}
...
}
可以看出，最速下降法其实是很简单的算法，优化迭代本身并没有多少代码了，但可以帮我们理清楚线搜索算法的整个框架，是个不错的开端。需要注意的是在(4)处我们并没有显式的更新iter_x、fval和gradient，因此在步长搜索stepSearch()中我们已经实时的将它们更新了，避免了重复计算。
对于 $f=(x-1)^2+(y-1)^2$ 这个优化问题，可以看到迭代过程和结果。

优化过程和结果

上面展示出的是算法的核心部分，也就是两个循环迭代，更具体的内容去Chimes中阅读，其中向量计算部分使用了第三方库Eigen，编译需要用到cmake工具。Chimes也正在持续开发中，后续算法实现也会在上面共享^_^

stonstad · 发表于 2022-5-1 13:27

[赞同]

		自动登录	找回密码
密码			立即注册

数值优化（五）——最速下降法实战

本帖子中包含更多资源