Introduction

Every optimization problem has the same skeleton: you have a set of choices and a cost, and you want the choice that makes the cost as small as possible. Train a neural network, plan a supply chain, price a financial portfolio — they all reduce to "minimize this function."

The hard part is that most functions are bumpy. Slide downhill and you can land in a valley that looks like a minimum but is really just a local dip — the true bottom is somewhere else, and descent can't see it from here.

Convexity removes that trap. A function is convex if its graph looks like a bowl: the line connecting any two points on it always stays above or on the curve. In such a landscape there are no false valleys — any direction that looks downhill locally is downhill globally, and gradient descent always reaches the one true minimum.

That single geometric property is the dividing line between optimization we understand deeply and optimization that can be provably intractable.

Drop the Ball

Click anywhere on either surface to drop a ball and watch gradient descent roll it downhill. The convex bowl always delivers the ball to the same bottom; the bumpy surface may trap it in a local valley depending on where you start.

<p class="hint">Click anywhere on either surface to drop a ball and watch gradient descent roll it to the bottom. The convex bowl <b>always</b> finds the global minimum; the bumpy surface may get stuck in a local dip.</p>
<div class="canvases">
  <div class="panel">
    <div class="panel-label">Convex bowl</div>
    <canvas id="cvx" width="220" height="180"></canvas>
    <div class="panel-status" id="cvx-status"></div>
  </div>
  <div class="panel">
    <div class="panel-label">Bumpy surface</div>
    <canvas id="noncvx" width="220" height="180"></canvas>
    <div class="panel-status" id="noncvx-status"></div>
  </div>
</div>
<div class="btns">
  <button id="reset" type="button" class="ghost">Reset both</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 .8rem; line-height: 1.45; }
.canvases { display: flex; gap: 12px; flex-wrap: wrap; margin-bottom: .6rem; }
.panel { display: flex; flex-direction: column; align-items: center; }
.panel-label { font-size: .78rem; font-weight: 700; color: #1d3557; margin-bottom: 3px;
               text-transform: uppercase; letter-spacing: .04em; }
