Semidefinite Programming

Linear programming lets you optimize a linear goal over variables boxed in by linear inequalities — and we can solve it in polynomial time. Semidefinite programming (SDP) is its bigger cousin: instead of a vector of numbers, the unknown is a whole matrix, and the one extra rule is that this matrix must be positive-semidefinite — geometrically, it must describe a valid set of vectors and angles between them.

That sounds abstract, but it buys something remarkable. The set of positive-semidefinite matrices is convex — a smooth, bowl-shaped region with no traps — so we can still optimize over it efficiently. SDP sits squarely between the easy linear world and the brutal combinatorial one.

Its most famous use is a magic trick on a hard problem: take Max-Cut, an NP-hard problem, relax it into an SDP, solve that exactly, then round the answer back. The result is a cut provably at least 87.8% as good as the impossible-to-find best.

Max-Cut asks you to split a graph's nodes into two teams so that as many edges as possible cross between teams. The SDP relaxation replaces each node with a unit vector and tries to push vectors of connected nodes far apart. Here those vectors already sit on a circle — now comes the clever part.

<p class="hint">{{hint}}</p>
<canvas id="cv" width="320" height="320" aria-label="{{canvas_aria}}"></canvas>
<div class="stats">
  <div>{{this_cut}} <b id="cur">—</b> / <span id="m">5</span> {{edges}}</div>
  <div>{{throws_label}} <b id="n">0</b> &nbsp; {{avg_label}} <b id="avg">—</b></div>
  <div>{{gw_bound}}</div>
</div>
<div class="btns">
  <button id="throw" type="button">{{btn_throw}}</button>
  <button id="auto" type="button">{{btn_auto}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
canvas { display: block; margin: 0 auto; background: #f5f8fb; border: 1px solid #cdd9e3; border-radius: 10px; }
.stats { font-size: .95rem; margin: .7rem 0; line-height: 1.7; }
.stats b { color: #1d3557; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Press Throw a random hyperplane to slice the circle with a random line: every vector on one side joins team A, the rest team B. Edges whose endpoints land on opposite sides are cut. A single throw is luck, but average many throws and the cut settles near the Goemans-Williamson guarantee — at least 0.878 of the relaxation's value, which itself upper-bounds the true optimum.

Where does SDP sit on the map of hardness?

• Solving the SDP is easy. Because the feasible region is convex, interior-point methods find a solution to any desired accuracy in polynomial time. This is a solved algorithmic problem.
• The target, Max-Cut, is not. Deciding the maximum cut of a graph is NP-hard — almost certainly with no polynomial exact algorithm (see P vs NP).
• The bridge is rounding. In 1995, Michel Goemans and David Williamson showed that solving the SDP relaxation and rounding with a random hyperplane yields a cut worth at least $\alpha \approx 0.87856$ of the optimum — a constant-factor approximation, not an exact answer.
• And 0.878 may be the end of the line. Under the Unique Games Conjecture (Khot, 2002 — still open), no polynomial-time algorithm can beat that constant. So SDP rounding might be optimal, not merely good.

The lesson: a solved convex problem (SDP) becomes the sharpest known tool against an unsolved combinatorial one (Max-Cut). We do not break NP-hardness — we approximate it as well as anyone provably can.

Once you can optimize over positive-semidefinite matrices, a surprising range of problems falls into reach:

• Approximation algorithms: Max-Cut is the flagship, but SDP relaxations give the best known bounds for graph coloring, graph coloring variants, and many constraint problems.
• Control and engineering: stability of a system often reduces to a linear matrix inequality — exactly an SDP feasibility question.
• Quantum information: certifying entanglement and bounding quantum protocols are naturally SDPs over density matrices.
• Sensor and machine learning: localizing nodes from distances, low-rank matrix completion and kernel learning all lean on SDP.

The thread is the same one Max-Cut shows off: take a hard, discrete question, relax it into a smooth matrix world, solve that, and round — close cousins of the trick behind SAT-style constraint reasoning.

Semidefinite programming is a quiet workhorse with a spectacular party trick. Lift a stubborn combinatorial problem into the convex world of positive-semidefinite matrices, solve it exactly in polynomial time, then drop back down with a single random hyperplane — and you walk away with a cut guaranteed to be at least 87.8% as good as a best answer you could never compute.

That number is not arbitrary. It is a hard-won theorem from 1995, and under the still-open Unique Games Conjecture it may be the very best any efficient algorithm can promise. SDP is the rare place where the limits of computation, explored in P vs NP, come with a precise, beautiful, and possibly final guarantee.