Semidefinite programming

Matrix (chemical analysis)

Operating system

Regular polygon

Algorithm

Mathematical optimization

Convex optimization

Composite material

Materials science

Range (aeronautics)

Geometry

Laptop

Mathematics

Computer science

Scalability

Quadratically constrained quadratic program

Database

Quadratic programming

SIAM Journal on Mathematics of Data Science

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.

Scalable Semidefinite Programming