Transcript: Sparse Cuts for the Positive Semidefinite Cone

Alex: Welcome to another episode of ResearchPod.

Sam: This episode centers on a paper called "Sparse Cuts for the Positive Semidefinite Cone" by researchers including Oktay Günlük and others. The core idea is finding simple straight-line rules—linear inequalities—that match the tight bounds from heavy-duty semidefinite programming, but only using the few variables that actually matter in sparse problems.

Alex: So this paper tackles how to get the best possible lower bounds for tricky quadratic optimization problems without the huge computation cost of full matrix checks?

Sam: Yes, exactly. These problems show up in power grids and engineering—think minimizing costs where the math involves squares and products of variables, like x squared plus x times y. That creates a bumpy landscape that's hard to optimize globally. The standard fix is an SDP relaxation: you lift the variables into a bigger matrix and require it to be positive semidefinite, meaning it bends only one way, like a bowl that doesn't go negative. That gives strong bounds, but solving big SDPs at every step of branch-and-bound search is slow, especially on 200-variable networks.

Alex: Right, so the bottleneck is that full SDP checks are computationally heavy when the problem is sparse—most terms are zero—and branch-and-bound needs fast relaxations at thousands of nodes.

Sam: Precisely. In sparse cases, the key interactions are in a small set of positions: diagonals, borders, and nonzero spots. Standard cutting planes from eigenvectors are dense, forcing all variables into play and causing slowdowns. This work proves you can project the PSD cone onto just those spots, generating sparse linear inequalities—or cuts—that outer-approximate it exactly, matching the full SDP bound with LP speed.

Alex: Okay, so these sparse cuts use only the problem's own variables, like ignoring empty space on a map. But how do they guarantee the same bound as the dense SDP?

Sam: The proof hinges on projection duality: the shadow of the full PSD cone onto the sparse spots is exactly the dual of the supported PSD matrices there. Any feasible sparse matrix lifts to a full PSD one matching objectives on those spots. In practice, they separate cuts via a structured projection SDP near the SDP optimum—like blending a tiny bit of the current LP point with the SDP solution—to accelerate branch-and-bound on sparse problems.

Alex: So these sparse cuts match the full SDP bound exactly, even though they only touch the key spots. But how do they prove you don't need tons of them—just a handful?

Sam: They start from the full set of cuts that tighten a dense SDP to its optimum. Then, by projecting those onto just the sparse positions—like ignoring irrelevant blanks on a form—the result stays tight there. The needed cuts come from supported PSD matrices, so at most as many as those spots suffice.