基于线性规划的分布式鲁棒优化中矩不确定集下最坏情况期望优化问题的求解示例

字数 7306 2025-12-14 10:21:26

基于线性规划的分布式鲁棒优化中矩不确定集下最坏情况期望优化问题的求解示例

1. 题目描述

本题目将探讨分布式鲁棒优化（Distributionally Robust Optimization, DRO）中的一个经典模型：在矩不确定集下，求解最坏情况期望优化问题。具体来说，我们考虑一个单阶段随机线性规划问题，其部分参数（如成本系数、资源需求）是随机的，但其精确概率分布未知。我们仅知该随机变量的部分矩信息（如期望、协方差）。决策者希望在所有与已知矩信息一致的分布中，最小化最坏情况下的期望成本。我们将展示如何将此问题转化为一个可求解的线性规划模型。

2. 背景与问题形式化

2.1 标准随机线性规划
假设我们有一个随机线性规划问题：
最小化 \(c^T x + \mathbb{E}_{\xi} [Q(x, \xi)]\)
满足 \(Ax \leq b, x \geq 0\)。
其中：

\(x \in \mathbb{R}^n\) 是第一阶段决策变量。
\(c \in \mathbb{R}^n\) 是已知的第一阶段成本。
\(A \in \mathbb{R}^{m \times n}, b \in \mathbb{R}^m\) 是确定性的约束矩阵与右端项。
\(\xi \in \mathbb{R}^d\) 是一个随机向量，代表不确定性。
\(Q(x, \xi) = \min_{y} \{ q^T y : W y \geq h - T x, y \geq 0 \}\) 是第二阶段的补偿成本，其中 \(q, W, h, T\) 是已知的，但 \(h\) 和/或 \(T\) 可能依赖于 \(\xi\)。为简化，我们假设第二阶段问题是可行且有界的（相对完备 recourse）。

2.2 分布式鲁棒优化视角
在DRO中，我们不假设 \(\xi\) 的精确分布 \(\mathbb{P}\) 已知。相反，我们只知 \(\xi\) 属于某个分布族 \(\mathcal{P}\)，该族由部分矩信息定义。我们考虑矩不确定集：

\[\mathcal{P} = \{ \mathbb{P} \in \mathcal{M}_+ : \mathbb{E}_{\mathbb{P}}[\xi] = \mu, \mathbb{E}_{\mathbb{P}}[(\xi - \mu)(\xi - \mu)^T] \preceq \Sigma \} \]

其中：

\(\mathcal{M}_+\) 是所有概率分布的集合。
\(\mu \in \mathbb{R}^d\) 是已知的期望向量。
\(\Sigma \in \mathbb{R}^{d \times d}\) 是已知的正定矩阵，作为协方差矩阵的上界（在Loewner序意义下，即 \(\mathbb{E}[(\xi - \mu)(\xi - \mu)^T] \preceq \Sigma\) 表示 \(\Sigma - \mathbb{E}[(\xi - \mu)(\xi - \mu)^T]\) 是半正定矩阵）。
符号 \(\preceq\) 表示矩阵的半正定序。

我们的目标是：

\[\min_{x} \left\{ c^T x + \sup_{\mathbb{P} \in \mathcal{P}} \mathbb{E}_{\mathbb{P}}[Q(x, \xi)] : Ax \leq b, x \geq 0 \right\} \]

即，在第一阶段决策 \(x\) 时，考虑最坏情况下（在分布族 \(\mathcal{P}\) 中）的期望第二阶段成本。

2.3 简化假设
为突出核心转化步骤，我们假设：

随机性只出现在第二阶段成本向量 \(q\) 中，即 \(q = \xi\)，且 \(\xi \in \mathbb{R}^m\) 是随机成本向量。则 \(Q(x, \xi) = \min_{y} \{ \xi^T y : W y \geq h - T x, y \geq 0 \}\)。
我们已知 \(\mathbb{E}[\xi] = \mu\) 和 \(\text{Cov}(\xi) \preceq \Sigma\)。这里 \(\Sigma\) 是给定的正定矩阵，协方差矩阵的上界。

3. 将DRO问题转化为线性规划

3.1 利用对偶理论处理内层 sup 问题
内层问题为：对给定的 \(x\)（从而给定第二阶段可行域 \(Y(x) = \{ y \geq 0 : W y \geq h - T x \}\)），求

