Introduction

Some of the hardest problems in computer science ask you to make a collection of yes/no decisions — assign this city to cluster A or B, cut this edge or leave it, color this node red or blue. The number of candidate solutions grows exponentially, and exhaustive search quickly becomes hopeless.

Semidefinite relaxation is a surprising escape route: instead of forcing every variable to be exactly 0 or 1, you let each one become a unit vector in high-dimensional space. The resulting problem — a semidefinite program (SDP) — is convex, can be solved in polynomial time, and its optimum is an upper bound on the hard discrete problem. Then you round the vectors back into binary choices using a randomized geometric trick.

The classic showcase is the Goemans-Williamson algorithm (1995) for the Max-Cut problem. Given a graph, partition its vertices into two groups to maximize the number of edges that cross the partition. Max-Cut is NP-hard, so no one expects an exact polynomial algorithm. Goemans and Williamson showed that their SDP rounding achieves at least 0.878 (about 87.8%) of the optimal cut — a provable guarantee, not just an empirical observation.

Try It

The demo below runs a simplified Goemans-Williamson-style rounding on a small graph. Each node starts with a random unit vector in 2-D (the SDP assigns unit vectors in nn-D; 2-D is enough to visualize the idea). A random hyperplane through the origin splits the plane, assigning every node to side A or B depending on which half-plane its vector lands in.

<!-- Max-Cut with SDP-style hyperplane rounding (Goemans-Williamson) -->
<p class="hint">Each numbered node holds a unit vector (yellow arrow). A random hyperplane (dashed line) splits nodes into <b>side A (red)</b> and <b>side B (blue)</b>. Red edges cross the cut. Try many random hyperplanes to find a near-optimal partition.</p>
<div class="canvas-wrap">
  <canvas id="cv" width="320" height="220"></canvas>
</div>
<div class="status" id="status">Press a button to start.</div>
<div class="btns">
  <button id="btn-random" type="button">New random cut</button>
  <button id="btn-best" type="button">Best of 20</button>
  <button id="btn-reset" type="button" class="ghost">Reset vectors</button>
</div>
<div class="legend" id="legend"></div>

