线搜索

无约束优化与线搜索方法

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

在人工智能与机器学习的核心算法中，无论是训练神经网络还是拟合模型参数，最终都归结为一个寻找函数最优解的问题。本节我们将正式进入最优化领域，从无约束优化问题的定义出发，理解局部最优与全局最优的区别与联系，并掌握求解这类问题的基本思路—线搜索方法。学完本节，你将能够清晰地描述一个优化问题的构成，并理解梯度下降、牛顿法等经典算法的底层逻辑。

💡 核心导读

本节将围绕以下要点展开，为你构建清晰的知识地图：

1. 问题定义：明确什么是无约束优化问题，理解光滑函数假设的必要性及其局限性。
2. 最优解辨析：区分全局最优点与局部极小值点，认识非凸优化问题的普遍性与挑战。
3. 最优性条件：回顾并运用一阶、二阶必要条件与充分条件来判断候选点是否为极值点。
4. 凸函数的特权：理解凸函数下局部极小即全局最小的优良性质，认识其在优化中的特殊地位。
5. 线搜索框架：掌握线搜索方法的核心迭代公式 $x_{k+1} = x_k + \alpha_k p_k$，理解下降方向判据 $\nabla f(x_k)^T p_k < 0$ 的几何意义，并了解最速下降法、牛顿法与拟牛顿法在选择搜索方向上的本质区别。

无约束优化问题

在数学上，一个无约束优化问题通常表述为：给定一个目标函数 $f(x)$，其中 $x \in \mathbb{R}^n$（或其定义域的子集），我们希望找到一点 $x^$x∗，使得函数值 $f(x^$) 最小。即：

$$\min_{x \in \mathbb{R}^n} f(x)$$

我们的任务是同时找到这个最优解 $x^$x∗ 和对应的最优函数值 $f(x^$)。

为了便于理论分析和算法设计，我们通常对目标函数 $f$ 做出一个较强的假设：$f$ 是一个光滑函数。这意味着至少 $f$ 的一阶导数（梯度）是存在的。在机器学习的大多数场景中，这个假设是合理的，因为许多损失函数（如均方误差、交叉熵）都是可微的。没有一阶导数，像梯度下降、牛顿法等基于导数的经典算法就无法应用。当然，现实世界也存在大量不连续或不可微的函数，针对它们有专门的优化理论（如次梯度法、进化算法），这超出了本节的基础范畴。

全局最优与局部最优

对于一个最优解 $x^*$，我们根据其最优性的范围进行区分：

• 全局最优点：如果对于定义域内所有可行的 $x$，都有 $f(x^$) \le f(x)f(x∗)≤f(x)，则称 $x^$ 为全局最优点（全局最小值点）。
• 局部极小值点：如果存在 $x^$x∗ 的一个邻域，使得在该邻域内所有点 $x$ 都满足 $f(x^$) \le f(x)，则称 $x^*$ 为局部极小值点。

这与数学分析中“最小值点”和“极小值点”的概念完全对应，前者是整体性质，后者是局部性质。

理想情况下，我们总希望找到全局最优解。然而，对于复杂的非凸函数，其函数曲面可能非常曲折，存在大量“局部极小值点”和“鞍点”，而全局最优点可能深藏其中。在机器学习中，即使是简单的手写数字识别任务，其神经网络的损失函数曲面也常呈现这种复杂形态，使得寻找全局最优变得极其困难。

因此，在实践中，我们往往退而求其次，转而寻找局部极小值点。那么，在什么情况下局部极小就是全局最小呢？答案是：当函数是凸函数时。凸函数具有“局部极小即全局最小”的优良性质，这使得凸优化问题在理论上和计算上都更为友好。遗憾的是，现实中的多数问题都是非凸的。

最优性条件

如何判断一个点 $x^$x∗ 是否是局部极小值点呢？我们回顾数学分析中的经典条件。以下假设 $f$ 在 $x^$ 处具有所需的可微性。

1. 一阶必要条件：若 $x^$x∗ 是局部极小值点，且 $f$ 在 $x^$ 处一阶可导，则梯度必须为零向量。 $$\nabla f(x^*) = 0$$ 满足此条件的点称为驻点或临界点。

