随机规划中的外逼近方法 外逼近方法是一类求解随机规划问题的迭代算法，其核心思想是通过构造一系列逐渐逼近原问题的确定性优化问题来求解。下面逐步展开讲解： 1. 问题背景与动机 随机规划问题通常形式为： \[ \min_ {x \in X} \mathbb{E}[ F(x,\xi) ] \] 其中 \( \xi \) 是随机变量，\( F \) 可能非凸或不可微。直接求解困难，因为期望算子涉及高维积分。外逼近方法通过 外部线性化 期望函数，将问题转化为一系列易于求解的子问题。 2. 基本思想：外部线性化 外逼近的核心是 割平面法 。假设期望函数 \( Q(x) = \mathbb{E}[ F(x,\xi) ] \) 是凸的（或局部凸），则可在迭代过程中逐步添加线性割平面，这些割平面在每次迭代中从当前点 \( x^k \) 处生成，并满足： \[ Q(x) \geq Q(x^k) + g^k (x - x^k) \] 其中 \( g^k \) 是 \( Q(x) \) 在 \( x^k \) 处的次梯度（或梯度）。这些不等式构成对 \( Q(x) \) 的下逼近，逐步收紧近似。 3. 算法步骤 初始化 ：设定初始点 \( x^0 \)，容忍误差 \( \epsilon > 0 \)，迭代计数器 \( k=0 \)。 生成割平面 ： 在 \( x^k \) 处估计 \( Q(x^k) \) 和其次梯度 \( g^k \)（例如通过样本平均或随机梯度）。 记录割平面： \[ \ell^k(x) = Q(x^k) + g^k (x - x^k) \] 构建近似问题 ： 求解当前近似问题： \[ \min_ {x \in X} \max_ {j \leq k} \ell^j(x) \] 该问题是一个线性规划或凸优化问题，易求解，得到新迭代点 \( x^{k+1} \)。 收敛判断 ： 若 \( Q(x^k) - \max_ {j \leq k} \ell^j(x^{k+1}) < \epsilon \)，则停止；否则令 \( k = k+1 \) 返回步骤 2。 4. 关键技术细节 次梯度估计 ：若 \( F(x,\xi) \) 不可微，需使用随机次梯度（如随机拟梯度法）或光滑化技术。 收敛性 ：在凸性假设下，外逼近法具有有限步收敛性或渐近收敛性；非凸情形可能需要结合分支定界或启发式策略。 计算效率 ：每步需存储所有割平面，可能造成内存负担，可结合割平面删除策略（如淘汰旧割平面）。 5. 扩展与变体 随机外逼近 ：当期望无法精确计算时，用样本平均近似（SAA）生成随机割平面。 水平集方法 ：通过水平约束构造外部逼近，适用于约束随机规划。 结合内点法 ：用内点法求解近似问题，提升大规模问题求解效率。 6. 应用场景 外逼近方法常用于两阶段随机线性规划、风险优化问题（如条件风险价值优化），以及随机整数规划松弛后的连续问题。