最速下降法和牛顿法

最速下降法与牛顿法

小象实战讲义 · 人工智能数学基础

在求解无约束优化问题的道路上，我们已掌握了线搜索的基本框架。本节将介绍两种经典的线搜索算法：最速下降法与牛顿法。最速下降法以其思想朴素、实现简单而闻名，是理解优化算法的基础；牛顿法则通过引入二阶信息，展现出更快的收敛速度。学习本节，你将能理解这两种算法的原理、实现步骤，并能在实际中根据问题特性选择合适的算法。

💡 核心导读

• 最速下降法：以当前点的负梯度方向作为搜索方向，结合线搜索确定步长，是优化算法中最基础的思想。
• 算法优劣：最速下降法理论收敛，但实际中常因“锯齿”现象而收敛缓慢，且对函数尺度敏感。
• 牛顿法推导：通过目标函数的二阶泰勒展开近似，直接求解近似函数的最小值点，得到包含海塞矩阵逆的迭代公式。
• 牛顿法特性：具有局部收敛性和二阶收敛速度，但要求初始点接近最优解，且海塞矩阵需正定。
• 海塞矩阵修正：当海塞矩阵不正定时，可通过添加一个正定矩阵（如单位矩阵的倍数）进行修正，使其满足算法要求。

最速下降法：朴素而基础的起点

最速下降法的核心思想非常直观：在每一步迭代中，都沿着当前点函数值下降最快的方向前进。这个方向正是该点梯度的反方向，即负梯度方向。

给定一个可微的目标函数 $f(x)$，在点 $x_k$ 处，其搜索方向 $d_k$ 定义为： $$d_k = -\nabla f(x_k)$$ 因此，最速下降法的迭代公式为： $$x_{k+1} = x_k + \alpha_k d_k = x_k - \alpha_k \nabla f(x_k)$$ 其中，$\alpha_k > 0$ 是步长。

步长 $\alpha_k$ 的选择至关重要，它决定了每次迭代前进的幅度。我们可以采用之前学过的线搜索方法：

1. 精确线搜索：$\alpha_k = \arg\min_{\alpha > 0} f(x_k + \alpha d_k)$。
2. 非精确线搜索：使用 Wolfe 条件、Goldstein 条件或回溯法（Backtracking）来确定一个可接受的步长。

算法框架

基于以上讨论，最速下降法的算法框架如下：

1. 初始化：给定初始点 $x_0$，收敛精度 $\epsilon > 0$，令 $k = 0$。
2. 计算梯度：计算当前点的梯度 $g_k = \nabla f(x_k)$。
3. 收敛判断：若 $|g_k| \le \epsilon$，则停止迭代，输出 $x_k$ 作为近似极小值点。此判断依据是优化问题的一阶必要条件：在局部极小值点处，梯度应为零向量。
4. 确定搜索方向：令搜索方向 $d_k = -g_k$。
5. 线搜索：使用精确或非精确线搜索方法，确定步长 $\alpha_k$。
6. 更新迭代点：$x_{k+1} = x_k + \alpha_k d_k$。
7. 循环：令 $k = k+1$，返回步骤 2。

最速下降法的特性分析

最速下降法虽然基础，但其优缺点非常鲜明。

优点：

1. 理论收敛性：在适当的线搜索条件下（如 Wolfe 条件），算法可以收敛到一个局部极小值点。
2. 基础参考：许多更复杂的优化算法，在迭代后期或某些情况下，会退化为类似最速下降法的行为。

缺点：

1. 非尺度不变：对目标函数进行线性变换（缩放）后，算法的性能会发生显著变化，需要重新调整参数。
2. 收敛速度慢：这是最致命的缺点。最速下降法在等高线为椭圆的函数上，其搜索路径会呈现“之”字形（锯齿状）前进。即使步长收敛到 0，函数值也可能还未收敛到真正的极小点。这种收敛速度是线性的，且常数项可能很糟糕。
3. 实际可能不收敛：对于某些病态函数，如果步长控制不当，算法可能发散。

