Introduction

You're tuning a machine with a dozen knobs to make some cost — error, waste, money — as small as possible. The natural strategy is to feel which way is downhill and step that way, again and again. That's gradient descent, and on a smooth, bowl-shaped landscape it glides straight to the bottom.

But most real cost landscapes aren't bowls. They're bumpy: ridges, dips and valleys all over. Roll downhill and you settle into a valley — but is it the deepest one? Often not. You've found a local minimum, while the global minimum sits in some other valley you never reached, on the far side of a hill you'd have to climb to escape.

Finding the global minimum of such a non-convex function is, in general, NP-hard. Yet it's the daily reality of training neural networks, designing engineering systems and optimizing portfolios — which is why so much cleverness goes into not getting stuck.

Roll the Ball

Try it. Click anywhere on the bumpy curve to drop a ball there. It rolls downhill (gradient descent) and settles into the nearest valley. Did it find the deepest valley — the global minimum — or get trapped in a shallower one?

<p class="hint">Click anywhere on the curve to drop a ball. It rolls <b>downhill</b> (gradient descent) into the nearest valley. Did it reach the <span class="g">deepest</span> one — or get <span class="r">trapped</span>?</p>
<svg id="plot" viewBox="0 0 480 220" class="plot"></svg>
<div id="status" class="status"></div>
<div class="btns">
  <button id="many" type="button">Many starts</button>
  <button id="reset" type="button" class="ghost">Clear</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; }