2. 二阶必要条件：若 $x^$x∗ 是局部极小值点，且 $f$ 在 $x^$ 处二阶连续可导（即 Hessian 矩阵存在且连续），则在一阶条件 $\nabla f(x^$) = 0∇f(x∗)=0 满足的前提下，Hessian 矩阵 $\nabla^2 f(x^$) 必须是半正定的。 $$\nabla^2 f(x^*) \succeq 0$$

3. 二阶充分条件：若 $f$ 在 $x^$x∗ 处二阶连续可导，且满足 $\nabla f(x^$) = 0，同时 Hessian 矩阵 $\nabla^2 f(x^$)∇2f(x∗) 正定，则 $x^$ 是一个严格的局部极小值点。 $$\nabla^2 f(x^*) \succ 0$$

4. 凸函数的特权：

• 若 $f$ 是凸函数，则它的任何一个局部极小值点都是全局最小值点。
• 若 $f$ 是可导的凸函数，则满足 $\nabla f(x^$) = 0∇f(x∗)=0 的驻点 $x^$ 就是全局最小值点。

对于非凸问题，我们通常从寻找驻点（一阶条件）入手，并利用二阶条件判断其是否为局部极小。

线搜索方法框架

由于直接求解 $\nabla f(x) = 0$ 的解析解通常不可行，我们采用迭代算法。线搜索方法是最主流的迭代框架之一，其核心思想是：构造一个序列 ${x_k}$，使其收敛到最优解 $x^*$。每次迭代的更新公式为：

$$x_{k+1} = x_k + \alpha_k p_k$$

其中：

• $p_k$ 是第 $k$ 步的搜索方向。
• $\alpha_k > 0$ 是第 $k$ 步的步长（或学习率）。

算法的有效性完全取决于如何选择 $p_k$ 和 $\alpha_k$。

下降方向

首先，搜索方向 $p_k$ 必须是一个下降方向，以确保函数值有下降的可能。下降方向的数学判据为：

$$\nabla f(x_k)^T p_k < 0$$

这个不等式的几何意义非常深刻。回忆梯度 $\nabla f(x_k)$ 的方向是函数在该点上升最快的方向。两个向量的点积 $\nabla f(x_k)^T p_k = |\nabla f(x_k)| |p_k| \cos \theta$，其中 $\theta$ 是两者的夹角。点积小于零等价于 $\cos \theta < 0$，即夹角 $\theta$ 大于 $90^\circ$。这意味着搜索方向 $p_k$ 与梯度方向的夹角超过 $90^\circ$，大致指向函数值下降的半球区域。

通用形式与经典算法

许多线搜索方法中，搜索方向 $p_k$ 可以表示为如下通用形式：

$$p_k = -B_k^{-1} \nabla f(x_k)$$

其中 $B_k$ 是一个对称正定矩阵。不同的算法体现在 $B_k$ 的不同选择上：

1. 最速下降法：取 $B_k = I$（单位矩阵）。此时 $p_k = -\nabla f(x_k)$，即负梯度方向。这是函数值下降最快的局部方向，故得名。 $$p_k^{\text{SD}} = -\nabla f(x_k)$$

2. 牛顿法：取 $B_k = \nabla^2 f(x_k)$，即当前点的 Hessian 矩阵。此时 $p_k = -[\nabla^2 f(x_k)]^{-1} \nabla f(x_k)$。牛顿法利用了函数的二阶曲率信息，在驻点附近通常具有更快的收敛速度。 $$p_k^{\text{Newton}} = -[\nabla^2 f(x_k)]^{-1} \nabla f(x_k)$$

3. 拟牛顿法：牛顿法需要计算并求逆 Hessian 矩阵，计算成本高。拟牛顿法（如 DFP、BFGS 算法）通过迭代方式构造一个矩阵 $H_k$ 来近似 $[\nabla^2 f(x_k)]^{-1}$，从而避免直接求逆。 $$p_k^{\text{QN}} = -H_k \nabla f(x_k), \quad H_k \approx [\nabla^2 f(x_k)]^{-1}$$

算法框架

一个典型的线搜索算法框架如下：

