Convex optimization is appealing because a local supporting plane contains global information. But many interesting objectives combine competing effects: a fidelity term and a sparsity incentive, attraction and repulsion, or positive and negative contributions to a transport energy. Subtracting two convex functions is already enough to leave the convex world.
The resulting class is called difference-of-convex, or DC, optimization. It retains enough structure to admit a beautiful duality: conjugate both convex functions, reverse their order, and minimize again. This is Toland duality [1], [2]. Following the viewpoint of Guillaume Carlier [3], I want to explain both its elementary mechanism and a particularly pleasant possibility: a genuinely nonconvex objective can have a fully convex dual.
The same construction also gives an algorithm. The key is to introduce a slope as an additional variable. Minimizing jointly gives the duality theorem; minimizing alternately gives the DC algorithm. But when the dual is convex, there is a third option: solve that convex problem directly, then recover a global solution of the original problem. This is the real prize—not merely another way to write the same stationary-point equations.
Two convex functions make one nonconvex problem
Let \(F,G:\mathbb R^d\to\mathbb R\) be finite convex functions, and consider
\[ \inf_{x\in\mathbb R^d}\Phi(x), \qquad \Phi(x)=F(x)-G(x). \]The assumption that both functions are finite keeps the domain bookkeeping simple. They are then continuous. Their conjugates can still take the value \(+\infty\), which we will handle explicitly.
This class is large. For example, if a twice differentiable function \(f\) satisfies \(\nabla^2f\succeq-\rho I\), then
\[ f(x)=\left(f(x)+\frac{\rho}{2}\|x\|^2\right) -\frac{\rho}{2}\|x\|^2 \]is a DC decomposition. An indefinite quadratic form can likewise be split using the positive and negative parts of its matrix. Decompositions are not unique: adding the same convex function to \(F\) and \(G\) preserves \(\Phi\), but changes the algorithm built from the decomposition [4], [5].
The convex conjugate records the cost of a supporting slope:
\[ F^*(p)=\sup_x\{\langle p,x\rangle-F(x)\}. \]We write \(\operatorname{dom}F^*=\{p:F^*(p)<+\infty\}\). A supporting slope \(p\in\partial F(x)\) means
\[ F(z)\geq F(x)+\langle p,z-x\rangle \quad\text{for every }z. \]The two basic identities are \(F=F^{**}\), which reconstructs a convex function from its affine supports, and Fenchel's inequality \(F(x)+F^*(p)\geq\langle p,x\rangle\). Equality holds exactly when \(p\in\partial F(x)\) [6].
Toland duality in three lines
Conjugation reverses the two terms. Notice that the dual is another minimization problem, generally another DC problem.
Theorem 1 (Toland duality). For finite convex \(F,G:\mathbb R^d\to\mathbb R\),
\[ \inf_x\{F(x)-G(x)\} =\inf_{p\in\operatorname{dom}G^*} \{G^*(p)-F^*(p)\}. \]The common value may be \(-\infty\). On the right, \(G^*(p)\) is finite; if \(F^*(p)=+\infty\), the difference means \(-\infty\). Thus the formula never asks us to subtract two infinities. More general extended-real formulations are possible; Carlier discusses the necessary domain convention explicitly [3].
Proof: introduce a slope and exchange two infima
Since \(G=G^{**}\),
\[ \begin{aligned} \inf_x(F-G) &=\inf_x\inf_{p\in\operatorname{dom}G^*} \{F(x)+G^*(p)-\langle p,x\rangle\}\\ &=\inf_{p\in\operatorname{dom}G^*} \left\{G^*(p)+\inf_x(F(x)-\langle p,x\rangle)\right\}\\ &=\inf_{p\in\operatorname{dom}G^*}(G^*-F^*). \end{aligned} \]There is no minimax exchange here: an infimum over pairs can always be taken in either order. Every expression inside the joint infimum is a finite real number. The possible value \(-\infty\) appears only after taking an infimum.
It is useful to give the common two-variable function a name:
\[ B(x,p)=F(x)+G^*(p)-\langle p,x\rangle, \qquad p\in\operatorname{dom}G^*. \]Taking the infimum over \(p\) gives \(\Phi(x)\); taking it over \(x\) gives the dual objective \(\Psi(p)=G^*(p)-F^*(p)\). The function \(B\) is convex in either variable separately, but need not be jointly convex. Equality of the optimal values does not itself assert that either problem attains its infimum.
Proposition 1 (recovering minimizers). Suppose the common optimal value is finite. If \(x_\star\) is a primal minimizer, every \(p_\star\in\partial G(x_\star)\) is a dual minimizer. Conversely, if \(p_\star\) is a dual minimizer and \(x_\star\in\partial F^*(p_\star)\), then \(x_\star\) is a primal minimizer.
Proof: equality in Fenchel's inequality
In the first direction, \(p_\star\in\partial G(x_\star)\) gives \(B(x_\star,p_\star)=\Phi(x_\star)\). Theorem 1 and \(\Psi(p_\star)\leq B(x_\star,p_\star)\) force equality with the optimal value. In the second direction, \(x_\star\in\partial F^*(p_\star)\) gives \(B(x_\star,p_\star)=\Psi(p_\star)\), and \(\Phi(x_\star)\leq B(x_\star,p_\star)\) gives the same conclusion.
At such a minimizing pair, both Fenchel inequalities are equalities, so \(p_\star\in\partial F(x_\star)\cap\partial G(x_\star)\). Having a common supporting slope is necessary, but by itself does not imply global optimality.
The DC algorithm is alternating minimization
Instead of minimizing \(B\) globally, alternate its two convex subproblems:
\[ \begin{aligned} p_k&\in\partial G(x_k),\\ x_{k+1}&\in\operatorname*{argmin}_x \{F(x)-\langle p_k,x\rangle\}. \end{aligned} \]These are the standard DCA updates developed by Pham Dinh Tao and Le Thi Hoai An [4], [5]. The second line is equivalently \(x_{k+1}\in\partial F^*(p_k)\). The first update always exists because \(G\) is finite and convex; the second needs an attained minimum. Strong convexity of \(F\) guarantees a unique solution. One can enforce it by adding the same positive quadratic to both \(F\) and \(G\), without changing \(\Phi\).
In particular, if \(G\) is differentiable and \(F\) is strongly convex, the updates reduce to the simple composition
\[ x_{k+1}=\nabla F^*(\nabla G(x_k)). \]Equivalently, replace \(G\) by a supporting affine function at \(x_k\). Because it is subtracted, this produces a convex upper bound on \(\Phi\), touching it at the current iterate. Minimizing that bound is the same update. This is also the principle of the concave-convex procedure [7].
Proposition 2 (descent). Whenever the two updates are well defined, \(\Phi(x_{k+1})\leq\Phi(x_k)\). If \(F\) is \(\mu\)-strongly convex, then
\[ \Phi(x_k)-\Phi(x_{k+1}) \geq\frac{\mu}{2}\|x_{k+1}-x_k\|^2. \]Proof: follow the two block minimizations
For the quantitative bound, optimality of the second update gives \(p_k\in\partial F(x_{k+1})\). Apply strong convexity of \(F\) at \(x_{k+1}\), and convexity of \(G\) at \(x_k\), then subtract.
Descent alone guarantees neither convergence of the iterates nor global optimality. A useful weaker statement concerns DC critical points: points where \(\partial F\) and \(\partial G\) have a common slope.
Corollary 1 (critical accumulation points). If \(F\) is strongly convex and the DCA iterates stay bounded, every accumulation point is DC critical. This does not assert convergence of the whole sequence or global optimality [5].
Proof: vanishing steps and a common limiting slope
Continuity of \(\Phi\) bounds the objective values below on the bounded set of iterates. Summing Proposition 2 therefore gives \(\sum_k\|x_{k+1}-x_k\|^2<\infty\), so the steps tend to zero.
Take a subsequence \(x_{k_j}\to\bar x\). Since \(G\) is finite and convex on all of \(\mathbb R^d\), its subgradients are bounded on bounded sets. Passing to a further subsequence gives \(p_{k_j}\to\bar p\), while \(x_{k_j+1}\to\bar x\). The updates imply \(p_{k_j}\in\partial G(x_{k_j})\) and \(p_{k_j}\in\partial F(x_{k_j+1})\). Passing to the limit in the two supporting-plane inequalities gives \(\bar p\in\partial F(\bar x)\cap\partial G(\bar x)\).
What a convex dual actually buys us
Assume the common optimal value is finite and \(\Psi=G^*-F^*\) is convex on its feasible set \(D=\operatorname{dom}G^*\). We can then work with a genuine convex minimization problem instead of searching the nonconvex landscape of \(\Phi\). Every local minimizer of \(\Psi\) on \(D\) is global. First-order optimality can now certify the answer: when the objective has a differentiable extension to a neighborhood of \(D\), the condition is
\[ \langle\nabla\Psi(p_\star),q-p_\star\rangle\geq0 \qquad\text{for every }q\in D. \]Without constraints, this reduces to \(\nabla\Psi(p_\star)=0\). For a nonsmooth dual, one uses its convex subdifferential, including the feasible-set constraint. This is a condition on the whole dual objective, not merely the shared-slope condition of DCA.
This opens the door to convex optimization methods and global error certificates, provided the dual can be evaluated and its constraints or proximal subproblems can be handled. It does not automatically make the problem small, smooth, or cheap. Nor does convexity alone imply uniqueness; strict convexity would give uniqueness of an attained dual minimizer, and recovering a unique primal point requires an additional argument.
Crucially, one does not need to solve the dual exactly. A globally accurate dual solution can be turned into a globally accurate primal solution by solving one convex recovery problem. Let \(v_\star\) be the common finite optimal value, and measure recovery accuracy by the Fenchel residual
\[ r_F(x,p)=F(x)+F^*(p)-\langle p,x\rangle\geq0. \]For fixed \(p\), this is precisely the objective error in minimizing \(F(x)-\langle p,x\rangle\). It vanishes when \(x\in\partial F^*(p)\).
Proposition 3 (accuracy transfers to the primal). Let \(p\in\operatorname{dom}F^*\cap\operatorname{dom}G^*\) and \(\delta,\eta\geq0\). If
\[ \Psi(p)-v_\star\leq\delta, \qquad r_F(x,p)\leq\eta, \]then
\[ 0\leq\Phi(x)-v_\star\leq\delta+\eta. \]Proof: the two Fenchel residuals
Fenchel's inequality also gives \(r_G(x,p)=G(x)+G^*(p)-\langle p,x\rangle\geq0\). Subtracting yields
\[ \Phi(x)-\Psi(p)=r_F(x,p)-r_G(x,p)\leq r_F(x,p). \]Add \(\Psi(p)-v_\star\leq\delta\). The lower bound follows from the definition of \(v_\star\). The transfer inequality itself does not require a convex dual; convexity is what can make the certified bound \(\delta\) accessible.
For example, if a convex solver supplies a lower bound \(L\leq v_\star\), then \(\delta=\Psi(p)-L\) is a valid certificate. Beware of the terminology: because Toland duality equates two minima, a dual feasible value \(\Psi(p)\) is an upper bound on \(v_\star\), not a lower bound on every primal value. Thus \(\Phi(x)-\Psi(p)\) is not an ordinary nonnegative primal–dual gap.
A nonconvex primal with a convex dual
Here is an example requiring only an absolute value and a quadratic. Take \(F(x)=|x|\), and let \(G\) be the Huber function with threshold one [8]:
\[ G(x)= \begin{cases} x^2/2,& |x|\leq1,\\ |x|-1/2,& |x|\geq1. \end{cases} \]Both functions are convex, but their difference is
\[ \Phi(x)= \begin{cases} |x|-x^2/2,& |x|\leq1,\\ 1/2,& |x|\geq1. \end{cases} \]This objective is plainly nonconvex: on \((0,1)\), its second derivative is \(-1\). Nevertheless, writing \(I=[-1,1]\) and letting \(\iota_I\) denote the function equal to zero on \(I\) and \(+\infty\) outside, we have
\[ F^*(p)=\iota_I(p), \qquad G^*(p)=\frac{p^2}{2}+\iota_I(p). \]Thus the Toland dual, evaluated on \(\operatorname{dom}G^*=I\), is simply
\[ \min_{|p|\leq1}\frac{p^2}{2}. \]It is a strongly convex minimization problem on a convex interval. Its unique solution \(p_\star=0\) recovers \(x_\star=0\), the unique primal minimizer. The useful change is visible already here: the primal has an entire nonoptimal flat region, whereas the dual quadratic points directly towards its global minimum.
Proof: compute the two conjugates
For \(|p|\leq1\), \(px-|x|\leq0\), with equality at zero. For \(|p|>1\), take \(x\) to infinity with the sign of \(p\). This gives \(F^*=\iota_I\).
For \(|p|\leq1\), maximizing \(px-G(x)\) gives \(x=p\) and value \(p^2/2\). At the endpoints, a whole half-line also attains this value. For \(|p|>1\), the linear tail again makes the supremum infinite. This proves the formula for \(G^*\).
Finally, \(\partial F^*(0)=\{0\}\), so Proposition 1 recovers the primal minimizer. Directly, \(\Phi\) is nonnegative and vanishes only at zero.
The example also separates convex duality from DCA. If \(x_k>1\), then \(p_k=G'(x_k)=1\), and the next subproblem is \(\min_x(|x|-x)\). Every \(x\geq0\) minimizes it. Choosing \(x_{k+1}=x_k\) is allowed: DCA can remain forever on the nonoptimal plateau. Solving the convex dual directly avoids this ambiguity.
The shared-slope condition is weaker than stationarity of the convex dual. At \(p=1\), the subgradients of \(F^*\) and \(G^*\) overlap, but moving \(p\) towards zero still decreases \(\Psi(p)=p^2/2\).
Even a unique DCA update can remain on the plateau
Add \(\eta x^2/2\), with \(\eta>0\), to both \(F\) and \(G\). This preserves the objective and makes the first term strongly convex. At \(x_k>1\), the new slope is \(p_k=1+\eta x_k\). Up to a constant, the next subproblem becomes
\[ \min_x\left\{|x|-x+\frac{\eta}{2}(x-x_k)^2\right\}. \]Both terms are nonnegative and vanish together only at \(x=x_k\). The unique update is therefore \(x_{k+1}=x_k\). Thus the obstruction to global convergence persists even after removing the freedom to choose among minimizers. This modified decomposition has a different Toland dual, which is no longer convex.
Why the example works: smoothing by infimal convolution
The Huber function is the Moreau envelope of the absolute value. More generally, given a finite convex \(F\) and \(\lambda>0\), define [9]
\[ G(x)=\inf_z\left\{F(z)+\frac{\|x-z\|^2}{2\lambda}\right\}. \]Then \(G\leq F\) and
\[ G^*(p)=F^*(p)+\frac{\lambda}{2}\|p\|^2. \]Consequently, the dual of minimizing \(F-G\) is the convex problem
\[ \inf_{p\in\operatorname{dom}F^*}\frac{\lambda}{2}\|p\|^2. \]If \(\operatorname{dom}F^*\) is closed, its minimizer is the Euclidean projection of zero onto that domain. Recovery of a primal minimizer still requires the subgradient condition in Proposition 1. Without closedness, even dual attainment must be checked.
Proof: conjugating an infimal convolution
Put \(w=x-z\) and separate the two suprema:
\[ \begin{aligned} G^*(p) &=\sup_{z,w}\left\{\langle p,z+w\rangle-F(z)-\frac{\|w\|^2}{2\lambda}\right\}\\ &=F^*(p)+\frac{\lambda}{2}\|p\|^2. \end{aligned} \]This identity holds as an extended-real identity. Subtracting \(F^*\) is done only on its effective domain, exactly as in Theorem 1.
Why the recovery condition matters: a dual minimum without a primal one
Take \(F(x)=e^x\) and its Moreau envelope with \(\lambda=1\). Its conjugate has domain \([0,\infty)\), with \(F^*(0)=0\) and \(F^*(p)=p\log p-p\) for \(p>0\). The dual \(\min_{p\geq0}p^2/2\) attains its minimum at zero.
The primal does not. For every finite \(x\), choosing \(z=x-\delta\) with sufficiently small \(\delta>0\) gives \(G(x)<F(x)\). Yet \(0<F(x)-G(x)\leq e^x\to0\) as \(x\to-\infty\). Thus its infimum is zero but is never attained.
There is no contradiction with Proposition 1: \(\partial F^*(0)\) is empty. Indeed, the slopes \((F^*(p)-F^*(0))/p=\log p-1\) tend to \(-\infty\) as \(p\downarrow0\), so no finite supporting slope exists there.
Carlier's example: a linear objective hidden inside transport
Carlier's transport example [3, Section 3] makes the benefit tangible. Let \(\mu_+,\mu_-\) have densities on a bounded open convex set \(\Omega\), and let \(K\subset\mathbb R^d\) be nonempty, compact and convex. All measures here are probabilities. Consider
\[ \min_{\nu\in\mathcal P(K)}J(\nu), \qquad J(\nu)=\frac12W_2^2(\mu_-,\nu)-\frac12W_2^2(\mu_+,\nu), \]where \(W_2\) is the quadratic Wasserstein distance and \(\mathcal P(K)\) contains the probabilities supported in \(K\). Introduce instead
\[ \mathcal A=\{u:\Omega\to\mathbb R: u\text{ convex},\ \nabla u\in K\text{ a.e.}\}, \qquad L(u)=\int_\Omega u\,d(\mu_+-\mu_-). \]Carlier proves
\[ \min_{\nu\in\mathcal P(K)}J(\nu) =\min_{u\in\mathcal A}L(u)-c, \qquad c=\frac12\int_\Omega |x|^2\,d(\mu_+-\mu_-). \]This uses Toland duality and a further change to a convex-potential variable: the raw dual parameterization is not itself the linear problem. At an exact minimizer \(u_\star\), the optimal measure is recovered by
\[ \nu_\star=(\nabla u_\star)_\#\mu_+ =(\nabla u_\star)_\#\mu_-. \]Every optimal measure arises this way. The value identity extends beyond densities; the stated gradient recovery uses absolute continuity.
Why is the new problem better structured? Its objective \(L\) is linear, and its feasible set is convex: averaging two convex functions preserves convexity, while their averaged gradient stays in the convex set \(K\). The difficult difference of transport costs has become a linear objective with geometric constraints. One can study global optimality in this convex set rather than navigate stationary points of a difference of distances.
There is an analytic benefit too. Adding a constant to \(u\) does not change \(L\), so fix \(u(x_0)=0\) at some \(x_0\in\Omega\). Boundedness of \(K\) bounds both slopes and values. After continuous extension to \(\overline\Omega\), the normalized feasible family is closed and compact in the uniform norm by Arzelà–Ascoli. This gives existence, not uniqueness: if \(\mu_+=\mu_-\), both objectives are constant.
A computational consequence: a finite linear program
For a finite approximation, replace the signed measure \(\mu_+-\mu_-\) by weights \(w_i\) at points \(x_i\in\Omega\), with \(\sum_iw_i=0\). Store a value \(u_i\) and a supporting slope \(g_i\) at each point. The resulting problem is
\[ \begin{aligned} \min_{u_i,g_i}\quad &\sum_iw_i u_i\\ \text{subject to}\quad &u_j\geq u_i+g_i\cdot(x_j-x_i)\quad\forall i,j,\\ &g_i\in K\quad\forall i,\qquad u_1=0. \end{aligned} \]The inequalities hold for every pair \(i,j\). They are linear in the unknown values and slopes; if \(K\) is a polytope, its constraints are linear too. Thus this finite potential problem is a linear program.
The constraints have a direct meaning. The convex function
\[ u(x)=\max_i\{u_i+g_i\cdot(x-x_i)\} \]interpolates the prescribed values and has gradients in \(K\) wherever it is differentiable. Conversely, feasible convex potentials supply such supporting slopes at interior sample points. The linear program therefore represents the discrete potential problem exactly. Approximation of the original measures, and recovery of a transport minimizer from an approximate potential, still need their own error analysis. This construction illustrates the benefit of convexity; it is not a claim that every discretization solves the continuum problem exactly.
This is also a reason to preserve the convex formulation when choosing numerical variables. Replacing \(u\) by an arbitrarily parameterized neural network can reintroduce nonconvexity in the parameters, even though the underlying optimization over functions is convex.
Related signed Wasserstein barycenters
For probability measures with finite second moments, a signed barycenter minimizes
\[ \inf_\mu\sum_i\lambda_i W_2^2(\mu,\nu_i), \qquad \sum_i\lambda_i=1, \]where some coefficients are negative. Positive coefficients encourage closeness to their reference measures; negative coefficients encourage separation, while the positive total weight controls the quadratic growth. The two-measure case defines metric extrapolation: it agrees with extending a minimizing Wasserstein geodesic when such a minimizing continuation exists, and remains defined when no such continuation exists [10].
Gallouët, Natale and Todeschi [11] establish two convex dual formulations when exactly one coefficient is positive: one uses Brenier potentials, the other a projection under convex-order constraints. They also study the general signed case and develop particle algorithms using entropic regularization. The special sign pattern matters: their general case need not have the same convexity or uniqueness properties.
These transport results show why the elementary duality is useful beyond finite-dimensional toy examples. It gives a systematic question to ask of a nonconvex model: does exchanging positions for supporting slopes reveal a better geometry?
References
- J. F. Toland. Duality in nonconvex optimization. Journal of Mathematical Analysis and Applications 66(2), 399–415, 1978.
- J. F. Toland. A duality principle for non-convex optimisation and the calculus of variations. Archive for Rational Mechanics and Analysis 71, 41–61, 1979.
- Guillaume Carlier. Remarks on Toland's duality, convexity constraint and optimal transport. Pacific Journal of Optimization 4(3), 423–432, 2008.
- Pham Dinh Tao and Le Thi Hoai An. Convex analysis approach to d.c. programming: theory, algorithms and applications. Acta Mathematica Vietnamica 22(1), 289–355, 1997.
- Hoai An Le Thi and Tao Pham Dinh. DC programming and DCA: thirty years of developments. Mathematical Programming 169, 5–68, 2018.
- R. Tyrrell Rockafellar. Convex Analysis. Princeton University Press, 1970.
- Alan L. Yuille and Anand Rangarajan. The concave-convex procedure. Neural Computation 15(4), 915–936, 2003.
- Peter J. Huber. Robust estimation of a location parameter. The Annals of Mathematical Statistics 35(1), 73–101, 1964.
- Jean-Jacques Moreau. Proximité et dualité dans un espace hilbertien. Bulletin de la Société Mathématique de France 93, 273–299, 1965.
- Thomas O. Gallouët, Andrea Natale and Gabriele Todeschi. Metric extrapolation in the Wasserstein space. Calculus of Variations and Partial Differential Equations 64, article 147, 2025.
- Thomas Gallouët, Andrea Natale and Gabriele Todeschi. Toland duality and particle approximations for signed Wasserstein barycenters. arXiv:2609.17073, 2026.