\[\sup_{\mathbb{P} \in \mathcal{P}} \mathbb{E}_{\mathbb{P}} \left[ \min_{y \in Y(x)} \xi^T y \right] \]

由于内层是 \(\min\)，外层是 \(\sup\)，直接处理困难。一个关键技巧是：对于任何 \(y \in Y(x)\)，有 \(\min_{y \in Y(x)} \xi^T y \leq \xi^T y\)。因此，对任意分布 \(\mathbb{P}\)，有

\[\mathbb{E}_{\mathbb{P}} \left[ \min_{y \in Y(x)} \xi^T y \right] \leq \mathbb{E}_{\mathbb{P}} [\xi^T y] = \mu^T y + \mathbb{E}_{\mathbb{P}}[(\xi - \mu)^T y] \]

由于 \(\mathbb{E}_{\mathbb{P}}[(\xi - \mu)^T y] = 0\)，所以上界为 \(\mu^T y\)。但我们要的是最坏情况期望，需要更精确的刻画。

3.2 利用鲁棒优化与矩问题的对偶
可以证明（通过测度理论中的矩问题对偶，或S-引理类方法），在最坏分布下，期望值可以表示为：

\[\sup_{\mathbb{P} \in \mathcal{P}} \mathbb{E}_{\mathbb{P}}[\min_{y \in Y(x)} \xi^T y] = \min_{y \in Y(x)} \sup_{\mathbb{P} \in \mathcal{P}} \mathbb{E}_{\mathbb{P}}[\xi^T y] \]

在适当的凸性假设下，上述“min”和“sup”可交换。现在内层是：

\[\sup_{\mathbb{P} \in \mathcal{P}} \mathbb{E}_{\mathbb{P}}[\xi^T y] = \sup_{\mathbb{P} \in \mathcal{P}} \mathbb{E}_{\mathbb{P}}[\xi]^T y = \mu^T y + \sup_{\mathbb{P} \in \mathcal{P}} \mathbb{E}_{\mathbb{P}}[(\xi - \mu)^T y] \]

由于 \(\mathbb{E}[\xi] = \mu\) 固定，只需处理第二项。而

\[\sup_{\mathbb{P} \in \mathcal{P}} \mathbb{E}_{\mathbb{P}}[(\xi - \mu)^T y] = \sup_{\mathbb{P} \in \mathcal{P}} \mathbb{E}_{\mathbb{P}}[z^T y] \quad \text{其中 } z = \xi - \mu \]

且 \(\mathbb{E}[z] = 0, \mathbb{E}[zz^T] \preceq \Sigma\)。这是矩问题：在满足一阶矩为0、二阶矩有上界 \(\Sigma\) 的所有分布中，最大化 \(\mathbb{E}[z^T y]\)。其最优值等于（通过半定规划对偶）：

\[\inf_{P \succeq 0, \lambda} \left\{ \text{trace}(\Sigma P) : \begin{bmatrix} P & y/2 \\ y^T/2 & \lambda \end{bmatrix} \succeq 0 \right\} \]

其中 \(P\) 是对偶变量矩阵，\(\lambda\) 是标量。进一步化简可得，最优值等于 \(\sqrt{y^T \Sigma y}\)。即，

\[\sup_{\mathbb{P} \in \mathcal{P}} \mathbb{E}_{\mathbb{P}}[(\xi - \mu)^T y] = \sqrt{y^T \Sigma y} \]

（这可以理解为：最坏分布将质量集中在使 \(z^T y\) 最大的方向上，受二阶矩约束，最大值就是 \(y\) 方向的“标准差”尺度）。

3.3 化简后的问题
因此，内层 sup 问题变为：

\[\sup_{\mathbb{P} \in \mathcal{P}} \mathbb{E}_{\mathbb{P}}[\xi^T y] = \mu^T y + \sqrt{y^T \Sigma y} \]

于是原DRO目标成为：

\[\min_{x, y} \left\{ c^T x + \mu^T y + \sqrt{y^T \Sigma y} : Ax \leq b, x \geq 0, W y \geq h - T x, y \geq 0 \right\} \]

注意这里 \(y\) 是第二阶段决策变量，与随机性无关（因为我们在最坏分布下优化）。

3.4 转化为线性规划
目标中的 \(\sqrt{y^T \Sigma y}\) 是凸函数，但非线性。我们可以通过引入辅助变量 \(t\) 将其线性化：