下面的代码演示了最速下降法在二维二次函数上的“锯齿”现象。

import numpy as np
import matplotlib.pyplot as plt

def steepest_descent(f, grad_f, x0, alpha=0.1, max_iter=100, tol=1e-6):
    """
    最速下降法实现
    f: 目标函数
    grad_f: 梯度函数
    x0: 初始点
    alpha: 固定步长 (这里为演示简单使用固定步长)
    max_iter: 最大迭代次数
    tol: 梯度范数容忍度
    """
    x = np.array(x0, dtype=float)
    path = [x.copy()]
    for i in range(max_iter):
        g = grad_f(x)
        if np.linalg.norm(g) < tol:
            break
        x = x - alpha * g  # 沿负梯度方向更新
        path.append(x.copy())
    return np.array(path)

# 定义一个条件数较大的二次函数: f(x) = 0.5 * (x1^2 + 10*x2^2)
# 其海塞矩阵为 diag(1, 10)，条件数为10。
def f_quad(x):
    return 0.5 * (x[0]**2 + 10 * x[1]**2)

def grad_f_quad(x):
    return np.array([x[0], 10 * x[1]])

# 运行最速下降法
x0 = [10.0, 1.0]
path = steepest_descent(f_quad, grad_f_quad, x0, alpha=0.1, max_iter=50)

# 绘制等高线和优化路径
x1 = np.linspace(-11, 11, 400)
x2 = np.linspace(-2, 2, 400)
X1, X2 = np.meshgrid(x1, x2)
Z = 0.5 * (X1**2 + 10 * X2**2)

plt.figure(figsize=(10, 6))
plt.contour(X1, X2, Z, levels=30, cmap='viridis')
plt.plot(path[:, 0], path[:, 1], 'ro-', linewidth=1.5, markersize=4, label='最速下降法路径')
plt.scatter(path[0, 0], path[0, 1], c='blue', s=100, marker='s', label='起始点')
plt.scatter(path[-1, 0], path[-1, 1], c='green', s=100, marker='*', label='终止点')
plt.xlabel('<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msub><mi>x</mi><mn>1</mn></msub></mrow><annotation encoding="application/x-tex">x_1</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="katex-base"><span class="katex-strut" style="height:0.5806em;vertical-align:-0.15em;"></span><span class="mord"><span class="mord mathnormal">x</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.3011em;"><span style="top:-2.55em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="katex-sizing reset-size6 size3 mtight"><span class="mord mtight">1</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span></span></span></span>')
plt.ylabel('<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msub><mi>x</mi><mn>2</mn></msub></mrow><annotation encoding="application/x-tex">x_2</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="katex-base"><span class="katex-strut" style="height:0.5806em;vertical-align:-0.15em;"></span><span class="mord"><span class="mord mathnormal">x</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.3011em;"><span style="top:-2.55em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="katex-sizing reset-size6 size3 mtight"><span class="mord mtight">2</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span></span></span></span>')
plt.title('最速下降法在椭圆等高线函数上的“之”字形路径')
plt.legend()
plt.grid(True, alpha=0.3)
plt.axis('equal')
plt.show()

牛顿法：引入二阶信息的飞跃

为了克服最速下降法收敛慢的问题，牛顿法引入了目标函数的二阶导数（海塞矩阵）信息。其基本思想是：在当前迭代点 $x_k$ 处，用目标函数的二阶泰勒展开式来近似原函数，然后直接求解这个二次近似函数的最小值点，并将其作为下一个迭代点。

考虑 $f(x)$ 在 $x_k$ 处的二阶泰勒展开： $$f(x) \approx f(x_k) + \nabla f(x_k)^T (x - x_k) + \frac{1}{2} (x - x_k)^T \nabla^2 f(x_k) (x - x_k)$$ 其中 $\nabla^2 f(x_k)$ 是 $f$ 在 $x_k$ 处的海塞矩阵（Hessian Matrix），记为 $H_k$。

