Semidefinite Programming (SDP) is the gold standard for convex relaxation. When faced with an NP-hard combinatorial or non-linear problem—such as finding dense subgraphs, synchronizing 3D poses in robotics, or certifying the safety of a neural network—researchers frequently lift the problem into a higher-dimensional matrix space. This relaxation yields a convex optimization problem that provides remarkably tight, provably robust bounds.
However, this theoretical elegance comes with a severe practical penalty: SDPs scale notoriously poorly. While a Linear Program (LP) deals with vectors, an SDP operates on a positive semidefinite matrix $X \in \mathbb{S}^n_+$. This dimensionality shift introduces a cubic or higher computational complexity per iteration, creating a scalability wall that historically prevented SDPs from being deployed on large-scale deep networks or massive real-world graphs.
To understand why SDPs are so expensive—and how a modern wave of research is making them scalable—we must look under the hood at the exact mathematical bottlenecks and the clever algorithmic workarounds designed to bypass them.
The Geometry of the Bottleneck
Why are SDPs so much harder to solve than LPs? In an LP with $n$ variables, the solver tracks a vector. In an SDP, the decision variable is an $n \times n$ matrix $X$. Enforcing the constraint that $X$ must be positive semidefinite ($X \succeq 0$) means the solver is effectively managing $O(n^2)$ interacting entries.
When traditional Interior Point Methods (IPMs) solve an SDP, they compute a series of Newton steps to navigate the interior of the feasible region. This requires computing and inverting a Hessian matrix. Because the slack variables are matrices rather than vectors, the Hessian inherits a complex Kronecker product structure. As noted by Huang et al. in Solving SDP Faster: A Robust IPM Framework and Efficient Implementation, this structure forces standard solvers to spend a prohibitive amount of time performing matrix inversions and handling dense algebraic overhead at every single iteration.
For a problem with $m$ constraints and an $n \times n$ matrix, a naive IPM requires $O(m \cdot n^3 + m^2 \cdot n^2 + m^3)$ time per step. If $n$ represents the number of neurons in a network or nodes in a graph, this cubic scaling quickly leads to memory exhaustion and computational paralysis.
Amortizing the Cost of Interior Point Methods
One way to scale SDPs is to fix IPMs from the inside out. If the primary bottleneck is the cost of recomputing and inverting the Hessian and slack matrices at every step, can we avoid doing it from scratch?
Jiang et al. broke this long-standing efficiency paradox in A Faster Interior Point Method for Semidefinite Programming. The core intuition is laziness: instead of fully updating the slack matrix at every iteration, the authors developed a novel low-rank maintenance strategy. By combining this with fast rectangular matrix multiplication, they amortized the cost of matrix operations across multiple steps.
Building on this philosophy, Huang et al. introduced a robust IPM framework that explicitly tolerates controlled numerical errors in the Newton steps. This error tolerance allows the solver to perform lazy, low-rank updates to the Hessian matrix rather than recalculating it entirely. By treating the heavy algebraic steps as a sequence of cheap, incremental updates, these modern IPMs can solve "tall dense" SDPs in a time complexity that approaches that of solving a standard system of linear equations.
Bypassing Convexity via Low-Rank Factorization
While accelerating IPMs pushes the theoretical boundaries, another highly successful paradigm abandons the massive $n \times n$ matrix entirely. This is known as the Burer-Monteiro approach.
The intuition is straightforward: if the optimal solution matrix $X$ is expected to be low-rank, why optimize over all $n \times n$ entries? Instead, we can factorize the matrix explicitly as $X = Y Y^T$, where $Y$ is an $n \times p$ matrix with a rank $p \ll n$. By substituting $Y Y^T$ into the SDP, we reduce the number of decision variables from $O(n^2)$ to $O(np)$, drastically shrinking the memory footprint and computational overhead.
The catch is that this factorization destroys convexity. The optimization landscape becomes non-convex, raising the prospect of getting trapped in poor local minima.
However, Boumal et al. provided a profound theoretical justification for why this trick works so well in practice. In The non-convex Burer-Monteiro approach works on smooth semidefinite programs, the authors proved that for a broad class of smooth SDPs, the non-convex landscape is surprisingly benign. Specifically, if the chosen rank $p$ satisfies the geometric threshold
$$\frac{p(p+1)}{2} > m$$
(where $m$ is the number of constraints), the problem almost never contains spurious local optima. Because the number of degrees of freedom in the low-rank matrix exceeds the number of constraints, the optimization landscape becomes smooth and free of traps. Local optimization methods, like Riemannian gradient descent, are guaranteed to converge to the global optimum, allowing large-scale synchronization and computer vision problems to be solved rapidly without the burden of full-scale SDP matrices.
First-Order Approximations and Sublinear Proxies
For ultra-large-scale applications—such as web-scale graph processing or deep neural network verification—even low-rank factorizations or optimized IPMs can hit a wall. In these regimes, researchers trade exact optimality for extreme speed, utilizing first-order optimization or spectral proxies.
Instead of relying on second-order Newton steps, first-order methods use only gradient information, which requires far less memory and avoids matrix inversions entirely. For instance, Garber et al. demonstrated in Approximating Semidefinite Programs in Sublinear Time that it is possible to compute approximate solutions to SDPs in sublinear time relative to the matrix size, bypassing the exact solution bottleneck entirely for specific machine learning applications.
Similarly, when dealing with the massive semidefinite programs generated by the Sum-of-Squares (SoS) hierarchy—a powerful framework introduced by Lasserre in A SUM OF SQUARES APPROXIMATION OF NONNEGATIVE POLYNOMIALS—the computational cost can be overwhelming. To circumvent this, Schramm et al. developed fast spectral algorithms in Fast and robust tensor decomposition with applications to dictionary learning. These spectral algorithms act as nearly linear-time proxies that mimic the structural robustness of full SoS semidefinite programs without ever forcing the computer to solve the underlying massive matrix inequalities.