设定

设一阶段决策为 ，二阶段线性递补值函数为

其中 。给定目标值 ，定义超额损失

经验参考分布取为

原问题

定义 1（标准两阶段 -Wasserstein RS 模型）

原始模型写为

其中 为基于 -范数的 Wasserstein 距离。

精确重构

定理 1（经验分布中心下的精确重构）

对任意给定 ，约束

等价于

证明

由 Wasserstein 距离定义，

故

由于

任意满足 的联合分布均可写为

其中 。于是上式化为

对每个 ，最优 可退化为单点分布，从而得到

证毕。

命题 1（半无限规划形式）

模型 等价于如下半无限规划：

证明（命题 1）

由定理 1，原问题约束等价于

对每个样本 引入上图变量 ，使其逐点上界对应的 supremum，即得结论。证毕。

CCG 主问题

设第 次迭代时，样本 已生成场景集合为

命题 2（受限主问题）

在 上截断半无限约束，得到 CCG 的主问题：

证明（命题 2）

对半无限约束

仅在 上保留。又因

故对每个已生成场景复制一套二阶段变量 ，即得主问题。证毕。

分离子问题

设 为 的最优解。

命题 3（分离子问题的原始形式）

对每个样本 ，其最坏违反值由下式给出：

若

则对应最优场景 产生一条被违反的半无限约束，应加入 。

证明（命题 3）

这是半无限约束的直接可行性检验：当前解对样本 可行，当且仅当

证毕。

命题 4（分离子问题的对偶化）

若二阶段问题满足强对偶，则

因此， 等价于

证明（命题 4）

由二阶段线性规划强对偶，

同时，

代入 即得。证毕。

最坏场景结构

命题 5（坐标三点结构）

固定 与任意 ，记

则 中给定 后，每个坐标 的最优取值满足

且显式为

证明（命题 5）

固定 后，目标函数关于单个坐标 的部分为

这是一个在 处折点的分段线性函数。其左右斜率分别为

故：

  • 当 时，左右斜率均为正，最优点为 ；
  • 当 时，左右斜率均为负，最优点为 ；
  • 当 时，左斜率非负、右斜率非正，最优点为 。

证毕。

推论 1（有限候选场景集）

对每个样本 ，分离子问题只需在有限集合

上寻找最坏场景，故

收敛性

定理 2（最优性判别）

若第 次迭代的主问题最优解 满足

则 为原始模型 的最优解。

证明（定理 2）

上述条件表明当前解满足半无限约束的全部约束，因此对 可行，也即对原问题可行。另一方面， 是 的松弛，其最优值不大于原问题最优值；而当前解既是 的最优解，又对原问题可行，故二者目标值相等，从而当前解即为原问题最优解。证毕。

定理 3（有限终止）

若算法每次对任一被违反的样本 至少加入一个新场景 ，则 CCG 在有限步内终止。

证明（定理 3）

由推论 1，对每个样本 可加入的候选场景集合 有限，且

因此总可加入场景数有限。算法每次未终止时至少加入一个新场景，故只能有限次更新，必有限终止。终止时由定理 2 得最优性。证毕。

算法

算法 1：两阶段 -Wasserstein RS 的 CCG

步骤内容
0初始化：对每个 ，置 ，令 。
1求解主问题：求解 ，得到最优解 。
2分离：对每个 ，求解分离子问题 （或其对偶形式 ），得到 及最坏场景 。
3最优性检验：若对所有 都有 ，则停止，并输出 。
4场景扩充：对所有满足 的样本 ，更新 ；其余样本令 。
5迭代：令 ，返回步骤 1。