基于线性规划的分布式鲁棒优化中 Wasserstein 模糊集下分布鲁棒机会约束规划问题的求解示例
字数 5232 2025-12-18 19:57:11

基于线性规划的分布式鲁棒优化中 Wasserstein 模糊集下分布鲁棒机会约束规划问题的求解示例

1. 题目描述

考虑一个需要在不确定性下做决策的问题，例如在风电场出力不确定的情况下，决定各传统发电机组的出力，以满足电力负荷需求。由于风电场出力的真实概率分布未知，我们仅能获得一些历史观测数据（样本）。我们希望决策是“分布鲁棒”的，即对于一组可能的风电出力概率分布（称为模糊集），都大概率满足某些运行约束（例如线路容量限制）。这种包含概率约束的鲁棒优化问题，称为分布鲁棒机会约束规划。

具体建模为：
设决策变量为发电机出力向量 \(x \in \mathbb{R}^n\)，其运行成本为 \(c^\top x\)。不确定性来自风电出力向量 \(\xi \in \mathbb{R}^m\)，其真实分布 \(\mathbb{P}\) 未知。我们要求对于所有可能分布 \(\mathbb{P} \in \mathcal{P}\)（模糊集），系统在风电出力为 \(\xi\) 时的总出力与负荷平衡约束被违反的概率不超过一个小常数 \(\epsilon\)。这里模糊集 \(\mathcal{P}\) 由 Wasserstein 距离定义，它基于有限的历史样本 \(\{\hat{\xi}_1, \dots, \hat{\xi}_N\}\) 构建，包含了与经验分布“相距不远”的所有分布。

目标：最小化总成本 \(c^\top x\)，并满足上述分布鲁棒机会约束。我们的任务是将其建模为一个可求解的（通常是凸的）优化问题，并阐释其求解思路。

2. 问题形式化与 Wasserstein 模糊集

2.1 机会约束

设系统约束为线性形式：\(a(x)^\top \xi \le b(x)\)，其中 \(a(x), b(x)\) 是 \(x\) 的仿射函数。机会约束要求：

\[\sup_{\mathbb{P} \in \mathcal{P}} \mathbb{P}\{ a(x)^\top \xi > b(x) \} \le \epsilon \]

即，在最坏的可能分布 \(\mathbb{P} \in \mathcal{P}\) 下，违反约束的概率不超过 \(\epsilon\)。\(\epsilon\) 通常很小，如 0.05 或 0.1。

2.2 Wasserstein 模糊集

设有 \(N\) 个历史样本 \(\hat{\xi}_1, \dots, \hat{\xi}_N\)，定义经验分布 \(\hat{\mathbb{P}}_N = \frac{1}{N} \sum_{i=1}^N \delta_{\hat{\xi}_i}\)。Wasserstein 模糊集 \(\mathcal{P}\) 定义为：

\[\mathcal{P} = \{ \mathbb{P} \in \mathcal{M}(\Xi) : d_W(\mathbb{P}, \hat{\mathbb{P}}_N) \le \theta \} \]

其中：

  • \(\Xi \subseteq \mathbb{R}^m\) 是 \(\xi\) 的支撑集（通常为凸紧集，如一个盒子区域或整个空间）。
  • \(\mathcal{M}(\Xi)\) 是 \(\Xi\) 上所有概率分布的集合。
  • \(d_W\) 是 1-Wasserstein 距离，定义为：

\[ d_W(\mathbb{P}, \mathbb{Q}) = \inf_{\pi \in \Pi(\mathbb{P}, \mathbb{Q})} \int_{\Xi \times \Xi} \|\xi - \xi'\| \, \pi(d\xi, d\xi') \]

其中 \(\Pi(\mathbb{P}, \mathbb{Q})\) 是边缘分布为 \(\mathbb{P}, \mathbb{Q}\) 的所有联合分布。

  • \(\theta \ge 0\) 是模糊集半径，控制了我们对经验分布的“信任程度”。\(\theta\) 越大，考虑的分布范围越广，模型越保守。

3. 从分布鲁棒机会约束到确定性约束（关键转化）

对于形如 \(\sup_{\mathbb{P} \in \mathcal{P}} \mathbb{P}\{ a(x)^\top \xi > b(x) \} \le \epsilon\) 的约束，在 Wasserstein 模糊集下，可以通过鲁棒优化和对偶理论将其等价转化为一个确定性的凸约束。

