BFGS优化算法的C++实现

BFGS算法是一种非常常用的无约束优化算法，可以用于寻找函数的全局最小值或局部最小值。以下是BFGS算法的C++实现代码：

#include <iostream>
#include <cmath>
#include <vector>
#include <Eigen/Dense> // Eigen库，用于矩阵计算

using namespace std;
using namespace Eigen;

// 目标函数
double f(const VectorXd& x)
{
    double y = pow(x(0) - 1, 2) + pow(x(1) - 2.5, 2);
    return y;
}

// 梯度函数
VectorXd grad(const VectorXd& x)
{
    VectorXd g(2);
    g(0) = 2 * (x(0) - 1);
    g(1) = 2 * (x(1) - 2.5);
    return g;
}

// BFGS优化算法
VectorXd bfgs(const VectorXd& x0, int maxiter, double tol)
{
    int n = x0.size();
    MatrixXd B = MatrixXd::Identity(n, n); // 初始化Hessian矩阵的逆矩阵B
    VectorXd x = x0; // 初始化参数向量
    VectorXd g = grad(x); // 计算梯度
    int k = 0; // 迭代次数
    double alpha; // 步长

    while (k < maxiter && g.norm() > tol)
    {
        // 计算搜索方向d
        VectorXd d = -B * g;

        // 一维搜索，计算步长alpha
        double t = 1.0; // 初始步长
        double c = 0.5; // Armijo条件中的常数，取值范围为(0, 1)
        double rho = 0.9; // 步长更新的阻尼系数，取值范围为(0, 1)
        double phi = f(x + t * d); // 目标函数在x + t * d处的函数值
        double phi0 = f(x); // 目标函数在x处的函数值
        double dphi = grad(x).dot(d); // 目标函数在x处的梯度在d方向上的投影
        while (phi > phi0 + c * t * dphi)
        {
            t = rho * t;
            phi = f(x + t * d);
        }
        alpha = t;

        // 更新参数向量x
        x = x + alpha * d;

        // 计算梯度及其变化量
        VectorXd gnew = grad(x);
        VectorXd dg = gnew - g;
        g = gnew;

        // 更新逆Hessian矩阵B
        MatrixXd I = MatrixXd::Identity(n, n);
        B = (I - (alpha * d * dg.transpose()) / (d.transpose() * dg)) * B * (I - (dg * d.transpose()) / (d.transpose() * dg)) + (alpha * d * d.transpose()) / (d.transpose() * dg);

        k++; // 迭代次数加1
    }

    return x;
}

int main()
{
    // 初始化参数向量
    VectorXd x0(2);
    x0(0) = 0;
    x0(1) = 0;

    // 调用BFGS算法进行优化
    VectorXd x = bfgs(x0, 100, 1e-6);

    // 输出结果
    cout << "x = " << x.transpose() << endl;
    cout << "f(x) = " << f(x) << endl;

    return 0;
}

代码中的目标函数为$f(x_1, x_2) = (x_1 - 1)^2 + (x_2 - 2.5)^2$，梯度为$\nabla f(x_1, x_2) = [2(x_1 - 1), 2(x_2 - 2.5)]^T$。BFGS算法中的一维搜索使用了Armijo条件。在调用BFGS算法时，需要指定初始参数向量$x_0$、最大迭代次数$maxiter$和停止迭代的误差限制$tol$。在本例中，初始参数向量为$(0, 0)^T$，最大迭代次数为$100$，误差限制为$10^{-6}$。最终输出结果为：

x = 1 2.5
f(x) = 0

即$x^* = (1, 2.5)^T$是目标函数的全局最小值点，目标函数在$x^*$处的最小值为$0$。