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 algorithm's 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.

本文介绍一种更快的内点法，用于求解具有变量大小的一般半定规划问题，并解释了算法的运行时间和矩阵乘法的指数和相对精度之间的关系。