\[\min_{x, y, t} \left\{ c^T x + \mu^T y + t : Ax \leq b, x \geq 0, W y \geq h - T x, y \geq 0, \sqrt{y^T \Sigma y} \leq t \right\} \]

约束 \(\sqrt{y^T \Sigma y} \leq t\) 等价于二阶锥约束 \(\| \Sigma^{1/2} y \|_2 \leq t\)，其中 \(\Sigma^{1/2}\) 是 \(\Sigma\) 的对称平方根矩阵。这本身是二阶锥规划（SOCP），但我们可以进一步利用线性规划近似，或通过以下技巧转化为线性规划（当维度低或特殊结构时）：

如果 \(\Sigma\) 是对角矩阵（即随机变量各分量不相关，但方差有界），设 \(\Sigma = \text{diag}(\sigma_1^2, \dots, \sigma_m^2)\)，则

\[\sqrt{y^T \Sigma y} = \sqrt{\sum_{j=1}^m \sigma_j^2 y_j^2} = \| (\sigma_1 y_1, \dots, \sigma_m y_m) \|_2 \]

约束 \(\| (\sigma_1 y_1, \dots, \sigma_m y_m) \|_2 \leq t\) 可以用一系列线性约束近似（如多面体范数逼近），或者，如果我们允许保守近似，可以利用范数不等式：

\[\| (\sigma_1 y_1, \dots, \sigma_m y_m) \|_2 \leq \sum_{j=1}^m \sigma_j |y_j| \]

由于 \(y_j \geq 0\)，有 \(|y_j| = y_j\)。所以 \(\sqrt{y^T \Sigma y} \leq \sum_{j=1}^m \sigma_j y_j\)。这样，我们可以用线性上界替代，得到：

\[\min_{x, y} \left\{ c^T x + \mu^T y + \sum_{j=1}^m \sigma_j y_j : Ax \leq b, x \geq 0, W y \geq h - T x, y \geq 0 \right\} \]

这就是一个线性规划！虽然它比原问题保守（因为用了上界），但计算简便，且在某些应用中可接受。

3.5 精确的线性规划重构（通过对偶）
另一种方法是回到内层 sup 问题的对偶形式。可以证明，原DRO问题等价于：

\[\min_{x, y, M} \left\{ c^T x + \mu^T y + \text{trace}(\Sigma M) : Ax \leq b, x \geq 0, W y \geq h - T x, y \geq 0, M \succeq 0, M - y y^T \succeq 0 \right\} \]

其中 \(M\) 是一个对称矩阵变量。约束 \(M - y y^T \succeq 0\) 可以写为线性矩阵不等式（LMI），这导致一个半定规划（SDP），而不是线性规划。但如果我们用 Schur 补，可以引入新变量，但仍然是 SDP。因此，要得到精确的线性规划，通常需要假设随机向量 \(\xi\) 的支撑集是有限个场景（离散分布），这时矩不确定集下的 DRO 可以转化为线性规划。但本示例中，我们假设连续矩信息，并采用上述线性上界近似，从而得到线性规划。

4. 解题步骤总结

问题建模：识别随机参数、决策阶段、目标与约束，定义矩不确定集 \(\mathcal{P}\)。
内层最坏期望转化：利用矩问题对偶，将内层 sup 问题转化为关于决策变量 \(y\) 的确定性表达式 \(\mu^T y + \sqrt{y^T \Sigma y}\)。
线性化近似：将非线性项 \(\sqrt{y^T \Sigma y}\) 用线性上界 \(\sum \sigma_j y_j\) 替代（在 \(\Sigma\) 对角且 \(y \geq 0\) 条件下）。
整合为线性规划：将目标与约束全部写为线性形式，得到最终的线性规划模型。
求解与后分析：用单纯形法或内点法求解该线性规划，得到第一阶段决策 \(x^*\) 和第二阶段决策 \(y^*\)。分析解的鲁棒性。

5. 一个简单数值示例

假设：

第一阶段：\(n=1, c=1, A=1, b=10\)，即 \(x \leq 10, x \geq 0\)。
第二阶段：\(m=2\)，随机成本 \(\xi = (\xi_1, \xi_2)\)，期望 \(\mu = (2, 3)\)，协方差上界矩阵 \(\Sigma = \begin{bmatrix} 4 & 0 \\ 0 & 9 \end{bmatrix}\)（即标准差 \(\sigma_1=2, \sigma_2=3\)）。
第二阶段的约束：\(W = I_2\), \(h = (5, 4)^T\), \(T = (1, 1)^T\)，即

