Operator splitting for a homogeneous embedding of the linear complementarity problem
From MaRDI portal
ADMMcomplementarity problemscone programmingDouglas-Rachford splittingfirst-order methodshomogeneous embeddingsmonotone operatorsoperator splittingquadratic programming
Numerical mathematical programming methods (65K05) Numerical optimization and variational techniques (65K10) Linear programming (90C05) Large-scale problems in mathematical programming (90C06) Quadratic programming (90C20) Semidefinite programming (90C22) Convex programming (90C25) Nonlinear programming (90C30) Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) (90C33) Optimality conditions and duality in mathematical programming (90C46)
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.
Recommendations
- Conic optimization via operator splitting and homogeneous self-dual embedding
- OSQP: an operator splitting solver for quadratic programs
- COSMO: a conic operator splitting method for convex conic problems
- A computational study of the homogeneous algorithm for large-scale convex optimization
- On homogeneous and self-dual algorithms for LCP
Cites work
- A Modified Forward-Backward Splitting Method for Maximal Monotone Mappings
- A new use of Douglas-Rachford splitting for identifying infeasible, unbounded, and pathological conic programs
- A primer on monotone operator methods
- A repository of convex quadratic programming problems
- Advances in convex optimization: conic programming
- Alternating direction augmented Lagrangian methods for semidefinite programming
- An O(√nL)-Iteration Homogeneous and Self-Dual Linear Programming Algorithm
- Benchmarking optimization software with performance profiles.
- Branch-and-Bound Methods: A Survey
- Chordal decomposition in operator-splitting methods for sparse semidefinite programs
- Conic optimization via operator splitting and homogeneous self-dual embedding
- Convergence rate analysis of several splitting schemes
- Convex Analysis
- Convex analysis and monotone operator theory in Hilbert spaces
- CVXPY: a Python-embedded modeling language for convex optimization
- Direct Methods for Sparse Linear Systems
- Distributed optimization and statistical learning via the alternating direction method of multipliers
- Douglas-Rachford splitting for the sum of a Lipschitz continuous and a strongly monotone operator
- Fast alternating direction optimization methods
- Globally Convergent Type-I Anderson Acceleration for Nonsmooth Fixed-Point Iterations
- scientific article; zbMATH DE number 3833218 (Why is no real title available?)
- scientific article; zbMATH DE number 3121284 (Why is no real title available?)
- scientific article; zbMATH DE number 53115 (Why is no real title available?)
- scientific article; zbMATH DE number 192986 (Why is no real title available?)
- scientific article; zbMATH DE number 729680 (Why is no real title available?)
- scientific article; zbMATH DE number 2107836 (Why is no real title available?)
- scientific article; zbMATH DE number 780774 (Why is no real title available?)
- scientific article; zbMATH DE number 845714 (Why is no real title available?)
- scientific article; zbMATH DE number 5060482 (Why is no real title available?)
- Infeasibility detection in the alternating direction method of multipliers for convex optimization
- JuMP: a modeling language for mathematical optimization
- Linear Convergence and Metric Selection for Douglas-Rachford Splitting and ADMM
- Low-rank matrix completion using alternating minimization
- Monotone (nonlinear) operators in Hilbert space
- Monotone Operators and the Proximal Point Algorithm
- Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion
- On a homogeneous algorithm for the monotone complementarity problem
- On homogeneous and self-dual algorithms for LCP
- On the convergence rate of Douglas-Rachford operator splitting method
- On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators
- On the maximal domain of a monotone function
- On the minimal displacement vector of the Douglas-Rachford operator
- On the Numerical Solution of Heat Conduction Problems in Two and Three Space Variables
- OSQP: an operator splitting solver for quadratic programs
- Parameter selection and preconditioning for a graph form solver
- Preconditioned Douglas--Rachford Splitting Methods for Convex-concave Saddle-point Problems
- SDPLIB 1.2, a library of semidefinite programming test problems
- Solving conic optimization problems via self-dual embedding and facial reduction: A unified approach
- Solving SDP completely with an interior point oracle
- Splitting Algorithms for the Sum of Two Nonlinear Operators
- SuperMann: A Superlinearly Convergent Algorithm for Finding Fixed Points of Nonexpansive Operators
- Symmetric Quasidefinite Matrices
- The Linear Complementarity Problem
- The Numerical Solution of Parabolic and Elliptic Differential Equations
- The practical behavior of the homogeneous self-dual formulations in interior point methods
- Weak infeasibility in second order cone programming
Cited in
(22)- COSMO: a conic operator splitting method for convex conic problems
- Solution refinement at regular points of conic problems
- Conic optimization via operator splitting and homogeneous self-dual embedding
- scientific article; zbMATH DE number 4081173 (Why is no real title available?)
- Time-Varying Semidefinite Programming: Path Following a Burer–Monteiro Factorization
- Infeasibility Detection with Primal-Dual Hybrid Gradient for Large-Scale Linear Programming
- Randomized approach to matrix completion: applications in recommendation systems and image inpainting
- Quantum-compliant users scheduling optimization in joint transmission mobile access networks
- A practical and optimal first-order method for large-scale convex quadratic programming
- Data-driven performance guarantees for classical and learned optimizers
- A Halpern fixed-point iteration-based approach to harmonic model predictive control problem
- On the geometry and refined rate of primal-dual hybrid gradient for linear programming
- A data-driven practical stabilization approach for solving stochastic dynamic programming problems
- Randomized quasi-Monte Carlo methods for risk-averse stochastic optimization
- A computationally efficient primal-dual solver for linear-quadratic optimal control problems
- Coordinate-update algorithms can efficiently detect infeasible optimization problems
- HPR-LP: an implementation of an HPR method for solving linear programming
- A gradient descent akin method for constrained optimization: algorithms and applications
- A Splitting Architecture for Exact Reduced Coulomb Friction
- Learning algorithm hyperparameters for fast parametric convex optimization
- Verification of first-order methods for parametric quadratic optimization
- OSQP: an operator splitting solver for quadratic programs
Describes a project that uses
Uses Software
This page was built for publication: Operator splitting for a homogeneous embedding of the linear complementarity problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5010047)
