随机规划中的渐进一致性分析 我们先从随机规划问题的基本形式开始。考虑随机规划问题： \[ \min_ {x \in X} \mathbb{E}[ f(x,\xi) ] \] 其中 \(X \subseteq \mathbb{R}^n\) 是可行域，\(\xi\) 是定义在概率空间 \((\Omega, \mathcal{F}, P)\) 上的随机向量。由于期望的精确计算通常困难，实践中常用样本平均近似（SAA）方法： \[ \min_ {x \in X} \hat{f} N(x) = \frac{1}{N}\sum {i=1}^N f(x,\xi_ i) \] 其中 \(\{\xi_ i\}_ {i=1}^N\) 是独立同分布的样本。 渐进一致性分析的核心问题是：当样本量 \(N \to \infty\) 时，SAA问题的最优解和最优值在何种意义下收敛到原问题的真解和真值？ 首先考虑最优值的收敛性。在适当的正则性条件下（如 \(f(x,\xi)\) 关于 \(x\) 连续，且存在可积函数支配），由大数定律，对每个固定的 \(x\)，有 \(\hat{f}_ N(x) \to \mathbb{E}[ f(x,\xi)]\) 几乎必然成立。但一致收敛性更为关键：若 \(\hat{f}_ N(x)\) 在 \(X\) 上一致收敛到 \(\mathbb{E}[ f(x,\xi)]\)，则记 \(v^ \) 和 \(\hat{v}_ N\) 分别为原问题和SAA问题的最优值，有 \(\hat{v}_ N \to v^ \) 几乎必然。 进一步，考虑最优解集的收敛性。定义原问题的最优解集 \(S^* \) 和SAA问题的最优解集 \(\hat{S}_ N\)。在 \(\hat{f}_ N\) 在 \(X\) 上以概率1一致收敛到 \(\mathbb{E}[ f(x,\xi) ]\) 且 \(X\) 紧的条件下，有： \(\hat{v}_ N \to v^* \) 以概率1成立 \(\hat{S}_ N\) 到 \(S^* \) 的Hausdorff距离以概率1收敛到0 现在考虑收敛速率。若 \(f(x,\xi)\) 在 \(X\) 上Lipschitz连续，则最优值收敛速率为 \(O_ p(N^{-1/2})\)。更精确地，在特定条件下，\(\hat{v}_ N - v^* \) 的渐近分布与某个正态分布相关。 当原问题有唯一最优解 \(x^ \) 时，在二阶充分条件下，SAA问题的最优解 \(\hat{x}_ N\) 满足： \[ \sqrt{N}(\hat{x}_ N - x^ ) \xrightarrow{d} \mathcal{N}(0, V) \] 其中协方差矩阵 \(V\) 依赖于 \(f\) 在 \(x^* \) 处的Hessian矩阵和梯度协方差。 对于约束问题 \(\min_ {x \in X} \{\mathbb{E}[ f(x,\xi)]: \mathbb{E}[ g_ j(x,\xi) ] \leq 0, j=1,\dots,m\}\)，SAA形式为： \[ \min_ {x \in X} \{\hat{f} N(x): \hat{g} {jN}(x) \leq 0, j=1,\dots,m\} \] 此时需考虑可行域的近似一致性。若真实可行域和近似可行集之间的Hausdorff距离以概率1收敛到0，则最优值和最优解集的收敛性结论仍然成立。 渐进一致性分析为样本量选择提供了理论指导：要获得ε-近似解，样本量需满足 \(N = O(1/\varepsilon^2)\)。这一结论在随机规划的算法设计和实际应用中具有重要价值。