/* Layout and colour styles for the SDP rounding demo. */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; padding: .5rem; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
.canvas-wrap { display: flex; justify-content: center; margin: 0 0 .5rem; }
canvas { border: 1px solid #cdd9e3; border-radius: 8px; background: #f8fafc; max-width: 100%; }
.status { font-size: .95rem; font-weight: 600; min-height: 1.4em; margin: .3rem 0; }
.status.ok { color: #0a7d33; }
.status.info { color: #1d3557; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .4rem; }
button { font: 600 14px system-ui, sans-serif; padding: .42rem .85rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.legend { font-size: .82rem; color: #555; line-height: 1.6; }
.legend span { display: inline-block; width: 10px; height: 10px;
               border-radius: 50%; margin-right: 4px; vertical-align: middle; }
.dot-a { background: #e63946; }
.dot-b { background: #457b9d; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// 5-node graph: nodes 0-4, 8 edges.
// Optimal max-cut = 6 (e.g. partition {0,4} vs {1,2,3}).
const NODES = [
  { x: 80,  y: 60  },
  { x: 240, y: 60  },
  { x: 160, y: 130 },
  { x: 60,  y: 170 },
  { x: 260, y: 170 }
];
const EDGES = [[0,1],[0,2],[0,3],[1,2],[1,4],[2,3],[2,4],[3,4]];
// Optimal cut value for this graph: 6 edges.
// Partition A={0,4}, B={1,2,3} achieves it (0-indexed).
const OPTIMAL = 6;

// Each node gets a random 2-D unit vector (simulates the SDP solution).
// In full Goemans-Williamson the vectors live in n-D and are SDP-optimal.
let vecs = NODES.map(() => randomUnit());

function randomUnit() {
  const a = Math.random() * 2 * Math.PI;
  return [Math.cos(a), Math.sin(a)];
}

// Hyperplane normal vector from angle; classify nodes by which side they fall on.
function cutFromAngle(angle) {
  const nx = -Math.sin(angle), ny = Math.cos(angle); // normal to the hyperplane
  return NODES.map((_, i) => {
    const dot = vecs[i][0] * nx + vecs[i][1] * ny;
    return dot >= 0 ? 0 : 1; // side 0 = A, side 1 = B
  });
}

function countCut(sides) {
  return EDGES.filter(([u, v]) => sides[u] !== sides[v]).length;
}

let currentSides = NODES.map(() => 0);
let currentAngle = 0;

function draw(angle, sides) {
  const cv = document.getElementById('cv');
  const ctx = cv.getContext('2d');
  const W = cv.width, H = cv.height;
  ctx.clearRect(0, 0, W, H);

  // Draw the random hyperplane (dashed line through canvas centre).
  const nx = -Math.sin(angle), ny = Math.cos(angle);
  const cx = W / 2, cy = H / 2, len = Math.max(W, H);
  ctx.save();
  ctx.setLineDash([6, 4]);
  ctx.strokeStyle = '#aaa';
  ctx.lineWidth = 1.2;
  ctx.beginPath();
  ctx.moveTo(cx - ny * len, cy + nx * len);
  ctx.lineTo(cx + ny * len, cy - nx * len);
  ctx.stroke();
  ctx.restore();

  // Draw edges — red if cut, grey otherwise.
  for (const [u, v] of EDGES) {
    const cut = sides[u] !== sides[v];
    ctx.beginPath();
    ctx.moveTo(NODES[u].x, NODES[u].y);
    ctx.lineTo(NODES[v].x, NODES[v].y);
    ctx.strokeStyle = cut ? '#e63946' : '#c9ccd1';
    ctx.lineWidth = cut ? 2.2 : 1.4;
    ctx.stroke();
  }

  // Draw nodes coloured by side.
  const COLORS = ['#e63946', '#457b9d'];
  for (let i = 0; i < NODES.length; i++) {
    const { x, y } = NODES[i];
    ctx.beginPath();
    ctx.arc(x, y, 14, 0, 2 * Math.PI);
    ctx.fillStyle = COLORS[sides[i]];
    ctx.fill();
    ctx.strokeStyle = '#fff';
    ctx.lineWidth = 2;
    ctx.stroke();
    ctx.fillStyle = '#fff';
    ctx.font = 'bold 11px system-ui, sans-serif';
    ctx.textAlign = 'center';
    ctx.textBaseline = 'middle';
    ctx.fillText(i + 1, x, y);

    // Draw the unit vector as a short yellow arrow.
    const vx = vecs[i][0] * 18, vy = vecs[i][1] * 18;
    ctx.beginPath();
    ctx.moveTo(x, y);
    ctx.lineTo(x + vx, y + vy);
    ctx.strokeStyle = '#ffd166';
    ctx.lineWidth = 1.5;
    ctx.stroke();
  }
}

function randomCut() {
  currentAngle = Math.random() * 2 * Math.PI;
  currentSides = cutFromAngle(currentAngle);
  const n = countCut(currentSides);
  draw(currentAngle, currentSides);
  const pct = Math.round(100 * n / OPTIMAL);
  const el = document.getElementById('status');
  el.textContent = i18nFmt('Cut: %n% / %opt% edges (%pct%%)', { n: n, opt: OPTIMAL, pct: pct });
  el.className = 'status ok';
  updateLegend(currentSides);
}

function bestOf20() {
  let bestSides = null, bestN = -1, bestAngle = 0;
  for (let t = 0; t < 20; t++) {
    const a = Math.random() * 2 * Math.PI;
    const s = cutFromAngle(a);
    const n = countCut(s);
    if (n > bestN) { bestN = n; bestSides = s; bestAngle = a; }
  }
  currentAngle = bestAngle;
  currentSides = bestSides;
  draw(currentAngle, currentSides);
  const pct = Math.round(100 * bestN / OPTIMAL);
  const el = document.getElementById('status');
  el.textContent = i18nFmt('Best of 20 cuts: %n% / %opt% edges (%pct%%)', { n: bestN, opt: OPTIMAL, pct: pct });
  el.className = 'status ok';
  updateLegend(currentSides);
}

function updateLegend(sides) {
  const aNodes = sides.map((s, i) => s === 0 ? i + 1 : null).filter(Boolean).join(', ');
  const bNodes = sides.map((s, i) => s === 1 ? i + 1 : null).filter(Boolean).join(', ');
  document.getElementById('legend').innerHTML =
    '<span class="dot-a"></span> Side A: nodes ' + aNodes +
    ' &nbsp; <span class="dot-b"></span> Side B: nodes ' + bNodes +
    '<br>Optimal cut: ' + OPTIMAL + ' edges';
}

function resetDemo() {
  vecs = NODES.map(() => randomUnit());
  currentSides = NODES.map(() => 0);
  currentAngle = 0;
  draw(currentAngle, currentSides);
  const el = document.getElementById('status');
  el.textContent = 'Press a button to start.';
  el.className = 'status info';
  document.getElementById('legend').innerHTML =
    'Optimal cut: ' + OPTIMAL + ' edges';
}

document.getElementById('btn-random').addEventListener('click', randomCut);
document.getElementById('btn-best').addEventListener('click', bestOf20);
document.getElementById('btn-reset').addEventListener('click', resetDemo);

// Initial draw with all nodes in side A (no cut yet).
draw(currentAngle, currentSides);
document.getElementById('legend').innerHTML = 'Optimal cut: ' + OPTIMAL + ' edges';
Result
Console

Click New random cut to draw a fresh hyperplane and see a different partition. Click Best of 20 to run 20 random cuts and keep the one with the most crossing edges — this is exactly how the Goemans-Williamson rounding works in practice. Notice how often the result matches or nearly matches the true optimum shown at the bottom.

The Real Complexity

The SDP relaxation sits at a remarkable intersection of geometry, algebra and complexity theory.

  • Solving the SDP is the easy part. Semidefinite programs are convex and can be solved to any desired accuracy in polynomial time by interior-point methods. The number of variables is O(n2)O(n^{2}) (one entry per pair of vectors), and modern solvers handle instances with thousands of nodes.
  • The rounding guarantee. After solving, each node ii holds a unit vector viv_{i}. A random unit vector rr is drawn; node ii goes to side A if r⋅vi≥0r \cdot v_{i} \geq 0, else side B. For each edge (i,j)(i,j), the probability that it is cut equals θijπ\frac{\theta_{ij}}{\pi}, where θij\theta_{ij} is the angle between viv_{i} and vjv_{j}. Goemans and Williamson proved that θ/π(1−cos⁡θ)/2≥0.878\frac{\theta / \pi}{(1 - \cos \theta)/2} \geq 0.878 for all θ∈[0,π]\theta \in [0, \pi], so the expected cut is at least 0.8780.878 times the SDP optimum, which is itself at least the true optimum.
  • Optimality under the Unique Games Conjecture. Khot, Kindler, Mossel and O'Donnell (2007) showed that if the Unique Games Conjecture is true, then no polynomial-time algorithm can beat the 0.878 factor. The conjecture is widely believed but not proved, making 87.8% the likely-best barrier for max-cut.
  • Beyond max-cut. The same toolkit powers approximation algorithms for graph coloring, constraint satisfaction, and quantum information problems. SDP hierarchies (Lasserre, Sherali-Adams+SDP) can squeeze out even better bounds by adding more rounds of relaxation.

Where It Matters

Semidefinite relaxation is not just a theoretical curiosity — it delivers practical near-optimal solutions in many fields:

  • VLSI circuit partitioning: dividing a chip's components between two halves of a board to minimize the wire crossings is essentially a max-cut problem. SDP rounding gives a proven near-optimal split.
  • Community detection in networks: finding densely-connected clusters in social or biological networks can be cast as a graph-partitioning SDP, yielding provably good community structure.
  • Quantum information theory: the quantum chromatic number and other quantum graph parameters are naturally expressed as SDPs. Semidefinite programming is the primary tool for bounding what quantum protocols can achieve.
  • Constraint satisfaction and MAX-2-SAT: the Goemans-Williamson technique extends to SAT-style problems, giving the best known approximation ratios for many CSPs.
  • Control theory and signal processing: stability analysis of dynamical systems and certain filter design problems reduce to checking feasibility of an SDP.

In all these cases the key payoff is the same: a polynomial-time algorithm with a provable worst-case guarantee, which heuristics and local search cannot match.

Conclusion

Semidefinite relaxation is one of the deepest ideas in the theory of algorithms: when a combinatorial problem is too hard to solve exactly, lift it into the geometry of unit vectors, solve the relaxed problem efficiently, then slice the sphere with a random hyperplane to snap everything back to a discrete answer.

The result is not just "usually good" — it comes with a mathematical guarantee. For max-cut that guarantee is 87.8%, and it is likely the best any efficient algorithm can ever achieve. That is the quiet power of the technique: it turns intractability from a wall into a precisely measured gap, and shows us exactly how close we can get to the optimal answer without breaking the bounds of polynomial time.

If you want to go further, the natural next step is the P vs NP question itself — the question that determines whether these gaps can ever be closed.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/semidefinite-relaxation/Content licensed under CC BY-NC 4.0.