BFGS算法（Broyden-Fletcher-Goldfarb-Shanno算法）

BFGS算法（Broyden-Fletcher-Goldfarb-Shanno算法）是一种用于求解无约束优化问题的迭代算法，它是牛顿法的一种拟牛顿法。它通过逐步建立一个目标函数的近似Hessian矩阵的逆来迭代求解目标函数的极小值点。

BFGS算法的基本思想是在每次迭代中，通过计算目标函数的梯度和Hessian矩阵的逆来确定搜索方向，然后利用线性搜索确定步长，最终求得当前点的下一步更新位置。

BFGS算法的代码实现如下：

import numpy as np

def BFGS(f, df, x0, max_iter=1000, tol=1e-6):
    # 初始点和矩阵
    x = x0
    H = np.eye(len(x0))

    for i in range(max_iter):
        # 计算梯度和函数值
        grad = df(x)
        fx = f(x)

        # 判断是否达到收敛
        if np.linalg.norm(grad) < tol:
            break

        # 计算搜索方向
        p = -np.dot(H, grad)

        # 一维搜索得到步长alpha
        alpha = backtracking(f, df, x, p)

        # 更新x
        x_new = x + alpha * p

        # 计算梯度差和x差
        s = x_new - x
        y = df(x_new) - grad

        # 更新H
        H = H + np.dot(y, y.T) / np.dot(y.T, s) - np.dot(np.dot(H, s), np.dot(H, s).T) / np.dot(s.T, np.dot(H, s))

        # 更新x
        x = x_new

    return x

def backtracking(f, df, x, p, alpha=1, rho=0.5, c=1e-4):
    # 初始步长和函数值
    fx = f(x)
    fp = f(x + alpha * p)

    # 迭代直到满足Armijo准则
    while fp > fx + c * alpha * np.dot(df(x).T, p):
        alpha = rho * alpha
        fp = f(x + alpha * p)

    return alpha

 其中，f是目标函数，x0是初始点，tol是容差，maxiter是最大迭代次数。line_search函数是用来进行线性搜索的。在每次迭代中，首先计算梯度和搜索方向，然后进行线性搜索，确定步长。接着计算新的点和目标函数的值，重新计算梯度，并更新近似Hessian矩阵的逆。最终返回最优解。

 下面是一个简单的例子，使用BFGS算法求解f(x,y)=x^2+y^2的最小值点：

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

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

x0 = np.array([1, 1])
x = BFGS(f, df, x0)

print(x)  # 输出 [0. 0.]

 BFGS算法是一种数值优化算法，用于求解非线性最优化问题。它属于拟牛顿法的一种，通过不断地迭代来寻找函数的极小值点。