canvas { border: 1px solid #cdd9e3; border-radius: 8px; cursor: crosshair;
         background: #f4f7fb; display: block; }
.panel-status { font-size: .82rem; font-weight: 600; min-height: 1.3em; margin-top: 4px;
                text-align: center; }
.panel-status.ok { color: #0a7d33; }
.panel-status.trapped { color: #c92f3c; }
.btns { margin-top: .3rem; }
button { font: 600 14px system-ui, sans-serif; padding: .4rem .85rem;
         border: 1px solid #1d3557; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Convex vs non-convex gradient descent demo.
// Each canvas shows a 1-D cross-section of a surface.
// The user clicks to set a starting x; we run gradient descent
// and animate the ball rolling to a minimum.
//
// Convex function:   f(x) = (x-0.5)^2          -- single global min at x=0.5
// Non-convex:        f(x) = 0.18*sin(12x) + 0.6*(x-0.5)^2
//                    -- 2 interior local minima at ~x=0.40 and ~x=0.90;
//                    -- starting near x<0.15 traps at left edge, x>0.65 traps at right local min
//
// x is in [0,1]; y (canvas) is mapped so f(0)..f(1) fill most of the height.

const W = 220, H = 180;
const PAD_X = 20, PAD_TOP = 16, PAD_BOT = 28;
const PLOT_W = W - 2*PAD_X;
const PLOT_H = H - PAD_TOP - PAD_BOT;
const STEPS = 600;
const LR_CVX = 0.04;
const LR_NC  = 0.012;
const EPS = 1e-7;

function fConvex(x)    { return (x - 0.5) ** 2; }
function dfConvex(x)   { return 2 * (x - 0.5); }

function fNonConvex(x) { return 0.18 * Math.sin(12 * x) + 0.6 * (x - 0.5) ** 2; }
function dfNonConvex(x){ return 0.18 * 12 * Math.cos(12 * x) + 2 * 0.6 * (x - 0.5); }

// Sample f over [0,1] to find range for scaling
function getRange(f) {
  let mn = Infinity, mx = -Infinity;
  for (let i = 0; i <= 200; i++) {
    const v = f(i / 200);
    if (v < mn) mn = v;
    if (v > mx) mx = v;
  }
  return { mn, mx };
}

const rConvex   = getRange(fConvex);
const rNonConvex = getRange(fNonConvex);

// Map (x in [0,1], fval) -> canvas pixel
function toCanvas(x, fval, range) {
  const px = PAD_X + x * PLOT_W;
  const norm = (fval - range.mn) / (range.mx - range.mn + 1e-10);
  const py = PAD_TOP + PLOT_H * (1 - norm) * 0.88 + PLOT_H * 0.04;
  return { px, py };
}

function drawCurve(ctx, f, range, color) {
  ctx.beginPath();
  for (let i = 0; i <= 300; i++) {
    const x = i / 300;
    const { px, py } = toCanvas(x, f(x), range);
    i === 0 ? ctx.moveTo(px, py) : ctx.lineTo(px, py);
  }
  ctx.strokeStyle = color;
  ctx.lineWidth = 2.5;
  ctx.stroke();
}

function drawAxes(ctx) {
  ctx.strokeStyle = '#b0bec5';
  ctx.lineWidth = 1;
  ctx.beginPath();
  ctx.moveTo(PAD_X, H - PAD_BOT);
  ctx.lineTo(W - PAD_X, H - PAD_BOT);
  ctx.stroke();
}

function drawBall(ctx, px, py, color) {
  ctx.beginPath();
  ctx.arc(px, py, 7, 0, Math.PI * 2);
  ctx.fillStyle = color;
  ctx.fill();
  ctx.strokeStyle = '#fff';
  ctx.lineWidth = 1.5;
  ctx.stroke();
}

function drawMinMarker(ctx, x, f, range) {
  const { px, py } = toCanvas(x, f(x), range);
  ctx.beginPath();
  ctx.moveTo(px, py + 10);
  ctx.lineTo(px - 6, py + 18);
  ctx.lineTo(px + 6, py + 18);
  ctx.closePath();
  ctx.fillStyle = '#0a7d33';
  ctx.fill();
}

// Global minimum of non-convex: find by scanning
function globalMin(f) {
  let bx = 0, bv = f(0);
  for (let i = 1; i <= 2000; i++) {
    const x = i / 2000, v = f(x);
    if (v < bv) { bv = v; bx = x; }
  }
  return bx;
}
const GLOBAL_NC = globalMin(fNonConvex);
const GLOBAL_CVX = 0.5;

// State per canvas
const state = {
  cvx:   { animId: null, trail: [], x: null, done: false },
  noncvx: { animId: null, trail: [], x: null, done: false }
};

function clearCanvas(ctx, id) {
  const s = state[id];
  if (s.animId) { cancelAnimationFrame(s.animId); s.animId = null; }
  s.trail = []; s.x = null; s.done = false;
  ctx.clearRect(0, 0, W, H);
}

function baseRender(ctx, f, range, id) {
  ctx.clearRect(0, 0, W, H);
  drawAxes(ctx);
  const color = id === 'cvx' ? '#1d6fa0' : '#c0392b';
  drawCurve(ctx, f, range, color);
}

function renderState(ctx, f, df, range, id, lr, globalX, statusEl, isConvex) {
  const s = state[id];
  baseRender(ctx, f, range, id);

  // Draw trail
  if (s.trail.length > 1) {
    ctx.beginPath();
    s.trail.forEach(([tx, ty], i) => i === 0 ? ctx.moveTo(tx, ty) : ctx.lineTo(tx, ty));
    ctx.strokeStyle = 'rgba(255,165,0,0.5)';
    ctx.lineWidth = 1.5;
    ctx.stroke();
  }

  if (s.x !== null) {
    const { px, py } = toCanvas(s.x, f(s.x), range);
    drawBall(ctx, px, py, s.done ? '#0a7d33' : '#e67e22');
  }

  if (s.done) {
    // Show global min marker
    drawMinMarker(ctx, globalX, f, range);
    const atGlobal = Math.abs(s.x - globalX) < 0.04;
    statusEl.textContent = atGlobal
      ? '✓ Reached the global minimum!'
      : '✗ Trapped in a local minimum';
    statusEl.className = 'panel-status ' + (atGlobal ? 'ok' : 'trapped');
  }
}

function runDescent(canvasId, x0, f, df, range, lr, globalX, statusEl, isConvex) {
  const s = state[canvasId];
  const ctx = document.getElementById(canvasId).getContext('2d');
  clearCanvas(ctx, canvasId);
  statusEl.textContent = 'Descending…';
  statusEl.className = 'panel-status';

  s.x = x0;
  s.trail = [];
  s.done = false;

  let step = 0;
  // Precompute full path
  const path = [x0];
  let cx = x0;
  for (let i = 0; i < STEPS; i++) {
    const g = df(cx);
    const nx = Math.max(0, Math.min(1, cx - lr * g));
    path.push(nx);
    if (Math.abs(nx - cx) < EPS) break;
    cx = nx;
  }

  const finalX = path[path.length - 1];

  function animate() {
    if (step >= path.length) {
      s.x = finalX;
      s.done = true;
      renderState(ctx, f, df, range, canvasId, lr, globalX, statusEl, isConvex);
      return;
    }
    // Advance a few steps per frame for smooth animation
    const batch = Math.max(1, Math.floor(path.length / 80));
    for (let b = 0; b < batch && step < path.length; b++, step++) {
      s.x = path[step];
      const { px, py } = toCanvas(s.x, f(s.x), range);
      s.trail.push([px, py]);
    }
    renderState(ctx, f, df, range, canvasId, lr, globalX, statusEl, isConvex);
    s.animId = requestAnimationFrame(animate);
  }
  s.animId = requestAnimationFrame(animate);
}

// Initial draw
const ctxC = document.getElementById('cvx').getContext('2d');
const ctxN = document.getElementById('noncvx').getContext('2d');
baseRender(ctxC, fConvex, rConvex, 'cvx');
baseRender(ctxN, fNonConvex, rNonConvex, 'noncvx');

function xFromClick(e, canvas) {
  const rect = canvas.getBoundingClientRect();
  const rawX = e.clientX - rect.left;
  return Math.max(0, Math.min(1, (rawX - PAD_X) / PLOT_W));
}

document.getElementById('cvx').addEventListener('click', function(e) {
  const x0 = xFromClick(e, this);
  runDescent('cvx', x0, fConvex, dfConvex, rConvex, LR_CVX, GLOBAL_CVX,
             document.getElementById('cvx-status'), true);
});

document.getElementById('noncvx').addEventListener('click', function(e) {
  const x0 = xFromClick(e, this);
  runDescent('noncvx', x0, fNonConvex, dfNonConvex, rNonConvex, LR_NC, GLOBAL_NC,
             document.getElementById('noncvx-status'), false);
});

document.getElementById('reset').addEventListener('click', function() {
  clearCanvas(ctxC, 'cvx');
  clearCanvas(ctxN, 'noncvx');
  baseRender(ctxC, fConvex, rConvex, 'cvx');
  baseRender(ctxN, fNonConvex, rNonConvex, 'noncvx');
  document.getElementById('cvx-status').textContent = '';
  document.getElementById('cvx-status').className = 'panel-status';
  document.getElementById('noncvx-status').textContent = '';
  document.getElementById('noncvx-status').className = 'panel-status';
});

// Console log for node verification
console.log('Demo loaded. Convex global min: x=0.5, f=0.00');
console.log(fmt('Non-convex global min: x=%GLOBAL_NC%, f=%fNonConvex%', { GLOBAL_NC: GLOBAL_NC.toFixed(4), fNonConvex: fNonConvex(GLOBAL_NC).toFixed(4) }));
// Verify convexity: for any two points a,b and t in [0,1], f(ta+(1-t)b) <= t*f(a)+(1-t)*f(b)
(function verifyConvex() {
  const tests = [[0.1,0.9],[0.2,0.7],[0.0,1.0],[0.3,0.8]];
  const t = 0.5;
  let ok = true;
  tests.forEach(([a,b]) => {
    const lhs = fConvex(t*a + (1-t)*b);
    const rhs = t*fConvex(a) + (1-t)*fConvex(b);
    if (lhs > rhs + 1e-10) { ok = false; console.error('Convexity violated!', a, b); }
  });
  console.log(fmt('Convexity check (Jensen): %v%', { v: ok ? 'PASS' : 'FAIL' }));
})();
Result
Console

Try clicking at several different starting points on each surface. Notice that on the convex bowl (left) the ball always ends at the single global minimum regardless of where it starts. On the bumpy surface (right) the outcome depends entirely on the starting point — the same algorithm, the same cost, but a completely different guarantee.

The Real Complexity

Why does a single geometric property change everything algorithmically?

  • Checking a point is easy: given any candidate solution, computing whether it satisfies the constraints and what the cost is takes linear time — no harder than Minesweeper's check-a-board step.
  • Convex problems are solvable in polynomial time. The key insight, made precise by Khachian (1979, ellipsoid method) and then dramatically improved by Karmarkar (1984, interior-point methods), is that any local minimum of a convex function is a global minimum. Gradient descent can therefore stop the moment it can't find a downhill direction — it has the global answer. For linear programs this was known since the simplex method (Dantzig, 1947), but polynomial-time guarantees came later.
  • Non-convex optimization is NP-hard in general. Even deciding whether a point is a local minimum — let alone a global one — can require exploring exponentially many candidates when the landscape has many bumps. Many integer programming problems are non-convex for exactly this reason.
  • The boundary is surprisingly sharp. Adding a single non-convex constraint to a convex program can jump from polynomial to NP-hard. Conversely, finding a convex relaxation of a hard problem — a convex surrogate that lower-bounds the original — is one of the most powerful tools in approximation algorithms.

Status: solved (for convex problems). Polynomial-time algorithms exist and are used daily. The open question is how to handle the non-convex problems that matter most in practice — deep learning, combinatorial optimization, and protein folding all live in non-convex territory, and finding global optima there has no known efficient solution in general.

Where It Matters

The convexity guarantee is not an abstract luxury — it is the reason many real algorithms are trustworthy:

  • Machine learning: support-vector machines (SVMs) find the maximum-margin separator by solving a convex quadratic program. Logistic regression, LASSO, and ridge regression are all convex, so their training is reliable. Deep learning deliberately uses convex loss surfaces at each layer when possible.
  • Portfolio optimization: Markowitz mean-variance optimization (1952) is a convex quadratic program. Given expected returns and a covariance matrix, it finds the portfolio with minimum risk for a target return — and the efficient frontier is the solution set of a family of such convex programs.
  • Signal processing and compressed sensing: recovering a sparse signal from few measurements reduces to minimizing a convex L1 norm subject to linear constraints — solvable in polynomial time even when the naive search would be exponential.
  • Control and robotics: model-predictive control (MPC) solves a convex program at every time step to compute optimal actuator inputs in real time.
  • Network flows: the cheapest-flow problem on a network is convex, which is why logistics companies can optimize continent-sized supply chains. See also min-cost flow.

Understanding convexity lets you see why these algorithms can be trusted — and recognize when a problem has left the safe convex world and entered the territory where only approximations or heuristics remain.

Conclusion

Convexity is one of mathematics' most powerful free lunches. Ask an algorithm to minimize a cost on a bumpy landscape and it can wander forever; put it on a bowl and it will always find the bottom — provably, efficiently, every time.

The practical world is messier: deep neural networks, combinatorial scheduling, and protein folding live on non-convex terrain, and no polynomial-time global-optimization algorithm is known for them. The art of modern optimization is finding convex surrogates, relaxations, and reformulations that let you borrow the bowl's guarantee even when the original problem is bumpy.

So the next time an algorithm confidently converges to a solution, ask: is that confidence earned, or just luck? If the problem is convex, the answer is earned — and centuries of mathematical analysis back it up. If it is not, you may be looking at a local minimum and calling it the truth.

Share this article

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

Comments

Loading comments...

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