跳转至

Sample Average Approximation (SAA)⚓︎

约 3460 个字 预计阅读时间 12 分钟 总阅读量 次

样本均值近似（Sample Average Approximation, SAA） 是一种基于蒙特卡洛模拟的数值方法，旨在==通过利用已知分布的随机变量==进行采样并构建成本函数，将包含期望值函数的随机优化问题（Stochastic Optimization Problems） 转化成一个确定性的近似问题进行求解。

在运筹学领域，它被广泛应用于处理那些因包含随机变量而难以直接求解的随机规划（Stochastic Programming）模型，特别是两阶段随机规划问题 (Two stage Stochastic Programming)。

问题⚓︎

SAA方法主要适用于以下情况的随机优化问题：

\[\min_{x \in X} \left\{ g(x) = f(x) + \mathbb{E}_{\xi}[Q(x, \xi)] \right\} ]\]

其中： * \(x\) 是第一阶段决策变量，必须在随机事件发生前确定。\(X\)是 \(x\)的可行域。 * \(f(x)\) 是与==第一阶段决策相关的确定性成本==。 * \(\xi\) 是一个代表不确定性的随机向量，其概率分布已知但实现值未知。 * \(Q(x, \xi)\) 是第二阶段成本函数，表示在第一阶段决策 \(x\)已定且随机变量实现为 \(\xi\) 的情况下，为满足约束而采取的最优追索行动（recourse actions）所产生的成本。 * \(\mathbb{E}_{\xi}[\cdot]\) 表示对随机向量 \(\xi\) 的所有可能实现取数学期望。

上述模型中，如果直接考察期望函数 \(\mathbb{E}_{\xi}[Q(x, \xi)]\)，会发现通常无法得到解析表达式，或者需要进行高维数值积分，这在计算上是极其困难甚至不可行的（computationally intractable）。SAA方法通过用样本均值来近似期望值，从而将原问题转化为一个确定性的近似问题。

思路⚓︎

SAA方法的核心思想是用样本均值（Sample Average）来替换期望值（Expected Value）。具体步骤如下：

  1. 生成样本 (Sampling): 从随机向量 \(\xi\)的概率分布中，独立同分布地抽取 \(N\)个样本（或称场景， Scenario），记为 \(\xi^1, \xi^2, \ldots, \xi^N\)。
  2. 构建近似问题 (Approximation): 将原问题 (*)中的期望项 \(\mathbb{E}_{\xi}[Q(x, \xi)]\)替换为其在 \(N\)个样本上的均值，从而构建如下的样本均值近似问题（SAA问题），约束条件省略。但是目标函数里一定有一个 \(\sum\) Scenario 的成本项在里面：
\[\min_{x \in X} \left\{ \hat{g}_N(x) = f(x) + \frac{1}{N} \sum_{i=1}^{N} Q(x, \xi^i) \right\} \quad (**)\]
  1. 你会发现在所有用SAA 的 Paper 上都会构建这么一个新的数学模型。
  2. 直觉：这个不确定性的问题，通过你的采样，实际上转化成了一个单一的、庞大的新的（往往是整数）规划问题；

怎么理解这个 \(Q\)：可以视为一个“追索成本”。

比如，对于一个考虑随机性的背包问题：事先给定背包容量和待选的货物数量、货物价值，不过每个货物的重量未知，但是我们预先知道了每个货物重量的概率分布。

在你不知道每个货物多重的情况下，无论你给出怎样的装载方案（只要装了物品），由于随机变量的存在，在采样出的一个结果中，这个重量可能超过预期，实际重量大于背包容量了。这时候你就要惩罚这个装载方案的效果。这个函数就代表了这种“惩罚”或者“追索”。

譬如5个货物，价值 0.1, 0.2,3,4,5，重量分别服从均值 \((\mu_1, \sigma_1), (\mu_1, \sigma_1),(\mu_2, \sigma_2),(\mu_3, \sigma_3),(\mu_4, \sigma_4),(\mu_5, \sigma_5)\) 的正态分布。你的包裹重 \(\mu_4 + \mu_5 + 0.5\)，你给出的装包方案是装 4，5号。但是实际你按照这个均值标准差采样一组结果，可能它重量就超过 \(\mu_4 + \mu_5 + 0.5\)了。这说明我们给出的一组装包方案在一种极端情况下，不那么合理。

所以，需要有一个追索成本，控制当前方案每次采样后（此时就是一个确定性问题，deterministic problem）带来的成本。

怎么理解这个“场景”：Scenario

一个场景 (Scenario)，指的是从所有不确定参数的联合概率分布中进行一次抽样，所得到的一组确定的数值。这个场景，与所有确定参数 组合在一起，就构成了一个完整的、可以求解的确定性问题实例。

