Solving Quadratic Programs with Complementarity Constraints
Many problems in robotics require reasoning over a mix of continuous dynamics and discrete events, such as making and breaking contact. These problems are locally well modeled by quadratic programs with linear complementarity constraints (QPCCs), an extension to QPs that introduce complementarity constraints. While very expressive, QPCCs are non-convex, and few solvers can efficiently compute high-quality local solutions for planning or control.
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.
Marble is implemented in C++ with Julia and Python bindings. It is competitive on the MacMPEC benchmark suite, and solves robotics problems where existing approaches fail to converge.
Related Papers
|
2026 August |
Complementarity by Construction: A Lie-Group Approach to Solving Quadratic Programs with Linear Complementarity Constraints
Robotics Automation and Letters (RAL). (Accepted) |
People
Micah Reich
Arun Bishop
