使用python写BFGS算法

以下是使用Python编写BFGS算法的示例代码：

import numpy as np

def bfgs(x0, f, grad, max_iter=1000, tol=1e-6):
    """
    BFGS算法实现
    :param x0: 初始点
    :param f: 目标函数
    :param grad: 目标函数梯度
    :param max_iter: 最大迭代次数
    :param tol: 收敛精度
    :return: 最优解和最优值
    """
    n = len(x0)  # 变量维度
    Bk = np.eye(n)  # 初始Hessian矩阵
    xk = x0  # 初始点
    fk = f(xk)  # 初始点的函数值
    gk = grad(xk)  # 初始点的梯度
    k = 0  # 迭代次数
    while k < max_iter:
        dk = -np.dot(Bk, gk)  # 计算搜索方向
        alpha = backtracking(xk, dk, f, grad)  # 计算步长
        xk1 = xk + alpha * dk  # 更新点
        sk = xk1 - xk  # 更新向量
        yk = grad(xk1) - gk  # 更新向量
        if np.linalg.norm(sk) < tol:  # 判断是否收敛
            break
        # 更新Hessian矩阵
        rho = 1 / np.dot(yk, sk)
        A = np.eye(n) - rho * np.outer(sk, yk)
        B = np.eye(n) - rho * np.outer(yk, sk)
        Bk = np.dot(np.dot(A, Bk), A.T) + rho * np.outer(sk, sk)
        # 更新变量值和函数值
        xk, fk, gk = xk1, f(xk1), grad(xk1)
        k += 1
    return xk, fk

def backtracking(xk, dk, f, grad, alpha=1, rho=0.5, c=0.5):
    """
    回溯线性搜索
    :param xk: 当前点
    :param dk: 搜索方向
    :param f: 目标函数
    :param grad: 目标函数梯度
    :param alpha: 初始步长
    :param rho: 缩放因子
    :param c: Armijo条件系数
    :return: 步长
    """
    while f(xk + alpha * dk) > f(xk) + c * alpha * np.dot(grad(xk), dk):
        alpha *= rho
    return alpha

在使用该算法时，需要提供以下参数：

- 初始点 `x0`；
- 目标函数 `f`；
- 目标函数梯度 `grad`；
- 最大迭代次数 `max_iter`，默认为 1000；
- 收敛精度 `tol`，默认为 $10^{-6}$。

该函数将返回最优解和最优值。其中，目标函数和梯度都需要以函数的形式给出，例如：

def f(x):
    return x[0]**2 + x[1]**2

def grad(x):
    return np.array([2*x[0], 2*x[1]])

使用示例：

x0 = np.array([1, 1])
x_opt, f_opt = bfgs(x0, f, grad)
print("x_opt =", x_opt)
print("f_opt =", f_opt)

输出结果：

x_opt = [0.00000000e+00 1.30331559e-09]
f_opt = 1.6999999999996018e-18