pith. sign in

arxiv: 2504.05757 · v2 · submitted 2025-04-08 · 📡 eess.SY · cs.SY· math.OC

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

Reza Rahimi Baghbadorani , Emilio Benenati , Sergio Grammatico This is my paper

Pith reviewed 2026-05-22 20:35 UTC · model grok-4.3

classification 📡 eess.SY cs.SYmath.OC
keywords Douglas-Rachford splittingvariational inequalitiesdynamic gameslinear-quadratic gamesmonotone operatorsreceding-horizon controlgame equilibriaautomated driving
0
0 comments X

The pith

Douglas-Rachford splitting applied to affine variational inequalities from constrained linear-quadratic dynamic games yields an algorithm with linear convergence and closed-form solutions near the attractor.

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

This paper establishes that constrained linear dynamic games with quadratic objective functions can be recast as affine variational inequalities and solved via Douglas-Rachford splitting. The approach exploits the problem structure to obtain linear convergence without extra assumptions on the game matrices. The resulting speed supports receding-horizon control, while a closed-form solution near the attractor further reduces computation. A sympathetic reader would care because these rates make equilibrium computation practical in real-time multi-agent settings such as automated driving.

Core claim

By leveraging the linear-quadratic structure of constrained dynamic games, the Douglas-Rachford splitting generates a solution algorithm for the associated affine variational inequality with linear convergence rate. This enables receding-horizon control architectures. The paper also demonstrates that the VI admits a closed-form solution within a neighborhood of the attractor, allowing further reduction in computation time, as validated through numerical experiments in an automated driving application.

What carries the argument

Douglas-Rachford splitting operator applied to the monotone affine variational inequality arising from the linear-quadratic game.

If this is right

  • Linear convergence enables real-time receding-horizon implementations of the game equilibria.
  • Closed-form solutions near the attractor cut computation time beyond the splitting iterations alone.
  • The method applies directly to constrained linear-quadratic games without requiring extra matrix assumptions.
  • Benchmark results in automated driving confirm practical feasibility of the algorithm.

Where Pith is reading between the lines

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

  • The linear rate and closed-form neighborhood together suggest hybrid solvers that switch to the analytic expression once iterates enter the neighborhood.
  • The same splitting structure might be reused for sensitivity analysis or warm-starting across successive receding-horizon steps.
  • If monotonicity is preserved locally around equilibria in mildly nonlinear extensions, the same convergence guarantees could apply with only local linearization.

Load-bearing premise

The variational inequality remains monotone and the linear-quadratic structure is preserved under the chosen constraints so that standard Douglas-Rachford convergence theory delivers a linear rate without additional assumptions on the game matrices.

What would settle it

A numerical run on a linear-quadratic game instance in which the number of iterations required to reach a given tolerance fails to decrease linearly with the tolerance would falsify the claimed linear convergence.

Figures

Figures reproduced from arXiv: 2504.05757 by Emilio Benenati, Reza Rahimi Baghbadorani, Sergio Grammatico.

