随机规划中的外逼近方法 随机规划中的外逼近方法是一种求解具有复杂期望约束或目标函数的随机优化问题的算法框架。其核心思想是通过逐步添加外部线性约束（割平面）来逼近原问题的可行域或目标函数，将难以直接求解的问题转化为一系列相对简单的子问题。 第一步：问题背景与动机 考虑随机规划问题的一般结构： min { f(x) = E[ F(x,ξ)] | x ∈ X, g_ i(x) = E[ G_ i(x,ξ) ] ≤ 0, i=1,...,m } 其中ξ是随机变量，F和G_ i可能为非线性函数，期望运算E[ · ]通常无显式表达式。直接求解此类问题困难，因为： 期望值计算需高维积分，计算昂贵； 约束或目标函数的非线性导致非凸性。 外逼近法通过构造外部线性逼近函数，将原问题转化为可迭代求解的序列规划问题。 第二步：基本框架与割平面生成 外逼近法的核心步骤是生成割平面（cutting plane）。以目标函数f(x)为例： 在迭代点x_ k处，若f(x)是凸函数，则存在次梯度∂f(x_ k)满足： f(x) ≥ f(x_ k) + ∂f(x_ k)^T (x - x_ k), ∀x ∈ X。 此线性不等式称为割平面，它在x_ k处紧贴f(x)，且在其它点提供下界逼近。 类似地，对约束函数g_ i(x)，可生成约束割平面： g_ i(x) ≥ g_ i(x_ k) + ∂g_ i(x_ k)^T (x - x_ k) ≤ 0。 割平面将原非线性期望函数局部线性化，使问题简化为线性规划或二次规划。 第三步：算法流程 初始化 ：选择初始点x_ 0，设定容忍度ε>0，迭代计数器k=0。 割平面生成 ： 在x_ k处，通过样本平均近似或随机梯度估计计算f(x_ k)和g_ i(x_ k)的估计值及次梯度。 生成目标函数割平面：L_ k(x) = f(x_ k) + ∂f(x_ k)^T (x - x_ k)。 生成约束割平面：C_ {i,k}(x) = g_ i(x_ k) + ∂g_ i(x_ k)^T (x - x_ k) ≤ 0。 主问题求解 ：构建当前逼近问题： min { t | t ≥ L_ j(x), C_ {i,j}(x) ≤ 0, ∀j≤k, x∈X }， 其中t为辅助变量，代表目标函数上界。求解得新迭代点x_ {k+1}。 收敛判断 ：若|f(x_ k) - f(x_ {k+1})| < ε，停止；否则k=k+1，返回步骤2。 第四步：收敛性分析 外逼近法的收敛性依赖于以下条件： 凸性假设 ：若f(x)和g_ i(x)为凸函数，且集合X紧致，则生成割平面序列的极限点必为原问题最优解。 次梯度有界性 ：次梯度∂f(x_ k)和∂g_ i(x_ k)需一致有界，保证逼近误差可控。 采样误差管理 ：当使用随机样本估计期望时，需增加样本量使估计误差渐近趋于零。 收敛速率通常为O(1/√k)（非光滑情形）或O(1/k)（光滑强凸情形）。 第五步：扩展与变体 随机情景 ：当期望无法精确计算时，可采用样本平均近似（SAA）生成随机割平面，并结合大数定律保证收敛。 非凸处理 ：对于非凸问题，可引入凸松弛或组合割平面（如反向线性化），但可能收敛至局部解。 分布式实现 ：对大规模问题，可将割平面生成任务分解到多个计算节点，并行求解主问题。 外逼近法通过逐次线性化将复杂随机规划问题分解为可处理的子问题，特别适用于具有可分结构或高维随机参数的优化模型。