# Operator splitting for a homogeneous embedding of the linear complementarity problem

arXiv: https://arxiv.org/abs/2004.02177 · HTML: https://mlsanity.com/paper/2004.02177/

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Apr 2020.

## Built on by (most cited first, 21 of 21)

- [Learning to Warm-Start Fixed-Point Optimization Algorithms](https://mlsanity.com/paper/2309.07835/) (2023)
- [FSNet: Feasibility-Seeking Neural Network for Constrained Optimization with Guarantees](https://mlsanity.com/paper/2506.00362/) (2025)
- [PDHG-Unrolled Learning-to-Optimize Method for Large-Scale Linear Programming](https://mlsanity.com/paper/2406.01908/) (2024)
- [Probabilistic Inference in Reinforcement Learning Done Right](https://mlsanity.com/paper/2311.13294/) (2023)
- [BPQP: A Differentiable Convex Optimization Framework for Efficient End-to-End Learning](https://mlsanity.com/paper/2411.19285/) (2024)
- [Diff-Explainer: Differentiable Convex Optimization for Explainable Multi-hop Inference](https://mlsanity.com/paper/2105.03417/) (2021)
- [Variational Bayesian Optimistic Sampling](https://mlsanity.com/paper/2110.15688/) (2021)
- [Fast quantum state reconstruction via accelerated non-convex programming](https://mlsanity.com/paper/2104.07006/) (2021)
- [Data-Driven Performance Guarantees for Classical and Learned Optimizers](https://mlsanity.com/paper/2404.13831/) (2024)
- [Feasible Learning](https://mlsanity.com/paper/2501.14912/) (2025)
- [An Efficient Unsupervised Framework for Convex Quadratic Programs via Deep Unrolling](https://mlsanity.com/paper/2412.01051/) (2024)
- [DFWLayer: Differentiable Frank-Wolfe Optimization Layer](https://mlsanity.com/paper/2308.10806/) (2023)
- [Gradient boosting for convex cone predict and optimize problems](https://mlsanity.com/paper/2204.06895/) (2022)
- [An information-matching approach to optimal experimental design and active learning](https://mlsanity.com/paper/2411.02740/) (2024)
- [Dual NUP Representations and Min-Maximization in Factor Graphs](https://mlsanity.com/paper/2501.12113/) (2025)
- [Scalable and adaptive prediction bands with kernel sum-of-squares](https://mlsanity.com/paper/2505.21039/) (2025)
- [Batched First-Order Methods for Parallel LP Solving in MIP](https://mlsanity.com/paper/2601.21990/) (2026)
- [On the Expressive Power of GNNs to Solve Linear SDPs](https://mlsanity.com/paper/2604.27786/) (2026)
- [Solving Max-Cut to Global Optimality via Feasibility-Preserving Graph Neural Networks](https://mlsanity.com/paper/2605.07113/) (2026)
- [Randomized Approach to Matrix Completion: Applications in Recommendation Systems and Image Inpainting](https://mlsanity.com/paper/2403.01919/) (2024)
- [SCaLE: Switching Cost aware Learning and Exploration](https://mlsanity.com/paper/2601.09042/) (2026)

## Abstract (arXiv)

The linear complementarity problem (LCP) is a general set membership problem that includes quadratic cone programming as a special case. In this work we consider a homogeneous embedding of the LCP, which encodes both the optimality conditions of the original LCP as well as certificates of infeasibility. The resulting problem can be expressed as a monotone inclusion problem involving the sum of two maximal monotone operators, to which we apply Douglas-Rachford splitting. The resulting algorithm has almost identical per-iteration cost as applying the splitting to the LCP directly. Specifically, each iteration requires solving a linear system and projecting onto a convex cone. The resulting algorithm has no explicit hyper-parameters and is able to return a primal-dual solution should one exist or a certificate of infeasibility otherwise. If a sequence of related problems are solved it can easily be warm-started and make use of factorization caching of the linear system. We demonstrate on a range of public and synthetic datasets that for feasible problems our approach tends to be somewhat faster than applying operator splitting directly to the LCP, and in cases of infeasibility our approach can be significantly faster than alternative approaches based on diverging iterates. The algorithm we describe has been implemented in C and is available open-source as SCS-3.0.