Conformal Predictive Programming for Chance Constrained Optimization

技术摘要：用于机会约束优化的共形预测规划 (Conformal Predictive Programming)

问题陈述
本文研究了机会约束优化 (Chance Constrained Optimization, CCO) 问题，这类问题涉及在随机向量 $Y$ 的高概率 ($1-\delta$) 下最小化代价函数 $J(x)$，并满足约束条件。形式化定义为：
$$\min_{x \in X} J(x) \quad \text{s.t.} \quad P(f(x, Y) \leq 0) \geq 1 - \delta$$
其中 $f$ 是 Borel 可测函数，且 $Y$ 服从未知的分布 $P_Y$。解决 CCO 的主要挑战在于 $P_Y$ 通常是未知的，即使已知，评估概率约束也需要求解复杂的、通常是难以处理的积分。现有的基于采样的方法（如情景法 (Scenario Approach, SA) 和样本平均近似法 (Sample Average Approximation, SAA)）通常依赖于强结构假设（例如 $J$、$f$ 和 $X$ 的凸性）来提供先验保证。当这些假设不成立，或者先验保证过于保守或计算成本过高（例如需要识别支持约束）时，现有方法难以提供可靠的后验可行性保证。

方法论：共形预测规划 (Conformal Predictive Programming, CPP)
作者提出了共形预测规划 (CPP)，这是一个利用共形预测 (Conformity Prediction, CP) 将随机 CCO 问题转化为确定性优化问题的框架。CPP 分为两个截然不同的阶段运行：

1. 优化步骤（分位数重构）：
   CPP 不直接使用原始的机会约束，而是使用一个定义在优化数据集 $\{Y^{(1)}, \dots, Y^{(K)}\}$ 上的分位数约束进行替换。该问题被重构为：
   $$\min_{x \in X} J(x) \quad \text{s.t.} \quad \hat{Q}_{\alpha(K)}(f(x, Y^{(1)}), \dots, f(x, Y^{(K)})) \leq 0$$
   这里 $\hat{Q}_{\alpha(K)}$ 是特定置信水平 $\alpha(K)$ 下的经验分位数。作者证明，这种重构是 SAA 的一种实例化，使得 CPP 能够为特定的问题类（如可分离约束）继承来自 SAA 文献的先验保证。

2. 校准步骤（后验保证）：
   为了在不依赖凸性等结构假设的情况下提供严格的后验可行性保证，CPP 利用第二个独立的校准数据集 $\{Y^{(K+1)}, \dots, Y^{(K+L)}\}$ 进行操作。

   • 边际保证 (Marginal Guarantees)： 利用 CP 中的分位数引理 (Quantile Lemma)，CPP 计算出校准数据上的一个分位数 $C_m$。定理 3.4 确立了对于数据乘积测度，解 $x^*(K)$ 满足 $P(f(x^*(K), Y) \leq C_m) \geq 1-\delta$。
   • 条件保证 (Conditional Guarantees)： 通过在分位数计算中使用更紧凑的置信水平（条件分位数引理），CPP 提供了以高置信度 ($1-\beta$) 在给定校准数据集条件下成立的保证。
   • 分位数偏移 (Quantile Shift)： 为了处理计算出的界限 $C$ 为正数的情况，作者提出了“分位数偏移”方法（定理 3.6）。该方法通过计算校准集中满足约束的数量来计算调整后的失效概率 $\delta^*$，从而确保 $P(f(x^*(K), Y) \leq 0) \geq 1-\delta^*$ 以高置信度成立。

核心贡献

• 新框架： 引入了 CPP 作为一种采样方法，它对 CCO 问题所需的结构假设非常有限。
• 统计保证： 提供了两种后验可行性保证：条件保证和边际保证。与标准情景法 (SA) 不同，这些保证不依赖于决策变量的维度 $n$，从而降低了高维问题中的保守性。
• 模块化与多功能性： 该框架旨在轻松整合各种共形预测 (CP) 变体。作者通过将 CPP 扩展到以下领域展示了这一点：
  • 鲁棒 CPP (RCPP)： 使用鲁棒共形预测和模糊集来处理分布偏移（例如 sim-to-real 差距）。
  • Mondrian CPP (MCPP)： 处理类条件机会约束 (MCCO)，确保安全保证对随机变量分布的特定子集有效。
• 与现有理论的联系： 本文确立了 CPP 继承了来自 SAA 的先验保证，并且其条件后验保证在渐近意义上收敛至切尔诺夫界 (Chernoff bounds)。

结果与案例研究
作者通过涉及凸和非凸问题以及随机最优控制任务的数值案例研究验证了 CPP。

• 凸与非凸优化： 在针对非凸问题的 CPP 与情景法 (SA) 的对比实验中，CPP 展示了具有竞争力的表现。值得注意的是，虽然非凸 SA 方法（如 [18, 26]）需要计算量巨大的步骤来寻找不可约支持子集以获得后验保证（在研究中耗时约 10 秒），但 CPP 的分位数偏移计算要快得多（线性时间）。
• 经验覆盖率： 实验证实，解的经验覆盖率收敛于理论界限 ($1-\delta$ 或 $1-\delta^*$)。计算出的界限中心位于零附近，这表明分位数重构有效地近似了原始的机会约束。
• 鲁棒与 Mondrian 扩展： 在一个随机最优控制问题（机器人导航）中，RCPP 成功处理了分布偏移（模拟噪声方差的变化），实现了比标准 CPP 基准更高的经验覆盖率 (0.96 vs 0.80)。同样，Mondrian CPP 成功地为特定扰动幅度组维持了覆盖保证，而标准 CPP 在这些组中失败了。

意义与主张
本文声称，对于无法获得或难以验证标准假设（如凸性、已知分布）的 CCO 问题，CPP 提供了一个计算高效且可扩展的框架。其主要意义在于提供了与维度无关的可行性证书。与情景法不同——在情景法中，随着决策变量数量的增加，保证会变得越来越松散——CPP 的保证无论维度如何都能保持稳健，只要存在第二个校准数据集。作者强调，这种方法弥合了共形预测的理论严谨性与控制及规划在不确定性下实际需求之间的鸿沟，为那些依赖复杂结构分析或产生过度保守解的方法提供了一个实用的替代方案。