Conic optimization via operator splitting and homogeneous self-dual embedding
From MaRDI portal
(Redirected from Publication:301735)
Abstract: We introduce a first order method for solving very large convex cone programs. The method uses an operator splitting method, the alternating directions method of multipliers, to solve the homogeneous self-dual embedding, an equivalent feasibility problem involving finding a nonzero point in the intersection of a subspace and a cone. This approach has several favorable properties. Compared to interior-point methods, first-order methods scale to very large problems, at the cost of requiring more time to reach very high accuracy. Compared to other first-order methods for cone programs, our approach finds both primal and dual solutions when available or a certificate of infeasibility or unboundedness otherwise, is parameter-free, and the per-iteration cost of the method is the same as applying a splitting method to the primal or dual alone. We discuss efficient implementation of the method in detail, including direct and indirect methods for computing projection onto the subspace, scaling the original problem data, and stopping criteria. We describe an open-source implementation, which handles the usual (symmetric) non-negative, second-order, and semidefinite cones as well as the (non-self-dual) exponential and power cones and their duals. We report numerical results that show speedups over interior-point cone solvers for large problems, and scaling to very large general cone programs.
Recommendations
- Operator splitting for a homogeneous embedding of the linear complementarity problem
- COSMO: a conic operator splitting method for convex conic problems
- OSQP: an operator splitting solver for quadratic programs
- Primal-dual first-order methods with \({\mathcal {O}(1/\varepsilon)}\) iteration-complexity for cone programming
- A computational study of the homogeneous algorithm for large-scale convex optimization
Cites work
- scientific article; zbMATH DE number 3833218 (Why is no real title available?)
- scientific article; zbMATH DE number 3852340 (Why is no real title available?)
- scientific article; zbMATH DE number 3973706 (Why is no real title available?)
- scientific article; zbMATH DE number 45081 (Why is no real title available?)
- scientific article; zbMATH DE number 3574917 (Why is no real title available?)
- scientific article; zbMATH DE number 729680 (Why is no real title available?)
- scientific article; zbMATH DE number 1953444 (Why is no real title available?)
- scientific article; zbMATH DE number 3997612 (Why is no real title available?)
- scientific article; zbMATH DE number 2107836 (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?)
- scientific article; zbMATH DE number 961607 (Why is no real title available?)
- A Newton-CG augmented Lagrangian method for semidefinite programming
- A dual algorithm for the solution of nonlinear variational problems via finite element approximation
- A first-order augmented Lagrangian method for compressed sensing
- A first-order block-decomposition method for solving two-easy-block structured semidefinite programs
- A first-order primal-dual algorithm for convex problems with applications to imaging
- A general framework for a class of first order primal-dual algorithms for convex optimization in imaging science
- A homogeneous interior-point algorithm for nonsymmetric convex conic optimization
- A multiprojection algorithm using Bregman projections in a product space
- A primal-dual projection method for solving systems of linear inequalities
- A simplified homogeneous and self-dual linear programming algorithm and its implementation
- Adaptive restart for accelerated gradient schemes
- Algorithm 837
- Algorithm 849
- Alternating direction algorithms for \(\ell_1\)-problems in compressive sensing
- Alternating direction augmented Lagrangian methods for semidefinite programming
- An O(√nL)-Iteration Homogeneous and Self-Dual Linear Programming Algorithm
- An independent benchmarking of SDP and SOCP solvers
- An iterative thresholding algorithm for linear inverse problems with a sparsity constraint
- Applications of second-order cone programming
- Applications of the method of partial inverses to convex programming: Decomposition
- Benchmarks for Optimization Software
- Block splitting for distributed optimization
- CVXPY: a Python-embedded modeling language for convex optimization
- Condition numbers and equilibration of matrices
- Convex Analysis
- Convex.jl
- Differential properties of Euclidean projection onto power cone
- Direct Methods for Sparse Linear Systems
- Distributed optimization and statistical learning via the alternating direction method of multipliers
- Dykstra's alternating projection algorithm for two sets
- Eventual linear convergence of the Douglas-Rachford iteration for basis pursuit
- Implementation of a block-decomposition algorithm for solving large-scale conic semidefinite programming problems
- Iterative oblique projection onto convex sets and the split feasibility problem
- Matrix-free interior point method
- Metric selection in fast dual forward-backward splitting
- Monotone Operators and the Proximal Point Algorithm
- On Pre-Conditioning of Matrices
- On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators
- On the Numerical Solution of Heat Conduction Problems in Two and Three Space Variables
- On the \(O(1/n)\) convergence rate of the Douglas-Rachford alternating direction method
- On the effectiveness of projection methods for convex feasibility problems with linear inequality constraints
- Optimally scaled matrices
- Parallel alternating direction multiplier decomposition of convex programs
- Partial inverse of a monotone operator
- Perturbed projections and subgradient projections for the multiple-sets split feasibility problem
- Primal-dual decomposition by operator splitting and applications to image deblurring
- Primal-dual first-order methods with \({\mathcal {O}(1/\varepsilon)}\) iteration-complexity for cone programming
- Primal-dual splitting algorithm for solving inclusions with mixtures of composite, Lipschitzian, and parallel-sum type monotone operators
- Projection methods: Swiss army knives for solving feasibility and best approximation problems with halfspaces
- Proximal splitting methods in signal processing
- Remarks on optimally scaled matrices
- SDPT3 — A Matlab software package for semidefinite programming, Version 1.3
- Self equivalence of the alternating direction method of multipliers
- Signal Recovery by Proximal Forward-Backward Splitting
- Splitting Algorithms for the Sum of Two Nonlinear Operators
- Symmetric Quasidefinite Matrices
- Systems of Structured Monotone Inclusions: Duality, Algorithms, and Applications
- The Split Bregman Method for L1-Regularized Problems
- Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
Cited in
(99)- An optimal-storage approach to semidefinite programming using approximate complementarity
- Computing large market equilibria using abstractions
- Chordal decomposition in operator-splitting methods for sparse semidefinite programs
- HOMOGENEOUS SELF-DUAL METHODS FOR SYMMETRIC CONES UNDER UNCERTAINTY
- Bounds on heat transfer for Bénard-Marangoni convection at infinite Prandtl number
- Relaxation methods for navigation satellites set optimization
- Globally Convergent Type-I Anderson Acceleration for Nonsmooth Fixed-Point Iterations
- Alfonso: Matlab Package for Nonsymmetric Conic Optimization
- Time-Varying Semidefinite Programming: Path Following a Burer–Monteiro Factorization
- Tutorial on Amortized Optimization
- Semi-definite programming and quantum information
- On property (T) for \(\Aut(F_n)\) and \(\mathrm{SL}_n(\mathbb{Z})\)
- An Approximation Scheme for Distributionally Robust Nonlinear Optimization
- Infeasibility detection in the alternating direction method of multipliers for convex optimization
- FANOK: knockoffs in linear time
- Stochastic matrix-free equilibration
- Optimal perturbations for nonlinear systems using graph-based optimal transport
- An efficient algorithm for optimal routing through constant function market makers
- Anderson Accelerated Douglas--Rachford Splitting
- Coverage path planning for 3D terrain with constraints on trajectory curvature based on second-order cone programming
- Path deformation method with constraints on normal curvature for wheeled robots in precision agriculture based on second-order cone programming
- Convergence of anisotropic mesh adaptation via metric optimization
- Error bounds, facial residual functions and applications to the exponential cone
- Exploiting constant trace property in large-scale polynomial optimization
- Quantile-constrained Wasserstein projections for robust interpretability of numerical and machine learning models
- \(\Aut(\mathbb{F}_5)\) has property \((T)\)
- Matrix-free convex optimization modeling
- Scenario-based verification of uncertain MDPs
- Automatic repair of convex optimization problems
- A survey on conic relaxations of optimal power flow problem
- Estimation of the geometric measure of entanglement with Wehrl moments through artificial neural networks
- Faster first-order primal-dual methods for linear programming using restarts and sharpness
- Distance geometry and data science
- Minimizing oracle-structured composite functions
- Risk budgeting portfolios from simulations
- Remark on Algorithm 1012: computing projections with large datasets
- Compositional synthesis for linear systems via convex optimization of assume-guarantee contracts
- Reconstructing manifolds from truncations of spectral triples
- Tax-aware portfolio construction via convex optimization
- PEPIT: computer-assisted worst-case analyses of first-order optimization methods in python
- Efficient differentiable quadratic programming layers: an ADMM approach
- Projection onto the exponential cone: a univariate root-finding problem
- Linear convergence of first order methods for non-strongly convex optimization
- Tuning as convex optimisation: a polynomial tuner for multi-parametric combinatorial samplers
- Certifying numerical estimates of spectral gaps
- Perspective functions: proximal calculus and applications in high-dimensional statistics
- Performance enhancements for a generic conic interior point algorithm
- GMRES-accelerated ADMM for quadratic objectives
- Frank--Wolfe Methods with an Unbounded Feasible Region and Applications to Structured Learning
- scientific article; zbMATH DE number 7306855 (Why is no real title available?)
- Optimal transport over nonlinear systems via infinitesimal generators on graphs
- Exploiting low-rank structure in semidefinite programming by approximate operator splitting
- Proportional-integral projected gradient method for conic optimization
- Solving Natural Conic Formulations with Hypatia.jl
- Computation of the maximum likelihood estimator in low-rank factor analysis
- A convex optimization approach to radiation treatment planning with dose constraints
- Infeasibility Detection with Primal-Dual Hybrid Gradient for Large-Scale Linear Programming
- Bounds on mean energy in the Kuramoto–Sivashinsky equation computed using semidefinite programming
- Proximal distance algorithms: theory and practice
- OSQP: an operator splitting solver for quadratic programs
- Solution refinement at regular points of conic problems
- Stochastic block projection algorithms with extrapolation for convex feasibility problems
- MG-CNN: a deep CNN to predict saddle points of matrix games
- MathOptInterface: A Data Structure for Mathematical Optimization Problems
- Bounds-constrained polynomial approximation using the Bernstein basis
- An ADMM-based interior-point method for large-scale linear programming
- A distributed algorithm for high-dimension convex quadratically constrained quadratic programs
- Non-Convex Global Minimization and False Discovery Rate Control for the TREX
- A dual semismooth Newton based augmented Lagrangian method for large-scale linearly constrained sparse group square-root Lasso problems
- On implementation of a self-dual embedding method for convex programming
- Observer‐based predictor for a susceptible‐infectious‐recovered model with delays: An optimal‐control case study
- On the robustness and scalability of semidefinite relaxation for optimal power flow problems
- Anderson accelerating the preconditioned modulus approach for linear complementarity problems on second-order cones
- Solving conic optimization problems via self-dual embedding and facial reduction: A unified approach
- Primal-dual first-order methods for a class of cone programming
- Operator splitting for a homogeneous embedding of the linear complementarity problem
- Regional consensus in discrete-time multi-agent systems subject to time-varying delays and saturating actuators
- Certifying optimality of Bell inequality violations: noncommutative polynomial optimization through semidefinite programming and local optimization
- CvxPnPL: a unified convex solution to the absolute pose estimation problem from point and line correspondences
- Low-rank matrix iteration using polynomial-filtered subspace extraction
- Clustering is semidefinitely not that hard: nonnegative SDP for manifold disentangling
- Kullback-Leibler divergence based multidimensional robust universal hypothesis testing
- Outer approximation with conic certificates for mixed-integer convex problems
- Optimal rates for estimation of two-dimensional totally positive distributions
- An accelerated proximal alternating direction method of multipliers for optimal decentralized control of uncertain systems
- COSMO: a conic operator splitting method for convex conic problems
- A dynamical neural network approach for solving stochastic two-player zero-sum games
- Efficient semidefinite programming with approximate ADMM
- Fixed-order H-infinity controller design for port-Hamiltonian systems
- Finding unstable periodic orbits: a hybrid approach with polynomial optimization
- Approximate modularity: Kalton's constant is not smaller than 3
- Accelerated first-order methods for a class of semidefinite programs
- Splitting proximal algorithms for convex optimizations over metric spaces with curvature bounded above
- Optimal representative sample weighting
- On a primal-dual Newton proximal method for convex quadratic programs
- Estimation of Monge matrices
- New bounds for the empirical robust Kullback-Leibler divergence problem
- Multi-task sparse identification for closed-loop systems with general observation sequences
- Parameter selection and preconditioning for a graph form solver
Describes a project that uses
Uses Software
This page was built for publication: Conic optimization via operator splitting and homogeneous self-dual embedding
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q301735)
