Operator splitting for a homogeneous embedding of the linear complementarity problem

2020/04/05 by Brendan O'Donoghue, Brendan O’Donoghue, O'Donoghue, Brendan · 29 citations
Business, Management and Accounting · Decision Sciences · Mathematics · #Advanced Optimization Algorithms Research #FOS: Mathematics #Facility Location and Emergency Management #Multi-Criteria Decision Making #Optimization and Control (math.OC) #math.OC

paper · pdf · doi:10.48550/arxiv.2004.02177

openalex publication_date 2020/04/05 · arxiv created 2021/06/12 · arxiv updated 2021/06/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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.

Cited by

• Large-scale Lindblad learning from time-series data
• Data-Driven Analysis of First-Order Methods via Distributionally Robust Optimization
• Verification of Sequential Convex Programming for Parametric Non-convex Optimization
• Krylov Subspace Acceleration for First-Order Splitting Methods in Convex Quadratic Programming
• Nonparametric Robust Comparison of Solutions under Input Uncertainty
• Artificial-reference tracking MPC with probabilistically validated performance on industrial embedded systems
• Projections onto Spectral Matrix Cones
• GFORS: GPU-Accelerated First-Order Method with Randomized Sampling for Binary Integer Programs
• Empirical bounds for commuting dilations of free unitaries and the universal commuting dilation constant
• On the Relationships among GPU-Accelerated First-Order Methods for Solving Linear Programming
• From GPUs to RRAMs: Distributed In-Memory Primal-Dual Hybrid Gradient Method for Solving Large-Scale Linear Optimization Problem
• Differentiating Through a Quadratic Cone Program
• SSNCVX: A primal-dual semismooth Newton method for convex composite optimization problem
• Large-Scale Network Utility Maximization via GPU-Accelerated Proximal Message Passing
• Efficient Convex Optimization for Bosonic State Tomography
• Solving Quadratic Programs via Deep Unrolled Douglas-Rachford Splitting
• Onboard Dual Quaternion Guidance for Rocket Landing
• Quadratic Programming-Based Posture Manipulation and Thrust-vectoring for Agile Dynamic Walking on Narrow Pathways
• Learning Acceleration Algorithms for Fast Parametric Convex Optimization with Certified Robustness
• HPR-QP: A dual Halpern Peaceman-Rachford method for solving large-scale convex composite quadratic programming
• An Overview of GPU-based First-Order Methods for Linear Programming and Extensions
• FSNet: Feasibility-Seeking Neural Network for Constrained Optimization with Guarantees
• Collision-free Control Barrier Functions for General Ellipsoids via Separating Hyperplane
• Scalable and adaptive prediction bands with kernel sum-of-squares
• New Understandings and Computation on Augmented Lagrangian Methods for Low-Rank Semidefinite Programming
• Customized Interior-Point Methods Solver for Embedded Real-Time Convex Optimization
• A Learning-Based Inexact ADMM for Solving Quadratic Programs
• PDCS: A Primal-Dual Large-Scale Conic Programming Solver with GPU Enhancements
• Structured Differentiable Optimization for Efficient Decision-focused Learning in Power Systems

Related

• Forward-partial inverse-half-forward splitting algorithm for solving monotone inclusions
• Fast Solutions to Projective Monotone Linear Complementarity Problems
• Four Operator Splitting via a Forward-Backward-Half-Forward Algorithm with Line Search
• Asymmetric Forward-Backward-Adjoint Splitting for Solving Monotone Inclusions Involving Three Operators
• Clarabel: An interior-point solver for conic programs with quadratic objectives