我们以一个顾客需求不确定性、路段走行时间不确定的 VRP 问题来举个例子：

原始随机问题信息 (概率分布信息): * 确定参数: * 客户 A 位置: (10, 20) * 客户 B 位置: (30, 40) * 车辆容量: 100 * 不确定参数 (概率分布): * 客户 A 的需求 (Demand A): 服从均值为 30 的正态分布 N(30, 5²)。 * 客户 B 的需求 (Demand B): 服从 [50, 70] 区间的均匀分布 U(50, 70)。 * A到B的行驶时间 (Time AB): 有70%概率是20分钟，30%概率是35分钟。

我们进行一次随机抽样： * 从 N(30, 5²) 中抽到一个值：32 * 从 U(50, 70) 中抽到一个值：61 * 根据 70%/30% 的概率，抽到一个时间：20分钟

那么，上述抽样就构成了如下所示的、完全确定的VRP问题：

  • 客户 A 位置: (10, 20)，需求: 32
  • 客户 B 位置: (30, 40)，需求: 61
  • A到B的行驶时间: 20分钟
  • 车辆容量: 100

这个确定问题就是一个 Scenario。

对于不考虑随机性的问题而言，这可以直接用整数规划或者其他算法来解，但是我们不这么做！这只是其中一个样本而已，我们要做的见下一个问题。

假设采样了 100个场景，我们要解100次么？

这是关于SAA最关键、也最容易产生误解的一点。

根本性的区别在于：SAA方法的目标不是为这100个场景分别求解100条不同的解然后“挑选”一条。

相反，SAA构建的是一个单一的、巨大的确定性优化模型。这个模型的最终解，是一个唯一的方案（a priori solution），这个方案在这100个场景的平均表现是最好的。

怎么衡量这个 “表现”？ 这就是上面的\(Q\) 函数了。针对问题而定。

  1. 在这个巨大的模型里，变量被分为两类。

    • 第一阶段变量 (First-stage variables): 这些变量定义了你的初始决策方案。对于一个不确定的背包问题，就是“是否装物品 \(i\)，对于一个不确定的 VRP 问题，就是 “\(k\) 是否走 \((i, j)\)
    • 第二阶段变量 (Second-stage variables): 这些变量代表在某个特定场景下，当初始路径确定后，你需要采取的追索行动。例如，一个不确定的 VRP 问题，会有一个变量 \(y_{is}\) 表示“在场景s下，客户i的需求有多少未被满足”；或者 \(z_s\) 表示“在场景 \(s\) 下，车辆需要返回车库的次数”。这些变量是与每个场景s绑定的，所以如果你有100个场景，你就会有100套这样的变量。

  2. 统一的目标函数： 这个巨大模型的目标函数是：

    \[\min \left( \text{第一阶段成本} + \frac{1}{N} \sum_{s=1}^{N} \text{场景 s 的追索成本} \right)\]

    第一阶段成本: 完全由第一阶段变量\(x_{ijk}\)决定，比如初始路径的总长度。这个成本只计算一次。

    场景s的追索成本: 由第二阶段变量\(y_{is}, z_s\)等决定。它代表，假如我们执行了第一阶段给出的初始路径，而在执行时恰好遇到了场景s的状况（比如具体的需求和行驶时间），为了完成任务所付出的额外代价。

    求和再平均: 我们把这个追索成本在所有100个场景下进行计算，然后取一个平均值。这代表了我们对“期望追索成本”的近似。

  3. 求解与结果： 当你把这个包含了一套第一阶段变量和100套第二阶段变量以及上述目标函数的巨大确定性模型交给求解器去求解，就可了！

    • 求解器会同时优化所有这些变量。它会去寻找一套唯一的初始路径（由第一阶段变量决定），这套路径也许在场景1里不是最优的，在场景23里也不是最优的，但它能使得“初始路径成本 + 在100个场景下的平均追索成本”这个总期望成本达到最小。
    • 因此，求解结束后，你从结果中提取的，只有那一套第一阶段变量的值。它们共同构成了那个唯一的、“对原随机问题的最好近似”的初始路径。第二阶段变量的值在得到初始解后就不再重要了，它们的作用是在求解过程中帮助评估每个潜在初始解的“鲁棒性”。

这个SAA问题 (**) 是一个确定性的优化问题。对于每一个给定的第一阶段决策 \(x\)和一个具体的场景 \(\xi^i\)，\(Q(x, \xi^i)\)的值可以通过求解一个确定性的第二阶段子问题得到：

\(Q(x, \xi^i) = \min_{y} \{ q(y) \mid T(x) + W(\xi^i)y \ge h(\xi^i) \}\)