1. 初始化起点 $x_0$，设置精度要求 $\epsilon$，令 $k=0$。
2. while $|\nabla f(x_k)| > \epsilon$ do
3.     确定下降方向 $p_k$（例如，采用上述某种方法）。
4.     验证下降条件：确保 $\nabla f(x_k)^T p_k < 0$。
5.     确定步长 $\alpha_k$（可通过精确线搜索或 Armijo、Wolfe 等非精确线搜索准则）。
6.     更新迭代点：$x_{k+1} = x_k + \alpha_k p_k$。
7.      $k \leftarrow k + 1$。
8. end while

步长 $\alpha_k$ 的选择同样关键，好的步长能在保证下降的前提下加速收敛。

import numpy as np
import matplotlib.pyplot as plt

# 定义目标函数：Rosenbrock函数，一个经典的非凸优化测试函数
def rosenbrock(x):
    """Rosenbrock函数，f(x,y) = (a-x)^2 + b*(y-x^2)^2, 通常取a=1, b=100"""
    a, b = 1, 100
    return (a - x[0])**2 + b * (x[1] - x[0]**2)**2

# 定义梯度
def rosenbrock_grad(x):
    a, b = 1, 100
    df_dx = -2*(a - x[0]) - 4*b * x[0] * (x[1] - x[0]**2)
    df_dy = 2*b * (x[1] - x[0]**2)
    return np.array([df_dx, df_dy])

# 定义Hessian矩阵
def rosenbrock_hessian(x):
    a, b = 1, 100
    df_dx2 = 2 - 4*b*(x[1] - x[0]**2) + 8*b*x[0]**2
    df_dxdy = -4*b*x[0]
    df_dy2 = 2*b
    return np.array([[df_dx2, df_dxdy], [df_dxdy, df_dy2]])

# 实现最速下降法
def steepest_descent(x0, grad_func, max_iter=10000, lr=0.001, tol=1e-6):
    x = x0.copy()
    path = [x0.copy()]
    for i in range(max_iter):
        g = grad_func(x)
        if np.linalg.norm(g) < tol:
            break
        # 搜索方向：负梯度
        p = -g
        # 固定步长更新
        x = x + lr * p
        path.append(x.copy())
    return np.array(path), i

# 实现牛顿法
def newton_method(x0, grad_func, hess_func, max_iter=100, tol=1e-6):
    x = x0.copy()
    path = [x0.copy()]
    for i in range(max_iter):
        g = grad_func(x)
        if np.linalg.norm(g) < tol:
            break
        H = hess_func(x)
        # 搜索方向：-H^{-1} * g
        p = -np.linalg.solve(H, g) # 解线性方程组，避免直接求逆
        # 固定步长为1（经典牛顿法）
        x = x + p
        path.append(x.copy())
    return np.array(path), i

# 运行两种方法
x0 = np.array([-1.5, 2.0]) # 非平凡的初始点
path_sd, iter_sd = steepest_descent(x0, rosenbrock_grad, lr=0.001, max_iter=20000)
path_nt, iter_nt = newton_method(x0, rosenbrock_grad, rosenbrock_hessian, max_iter=50)

print(f"最速下降法：从 {x0} 出发，经过 {iter_sd} 次迭代，终点 {path_sd[-1].round(4)}")
print(f"牛顿法：从 {x0} 出发，经过 {iter_nt} 次迭代，终点 {path_nt[-1].round(4)}")
print(f"理论全局最优点: [1, 1]")

# 可视化优化路径 (在等高线图上)
x = np.linspace(-2, 2, 400)
y = np.linspace(-1, 3, 400)
X, Y = np.meshgrid(x, y)
Z = rosenbrock([X, Y])

plt.figure(figsize=(12, 5))
plt.subplot(1, 2, 1)
plt.contour(X, Y, Z, levels=np.logspace(-0.5, 3.5, 20), cmap='viridis')
plt.plot(path_sd[:, 0], path_sd[:, 1], 'ro-', markersize=3, linewidth=0.8, label=f'最速下降 ({iter_sd} iter)')
plt.plot(x0[0], x0[1], 'bs', label='起点')
plt.plot(1, 1, 'g*', markersize=15, label='最优点 (1,1)')
plt.xlabel('x')
plt.ylabel('y')
plt.title('最速下降法优化路径')
plt.legend()
plt.axis('equal')

