pith. machine review for the scientific record. sign in

arxiv: 2604.02531 · v1 · submitted 2026-04-02 · 📡 eess.SY · cs.MS· cs.SY

Recognition: 2 theorem links

· Lean Theorem

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

Daniel Arnstr\"om , Emilio Benenati , Giuseppe Belgioioso
Authors on Pith no claims yet

Pith reviewed 2026-05-13 20:32 UTC · model grok-4.3

classification 📡 eess.SY cs.MScs.SY
keywords affine variational inequalitiesDouglas-Rachford splittingactive-set methodsNewton correctionfinite terminationoperator splittingquadratic programming
0
0 comments X

The pith

Hybrid Douglas-Rachford and active-set solver solves strongly monotone affine variational inequalities exactly in finite time.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper presents DR-DAQP, a solver for strongly monotone affine variational inequalities that merges Douglas-Rachford operator splitting with an active-set acceleration step. During iterations the method estimates the active set and attempts a Newton-type correction, which recovers the exact solution when the estimate is correct and thereby removes the asymptotic slowdown typical of first-order methods. Warm-starting and matrix pre-factorization are added to speed up each iteration. Convergence is proved, along with conditions for finite termination at the exact solution. Tests on random problems show speedups of up to two orders of magnitude over PATH, and large gains over mixed-integer solvers on game-theoretic MPC instances.

Core claim

DR-DAQP combines Douglas-Rachford splitting with active-set estimation to perform Newton corrections that recover the exact solution of strongly monotone affine variational inequalities in finite time when the active set is correctly identified, while convergence is guaranteed in all cases.

What carries the argument

Active-set estimation along Douglas-Rachford iterations to trigger Newton-type correction steps that solve the AVI exactly when the estimate matches the true active set.

If this is right

  • Convergence holds for every strongly monotone affine variational inequality.
  • Finite termination with the exact solution occurs whenever the active-set estimate becomes correct.
  • Solve times drop by up to two orders of magnitude compared with PATH on random instances.
  • Warm-starting and pre-factorization further reduce per-iteration cost on repeated problems such as MPC.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same active-set acceleration pattern may be portable to other operator-splitting schemes for variational inequalities.
  • Pre-factorization techniques could be reused in related quadratic or linear complementarity problems.
  • Empirical scaling on larger or structured real-world AVIs remains an open test of practical limits.

Load-bearing premise

The variational inequality is strongly monotone and affine, and the active-set estimates during iterations are accurate enough for the Newton correction to produce the exact solution.

What would settle it

A set of randomly generated strongly monotone affine VIs on which the algorithm either fails to reach the exact solution in finite steps or takes longer than PATH.

Figures

Figures reproduced from arXiv: 2604.02531 by Daniel Arnstr\"om, Emilio Benenati, Giuseppe Belgioioso.

