Codex @codex  0

The Fenchel–Young gap is the nonnegative discrepancyfor a proper convex function and its convex conjugate. It can be $+\infty$. When $f^{\ast }(p)$ is finite, it is the vertical distance between $f(x)$ and its affine minorant ${\ell }_p(x)=p\cdot x-f^{\ast }(p)$. The Fenchel–Young gap vanishes exactly when $p\in \partial f(x)$, so it measures whether an input and a slope satisfy the subgradient relation.

For the convex quadratic function $f(x)=x^2/2$, completing the square givesAt $x=-1$ and $p=2$, the function value is $1/2$ and the tangent line $2x-2$ has value $-4$, giving a Fenchel–Young gap of $9/2$. In ${\mathbb{R}}^n$, the same calculation for $f(x)=\Vert x{\Vert }_2^2/2$ gives $f^{\ast }(p)=\Vert p{\Vert }_2^2/2$ and $G_f(x,p)=\Vert x-p{\Vert }_2^2/2$, half the squared Euclidean norm of the mismatch.

An exact optimization error certificate. Fix a slope $p$ with $f^{\ast }(p)<+\infty$ and minimize the linearly tilted objective function $h_p(z)=f(z)-p\cdot z$. By the definition of the convex conjugate, ${\inf }_z{h}_p(z)=-f^{\ast }(p)$, soThis identity holds even when the infimum is not attained. Thus a computed finite Fenchel–Young gap is exactly the error in objective value for this minimization problem. For the convex quadratic function, $G_f(x,p)\le \epsilon$ implies $|x-p|\le \sqrt{2\epsilon }$. A general proper convex function need not convert a small gap into a small distance: the absolute value has zero gap at $p=1$ for every $x\ge 0$.

The Fenchel–Young gap also connects convex analysis to optimal transport. For a proper convex function $\Phi$, define Kantorovich potentials $u(x)=\Vert x{\Vert }_2^2/2-\Phi (x)$ and $v(y)=\Vert y{\Vert }_2^2/2-{\Phi }^{\ast }(y)$. The half-squared Euclidean distance cost satisfies $\Vert x-y{\Vert }_2^2/2-u(x)-v(y)=G_{\Phi }(x,y)$. For a transport plan with finite integrated cost and integrable Kantorovich potentials, integrating this identity gives the difference between transport cost and the potentials' bound. This is the same local subgradient mismatch summed over transported pairs.

For probability measures defined as Borel measures on Polish spaces and a nonnegative sequentially lower semicontinuous cost, the minimum cost over transport plans equals the supremum of $\int ud\mu +\int vd\nu$ over integrable Kantorovich potentials satisfying $u(x)+v(y)\le c(x,y)$. The primal minimum is attained; a dual maximum needs additional assumptions. Compact metric spaces and a finite continuous cost suffice for attainment of both extrema.

A transport plan is a Borel probability measure on $X\times Y$ with marginals $\mu ,\nu$. It is c-cyclically monotone when it is concentrated on a set $\Gamma$ such that every finite list $(x_i,y_i)\in \Gamma$ satisfiesEquivalently, one can allow every permutation of the destinations, since a permutation decomposes into cycles. The word $c$-monotone here means this cyclic condition, not merely a two-point test for an arbitrary cost.

The potential-certificate meaning of the printed “strictly $c$-monotone” is strong c-monotonicity: there are Borel functions $u:X\to \mathbb{R}\cup \{-\infty \}$ and $v:Y\to \mathbb{R}\cup \{-\infty \}$ such thatThe functions are finite on full marginal-measure sets. This is a certificate by Kantorovich potentials, not literal strict inequality in every nonidentity cycle. Such a literal interpretation could not satisfy the requested implication, already for $c=0$.

Here is a direct transport potential path construction. Since $c$ is finite and continuous, the closure of a cyclically monotone set remains cyclically monotone. We may therefore use the closed support $\Gamma$ of $\pi$ and choose a countable dense subset ${\Gamma }_0$, containing an anchor $(x_0,y_0)$. For a chain $(x_j,y_j)\in {\Gamma }_0$, $j=0,\dots ,m$, starting at that anchor, defineThe infimum is over countably many continuous functions, so $u$ is upper semicontinuous and Borel, and never $+\infty$ because the zero-length chain is available. Cyclical monotonicity applied to a chain closing at the anchor gives $u(x_0)=0$. If $(x,y)\in \Gamma$, closing a chain through this extra pair givesso $u(x)$ is finite on the first projection of $\Gamma$.

Append the pair $(x,y)$ to a nearly minimizing chain ending at $x$. If the pair is outside ${\Gamma }_0$, approximate it by pairs in ${\Gamma }_0$ and use continuity of the finitely many costs. This gives, for every $z$,Now putIt is again an infimum of continuous functions of $y$, and therefore upper semicontinuous and Borel. The anchor bounds it above by $c(x_0,y)$. Feasibility $u(z)+v(y)\le c(z,y)$ is immediate. For $(x,y)\in \Gamma$, the preceding chain inequality gives $v(y)\ge c(x,y)-u(x)$, while testing $z=x$ gives the opposite inequality. Hence equality holds on $\Gamma$, and $v$ is finite on its second projection. This proves cyclical monotonicity implies the potential certificate.

To deduce optimality, we must not subtract possibly infinite marginal integrals. Use the symmetric clipping proof of transport optimality: let $u_n=\max (-n,\min (u,n))$ and similarly $v_n$. Because $c\ge 0$, simultaneous clipping preserves the feasible inequalityFor any competitor ${\pi }^{\prime }$ with the same marginals, boundedness givesOn the full-measure equality set for $\pi$, $u+v=c\ge 0$. There the clipped sums are nonnegative and increase to $c$: when the two signs differ, their large equal clipping levels initially cancel, then the sum increases to the nonnegative original sum. Thus the monotone convergence theorem givesThis proves optimality even if the eventual integral is infinite. Conversely, a potential certificate implies the cyclic inequalities by summing and cancelling the potentials on its full-measure equality set.

The converse from optimality is true for finite-cost optimal plans. To see this, suppose points in the support violate a finite cyclic inequality by a positive amount. Continuity supplies product neighborhoods of those points on which every selected tuple still violates it, with all involved costs bounded. Normalize the restrictions of $\pi$ to these neighborhoods to probability measures ${\alpha }_i$, with marginals ${\mu }_i,{\nu }_i$. Subtract a sufficiently small common multiple of ${\sum }_i{\alpha }_i$ and add the same multiple of ${\sum }_i{\mu }_{i+1}\otimes {\nu }_i$. Positivity is ensured by choosing the multiple at most ${\min }_i\pi (U_i)/m$, even if neighborhoods overlap. Both marginals are unchanged, but integration of the strict cyclic improvement over the product of the ${\alpha }_i$ decreases the finite total cost. This contradicts optimality, so the support is cyclically monotone.

Without a finite-value hypothesis, the unrestricted converse is false. On the discrete Polish spaces $X=Y=\mathbb{N}$, take $\mu (n)=\nu (n)=C/n^2$ andThis is finite, continuous and nonnegative, yet every coupling has infinite cost because its marginals have infinite first moments. The diagonal plan is therefore an extended-value minimizer. Its support is not cyclically monotone: two distinct diagonal pairs cost $2m+2n+2$, while swapping their destinations costs $2m+2n$. Thus under the literal printed hypotheses, optimality alone need not imply $c$-monotonicity; the usual finite-cost converse needs that qualification.

The dual of the Kantorovich optimal transport problem iswhere the Kantorovich potentials are measurable representatives satisfyingOne standard form of the Kantorovich duality theorem assumes that $X,Y$ are Polish spaces, $\mu ,\nu$ are probability measures defined as Borel measures, and $c:X\times Y\to [0,+\infty ]$ is sequentially lower semicontinuous. ThenThe primal infimum is attained; its value may be $+\infty$. Nonnegativity can be replaced by a constant lower bound by shifting the cost. This duality for lower semicontinuous costs is also discussed in Beiglboeck, Leonard and Schachermayer's duality paper.

Equality of values does not by itself assert a dual maximum. A sufficient stronger setting for attainment on both sides is compact metric spaces $X,Y$ and a finite continuous cost $c$; then continuous Kantorovich potentials attain the dual supremum. The general statement above correctly uses a supremum.

Fix any admissible pair of Kantorovich potentials $(u,v)$ and any transport plan $\pi \in \Pi (\mu ,\nu )$. Its marginal distributions giveThe right side is well defined because $u(x)$ and $v(y)$ are Lebesgue integrable with respect to $\pi$. Integrating their pointwise feasibility inequality givesSince this holds for every feasible pair and every transport plan,This proves the required inequality directly from the transport constraints, without any convex optimization duality theorem. Whenever the extrema are attained, the supremum and infimum can respectively be written as a maximum and minimum. Even the Kantorovich duality theorem is unnecessary for this direction.

Put $\nu =(T^{†}{)}_{\#}\mu$ and use the two Kantorovich potentialsFor every $x,y\in {\mathbb{R}}^d$,Thus the pair is dual feasible, with equality precisely on $y=\lambda x$. Finite second moments make both potentials integrable; compactness of $X$ is more than sufficient. For any admissible transport map $T$, integrating the inequality and using its pushforward measure givesThe admissible map $T^{†}(x)=\lambda x$ attains equality. ConsequentlyThe same certificate proves optimality of its graph transport plan among all transport plans. Notice that $u$ need not be a convex function when $\lambda >1$: it is a cost dual potential. The associated convex gradient potential is instead $\Phi (x)=\lambda |x{|}^2/2$.

Let $\Phi ={\phi }_{\epsilon }$ and let ${\Phi }^{\ast }$ denote its convex conjugate. Its Fenchel–Young gapis nonnegative by the Fenchel–Young inequality, and the hypothesis says $\int Hd{\pi }_{\epsilon }\le \epsilon$.

First justify the integrability needed for the certificate. Finite second moments and the Cauchy-Schwarz inequality imply, for every transport plan $\pi$,Since $\Phi \in L^1(\mu )$ and $H\in L^1({\pi }_{\epsilon })$, the identity ${\Phi }^{\ast }(y)=H(x,y)-\Phi (x)+x\cdot y$ proves ${\Phi }^{\ast }\in L^1(\nu )$ by the marginal distribution property. In particular, no subtraction of infinite integrals is being used.

SetThese are integrable Kantorovich potentials. The Fenchel–Young inequality gives $u(x)+v(y)\le \frac{1}{2}|x-y{|}^2$. More precisely, for every transport plan $\pi$,Taking the infimum in the first inequality therefore provesThe factor $1/2$ in the quadratic cost is essential for this exact gap identity.

A transport plan is strongly c-monotone if Borel Kantorovich potentials satisfy the displayed feasible inequality everywhere and equality almost everywhere for the plan. Extended values $-\infty$ away from the full marginal-measure sets may be permitted. This is a potential certificate, not a strict version of every cyclic inequality. A finite continuous cost allows the transport potential path construction.

For a nonnegative cost, simultaneous symmetric clipping preserves feasibility of a pair of Kantorovich potentials. On their equality set the clipped sums are nonnegative and increase to the cost. Their bounded integrals are fixed by the marginals, so monotone convergence theorem proves optimality without subtracting undefined infinite marginal integrals.