python实现牛顿法求解求解最小值（包括拟牛顿法）【最优化课程笔记】

牛顿法是一种高效的数值优化算法，可以用于求解实值函数的最小值或最大值。下面是使用Python实现牛顿法求解最小值的步骤：

1. 定义需要求解的目标函数f(x)及其一阶和二阶导数f'(x)和f''(x)。

2. 选择一个初始点x0作为起点。

3. 计算f'(x0)和f''(x0)。

4. 计算x1 = x0 - f'(x0)/f''(x0)。

5. 判断是否满足收敛条件，如果满足则停止迭代，否则返回第3步，计算f'(x1)和f''(x1)。

6. 重复第4步到第5步，直到满足收敛条件为止。

下面是使用Python实现牛顿法的代码：

import numpy as np

def newton_optimize(f, df, ddf, x0, eps=1e-6, max_iter=100):
    """
    使用牛顿法求解函数的最小值
    :param f: 目标函数
    :param df: f的一阶导数
    :param ddf: f的二阶导数
    :param x0: 初始点
    :param eps: 精度
    :param max_iter: 最大迭代次数
    :return: 最小值
    """
    x = x0
    for i in range(max_iter):
        g = df(x)
        h = ddf(x)
        if abs(g) < eps:
            break
        x = x - g / h
    return x

# example
f = lambda x: x**2 + np.sin(x)
df = lambda x: 2 * x + np.cos(x)
ddf = lambda x: 2 - np.sin(x)
x0 = 1.0
x = newton_optimize(f, df, ddf, x0)
print("最小值为:", x)

拟牛顿法是一种牛顿法的变种，它通过估计Hessian矩阵的逆来避免计算和存储Hessian矩阵，从而减少了计算量和内存开销。下面是使用Python实现拟牛顿法的代码：

def bfgs_optimize(f, df, x0, eps=1e-6, max_iter=100):
    """
    使用BFGS算法求解函数的最小值
    :param f: 目标函数
    :param df: f的一阶导数
    :param x0: 初始点
    :param eps: 精度
    :param max_iter: 最大迭代次数
    :return: 最小值
    """
    n = len(x0)
    H = np.eye(n)
    x = x0
    for i in range(max_iter):
        g = df(x)
        if np.linalg.norm(g) < eps:
            break
        p = -np.dot(H, g)
        alpha = line_search(f, df, x, p)
        s = alpha * p
        x_next = x + s
        y = df(x_next) - g
        if np.dot(y.T, s) > 0:
            H = np.dot((np.eye(n) - np.dot(s, y.T) / np.dot(y.T, s)), np.dot(H, (np.eye(n) - np.dot(y, s.T) / np.dot(y.T, s)))) + np.dot(s, s.T) / np.dot(y.T, s)
        x = x_next
    return x

# example
f = lambda x: x[0]**2 + x[1]**2 + np.sin(x[0]) + np.sin(x[1])
df = lambda x: np.array([2 * x[0] + np.cos(x[0]), 2 * x[1] + np.cos(x[1])])
x0 = np.array([1.0, 1.0])
x = bfgs_optimize(f, df, x0)
print("最小值为:", x)

上面的代码使用BFGS算法求解函数的最小值，其中line_search函数是用来计算步长的函数，这里就不再赘述了。