pith. sign in

arxiv: 2604.11991 · v2 · submitted 2026-04-13 · 💻 cs.RO

Complementarity by Construction: A Lie-Group Approach to Solving Quadratic Programs with Linear Complementarity Constraints

Arun L. Bishop , Micah I. Reich , Zachary Manchester This is my paper

Pith reviewed 2026-05-10 15:42 UTC · model grok-4.3

classification 💻 cs.RO
keywords linear complementarity quadratic programsLie groupson-manifold optimizationcontact constraintsrobotics planningretraction mapquadratic programming
0
0 comments X

The pith

Complementarity constraints in LCQPs can be satisfied by construction using a Lie-group retraction map for on-manifold optimization.

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

The paper establishes that linear complementarity constraints form a Lie group under infinitesimal relaxation. This structure supports an on-manifold optimization approach where a retraction map parameterizes the variables so the constraints hold automatically. The resulting method sidesteps many numerical difficulties of standard LCQP solvers. It is packaged in the open-source Marble solver and shown to handle robotics contact problems where other techniques fail to converge.

Core claim

Complementarity constraints form a Lie group under infinitesimal relaxation. A numerically stable retraction map is introduced to parameterize solutions so that the constraints are satisfied by construction during the optimization process.

What carries the argument

The retraction map that sends elements of the Lie algebra to the Lie group manifold of complementarity constraints, thereby enforcing the conditions automatically.

If this is right

  • LCQPs can be optimized without explicit enforcement of complementarity at every iteration.
  • The solver avoids classical failure modes such as cycling or non-convergence on contact problems.
  • Robotics planning pipelines gain a reliable local solver for mixed continuous-discrete dynamics.
  • The open-source Marble implementation is competitive on existing benchmarks and succeeds where prior methods fail.

Where Pith is reading between the lines

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

  • The Lie-group perspective could extend to other hybrid-system constraints that admit similar infinitesimal group structures.
  • On-manifold parameterization may improve real-time stability in robotic control loops involving repeated contact decisions.
  • If analogous group structures exist for nonlinear complementarity problems, the retraction technique might generalize beyond linear cases.

Load-bearing premise

That complementarity constraints truly form a Lie group under infinitesimal relaxation and that the retraction map stays numerically stable without biasing solutions or creating new convergence problems.

What would settle it

If applying the retraction map on standard benchmark LCQPs produces divergence or systematically biased solutions while classical solvers converge, the core claim would be refuted.

Figures

Figures reproduced from arXiv: 2604.11991 by Arun L. Bishop, Micah I. Reich, Zachary Manchester.