核心定理（简化表述）：
假设支撑集 \(\Xi = \mathbb{R}^m\) 或为一个凸多面体，且代价函数 \(\|\cdot\|\) 为任意范数。则上述分布鲁棒机会约束等价于存在一个辅助变量 \(s \ge 0\) 和 \(t \in \mathbb{R}\)，使得以下两个条件同时成立：

  1. 一个线性约束：

\[ b(x) - a(x)^\top \xi_i \ge s, \quad \forall i = 1, \dots, N \]

这是对每个样本点 \(\hat{\xi}_i\) 的约束。

  1. 一个非线性凸约束：

\[ \theta \|a(x)\|_* + \frac{1}{N} \sum_{i=1}^N \max\{ b(x) - a(x)^\top \hat{\xi}_i - s, \, 0 \} \le \epsilon s \]

其中 \(\| \cdot \|_*\) 是 Wasserstein 距离中所用范数 \(\|\cdot\|\) 的对偶范数（例如，若 Wasserstein 距离用 \(l_1\) 范数，则对偶范数为 \(l_\infty\)）。

  1. 另外，还需满足 \(s \ge 0\)。

直观理解：

  • 第一个条件保证了对于每个历史样本点，约束 \(a(x)^\top \xi \le b(x)\) 有一个至少为 \(s\) 的“安全余量”。
  • 第二个条件是一个关于 \(s\) 和 \(x\) 的凸约束，它综合了 Wasserstein 球半径 \(\theta\)、对偶范数、经验违反程度和风险水平 \(\epsilon\)，确保在最坏分布下违反概率不超过 \(\epsilon\)。

4. 完整优化问题建模

基于上述转化，原分布鲁棒机会约束规划问题可写为如下确定性优化问题：

\[\begin{aligned} \min_{x, s} \quad & c^\top x \\ \text{s.t.} \quad & b(x) - a(x)^\top \hat{\xi}_i \ge s, \quad \forall i = 1, \dots, N, \\ & \theta \|a(x)\|_* + \frac{1}{N} \sum_{i=1}^N \max\{ b(x) - a(x)^\top \hat{\xi}_i - s, \, 0 \} \le \epsilon s, \\ & s \ge 0, \\ & x \in \mathcal{X}, \end{aligned} \]

其中 \(\mathcal{X}\) 是 \(x\) 的其它确定约束集合（如出力上下限、爬坡速率等）。

注意：目标函数和第一个约束关于 \(x\) 是线性的（因 \(a(x), b(x)\) 是 \(x\) 的仿射函数）。第二个约束中包含 \(\max\) 函数和范数，是凸的但非光滑。

5. 求解步骤（以 \(l_1\) Wasserstein 距离为例）

假设 Wasserstein 距离使用 \(l_1\) 范数，则其对偶范数 \(\| \cdot \|_* = \| \cdot \|_\infty\)。我们逐步求解：

5.1 引入辅助变量处理 \(\max\) 函数

对每个样本 \(i\)，引入辅助变量 \(z_i \ge 0\)，将第二个约束等价写为：

\[\begin{aligned} & \theta \|a(x)\|_\infty + \frac{1}{N} \sum_{i=1}^N z_i \le \epsilon s, \\ & z_i \ge b(x) - a(x)^\top \hat{\xi}_i - s, \quad \forall i, \\ & z_i \ge 0, \quad \forall i. \end{aligned} \]

5.2 处理无穷范数 \(\|a(x)\|_\infty\)

设 \(a(x) = A x + d\)（\(A\) 为矩阵，\(d\) 为向量）。约束 \(\|A x + d\|_\infty \le t\) 等价于一组线性约束：

\[-t \le (A x + d)_j \le t, \quad \forall j = 1, \dots, m. \]

这里我们可引入新变量 \(t \ge 0\)，并令 \(\theta t + \frac{1}{N} \sum_i z_i \le \epsilon s\)，同时添加约束 \(-t \le (A x + d)_j \le t, \, \forall j\)。

5.3 得到最终线性规划（LP）或二阶锥规划（SOCP）问题

综合以上，原问题转化为：

\[\begin{aligned} \min_{x, s, t, \{z_i\}} \quad & c^\top x \\ \text{s.t.} \quad & b(x) - a(x)^\top \hat{\xi}_i \ge s, \quad \forall i, \\ & z_i \ge b(x) - a(x)^\top \hat{\xi}_i - s, \quad \forall i, \\ & z_i \ge 0, \quad \forall i, \\ & -t \le (A x + d)_j \le t, \quad \forall j, \\ & \theta t + \frac{1}{N} \sum_{i=1}^N z_i \le \epsilon s, \\ & s \ge 0, \, t \ge 0, \\ & x \in \mathcal{X}. \end{aligned} \]

