We consider optimization problems containing nonconvex quadratic functions for which semidefinite programming (SDP) relaxations often yield strong bounds. We investigate linear inequalities that outer approximate the positive semidefinite cone and are sparse in the sense that they are supported only on the variables corresponding to products of variables present in quadratic functions. We show that these sparse linear inequalities yield an LP relaxation that gives the same bound as the SDP relaxation. We demonstrate how to identify these inequalities via a separation procedure that involves solving a structured ``projection'' SDP. In a computational study, we find that the sparse LP relaxations defined by these inequalities can accelerate branch-and-bound methods for globally solving nonconvex optimization problems.
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.
Alex: Okay, that keeps it simple and fast. What if the problem has non-negative variables?
Sam: Those allow a tighter relaxation called doubly nonnegative. It adds entrywise non-negativity on top of PSD—like requiring no negative numbers anywhere. The paper generalizes projection duality to show the sparse version matches the full bound.
Alex: So the hierarchy holds: QP bound greater than or equal to DNN equals sparse DNN greater than or equal to sparse SDP equals full SDP.
Sam: To add these cuts, they solve a separation SDP: find the most violated inequality by minimizing the inner product with the current LP point, over sparse PSD matrices normalized by diagonal sum at most one. For non-negative cases, they tweak it to allow non-positive entries outside the sparse spots.
Alex: And they speed it further by separating near the SDP solution itself?
Sam: Yes—blend a tiny bit of the LP point, like 0.001 times it, with the projected SDP optimum. Points near the true boundary yield better-approximating cuts, closing the gap faster despite solving the full SDP once upfront. The paper suggests this accelerates branch-and-bound notably on sparse networks.
Alex: Does the paper show how this plays out in actual tests—like on real problems?
Sam: Yes, they tested on synthetic box-constrained problems and QPLIB instances up to 200 variables. Sparse cuts close the gap to the SDP bound about as well as dense ones, but their linear programs solve orders of magnitude faster by ignoring irrelevant zeros. They plug these into Gurobi, a branch-and-bound solver. On harder cases, adding cuts lets it solve more instances to optimality within ten hours, often faster, because the root bound strengthens without slowing LPs. QPLIB results are mostly neutral or better.
Alex: Huh—so for power-grid-like sparse quadratics, the sparse cuts make global solving practical where it wasn't. The speedup comes from tight bounds without density drag.
Sam: That's the key. It makes strong SDP-level bounds usable in branch-and-bound at scale, a meaningful step for large sparse problems. A notable limitation is the need for an initial full SDP solve upfront, though it keeps total time competitive on tested networks up to 200 variables. In power grid optimization, dense SDP relaxations often fail on such sparse networks due to matrix density overwhelming solvers, but these sparse cuts make global solutions practical.
Alex: Well, that's a clear step forward for making tough optimizations workable on real hardware. Thanks, Sam—this has been a solid look at how sparse math unlocks practical solving.
Sam: My pleasure, Alex. It highlights careful exploitation of structure in optimization.