我们的目标是找到 $x$ 使得这个二次近似函数 $q(x)$ 最小化。根据无约束优化的一阶必要条件，$q(x)$ 的极小值点应满足其梯度为零： $$\nabla q(x) = \nabla f(x_k) + H_k (x - x_k) = 0$$ 假设 $H_k$ 可逆，解这个线性方程得到： $$x - x_k = -H_k^{-1} \nabla f(x_k)$$ 于是，我们得到了牛顿法的迭代公式： $$x_{k+1} = x_k - H_k^{-1} \nabla f(x_k)$$

在牛顿法中，搜索方向 $d_k$ 为： $$d_k = -H_k^{-1} \nabla f(x_k)$$ 步长 $\alpha_k$ 通常取为 1（即“纯”牛顿步），但为了全局收敛性，我们同样可以引入线搜索，使用非精确线搜索（Wolfe条件、回溯法等）来确定步长 $\alpha_k$。此时迭代公式变为： $$x_{k+1} = x_k + \alpha_k d_k = x_k - \alpha_k H_k^{-1} \nabla f(x_k)$$

算法框架与关键问题

带线搜索的牛顿法算法框架如下：

1. 初始化：给定初始点 $x_0$，收敛精度 $\epsilon > 0$，令 $k = 0$。
2. 计算梯度与海塞矩阵：计算 $g_k = \nabla f(x_k)$ 和 $H_k = \nabla^2 f(x_k)$。
3. 收敛判断：若 $|g_k| \le \epsilon$，则停止迭代。
4. 求解线性系统：求解 $H_k d_k = -g_k$，得到搜索方向 $d_k$。（实践中通常求解线性系统，而非显式计算逆矩阵）。
5. 线搜索：使用非精确线搜索确定步长 $\alpha_k$。
6. 更新迭代点：$x_{k+1} = x_k + \alpha_k d_k$。
7. 循环：令 $k = k+1$，返回步骤 2。

牛顿法在理论上非常优美，但在实际应用中需要注意几个关键问题：

1. 海塞矩阵的可逆性与正定性：迭代公式要求 $H_k$ 可逆。更重要的是，为了确保 $d_k$ 是下降方向（即 $g_k^T d_k < 0$），需要 $H_k$ 正定。因为 $g_k^T d_k = -g_k^T H_k^{-1} g_k$，当 $H_k$ 正定时，其逆也正定，该式小于零。
2. 局部收敛性：牛顿法具有局部收敛性。即，只有当初始点 $x_0$ 距离局部极小值点 $x^$x∗ 足够近时，算法才能收敛到 $x^$。如果初始点选择不当，算法可能发散。
3. 收敛速度：在满足一定条件下（如 $f$ 二阶连续可微，$x^$x∗ 处海塞矩阵正定，初始点足够接近 $x^$），牛顿法具有二阶收敛速度。这意味着其误差的衰减速度远快于最速下降法的线性收敛，是它最大的优势。

下面的代码对比了最速下降法和牛顿法在同一个问题上的表现。

import numpy as np
import matplotlib.pyplot as plt

def newton_method(f, grad_f, hess_f, x0, alpha_method='backtracking', max_iter=100, tol=1e-6):
    """
    带线搜索的牛顿法实现
    alpha_method: 步长选择方法，这里实现简单的回溯法
    """
    def backtracking_line_search(x, d):
        alpha = 1.0
        rho = 0.5
        c = 1e-4
        while f(x + alpha * d) > f(x) + c * alpha * grad_f(x).dot(d):
            alpha *= rho
        return alpha

    x = np.array(x0, dtype=float)
    path = [x.copy()]
    for i in range(max_iter):
        g = grad_f(x)
        H = hess_f(x)
        if np.linalg.norm(g) < tol:
            break
        # 求解线性系统 H * d = -g
        try:
            # 使用Cholesky分解求解（要求H正定）
            L = np.linalg.cholesky(H)
            y = np.linalg.solve(L, -g)
            d = np.linalg.solve(L.T, y)
        except np.linalg.LinAlgError:
            # 如果Cholesky分解失败（不正定），使用普通求解（可能不是下降方向）
            print(f"迭代 {i}: 海塞矩阵不正定，使用普通求解。")
            d = np.linalg.solve(H, -g)

        if alpha_method == 'backtracking':
            alpha = backtracking_line_search(x, d)
        else:
            alpha = 1.0  # 纯牛顿步

        x = x + alpha * d
        path.append(x.copy())
    return np.array(path)

