用神经网络+对偶算法解决不确定环境下的决策优化问题。
Primal-dual algorithm for contextual stochastic combinatorial optimization
- 用带组合优化层的神经网络编码策略，结合对偶方法求解。
- 在三个任务上性能媲美顶尖方法，计算量大幅降低。
- 适合需要高效应对不确定性决策的研究者与工程师。
本文提出一种新方法，融合运筹学与机器学习，解决不确定性环境下的上下文随机组合优化问题。传统方法常忽略上下文信息，为此我们引入带组合优化层的神经网络来编码策略，目标是最小化基于历史数据估计的经验成本。为此，我们构建了一个代理学习问题，并设计了一种通用的原-对偶算法，适用于多种随机优化组合场景。该方法拓展了经典的Fenchel-Yong损失理论，提出一种在分布单纯形上使用稀疏扰动的新正则化方法，实现原始空间中的可计算更新，支持多样目标函数。我们证明了精确线性参数版本的次线性收敛性，并给出了所得策略在经验成本上的非最优性界。在三个上下文随机优化问题上的实验表明，该算法高效且可扩展，性能接近现有最优基准，但计算开销显著降低。
原文摘要 · Abstract (English)
This paper introduces a novel approach to contextual stochastic optimization, integrating operations research and machine learning to address decision-making under uncertainty. Traditional methods often fail to leverage contextual information, which underscores the necessity for new algorithms. In this study, we utilize neural networks with combinatorial optimization layers to encode policies. Our goal is to minimize the empirical cost, which is estimated from past data on uncertain parameters and contexts. To that end, we present a surrogate learning problem and a generic primal-dual algorithm that is applicable to various combinatorial settings in stochastic optimization. Our approach extends classic Fenchel--Young loss results and introduces a new regularization method using sparse perturbations on the distribution simplex. This allows for tractable updates in the original space and can accommodate diverse objective functions. We establish sublinear convergence for the exact linear-parametric version and provide a bound on the non-optimality of the resulting policy in terms of the empirical cost. Experiments on three contextual stochastic optimization problems show that our algorithm is efficient and scalable, achieving performance comparable to state-of-the-art baselines with significantly reduced computational requirements.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。