Scalable Semidefinite Programming

Abstract

Semidefinite programming (SDP) is a powerful framework from convex optimization that has striking potential for data science applications. This paper develops a provably correct randomized algorithm for solving large, weakly constrained SDP problems by economizing on the storage and arithmetic costs. Numerical evidence shows that the method is effective for a range of applications, including relaxations of MaxCut, abstract phase retrieval, and quadratic assignment. Running on a laptop equivalent, the algorithm can handle SDP instances where the matrix variable has over $10^{14}$ entries.

References in corpus (2)

• Wide-field, high-resolution Fourier ptychographic microscopy
• Practical sketching algorithms for low-rank matrix approximation

Cited by in corpus (11)

• Warm-starting quantum optimization
• Quantum metrology for non-Markovian processes
• Projected Least-Squares Quantum Process Tomography
• Chordal and factor-width decompositions for scalable semidefinite and polynomial optimization
• Limitations of optimization algorithms on noisy quantum devices
• Lower Bounding Ground-State Energies of Local Hamiltonians Through the Renormalization Group
• On computational capabilities of Ising machines based on nonlinear oscillators,
• Semidefinite Programs at Finite Fermion Density
• Finding unstable periodic orbits: a hybrid approach with polynomial optimization
• Alleviating the quantum Big-$M$ problem
• Sub-universal variational circuits for combinatorial optimization problems