A Faster Interior Point Method for Semidefinite Programming

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.

Authors

• Haotian Jiang
• Tarun Kathuria
• Yin Tat Lee
• Swati Padmanabhan
• Zhao Song 0002

Keywords

• Runtime
• Manganese
• Optimization
• Complexity theory
• Approximation algorithms
• Time factors
• Programming
• Interior Point Method
• Semidefinite Programming
• Optimization Problem
• Class Of Problems
• Matrix Multiplication
• Input Size
• Robust Learning
• Cutting-plane
• Class Of Optimization Problems
• Iteration Matrix
• Loss Of Generality
• Barrier Function
• Matrix Size
• Linear Programming
• Fundamental Problem
• Vector Of Length
• Convex Optimization
• Accurate Parameters
• Convex Set
• Matrix Estimation
• First-order Algorithm
• Approximate Computation
• Theoretical Computer Science
• Central Path
• Kronecker Product
• Spectral Estimation
• List Of Works
• SDP
• Numerical Linear Algebra