Semidefinite programs (SDPs) are a fundamental class of optimization problems with important recent applications in approximation algorithms, quantum complexity, robust learning, algorithmic rounding, and adversarial deep learning. This paper presents a faster interior point method to solve generic SDPs with variable size $n times n$ and $m$ constraints in time begin{align*} widetilde{O}(sqrt{n}( mn^2 + m^omega + n^omega) log(1 / epsilon) ), end{align*} where $omega$ is the exponent of matrix multiplication and $epsilon$ is the relative accuracy. In the predominant case of $m geq n$, our runtime outperforms that of the previous fastest SDP solver, which is based on the cutting plane method of Jiang, Lee, Song, and Wong [JLSW20]. Our algorithms runtime can be naturally interpreted as follows: $widetilde{O}(sqrt{n} log (1/epsilon))$ is the number of iterations needed for our interior point method, $mn^2$ is the input size, and $m^omega + n^omega$ is the time to invert the Hessian and slack matrix in each iteration. These constitute natural barriers to further improving the runtime of interior point methods for solving generic SDPs.
Download