cs.ROApr 13, 2026

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

Authors: Arun L. Bishop, Micah I. Reich, Zachary Manchester

Organizations: Authors are with the Robotics Institute, Carnegie Mellon University · Author is with the Department of Aeronautics and Astronautics, Massachusetts Institute of Technology

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

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.

Figures & tables

Fig. 2: Feasible sets of st=κst=\kappa and (s−t+2)(s+t−1)=κ(s-t+2)(s+t-1)=\kappa for varying κ\kappa . Three disjoint feasible points exist at κ=0\kappa=0 which reduces to one as κ\kappa grows.
Fig. 3: Relaxed complementarity feasible sets for different relaxation parameters. σ\sigma smoothly and globally parametrizes a feasible set for a fixed relaxation (black, red dot).
NameSymbolValue
Penalty Initialρ0\rho_{0}1010
Penalty Scalingγρ\gamma_{\rho}1010
Penalty Maxρmax\rho_{\mathrm{max}}10710^{7}
Relaxation Initialκ0\kappa_{0}0.10.1
Relaxation Scalingγκ\gamma_{\kappa}0.50.5
Relaxation Minκmin\kappa_{\mathrm{min}}10−910^{-9}
TABLE I: Solver parameters and their default values.
Fig. 4: Total problems solved versus performance ratio (solve time scaled by minimum time per problem) for each solver. Marble is the fastest for 72% of problems and is at most 4.85x slower.
Fig. 5: Hopper trajectory with contact forces (red arrows). The hopper is shaded red to indicate contact (signed distance ≤10−4\leq 10^{-4} m.
Fig. 6: Gate traversal trajectory with progress constraints. The quadrotor is shaded red to indicate timesteps where the progress control variable μ(j)\mu^{(j)} is equal to one for gate 1≤j≤41\leq j\leq 4 .
More in this topic

Constrained Optimization

Constrained optimization finds the best decisions while satisfying equality, inequality, resource, safety, or fairness requirements.

See all 333 papers

Explore similar work

CardsList

  1. MixedComplementarityProblems.jl: A Fast, Batched, Open-Source Interior Point Solver for Mixed Complementarity Problems

    Aug 2, 2026David Fridovich-KeilConstrained Optimization

    Department of Aerospace Engineering and Engineering Mechanics The University of Texas at Austin Austin, TX, USA

  2. ElastiQP: An Always-Feasible QP Solver for Constrained Robot Control

    Sep 16, 2026Daniel Morton, Jon Arrizabalaga, Zachary Manchester +1Robotic ControlConstrained Optimization

    Departments of Mechanical Engineering and Aeronautics & Astronautics, Stanford University, USA · Department of Aeronautics and Astronautics, Massachusetts Institute of Technology, USA

  3. CMC-Opt: Constraint Manifold with Corners for Inequality-Constrained Optimization

    May 20, 2026Yetong Zhang, Frank DellaertKinodynamic Motion PlanningRiemannian Optimization

    College of Computing Georgia Institute of Technology Atlanta, USA