基于线性规划的分布式鲁棒优化中Wasserstein模糊集下最坏情况条件风险值（CVaR）优化问题的求解示例
字数 7483 2025-12-18 00:59:11

基于线性规划的分布式鲁棒优化中Wasserstein模糊集下最坏情况条件风险值（CVaR）优化问题的求解示例

1. 问题描述

我们考虑一个在不确定参数下进行决策的问题。传统鲁棒优化假设不确定参数在一个确定性集合（如椭球、多面体）内任意变化，然后优化最坏情况下的性能。然而，这种方法可能过于保守，因为它防范了所有理论上可能的扰动，即便那些概率极低的。分布式鲁棒优化（Distributionally Robust Optimization, DRO）是鲁棒优化和随机规划的折中：它不假设不确定参数的确切分布，而是假设其分布属于一个模糊集（即，一族可能的概率分布）。然后，我们在该模糊集中最坏可能的分布下，优化某个性能指标的期望。

具体模型：

  • 决策变量：\(x \in \mathbb{R}^n\)，表示需要在观察到不确定参数 \(\xi\) 之前做出的“此处即现在”的决策。其可行域为 \(X = \{x: Ax \le b, x \ge 0\}\)。
  • 不确定参数：\(\xi \in \mathbb{R}^m\)，是一个随机向量，其真实概率分布 \(\mathbb{P}\) 未知。
  • 损失函数：\(f(x, \xi)\)，表示在决策 \(x\) 和参数实现 \(\xi\) 下的损失（例如成本、负收益）。
  • 风险度量：我们不简单地优化期望损失，而是采用条件风险值（Conditional Value-at-Risk, CVaR）。在给定置信水平 \(\alpha \in (0,1)\) 下，CVaR度量的是损失分布中超过风险值（VaR）那部分尾部的条件期望。它比VaR具有更好的数学性质（如次可加性、凸性）。
  • 模糊集：我们假设真实分布 \(\mathbb{P}\) 属于一个以某个参考分布 \(\mathbb{P}_0\)（例如经验分布）为中心、以 Wasserstein距离 为半径 \(\epsilon\) 的球。即，模糊集为 \(\mathcal{P} = \{ \mathbb{P} \in \mathcal{M}(\Xi): d_W(\mathbb{P}, \mathbb{P}_0) \le \epsilon \}\)，其中 \(\mathcal{M}(\Xi)\) 是 \(\Xi\) 上所有概率测度的集合，\(d_W\) 是1-Wasserstein距离。Wasserstein距离衡量了两个分布之间的“搬运”成本，能很好地捕捉分布的几何形状，对离散和经验分布尤其适用。
  • 目标：我们在最坏情况的分布（即模糊集 \(\mathcal{P}\) 内）下，最小化损失的CVaR。这构成了一个min-max问题：

\[ \min_{x \in X} \sup_{\mathbb{P} \in \mathcal{P}} \text{CVaR}_{\alpha}^{\mathbb{P}}[f(x, \xi)] \]

其中，\(\text{CVaR}_{\alpha}^{\mathbb{P}}[Z] = \inf_{t \in \mathbb{R}} \left\{ t + \frac{1}{1-\alpha} \mathbb{E}_{\mathbb{P}}[(Z - t)_+] \right\}\)，\((\cdot)_+ = \max(\cdot, 0)\)。

问题的挑战：这是一个两层的优化问题（外层最小化决策 \(x\)，内层最大化分布 \(\mathbb{P}\)），且内层涉及在无限维分布空间上的优化。我们的目标是将它转化为一个可计算的（通常是有限维的）数学规划问题。

2. 模型转化与推导（循序渐进）

步骤1：展开CVaR的表达式
根据CVaR的经典对偶表示，我们的目标函数可以写为：

\[\sup_{\mathbb{P} \in \mathcal{P}} \inf_{t \in \mathbb{R}} \left\{ t + \frac{1}{1-\alpha} \mathbb{E}_{\mathbb{P}}[(f(x, \xi) - t)_+] \right\} \]

