arXiv:2409.17500cs.AIcs.SY2024-09NeurIPS被引 7

提出可微分的线性约束满足层,让神经网络输出自动符合复杂约束。

GLinSAT: The General Linear Satisfiability Neural Network Layer By Accelerated Gradient Descent

  • 将约束满足转化为可微凸优化问题,用加速梯度法求解。
  • 在4类实际问题上优于现有方法,如旅行商、投资组合等。
  • 首个全可微且无需矩阵分解的通用线性约束层,适合决策类任务。

确保神经网络输出满足特定约束对真实决策问题至关重要。本文研究如何使一批神经网络输出满足有界且一般的线性约束。首先将输出投影问题重新表述为熵正则化的线性规划问题,根据对偶定理,该问题可等价转化为具有Lipschitz连续梯度的无约束凸优化问题。随后,基于数值性能增强的加速梯度下降算法,提出GLinSAT架构来求解。据我们所知,这是首个所有操作均可微且无需矩阵分解的通用线性可满足性层。尽管可通过自动微分显式执行反向传播,我们还提供基于最优性条件隐式微分的替代方法。在受限旅行商问题、含异常值的部分图匹配、预测性投资组合分配及电力系统机组组合上的实验表明,GLinSAT显著优于现有可满足性层。代码已开源:https://github.com/HunterTracer/GLinSAT。

原文摘要 · Abstract (English)

Ensuring that the outputs of neural networks satisfy specific constraints is crucial for applying neural networks to real-life decision-making problems. In this paper, we consider making a batch of neural network outputs satisfy bounded and general linear constraints. We first reformulate the neural network output projection problem as an entropy-regularized linear programming problem. We show that such a problem can be equivalently transformed into an unconstrained convex optimization problem with Lipschitz continuous gradient according to the duality theorem. Then, based on an accelerated gradient descent algorithm with numerical performance enhancement, we present our architecture, GLinSAT, to solve the problem. To the best of our knowledge, this is the first general linear satisfiability layer in which all the operations are differentiable and matrix-factorization-free. Despite the fact that we can explicitly perform backpropagation based on automatic differentiation mechanism, we also provide an alternative approach in GLinSAT to calculate the derivatives based on implicit differentiation of the optimality condition. Experimental results on constrained traveling salesman problems, partial graph matching with outliers, predictive portfolio allocation and power system unit commitment demonstrate the advantages of GLinSAT over existing satisfiability layers. Our implementation is available at \url{https://github.com/HunterTracer/GLinSAT}.

神经网络约束满足可微分优化决策系统

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。