Scaling Semidefinite Programs Beyond Quadratic Memory

22 concepts20 papers1 proposal

Semidefinite Programming (SDP) is a cornerstone of convex optimization. By optimizing a linear objective over the intersection of the cone of positive semidefinite (PSD) matrices and affine constraints, SDPs provide tight approximations for hard problems. They are widely used in fields ranging from neural network verification (Brendon G. Anderson et al. in Tight Certified Robustness via Min-Max Representations of ReLU Neural Networks) to estimating the Lipschitz constants of deep architectures (Zi Wang et al. in On the Scalability and Memory Efficiency of Semidefinite Programs for Lipschitz Constant Estimation of Neural Networks).

Despite their utility, SDPs suffer from a severe curse of dimensionality. Standard solvers rely on interior-point methods (IPMs) that explicitly store and manipulate an $n \times n$ matrix variable $X$. As highlighted by Alp Yurtsever et al. in Scalable Semidefinite Programming, this introduces a quadratic memory complexity ($O(n^2)$). If a problem involves a million variables, storing the matrix requires a trillion entries—instantly causing memory exhaustion on standard hardware (Claudio Gambella et al. in Projections onto the Set of Feasible Inputs and the Set of Feasible Solutions).

To scale SDPs to real-world dimensions, a modern research direction focuses on bypassing this quadratic storage bottleneck. Three primary paradigms have emerged: low-rank factorization, matrix-free first-order optimization, and structural sparsity decomposition.


Low-Rank Factorization: The Burer-Monteiro Method

One intuitive way to avoid storing an $n \times n$ matrix $X$ is to exploit the fact that many optimal SDP solutions are inherently low-rank. The Burer-Monteiro method replaces the massive matrix variable $X$ with a low-rank factorization:

$$X = Y Y^T$$

where $Y$ is an $n \times r$ matrix, and the rank $r \ll n$. This simple substitution drops the storage requirement from $O(n^2)$ to $O(nr)$, transforming a memory-prohibitive problem into a highly manageable one.

However, this compression comes at a cost. Substituting $Y Y^T$ for $X$ destroys the convexity of the SDP, turning it into a non-convex optimization problem plagued by potential local minima.

Convex SDP Space (Global Optimum)
   └── [Substitution: X = YYᵀ] ──> Non-Convex Landscape (Risk of Local Minima)

To understand when this method is reliable, researchers look to the Barvinok-Pataki bound, which states that an extreme point of an SDP with $m$ affine constraints satisfies $r(r+1)/2 \le m$. Diego Cifuentes et al. in Polynomial time guarantees for the Burer-Monteiro method proved that under "smoothed analysis"—which models slight real-world perturbations—the Burer-Monteiro method can find the global optimum in polynomial time when the rank is chosen near this bound.

Yet, this guarantee is not absolute. Liam O'Carroll et al. demonstrated in The Burer-Monteiro SDP method can fail even above the Barvinok-Pataki bound that worst-case instances still harbor "trap" local minima even at higher ranks, showing that pure low-rank factorization requires careful structural assumptions.


Matrix-Free and Projection-Free First-Order Methods

Instead of changing the problem formulation, another paradigm changes how the optimization algorithm interacts with memory. Standard solvers use second-order methods that compute heavy Hessian matrices. First-order methods, by contrast, rely only on gradient information.

To eliminate the $O(n^2)$ matrix storage entirely, researchers combine first-order algorithms with randomized sketching or on-the-fly computation.


Exploiting Structural and Chordal Sparsity

A third approach scales optimization by breaking a single monolithic problem into smaller, decoupled pieces. Many large-scale SDPs possess aggregate sparsity, meaning that individual constraints only couple a small subset of variables together.

Monolithic Matrix Constraint (Large n × n)
         │
         ▼ [Chordal Decomposition]
[Small Block 1] ── (Overlapping Variables) ── [Small Block 2]

Yang Zheng 0001 et al. demonstrated in Fast ADMM for semidefinite programs with chordal sparsity that if the sparsity pattern of the constraints forms a chordal graph, a massive $n \times n$ PSD constraint can be equivalently decomposed into a collection of much smaller, overlapping PSD constraints. By pairing this decomposition with the Alternating Direction Method of Multipliers (ADMM), the authors distribute the computational load across smaller matrices, drastically reducing memory usage.

When the structure allows, this overhead can be reduced even further. Heejune Sheen et al. in Exploiting aggregate sparsity in second-order cone relaxations for quadratic constrained quadratic programming problems showed that certain quadratic problems can be relaxed into Second-Order Cone Programs (SOCPs) rather than full SDPs. This completely avoids the matrix cone overhead while preserving high approximation accuracy.

Hybrid Frameworks

Rather than relying on a single technique, state-of-the-art solvers often combine these insights. For instance, Heng Yang et al. introduced STRIDE in STRIDE along Spectrahedral Vertices for Solving Large-Scale Rank-One Semidefinite Relaxations, a framework that initializes optimization using global convex methods and transitions to rapid, low-rank non-convex local refinement. Similarly, Mehmet Fatih Sahin et al. in An Inexact Augmented Lagrangian Framework for Nonconvex Optimization with Nonlinear Constraints and Bo Yang et al. in An Accelerated Proximal Alternating Direction Method of Multipliers for Optimal Decentralized Control of Uncertain Systems utilize inexact subproblem updates and fixed-point acceleration to handle non-linear constraints without encountering the memory walls of traditional interior-point methods.

By replacing explicit matrix storage with low-rank factors, matrix-free operators, or sparse graph decompositions, these methods collectively allow convex optimization to scale to millions of variables on standard hardware.

Key Foundational Work

Fast ADMM for semidefinite programs with chordal sparsity (2017) — contributed 1 concept elements to this direction.
Fast SDP Relaxations of Graph Cut Clustering, Transduction, and Other Combinatorial Problems (2006) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_memory_constrained_optimization_quadrati_caf660da,
  title = {memory-constrained optimization (quadratic memory scaling)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/memory-constrained-optimization-quadratic-memory-scaling/rdr_caf660da372149259d23947dcc984c3f},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_memory_constrained_optimization_quadrati_caf660da_v1,
  title = {memory-constrained optimization (quadratic memory scaling)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/memory-constrained-optimization-quadratic-memory-scaling/rdr_caf660da372149259d23947dcc984c3f/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake