Dual Problem

Duality turns the transport problem into a search for potentials rather than couplings. This chapter explains why potentials certify optimality, how $c$-transforms regularize them, and why the quadratic case reveals convex analysis behind Brenier maps. Linear-programming duality gives the discrete picture Bertsimas & Tsitsiklis, 1997, while the continuous form is one of the central theorems of optimal transport Villani, 2003Santambrogio, 2015.

from pathlib import Path
import sys

from IPython.display import Image as DisplayImage
from IPython.display import display

here = Path.cwd()
myst_dir = None
for candidate in [here, here.parent, here / "myst", here.parent / "myst", here.parent.parent / "myst"]:
    if (candidate / "ot4ml_web.py").exists():
        myst_dir = candidate.resolve()
        sys.path.insert(0, str(myst_dir))
        break

if myst_dir is None:
    raise RuntimeError("Could not locate myst/ot4ml_web.py")

repo_root = myst_dir.parent
thumbnails = repo_root / "notebooks-figures" / "thumbnails"

def show_book_figure(name, width=760):
    display(DisplayImage(filename=str(thumbnails / f"{name}.png"), width=width))

Discrete Dual¶

The discrete dual gives finite-dimensional certificates of optimality. Its complementary-slackness conditions identify where an optimal coupling can put mass.

The two vectors play the role of source and target prices; admissibility means that no transported pair is priced above its travel cost. The discrete Kantorovich problem is a linear program. Hence its value can be computed either by minimizing over couplings or by maximizing over a pair of dual vectors.

Thus potentials are not transport maps themselves. They are certificates, and their equality set with the cost matrix is where an optimal coupling is allowed to place mass.

Figure Div shows these finite-dimensional certificates on a one-dimensional quadratic problem.

show_book_figure("dual-kantorovich-discrete-potentials")

Discrete Kantorovich dual potentials for the quadratic cost $\C_{ij}=|x_i-y_j|^2$. The upper strip shows the fixed source histogram in red and the target histogram in blue. The lower strip shows optimal dual vectors $(f,g)$, with a gauge chosen so that $\langle f,a\rangle=0$. Complementary slackness states that mass can be transported only through entries where $f_i+g_j=\C_{ij}$.

The interactive demo varies the target law and the number of bins. The lower curves are reconstructed from the active monotone transport graph, so the equality set moves as the coupling support changes.

The formula (2) also shows that $(a,b)\mapsto\mathcal{L}_\C(a,b)$ is convex, being a supremum of linear functions. From the primal formulation, $\C\mapsto\mathcal{L}_\C(a,b)$ is concave.

General Formulation¶

The continuous dual is the analytic counterpart of the discrete linear program. It uses continuous potentials because measures are naturally probed through integration.

Continuous Duality¶

The finite-dimensional price vectors become continuous test functions. The pairing is $\langle f,\alpha\rangle\eqdef\int f\,\d\alpha$.

Complementary Slackness¶

As in the finite problem, equality of primal and dual values localizes the support of every optimal coupling.

The discrete case corresponds to dual vectors that sample the continuous potentials, $(f_i,g_j)=(f(x_i),g(y_j))$.

For the one-dimensional quadratic cost, the continuous potentials can be read from the monotone map $T=F_\beta^{-1}\circ F_\alpha$: on the active graph, $f'(x)=2(x-T(x))$ and $g=f^c$.

Figure Div shows how these continuous potentials adapt to increasingly multimodal source and target densities while retaining the same complementary-slackness interpretation.

show_book_figure("dual-kantorovich-continuous-potentials")

Continuous Kantorovich potentials for the same source and target families as the discrete potential figure. The upper strips show the source density $\alpha$ in red and the target density $\beta$ in blue. The lower strips show potentials $f$ and $g=f^c$ for the quadratic cost $c(x,y)=|x-y|^2$. The equality set $f(x)+g(y)=c(x,y)$ contains the monotone transport graph.

The same optimality condition is even more explicit if one plots the slack

Dual feasibility is the statement $s\ge 0$, while complementary slackness says that an optimal coupling can only live where this slack vanishes. The next figure shows this zero set for increasingly structured one-dimensional transports, including a Gaussian source mapped to a separated three-component target mixture: the transported graph is not guessed from the potentials separately, but appears as the contact valley of the dual inequality.

Figure Div shows this zero set for increasingly structured one-dimensional transports, including a Gaussian source mapped to a three-component target mixture: the transported graph is not guessed from the potentials separately, but appears as the contact valley of the dual inequality.

show_book_figure("dual-complementary-slackness-contacts", width=760)

Complementary slackness contacts for one-dimensional quadratic OT. From left to right: two Gaussian densities, two-component Gaussian-mixture densities, and one Gaussian density transported to a separated three-component mixture. The central heatmaps display the nonnegative dual slack $s(x,y)=|x-y|^2-f(x)-g(y)$: pale colors mark the contact valley and darker blue means larger strict slack. The red top strip and blue side strip show the source and target densities. The violet curve is the quantile transport contact graph $(x,T(x))$, where $s(x,T(x))=0$ and the optimal Monge plan is supported.