# 使用同一个二次函数
def hess_f_quad(x):
    return np.array([[1, 0], [0, 10]])

# 运行两种算法
x0 = [10.0, 1.0]
path_sd = steepest_descent(f_quad, grad_f_quad, x0, alpha=0.1, max_iter=50)
path_nt = newton_method(f_quad, grad_f_quad, hess_f_quad, x0, max_iter=50)

# 绘制对比图
plt.figure(figsize=(12, 5))

plt.subplot(1, 2, 1)
plt.contour(X1, X2, Z, levels=30, cmap='viridis')
plt.plot(path_sd[:, 0], path_sd[:, 1], 'ro-', linewidth=1.5, markersize=4, label='最速下降法')
plt.scatter(path_sd[0, 0], path_sd[0, 1], c='blue', s=100, marker='s')
plt.scatter(path_sd[-1, 0], path_sd[-1, 1], c='green', s=100, marker='*')
plt.title('最速下降法路径')
plt.xlabel('<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msub><mi>x</mi><mn>1</mn></msub></mrow><annotation encoding="application/x-tex">x_1</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="katex-base"><span class="katex-strut" style="height:0.5806em;vertical-align:-0.15em;"></span><span class="mord"><span class="mord mathnormal">x</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.3011em;"><span style="top:-2.55em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="katex-sizing reset-size6 size3 mtight"><span class="mord mtight">1</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span></span></span></span>')
plt.ylabel('<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msub><mi>x</mi><mn>2</mn></msub></mrow><annotation encoding="application/x-tex">x_2</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="katex-base"><span class="katex-strut" style="height:0.5806em;vertical-align:-0.15em;"></span><span class="mord"><span class="mord mathnormal">x</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.3011em;"><span style="top:-2.55em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="katex-sizing reset-size6 size3 mtight"><span class="mord mtight">2</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span></span></span></span>')
plt.legend()
plt.grid(True, alpha=0.3)
plt.axis('equal')

plt.subplot(1, 2, 2)
plt.contour(X1, X2, Z, levels=30, cmap='viridis')
plt.plot(path_nt[:, 0], path_nt[:, 1], 'mo-', linewidth=1.5, markersize=4, label='牛顿法')
plt.scatter(path_nt[0, 0], path_nt[0, 1], c='blue', s=100, marker='s')
plt.scatter(path_nt[-1, 0], path_nt[-1, 1], c='green', s=100, marker='*')
plt.title('牛顿法路径')
plt.xlabel('<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msub><mi>x</mi><mn>1</mn></msub></mrow><annotation encoding="application/x-tex">x_1</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="katex-base"><span class="katex-strut" style="height:0.5806em;vertical-align:-0.15em;"></span><span class="mord"><span class="mord mathnormal">x</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.3011em;"><span style="top:-2.55em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="katex-sizing reset-size6 size3 mtight"><span class="mord mtight">1</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span></span></span></span>')
plt.ylabel('<span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><msub><mi>x</mi><mn>2</mn></msub></mrow><annotation encoding="application/x-tex">x_2</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="katex-base"><span class="katex-strut" style="height:0.5806em;vertical-align:-0.15em;"></span><span class="mord"><span class="mord mathnormal">x</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.3011em;"><span style="top:-2.55em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="katex-sizing reset-size6 size3 mtight"><span class="mord mtight">2</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span></span></span></span>')
plt.legend()
plt.grid(True, alpha=0.3)
plt.axis('equal')

plt.tight_layout()
plt.show()