注意：这里 \(b(x) - a(x)^\top \hat{\xi}_i\) 是 \(x\) 的线性函数。因此，所有约束都是线性的，目标也是线性的。这形成了一个线性规划（LP），可以用单纯形法或内点法高效求解。

如果 Wasserstein 距离使用 \(l_2\) 范数，则对偶范数为 \(l_2\) 范数，约束 \(\theta \|a(x)\|_2 + \cdots \le \epsilon s\) 会引入一个二阶锥约束，问题变为二阶锥规划（SOCP），也可用内点法求解。

6. 求解过程总结

  1. 收集数据：获得历史风电出力样本 \(\hat{\xi}_1, \dots, \hat{\xi}_N\)。
  2. 选择参数：设定风险水平 \(\epsilon\) 和 Wasserstein 球半径 \(\theta\)（后者可通过交叉验证等方法调整）。
  3. 建立模型：将分布鲁棒机会约束按上述方法转化为一组确定性线性（或二阶锥）约束。
  4. 调用求解器：使用线性规划（如 GLPK, CPLEX, Gurobi）或二阶锥规划求解器（如 MOSEK, CPLEX, Gurobi）求解最终模型，得到最优决策 \(x^*\) 和对应的安全余量 \(s^*\)。
  5. 分析结果：\(x^*\) 即为在风电出力分布不确定下，满足鲁棒机会约束的最小成本发电计划。

7. 延伸讨论

  • Wasserstein 半径 \(\theta\) 的选择：\(\theta\) 控制了保守程度。\(\theta=0\) 时，模糊集只包含经验分布，模型退化为传统机会约束规划（样本平均近似）；\(\theta\) 增大，模型更鲁棒，但成本可能更高。可通过样本外交叉验证或渐进理论（如 \(\theta \propto 1/\sqrt{N}\)）来选取。
  • 多约束情形：若有多条机会约束，每条可独立转化为上述形式，然后联合求解。
  • 计算优势：与传统的场景鲁棒优化（需处理大量场景）相比，Wasserstein 方法通常只需样本个数 \(N\) 的线性规模约束，更易求解。

这种方法将数据驱动的分布不确定性、风险容忍度和鲁棒性统一在一个凸优化框架中，是近年来随机优化领域的重要进展。

