Using Optimization to Obtain a Width-Independent, Parallel, Simpler, and Faster Positive SDP Solver

DOI10.1137/1.9781611974331.CH127zbMath1411.68180arXiv1507.02259OpenAlexW796181159MaRDI QIDQ4575711

Zeyuan Allen Zhu, Yin Tat Lee, Lorenzo Orecchia

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1507.02259

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Semidefinite programming (90C22) Parallel algorithms in computer science (68W10) Approximation algorithms (68W25)

Related Items (12)

Robust sub-Gaussian estimation of a mean vector in nearly linear time ⋮ Finding Sparse Solutions for Packing and Covering Semidefinite Programs ⋮ A multiplicative weight updates algorithm for packing and covering semi-infinite linear programs ⋮ Nearly linear-time packing and covering LP solvers. Nearly linear-time packing and covering LP solvers, achieving width-independence and \(=(1/\varepsilon)\)-convergence ⋮ Factor-\(\sqrt{2}\) acceleration of accelerated gradient methods ⋮ A Generalized Central Limit Conjecture for Convex Bodies ⋮ Unnamed Item ⋮ Unnamed Item ⋮ An almost constant lower bound of the isoperimetric coefficient in the KLS conjecture ⋮ Oracle-Based Primal-Dual Algorithms for Packing and Covering Semidefinite Programs ⋮ Linear Coupling: An Ultimate Unification of Gradient and Mirror Descent ⋮ Scalable Semidefinite Programming

This page was built for publication: Using Optimization to Obtain a Width-Independent, Parallel, Simpler, and Faster Positive SDP Solver