A Unified Theorem on SDP Rank Reduction
From MaRDI portal
Publication:3169003
DOI10.1287/moor.1080.0326zbMath1218.90153MaRDI QIDQ3169003
Yinyu Ye, Anthony Man-Cho So, Jia-Wei Zhang
Publication date: 27 April 2011
Published in: Mathematics of Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1287/moor.1080.0326
semidefinite programming; quadratic optimization; randomized algorithm; metric embedding; low-rank matrices
90C22: Semidefinite programming
90C90: Applications of mathematical programming
68W25: Approximation algorithms
68W20: Randomized algorithms
Related Items
Sensor network localization, Euclidean distance matrix completions, and graph realization, Convexity of the image of a quadratic map via the relative entropy distance, Approximation algorithms for homogeneous polynomial optimization with quadratic constraints, Semidefinite relaxation bounds for bi-quadratic optimization problems with quadratic constraints, Deterministic approximation algorithms for sphere constrained homogeneous polynomial optimization problems, Moment inequalities for sums of random matrices and their applications in optimization, Theorems of the alternative for inequality systems of real polynomials, Improved semidefinite approximation bounds for nonconvex nonhomogeneous quadratic optimization with ellipsoid constraints, Semidefinite approximation bound for a class of nonhomogeneous nonconvex quadratically constrained quadratic programming problem, Jordan-algebraic aspects of optimization: randomization