L-BFGS-B(Limited-memory Broyden–Fletcher–Goldfarb–Shanno )算法理解_附代码

L-BFGS-B(Limited-memory Broyden–Fletcher–Goldfarb–Shanno )算法理解

定义

有限内存BFGS（L-BFGS或LM-BFGS）是牛顿方法家族中的一种优化算法，它使用有限数量的计算机内存近似于Broyden-Fletcher-Goldfarb-Shanno算法（BFGS）。

作用

L-BFGS是机器学习中用于参数估计的流行算法。该算法的目标问题是最小化f(x)在实向量的无约束值上的x,这里f是一个可微标量函数。

代码

要使用LBFGS ++，首先需要定义子函数以表示要最小化的多元函数。它应该返回向量x上的目标函数值，并用x上计算的梯度grad覆盖向量。例如，我们可以通过以下方式定义Rosenbrock函数：

#include <Eigen/Core>
#include <iostream>
#include <LBFGS.h>

using Eigen::VectorXd;
using namespace LBFGSpp;

class Rosenbrock
{
private:
    int n;
public:
    Rosenbrock(int n_) : n(n_) {}
    double operator()(const VectorXd& x, VectorXd& grad)
    {
        double fx = 0.0;
        for(int i = 0; i < n; i += 2)
        {
            double t1 = 1.0 - x[i];
            double t2 = 10 * (x[i + 1] - x[i] * x[i]);
            grad[i + 1] = 20 * t2;
            grad[i]     = -2.0 * (x[i] * grad[i + 1] + t1);
            fx += t1 * t1 + t2 * t2;
        }
        return fx;
    }
};

然后，我们只需要设置参数，创建求解器对象，提供初始猜测，然后运行最小化功能。

int main()
{
    const int n = 10;
    // Set up parameters
    LBFGSParam<double> param;
    param.epsilon = 1e-6;
    param.max_iterations = 100;

    // Create solver and function object
    LBFGSSolver<double> solver(param);
    Rosenbrock fun(n);

    // Initial guess
    VectorXd x = VectorXd::Zero(n);
    // x will be overwritten to be the best point found
    double fx;
    int niter = solver.minimize(fun, x, fx);

    std::cout << niter << " iterations" << std::endl;
    std::cout << "x = \n" << x.transpose() << std::endl;
    std::cout << "f(x) = " << fx << std::endl;

    return 0;
}

最后可以编译并运行该示例。

$ g++ -I/path/to/eigen -I/path/to/lbfgspp/include -O2 example.cpp
$ ./a.out
23 iterations
x =
1 1 1 1 1 1 1 1 1 1
f(x) = 1.87948e-19

补充

1. 更多代码和API接口都在代码里面。
2. 与原始的BFGS一样，L-BFGS使用逆黑森矩阵的估计来引导其搜索通过可变空间，但BFGS存储了密集空间n×n近似于逆黑森量（n 是问题中的变量数），L-BFGS 仅存储几个隐式表示近似的向量。由于其由此产生的线性内存要求，L-BFGS方法特别适用于许多变量的优化问题。
   L-BFGS 不是逆黑森 Hk，而是维护位置 x 和梯度 ∇f（x） 的过去 m 个更新的历史记录，其中通常历史大小 m 可以很小（通常 m<10)。这些更新用于隐式执行需要 Hk 向量积的操作。