plt.subplot(1, 2, 2)
plt.contour(X, Y, Z, levels=np.logspace(-0.5, 3.5, 20), cmap='viridis')
plt.plot(path_nt[:, 0], path_nt[:, 1], 'mo-', markersize=5, linewidth=1, label=f'牛顿法 ({iter_nt} iter)')
plt.plot(x0[0], x0[1], 'bs', label='起点')
plt.plot(1, 1, 'g*', markersize=15, label='最优点 (1,1)')
plt.xlabel('x')
plt.ylabel('y')
plt.title('牛顿法优化路径')
plt.legend()
plt.axis('equal')
plt.tight_layout()
plt.show()

📝 动手练一练

1. 下降方向判断：设函数 $f(x, y) = x^2 + 3y^2$ 在点 $(1, 1)$ 处。 a) 计算该点的梯度 $\nabla f(1, 1)$。 b) 判断向量 $\mathbf{p}_1 = (-1, -1)$ 和 $\mathbf{p}_2 = (1, -2)$ 是否为该点处的下降方向？请用下降方向判据说明。

2. 驻点与极值点分析：考虑单变量函数 $f(x) = x^3 - 3x$。 a) 求其所有驻点（即满足 $f’(x)=0$ 的点）。 b) 利用二阶导数判断这些驻点是局部极小点、局部极大点还是鞍点。 c) 这个函数是凸函数吗？它的局部极小点是全局最小点吗？

参考答案：

1. a) 梯度 $\nabla f = (2x, 6y)$，故 $\nabla f(1,1) = (2, 6)$。 b) 对于 $\mathbf{p}_1 = (-1, -1)$：$\nabla f \cdot \mathbf{p}_1 = (2,6)\cdot(-1,-1) = -2-6 = -8 < 0$，是下降方向。 对于 $\mathbf{p}_2 = (1, -2)$：$\nabla f \cdot \mathbf{p}_2 = (2,6)\cdot(1,-2) = 2-12 = -10 < 0$，是下降方向。

2. a) $f’(x) = 3x^2 - 3$，令 $f’(x)=0$ 得 $x^2=1$，故驻点为 $x = 1$ 和 $x = -1$。 b) $f”(x) = 6x$。在 $x=1$ 处，$f”(1)=6>0$，故 $x=1$ 是局部极小点。在 $x=-1$ 处，$f”(-1)=-6<0$，故 $x=-1$ 是局部极大点。 c) 二阶导数 $f”(x)=6x$ 在定义域 $\mathbb{R}$ 上不恒大于等于零（例如当 $x<0$ 时），因此 $f(x)$ 不是凸函数。其局部极小点 $x=1$ 对应的函数值 $f(1)=-2$，但当 $x \to -\infty$ 时，$f(x) \to -\infty$，存在更小的函数值，所以该局部极小点不是全局最小点。

本章小结

本节我们建立了最优化问题的基本认知框架：

• 问题核心：无约束优化旨在最小化一个光滑函数 $f(x)$。
• 现实困境：非凸问题的全局最优解难以获取，实践中多寻求局部极小解。
• 判断依据：利用一阶必要条件（梯度为零）找驻点，结合二阶条件（Hessian 正定）判断是否为局部极小。
• 理想情形：对于凸函数，局部极小即全局最小，优化问题大大简化。
• 求解框架：线搜索方法通过迭代公式 $x_{k+1} = x_k + \alpha_k p_k$ 逼近解，其核心是选择下降方向 ($\nabla f^T p_k < 0$) 与合适步长。最速下降法、牛顿法等经典算法的区别本质在于搜索方向 $p_k$ 的构造方式不同。

行动清单 学完本节，你可以立即：

1. 辨析概念：面对一个优化问题，能清晰区分其目标是寻找全局最优还是局部最优，并判断目标函数的凸性是否能为求解带来便利。
2. 应用条件：给定一个候选点，能够运用一阶和二阶最优性条件，判断其是否为局部极值点。
3. 理解算法：阅读梯度下降等优化算法的代码时，能识别出其对应的线搜索框架，并理解其中方向与步长更新的数学原理。

— 小象教研组