A Faster Interior Point Method for Semidefinite Programming
A Faster Interior Point Method for Semidefinite Programming
复制标题
DOI：
10.1109/focs46700.2020.00089
复制
发表时间：
2020-09
期刊：
影响因子：
--
通讯作者：
Haotian Jiang;Tarun Kathuria;Y. Lee;Swati Padmanabhan;Zhao Song
中科院分区：
文献类型：
--
作者：
Haotian Jiang;Tarun Kathuria;Y. Lee;Swati Padmanabhan;Zhao Song
半定规划是一类基本的优化问题，近年来在近似算法、量子复杂性、稳健学习、算法舍入和对抗性深度学习等领域有着重要的应用。本文提出了一种求解一般SDP问题的快速内点方法，其中$omega$是矩阵乘法的指数，$epsilon$是相对精度。在$m\geq n$的主要情况下，我们的运行时间比以前最快的基于割平面法的SDP求解器[JLSW20]要好。我们的算法的运行时间可以自然地解释为：$O(\sqrt{n}\log(1/\epsilon))$是内点法所需的迭代次数，$Mn^{2}$是输入大小，$m^{\omega}+n^{\omega}$是在每次迭代中求逆Hessian和Sack矩阵的时间。这些构成了进一步改进求解一般SDP的内点方法的运行时间的自然障碍。
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{equation*} \tilde{O}(\sqrt{n}(mn^{2}+m^{\omega}+n^{\omega})\log(1/\epsilon)), \end{equation*} 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 [JLSW20]. Our algorithm's runtime can be naturally interpreted as follows: $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.