基于线性规划的分布式鲁棒优化中 Wasserstein 模糊集下分布鲁棒机会约束规划问题的求解示例 1. 题目描述 考虑一个需要在不确定性下做决策的问题，例如在风电场出力不确定的情况下，决定各传统发电机组的出力，以满足电力负荷需求。由于风电场出力的真实概率分布未知，我们仅能获得一些历史观测数据（样本）。我们希望决策是“分布鲁棒”的，即对于一组可能的风电出力概率分布（称为模糊集），都 大概率 满足某些运行约束（例如线路容量限制）。这种包含概率约束的鲁棒优化问题，称为 分布鲁棒机会约束规划 。 具体建模为 ： 设决策变量为发电机出力向量 \(x \in \mathbb{R}^n\)，其运行成本为 \(c^\top x\)。不确定性来自风电出力向量 \(\xi \in \mathbb{R}^m\)，其真实分布 \(\mathbb{P}\) 未知。我们要求对于所有可能分布 \(\mathbb{P} \in \mathcal{P}\)（模糊集），系统在风电出力为 \(\xi\) 时的总出力与负荷平衡约束被违反的概率不超过一个小常数 \(\epsilon\)。这里模糊集 \(\mathcal{P}\) 由 Wasserstein 距离定义，它基于有限的历史样本 \(\{\hat{\xi}_ 1, \dots, \hat{\xi}_ N\}\) 构建，包含了与经验分布“相距不远”的所有分布。 目标 ：最小化总成本 \(c^\top x\)，并满足上述分布鲁棒机会约束。我们的任务是将其建模为一个可求解的（通常是凸的）优化问题，并阐释其求解思路。 2. 问题形式化与 Wasserstein 模糊集 2.1 机会约束 设系统约束为线性形式：\(a(x)^\top \xi \le b(x)\)，其中 \(a(x), b(x)\) 是 \(x\) 的仿射函数。机会约束要求： \[ \sup_ {\mathbb{P} \in \mathcal{P}} \mathbb{P}\{ a(x)^\top \xi > b(x) \} \le \epsilon \] 即，在最坏的可能分布 \(\mathbb{P} \in \mathcal{P}\) 下，违反约束的概率不超过 \(\epsilon\)。\(\epsilon\) 通常很小，如 0.05 或 0.1。 2.2 Wasserstein 模糊集 设有 \(N\) 个历史样本 \(\hat{\xi}_ 1, \dots, \hat{\xi} N\)，定义经验分布 \(\hat{\mathbb{P}} N = \frac{1}{N} \sum {i=1}^N \delta {\hat{\xi}_ i}\)。Wasserstein 模糊集 \(\mathcal{P}\) 定义为： \[ \mathcal{P} = \{ \mathbb{P} \in \mathcal{M}(\Xi) : d_ W(\mathbb{P}, \hat{\mathbb{P}}_ N) \le \theta \} \] 其中： \(\Xi \subseteq \mathbb{R}^m\) 是 \(\xi\) 的支撑集（通常为凸紧集，如一个盒子区域或整个空间）。 \(\mathcal{M}(\Xi)\) 是 \(\Xi\) 上所有概率分布的集合。 \(d_ W\) 是 1-Wasserstein 距离，定义为： \[ d_ W(\mathbb{P}, \mathbb{Q}) = \inf_ {\pi \in \Pi(\mathbb{P}, \mathbb{Q})} \int_ {\Xi \times \Xi} \|\xi - \xi'\| \, \pi(d\xi, d\xi') \] 其中 \(\Pi(\mathbb{P}, \mathbb{Q})\) 是边缘分布为 \(\mathbb{P}, \mathbb{Q}\) 的所有联合分布。 \(\theta \ge 0\) 是模糊集半径，控制了我们对经验分布的“信任程度”。\(\theta\) 越大，考虑的分布范围越广，模型越保守。 3. 从分布鲁棒机会约束到确定性约束（关键转化） 对于形如 \(\sup_ {\mathbb{P} \in \mathcal{P}} \mathbb{P}\{ a(x)^\top \xi > b(x) \} \le \epsilon\) 的约束，在 Wasserstein 模糊集下，可以通过 鲁棒优化 和 对偶理论 将其等价转化为一个确定性的凸约束。 核心定理（简化表述） ： 假设支撑集 \(\Xi = \mathbb{R}^m\) 或为一个凸多面体，且代价函数 \(\|\cdot\|\) 为任意范数。则上述分布鲁棒机会约束等价于存在一个辅助变量 \(s \ge 0\) 和 \(t \in \mathbb{R}\)，使得以下两个条件同时成立： 一个线性约束： \[ b(x) - a(x)^\top \xi_ i \ge s, \quad \forall i = 1, \dots, N \] 这是对每个样本点 \(\hat{\xi}_ i\) 的约束。 一个非线性凸约束： \[ \theta \|a(x)\| * + \frac{1}{N} \sum {i=1}^N \max\{ b(x) - a(x)^\top \hat{\xi} i - s, \, 0 \} \le \epsilon s \] 其中 \(\| \cdot \| * \) 是 Wasserstein 距离中所用范数 \(\|\cdot\|\) 的对偶范数（例如，若 Wasserstein 距离用 \(l_ 1\) 范数，则对偶范数为 \(l_ \infty\)）。 另外，还需满足 \(s \ge 0\)。 直观理解 ： 第一个条件保证了对于每个历史样本点，约束 \(a(x)^\top \xi \le b(x)\) 有一个至少为 \(s\) 的“安全余量”。 第二个条件是一个关于 \(s\) 和 \(x\) 的凸约束，它综合了 Wasserstein 球半径 \(\theta\)、对偶范数、经验违反程度和风险水平 \(\epsilon\)，确保在最坏分布下违反概率不超过 \(\epsilon\)。 4. 完整优化问题建模 基于上述转化，原分布鲁棒机会约束规划问题可写为如下确定性优化问题： \[ \begin{aligned} \min_ {x, s} \quad & c^\top x \\ \text{s.t.} \quad & b(x) - a(x)^\top \hat{\xi} i \ge s, \quad \forall i = 1, \dots, N, \\ & \theta \|a(x)\| * + \frac{1}{N} \sum_ {i=1}^N \max\{ b(x) - a(x)^\top \hat{\xi}_ i - s, \, 0 \} \le \epsilon s, \\ & s \ge 0, \\ & x \in \mathcal{X}, \end{aligned} \] 其中 \(\mathcal{X}\) 是 \(x\) 的其它确定约束集合（如出力上下限、爬坡速率等）。 注意 ：目标函数和第一个约束关于 \(x\) 是线性的（因 \(a(x), b(x)\) 是 \(x\) 的仿射函数）。第二个约束中包含 \(\max\) 函数和范数，是凸的但非光滑。 5. 求解步骤（以 \(l_ 1\) Wasserstein 距离为例） 假设 Wasserstein 距离使用 \(l_ 1\) 范数，则其对偶范数 \(\| \cdot \| * = \| \cdot \| \infty\)。我们逐步求解： 5.1 引入辅助变量处理 \(\max\) 函数 对每个样本 \(i\)，引入辅助变量 \(z_ i \ge 0\)，将第二个约束等价写为： \[ \begin{aligned} & \theta \|a(x)\| \infty + \frac{1}{N} \sum {i=1}^N z_ i \le \epsilon s, \\ & z_ i \ge b(x) - a(x)^\top \hat{\xi}_ i - s, \quad \forall i, \\ & z_ i \ge 0, \quad \forall i. \end{aligned} \] 5.2 处理无穷范数 \(\|a(x)\|_ \infty\) 设 \(a(x) = A x + d\)（\(A\) 为矩阵，\(d\) 为向量）。约束 \(\|A x + d\|_ \infty \le t\) 等价于一组线性约束： \[ -t \le (A x + d)_ j \le t, \quad \forall j = 1, \dots, m. \] 这里我们可引入新变量 \(t \ge 0\)，并令 \(\theta t + \frac{1}{N} \sum_ i z_ i \le \epsilon s\)，同时添加约束 \( -t \le (A x + d)_ j \le t, \, \forall j \)。 5.3 得到最终线性规划（LP）或二阶锥规划（SOCP）问题 综合以上，原问题转化为： \[ \begin{aligned} \min_ {x, s, t, \{z_ i\}} \quad & c^\top x \\ \text{s.t.} \quad & b(x) - a(x)^\top \hat{\xi}_ i \ge s, \quad \forall i, \\ & z_ i \ge b(x) - a(x)^\top \hat{\xi}_ i - s, \quad \forall i, \\ & z_ i \ge 0, \quad \forall i, \\ & -t \le (A x + d) j \le t, \quad \forall j, \\ & \theta t + \frac{1}{N} \sum {i=1}^N z_ i \le \epsilon s, \\ & s \ge 0, \, t \ge 0, \\ & x \in \mathcal{X}. \end{aligned} \] 注意 ：这里 \(b(x) - a(x)^\top \hat{\xi}_ i\) 是 \(x\) 的线性函数。因此，所有约束都是线性的，目标也是线性的。这形成了一个 线性规划（LP） ，可以用单纯形法或内点法高效求解。 如果 Wasserstein 距离使用 \(l_ 2\) 范数，则对偶范数为 \(l_ 2\) 范数，约束 \(\theta \|a(x)\|_ 2 + \cdots \le \epsilon s\) 会引入一个二阶锥约束，问题变为 二阶锥规划（SOCP） ，也可用内点法求解。 6. 求解过程总结 收集数据 ：获得历史风电出力样本 \(\hat{\xi}_ 1, \dots, \hat{\xi}_ N\)。 选择参数 ：设定风险水平 \(\epsilon\) 和 Wasserstein 球半径 \(\theta\)（后者可通过交叉验证等方法调整）。 建立模型 ：将分布鲁棒机会约束按上述方法转化为一组确定性线性（或二阶锥）约束。 调用求解器 ：使用线性规划（如 GLPK, CPLEX, Gurobi）或二阶锥规划求解器（如 MOSEK, CPLEX, Gurobi）求解最终模型，得到最优决策 \(x^ \) 和对应的安全余量 \(s^ \)。 分析结果 ：\(x^* \) 即为在风电出力分布不确定下，满足鲁棒机会约束的最小成本发电计划。 7. 延伸讨论 Wasserstein 半径 \(\theta\) 的选择 ：\(\theta\) 控制了保守程度。\(\theta=0\) 时，模糊集只包含经验分布，模型退化为传统机会约束规划（样本平均近似）；\(\theta\) 增大，模型更鲁棒，但成本可能更高。可通过样本外交叉验证或渐进理论（如 \(\theta \propto 1/\sqrt{N}\)）来选取。 多约束情形 ：若有多条机会约束，每条可独立转化为上述形式，然后联合求解。 计算优势 ：与传统的场景鲁棒优化（需处理大量场景）相比，Wasserstein 方法通常只需样本个数 \(N\) 的线性规模约束，更易求解。 这种方法将数据驱动的分布不确定性、风险容忍度和鲁棒性统一在一个凸优化框架中，是近年来随机优化领域的重要进展。