Figure 1
Figure 1. Figure 1: Quadratic programs with linear complementarity constraints can model a wide variety of robotics problems with non [PITH_FULL_IMAGE:figures/full_fig_p001_1.png] view at source ↗
Figure 3
Figure 3. Figure 3: Relaxed complementarity feasible sets for different [PITH_FULL_IMAGE:figures/full_fig_p003_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Total problems solved versus performance ratio (solve [PITH_FULL_IMAGE:figures/full_fig_p005_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Hopper trajectory with contact forces (red arrows). [PITH_FULL_IMAGE:figures/full_fig_p007_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Gate traversal trajectory with progress constraints. [PITH_FULL_IMAGE:figures/full_fig_p007_6.png] view at source ↗
read the original abstract

Many problems in robotics require reasoning over a mix of continuous dynamics and discrete events, such as making and breaking contact in manipulation and locomotion. These problems are locally well modeled by linear complementarity quadratic programs (LCQPs), an extension to QPs that introduce complementarity constraints. While very expressive, LCQPs are non-convex, and few solvers exist for computing good local solutions for use in planning pipelines. In this work, we observe that complementarity constraints form a Lie group under infinitesimal relaxation, and leverage this structure to perform on-manifold optimization. We introduce a retraction map that is numerically well behaved, and use it to parameterize the constraints so that they are satisfied by construction. The resulting solver avoids many of the classical issues with complementarity constraints. We provide an open-source solver, Marble, that is implemented in C++ with Julia and Python bindings. We demonstrate that Marble is competitive on a suite of benchmark problems, and solves a number of robotics problems where existing approaches fail to converge.

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

Summary. The paper claims that complementarity constraints in LCQPs form a Lie group under infinitesimal relaxation, enabling on-manifold optimization via a newly introduced retraction map that parameterizes the constraints so they hold by construction. This avoids classical complementarity issues in non-convex QPs. The authors release an open-source C++ solver Marble (with Julia/Python bindings) and report that it is competitive on benchmarks while succeeding on robotics problems where existing solvers fail to converge.

Significance. If the Lie-group structure and retraction properties are rigorously verified, the approach could provide a principled alternative for handling contact-rich problems in robotics planning and control, reducing reliance on heuristic relaxations or penalty methods. The open-source implementation with multi-language bindings is a clear strength for reproducibility and adoption.

major comments (2)
  1. [Lie-group observation and retraction construction] The central claim that complementarity constraints form a Lie group under infinitesimal relaxation (and the subsequent on-manifold parameterization) requires an explicit definition of the group operation, identity element, and inverses, together with verification that the structure is closed under the proposed relaxation; this is load-bearing for the entire method and is not fully derived in the provided description.
  2. [Retraction map definition and numerical properties] The retraction map is stated to be numerically well behaved and to satisfy the constraints by construction, but the manuscript must demonstrate that it meets the standard retraction axioms R(0) = x and DR(0) = Id, and must bound or empirically measure manifold drift under finite integration steps; without this, the 'by construction' guarantee can fail and classical complementarity pathologies reappear.
minor comments (2)
  1. [Abstract] The abstract asserts competitiveness and success on failure cases but supplies no quantitative metrics (e.g., solve times, success rates, or specific benchmark identifiers); adding a concise table or sentence would strengthen the claim.
  2. [Notation and preliminaries] Notation for the relaxed complementarity set and the infinitesimal generator should be introduced with a small example or diagram to clarify how the Lie-algebra parameterization maps back to the original variables.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their constructive and detailed comments. We agree that the Lie-group structure and retraction properties require more explicit derivation and verification to support the central claims. We address each major comment below and will revise the manuscript accordingly.

read point-by-point responses

  1. Referee: The central claim that complementarity constraints form a Lie group under infinitesimal relaxation (and the subsequent on-manifold parameterization) requires an explicit definition of the group operation, identity element, and inverses, together with verification that the structure is closed under the proposed relaxation; this is load-bearing for the entire method and is not fully derived in the provided description.

    Authors: We agree that the Lie-group observation is central and that the current description does not provide a complete derivation. In the revised manuscript we will insert a dedicated subsection that explicitly defines the group operation on the infinitesimally relaxed complementarity set, identifies the identity element and inverses, and proves closure under the relaxation. This will directly support the subsequent on-manifold parameterization. revision: yes

  2. Referee: The retraction map is stated to be numerically well behaved and to satisfy the constraints by construction, but the manuscript must demonstrate that it meets the standard retraction axioms R(0) = x and DR(0) = Id, and must bound or empirically measure manifold drift under finite integration steps; without this, the 'by construction' guarantee can fail and classical complementarity pathologies reappear.

    Authors: We acknowledge that the retraction axioms and drift behavior must be verified. The revised version will contain a short proof establishing that the proposed retraction satisfies R(0) = x and DR(0) = Id. We will also add numerical experiments that measure manifold drift over successive integration steps on the benchmark suite, thereby quantifying the numerical stability of the 'by construction' guarantee. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained via new Lie-group observation and retraction

full rationale

The paper's central derivation starts from the stated observation that complementarity constraints form a Lie group under infinitesimal relaxation, then defines a retraction map to parameterize the manifold so constraints hold by construction. This is not a self-definition (the group structure is not defined using the retraction or solver outputs), nor a fitted prediction (no parameters are fit to data and relabeled as predictions), nor reliant on self-citation chains for uniqueness or ansatzes. The retraction is introduced as an independent construction whose properties are asserted to be numerically well-behaved, with the solver then built around it. Benchmarks and open-source code provide external verifiability. No quoted equations or steps reduce the claimed result to its inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the domain assumption that complementarity constraints admit a Lie-group structure under relaxation; no free parameters or invented entities are mentioned in the abstract.

axioms (1)
  • domain assumption Complementarity constraints form a Lie group under infinitesimal relaxation
    Directly stated as the key observation enabling the on-manifold approach.

pith-pipeline@v0.9.0 · 5476 in / 1097 out tokens · 24569 ms · 2026-05-10T15:42:07.144936+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 1 Pith paper

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

  1. A Differentiable Interior-Point Method in Single Precision

    math.OC 2026-05 conditional novelty 6.0

    An alternative complementarity formulation for primal-dual interior-point methods keeps linear systems spectrally bounded near the solution, enabling stable single-precision solves and differentiation for bilevel and ...

Reference graph

Works this paper leans on

31 extracted references · 31 canonical work pages · cited by 1 Pith paper

  1. [1]

    Successive Convexification for Real-Time Six-Degree-of-Freedom Powered Descent Guidance with State-Triggered Constraints,

    M. Szmuk, T. P. Reynolds, and B. Ac ¸ıkmes ¸e, “Successive Convexification for Real-Time Six-Degree-of-Freedom Powered Descent Guidance with State-Triggered Constraints,”Journal of Guidance, Control, and Dynamics, vol. 43, no. 8, pp. 1399–1413, Aug

    work page

  2. [2]

    Available: https://arc.aiaa.org/doi/10.2514/1.G004549

    [Online]. Available: https://arc.aiaa.org/doi/10.2514/1.G004549

    work page doi:10.2514/1.g004549

  3. [3]

    MPEC Methods for Bilevel Optimization Problems,

    Y . Kim, S. Leyffer, and T. Munson, “MPEC Methods for Bilevel Optimization Problems,” inBilevel Optimization, S. Dempe and A. Zemkoho, Eds. Cham: Springer International Publishing, 2020, vol. 161, pp. 335–360, series Title: Springer Optimization and Its Applications. [Online]. Available: http://link.springer.com/10.1007/ 978-3-030-52119-6 12

    work page 2020

  4. [4]

    Nocedal and S

    J. Nocedal and S. J. Wright,Numerical Optimization, ser. Springer Series in Operations Research and Financial Engineering. Springer New York, 2006. [Online]. Available: http://link.springer.com/10. 1007/978-0-387-40065-5

    work page 2006

  5. [5]

    An Implicit Time-Stepping Scheme for Rigid Body Dynamics with Inelastic Collisions and Coulomb Fric- tion,

    D. E. Stewart and J. C. Trinkle, “An Implicit Time-Stepping Scheme for Rigid Body Dynamics with Inelastic Collisions and Coulomb Fric- tion,”International Journal for Numerical Methods in Engineering, vol. 39, no. 15, pp. 2673–2691, 1996

    work page 1996

  6. [6]

    Engineering and Economic Applications of Complementarity Problems,

    M. C. Ferris and J. S. Pang, “Engineering and Economic Applications of Complementarity Problems,”SIAM Review, vol. 39, no. 4, pp. 669–713, Jan. 1997. [Online]. Available: http://epubs.siam.org/doi/10. 1137/S0036144595285963

    work page 1997

  7. [7]

    A Class of Quadratic Programs with Linear Complementarity Constraints,

    X. Chen and J. J. Ye, “A Class of Quadratic Programs with Linear Complementarity Constraints,”Set-V alued and V ariational Analysis, vol. 17, no. 2, pp. 113–133, Jun. 2009. [Online]. Available: https://doi.org/10.1007/s11228-009-0112-5

    work page doi:10.1007/s11228-009-0112-5 2009

  8. [8]

    On convex quadratic programs with linear complementarity constraints,

    L. Bai, J. E. Mitchell, and J.-S. Pang, “On convex quadratic programs with linear complementarity constraints,”Computational Optimization and Applications, vol. 54, no. 3, pp. 517–554, Apr. 2013. [Online]. Available: https://doi.org/10.1007/s10589-012-9497-4

    work page doi:10.1007/s10589-012-9497-4 2013

  9. [9]

    The C-Index: A New Stability Concept for Quadratic Programs with Complementarity Constraints,

    D. Ralph and O. Stein, “The C-Index: A New Stability Concept for Quadratic Programs with Complementarity Constraints,”Mathematics of Operations Research, vol. 36, no. 3, pp. 504–526, 2011. [Online]. Available: https://www.jstor.org/stable/23012339

    work page arXiv 2011

  10. [10]

    CALIPSO: A Differentiable Solver for Trajectory Optimization with Conic and Complementarity Constraints,

    T. A. Howell, S. L. Cleac’h, K. Tracy, and Z. Manchester, “CALIPSO: A Differentiable Solver for Trajectory Optimization with Conic and Complementarity Constraints,” Jan. 2023, arXiv:2205.09255 [cs]. [Online]. Available: http://arxiv.org/abs/2205.09255

    work page arXiv 2023

  11. [11]

    Log-domain interior-point methods for convex quadratic programming,

    F. Permenter, “Log-domain interior-point methods for convex quadratic programming,”Optimization Letters, vol. 17, no. 7, pp. 1613–1631, Sep. 2023. [Online]. Available: https://doi.org/10.1007/ s11590-022-01952-z

    work page 2023

  12. [12]

    Luo, J.-S

    Z.-Q. Luo, J.-S. Pang, and D. Ralph,Mathematical Programs with Equilibrium Constraints. Cambridge University Press, Nov. 1996

    work page 1996

  13. [13]

    A micro Lie theory for state estimation in robotics,

    J. Sol `a, J. Deray, and D. Atchuthan, “A micro Lie theory for state estimation in robotics,” Dec. 2021, arXiv:1812.01537 [cs]. [Online]. Available: http://arxiv.org/abs/1812.01537

    work page arXiv 2021

  14. [14]

    Absil, R

    P.-A. Absil, R. Mahony, and R. Sepulchre,Optimization Algorithms on Matrix Manifolds. Princeton University Press, Apr. 2009

    work page 2009

  15. [15]

    Stillwell,Naive Lie Theory

    J. Stillwell,Naive Lie Theory. Springer Science & Business Media, Dec. 2008

    work page 2008

  16. [16]

    Planning With Attitude,

    B. E. Jackson, K. Tracy, and Z. Manchester, “Planning With Attitude,” IEEE Robotics and Automation Letters, vol. 6, no. 3, pp. 5658–5664, Jul. 2021. [Online]. Available: https://ieeexplore.ieee.org/document/ 9326337/

    work page 2021

  17. [17]

    Invariant Kalman Filtering,

    A. Barrau and S. Bonnabel, “Invariant Kalman Filtering,”Annual Review of Control, Robotics, and Autonomous Systems, vol. 1, no. 1, pp. 237–257, May 2018. [Online]. Available: https://www. annualreviews.org/doi/10.1146/annurev-control-060117-105010

    work page doi:10.1146/annurev-control-060117-105010 2018

  18. [18]

    An Interior Point Method for Mathematical Programs with Complementarity Constraints (MPCCs),

    A. U. Raghunathan and L. T. Biegler, “An Interior Point Method for Mathematical Programs with Complementarity Constraints (MPCCs),”SIAM Journal on Optimization, vol. 15, no. 3, pp. 720–750, Jan. 2005. [Online]. Available: http://epubs.siam.org/doi/10. 1137/S1052623403429081

    work page 2005

  19. [19]

    LCQPow – A Solver for Linear Complementarity Quadratic Programs,

    J. Hall, A. Nurkanovic, F. Messerer, and M. Diehl, “LCQPow – A Solver for Linear Complementarity Quadratic Programs,” Mathematical Programming Computation, vol. 17, no. 1, pp. 81–109, Mar. 2025, arXiv:2211.16341 [math]. [Online]. Available: http://arxiv.org/abs/2211.16341

    work page arXiv 2025

  20. [20]

    Gurobi Optimizer Reference Manual,

    Gurobi Optimization, LLC, “Gurobi Optimizer Reference Manual,”

    work page

  21. [21]

    Available: https://www.gurobi.com

    [Online]. Available: https://www.gurobi.com

    work page

  22. [22]

    Solving mathematical programs with complementarity constraints as nonlinear programs,

    R. Fletcher and S. Leyffer, “Solving mathematical programs with complementarity constraints as nonlinear programs,”Optimization Methods and Software, vol. 19, no. 1, pp. 15–40, Feb

    work page

  23. [23]

    Available: http://www.tandfonline.com/doi/abs/10

    [Online]. Available: http://www.tandfonline.com/doi/abs/10. 1080/10556780410001654241

    work page

  24. [24]

    SIAM Journal on Optimization 22(4), 1579-1606 (2012)

    A. F. Izmailov, M. V . Solodov, and E. I. Uskov, “Global Convergence of Augmented Lagrangian Methods Applied to Optimization Problems with Degenerate Constraints, Including Problems with Complementarity Constraints,”SIAM Journal on Optimization, vol. 22, no. 4, pp. 1579–1606, Jan. 2012. [Online]. Available: http://epubs.siam.org/doi/10.1137/120868359

    work page doi:10.1137/120868359 2012

  25. [25]

    On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming,

    A. W ¨achter and L. T. Biegler, “On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming,”Mathematical Programming, vol. 106, no. 1, pp. 25–57, Mar. 2006. [Online]. Available: https://doi.org/10.1007/ s10107-004-0559-y

    work page 2006

  26. [26]

    OSQP: An Operator Splitting Solver for Quadratic Programs,

    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, Dec. 2020, arXiv:1711.08013 [math]. [Online]. Available: http://arxiv.org/abs/1711.08013

    work page arXiv 2020

  27. [27]

    A scaling algorithm to equilibrate both rows and columns norms in matrices,

    D. Ruiz, “A scaling algorithm to equilibrate both rows and columns norms in matrices,” RAL, Oxon, UL, Technical RAL-TR-2001-034,

    work page 2001

  28. [28]

    Available: https://cds.cern.ch/record/585592

    [Online]. Available: https://cds.cern.ch/record/585592

    work page

  29. [29]

    MacMPEC: AMPL collection of MPECs

    S. Leyffer, “MacMPEC: AMPL collection of MPECs.” [Online]. Available: https://wiki.mcs.anl.gov/leyffer/index.php/MacMPEC

    work page

  30. [30]

    qpOASES: a parametric active-set algorithm for quadratic programming,

    H. J. Ferreau, C. Kirches, A. Potschka, H. G. Bock, and M. Diehl, “qpOASES: a parametric active-set algorithm for quadratic programming,”Mathematical Programming Computation, vol. 6, no. 4, pp. 327–363, Dec. 2014. [Online]. Available: https: //doi.org/10.1007/s12532-014-0071-1

    work page doi:10.1007/s12532-014-0071-1 2014

  31. [31]

    Science Robotics , author =

    P. Foehn, A. Romero, and D. Scaramuzza, “Time-optimal planning for quadrotor waypoint flight,”Science Robotics, vol. 6, no. 56, p. eabh1221, Jul. 2021. [Online]. Available: https://www.science.org/ doi/10.1126/scirobotics.abh1221

    work page doi:10.1126/scirobotics.abh1221 2021