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

• URL: http://arxiv.org/abs/2604.11991v1
• Date: Mon, 13 Apr 2026 19:31:41 GMT
• Title: Complementarity by Construction: A Lie-Group Approach to Solving Quadratic Programs with Linear Complementarity Constraints
• Abstract summary: Many problems in robotics require reasoning over a mix of continuous dynamics and discrete events.<n>We provide an opensource solver, Marble, that is implemented in C++ with Julia.
• Score: 9.967127506836453
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Translating finite-domain integer constraint models to CP/SMT/ILP/PB/SAT solvers with CPMpy [6.498850269638911]
  Constraint solving is a declarative approach for solving satisfaction and optimization problems.<n>Our goal is to translate high-level constraint satisfaction and optimization problems into any lower-level formalism.<n>We present a modular framework for transforming our high-level modeling language to CP/SMT/ILP/PB and (Max)SAT solvers.
  arXiv  Detail & Related papers  (2026-08-15T09:38:09Z)
• Constrained Stein Variational Gradient Descent for Robot Perception, Planning, and Identification [11.126853736828984]
  We present two novel frameworks for applying principles of constrained optimization to the new variational inference Stein variational descent.<n>We show that we can build distributions of: robot motion plans that exactly avoid collisions, robot arm joint angles on the SE(3) manifold with exact table placement constraints, and object poses from point clouds with table placement constraints.
  arXiv  Detail & Related papers  (2025-05-31T14:52:34Z)
• Single-loop Algorithms for Stochastic Non-convex Optimization with Weakly-Convex Constraints [49.76332265680669]
  This paper examines a crucial subset of problems where both the objective and constraint functions are weakly convex.<n>Existing methods often face limitations, including slow convergence rates or reliance on double-loop designs.<n>We introduce a novel single-loop penalty-based algorithm to overcome these challenges.
  arXiv  Detail & Related papers  (2025-04-21T17:15:48Z)
• Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization [72.41480594026815]
  Constrained optimization problems abound in industry, from portfolio optimization to logistics. One of the major roadblocks in solving these problems is the presence of non-trivial hard constraints which limit the valid search space. In this work, we encode arbitrary integer-valued equality constraints of the form Ax=b, directly into U(1) symmetric networks (TNs) and leverage their applicability as quantum-inspired generative models.
  arXiv  Detail & Related papers  (2022-11-16T18:59:54Z)
• Constrained mixers for the quantum approximate optimization algorithm [55.41644538483948]
  We present a framework for constructing mixing operators that restrict the evolution to a subspace of the full Hilbert space. We generalize the "XY"-mixer designed to preserve the subspace of "one-hot" states to the general case of subspaces given by a number of computational basis states. Our analysis also leads to valid Trotterizations for "XY"-mixer with fewer CX gates than is known to date.
  arXiv  Detail & Related papers  (2022-03-11T17:19:26Z)
• Constrained Machine Learning: The Bagel Framework [5.945320097465419]
  Constrained machine learning problems are problems where learned models have to both be accurate and respect constraints. The goal of this paper is to broaden the modeling capacity of constrained machine learning problems by incorporating existing work from optimization. Because machine learning has specific requirements, we also propose an extended table constraint to split the space of hypotheses.
  arXiv  Detail & Related papers  (2021-12-02T10:10:20Z)
• PYROBOCOP : Python-based Robotic Control & Optimization Package for Manipulation and Collision Avoidance [12.292075907844067]
  PYROBOCOP is a Python-based package for control and optimization of robotic systems. It can handle systems with contacts that are described by complementarity constraints.
  arXiv  Detail & Related papers  (2021-06-06T19:46:29Z)
• Solving weakly supervised regression problem using low-rank manifold regularization [77.34726150561087]
  We solve a weakly supervised regression problem. Under "weakly" we understand that for some training points the labels are known, for some unknown, and for others uncertain due to the presence of random noise or other reasons such as lack of resources. In the numerical section, we applied the suggested method to artificial and real datasets using Monte-Carlo modeling.
  arXiv  Detail & Related papers  (2021-04-13T23:21:01Z)
• An Integer Linear Programming Framework for Mining Constraints from Data [81.60135973848125]
  We present a general framework for mining constraints from data. In particular, we consider the inference in structured output prediction as an integer linear programming (ILP) problem. We show that our approach can learn to solve 9x9 Sudoku puzzles and minimal spanning tree problems from examples without providing the underlying rules.
  arXiv  Detail & Related papers  (2020-06-18T20:09:53Z)
• Competitive Mirror Descent [67.31015611281225]
  Constrained competitive optimization involves multiple agents trying to minimize conflicting objectives, subject to constraints. We propose competitive mirror descent (CMD): a general method for solving such problems based on first order information. As a special case we obtain a novel competitive multiplicative weights algorithm for problems on the positive cone.
  arXiv  Detail & Related papers  (2020-06-17T22:11:35Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.