这里，\(t\) 是一个辅助变量，与VaR有关。

步骤2：交换 sup 和 inf（应用Minimax定理）
在一定的正则性条件下（例如，损失函数 \(f(x, \cdot)\) 适当连续，模糊集 \(\mathcal{P}\) 紧致），我们可以交换 sup 和 inf 的顺序。这是本问题可处理的关键一步。交换后得到：

\[\inf_{t \in \mathbb{R}} \left\{ t + \frac{1}{1-\alpha} \sup_{\mathbb{P} \in \mathcal{P}} \mathbb{E}_{\mathbb{P}}[(f(x, \xi) - t)_+] \right\} \]

现在，内层问题变为：在模糊集 \(\mathcal{P}\) 中，寻找一个分布 \(\mathbb{P}\)，使得函数 \(h_{x,t}(\xi) = (f(x, \xi) - t)_+\) 的期望最大。

步骤3：处理内层的Wasserstein DRO期望最大化问题
内层问题是：\(\sup_{\mathbb{P}: d_W(\mathbb{P}, \mathbb{P}_0) \le \epsilon} \mathbb{E}_{\mathbb{P}}[h(\xi)]\)，其中 \(h(\xi) = (f(x, \xi) - t)_+\)。这是一个典型的分布鲁棒期望问题。假设参考分布 \(\mathbb{P}_0\) 是离散的，由 \(N\) 个样本点（或称场景）\(\{\hat{\xi}_i\}_{i=1}^{N}\) 及其概率质量 \(p_{0i} = 1/N\)（如果是经验分布）构成。
利用1-Wasserstein距离的对偶表示和强对偶定理，这个无限维的sup问题可以等价地转化为一个有限维的优化问题。具体地，存在一个著名的对偶重构定理，它告诉我们：

\[\sup_{\mathbb{P}: d_W(\mathbb{P}, \mathbb{P}_0) \le \epsilon} \mathbb{E}_{\mathbb{P}}[h(\xi)] = \inf_{\lambda \ge 0} \left\{ \lambda \epsilon + \frac{1}{N} \sum_{i=1}^{N} \sup_{\xi \in \Xi} \left[ h(\xi) - \lambda \|\xi - \hat{\xi}_i\| \right] \right\} \]

其中，\(\lambda\) 是一个对偶变量（可解释为运输成本的“单价”），\(\| \cdot \|\) 是定义Wasserstein距离的范数（常取1-范数或2-范数）。注意，外层关于 \(\lambda\) 是极小化。

步骤4：代入具体函数并整合
将 \(h(\xi) = (f(x, \xi) - t)_+\) 代入上式。注意到内层有一个关于 \(\xi\) 的 sup 运算：\(\sup_{\xi \in \Xi} \left[ (f(x, \xi) - t)_+ - \lambda \|\xi - \hat{\xi}_i\| \right]\)。
为了进一步处理，我们通常需要对函数 \(f(x, \xi)\) 和集合 \(\Xi\) 做一些假设。一个常见且可处理的假设是：\(f(x, \xi)\) 关于 \(\xi\) 是线性的，即 \(f(x, \xi) = c(x)^\top \xi + d(x)\)，并且不确定集 \(\Xi\) 是一个简单的凸集（如多面体、椭球）。这里我们假设 \(f(x, \xi) = \xi^\top x\)（即线性损失），且 \(\Xi = \mathbb{R}^m\)，范数取 \(l_1\)-范数。

那么，对于每个样本点 \(i\)，内层 sup 问题变为：

\[\sup_{\xi \in \mathbb{R}^m} \left[ (\xi^\top x - t)_+ - \lambda \|\xi - \hat{\xi}_i\|_1 \right] \]

