Difference of Convex

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)$$

where both $g$ and $h$ are convex — each a bowl with no local traps. The nonconvexity of $f$ 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 $h$ 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 $f$.

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.

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

<p class="hint">{{hint_para}}</p>
<canvas id="chart" width="560" height="220"></canvas>
<div class="controls">
  <label>{{label_start}} <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">{{status_idle}}</div>
<div class="btns">
  <button id="btnRun" type="button">{{btn_run}}</button>
  <button id="btnStep" type="button">{{btn_step}}</button>
  <button id="btnReset" type="button" class="ghost">{{btn_reset}}</button>
</div>

/* {{c_layout}} */
* { 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; }

// Code not found

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.

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

• What DCA guarantees: every iterate strictly decreases $f$ (or stops), and the sequence converges to a critical point of $f$ — a point where $\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 $f$ can be split into $g - h$ in many ways. A tighter decomposition — one where $h$ 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.

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

• Sparse recovery and compressed sensing: the $\ell_0$ "count of non-zeros" penalty minus a convex term is a classical DC decomposition. DCA recovers sparse signals far better than pure $\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: $k$-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 $h$ 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.

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.