其中 \(y\)是第二阶段决策变量。因此，SAA问题 (**) 是一个大规模的确定性优化问题，理论上可以使用标准的确定性优化求解器进行求解。

在实际中，这个庞大问题一般都会针对每个场景进行分支或者应用一些分解算，比如 Benders 等，从而加速计算。

理论保证⚓︎

以下生成自 Gemini 2.5 Pro，因为我不怎么看得懂理论了，如果有错或许需要有人来提示。更好地学习方式是看看Paper：The Sample Average Approximation Method for Stochastic Discrete Optimization. Anton J. Kleywegt, Alexander Shapiro, and Tito Homem-de-Mello. SIAM Journal on Optimization 2002 12:2, 479-502

SAA方法的有效性依赖于大数定律和中心极限定理，其理论保证是该方法得以广泛应用的基石。

  • 收敛性 (Consistency):

    • 最优值的收敛性： 当样本量 \(N \to \infty\)时，SAA问题 (**) 的最优目标值 \(\hat{v}_N\)以概率1收敛于原随机问题 (*) 的真实最优目标值 \(v^*\)。即 \(\hat{v}_N \xrightarrow{a.s.} v^*\)。
    • 最优解的收敛性： 在一定正则条件下，SAA问题的最优解集 \(\hat{S}_N\)会收敛于原问题的最优解集 \(S^*\)。这意味着当样本量足够大时，通过求解SAA问题得到的解 \(\hat{x}_N\)可以是原问题真实最优解的一个良好近似。

  • 统计推断 (Statistical Inference):

    • 下界估计 (Lower Bound): SAA问题的最优值 \(\hat{v}_N = \hat{g}_N(\hat{x}_N)\)是对原问题真实最优值 \(v^*\)的一个有偏估计（通常是偏低的）。一个更好的（近似无偏的）下界估计可以通过对一个新的、独立的、大规模的样本集 \(N'\)来计算：\(LB = f(\hat{x}_N) + \frac{1}{N'} \sum_{j=1}^{N'} Q(\hat{x}_N, \xi^j)\)。
    • 上界估计 (Upper Bound): 原问题的真实最优目标值 \(v^*\)的一个有效统计上界是 \(\mathbb{E}[\hat{v}_N]\)。
    • 最优性差距 (Optimality Gap): 通过比较下界和上界，可以估计所求得解 \(\hat{x}_N\)的次优程度。最优性差距 \(g(\hat{x}_N) - v^*\)可以通过 \((LB - \hat{v}_N)\)来估计，并可以构建其置信区间。这为评估解的质量提供了量化依据。

4. SAA方法的难点与挑战⚓︎

虽然SAA方法理论上具有优良性质，但在实践中仍面临诸多挑战：

  1. 计算复杂度 (Computational Complexity):

    • SAA问题 (**) 的规模随着样本量 \(N\)的增大而线性增长。当每个场景的第二阶段问题本身就很复杂时，整个SAA模型可能变得异常庞大，导致求解时间过长。
    • 决策变量的数量和约束的数量通常是 \(O(N)\)的量级，对于复杂的VRP问题，这会迅速达到商业求解器处理能力的极限。

  2. 样本量选择 (Sample Size Selection):

    • 样本量太小： 会导致样本均值 \(\hat{g}_N(x)\)对真实期望 \(g(x)\)的近似质量很差，解的稳定性低。用不同批次的少量样本求解得到的解 \(\hat{x}_N\)可能差异巨大。
    • 样本量太大： 会导致计算负担难以承受。
    • 如何在解的质量和计算成本之间取得平衡，选择一个“足够好”的样本量 \(N\)，是实践中的一个核心难题，通常需要结合问题特性和经验进行判断。

  3. 解的评估 (Solution Evaluation):

    • SAA问题 (**) 的最优值 \(\hat{v}_N\)并不能直接代表解 \(\hat{x}_N\)在原问题 (*) 中的真实性能。
    • 为了客观评估解 \(\hat{x}_N\)的质量，必须进行核外验证 (Out-of-Sample Validation)：即重新生成一个规模巨大（\(N' \gg N\)）的独立测试样本集，并计算 \(g_{N'}(\hat{x}_N) = f(\hat{x}_N) + \frac{1}{N'} \sum_{j=1}^{N'} Q(\hat{x}_N, \xi^j)\)。这个值才是对解 \(\hat{x}_N\)真实期望成本的可靠估计。

  4. 随机变量的高维性： 当随机向量 \(\xi\)的维度非常高时（例如，每个客户的需求和每条路的行驶时间都是随机的），可能需要极大的样本量 \(N\)才能充分探索不确定性的空间，这加剧了“维度灾难”问题。