\texttt{DR-DAQP}: An Hybrid Operator Splitting and Active-Set Solver for Affine Variational Inequalities

📄 arXiv: 2604.02531 📥 PDF

作者: Daniel Arnström, Emilio Benenati, Giuseppe Belgioioso

分类: eess.SY, cs.MS

发布日期: 2026-04-06

💡 一句话要点

提出DR-DAQP以解决强单调仿射变分不等式问题

🎯 匹配领域: 支柱一：机器人控制 (Robot Control)

关键词: 变分不等式 主动集方法 Douglas-Rachford 牛顿修正 优化算法 高性能计算 开源软件

📋 核心要点

  1. 现有方法在求解强单调仿射变分不等式时存在渐近收敛限制，导致效率低下。
  2. 论文提出DR-DAQP，通过估计主动集并结合牛顿类型修正，显著提高求解精度与速度。
  3. 实验结果显示，DR-DAQP在随机生成的AVI上比现有求解器快两个数量级，具有显著的性能提升。

📝 摘要（中文）

我们提出了DR-DAQP，一个开源求解器，用于强单调仿射变分不等式，结合了Douglas-Rachford算子分裂与主动集加速策略。关键思想是在迭代过程中估计主动集，以尝试进行牛顿类型的修正。当主动集正确估计时，此步骤可获得精确的AVI解，从而克服一阶方法固有的渐近收敛限制。此外，我们利用热启动和相关矩阵的预因子化进一步加速算法迭代的评估。我们证明了收敛性，并建立了算法在有限时间内终止于精确解的条件。随机生成的AVI的数值实验表明，DR-DAQP的速度比最先进的求解器PATH快两个数量级。在博弈论MPC基准上，DR-DAQP的求解时间比混合整数求解器NashOpt低几个数量级。高性能的C实现可在此链接获取，并提供了对Julia、MATLAB和Python的易用接口。

🔬 方法详解

问题定义：论文旨在解决强单调仿射变分不等式（AVI）的问题。现有方法在处理此类问题时，往往面临渐近收敛的限制，导致求解效率低下。

核心思路：DR-DAQP的核心思路是结合Douglas-Rachford算子分裂与主动集加速策略，通过在迭代过程中动态估计主动集，进行牛顿类型的修正，从而提高求解的精度和速度。

技术框架：该方法的整体架构包括主动集估计、牛顿修正、热启动和相关矩阵的预因子化等模块。算法通过这些模块的协同作用，优化了迭代过程，提升了求解效率。

关键创新：DR-DAQP的主要创新在于其主动集估计与牛顿修正的结合，这一设计使得算法在主动集正确估计的情况下能够获得精确解，克服了传统一阶方法的局限性。

关键设计：在算法实现中，采用了热启动策略以减少初始迭代的计算负担，并通过预因子化技术加速矩阵运算，从而提高了整体算法的运行效率。算法的C实现具备高性能，并提供了多种编程语言的接口。

🖼️ 关键图片

fig_0

📊 实验亮点

实验结果表明，DR-DAQP在随机生成的AVI问题上比最先进的求解器PATH快两个数量级。在博弈论MPC基准测试中，DR-DAQP的求解时间比混合整数求解器NashOpt低几个数量级，显示出其卓越的性能。

🎯 应用场景

该研究的潜在应用领域包括优化问题、博弈论、控制系统等，尤其是在需要快速求解复杂变分不等式的场景中。DR-DAQP的高效性和准确性使其在实际工程和研究中具有重要的应用价值，未来可能推动相关领域的进一步发展。

📄 摘要（原文）

We present \texttt{DR-DAQP}, an open-source solver for strongly monotone affine variational inequaliries that combines Douglas-Rachford operator splitting with an active-set acceleration strategy. The key idea is to estimate the active set along the iterations to attempt a Newton-type correction. This step yields the exact AVI solution when the active set is correctly estimated, thus overcoming the asymptotic convergence limitation inherent in first-order methods. Moreover, we exploit warm-starting and pre-factorization of relevant matrices to further accelerate evaluation of the algorithm iterations. We prove convergence and establish conditions under which the algorithm terminates in finite time with the exact solution. Numerical experiments on randomly generated AVIs show that \texttt{DR-DAQP} is up to two orders of magnitude faster than the state-of-the-art solver \texttt{PATH}. On a game-theoretic MPC benchmark, \texttt{DR-DAQP} achieves solve times several orders of magnitude below those of the mixed-integer solver \texttt{NashOpt}. A high-performing C implementation is available at \textt{this https URL}, with easily-accessible interfaces to Julia, MATLAB, and Python.