Scalable semidefinite programming
From MaRDI portal
Abstract: Semidefinite programming (SDP) is a powerful framework from convex optimization that has striking potential for data science applications. This paper develops a provably correct randomized algorithm for solving large, weakly constrained SDP problems by economizing on the storage and arithmetic costs. Numerical evidence shows that the method is effective for a range of applications, including relaxations of MaxCut, abstract phase retrieval, and quadratic assignment. Running on a laptop equivalent, the algorithm can handle SDP instances where the matrix variable has over entries.
Recommendations
- Memory-efficient structured convex optimization via extreme point sampling
- Subsampling algorithms for semidefinite programming
- An efficient approach to solve the large-scale semidefinite programming problems
- Large-scale semidefinite programming via a saddle point mirror-prox algorithm
- An optimal-storage approach to semidefinite programming using approximate complementarity
Cites work
- scientific article; zbMATH DE number 5957285 (Why is no real title available?)
- scientific article; zbMATH DE number 3914081 (Why is no real title available?)
- scientific article; zbMATH DE number 729680 (Why is no real title available?)
- scientific article; zbMATH DE number 1049353 (Why is no real title available?)
- scientific article; zbMATH DE number 1860211 (Why is no real title available?)
- scientific article; zbMATH DE number 3231692 (Why is no real title available?)
- scientific article; zbMATH DE number 3293978 (Why is no real title available?)
- scientific article; zbMATH DE number 2246591 (Why is no real title available?)
- A Newton-CG augmented Lagrangian method for semidefinite programming
- A combinatorial, primal-dual approach to semidefinite programs
- A continuous method for computing bounds in integer quadratic optimization problems
- A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
- A randomized mirror-prox method for solving structured large-scale matrix saddle-point problems
- A shortest augmenting path algorithm for dense and sparse linear assignment problems
- A simple lemma on greedy approximation in Hilbert space and convergence rates for projection pursuit regression and neural network training
- A survey for the quadratic assignment problem
- ARPACK Users' Guide
- Algorithm 971
- Algorithms for the Assignment and Transportation Problems
- Alternating direction augmented Lagrangian methods for semidefinite programming
- An O(nL) iteration algorithm for computing bounds in quadratic optimization problems
- Array imaging using intensity-only measurements
- Complementarity and nondegeneracy in semidefinite programming
- Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm
- Estimating the Largest Eigenvalue by the Power and Lanczos Algorithms with a Random Start
- Fast low-rank modifications of the thin singular value decomposition
- Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
- Generalized conditional gradient with augmented Lagrangian for composite minimization
- Graph Partitioning and Graph Clustering
- Handbook on semidefinite, conic and polynomial optimization
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Improved matrix algorithms via the subsampled randomized Hadamard transform
- Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
- Introductory lectures on convex optimization. A basic course.
- Laplacian eigenvalues and the maximum cut problem
- Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
- Local minima and convergence in low-rank semidefinite programming
- Manopt, a Matlab toolbox for optimization on manifolds
- On signal reconstruction without phase
- On the Burer-Monteiro method for general semidefinite programs
- On the nonergodic convergence rate of an inexact augmented Lagrangian framework for composite convex programming
- On the rank minimization problem over a positive semidefinite linear matrix inequality
- On the rank of extreme matrices in semidefinite programs and the multiplicity of optimal eigenvalues
- P-Complete Approximation Problems
- Painless reconstruction from magnitudes of frame coefficients
- Phase retrieval from coded diffraction patterns
- Practical sketching algorithms for low-rank matrix approximation
- Primal-Dual Interior-Point Methods for Semidefinite Programming: Convergence Rates, Stability and Numerical Results
- Primal-dual subgradient methods for convex problems
- Prox-Method with Rate of Convergence O(1/t) for Variational Inequalities with Lipschitz Continuous Monotone Operators and Smooth Convex-Concave Saddle Point Problems
- QAPLIB - a quadratic assignment problem library
- Rank optimality for the Burer-Monteiro factorization
- Reducibility among combinatorial problems
- SDPNAL+: a majorized semismooth Newton-CG augmented Lagrangian method for semidefinite programming with nonnegative constraints
- SDPT3 — A Matlab software package for semidefinite programming, Version 1.3
- SYMMETRIC GAUGE FUNCTIONS AND UNITARILY INVARIANT NORMS
- Semidefinite programming approach for the quadratic assignment problem with a sparse graph
- Semidefinite programming relaxations for the quadratic assignment problem
- Solving Euclidean distance matrix completion problems via semidefinite progrmming
- Solving Lift-and-Project Relaxations of Binary Integer Programs
- Sparse Approximate Solutions to Semidefinite Programs
- Streaming low-rank matrix approximation with an application to scientific simulation
- Sublinear time algorithms for approximate semidefinite programming
- The performance of an eigenvalue bound on the max-cut problem in some classes of graphs
- Trust-region methods on Riemannian manifolds
- Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
- Using optimization to obtain a width-independent, parallel, simpler, and faster positive SDP solver
Cited in
(48)- Partitioning through projections: strong SDP bounds for large graph partition problems
- An optimal-storage approach to semidefinite programming using approximate complementarity
- Solving low-rank semidefinite programs via manifold optimization
- Fast and accurate randomized algorithms for linear systems and eigenvalue problems
- CS-TSSOS: correlative and term sparsity for large-scale polynomial optimization
- How robust is randomized blind deconvolution via nuclear norm minimization against adversarial noise?
- Finding graph embeddings by incremental low-rank semidefinite programming
- A feasible method for general convex low-rank SDP problems
- Low-rank extragradient methods for scalable semidefinite optimization
- Conic optimization: a survey with special focus on copositive optimization and binary quadratic problems
- Grid is good. Adaptive refinement algorithms for off-the-grid total variation minimization
- A semidefinite relaxation for sums of heterogeneous quadratic forms on the Stiefel manifold
- Provably faster gradient descent via long steps
- Minimal energy configurations of bilayer plates as a polynomial optimization problem
- Exploiting constant trace property in large-scale polynomial optimization
- An inexact projected gradient method with rounding and lifting by nonlinear programming for solving rank-one semidefinite relaxation of polynomial optimization
- The moment-SOS hierarchy: applications and related topics
- A convex relaxation to compute the nearest structured rank deficient matrix
- Near-optimal bounds for generalized orthogonal Procrustes problem via generalized power method
- A new complexity metric for nonconvex rank-one generalized matrix completion
- Higher-order Newton methods with polynomial work per iteration
- Scalable low-rank semidefinite programming for certifiably correct machine perception
- SDPA PROJECT : SOLVING LARGE-SCALE SEMIDEFINITE PROGRAMS(<Special Issue>the 50th Anniversary of the Operations Research Society of Japan)
- A stochastic approximation method for convex programming with many semidefinite constraints
- Cutting plane generation through sparse principal component analysis
- Automated verification and synthesis of stochastic hybrid systems: a survey
- On computational capabilities of Ising machines based on nonlinear oscillators
- Solving matrix nearness problems via Hamiltonian systems, matrix factorization, and optimization
- Exploiting low-rank structure in semidefinite programming by approximate operator splitting
- A hierarchy of spectral relaxations for polynomial optimization
- PCA Sparsified
- Optimal neural network approximation of Wasserstein gradient direction via convex optimization
- An overview and comparison of spectral bundle methods for primal and dual semidefinite programs
- Oblivious stochastic convex optimization
- Subsampling algorithms for semidefinite programming
- An efficient approach to solve the large-scale semidefinite programming problems
- Positive Semi-definite Embedding for Dimensionality Reduction and Out-of-Sample Extensions
- scientific article; zbMATH DE number 7626745 (Why is no real title available?)
- Sparse sub-Gaussian random projections for semidefinite programming relaxations
- Exploiting term sparsity in noncommutative polynomial optimization
- Scalable approximate optimal diagonal preconditioning
- Loraine – an interior-point solver for low-rank semidefinite programming
- Solving orthogonal group synchronization via convex and low-rank optimization: tightness and landscape analysis
- Finding unstable periodic orbits: a hybrid approach with polynomial optimization
- Accelerated first-order methods for a class of semidefinite programs
- Revisiting Spectral Bundle Methods: Primal-Dual (Sub)linear Convergence Rates
- Memory-efficient structured convex optimization via extreme point sampling
- Community detection with nodal information: likelihood and its variational approximation
Describes a project that uses
Uses Software
This page was built for publication: Scalable semidefinite programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4999352)
