Introduction

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.

Round the Relaxation

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">Each node of the graph is a <b>unit vector</b> on this circle — the SDP relaxation spread them so connected nodes point apart. Throw a <b>random hyperplane</b> (a line through the center): nodes on one side join team A, the rest team B. Edges crossing the line are <b>cut</b>. One throw is luck; the running average closes on the 0.878 guarantee.</p>
<canvas id="cv" width="320" height="320" aria-label="Max-Cut SDP relaxation on a circle"></canvas>
<div class="stats">
  <div>This cut: <b id="cur">—</b> / <span id="m">5</span> edges</div>
  <div>Throws: <b id="n">0</b> &nbsp; Avg cut fraction: <b id="avg">—</b></div>
  <div>Goemans-Williamson bound: <b>0.87856 ×</b> relaxation</div>
</div>
<div class="btns">
  <button id="throw" type="button">Throw a random hyperplane</button>
  <button id="auto" type="button">Throw 200 ×</button>
  <button id="reset" type="button" class="ghost">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; }

// Goemans-Williamson rounding for Max-Cut.
// The SDP relaxation assigns each node a unit vector; here they live on a circle
// at the angles below (a good spread for this 5-cycle + chords graph). Rounding:
// pick a random hyperplane (a random direction theta); a node v goes to team A if
// dot(v, normal) >= 0, else team B. An edge (i,j) is cut iff its endpoints land on
// opposite sides. Expected cut probability for an edge = angle(i,j) / PI, and
// GW prove the rounded cut is >= 0.87856 * relaxation value in expectation.
const TAU = Math.PI * 2;
// angles (radians) of each node's unit vector, as an SDP solver might place them
const ANG = [0.4, 1.7, 2.9, 4.0, 5.2];
const V = ANG.map(a => [Math.cos(a), Math.sin(a)]);
// edges of the graph
const E = [[0,1],[1,2],[2,3],[3,4],[4,0]]; // a 5-cycle
const M = E.length;

let throws = 0, totalFrac = 0, lastNormal = null, lastTeam = null, lastCut = 0;

function rand(){ return Math.random(); }
function roundOnce(){
  const t = rand() * Math.PI;          // hyperplane direction in [0, PI)
  const nrm = [Math.cos(t + Math.PI/2), Math.sin(t + Math.PI/2)]; // its normal
  const team = V.map(v => (v[0]*nrm[0] + v[1]*nrm[1]) >= 0 ? 0 : 1);
  let cut = 0;
  for(const [i,j] of E) if(team[i] !== team[j]) cut++;
  return { t, nrm, team, cut };
}
function applyThrow(r){
  throws++; totalFrac += r.cut / M;
  lastNormal = [Math.cos(r.t), Math.sin(r.t)]; lastTeam = r.team; lastCut = r.cut;
  document.getElementById('cur').textContent = r.cut;
  document.getElementById('n').textContent = throws;
  document.getElementById('avg').textContent = (totalFrac / throws).toFixed(3);
  draw();
}

const cv = document.getElementById('cv'), ctx = cv.getContext('2d');
const CX = 160, CY = 160, R = 120;
const px = v => [CX + v[0]*R, CY - v[1]*R];
function draw(){
  ctx.clearRect(0,0,320,320);
  // circle
  ctx.strokeStyle = '#cdd9e3'; ctx.lineWidth = 1.5;
  ctx.beginPath(); ctx.arc(CX,CY,R,0,TAU); ctx.stroke();
  // hyperplane (the dividing line is perpendicular to lastNormal... we stored the line direction in lastNormal as [cos t, sin t])
  if(lastNormal){
    ctx.strokeStyle = '#e63946'; ctx.lineWidth = 2; ctx.setLineDash([6,4]);
    ctx.beginPath();
    ctx.moveTo(CX - lastNormal[0]*R*1.15, CY + lastNormal[1]*R*1.15);
    ctx.lineTo(CX + lastNormal[0]*R*1.15, CY - lastNormal[1]*R*1.15);
    ctx.stroke(); ctx.setLineDash([]);
  }
  // edges
  for(const [i,j] of E){
    const a = px(V[i]), b = px(V[j]);
    const isCut = lastTeam && lastTeam[i] !== lastTeam[j];
    ctx.strokeStyle = isCut ? '#0a7d33' : '#b9c2cc';
    ctx.lineWidth = isCut ? 3 : 1.5;
    ctx.beginPath(); ctx.moveTo(a[0],a[1]); ctx.lineTo(b[0],b[1]); ctx.stroke();
  }
  // nodes
  V.forEach((v,i)=>{
    const p = px(v);
    const t = lastTeam ? lastTeam[i] : -1;
    ctx.fillStyle = t === 0 ? '#1d3557' : (t === 1 ? '#f4a261' : '#8a94a0');
    ctx.beginPath(); ctx.arc(p[0],p[1],11,0,TAU); ctx.fill();
    ctx.fillStyle = '#fff'; ctx.font = '700 13px system-ui'; ctx.textAlign='center'; ctx.textBaseline='middle';
    ctx.fillText(String(i), p[0], p[1]);
  });
}
function reset(){ throws=0; totalFrac=0; lastNormal=null; lastTeam=null; lastCut=0;
  document.getElementById('cur').textContent='—'; document.getElementById('n').textContent='0';
  document.getElementById('avg').textContent='—'; draw(); }

document.getElementById('m').textContent = M;
document.getElementById('throw').addEventListener('click',()=>applyThrow(roundOnce()));
document.getElementById('auto').addEventListener('click',()=>{
  for(let k=0;k<200;k++){ const r=roundOnce(); throws++; totalFrac += r.cut/M;
    lastNormal=[Math.cos(r.t),Math.sin(r.t)]; lastTeam=r.team; lastCut=r.cut; }
  document.getElementById('cur').textContent=lastCut;
  document.getElementById('n').textContent=throws;
  document.getElementById('avg').textContent=(totalFrac/throws).toFixed(3);
  draw();
  console.log('After', throws, 'throws — avg cut fraction', (totalFrac/throws).toFixed(4));
});
document.getElementById('reset').addEventListener('click',reset);
reset();
Result
Console

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.

The Real Complexity

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 α≈0.87856\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.

Where It Matters

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.

Conclusion

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.

Share this article

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

Comments

Loading comments...

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