print(f"最速下降法最终点: {path_sd[-1]}, 最终函数值: {f_quad(path_sd[-1]):.6f}")
print(f"牛顿法最终点: {path_nt[-1]}, 最终函数值: {f_quad(path_nt[-1]):.6f}")

海塞矩阵的修正

牛顿法要求海塞矩阵 $H_k$ 正定，以确保搜索方向是下降方向且算法稳定。然而，对于非凸函数，$H_k$ 可能不定甚至负定。此时，直接求解 $H_k d_k = -g_k$ 得到的 $d_k$ 可能不是下降方向，导致算法失败。

一个常见的解决方案是修正海塞矩阵，将其变为一个正定矩阵。基本思想是： $$\tilde{H}_k = H_k + E_k$$ 其中 $E_k$ 是一个修正项，使得 $\tilde{H}_k$ 正定。最常用且简单的方法是添加一个单位矩阵的倍数： $$\tilde{H}_k = H_k + \tau_k I$$ 其中 $\tau_k > 0$，$I$ 是单位矩阵。

数学原理：对于一个对称矩阵 $H$，只要 $\tau$ 足够大，使得 $\tau$ 大于 $H$ 的负特征值的模的最大值，那么 $H + \tau I$ 的所有特征值都为正，从而成为正定矩阵。

修正算法：Cholesky 分解试探法

一种实用的修正策略是通过尝试 Cholesky 分解来确定 $\tau_k$。Cholesky 分解要求矩阵对称正定，分解失败则说明矩阵不正定。

算法步骤如下：

1. 给定初始试探值 $\tau_0$。一个简单的设置是：如果 $H$ 的对角线元素 $h_{ii}$ 不全为正，则令 $\tau_0 = \beta - \min_i h_{ii}$，其中 $\beta > 0$ 是一个小常数（如 0.001）；否则令 $\tau_0 = 0$。
2. 对于 $k = 0, 1, 2, …$： a. 尝试对 $B_k = H + \tau_k I$ 进行 Cholesky 分解：$B_k = L_k L_k^T$。 b. 如果分解成功，则返回修正后的矩阵 $B_k$ 及其 Cholesky 因子 $L_k$。 c. 如果分解失败，则增大修正量：$\tau_{k+1} = \max(2\tau_k, \beta)$，然后重复步骤 a。
3. 为了防止 $\tau$ 无限制增大，可以设置一个上限。

下面的代码演示了海塞矩阵修正的过程。

import numpy as np

def modify_hessian_with_cholesky(H, beta=1e-3, max_iter=20):
    """
    使用Cholesky分解试探法修正海塞矩阵，使其正定。
    H: 待修正的对称矩阵
    beta: 一个小的正数
    max_iter: 最大试探次数
    返回: (修正后的正定矩阵B, Cholesky下三角因子L, 使用的tau)
    """
    n = H.shape[0]
    # 检查对角线元素，确定初始tau
    min_diag = np.min(np.diag(H))
    if min_diag > 0:
        tau = 0.0
    else:
        tau = beta - min_diag

    for i in range(max_iter):
        B = H + tau * np.eye(n)
        try:
            L = np.linalg.cholesky(B)
            # print(f"成功！tau = {tau:.6f}")
            return B, L, tau
        except np.linalg.LinAlgError:
            tau = max(2 * tau, beta)  # 增大tau
            # print(f"Cholesky分解失败，增大tau至 {tau:.6f}")
    # 如果达到最大迭代仍未成功，返回最后一次尝试的矩阵（可能仍不正定）
    print("警告：达到最大修正迭代次数，返回的矩阵可能仍不正定。")
    return H + tau * np.eye(n), None, tau

# 测试修正算法
# 创建一个非正定的对称矩阵
H_indefinite = np.array([[4, 2],
                         [2, -1]])  # 特征值约为 4.56 和 -1.56，不正定
print("原始海塞矩阵 H:")
print(H_indefinite)
print("H 的特征值:", np.linalg.eigvals(H_indefinite))

