Introduction

Most interesting optimization problems are nonconvex: the landscape of the objective function has multiple valleys, ridges, and saddle points. Standard gradient descent gets stuck in the first valley it finds, which might be far from the best one.

Difference of Convex (DC) programming offers a structured way out. The key insight is that almost every smooth function you encounter in practice can be written as

f(x)=g(x)−h(x)f(x) = g(x) - h(x)

where both gg and hh are convex — each a bowl with no local traps. The nonconvexity of ff comes entirely from their difference.

Once you have this split, the DC Algorithm (DCA), developed by Pham Dinh Tao and Le Thi Hoai An in the 1980s–90s, gives a recipe: at each step, linearize hh around the current point and minimize the resulting convex subproblem. Because linearizing a convex function gives a global lower bound, you are always solving something easier than the original — and the iterates are guaranteed to decrease ff.

DCA does not promise a global minimum (the problem remains non-convex optimization), but it finds stationary points efficiently, often reaching very good solutions in practice.

Try It

The demo below runs DCA on a wiggly one-dimensional objective. The function is written as f(x)=g(x)−h(x)f(x) = g(x) - h(x), with both gg and hh convex. At each iteration DCA replaces hh with its tangent line at the current point and minimizes the resulting convex problem exactly.

<p class="hint">The wiggly curve is <b>f = g − h</b> (both g and h are convex bowls). DCA linearizes h at the current point and solves a convex subproblem — guaranteed to descend. Try different start positions to see how the path changes.</p>
<canvas id="chart" width="560" height="220"></canvas>
<div class="controls">
  <label>Start x = <input id="startSlider" type="range" min="-4" max="4" step="0.1" value="3"></label>
  <span id="startVal" class="val-badge">3.0</span>
</div>
<div class="status" id="status">Choose a start point and press Run DCA or Step.</div>
<div class="btns">
  <button id="btnRun" type="button">Run DCA</button>
  <button id="btnStep" type="button">Step</button>
  <button id="btnReset" type="button" class="ghost">Reset</button>
</div>