The interactive view computes the monotone map from numerical quantiles and then integrates $f'(x)=2(x-T(x))$. It makes clear that the potentials change smoothly with the target law, even though the equality set remains a thin transport graph.

In contrast to the primal problem, dual attainment is not immediate: the constraint set is not compact and the objective is not coercive. The $c$-transform selects canonical representatives that inherit the modulus of continuity of the cost; a gauge condition then makes the family compact.

c-Transforms¶

The $c$-transform is the operation that improves potentials without changing feasibility. It is both a proof device for dual attainment and the route from duality to Brenier’s convex potentials.

Best-Response Potentials¶

Keeping a dual potential $f$ fixed, one can maximize in closed form over the second potential in the dual problem:

The constraint is equivalent to $g(y)\le f^c(y)$.

Since $\beta$ is nonnegative, maximizing $\int g\,\d\beta$ is achieved by taking $g=f^c$ on the support of $\beta$, equivalently $\beta$-almost everywhere.

Figure Div makes the best-response operation geometric: the discrete $c$-transform is the lower envelope of the shifted cost functions.

show_book_figure("dual-c-transform-envelope")

Discrete $c$-transform as a lower envelope for costs $c_p(x,y)=|x-y|^p$. The red circles are four source atoms $x_i$ with potential values $f_i$; the gray curves are $y\mapsto c_p(x_i,y)-f_i$; the colored curve is their lower envelope $f^c(y)=\min_i c_p(x_i,y)-f_i$. This is the semi-discrete situation where the source space is finite.

The interactive envelope view exposes the exponent, the number of atoms, and the potential amplitude. This is the local mechanism behind many dual regularity statements: taking a pointwise minimum of translated costs inherits regularity from the cost.

The updates must be sequential:

Each step preserves feasibility and improves the objective. Simultaneously replacing an arbitrary old pair by $(g^{\bar c},f^c)$ need not preserve feasibility, because the two best responses were computed against different old coordinates. For example, if $c\equiv0$ and $f=g\equiv-1$, both transforms equal 1 and their simultaneous update violates the dual constraint. Functions of the form $f^c$ and $g^{\bar c}$ are called $c$-concave and $\bar c$-concave, respectively.

This stability is crucial for dual attainment. On compact spaces, continuity of $c$ already supplies uniform moduli; sequential closure and a harmless additive gauge then give compactness by Arzela--Ascoli.

Euclidean Case¶

The Euclidean quadratic cost is the model case where $c$-transforms become ordinary convex conjugates after removing quadratic terms. This is the algebraic bridge between Kantorovich duality and Brenier maps.

Normalize the quadratic cost as $q(x,y)=\frac12\norm{x-y}^2$. For any $\pi\in\Couplings(\alpha,\beta)$,

The first two terms depend only on the marginals, so quadratic OT reduces to $c(x,y)=-\langle x,y\rangle$. For this bilinear cost,

On full Euclidean space, $f^{c\bar c}=-(-f)^{**}$. Hence $c$-closed functions are negatives of lower semicontinuous convex functions, and closure gives the smallest upper semicontinuous concave majorant. On restricted compact domains, the supporting slopes must additionally belong to the opposite domain.

Why Hard Alternating Optimization Stops¶

A crucial property of the Legendre transform is that $f^{***}=f^*$, while $f^{**}$ is the lower semicontinuous convex envelope of a proper $f$. Analogous identities explain why exact alternating best responses stop after one cycle for $c$-transforms Rockafellar, 2015.

This invariance shows that exact block maximization reaches a coordinatewise fixed point after one full cycle:

The resulting pair is dual feasible but need not maximize the joint objective, because its value still depends on the arbitrary initial $f$. Entropic regularization replaces hard minima by soft log-sum-exp responses and leads to the nontrivial Sinkhorn scaling iteration.

For $c(x,y)=-xy$ on compact intervals, $f^{c\bar c}$ is the smallest concave majorant representable with slopes in the opposite interval. In the displayed example that interval contains every relevant supporting slope, so the restricted closure is the ordinary concave envelope.

In Figure Div, the displayed interval contains all relevant supporting slopes, so this restricted closure agrees with the ordinary concave envelope.

show_book_figure("dual-alternating-c-transform-failure")

Hard $c$-transforms for the bilinear cost $c(x,y)=-xy$. Dark curves are the double-transform closures $f^{c\bar c}$ and $g^{\bar c c}$, while dashed lighter curves are the one-sided best responses after a harmless gauge shift. The domains contain the relevant supporting slopes, so these restricted closures coincide with ordinary concave majorants. Exact best responses are useful for certificates but do not give the smooth iterative dynamics of entropic regularization.

The final interactive demo turns this algebra into a visible operation: change the roughness of the starting potential and observe that the hard double transform jumps directly to its concave closure.