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)- COSMO: a conic operator splitting method for convex conic problems
- Chordal decomposition in operator-splitting methods for sparse semidefinite programs
- Solving Natural Conic Formulations with Hypatia.jl
- Stochastic matrix-free equilibration
- Primal-dual first-order methods for a class of cone programming
- Optimal perturbations for nonlinear systems using graph-based optimal transport
- Linear convergence of first order methods for non-strongly convex optimization
- Relaxation methods for navigation satellites set optimization
- Proximal distance algorithms: theory and practice
- GMRES-accelerated ADMM for quadratic objectives
- A convex optimization approach to radiation treatment planning with dose constraints
- Reconstructing manifolds from truncations of spectral triples
- On the robustness and scalability of semidefinite relaxation for optimal power flow problems
- Solution refinement at regular points of conic problems
- Non-Convex Global Minimization and False Discovery Rate Control for the TREX
- Efficient semidefinite programming with approximate ADMM
- Bounds on mean energy in the Kuramoto–Sivashinsky equation computed using semidefinite programming
- Clustering is semidefinitely not that hard: nonnegative SDP for manifold disentangling
- MathOptInterface: A Data Structure for Mathematical Optimization Problems
- Infeasibility detection in the alternating direction method of multipliers for convex optimization
- Anderson Accelerated Douglas--Rachford Splitting
- A distributed algorithm for high-dimension convex quadratically constrained quadratic programs
- Frank--Wolfe Methods with an Unbounded Feasible Region and Applications to Structured Learning
- Efficient differentiable quadratic programming layers: an ADMM approach
- Tax-aware portfolio construction via convex optimization
- Estimation of Monge matrices
- Automatic repair of convex optimization problems
- Finding unstable periodic orbits: a hybrid approach with polynomial optimization
- Globally Convergent Type-I Anderson Acceleration for Nonsmooth Fixed-Point Iterations
- Proportional-integral projected gradient method for conic optimization
- A dynamical neural network approach for solving stochastic two-player zero-sum games
- Alfonso: Matlab Package for Nonsymmetric Conic Optimization
- Outer approximation with conic certificates for mixed-integer convex problems
- Perspective functions: proximal calculus and applications in high-dimensional statistics
- A survey on conic relaxations of optimal power flow problem
- Optimal representative sample weighting
- Low-rank matrix iteration using polynomial-filtered subspace extraction
- OSQP: an operator splitting solver for quadratic programs
- Multi-task sparse identification for closed-loop systems with general observation sequences
- Distance geometry and data science
- Solving conic optimization problems via self-dual embedding and facial reduction: A unified approach
- Fixed-order H-infinity controller design for port-Hamiltonian systems
- Certifying numerical estimates of spectral gaps
- Scenario-based verification of uncertain MDPs
- Convergence of anisotropic mesh adaptation via metric optimization
- Optimal rates for estimation of two-dimensional totally positive distributions
- Computation of the maximum likelihood estimator in low-rank factor analysis
- \(\Aut(\mathbb{F}_5)\) has property \((T)\)
- An Approximation Scheme for Distributionally Robust Nonlinear Optimization
- On property (T) for \(\Aut(F_n)\) and \(\mathrm{SL}_n(\mathbb{Z})\)
- An ADMM-based interior-point method for large-scale linear programming
- FANOK: knockoffs in linear time
- Parameter selection and preconditioning for a graph form solver
- Anderson accelerating the preconditioned modulus approach for linear complementarity problems on second-order cones
- Matrix-free convex optimization modeling
- Exploiting low-rank structure in semidefinite programming by approximate operator splitting
- Stochastic block projection algorithms with extrapolation for convex feasibility problems
- HOMOGENEOUS SELF-DUAL METHODS FOR SYMMETRIC CONES UNDER UNCERTAINTY
- Optimal transport over nonlinear systems via infinitesimal generators on graphs
- Bounds-constrained polynomial approximation using the Bernstein basis
- On a primal-dual Newton proximal method for convex quadratic programs
- scientific article; zbMATH DE number 7306855 (Why is no real title available?)
- Error bounds, facial residual functions and applications to the exponential cone
- Kullback-Leibler divergence based multidimensional robust universal hypothesis testing
- Bounds on heat transfer for Bénard-Marangoni convection at infinite Prandtl number
- Faster first-order primal-dual methods for linear programming using restarts and sharpness
- Path deformation method with constraints on normal curvature for wheeled robots in precision agriculture based on second-order cone programming
- Remark on Algorithm 1012: computing projections with large datasets
- Certifying optimality of Bell inequality violations: noncommutative polynomial optimization through semidefinite programming and local optimization
- Computing large market equilibria using abstractions
- Compositional synthesis for linear systems via convex optimization of assume-guarantee contracts
- A dual semismooth Newton based augmented Lagrangian method for large-scale linearly constrained sparse group square-root Lasso problems
- Regional consensus in discrete-time multi-agent systems subject to time-varying delays and saturating actuators
- Observer‐based predictor for a susceptible‐infectious‐recovered model with delays: An optimal‐control case study
- Projection onto the exponential cone: a univariate root-finding problem
- An efficient algorithm for optimal routing through constant function market makers
- An optimal-storage approach to semidefinite programming using approximate complementarity
- Exploiting constant trace property in large-scale polynomial optimization
- Coverage path planning for 3D terrain with constraints on trajectory curvature based on second-order cone programming
- Estimation of the geometric measure of entanglement with Wehrl moments through artificial neural networks
- PEPIT: computer-assisted worst-case analyses of first-order optimization methods in python
- Tuning as convex optimisation: a polynomial tuner for multi-parametric combinatorial samplers
- Time-Varying Semidefinite Programming: Path Following a Burer–Monteiro Factorization
- Tutorial on Amortized Optimization
- Splitting proximal algorithms for convex optimizations over metric spaces with curvature bounded above
- MG-CNN: a deep CNN to predict saddle points of matrix games
- Quantile-constrained Wasserstein projections for robust interpretability of numerical and machine learning models
- Minimizing oracle-structured composite functions
- Operator splitting for a homogeneous embedding of the linear complementarity problem
- CvxPnPL: a unified convex solution to the absolute pose estimation problem from point and line correspondences
- On implementation of a self-dual embedding method for convex programming
- Risk budgeting portfolios from simulations
- Performance enhancements for a generic conic interior point algorithm
- Approximate modularity: Kalton's constant is not smaller than 3
- Semi-definite programming and quantum information
- Infeasibility Detection with Primal-Dual Hybrid Gradient for Large-Scale Linear Programming
- An accelerated proximal alternating direction method of multipliers for optimal decentralized control of uncertain systems
- Accelerated first-order methods for a class of semidefinite programs
- New bounds for the empirical robust Kullback-Leibler divergence problem
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)