\[ y_1 \geq 5 - x, \quad y_2 \geq 4 - x, \quad y_1, y_2 \geq 0 \]

线性规划模型（采用线性上界近似）：
目标：最小化 \(1 \cdot x + 2 y_1 + 3 y_2 + 2 y_1 + 3 y_2 = x + 4 y_1 + 6 y_2\)
约束：

\(x \leq 10, x \geq 0\)
\(y_1 \geq 5 - x, y_2 \geq 4 - x\)
\(y_1, y_2 \geq 0\)

由于 \(y_1, y_2\) 出现在目标中带正系数，在约束下应取最小值，即 \(y_1 = \max(0, 5-x)\), \(y_2 = \max(0, 4-x)\)。分区间讨论：

若 \(x \geq 5\)，则 \(y_1=0, y_2=0\)，目标 = \(x\)，最优在 \(x=5\) 得 5。
若 \(4 \leq x < 5\)，则 \(y_1=5-x, y_2=0\)，目标 = \(x + 4(5-x) = 20 - 3x\)，在 \(x=5\) 得 5（边界）。
若 \(x < 4\)，则 \(y_1=5-x, y_2=4-x\)，目标 = \(x + 4(5-x) + 6(4-x) = x + 20-4x + 24-6x = 44 - 9x\)，在 \(x=4\) 得 8。
比较得全局最优解：\(x^* = 5, y_1^* = 0, y_2^* = 0\)，最优值 = 5。

6. 关键点说明

矩不确定集 DRO 通过最坏情况期望，平衡了优化与不确定性。
在特殊结构下（对角协方差、非负决策），可近似为线性规划，计算高效。
更一般情况需用二阶锥规划或半定规划，但线性近似提供了一个保守但简单的可行方案。

这个示例展示了如何将复杂的分布式鲁棒优化问题，在矩信息下，转化为可计算的线性规划，从而为决策提供鲁棒方案。