这个最大化问题可以进一步分解。引入辅助变量 \(s \ge 0\) 来表示 \((\cdot)_+\)，即 \(s = (\xi^\top x - t)_+\)，等价于 \(s \ge 0, \, s \ge \xi^\top x - t\)。同时，\(l_1\)-范数可以通过引入非负变量分解：\(\|\xi - \hat{\xi}_i\|_1 = \sum_{j=1}^m |\xi_j - \hat{\xi}_{ij}|\)。引入变量 \(u_{ij}^+, u_{ij}^- \ge 0\) 使得 \(\xi_j - \hat{\xi}_{ij} = u_{ij}^+ - u_{ij}^-\)，且 \(|\xi_j - \hat{\xi}_{ij}| = u_{ij}^+ + u_{ij}^-\)。

步骤5：构造最终等价的线性规划
经过上述代换，原 min-max CVaR 问题最终可等价地转化为一个线性规划（如果 \(f(x,\xi)\) 关于 \(x\) 也是线性的，且集合 \(X\) 是多面体）。整合所有步骤，我们得到如下等价问题：

\[\begin{aligned} \min_{x, t, \lambda, s_i, u_{ij}^+, u_{ij}^-} \quad & t + \frac{1}{1-\alpha} \left( \lambda \epsilon + \frac{1}{N} \sum_{i=1}^{N} s_i \right) \\ \text{s.t.} \quad & Ax \le b, \quad x \ge 0, \quad \lambda \ge 0, \\ & s_i \ge 0, \quad \forall i = 1, \dots, N, \\ & s_i \ge \sum_{j=1}^m \hat{\xi}_{ij} x_j + \sum_{j=1}^m (u_{ij}^+ - u_{ij}^-) x_j - t, \quad \forall i, \\ & s_i \ge 0, \quad \forall i, \quad (\text{但通常由上一条约束隐含要求 } s_i \ge \cdot, \text{ 所以此条可省}) \\ & u_{ij}^+, u_{ij}^- \ge 0, \quad \forall i, j, \\ & \text{并且，我们必须将 } \xi_j \text{ 用 } \hat{\xi}_{ij} + u_{ij}^+ - u_{ij}^- \text{ 代入，而约束中的 } \sum_j \xi_j x_j = \sum_j \hat{\xi}_{ij} x_j + \sum_j (u_{ij}^+ - u_{ij}^-) x_j. \\ & \text{（注意：这里 } \xi_j \text{ 本身不再是变量，已被 } u_{ij}^+, u_{ij}^- \text{ 表示。）} \end{aligned} \]

但上面的形式还不是线性规划，因为约束 \(s_i \ge \sum_j (u_{ij}^+ - u_{ij}^-) x_j\) 中含有变量乘积 \(u_{ij}^+ x_j\) 和 \(u_{ij}^- x_j\)。这是双线性项。为了线性化，我们需要利用对偶性再次转换。

实际上，更标准的处理方式是：对于每个 \(i\)，内层 sup 问题 \(\sup_{\xi} [(\xi^\top x - t)_+ - \lambda \|\xi - \hat{\xi}_i\|_1]\) 本身是一个凸优化问题（在给定 \(x, t, \lambda\) 下）。我们可以写出它的对偶问题，而这个对偶问题关于 \(x, t, \lambda\) 是线性的。经过一系列推导（利用线性规划对偶或锥对偶），最终可得到如下形式的线性规划：

\[\begin{aligned} \min \quad & t + \frac{1}{1-\alpha} \left( \lambda \epsilon + \frac{1}{N} \sum_{i=1}^{N} p_i \right) \\ \text{s.t.} \quad & Ax \le b, \quad x \ge 0, \quad \lambda \ge 0, \\ & p_i \ge \hat{\xi}_i^\top x - t - \lambda \theta_i, \quad \forall i, \\ & p_i \ge 0, \quad \forall i, \\ & -z_{ij} \le x_j \le z_{ij}, \quad \forall i, j, \quad (\text{或等价地 } |x_j| \le z_{ij}) \\ & \sum_{j=1}^m z_{ij} \le \theta_i, \quad \forall i, \\ & \theta_i \ge 0, \quad \forall i. \end{aligned} \]

