  We give the first approximation algorithm for mixed packing and covering
semidefinite programs (SDPs) with polylogarithmic dependence on width. Mixed
packing and covering SDPs constitute a fundamental algorithmic primitive with
recent 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 $\epsilon$, our algorithm takes
$O(\log^3(nd\rho) \cdot \epsilon^{-3})$ parallelizable iterations, where $n$,
$d$ are dimensions of the problem 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) \cdot
\epsilon^{-2})$, a slight improvement and derandomization of the
state-of-the-art (Allen-Zhu et. al. '16, Peng et. al. '16, Wang et. al. '15).
For a wide variety of structured instances commonly found in applications, the
iterations of our algorithm run in nearly-linear time.
  In doing so, we give matrix analytic techniques for overcoming obstacles that
have stymied prior approaches to this open problem, as stated in past works
(Peng et. al. '16, Mahoney et. al. '16). Crucial to our analysis are a
simplification of existing algorithms for mixed positive linear programs,
achieved by removing an asymmetry caused by modifying covering constraints, and
a suite of matrix inequalities whose proofs are based on analyzing the Schur
complements of matrices in a higher dimension. We hope that both our algorithm
and techniques open the door to improved solvers for positive semidefinite
programming, as well as its applications.