B, L, tau_used = modify_hessian_with_cholesky(H_indefinite, beta=0.001)
print(f"\n使用的修正量 tau = {tau_used:.6f}")
print("修正后的矩阵 B = H + tau*I:")
print(B)
print("B 的特征值:", np.linalg.eigvals(B))
if L is not None:
    print("Cholesky 分解因子 L:")
    print(L)
    print("验证 L * L^T:")
    print(L @ L.T)

📝 动手练一练

1. 最速下降法步长实验：对于函数 $f(x) = x_1^2 + 5x_2^2$，从点 $(2, 2)$ 出发，分别使用固定步长 $\alpha = 0.1$ 和 $\alpha = 0.2$ 运行最速下降法（迭代20步）。观察并解释两种步长下收敛路径和速度的差异。固定步长过大或过小会导致什么问题？

2. 牛顿法修正实践：考虑函数 $f(x) = x_1^4 + x_2^2$ 在点 $(1, 1)$ 处。 a) 计算该点的梯度 $\nabla f$ 和海塞矩阵 $H$。 b) 判断 $H$ 是否正定。 c) 使用上面提供的 modify_hessian_with_cholesky 函数对 $H$ 进行修正，并验证修正后的矩阵是正定的。

参考答案：

1. 固定步长 $\alpha$ 的选择至关重要。步长过小（如 0.01）会导致收敛极其缓慢，需要很多次迭代才能接近最优点。步长过大（如 0.5）可能导致迭代点在最优解两侧震荡，甚至发散（函数值不降反升）。对于本例的二次函数，存在一个最优固定步长（与海塞矩阵的特征值有关），但最速下降法通常使用线搜索来自适应确定步长。

2. a) 梯度 $\nabla f = [4x_1^3, 2x_2]^T$，在 $(1,1)$ 处为 $[4, 2]^T$。海塞矩阵 $H = \begin{bmatrix} 12x_1^2 & 0 \ 0 & 2 \end{bmatrix}$，在 $(1,1)$ 处为 $\begin{bmatrix} 12 & 0 \ 0 & 2 \end{bmatrix}$。 b) 该海塞矩阵是对角矩阵，对角线元素 12 和 2 均大于 0，因此是正定矩阵，无需修正。 c) 如果尝试对一个负定矩阵（如 H_test = np.array([[-2, 1], [1, -2]])）进行修正，上述函数会找到一个合适的 $\tau$（如 2.001）使其正定。

本章小结

本节深入探讨了两种基础而重要的无约束优化算法：最速下降法与牛顿法。

• 最速下降法以负梯度方向为搜索方向，思想朴素，实现简单，是理解优化迭代思想的起点。但其收敛速度慢（线性收敛）、易产生“锯齿”现象，且对函数尺度敏感，在实际复杂问题中较少单独使用。
• 牛顿法通过利用目标函数的二阶信息（海塞矩阵），构造当前点的二次模型并求其极小点，实现了迭代方向的“智能化”。它具有局部收敛性和二阶收敛速度，远快于最速下降法。然而，牛顿法要求海塞矩阵正定（以保证下降方向），且初始点需接近最优解（局部收敛性）。当海塞矩阵不正定时，需要通过添加修正项（如 $\tau I$）使其正定。

学完本节，你可以立刻行动：

1. 代码复现：在 Python 中分别实现最速下降法和带线搜索的牛顿法，并用一个简单的二次函数（如 $f(x) = x^T A x$，$A$ 正定）测试，直观感受两者收敛路径和速度的差异。
2. 问题诊断：当你使用某个优化库遇到收敛问题时，可以初步判断：如果迭代路径呈“之”字形缓慢前进，可能是算法陷入最速下降模式；如果算法在初始几步就发散，可能是初始点离解太远或海塞矩阵不正定导致的方向错误。
3. 算法选择：面对一个新优化问题时，可以优先尝试牛顿法或拟牛顿法（下节内容）。如果问题规模很大，海塞矩阵计算或存储成本过高，则梯度类方法（如最速下降法的改进版本）仍是备选。

— 小象教研组