Difference of Convex Programming

436 concepts312 papers4 proposals

In machine learning and mathematical optimization, we frequently face a trade-off between mathematical convenience and realistic modeling. Convex optimization is highly desirable because any local minimum is guaranteed to be a global minimum, allowing algorithms to converge reliably and efficiently. However, many real-world phenomena—ranging from sparse regularizers and non-smooth losses to complex decision-making landscapes—are inherently non-convex.

Difference of Convex (DC) programming bridges this divide. The core intuition is that a vast majority of non-convex, non-smooth continuous functions can be decomposed into the difference of two convex functions:

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

where both $g(x)$ and $h(x)$ are convex. While the objective function $f(x)$ itself can be wildly non-convex and exhibit multiple local minima, its individual components inherit the well-behaved geometry of convex functions. By exploiting this structural decomposition, we can transform an intractable non-convex optimization problem into a sequence of easily solvable convex sub-problems.


The Geometry of DC Linearization

To understand why DC programming works, we must look at how it approximates a non-convex landscape. Suppose we want to minimize $f(x) = g(x) - h(x)$. The difficulty arises entirely from subtracting the convex function $h(x)$, which introduces non-convexity (or concavity, via $-h(x)$) into the objective.

A fundamental property of any convex function $h(x)$ is that it is always globally majorized by its tangent lines (or subgradients, if the function is non-smooth). Geometrically, if you draw a tangent line at any point $x_k$ on a convex curve, the curve lies entirely above or on that line:

$$h(x) \ge h(x_k) + \langle y_k, x - x_k \rangle$$

where $y_k \in \partial h(x_k)$ is a subgradient of $h$ at $x_k$.

If we multiply this inequality by $-1$, the direction flips. The concave component $-h(x)$ is globally upper-bounded by its linearized approximation:

$$-h(x) \le -h(x_k) - \langle y_k, x - x_k \rangle$$

By substituting this linear upper bound back into our original objective function, we construct a surrogate function $\tilde{f}(x)$ at the current estimate $x_k$:

$$\tilde{f}(x) = g(x) - h(x_k) - \langle y_k, x - x_k \rangle$$

Because $g(x)$ remains untouched and the rest of the terms are purely linear, $\tilde{f}(x)$ is strictly convex. Crucially, because $\tilde{f}(x) \ge f(x)$ globally and $\tilde{f}(x_k) = f(x_k)$, minimizing this convex surrogate guarantees a step that decreases (or maintains) the original non-convex objective value. This optimization strategy is a powerful instance of the Majorization-Minimization framework.


The Difference-of-Convex Algorithm

The algorithmic realization of this idea is known as the Difference-of-Convex Algorithm (DCA), or the Concave-Convex Procedure (CCCP). The algorithm proceeds iteratively through two main steps:

  1. Linearization: Find a subgradient of the energy-subtracting component: $y_k \in \partial h(x_k)$.
  2. Convex Optimization: Solve the resulting convex sub-problem to find the next iterate: $$x_{k+1} = \arg\min_x \{ g(x) - \langle y_k, x \rangle \}$$

As noted by Alain Rakotomamonjy et al. in DC Proximal Newton for Nonconvex Optimization Problems, linearizing only the concave components creates a principled descent toward stationary points. This partial linearization preserves the local convex structure of $g(x)$, providing a more stable and effective guide for optimization than general-purpose non-convex solvers or standard gradient descent, which linearize the entire objective function indiscriminately.


Versatility Across Domains

The power of DC programming lies in its universality. A remarkable variety of complex machine learning problems can be naturally cast into a DC framework by identifying their hidden convex components.

1. Reinforcement Learning and Non-Smooth Operators

In reinforcement learning, objectives often involve non-smooth operators like maximums over actions. Bilal Piot et al. demonstrate in Difference of Convex Functions Programming for Reinforcement Learning that the absolute value operations inherent in minimizing the Optimal Bellman Residual preserve the DC property. This allows complex, non-differentiable reinforcement learning objectives to be broken down into a sequence of simpler, solvable convex sub-problems.

2. Learning with Indefinite Kernels

Standard kernel methods, such as Support Vector Machines (SVMs), rely on positive semi-definite matrices to guarantee convexity. However, real-world similarity measures often yield indefinite kernels. To handle this, Fanghui Liu et al. in Indefinite Kernel Logistic Regression With Concave-Inexact-Convex Procedure and Haiming Xu et al. in Solving Indefinite Kernel Support Vector Machine with Difference of Convex Functions Programming leverage the eigenspectrum of the indefinite matrix. By splitting the matrix into its positive and negative eigenvalues, the authors decompose the non-convex learning problem into a difference of two positive definite (and thus convex) kernel functions.

3. Combinatorial and Submodular Optimization

The core philosophy of DC programming extends beyond continuous spaces into discrete domains. When optimizing complex combinatorial objectives that fail to satisfy strict submodularity, researchers look for a discrete analog. Kevin K Yang et al. in Batched Stochastic Bayesian Optimization via Combinatorial Constraints Design show that non-submodular functions can be optimized by decomposing them into a Difference of Submodular functions (DS).

Further establishing this universality, George Orfanides et al. in Discrete and Continuous Difference of Submodular Minimization prove that virtually any function defined on a finite discrete domain or any smooth function on a continuous domain can be represented as a difference of two submodular functions, providing a universal framework for non-convex discrete optimization.

4. Distributed Multi-Agent Systems

DC programming is also highly effective in decentralized settings. In distributed networks, agents must optimize local objectives while maintaining consensus. Ying Sun et al. show in Distributed Nonconvex Optimization for Sparse Representation that by utilizing a difference-of-convex decomposition, agents can linearize only the concave portions of their local penalties. This preserves the structural benefits of the convex components across the network, yielding more stable optimization updates and faster convergence than methods that linearize the entire objective.

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 2, frozen text):

@misc{lacuna_difference_of_convex_programming_1568db60_v2,
  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/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake