Stuck in the Wrong Valley

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.

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">{{hint}}</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">{{btn_many}}</button>
  <button id="reset" type="button" class="ghost">{{btn_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; }

// Code not found

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 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.

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.

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.