Conic optimization via operator splitting and homogeneous self-dual embedding
From MaRDI portal
Publication:301735
DOI10.1007/S10957-016-0892-3zbMATH Open1342.90136arXiv1312.3039OpenAlexW2288174618MaRDI QIDQ301735FDOQ301735
Authors: Brendan O'Donoghue, Eric Chu, Neal Parikh, Stephen Boyd 
Publication date: 1 July 2016
Published in: Journal of Optimization Theory and Applications (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1312.3039
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
Convex programming (90C25) Large-scale problems in mathematical programming (90C06) Numerical methods involving duality (49M29) Numerical methods based on necessary conditions (49M05)
Cites Work
- Algorithm 849
- Algorithm 837
- Benchmarks for Optimization Software
- SDPT3 — A Matlab software package for semidefinite programming, Version 1.3
- Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
- CVXPY: a Python-embedded modeling language for convex optimization
- Direct Methods for Sparse Linear Systems
- Convex.jl
- A first-order block-decomposition method for solving two-easy-block structured semidefinite programs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Distributed optimization and statistical learning via the alternating direction method of multipliers
- A dual algorithm for the solution of nonlinear variational problems via finite element approximation
- Parallel alternating direction multiplier decomposition of convex programs
- On the Numerical Solution of Heat Conduction Problems in Two and Three Space Variables
- Splitting Algorithms for the Sum of Two Nonlinear Operators
- Title not available (Why is that?)
- Title not available (Why is that?)
- Symmetric Quasidefinite Matrices
- Title not available (Why is that?)
- Title not available (Why is that?)
- Metric selection in fast dual forward-backward splitting
- On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators
- Adaptive restart for accelerated gradient schemes
- On the \(O(1/n)\) convergence rate of the Douglas-Rachford alternating direction method
- A Newton-CG augmented Lagrangian method for semidefinite programming
- Convex Analysis
- The Split Bregman Method for L1-Regularized Problems
- A multiprojection algorithm using Bregman projections in a product space
- Proximal splitting methods in signal processing
- Iterative oblique projection onto convex sets and the split feasibility problem
- Signal Recovery by Proximal Forward-Backward Splitting
- Perturbed projections and subgradient projections for the multiple-sets split feasibility problem
- A first-order primal-dual algorithm for convex problems with applications to imaging
- Implementation of a block-decomposition algorithm for solving large-scale conic semidefinite programming problems
- Title not available (Why is that?)
- A general framework for a class of first order primal-dual algorithms for convex optimization in imaging science
- Alternating direction algorithms for \(\ell_1\)-problems in compressive sensing
- Title not available (Why is that?)
- Monotone Operators and the Proximal Point Algorithm
- An iterative thresholding algorithm for linear inverse problems with a sparsity constraint
- Title not available (Why is that?)
- Applications of second-order cone programming
- A simplified homogeneous and self-dual linear programming algorithm and its implementation
- Title not available (Why is that?)
- An O(√nL)-Iteration Homogeneous and Self-Dual Linear Programming Algorithm
- Title not available (Why is that?)
- Primal-dual splitting algorithm for solving inclusions with mixtures of composite, Lipschitzian, and parallel-sum type monotone operators
- Alternating direction augmented Lagrangian methods for semidefinite programming
- Title not available (Why is that?)
- Systems of Structured Monotone Inclusions: Duality, Algorithms, and Applications
- Primal-dual first-order methods with \({\mathcal {O}(1/\varepsilon)}\) iteration-complexity for cone programming
- A primal-dual projection method for solving systems of linear inequalities
- An independent benchmarking of SDP and SOCP solvers
- Condition numbers and equilibration of matrices
- Self equivalence of the alternating direction method of multipliers
- Projection methods: Swiss army knives for solving feasibility and best approximation problems with halfspaces
- Partial inverse of a monotone operator
- On the effectiveness of projection methods for convex feasibility problems with linear inequality constraints
- Dykstra's alternating projection algorithm for two sets
- A homogeneous interior-point algorithm for nonsymmetric convex conic optimization
- Remarks on optimally scaled matrices
- A first-order augmented Lagrangian method for compressed sensing
- On Pre-Conditioning of Matrices
- Eventual linear convergence of the Douglas-Rachford iteration for basis pursuit
- Applications of the method of partial inverses to convex programming: Decomposition
- Matrix-free interior point method
- Primal-dual decomposition by operator splitting and applications to image deblurring
- Block splitting for distributed optimization
- Optimally scaled matrices
- Differential properties of Euclidean projection onto power cone
Cited In (99)
- HOMOGENEOUS SELF-DUAL METHODS FOR SYMMETRIC CONES UNDER UNCERTAINTY
- Chordal decomposition in operator-splitting methods for sparse semidefinite programs
- Globally Convergent Type-I Anderson Acceleration for Nonsmooth Fixed-Point Iterations
- Alfonso: Matlab Package for Nonsymmetric Conic Optimization
- Relaxation methods for navigation satellites set optimization
- On property (T) for \(\Aut(F_n)\) and \(\mathrm{SL}_n(\mathbb{Z})\)
- An Approximation Scheme for Distributionally Robust Nonlinear Optimization
- FANOK: knockoffs in linear time
- Infeasibility detection in the alternating direction method of multipliers for convex optimization
- Stochastic matrix-free equilibration
- Optimal perturbations for nonlinear systems using graph-based optimal transport
- Anderson Accelerated Douglas--Rachford Splitting
- Convergence of anisotropic mesh adaptation via metric optimization
- Scenario-based verification of uncertain MDPs
- \(\Aut(\mathbb{F}_5)\) has property \((T)\)
- Matrix-free convex optimization modeling
- Automatic repair of convex optimization problems
- A survey on conic relaxations of optimal power flow problem
- Distance geometry and data science
- Reconstructing manifolds from truncations of spectral triples
- Efficient differentiable quadratic programming layers: an ADMM approach
- Tax-aware portfolio construction via convex optimization
- Linear convergence of first order methods for non-strongly convex optimization
- GMRES-accelerated ADMM for quadratic objectives
- Frank--Wolfe Methods with an Unbounded Feasible Region and Applications to Structured Learning
- Perspective functions: proximal calculus and applications in high-dimensional statistics
- Certifying numerical estimates of spectral gaps
- Exploiting low-rank structure in semidefinite programming by approximate operator splitting
- Optimal transport over nonlinear systems via infinitesimal generators on graphs
- Solving Natural Conic Formulations with Hypatia.jl
- Proportional-integral projected gradient method for conic optimization
- Computation of the maximum likelihood estimator in low-rank factor analysis
- A convex optimization approach to radiation treatment planning with dose constraints
- Proximal distance algorithms: theory and practice
- Bounds on mean energy in the Kuramoto–Sivashinsky equation computed using semidefinite programming
- Stochastic block projection algorithms with extrapolation for convex feasibility problems
- Solution refinement at regular points of conic problems
- MathOptInterface: A Data Structure for Mathematical Optimization Problems
- OSQP: an operator splitting solver for quadratic programs
- An ADMM-based interior-point method for large-scale linear programming
- Bounds-constrained polynomial approximation using the Bernstein basis
- Non-Convex Global Minimization and False Discovery Rate Control for the TREX
- A distributed algorithm for high-dimension convex quadratically constrained quadratic programs
- Solving conic optimization problems via self-dual embedding and facial reduction: A unified approach
- Anderson accelerating the preconditioned modulus approach for linear complementarity problems on second-order cones
- Primal-dual first-order methods for a class of cone programming
- On the robustness and scalability of semidefinite relaxation for optimal power flow problems
- Clustering is semidefinitely not that hard: nonnegative SDP for manifold disentangling
- Low-rank matrix iteration using polynomial-filtered subspace extraction
- A dynamical neural network approach for solving stochastic two-player zero-sum games
- Outer approximation with conic certificates for mixed-integer convex problems
- Fixed-order H-infinity controller design for port-Hamiltonian systems
- Optimal rates for estimation of two-dimensional totally positive distributions
- COSMO: a conic operator splitting method for convex conic problems
- Efficient semidefinite programming with approximate ADMM
- Finding unstable periodic orbits: a hybrid approach with polynomial optimization
- Optimal representative sample weighting
- On a primal-dual Newton proximal method for convex quadratic programs
- Estimation of Monge matrices
- Multi-task sparse identification for closed-loop systems with general observation sequences
- Parameter selection and preconditioning for a graph form solver
- Computing large market equilibria using abstractions
- Bounds on heat transfer for Bénard-Marangoni convection at infinite Prandtl number
- Time-Varying Semidefinite Programming: Path Following a Burer–Monteiro Factorization
- Tutorial on Amortized Optimization
- Semi-definite programming and quantum information
- An efficient algorithm for optimal routing through constant function market makers
- 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
- 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
- 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
- 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
- PEPIT: computer-assisted worst-case analyses of first-order optimization methods in python
- Projection onto the exponential cone: a univariate root-finding problem
- Tuning as convex optimisation: a polynomial tuner for multi-parametric combinatorial samplers
- Performance enhancements for a generic conic interior point algorithm
- Title not available (Why is that?)
- Infeasibility Detection with Primal-Dual Hybrid Gradient for Large-Scale Linear Programming
- MG-CNN: a deep CNN to predict saddle points of matrix games
- A dual semismooth Newton based augmented Lagrangian method for large-scale linearly constrained sparse group square-root Lasso problems
- Observer‐based predictor for a susceptible‐infectious‐recovered model with delays: An optimal‐control case study
- On implementation of a self-dual embedding method for convex programming
- Operator splitting for a homogeneous embedding of the linear complementarity problem
- Certifying optimality of Bell inequality violations: noncommutative polynomial optimization through semidefinite programming and local optimization
- Regional consensus in discrete-time multi-agent systems subject to time-varying delays and saturating actuators
- CvxPnPL: a unified convex solution to the absolute pose estimation problem from point and line correspondences
- Kullback-Leibler divergence based multidimensional robust universal hypothesis testing
- An accelerated proximal alternating direction method of multipliers for optimal decentralized control of uncertain systems
- 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
- New bounds for the empirical robust Kullback-Leibler divergence problem
- An optimal-storage approach to semidefinite programming using approximate complementarity
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)