.hint .g { color: #0a7d33; font-weight: 700; } .hint .r { color: #c0392b; font-weight: 700; }
.plot { width: 100%; max-width: 520px; background: #f4f7f9; border: 1px solid #e2e6eb; border-radius: 10px; display: block; cursor: pointer; }
.curve { fill: none; stroke: #457b9d; stroke-width: 2.5; }
.gmark { stroke: #0a7d33; stroke-width: 1.5; stroke-dasharray: 3 3; }
.ball { fill: #e76f51; stroke: #fff; stroke-width: 1.5; }
.ball.good { fill: #0a7d33; }
.status { font-weight: 800; min-height: 1.4em; margin: .8rem 0 .5rem; font-size: 1rem; }
.status.g { color: #0a7d33; } .status.r { color: #c0392b; } .status.n { color: #777; }
.btns { display: flex; gap: .5rem; }
button { font: 600 14px system-ui, sans-serif; padding: .5rem 1rem; border: 1px solid #457b9d; background: #457b9d; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #457b9d; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Non-convex optimization: gradient descent rolls a ball downhill into the
    // NEAREST valley (local minimum) — not necessarily the global one. Finding
    // the global minimum of a bumpy function is NP-hard in general.
const X0 = 0, X1 = 10, PADL = 20, PADR = 460, PADT = 20, PADB = 195;
function f(x) { return 0.6 * Math.sin(1.6 * x) + Math.sin(0.75 * x + 0.5) + 0.07 * (x - 5) * (x - 5); }
function df(x) { const h = 1e-4; return (f(x + h) - f(x - h)) / (2 * h); }
// sample for plot range + global min
let YMIN = Infinity, YMAX = -Infinity, GX = 0, GMIN = Infinity;
for (let i = 0; i <= 600; i++) { const x = X0 + (X1 - X0) * i / 600, y = f(x); if (y < YMIN) YMIN = y; if (y > YMAX) YMAX = y; if (y < GMIN) { GMIN = y; GX = x; } }
const sx = x => PADL + (x - X0) / (X1 - X0) * (PADR - PADL);
const sy = y => PADT + (1 - (y - YMIN) / (YMAX - YMIN)) * (PADB - PADT);
const fromSx = px => X0 + (px - PADL) / (PADR - PADL) * (X1 - X0);

function descend(x) { let lr = 0.06; for (let i = 0; i < 220; i++) { x -= lr * df(x); x = Math.max(X0, Math.min(X1, x)); } return x; }

let balls = []; // {x}
let anim = null;

function curvePath() { let d = ''; for (let i = 0; i <= 240; i++) { const x = X0 + (X1 - X0) * i / 240; d += (i ? 'L' : 'M') + sx(x).toFixed(1) + ' ' + sy(f(x)).toFixed(1) + ' '; } return d; }

function render() {
  let s = '<path class="curve" d="' + curvePath() + '"/>';
  s += '<line class="gmark" x1="' + sx(GX) + '" y1="' + sy(GMIN) + '" x2="' + sx(GX) + '" y2="' + PADB + '"/>';
  s += fmt('<text x="%v%" y="%PADB%%v2%" style="font:600 9px system-ui;fill:#0a7d33">global min</text>', { v: sx(GX) - 4, PADB: PADB, v2: 14 });
  balls.forEach(b => { const good = Math.abs(f(b.x) - GMIN) < 0.15; s += '<circle class="ball' + (good ? ' good' : '') + '" cx="' + sx(b.x) + '" cy="' + (sy(f(b.x)) - 6) + '" r="6"/>'; });
  document.getElementById('plot').innerHTML = s;
}

function dropAt(px) {
  if (anim) { clearInterval(anim); anim = null; }
  let x = Math.max(X0, Math.min(X1, fromSx(px)));
  balls = [{ x }];
  let step = 0;
  anim = setInterval(() => {
    x -= 0.06 * df(x); x = Math.max(X0, Math.min(X1, x)); balls[0].x = x; render();
    if (++step > 200) { clearInterval(anim); anim = null; finish(x); }
  }, 16);
  render();
}

function finish(x) {
  const st = document.getElementById('status');
  if (Math.abs(f(x) - GMIN) < 0.15) { st.className = 'status g'; st.textContent = '✓ Reached the global minimum!'; }
  else { st.className = 'status r'; st.textContent = '✗ Trapped in a local valley — the global minimum is deeper, elsewhere.'; }
}

function many() {
  if (anim) { clearInterval(anim); anim = null; }
  balls = [];
  let reached = 0;
  for (let i = 0; i < 11; i++) { const start = X0 + (X1 - X0) * (i + 0.5) / 11; const end = descend(start); balls.push({ x: end }); if (Math.abs(f(end) - GMIN) < 0.15) reached++; }
  render();
  const st = document.getElementById('status');
  st.className = 'status n';
  st.innerHTML = fmt('From 11 evenly spaced starts, only <b style="color:#0a7d33">%reached%</b> reached the global minimum — the rest got stuck. That’s why optimizers use many random restarts.', { reached: reached });
}

document.getElementById('plot').addEventListener('click', e => {
  const svg = document.getElementById('plot'); const r = svg.getBoundingClientRect();
  const px = (e.clientX - r.left) / r.width * 480; dropAt(px);
});
document.getElementById('many').addEventListener('click', many);
document.getElementById('reset').addEventListener('click', () => { if (anim) clearInterval(anim); anim = null; balls = []; document.getElementById('status').textContent = ''; render(); });
render();
Result
Console

Drop it from different spots and watch the outcome change: the same simple rule lands in different valleys depending on where it starts. Hit Many starts to scatter balls everywhere — only some find the true bottom. That's the whole trap of non-convex optimization, live.

The Hard Part

The dividing line is convexity:

  • Convex problems are easy. If the landscape is a single bowl (convex), every local minimum is the global one — so rolling downhill always works, in polynomial time. This is the happy world of linear and convex programming.
  • Non-convex is NP-hard. With many valleys, no local rule can know whether a better one lies beyond the next hill. In general, finding the global minimum is NP-hard — you might have to inspect exponentially many valleys.
  • Checking is hard too. Unlike many problems here, even verifying you've found the global minimum can be intractable — there's no easy certificate that no deeper valley exists.
  • The toolbox of escape. In practice: random restarts (drop many balls), momentum (roll through shallow dips), simulated annealing (occasionally climb), and convex relaxations (approximate the bumpy problem with a bowl).
  • The surprise of deep learning. Training neural nets is wildly non-convex, yet gradient descent works astonishingly well — because in very high dimensions, most traps are saddle points, not bad local minima. Why it works so well is still an active research mystery.

So non-convexity is where "just roll downhill" meets its limit — and where most of the art of modern optimization lives.

Where It Matters

Bumpy landscapes are everywhere optimization meets the real world:

  • Machine learning: training neural networks minimizes a hugely non-convex loss — the defining computation of modern AI. See neural network training.
  • Engineering design: shaping wings, structures and circuits to minimize weight, drag or cost.
  • Finance: portfolio optimization with realistic, non-convex constraints.
  • Control and robotics: trajectory and motion planning over rugged cost surfaces.
  • Physics and chemistry: finding minimum-energy configurations (protein folding, molecular structure).

Because the global optimum is out of reach in general, these fields prize good enough solutions — and the heuristics that reliably find them.

Conclusion

Non-convex optimization is the gap between "I found a good answer" and "I found the best answer." Roll downhill on a bumpy landscape and you'll always reach a valley — just rarely a guarantee that it's the deepest. That guarantee is exactly what NP-hardness denies you.

And yet this is one of the most quietly triumphant hard problems on the site: the entire deep-learning revolution runs on gradient descent over ferociously non-convex landscapes, succeeding far better than theory says it should. Non-convexity reminds us that "NP-hard in the worst case" and "works beautifully in practice" can both be true — and that the space between them is where a lot of the future is being built.

Share this article

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

Comments

Loading comments...

https://www.kipuhub.com/en/article/non-convex-optimization/Content licensed under CC BY-NC 4.0.