替代目标框架带有软约束的预测+优化
由crisvalentine创建，最终由crisvalentine 被浏览 37 用户
论文原名
A Surrogate Objective Framework for Prediction+Optimization with Soft Constraints
论文作者
Kai Yan， Jie Yan，Liting Chen，Qingwei Lin，Dongmei Zhang
修订时间
2021年11月22日
引言
预测+优化是一种常见的现实世界范式，我们必须预先在解决优化问题之前先输入问题参数。但是，那训练预测模型的标准通常与下游优化问题的目标。最近，以决策为中心的预已经提出了诸如 SPO+ 和直接优化之类的字典方法来填补这个空白。然而，他们不能直接处理软约束许多实际目标所需的最大算子。本文提出一种新颖的分析可微代理目标框架，适用于现实世界具有软线性的线性和半定负二次规划问题和非负硬约束。这个框架给出了理论界限关于约束的乘数，并推导出关于预测参数以及问题中任何变量的梯度。我们在三个使用软约束扩展的应用程序中评估我们的方法：合成线性规划、投资组合优化和资源供应、演示我们的方法优于传统的两阶段方法和其他以决策为中心的方法。
简介
数学优化（又名数学规划），例如线性和二次规划-ming，已广泛应用于决策过程，如资源调度[ 1 ]、货物生产计划 [ 2]、投资组合优化 [3] 和电力调度 [4]。在实践中，问题参数（例如，商品需求和股权回报）通常是由模型预测的具有观察到的特征（例如，历史时间序列）。随着机器学习技术的普及并且越来越多的可用数据，预测+优化已经成为一种常态，预测对于完整预测+优化工作流程的性能变得至关重要，因为现代优化求解器（例如 Gurobi [ 6 ] 和 CPLEX [7]）已经可以有效地找到最优解大多数大规模优化问题的解决方案。传统上，预测被单独处理为一个通用的监督学习问题，通过最小化通用损失函数（例如，回归的均方误差）。然而，研究表明，最小化拟合错误不一定会导致更好的最终决策性能 [8 , 9, 10, 11]。最近，在使用优化目标来指导预测模型的学习方面做了很多努力已经做出，在训练预测模型时以决策为重点，而不是使用传统的预测指标，例如均方误差损失。对于线性物镜，'SmartPredict then Optimize' ([ 10 ]) 提出了 SPO+ 损失函数来衡量预测误差针对优化目标，而直接优化（[12 ]）更新预测模型的扰动参数。对于二次目标，OptNet [13 , 14] 实现了优化作为一个隐式层，其梯度可以通过微分 KKT 条件来计算，然后反向传播到预测神经网络。CVXPY [15 ]使用与 OptNet 类似的技术但扩展到凸优化的更一般情况。然而，上述所有最先进的技术方法在其目标中不包含软约束。在本文中，我们考虑线性'soft-constraints'，一种形式为 max(z, 0) 的惩罚，其中 z = Cx − d 是决策的投影变量 x ∈ R n和上下文变量 C ∈ R m×n ,d ∈ R m。通常需要这种软约束在实践中：例如，它们可能是超出需求的资源浪费或额外的违反监管规定时缴纳的税款。不幸的是，max(·, 0) 运算符是不可微的因此不能由这些现有方法直接处理。区分软约束是一个本文的主要动机。在本文中，我们为一系列广泛的现实世界线性和具有线性软约束的二次规划问题并实现以决策为中心的差分可推论的预测，假设硬约束参数的非负性。这框架包括三个步骤：1）将所有硬约束重写为分段线性软约束具有有界惩罚乘数的约束；2) 使用可微分的元素代理来替换分段目标，并通过数值求解原始函数来决定哪个分段最佳点在；3) 解析求解局部代理并得到梯度；梯度与分段代理的梯度相同，因为代理是凸/凹的认为最优点是唯一的。我们的主要贡献总结如下。首先，我们提出了一个可微的替代对象包含软约束和硬约束的功能。作为我们方法论的基础，在第3节中，我们证明，在现实世界中普遍满足的合理假设下，对于线性和半定负二次规划问题，约束可以变换进入软约束；然后我们提出了一个分析可微的软代理函数约束最大（·，0）。其次，我们提出了三个派生的解析解和封闭形式解第 4 节中使用软约束扩展的代表性优化问题——线性规划软约束、二次规划软约束和非对称软约束最小化。与基于 KKT 的微分方法不同，我们的方法使计算梯度直接用于预测问题任何部分的上下文参数。最后，我们应用理论推导并在三种情况下评估我们的方法，包括合成第 4 节中的线性规划、投资组合优化和资源供应，凭经验证明我们的方法优于两阶段和其他预测+优化方法。
论文PDF
/wiki/static/upload/8c/8c526a9b-e312-43b0-a577-6718b3a13036.pdf
\