wolfe简约梯度法python

Wolfe 算法是一种非常常用的优化算法，用于求解无约束优化问题。 它的基本思想是在一维搜索中同时满足 Armijo 规则和曲率条件，以保证搜索方向的正确性和搜索步长的合适性。简约梯度法是 Wolfe 算法的一种变形，它使用了类似于 L-BFGS 的方法来近似计算 Hessian 矩阵的逆，从而提高了算法的收敛速度。

下面是使用 Python 实现 Wolfe 简约梯度法的示例代码：

import numpy as np

def wolfe_simple_gradient(f, grad, x0, max_iter=1000, tol=1e-6, c1=1e-4, c2=0.9, m=20):
    """
    Wolfe 简约梯度法
    :param f: 目标函数
    :param grad: 目标函数的梯度
    :param x0: 初始点
    :param max_iter: 最大迭代次数
    :param tol: 收敛精度
    :param c1: Armijo 条件参数
    :param c2: 曲率条件参数
    :param m: L-BFGS 中用于近似计算 Hessian 矩阵逆的历史梯度数目
    :return: 最优解 x_star, 最优解对应的函数值 f_star, 迭代次数 iter_num
    """
    x = x0
    iter_num = 0
    s_list = []
    y_list = []
    alpha_list = []
    f_val_list = []
    g_val_list = []
    while iter_num < max_iter:
        # 计算梯度
        g = grad(x)

        # 计算步长
        if iter_num == 0:
            alpha = 1.0
        else:
            alpha = line_search_wolfe2(f, grad, x, -g, alpha_list[-1], c1, c2)

        # 更新 x
        x_new = x - alpha * g

        # 更新历史梯度
        if iter_num > 0:
            s = x_new - x
            y = grad(x_new) - g
            s_list.append(s)
            y_list.append(y)
            if len(s_list) > m:
                s_list.pop(0)
                y_list.pop(0)

        # 更新 x 和迭代计数器
        x = x_new
        iter_num += 1

        # 计算目标函数和梯度的值，并记录历史值
        f_val = f(x)
        g_val = np.linalg.norm(grad(x))
        f_val_list.append(f_val)
        g_val_list.append(g_val)
        alpha_list.append(alpha)

        # 判断是否收敛
        if g_val < tol:
            break

    # 返回结果
    x_star = x
    f_star = f_val_list[-1]
    return x_star, f_star, iter_num

def line_search_wolfe2(f, grad, x, d, alpha0, c1, c2, max_iter=100):
    """
    Wolfe 算法的线搜索算法
    :param f: 目标函数
    :param grad: 目标函数的梯度
    :param x: 当前点
    :param d: 搜索方向
    :param alpha0: 初始步长
    :param c1: Armijo 条件参数
    :param c2: 曲率条件参数
    :param max_iter: 最大迭代次数
    :return: 步长 alpha
    """
    alpha = alpha0
    phi0 = f(x)
    phi0_grad = grad(x).dot(d)
    phi = f(x + alpha * d)
    iter_num = 0
    while iter_num < max_iter and \
            (phi > phi0 + c1 * alpha * phi0_grad or
             (phi_grad(x + alpha * d).dot(d) < c2 * phi0_grad)):
        alpha = alpha / 2.0
        phi = f(x + alpha * d)
        iter_num += 1
    return alpha

这里的 `f` 和 `grad` 分别代表目标函数和目标函数的梯度，`x0` 是初始点，`max_iter` 是最大迭代次数，`tol` 是收敛精度，`c1` 和 `c2` 分别是 Armijo 条件和曲率条件的参数，`m` 是 L-BFGS 中用于近似计算 Hessian 矩阵逆的历史梯度数目。函数的返回值包括最优解 `x_star`、最优解对应的函数值 `f_star` 和迭代次数 `iter_num`。