这里引入了新的变量 \(p_i, \theta_i, z_{ij}\)。\(p_i\) 等价于从对偶中产生的、与 \(s_i\) 相关的变量。约束 \(-z_{ij} \le x_j \le z_{ij}\) 和 \(\sum_j z_{ij} \le \theta_i\) 共同等价于 \(\|x\|_\infty \le \theta_i\) 的表示（因为我们使用了 \(l_1\) 范数作为成本，对偶中会出现 \(l_\infty\) 约束）。\(\theta_i\) 是辅助变量，用于表示每个样本 \(i\) 对应的“对偶范数”约束。

注意：上述线性规划的精确形式依赖于 \(f(x,\xi)\) 的具体形式和所选范数。不同的假设会导致不同的最终约束。但其核心思想是：通过Wasserstein DRO的对偶理论，将内层的无穷维分布鲁棒期望最大化问题，转化为一个涉及对偶变量 \(\lambda\) 和一系列线性约束的有限维优化问题，从而将原 min-max CVaR 问题整体转化为一个线性规划（或更一般的凸优化）问题。

3. 求解步骤概要

给定上述线性规划模型后，我们可以用标准线性规划求解器（如单纯形法、内点法）直接求解。具体步骤如下：

  1. 输入：置信水平 \(\alpha\)，Wasserstein半径 \(\epsilon\)，参考分布（经验样本）\(\{\hat{\xi}_i\}_{i=1}^{N}\)，可行域 \(X\) 的约束 \(A, b\)，范数类型（如 \(l_1\)）。
  2. 建立线性规划模型：根据推导出的最终等价线性规划，定义所有决策变量：\(x, t, \lambda, p_i, \theta_i, z_{ij}\)。
  3. 设置目标函数：\(\min \, t + \frac{1}{1-\alpha}(\lambda \epsilon + \frac{1}{N}\sum_i p_i)\)。
  4. 添加约束：
    • 原决策约束：\(Ax \le b, x \ge 0\)。
    • 对偶约束：\(p_i \ge \hat{\xi}_i^\top x - t - \lambda \theta_i, \, \forall i\)。
    • 非负约束：\(p_i \ge 0, \lambda \ge 0, \theta_i \ge 0, \forall i\)。
    • 范数相关约束：\(-z_{ij} \le x_j \le z_{ij}, \, \sum_j z_{ij} \le \theta_i, \, \forall i, j\)。
  5. 求解线性规划：使用求解器得到最优解 \(x^*\)。
  6. 输出：最优决策 \(x^*\)，以及对应的最坏情况CVaR值（目标函数值）。

4. 核心思想与意义

  • 分布鲁棒性：我们并不假定不确定参数遵循一个已知的分布，而是承认分布本身存在不确定性（模糊性），并用一个Wasserstein球来描述这种模糊性。这比传统随机规划（假设确切分布）更稳健，又比经典鲁棒优化（盒式不确定集）更少保守，因为它利用了分布的几何和样本数据。
  • 风险厌恶：采用CVaR作为风险度量，直接优化尾部风险的平均值，这对金融、能源、医疗等高风险领域尤为重要。
  • 可计算性：尽管原问题复杂，但在损失函数关于不确定参数为线性、且采用1-Wasserstein距离时，可以精确重构为一个线性规划，计算上可行。
  • 数据驱动：参考分布 \(\mathbb{P}_0\) 通常取为经验分布，因此模型完全由数据驱动。半径 \(\epsilon\) 控制了模型的保守程度：\(\epsilon=0\) 退化为经典样本平均近似（SAA）；\(\epsilon \to \infty\) 则趋近于最坏情况鲁棒优化。
