Optimization via Difference of Convex Decompositions

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 2451 papers544 conceptsfrozen 2026-10-04

In the landscape of mathematical optimization, convexity is the "gold standard." If a problem is convex, we can find its global minimum efficiently. However, the most interesting problems in machine learning—from training deep neural networks to recovering sparse signals—are stubbornly non-convex.

Difference of Convex (DC) programming offers a bridge between these two worlds. It rests on a powerful observation: many complex, non-convex functions can be decomposed into the difference of two convex functions. By exploiting this structure, researchers can apply the rigors of convex analysis to the "messy" reality of non-convex landscapes.

The Geometry of DC Decompositions

At its core, a DC function $f(x)$ is expressed as: $$f(x) = g(x) - h(x)$$ where both $g$ and $h$ are convex. While the resulting landscape $f$ can be highly non-convex, non-smooth, and full of local minima, its "DNA" is entirely convex.

This decomposition is surprisingly universal. As noted by Ali Siahkamari and colleagues in Piecewise Linear Regression via a Difference of Convex Functions, DC functions can approximate any continuous function with arbitrary precision. This makes them a "universal language" for optimization.

The intuition behind why this works is majorization. In a standard convex problem, the function curves "upward" everywhere. In a DC problem, $g(x)$ provides the upward curvature, while $-h(x)$ (a concave function) provides the downward curvature. The difficulty of the optimization depends on how these two forces compete.

The Difference of Convex Algorithm

The primary tool for solving these problems is the Difference of Convex Algorithm (DCA), often associated with the foundational work of Le Thi Hoai An.

The DCA works through a simple, iterative "linearize and solve" strategy:

  1. Linearize the concave part: At a current point $x_k$, we take the gradient (or subgradient) of the second function $h(x)$. Because $h$ is convex, its linear approximation is always a global under-estimator.
  2. Subtract the approximation: When we subtract this linear under-estimator from the first convex function $g(x)$, we create a new, purely convex surrogate function.
  3. Minimize the surrogate: We solve this convex sub-problem to find the next point $x_{k+1}$.

Because the linear approximation of $h$ stays below the actual function, the surrogate function $g(x) - \langle \nabla h(x_k), x - x_k \rangle$ stays above the original function $f(x)$. This creates a "Majorization-Minimization" (MM) effect: each step is guaranteed to either decrease the objective value or stay at a stationary point. Suvrit Sra and Melanie Weber demonstrate in On a class of geodesically convex optimization problems solved via Euclidean MM methods that this approach can even solve complex problems in matrix analysis without needing expensive Riemannian operations.

Taming Non-Convex Penalties and Kernels

One of the most impactful applications of DC programming is in sparse estimation. While the $\ell_1$ norm is the standard convex tool for sparsity, it often introduces bias. Non-convex penalties like the "capped-$\ell_1$" or "SCAD" are more accurate but harder to optimize.

Shanshan Cao and Jong-Shi Pang show in A Unifying Framework of High-Dimensional Sparse Estimation with Difference-of-Convex (DC) Regularizations that these penalties can be decomposed into an $\ell_1$ norm minus a convex correction term. This allows the DCA to treat non-convex sparse recovery as a sequence of weighted $\ell_1$ problems, combining the speed of convex solvers with the accuracy of non-convex models.

Similarly, in kernel methods, we often encounter "indefinite" kernels that don't satisfy standard positive-definite requirements. Fanghui Liu proposes in Indefinite Kernel Logistic Regression With Concave-Inexact-Convex Procedure that these kernels can be split into the difference of two positive semi-definite matrices. This transforms a mathematically "illegal" kernel problem into a standard DC program.

Implicit DC Structures in Deep Learning

Perhaps the most surprising recent development is the realization that DC optimization might already be happening inside our most successful models.

In Understand the Effectiveness of Shortcuts through the Lens of DCA, researchers argue that the "shortcut" connections in ResNets are not just for better gradient flow. Instead, they show that the ResNet architecture implicitly implements the update rules of the Difference-of-Convex Algorithm. By structuring the network this way, the training process effectively linearizes the "concave" parts of the loss landscape, explaining why these networks are so much easier to optimize than their "vanilla" counterparts.

Challenges in Decomposition

The primary hurdle in this field is not solving the DC program, but finding the decomposition itself. As Teodor Rotaru and François Glineur point out in Improved convergence rates for the Difference-of-Convex algorithm, there is no single "correct" way to split a function into $g - h$. Different splits lead to different convergence speeds and different local optima.

Despite this, the direction is clear: by viewing non-convexity as a structured interaction between convex components, researchers are moving away from "black-box" heuristics toward a more principled, geometric understanding of complex optimization.

Papers in this version

Showing 60 of 451 papers.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 331 papers
  2. Version 1 · 2026-10-04 · 451 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_difference_of_convex_programming_1568db60,
  title = {difference of convex programming},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/difference-of-convex-programming/rdr_1568db60b9d342c0a1264e55737eef09},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_optimization_via_difference_of_convex_de_1568db60_v1,
  title = {Optimization via Difference of Convex Decompositions},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/optimization-via-difference-of-convex-decompositions/rdr_1568db60b9d342c0a1264e55737eef09/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}