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

A team from Carnegie Mellon University has published a paper introducing a novel solver named Marble, designed to crack a specific class of tough optimization problems central to robotics. These problems, called Linear Complementarity Quadratic Programs (LCQPs), are essential for modeling tasks where continuous motion interacts with discrete events, such as a robot hand making or breaking contact with an object. While expressive, LCQPs are non-convex and notoriously difficult to solve, with few reliable solvers available for real-time planning. The researchers' key insight was recognizing that the complementarity constraints at the heart of these problems form a mathematical structure known as a Lie group.

By leveraging this Lie-group structure, the team developed an "on-manifold" optimization technique. They created a special retraction map that allows the solver to parameterize the problem so the tricky complementarity constraints are automatically satisfied "by construction." This elegant mathematical approach sidesteps the numerical instability and convergence failures that plague classical methods. The result is Marble, an open-source solver implemented in C++ with bindings for Julia and Python. In tests, Marble proved competitive on standard benchmarks and successfully solved several complex robotics simulation problems where existing state-of-the-art solvers failed to find a solution, demonstrating its practical utility for advancing contact-rich robot planning and control.