Operator splitting for a homogeneous embedding of the linear\n complementarity problem

2020/04/05 by Brendan O’Donoghue, O'Donoghue, Brendan · 18 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)

paper · pdf · doi:10.48550/arxiv.2004.02177

openalex publication_date 2020/04/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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

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

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\n Inclusions Involving Three Operators
• Clarabel: An interior-point solver for conic programs with quadratic objectives