基于线性规划的分布式鲁棒优化中Wasserstein模糊集下最坏情况条件风险值（CVaR）优化问题的求解示例 1. 问题描述 我们考虑一个在不确定参数下进行决策的问题。传统鲁棒优化假设不确定参数在一个确定性集合（如椭球、多面体）内任意变化，然后优化最坏情况下的性能。然而，这种方法可能过于保守，因为它防范了所有理论上可能的扰动，即便那些概率极低的。 分布式鲁棒优化 （Distributionally Robust Optimization, DRO）是鲁棒优化和随机规划的折中：它不假设不确定参数的确切分布，而是假设其分布属于一个 模糊集 （即，一族可能的概率分布）。然后，我们在该模糊集中最坏可能的分布下，优化某个性能指标的期望。 具体模型 ： 决策变量 ：\( x \in \mathbb{R}^n \)，表示需要在观察到不确定参数 \( \xi \) 之前做出的“此处即现在”的决策。其可行域为 \( X = \{x: Ax \le b, x \ge 0\} \)。 不确定参数 ：\( \xi \in \mathbb{R}^m \)，是一个随机向量，其真实概率分布 \( \mathbb{P} \) 未知。 损失函数 ：\( f(x, \xi) \)，表示在决策 \( x \) 和参数实现 \( \xi \) 下的损失（例如成本、负收益）。 风险度量 ：我们不简单地优化期望损失，而是采用 条件风险值 （Conditional Value-at-Risk, CVaR ）。在给定置信水平 \( \alpha \in (0,1) \) 下，CVaR度量的是损失分布中超过风险值（VaR）那部分尾部的条件期望。它比VaR具有更好的数学性质（如次可加性、凸性）。 模糊集 ：我们假设真实分布 \( \mathbb{P} \) 属于一个以某个参考分布 \( \mathbb{P}_ 0 \)（例如经验分布）为中心、以 Wasserstein距离 为半径 \( \epsilon \) 的球。即，模糊集为 \( \mathcal{P} = \{ \mathbb{P} \in \mathcal{M}(\Xi): d_ W(\mathbb{P}, \mathbb{P}_ 0) \le \epsilon \} \)，其中 \( \mathcal{M}(\Xi) \) 是 \( \Xi \) 上所有概率测度的集合，\( d_ W \) 是1-Wasserstein距离。Wasserstein距离衡量了两个分布之间的“搬运”成本，能很好地捕捉分布的几何形状，对离散和经验分布尤其适用。 目标 ：我们在最坏情况的分布（即模糊集 \( \mathcal{P} \) 内）下，最小化损失的CVaR。这构成了一个 min-max 问题： \[ \min_ {x \in X} \sup_ {\mathbb{P} \in \mathcal{P}} \text{CVaR} {\alpha}^{\mathbb{P}}[ f(x, \xi) ] \] 其中，\( \text{CVaR} {\alpha}^{\mathbb{P}}[ Z] = \inf_ {t \in \mathbb{R}} \left\{ t + \frac{1}{1-\alpha} \mathbb{E} {\mathbb{P}}[ (Z - t) +] \right\} \)，\( (\cdot)_ + = \max(\cdot, 0) \)。 问题的挑战 ：这是一个两层的优化问题（外层最小化决策 \( x \)，内层最大化分布 \( \mathbb{P} \)），且内层涉及在无限维分布空间上的优化。我们的目标是将它转化为一个可计算的（通常是有限维的）数学规划问题。 2. 模型转化与推导（循序渐进） 步骤1：展开CVaR的表达式 根据CVaR的经典对偶表示，我们的目标函数可以写为： \[ \sup_ {\mathbb{P} \in \mathcal{P}} \inf_ {t \in \mathbb{R}} \left\{ t + \frac{1}{1-\alpha} \mathbb{E} {\mathbb{P}}[ (f(x, \xi) - t) + ] \right\} \] 这里，\( t \) 是一个辅助变量，与VaR有关。 步骤2：交换 sup 和 inf（应用Minimax定理） 在一定的正则性条件下（例如，损失函数 \( f(x, \cdot) \) 适当连续，模糊集 \( \mathcal{P} \) 紧致），我们可以交换 sup 和 inf 的顺序。这是本问题可处理的关键一步。交换后得到： \[ \inf_ {t \in \mathbb{R}} \left\{ t + \frac{1}{1-\alpha} \sup_ {\mathbb{P} \in \mathcal{P}} \mathbb{E} {\mathbb{P}}[ (f(x, \xi) - t) + ] \right\} \] 现在，内层问题变为：在模糊集 \( \mathcal{P} \) 中，寻找一个分布 \( \mathbb{P} \)，使得函数 \( h_ {x,t}(\xi) = (f(x, \xi) - t)_ + \) 的期望最大。 步骤3：处理内层的Wasserstein DRO期望最大化问题 内层问题是：\( \sup_ {\mathbb{P}: d_ W(\mathbb{P}, \mathbb{P} 0) \le \epsilon} \mathbb{E} {\mathbb{P}}[ h(\xi)] \)，其中 \( h(\xi) = (f(x, \xi) - t) + \)。这是一个典型的分布鲁棒期望问题。假设参考分布 \( \mathbb{P} 0 \) 是离散的，由 \( N \) 个样本点（或称场景）\( \{\hat{\xi} i\} {i=1}^{N} \) 及其概率质量 \( p {0i} = 1/N \)（如果是经验分布）构成。 利用1-Wasserstein距离的对偶表示和强对偶定理，这个无限维的sup问题可以等价地转化为一个有限维的优化问题。具体地，存在一个著名的 对偶重构定理 ，它告诉我们： \[ \sup {\mathbb{P}: d_ W(\mathbb{P}, \mathbb{P} 0) \le \epsilon} \mathbb{E} {\mathbb{P}}[ h(\xi)] = \inf_ {\lambda \ge 0} \left\{ \lambda \epsilon + \frac{1}{N} \sum_ {i=1}^{N} \sup_ {\xi \in \Xi} \left[ h(\xi) - \lambda \|\xi - \hat{\xi}_ i\| \right ] \right\} \] 其中，\( \lambda \) 是一个对偶变量（可解释为运输成本的“单价”），\( \| \cdot \| \) 是定义Wasserstein距离的范数（常取1-范数或2-范数）。注意，外层关于 \( \lambda \) 是 极小化 。 步骤4：代入具体函数并整合 将 \( h(\xi) = (f(x, \xi) - t) + \) 代入上式。注意到内层有一个关于 \( \xi \) 的 sup 运算：\( \sup {\xi \in \Xi} \left[ (f(x, \xi) - t)_ + - \lambda \|\xi - \hat{\xi}_ i\| \right ] \)。 为了进一步处理，我们通常需要对函数 \( f(x, \xi) \) 和集合 \( \Xi \) 做一些假设。一个常见且可处理的假设是： \( f(x, \xi) \) 关于 \( \xi \) 是线性的 ，即 \( f(x, \xi) = c(x)^\top \xi + d(x) \)，并且不确定集 \( \Xi \) 是一个简单的凸集（如多面体、椭球）。这里我们假设 \( f(x, \xi) = \xi^\top x \)（即线性损失），且 \( \Xi = \mathbb{R}^m \)，范数取 \( l_ 1 \)-范数。 那么，对于每个样本点 \( i \)，内层 sup 问题变为： \[ \sup_ {\xi \in \mathbb{R}^m} \left[ (\xi^\top x - t) + - \lambda \|\xi - \hat{\xi} i\| 1 \right ] \] 这个最大化问题可以进一步分解。引入辅助变量 \( s \ge 0 \) 来表示 \( (\cdot) + \)，即 \( s = (\xi^\top x - t) + \)，等价于 \( s \ge 0, \, s \ge \xi^\top x - t \)。同时，\( l_ 1 \)-范数可以通过引入非负变量分解：\( \|\xi - \hat{\xi} i\| 1 = \sum {j=1}^m |\xi_ j - \hat{\xi} {ij}| \)。引入变量 \( u {ij}^+, u_ {ij}^- \ge 0 \) 使得 \( \xi_ j - \hat{\xi} {ij} = u {ij}^+ - u_ {ij}^- \)，且 \( |\xi_ j - \hat{\xi} {ij}| = u {ij}^+ + u_ {ij}^- \)。 步骤5：构造最终等价的线性规划 经过上述代换，原 min-max CVaR 问题最终可等价地转化为一个 线性规划 （如果 \( f(x,\xi) \) 关于 \( x \) 也是线性的，且集合 \( X \) 是多面体）。整合所有步骤，我们得到如下等价问题： \[ \begin{aligned} \min_ {x, t, \lambda, s_ i, u_ {ij}^+, u_ {ij}^-} \quad & t + \frac{1}{1-\alpha} \left( \lambda \epsilon + \frac{1}{N} \sum_ {i=1}^{N} s_ i \right) \\ \text{s.t.} \quad & Ax \le b, \quad x \ge 0, \quad \lambda \ge 0, \\ & s_ i \ge 0, \quad \forall i = 1, \dots, N, \\ & s_ i \ge \sum_ {j=1}^m \hat{\xi} {ij} x_ j + \sum {j=1}^m (u_ {ij}^+ - u_ {ij}^-) x_ j - t, \quad \forall i, \\ & s_ i \ge 0, \quad \forall i, \quad (\text{但通常由上一条约束隐含要求 } s_ i \ge \cdot, \text{ 所以此条可省}) \\ & u_ {ij}^+, u_ {ij}^- \ge 0, \quad \forall i, j, \\ & \text{并且，我们必须将 } \xi_ j \text{ 用 } \hat{\xi} {ij} + u {ij}^+ - u_ {ij}^- \text{ 代入，而约束中的 } \sum_ j \xi_ j x_ j = \sum_ j \hat{\xi} {ij} x_ j + \sum_ j (u {ij}^+ - u_ {ij}^-) x_ j. \\ & \text{（注意：这里 } \xi_ j \text{ 本身不再是变量，已被 } u_ {ij}^+, u_ {ij}^- \text{ 表示。）} \end{aligned} \] 但上面的形式还不是线性规划，因为约束 \( s_ i \ge \sum_ j (u_ {ij}^+ - u_ {ij}^-) x_ j \) 中含有变量乘积 \( u_ {ij}^+ x_ j \) 和 \( u_ {ij}^- x_ j \)。这是双线性项。为了线性化，我们需要利用 对偶性 再次转换。 实际上，更标准的处理方式是：对于每个 \( i \)，内层 sup 问题 \( \sup_ {\xi} [ (\xi^\top x - t)_ + - \lambda \|\xi - \hat{\xi}_ i\|_ 1] \) 本身是一个凸优化问题（在给定 \( x, t, \lambda \) 下）。我们可以写出它的 对偶问题 ，而这个对偶问题关于 \( x, t, \lambda \) 是线性的。经过一系列推导（利用线性规划对偶或锥对偶），最终可得到如下形式的线性规划： \[ \begin{aligned} \min \quad & t + \frac{1}{1-\alpha} \left( \lambda \epsilon + \frac{1}{N} \sum_ {i=1}^{N} p_ i \right) \\ \text{s.t.} \quad & Ax \le b, \quad x \ge 0, \quad \lambda \ge 0, \\ & p_ i \ge \hat{\xi} i^\top x - t - \lambda \theta_ i, \quad \forall i, \\ & p_ i \ge 0, \quad \forall i, \\ & -z {ij} \le x_ j \le z_ {ij}, \quad \forall i, j, \quad (\text{或等价地 } |x_ j| \le z_ {ij}) \\ & \sum_ {j=1}^m z_ {ij} \le \theta_ i, \quad \forall i, \\ & \theta_ i \ge 0, \quad \forall i. \end{aligned} \] 这里引入了新的变量 \( p_ i, \theta_ i, z_ {ij} \)。\( p_ i \) 等价于从对偶中产生的、与 \( s_ i \) 相关的变量。约束 \( -z_ {ij} \le x_ j \le z_ {ij} \) 和 \( \sum_ j z_ {ij} \le \theta_ i \) 共同等价于 \( \|x\| \infty \le \theta_ i \) 的表示（因为我们使用了 \( l_ 1 \) 范数作为成本，对偶中会出现 \( l \infty \) 约束）。\( \theta_ i \) 是辅助变量，用于表示每个样本 \( i \) 对应的“对偶范数”约束。 注意 ：上述线性规划的精确形式依赖于 \( f(x,\xi) \) 的具体形式和所选范数。不同的假设会导致不同的最终约束。但其核心思想是： 通过Wasserstein DRO的对偶理论，将内层的无穷维分布鲁棒期望最大化问题，转化为一个涉及对偶变量 \( \lambda \) 和一系列线性约束的有限维优化问题，从而将原 min-max CVaR 问题整体转化为一个线性规划（或更一般的凸优化）问题。 3. 求解步骤概要 给定上述线性规划模型后，我们可以用标准线性规划求解器（如单纯形法、内点法）直接求解。具体步骤如下： 输入 ：置信水平 \( \alpha \)，Wasserstein半径 \( \epsilon \)，参考分布（经验样本）\( \{\hat{\xi} i\} {i=1}^{N} \)，可行域 \( X \) 的约束 \( A, b \)，范数类型（如 \( l_ 1 \)）。 建立线性规划模型 ：根据推导出的最终等价线性规划，定义所有决策变量：\( x, t, \lambda, p_ i, \theta_ i, z_ {ij} \)。 设置目标函数 ：\( \min \, t + \frac{1}{1-\alpha}(\lambda \epsilon + \frac{1}{N}\sum_ i p_ i) \)。 添加约束 ： 原决策约束：\( Ax \le b, x \ge 0 \)。 对偶约束：\( p_ i \ge \hat{\xi}_ i^\top x - t - \lambda \theta_ i, \, \forall i \)。 非负约束：\( p_ i \ge 0, \lambda \ge 0, \theta_ i \ge 0, \forall i \)。 范数相关约束：\( -z_ {ij} \le x_ j \le z_ {ij}, \, \sum_ j z_ {ij} \le \theta_ i, \, \forall i, j \)。 求解线性规划 ：使用求解器得到最优解 \( x^* \)。 输出 ：最优决策 \( x^* \)，以及对应的最坏情况CVaR值（目标函数值）。 4. 核心思想与意义 分布鲁棒性 ：我们并不假定不确定参数遵循一个已知的分布，而是承认分布本身存在不确定性（模糊性），并用一个Wasserstein球来描述这种模糊性。这比传统随机规划（假设确切分布）更稳健，又比经典鲁棒优化（盒式不确定集）更少保守，因为它利用了分布的几何和样本数据。 风险厌恶 ：采用CVaR作为风险度量，直接优化尾部风险的平均值，这对金融、能源、医疗等高风险领域尤为重要。 可计算性 ：尽管原问题复杂，但在损失函数关于不确定参数为线性、且采用1-Wasserstein距离时，可以精确重构为一个线性规划，计算上可行。 数据驱动 ：参考分布 \( \mathbb{P}_ 0 \) 通常取为经验分布，因此模型完全由数据驱动。半径 \( \epsilon \) 控制了模型的保守程度：\( \epsilon=0 \) 退化为经典样本平均近似（SAA）；\( \epsilon \to \infty \) 则趋近于最坏情况鲁棒优化。