基于线性规划的分布式鲁棒优化中矩不确定集下最坏情况期望优化问题的求解示例 1. 题目描述本题目将探讨分布式鲁棒优化（Distributionally Robust Optimization, DRO）中的一个经典模型：在矩不确定集下，求解最坏情况期望优化问题。具体来说，我们考虑一个单阶段随机线性规划问题，其部分参数（如成本系数、资源需求）是随机的，但其精确概率分布未知。我们仅知该随机变量的部分矩信息（如期望、协方差）。决策者希望在所有与已知矩信息一致的分布中，最小化最坏情况下的期望成本。我们将展示如何将此问题转化为一个可求解的线性规划模型。 2. 背景与问题形式化 2.1 标准随机线性规划假设我们有一个随机线性规划问题：最小化 \( c^T x + \mathbb{E}_ {\xi} [ Q(x, \xi) ] \) 满足 \( Ax \leq b, x \geq 0 \)。其中： \( x \in \mathbb{R}^n \) 是第一阶段决策变量。 \( c \in \mathbb{R}^n \) 是已知的第一阶段成本。 \( A \in \mathbb{R}^{m \times n}, b \in \mathbb{R}^m \) 是确定性的约束矩阵与右端项。 \( \xi \in \mathbb{R}^d \) 是一个随机向量，代表不确定性。 \( Q(x, \xi) = \min_ {y} \{ q^T y : W y \geq h - T x, y \geq 0 \} \) 是第二阶段的补偿成本，其中 \( q, W, h, T \) 是已知的，但 \( h \) 和/或 \( T \) 可能依赖于 \( \xi \)。为简化，我们假设第二阶段问题是可行且有界的（相对完备 recourse）。 2.2 分布式鲁棒优化视角在DRO中，我们不假设 \( \xi \) 的精确分布 \( \mathbb{P} \) 已知。相反，我们只知 \( \xi \) 属于某个分布族 \( \mathcal{P} \)，该族由部分矩信息定义。我们考虑矩不确定集： \[ \mathcal{P} = \{ \mathbb{P} \in \mathcal{M} + : \mathbb{E} {\mathbb{P}}[ \xi] = \mu, \mathbb{E}_ {\mathbb{P}}[ (\xi - \mu)(\xi - \mu)^T ] \preceq \Sigma \} \] 其中： \( \mathcal{M}_ + \) 是所有概率分布的集合。 \( \mu \in \mathbb{R}^d \) 是已知的期望向量。 \( \Sigma \in \mathbb{R}^{d \times d} \) 是已知的正定矩阵，作为协方差矩阵的上界（在Loewner序意义下，即 \( \mathbb{E}[ (\xi - \mu)(\xi - \mu)^T] \preceq \Sigma \) 表示 \( \Sigma - \mathbb{E}[ (\xi - \mu)(\xi - \mu)^T ] \) 是半正定矩阵）。符号 \( \preceq \) 表示矩阵的半正定序。我们的目标是： \[ \min_ {x} \left\{ c^T x + \sup_ {\mathbb{P} \in \mathcal{P}} \mathbb{E}_ {\mathbb{P}}[ Q(x, \xi) ] : Ax \leq b, x \geq 0 \right\} \] 即，在第一阶段决策 \( x \) 时，考虑最坏情况下（在分布族 \( \mathcal{P} \) 中）的期望第二阶段成本。 2.3 简化假设为突出核心转化步骤，我们假设：随机性只出现在第二阶段成本向量 \( q \) 中，即 \( q = \xi \)，且 \( \xi \in \mathbb{R}^m \) 是随机成本向量。则 \( Q(x, \xi) = \min_ {y} \{ \xi^T y : W y \geq h - T x, y \geq 0 \} \)。我们已知 \( \mathbb{E}[ \xi ] = \mu \) 和 \( \text{Cov}(\xi) \preceq \Sigma \)。这里 \( \Sigma \) 是给定的正定矩阵，协方差矩阵的上界。 3. 将DRO问题转化为线性规划 3.1 利用对偶理论处理内层 sup 问题内层问题为：对给定的 \( x \)（从而给定第二阶段可行域 \( Y(x) = \{ y \geq 0 : W y \geq h - T x \} \)），求 \[ \sup_ {\mathbb{P} \in \mathcal{P}} \mathbb{E} {\mathbb{P}} \left[ \min {y \in Y(x)} \xi^T y \right ] \] 由于内层是 \( \min \)，外层是 \( \sup \)，直接处理困难。一个关键技巧是：对于任何 \( y \in Y(x) \)，有 \( \min_ {y \in Y(x)} \xi^T y \leq \xi^T y \)。因此，对任意分布 \( \mathbb{P} \)，有 \[ \mathbb{E} {\mathbb{P}} \left[ \min {y \in Y(x)} \xi^T y \right] \leq \mathbb{E} {\mathbb{P}} [ \xi^T y] = \mu^T y + \mathbb{E} {\mathbb{P}}[ (\xi - \mu)^T y ] \] 由于 \( \mathbb{E}_ {\mathbb{P}}[ (\xi - \mu)^T y ] = 0 \)，所以上界为 \( \mu^T y \)。但我们要的是最坏情况期望，需要更精确的刻画。 3.2 利用鲁棒优化与矩问题的对偶可以证明（通过测度理论中的矩问题对偶，或S-引理类方法），在最坏分布下，期望值可以表示为： \[ \sup_ {\mathbb{P} \in \mathcal{P}} \mathbb{E} {\mathbb{P}}[ \min {y \in Y(x)} \xi^T y] = \min_ {y \in Y(x)} \sup_ {\mathbb{P} \in \mathcal{P}} \mathbb{E} {\mathbb{P}}[ \xi^T y ] \] 在适当的凸性假设下，上述“min”和“sup”可交换。现在内层是： \[ \sup {\mathbb{P} \in \mathcal{P}} \mathbb{E} {\mathbb{P}}[ \xi^T y] = \sup {\mathbb{P} \in \mathcal{P}} \mathbb{E} {\mathbb{P}}[ \xi]^T y = \mu^T y + \sup {\mathbb{P} \in \mathcal{P}} \mathbb{E} {\mathbb{P}}[ (\xi - \mu)^T y ] \] 由于 \( \mathbb{E}[ \xi ] = \mu \) 固定，只需处理第二项。而 \[ \sup {\mathbb{P} \in \mathcal{P}} \mathbb{E} {\mathbb{P}}[ (\xi - \mu)^T y] = \sup {\mathbb{P} \in \mathcal{P}} \mathbb{E} {\mathbb{P}}[ z^T y ] \quad \text{其中 } z = \xi - \mu \] 且 \( \mathbb{E}[ z] = 0, \mathbb{E}[ zz^T] \preceq \Sigma \)。这是矩问题：在满足一阶矩为0、二阶矩有上界 \( \Sigma \) 的所有分布中，最大化 \( \mathbb{E}[ z^T y ] \)。其最优值等于（通过半定规划对偶）： \[ \inf {P \succeq 0, \lambda} \left\{ \text{trace}(\Sigma P) : \begin{bmatrix} P & y/2 \\ y^T/2 & \lambda \end{bmatrix} \succeq 0 \right\} \] 其中 \( P \) 是对偶变量矩阵，\( \lambda \) 是标量。进一步化简可得，最优值等于 \( \sqrt{y^T \Sigma y} \)。即， \[ \sup_ {\mathbb{P} \in \mathcal{P}} \mathbb{E}_ {\mathbb{P}}[ (\xi - \mu)^T y ] = \sqrt{y^T \Sigma y} \] （这可以理解为：最坏分布将质量集中在使 \( z^T y \) 最大的方向上，受二阶矩约束，最大值就是 \( y \) 方向的“标准差”尺度）。 3.3 化简后的问题因此，内层 sup 问题变为： \[ \sup_ {\mathbb{P} \in \mathcal{P}} \mathbb{E} {\mathbb{P}}[ \xi^T y ] = \mu^T y + \sqrt{y^T \Sigma y} \] 于是原DRO目标成为： \[ \min {x, y} \left\{ c^T x + \mu^T y + \sqrt{y^T \Sigma y} : Ax \leq b, x \geq 0, W y \geq h - T x, y \geq 0 \right\} \] 注意这里 \( y \) 是第二阶段决策变量，与随机性无关（因为我们在最坏分布下优化）。 3.4 转化为线性规划目标中的 \( \sqrt{y^T \Sigma y} \) 是凸函数，但非线性。我们可以通过引入辅助变量 \( t \) 将其线性化： \[ \min_ {x, y, t} \left\{ c^T x + \mu^T y + t : Ax \leq b, x \geq 0, W y \geq h - T x, y \geq 0, \sqrt{y^T \Sigma y} \leq t \right\} \] 约束 \( \sqrt{y^T \Sigma y} \leq t \) 等价于二阶锥约束 \( \| \Sigma^{1/2} y \|_ 2 \leq t \)，其中 \( \Sigma^{1/2} \) 是 \( \Sigma \) 的对称平方根矩阵。这本身是二阶锥规划（SOCP），但我们可以进一步利用线性规划近似，或通过以下技巧转化为线性规划（当维度低或特殊结构时）：如果 \( \Sigma \) 是对角矩阵（即随机变量各分量不相关，但方差有界），设 \( \Sigma = \text{diag}(\sigma_ 1^2, \dots, \sigma_ m^2) \)，则 \[ \sqrt{y^T \Sigma y} = \sqrt{\sum_ {j=1}^m \sigma_ j^2 y_ j^2} = \| (\sigma_ 1 y_ 1, \dots, \sigma_ m y_ m) \| 2 \] 约束 \( \| (\sigma_ 1 y_ 1, \dots, \sigma_ m y_ m) \| 2 \leq t \) 可以用一系列线性约束近似（如多面体范数逼近），或者，如果我们允许保守近似，可以利用范数不等式： \[ \| (\sigma_ 1 y_ 1, \dots, \sigma_ m y_ m) \| 2 \leq \sum {j=1}^m \sigma_ j |y_ j| \] 由于 \( y_ j \geq 0 \)，有 \( |y_ j| = y_ j \)。所以 \( \sqrt{y^T \Sigma y} \leq \sum {j=1}^m \sigma_ j y_ j \)。这样，我们可以用线性上界替代，得到： \[ \min {x, y} \left\{ c^T x + \mu^T y + \sum_ {j=1}^m \sigma_ j y_ j : Ax \leq b, x \geq 0, W y \geq h - T x, y \geq 0 \right\} \] 这就是一个线性规划！虽然它比原问题保守（因为用了上界），但计算简便，且在某些应用中可接受。 3.5 精确的线性规划重构（通过对偶）另一种方法是回到内层 sup 问题的对偶形式。可以证明，原DRO问题等价于： \[ \min_ {x, y, M} \left\{ c^T x + \mu^T y + \text{trace}(\Sigma M) : Ax \leq b, x \geq 0, W y \geq h - T x, y \geq 0, M \succeq 0, M - y y^T \succeq 0 \right\} \] 其中 \( M \) 是一个对称矩阵变量。约束 \( M - y y^T \succeq 0 \) 可以写为线性矩阵不等式（LMI），这导致一个半定规划（SDP），而不是线性规划。但如果我们用 Schur 补，可以引入新变量，但仍然是 SDP。因此，要得到精确的线性规划，通常需要假设随机向量 \( \xi \) 的支撑集是有限个场景（离散分布），这时矩不确定集下的 DRO 可以转化为线性规划。但本示例中，我们假设连续矩信息，并采用上述线性上界近似，从而得到线性规划。 4. 解题步骤总结问题建模：识别随机参数、决策阶段、目标与约束，定义矩不确定集 \( \mathcal{P} \)。内层最坏期望转化：利用矩问题对偶，将内层 sup 问题转化为关于决策变量 \( y \) 的确定性表达式 \( \mu^T y + \sqrt{y^T \Sigma y} \)。线性化近似：将非线性项 \( \sqrt{y^T \Sigma y} \) 用线性上界 \( \sum \sigma_ j y_ j \) 替代（在 \( \Sigma \) 对角且 \( y \geq 0 \) 条件下）。整合为线性规划：将目标与约束全部写为线性形式，得到最终的线性规划模型。求解与后分析：用单纯形法或内点法求解该线性规划，得到第一阶段决策 \( x^* \) 和第二阶段决策 \( y^* \)。分析解的鲁棒性。 5. 一个简单数值示例假设：第一阶段：\( n=1, c=1, A=1, b=10 \)，即 \( x \leq 10, x \geq 0 \)。第二阶段：\( m=2 \)，随机成本 \( \xi = (\xi_ 1, \xi_ 2) \)，期望 \( \mu = (2, 3) \)，协方差上界矩阵 \( \Sigma = \begin{bmatrix} 4 & 0 \\ 0 & 9 \end{bmatrix} \)（即标准差 \( \sigma_ 1=2, \sigma_ 2=3 \)）。第二阶段的约束：\( W = I_ 2 \), \( h = (5, 4)^T \), \( T = (1, 1)^T \)，即 \[ y_ 1 \geq 5 - x, \quad y_ 2 \geq 4 - x, \quad y_ 1, y_ 2 \geq 0 \] 线性规划模型（采用线性上界近似）：目标：最小化 \( 1 \cdot x + 2 y_ 1 + 3 y_ 2 + 2 y_ 1 + 3 y_ 2 = x + 4 y_ 1 + 6 y_ 2 \) 约束： \( x \leq 10, x \geq 0 \) \( y_ 1 \geq 5 - x, y_ 2 \geq 4 - x \) \( y_ 1, y_ 2 \geq 0 \) 由于 \( y_ 1, y_ 2 \) 出现在目标中带正系数，在约束下应取最小值，即 \( y_ 1 = \max(0, 5-x) \), \( y_ 2 = \max(0, 4-x) \)。分区间讨论：若 \( x \geq 5 \)，则 \( y_ 1=0, y_ 2=0 \)，目标 = \( x \)，最优在 \( x=5 \) 得 5。若 \( 4 \leq x < 5 \)，则 \( y_ 1=5-x, y_ 2=0 \)，目标 = \( x + 4(5-x) = 20 - 3x \)，在 \( x=5 \) 得 5（边界）。若 \( x < 4 \)，则 \( y_ 1=5-x, y_ 2=4-x \)，目标 = \( x + 4(5-x) + 6(4-x) = x + 20-4x + 24-6x = 44 - 9x \)，在 \( x=4 \) 得 8。比较得全局最优解：\( x^* = 5, y_ 1^* = 0, y_ 2^* = 0 \)，最优值 = 5。 6. 关键点说明矩不确定集 DRO 通过最坏情况期望，平衡了优化与不确定性。在特殊结构下（对角协方差、非负决策），可近似为线性规划，计算高效。更一般情况需用二阶锥规划或半定规划，但线性近似提供了一个保守但简单的可行方案。这个示例展示了如何将复杂的分布式鲁棒优化问题，在矩信息下，转化为可计算的线性规划，从而为决策提供鲁棒方案。