/* Canvas chart + slider controls + status + action buttons. */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
canvas { display: block; width: 100%; max-width: 560px; border-radius: 8px;
         border: 1px solid #cdd9e3; background: #f8fafc; }
.controls { display: flex; align-items: center; gap: .5rem; margin: .5rem 0; font-size: .9rem; }
.controls input[type=range] { width: 160px; }
.val-badge { font-weight: 600; color: #1d3557; min-width: 3ch; }
.status { font-size: 1rem; font-weight: 600; margin: .4rem 0; min-height: 1.4em; }
.status.running { color: #1d6fa5; }
.status.done { color: #0a7d33; }
.status.stuck { color: #c92f3c; }
.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; }
button:disabled { opacity: .45; cursor: default; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
/* DC programming: write f(x) = g(x) - h(x) with g,h convex. */
/* DCA: at each step, linearize h around current point xk, */
/* then minimize the resulting convex problem g(x) - [h(xk) + dh(xk)*(x-xk)]. */

const W = 560, H = 220;
const XMIN = -4.5, XMAX = 4.5;
/* f(x) = g(x) - h(x). g is a simple quadratic; h adds the oscillations. */
function g(x) { return 0.8 * x * x + 0.5; }
function h(x) { return 0.8 * x * x - 0.5 * Math.cos(2.5 * x) - 0.5 * Math.cos(1.5 * x); }
function f(x) { return g(x) - h(x); }

/* Gradient of h (needed to form the tangent at each DCA step). */
function dh(x) { return 1.6 * x + 1.25 * Math.sin(2.5 * x) + 0.75 * Math.sin(1.5 * x); }

/* One DCA step: return the minimizer of g(x) - linear-h(x). */
function dcaStep(xk) {
  /* Replace h with its first-order Taylor expansion at xk: */
  /* h(x) ~ h(xk) + dh(xk)*(x - xk)  =>  g(x) - (h(xk) + dh(xk)*(x-xk)) convex in x */
  /* The convex subproblem has a closed-form minimizer here: */
  /* minimize g(x) - dh(xk)*x  =>  derivative = dg(x) - dh(xk) = 1.6x - dh(xk) = 0 */
  return dh(xk) / 1.6;
}

const canvas = document.getElementById('chart');
const ctx = canvas.getContext('2d');
let x0 = 3.0, iterates = [], running = false, stepTimer = null;

function toCanvas(x, y, yMin, yMax) {
  return [
    (x - XMIN) / (XMAX - XMIN) * W,
    H - (y - yMin) / (yMax - yMin) * H * 0.85 - H * 0.05
  ];
}

/* Draw f(x) curve, the DCA tangent approximation, and the iterate path. */
function drawChart() {
  ctx.clearRect(0, 0, W, H);
  const N = 300;
  /* Sample f over [XMIN, XMAX] to get y-axis bounds. */
  const ys = Array.from({ length: N + 1 }, (_, i) => {
    const x = XMIN + (XMAX - XMIN) * i / N;
    return f(x);
  });
  const yMin = Math.min(...ys) - 0.3, yMax = Math.max(...ys) + 0.3;

  /* Draw the main f(x) curve in dark blue. */
  ctx.beginPath();
  ctx.strokeStyle = '#1d3557';
  ctx.lineWidth = 2;
  for (let i = 0; i <= N; i++) {
    const x = XMIN + (XMAX - XMIN) * i / N;
    const [px, py] = toCanvas(x, f(x), yMin, yMax);
    i === 0 ? ctx.moveTo(px, py) : ctx.lineTo(px, py);
  }
  ctx.stroke();

  /* Draw the convex tangent approximation used at the last step (orange dashed). */
  if (iterates.length >= 2) {
    const xk = iterates[iterates.length - 2];
    const slope = 1.6 - dh(xk) / 1;
    ctx.beginPath();
    ctx.strokeStyle = '#e07a3b';
    ctx.lineWidth = 1.3;
    ctx.setLineDash([5, 3]);
    for (let i = 0; i <= N; i++) {
      const x = XMIN + (XMAX - XMIN) * i / N;
      const ytangent = g(x) - (h(xk) + dh(xk) * (x - xk));
      const [px, py] = toCanvas(x, ytangent, yMin, yMax);
      i === 0 ? ctx.moveTo(px, py) : ctx.lineTo(px, py);
    }
    ctx.stroke();
    ctx.setLineDash([]);
  }

  /* Draw the DCA iterate path as colored dots. */
  for (let i = 0; i < iterates.length; i++) {
    const xi = iterates[i];
    const [px, py] = toCanvas(xi, f(xi), yMin, yMax);
    ctx.beginPath();
    ctx.arc(px, py, i === iterates.length - 1 ? 6 : 4, 0, 2 * Math.PI);
    ctx.fillStyle = i === 0 ? '#2a9d8f' : (i === iterates.length - 1 ? '#e63946' : '#a8c5da');
    ctx.fill();
    ctx.strokeStyle = '#fff';
    ctx.lineWidth = 1.2;
    ctx.stroke();
  }

  /* Highlight the start point when no iterates exist yet. */
  const [sx, sy] = toCanvas(x0, f(x0), yMin, yMax);
  if (iterates.length === 0) {
    ctx.beginPath();
    ctx.arc(sx, sy, 7, 0, 2 * Math.PI);
    ctx.fillStyle = '#2a9d8f';
    ctx.fill();
    ctx.strokeStyle = '#fff';
    ctx.lineWidth = 1.5;
    ctx.stroke();
  }
}

function setStatus(txt, cls) {
  const el = document.getElementById('status');
  el.textContent = txt;
  el.className = 'status ' + cls;
}

/* Reset state: clear iterates, re-enable buttons, redraw. */
function reset() {
  clearTimeout(stepTimer);
  running = false;
  iterates = [];
  document.getElementById('btnRun').disabled = false;
  document.getElementById('btnStep').disabled = false;
  setStatus('Choose a start point and press Run DCA or Step.', '');
  drawChart();
}

/* Execute one DCA step and update the chart and status. */
function doStep() {
  if (iterates.length === 0) iterates.push(x0);
  const xk = iterates[iterates.length - 1];
  const xnext = dcaStep(xk);
  const converged = Math.abs(xnext - xk) < 1e-5;
  iterates.push(xnext);
  drawChart();
  const iter = iterates.length - 1;
  if (converged) {
    setStatus(i18nFmt('Converged in %iter% steps: x = %x%, f(x) = %fx%', { iter: iter, x: xnext.toFixed(4), fx: f(xnext).toFixed(4) }), 'done');
    running = false;
    return true;
  }
  setStatus(i18nFmt('Iteration %iter%: x = %x%, f(x) = %fx%', { iter: iter, x: xnext.toFixed(4), fx: f(xnext).toFixed(4) }), 'running');
  return false;
}

/* Run DCA until convergence or 60 iterations, with animation. */
function runAll() {
  running = true;
  document.getElementById('btnRun').disabled = true;
  document.getElementById('btnStep').disabled = true;
  function tick() {
    if (!running) return;
    const done = doStep();
    if (!done && iterates.length < 60) stepTimer = setTimeout(tick, 220);
    else {
      running = false;
      document.getElementById('btnRun').disabled = false;
      document.getElementById('btnStep').disabled = false;
    }
  }
  tick();
}

const slider = document.getElementById('startSlider');
const valBadge = document.getElementById('startVal');
slider.addEventListener('input', () => {
  x0 = parseFloat(slider.value);
  valBadge.textContent = x0.toFixed(1);
  reset();
});
document.getElementById('btnRun').addEventListener('click', () => { reset(); setTimeout(runAll, 50); });
document.getElementById('btnStep').addEventListener('click', () => { if (!running) doStep(); });
document.getElementById('btnReset').addEventListener('click', reset);

drawChart();
Result
Console

Drag the start marker or click Reset to try a new starting point. Notice that the algorithm always descends — but depending on where you start, it can converge to different local minima. That is the fundamental limitation DC programming shares with all local nonconvex methods.

The Real Complexity

DC programming is powerful precisely because it is honest about what it can and cannot do.

  • What DCA guarantees: every iterate strictly decreases ff (or stops), and the sequence converges to a critical point of ff — a point where ∇g=∇h\nabla g = \nabla h. This is the best we can hope for from a local method.
  • What it does not guarantee: the critical point may be a local minimum, a saddle point, or simply a poor solution. Nonconvex optimization is NP-hard in general, and DCA is no exception.
  • The decomposition matters: the same function ff can be split into g−hg - h in many ways. A tighter decomposition — one where hh is "as convex as possible" — usually means the linearization is more accurate, and the algorithm converges faster and to better points.
  • Each subproblem is convex: this is the key practical win. Modern convex solvers are fast and reliable, so each DCA step is cheap even in high dimensions.

In practice, DCA is run from multiple starting points (multi-start) to reduce the risk of a poor local minimum. Combined with warm starts and clever decompositions, it solves large instances of problems that naive gradient descent handles poorly.

Where It Matters

The convex-minus-convex structure appears naturally across many fields:

  • Sparse recovery and compressed sensing: the ℓ0\ell_0 "count of non-zeros" penalty minus a convex term is a classical DC decomposition. DCA recovers sparse signals far better than pure ℓ1\ell_1 relaxation in many benchmarks.
  • Neural network training: loss landscapes in deep learning are nonconvex, but many regularization terms (weight decay, dropout surrogates) have explicit DC structure that DCA can exploit.
  • Portfolio optimization: mean-variance objectives with cardinality constraints can be cast as DC programs, giving principled heuristics for selecting a small basket of assets.
  • Clustering and combinatorial problems: kk-means and certain graph partitioning objectives have DC formulations; DCA-based methods often outperform spectral or greedy alternatives.
  • Robotics and control: trajectory optimization problems with obstacle-avoidance constraints decompose naturally into DC form, where hh captures the nonconvex geometry.

Whenever you have a nonconvex objective and you can identify its "convex core" and "convex remainder," DC programming gives you a systematic, convergence-guaranteed descent strategy.

Conclusion

Difference of Convex programming rests on a simple observation: almost any nonconvex function can be split into two convex pieces, and that split can be exploited algorithmically. The DCA turns the split into a loop — linearize, solve, repeat — that always descends and always terminates.

The price is honesty: DCA finds a stationary point, not necessarily the global minimum. But in the vast landscape of non-convex optimization, a principled, convergence-guaranteed descent strategy that reduces each step to a tractable convex problem is already remarkable. For many real applications, that is exactly enough.

Share this article

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

Comments

Loading comments...

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