Figure 1
Figure 1. Figure 1: Comparison of residuals for different state-of-the-art [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Block scheme of the closed-loop dynamics with [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Simulated scenario. The full animation is available at [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: (a): Distance between χ(i) and i. (b): Velocity of each agent. The dotted lines denote the reference values, and the red dashed lines denote the constraints. 0 10 20 30 40 100 102 104 106 [PITH_FULL_IMAGE:figures/full_fig_p007_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Number of iterations to achieve convergence of the [PITH_FULL_IMAGE:figures/full_fig_p007_5.png] view at source ↗
read the original abstract

This paper considers constrained linear dynamic games with quadratic objective functions, which can be cast as affine variational inequalities. By leveraging the problem structure, we apply the Douglas-Rachford splitting, which generates a solution algorithm with linear convergence rate. The fast convergence of the method enables receding-horizon control architectures. Furthermore, we demonstrate that {the associated VI admits a closed-form solution within a neighborhood of the attractor, thus allowing for a further reduction in computation time.} Finally, we benchmark the proposed method via numerical experiments in an automated driving application.

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 / 0 minor

Summary. The paper formulates constrained linear-quadratic dynamic games as affine variational inequalities and applies Douglas-Rachford splitting, claiming that the method achieves linear convergence by exploiting the problem structure. It further asserts that the VI admits a closed-form solution in a neighborhood of the attractor and validates the approach through numerical experiments on an automated driving receding-horizon control task.

Significance. If the linear convergence result is rigorously established under the stated monotonicity assumption, the work would offer a computationally efficient solver for dynamic games, supporting real-time receding-horizon implementations in control applications.

major comments (2)
  1. [Abstract and convergence analysis] Abstract and convergence analysis: the claim that Douglas-Rachford splitting yields linear convergence by leveraging the LQ structure is load-bearing for the central contribution. Standard DR theory on monotone operators guarantees only weak convergence; linear rates require strong monotonicity or an explicit contraction factor strictly less than 1. The manuscript must state the precise conditions on the game cost matrices (or constraint sets) that ensure this, or provide a counter-example when the operator is merely monotone (positive semi-definite but not definite).
  2. [Closed-form solution claim] Closed-form solution claim: the assertion that the associated VI admits a closed-form solution within a neighborhood of the attractor lacks a definition of the neighborhood radius, the explicit closed-form expression, and the derivation showing how the LQ structure produces it. This step is required to justify the claimed further reduction in computation time.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on the convergence analysis and closed-form solution claim. We address each point below and will revise the manuscript to incorporate the requested clarifications and details.

read point-by-point responses

  1. Referee: [Abstract and convergence analysis] Abstract and convergence analysis: the claim that Douglas-Rachford splitting yields linear convergence by leveraging the LQ structure is load-bearing for the central contribution. Standard DR theory on monotone operators guarantees only weak convergence; linear rates require strong monotonicity or an explicit contraction factor strictly less than 1. The manuscript must state the precise conditions on the game cost matrices (or constraint sets) that ensure this, or provide a counter-example when the operator is merely monotone (positive semi-definite but not definite).

    Authors: We agree that the linear convergence claim requires explicit conditions. The affine VI operator arising from the LQ game is strongly monotone precisely when the quadratic cost matrices are positive definite (ensuring the Hessian of the game is positive definite). We will add a theorem in Section 3 stating these conditions on the cost matrices and deriving the contraction factor <1 for the DR iteration. When the costs are only positive semi-definite, we will add a remark that convergence reduces to weak convergence in general and include a brief counter-example (a simple 2-player game with semi-definite costs) to illustrate the distinction. revision: yes

  2. Referee: [Closed-form solution claim] Closed-form solution claim: the assertion that the associated VI admits a closed-form solution within a neighborhood of the attractor lacks a definition of the neighborhood radius, the explicit closed-form expression, and the derivation showing how the LQ structure produces it. This step is required to justify the claimed further reduction in computation time.

    Authors: We acknowledge the need for additional rigor on this claim. The closed-form solution holds in a neighborhood of the attractor where the active-set of the projection operator stabilizes due to the linear dynamics and quadratic costs. In the revision we will: (i) define the neighborhood radius explicitly as the distance at which the KKT conditions become linear (computed from the Lipschitz constant of the operator), (ii) state the closed-form expression as the solution of the resulting linear system (inverse of the monotone matrix plus projection), and (iii) provide the derivation showing how the LQ structure reduces the resolvent to this linear solve. This will be added to Section 4. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper casts constrained LQ dynamic games as affine variational inequalities and applies Douglas-Rachford splitting, asserting linear convergence via problem structure and standard monotone operator theory. No self-definitional reductions, fitted inputs renamed as predictions, or load-bearing self-citations appear in the abstract or described claims. The central steps rest on external monotone operator results without reducing by construction to the authors' own prior inputs or fitted quantities. This is the expected honest non-finding for a methods paper grounded in established theory.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claims rest on standard properties of monotone operators and the Douglas-Rachford operator; no new free parameters, ad-hoc axioms, or invented entities are introduced in the abstract.

axioms (2)
  • domain assumption The variational inequality is monotone.
    Required for Douglas-Rachford convergence theory to apply with linear rate.
  • domain assumption The linear-quadratic structure is preserved under the chosen constraints.
    Allows casting the dynamic game as an affine VI.

pith-pipeline@v0.9.0 · 5630 in / 1011 out tokens · 46851 ms · 2026-05-22T20:35:02.593387+00:00 · methodology

discussion (0)

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

Forward citations

Cited by 3 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Fast Newton methods for linear-quadratic dynamic games with application to autonomous vehicle platooning and intersection crossing

    math.OC 2026-05 unverdicted novelty 7.0

    Newton methods for linear-quadratic dynamic games achieve local quadratic convergence via reformulation as affine variational inequalities, outperforming first-order methods in vehicle coordination simulations.

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

    eess.SY 2026-04 unverdicted novelty 7.0

    DR-DAQP is a hybrid solver using operator splitting and active-set methods that solves affine variational inequalities exactly in finite time under specified conditions and runs up to two orders of magnitude faster th...

  3. A Hybrid Algorithm for Monotone Variational Inequalities

    math.OC 2026-04 unverdicted novelty 5.0

    Hybrid momentum-switching algorithms improve convergence speed over standard aGRAAL for monotone variational inequalities.

Reference graph

Works this paper leans on

27 extracted references · 27 canonical work pages · cited by 3 Pith papers · 1 internal anchor

  1. [1]

    Bas ¸ar and G

    T. Bas ¸ar and G. J. Olsder, Dynamic Noncooperative Game Theory , 2nd ed., ser. Classics in Applied Mathematics. Philadelphia: SIAM, 1999, no. 23

    work page 1999

  2. [2]

    Haurie, J

    A. Haurie, J. B. Krawczyk, and G. Zaccour, Games and dynamic games. World Scientific Publishing Company, 2012, vol. 1

    work page 2012

  3. [3]

    Output-feedback mixed H-infinity and H-2 control – a dynamic game approach,

    Y . Theodor and U. Shaked, “Output-feedback mixed H-infinity and H-2 control – a dynamic game approach,” International Journal of Control, vol. 64, no. 2, pp. 263–279, May 1996

    work page 1996

  4. [4]

    Game- Theoretic Planning for Self-Driving Cars in Multivehicle Competitive Scenarios,

    M. Wang, Z. Wang, J. Talbot, J. C. Gerdes, and M. Schwager, “Game- Theoretic Planning for Self-Driving Cars in Multivehicle Competitive Scenarios,” IEEE Transactions on Robotics , vol. 37, no. 4, pp. 1313– 1325, Aug. 2021

    work page 2021

  5. [5]

    A Real-Time Game Theoretic Planner for Autonomous Two-Player Drone Racing,

    R. Spica, E. Cristofalo, Z. Wang, E. Montijano, and M. Schwager, “A Real-Time Game Theoretic Planner for Autonomous Two-Player Drone Racing,” IEEE Transactions on Robotics , vol. 36, no. 5, pp. 1389–1403, Oct. 2020

    work page 2020

  6. [6]

    Receding horizon games with coupling constraints for demand-side manage- ment,

    S. Hall, G. Belgioioso, D. Liao-McPherson, and F. Dorfler, “Receding horizon games with coupling constraints for demand-side manage- ment,” in 2022 IEEE 61st Conference on Decision and Control (CDC), 2022, pp. 3795–3800

    work page 2022

  7. [7]

    Game- theoretic model predictive control for modelling competitive supply chains,

    S. Hall, L. Guerrini, F. D ¨orfler, and D. Liao-McPherson, “Game- theoretic model predictive control for modelling competitive supply chains,” arXiv e-prints, pp. arXiv–2401, 2024

    work page 2024

  8. [8]

    Feedback and open-loop nash equilibria for lq infinite-horizon discrete-time dynamic games,

    A. Monti, B. Nortmann, T. Mylvaganam, and M. Sassano, “Feedback and open-loop nash equilibria for lq infinite-horizon discrete-time dynamic games,” SIAM Journal on Control and Optimization , vol. 62, no. 3, pp. 1417–1436, 2024

    work page 2024

  9. [9]

    Constructive design of open-loop nash equilibrium strategies that admit a feedback synthesis in lq games,

    M. Sassano and A. Astolfi, “Constructive design of open-loop nash equilibrium strategies that admit a feedback synthesis in lq games,” Automatica, vol. 133, p. 109840, 2021

    work page 2021

  10. [10]

    Linear-quadratic dynamic games as receding-horizon variational inequalities,

    E. Benenati and S. Grammatico, “Linear-quadratic dynamic games as receding-horizon variational inequalities,” arXiv preprint arXiv:2408.15703, 2024

    work page arXiv 2024

  11. [11]

    Facchinei and J.-S

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

    work page 2003

  12. [12]

    Problem complexity and method efficiency in optimization,

    A. S. Nemirovskij and D. B. Yudin, “Problem complexity and method efficiency in optimization,” 1983

    work page 1983

  13. [13]

    An extragradient algorithm for monotone variational inequalities,

    Y . V . Malitsky and V . Semenov, “An extragradient algorithm for monotone variational inequalities,” Cybernetics and Systems Analysis , vol. 50, no. 2, pp. 271–277, 2014

    work page 2014

  14. [14]

    Solving strongly monotone variational and quasi-variational inequalities,

    Y . Nesterov, L. Scrimali et al., “Solving strongly monotone variational and quasi-variational inequalities,” CORE, Tech. Rep., 2006

    work page 2006

  15. [15]

    Projected reflected gradient methods for monotone variational inequalities,

    Y . Malitsky, “Projected reflected gradient methods for monotone variational inequalities,”SIAM Journal on Optimization, vol. 25, no. 1, pp. 502–520, 2015

    work page 2015

  16. [16]

    Golden ratio algorithms for variational inequalities,

    ——, “Golden ratio algorithms for variational inequalities,” Mathe- matical Programming, vol. 184, no. 1, pp. 383–410, 2020

    work page 2020

  17. [17]

    Discrete-Time Riccati Equations in Open-Loop Nash and Stackelberg Games,

    G. Freiling, G. Jank, and H. Abou-Kandil, “Discrete-Time Riccati Equations in Open-Loop Nash and Stackelberg Games,” European Journal of Control , 1999

    work page 1999

  18. [18]

    Toward infinite-horizon optimality in nonlinear model predictive control,

    Bei Hu and A. Linnemann, “Toward infinite-horizon optimality in nonlinear model predictive control,” IEEE Transactions on Automatic Control, vol. 47, no. 4, pp. 679–682, Apr. 2002

    work page 2002

  19. [19]

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

    M. Ferris and J. Eckstein, “Operator splitting methods for monotone affine variational inequalities, with parallel application to optimal control,” Tech. Rep., 1996

    work page 1996

  20. [20]

    , author Banjac, G

    B. Stellato, G. Banjac, P. Goulart, A. Bemporad, and S. Boyd, “OSQP: an operator splitting solver for quadratic programs,” Mathematical Programming Computation , vol. 12, no. 4, pp. 637–672, 2020. [Online]. Available: https://doi.org/10.1007/s12532-020-00179-2

    work page doi:10.1007/s12532-020-00179-2 2020

  21. [21]

    H. H. Bauschke and P. L. Combettes, Convex Analysis and Monotone Operator Theory in Hilbert Spaces . Springer, 2017

    work page 2017

  22. [22]

    Tight global linear convergence rate bounds for douglas– rachford splitting,

    P. Giselsson, “Tight global linear convergence rate bounds for douglas– rachford splitting,” Journal of Fixed Point Theory and Applications , vol. 19, no. 4, pp. 2241–2270, 2017

    work page 2017

  23. [23]

    Douglas-Rachford splitting for a Lipschitz continuous and a strongly monotone operator

    W. Moursi and L. Vandenberghe, “Douglas–rachford splitting for a lipschitz continuous and a strongly monotone operator (2018),” arXiv preprint arXiv:1805.09396

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  24. [24]

    A unified distributed method for constrained networked optimization via saddle-point dynamics,

    Y . Huang, Z. Meng, J. Sun, and W. Ren, “A unified distributed method for constrained networked optimization via saddle-point dynamics,” IEEE Transactions on Automatic Control , vol. 69, no. 3, pp. 1818– 1825, 2023

    work page 2023

  25. [25]

    A game–theoretic approach for gener- ative adversarial networks,

    B. Franci and S. Grammatico, “A game–theoretic approach for gener- ative adversarial networks,” in 2020 59th IEEE conference on decision and control (CDC) . IEEE, 2020, pp. 1646–1651

    work page 2020

  26. [26]

    Semi-decentralized generalized nash equilibrium seeking in monotone aggregative games,

    G. Belgioioso and S. Grammatico, “Semi-decentralized generalized nash equilibrium seeking in monotone aggregative games,” IEEE Transactions on Automatic Control, vol. 68, no. 1, pp. 140–155, 2021

    work page 2021

  27. [27]

    monviso: A Python package for solving monotone variational inequalities,

    N. Mignoni, R. Rahimi Baghbadorani, P. Mohajerin Esfahani, R. Carli, M. Dotoli, and S. Grammatico, “ monviso: A Python package for solving monotone variational inequalities,” in 2025 European Control Conference (ECC). IEEE, 2025 (accepted)

    work page 2025