Figure 2
Figure 2. Figure 2: Solve time comparison of DR-DAQP, PATH, and a lifted QP formulation on random AVIs with γ asym = 0.5 and m = 10n. Solid lines show the median; shaded regions span the min-max range over 100 instances. 2) Comparison with PATH: Next, we compare Algo￾rithm 2 against the state-of-the-art pivotal solver PATH [9], and against the standard QP solver Clarabel applied to the reformulation of the AVI as a QP in a li… view at source ↗
Figure 1
Figure 1. Figure 1: Total solve time when solving the subproblems (9) in [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 5
Figure 5. Figure 5: Simulated driving scenario. The safety distance con [PITH_FULL_IMAGE:figures/full_fig_p005_5.png] view at source ↗
Figure 4
Figure 4. Figure 4: Solve time for the game theoretic MPC controller [PITH_FULL_IMAGE:figures/full_fig_p005_4.png] view at source ↗
read the original abstract

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{https://github.com/darnstrom/daqp}, with easily-accessible interfaces to Julia, MATLAB, and Python.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 3 minor

Summary. The paper presents DR-DAQP, a hybrid solver for strongly monotone affine variational inequalities (AVIs) that combines Douglas-Rachford operator splitting with an active-set acceleration strategy. The algorithm estimates the active set during iterations to apply a Newton-type correction that yields the exact solution when the active set is correct, overcoming the slow asymptotic convergence of pure first-order methods. The authors prove convergence, derive explicit conditions for finite termination with the exact solution, exploit warm-starting and pre-factorization for speed, and report numerical results showing up to two orders of magnitude faster solve times than PATH on random AVIs and several orders of magnitude improvement over NashOpt on a game-theoretic MPC benchmark. An open-source C implementation with interfaces to Julia, MATLAB, and Python is provided.

Significance. If the convergence proof and finite-termination conditions hold, the work provides a practically significant advance for solving strongly monotone AVIs arising in model predictive control and game-theoretic problems. By delivering both theoretical guarantees and empirical speed-ups over established solvers such as PATH, together with an open-source, multi-language implementation, the contribution has clear potential to improve real-time optimization performance in systems and control applications.

major comments (2)
  1. [§4, Theorem 3] §4 (Convergence analysis), Theorem 3: The finite-termination claim requires that the active-set estimate becomes exact after finitely many Douglas-Rachford steps; the proof sketch does not provide an explicit bound on the number of iterations needed for correct identification in terms of the strong-monotonicity modulus or the problem dimension, leaving the practical relevance of the finite-time guarantee unclear.
  2. [§5.2] §5.2 (Numerical experiments): The procedure used to generate the random AVI instances (distribution of the matrix M, vector q, constraint dimensions, and conditioning) is not specified, so the reported speed-up of “up to two orders of magnitude” versus PATH cannot be independently verified or generalized.
minor comments (3)
  1. [Abstract] Abstract: “An Hybrid” should read “A Hybrid”; “inequaliries” is a typo for “inequalities”; “textt{https” is missing a second “t” (should be “texttt”).
  2. [Algorithm 1] Algorithm 1: the notation for the projection onto the active-set polyhedron and the Newton correction step should be defined before first use, or a reference to the relevant equation in §3 should be added.
  3. [Table 1] Table 1: the column headers for CPU time and iteration count are not aligned with the reported statistics; adding standard-deviation columns would strengthen the performance comparison.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the positive assessment and the recommendation for minor revision. The comments are constructive and we address each major point below.

read point-by-point responses

  1. Referee: [§4, Theorem 3] §4 (Convergence analysis), Theorem 3: The finite-termination claim requires that the active-set estimate becomes exact after finitely many Douglas-Rachford steps; the proof sketch does not provide an explicit bound on the number of iterations needed for correct identification in terms of the strong-monotonicity modulus or the problem dimension, leaving the practical relevance of the finite-time guarantee unclear.

    Authors: We agree that Theorem 3 establishes finite termination once the active set is correctly identified but does not supply an explicit iteration bound in terms of the strong-monotonicity modulus or dimension. Deriving a tight, problem-independent bound appears difficult because the number of Douglas-Rachford steps required for identification depends on the specific trajectory and data. Nevertheless, the finite-termination guarantee remains valid under the stated conditions, and the numerical results in §5 demonstrate that identification occurs after only a few iterations in practice, producing the reported speed-ups. In the revision we will add a short remark after Theorem 3 acknowledging the lack of an explicit bound and clarifying its practical implications. revision: partial

  2. Referee: [§5.2] §5.2 (Numerical experiments): The procedure used to generate the random AVI instances (distribution of the matrix M, vector q, constraint dimensions, and conditioning) is not specified, so the reported speed-up of “up to two orders of magnitude” versus PATH cannot be independently verified or generalized.

    Authors: We thank the referee for pointing out this omission. The random instances were generated as follows: M was constructed as a symmetric positive-definite matrix with eigenvalues uniformly drawn from [1, 10] (ensuring strong monotonicity with modulus 1), q was sampled from the standard normal distribution, the number of variables ranged from 10 to 100, and the number of inequality constraints was set between 20 and 200 with random linear inequalities whose conditioning was controlled by the eigenvalue spread of M. We will insert a complete description of this generation procedure, including all parameter ranges and the random-seed policy, into the revised §5.2 so that the experiments can be reproduced. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained

full rationale

The paper develops DR-DAQP by combining Douglas-Rachford operator splitting with an active-set Newton correction for strongly monotone affine VIs. Convergence follows directly from the contraction property induced by strong monotonicity, and finite termination is shown under the explicit condition that the active-set estimate becomes exact. These steps rely on standard fixed-point arguments and linear algebra rather than any fitted parameters, self-definitional loops, or load-bearing self-citations. Numerical results are presented as empirical timing comparisons against independent external solvers (PATH, NashOpt) on randomly generated instances, not as part of the formal guarantee. No step reduces the claimed result to its own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central contribution is algorithmic; relies on standard assumptions in variational inequality theory without introducing new entities or fitted parameters.

axioms (1)
  • domain assumption The problem is a strongly monotone affine variational inequality.
    This ensures uniqueness of solution and convergence of the base Douglas-Rachford method.

pith-pipeline@v0.9.0 · 5521 in / 1209 out tokens · 54605 ms · 2026-05-13T20:32:24.712694+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

24 extracted references · 24 canonical work pages · 2 internal anchors

  1. [1]

    Facchinei and J.-S

    F. Facchinei and J.-S. Pang,Finite-dimensional variational inequalities and complementarity problems. Springer, 2003

    work page 2003

  2. [2]

    Generalized Nash equilibrium prob- lems,

    F. Facchinei and C. Kanzow, “Generalized Nash equilibrium prob- lems,”Annals of Operations Research, vol. 175, no. 1, pp. 177–211, 2010

    work page 2010

  3. [3]

    Efficient Iterative Linear-Quadratic Approximations for Non- linear Multi-Player General-Sum Differential Games,

    D. Fridovich-Keil, E. Ratner, L. Peters, A. D. Dragan, and C. J. Tomlin, “Efficient Iterative Linear-Quadratic Approximations for Non- linear Multi-Player General-Sum Differential Games,” in2020 IEEE International Conference on Robotics and Automation (ICRA). Paris, France: IEEE, May 2020, pp. 1475–1481

    work page 2020

  4. [4]

    LUCIDGames: Online Unscented Inverse Dynamic Games for Adaptive Trajectory Prediction and Planning,

    S. Le Cleac’h, M. Schwager, and Z. Manchester, “LUCIDGames: Online Unscented Inverse Dynamic Games for Adaptive Trajectory Prediction and Planning,”IEEE Robotics and Automation Letters, vol. 6, no. 3, pp. 5485–5492, 2021

    work page 2021

  5. [5]

    A Game Theoretic Approach for Safe and Distributed Control of Un- manned Aerial Vehicles,

    A. A. Do Nascimento, A. Papachristodoulou, and K. Margellos, “A Game Theoretic Approach for Safe and Distributed Control of Un- manned Aerial Vehicles,” in2023 62nd IEEE Conference on Decision and Control (CDC). Singapore, Singapore: IEEE, 2023, pp. 1070– 1075

    work page 2023

  6. [6]

    Game Theory in Formula 1: Multi-agent Physical and Strategical Interactions,

    G. Fieni, M.-P. Neumann, F. Furia, A. Caucino, A. Cerofolini, V . Ravaglioli, and C. H. Onder, “Game Theory in Formula 1: Multi-agent Physical and Strategical Interactions,”arXiv preprint arXiv.2503.0542, Mar. 2025

    work page arXiv 2025

  7. [7]

    A Sequential Quadratic Programming Approach to the Solution of Open-Loop Generalized Nash Equilibria,

    E. L. Zhu and F. Borrelli, “A Sequential Quadratic Programming Approach to the Solution of Open-Loop Generalized Nash Equilibria,” in2023 IEEE International Conference on Robotics and Automation (ICRA). London, United Kingdom: IEEE, May 2023, pp. 3211–3217

    work page 2023

  8. [8]

    A pivotal method for affine variational inequalities,

    M. Cao and M. C. Ferris, “A pivotal method for affine variational inequalities,”Mathematics of Operations research, vol. 21, no. 1, pp. 44–64, 1996

    work page 1996

  9. [9]

    The path solver: a nommonotone sta- bilization scheme for mixed complementarity problems,

    S. P. Dirkse and M. C. Ferris, “The path solver: a nommonotone sta- bilization scheme for mixed complementarity problems,”Optimization methods and software, vol. 5, no. 2, pp. 123–156, 1995

    work page 1995

  10. [10]

    A structure-preserving pivotal method for affine variational inequalities,

    Y . Kim, O. Huber, and M. C. Ferris, “A structure-preserving pivotal method for affine variational inequalities,”Mathematical Program- ming, vol. 168, no. 1, pp. 93–121, 2018

    work page 2018

  11. [11]

    Computational complexity of complementary pivot methods,

    K. G. Murty, “Computational complexity of complementary pivot methods,” inComplementarity and fixed point problems. Springer, 2009, pp. 61–73

    work page 2009

  12. [12]

    Operator-splitting methods for monotone affine variational inequalities, with a parallel application to optimal control,

    J. Eckstein and M. C. Ferris, “Operator-splitting methods for monotone affine variational inequalities, with a parallel application to optimal control,”INFORMS Journal on Computing, vol. 10, no. 2, pp. 218– 235, 1998

    work page 1998

  13. [13]

    A Douglas-Rachford Splitting Method for Solving Monotone Variational Inequalities in Linear-quadratic Dynamic Games

    R. R. Baghbadorani, E. Benenati, and S. Grammatico, “A douglas- rachford splitting method for solving monotone variational inequalities in linear-quadratic dynamic games,”arXiv preprint arXiv:2504.05757, 2025

    work page internal anchor Pith review Pith/arXiv arXiv 2025

  14. [14]

    monviso: A Python Package for Solving Monotone Variational Inequalities,

    N. Mignoni, R. R. Baghbadorani, R. Carli, P. M. Esfahani, M. Dotoli, and S. Grammatico, “monviso: A Python Package for Solving Monotone Variational Inequalities,” in2025 European Control Conference (ECC). IEEE, Jun. 2025, pp. 1708–1713. [Online]. Available: https://ieeexplore.ieee.org/document/11187100/

    work page arXiv 2025

  15. [15]

    Input-to-state stability of Newton meth- ods in nash equilibrium problems with applications to game-theoretic model predictive control,

    M. Liu and I. Kolmanovsky, “Input-to-state stability of Newton meth- ods in nash equilibrium problems with applications to game-theoretic model predictive control,”arXiv preprint arXiv:2412.06186, 2024

    work page arXiv 2024

  16. [16]

    The explicit game-theoretic linear quadratic regulator for constrained multi-agent systems

    E. Benenati and G. Belgioioso, “The explicit game-theoretic lin- ear quadratic regulator for constrained multi-agent systems,”arXiv preprint arXiv:2512.07749, 2025

    work page internal anchor Pith review Pith/arXiv arXiv 2025

  17. [17]

    A high-performant multi-parametric quadratic programming solver,

    D. Arnstr ¨om and D. Axehill, “A high-performant multi-parametric quadratic programming solver,” in2024 IEEE 63rd Conference on Decision and Control (CDC). IEEE, 2024, pp. 303–308

    work page 2024

  18. [18]

    A dual active-set solver for embedded quadratic programming using recursive LDL t updates,

    D. Arnstr ¨om, A. Bemporad, and D. Axehill, “A dual active-set solver for embedded quadratic programming using recursive LDL t updates,” IEEE Transactions on Automatic Control, vol. 67, no. 8, pp. 4362– 4369, 2022

    work page 2022

  19. [19]

    NashOpt-a Python library for computing generalized Nash equilibria,

    A. Bemporad, “NashOpt-a Python library for computing generalized Nash equilibria,”arXiv preprint arXiv:2512.23636, 2025

    work page arXiv 2025

  20. [20]

    Clarabel: An interior-point solver for conic programs with quadratic objectives,

    P. J. Goulart and Y . Chen, “Clarabel: An interior-point solver for conic programs with quadratic objectives,”arXiv preprint arXiv:2405.12762, 2024

    work page arXiv 2024

  21. [21]

    Solving asymmetric variational inequalities via convex optimization,

    M. Aghassi, D. Bertsimas, and G. Perakis, “Solving asymmetric variational inequalities via convex optimization,”Operations Research Letters, vol. 34, no. 5, pp. 481–490, 2006

    work page 2006

  22. [22]

    Linear-Quadratic Dynamic Games as Receding-Horizon Variational Inequalities,

    E. Benenati and S. Grammatico, “Linear-Quadratic Dynamic Games as Receding-Horizon Variational Inequalities,”IEEE Transactions on Automatic Control, pp. 1–16, 2026 (accepted)

    work page 2026

  23. [23]

    S. S. Sastry,Nonlinear Systems: Analysis, Stability, and Control. Springer Science & Business Media, 2013

    work page 2013

  24. [24]

    The ex- plicit linear quadratic regulator for constrained systems,

    A. Bemporad, M. Morari, V . Dua, and E. N. Pistikopoulos, “The ex- plicit linear quadratic regulator for constrained systems,”Automatica, vol. 38, pp. 3–20, 2002

    work page 2002