We study mixed packing and covering semidefinite programs (SDPs) and give the first approximation algorithm with polylogarithmic dependence on width. Mixed packing and covering SDPs constitute a fundamental algorithmi...
详细信息
ISBN:
(纸本)9781450369794
We study mixed packing and covering semidefinite programs (SDPs) and give the first approximation algorithm with polylogarithmic dependence on width. Mixed packing and covering SDPs constitute a fundamental algorithmic primitive with applications in combinatorial optimization, robust learning, and quantum complexity. The current approximate solvers for positive semidefinite programming can handle only pure packing instances, and technical hurdles prevent their generalization to a wider class of positive instances. For a given multiplicative accuracy of c, our algorithm takes O (log(3)(ndp) . epsilon(-3)) parallelizable iterations, where n, d are the problem dimensions and rho is a width parameter of the instance, generalizing or improving all previous parallel algorithms in the positive linear and semidefinite programming literature. When specialized to pure packing SDPs, our algorithm's iteration complexity is O (log(2) (nd) . epsilon(-2)), a slight improvement and derandomization of the state-of-the-art [AI,016, rrl16, WNIMI-215]. For several common structured instances, the iterations of our algorithm run in nearly-linear time. In doing so, we give matrix analytic techniques to overcome obstacles that have stymied prior approaches to this problem, as stated in [PTZ16, NIRWZ16]. Crucial to our analysis are a simplification of existing algorithms for mixed positive linear programs, achieved by removing an asymmetry from modifying covering constraints, and a suite of matrix inequalities with proofs based on analyzing the Schur complements of matrices in a higher dimension. We hope that our algorithm and techniques open the door to improved solvers for positive semidefinite programming and its applications.
暂无评论