Finite multi-marginal duality and complementary slackness #
For finitely many finite spaces, the multi-marginal dual problem has one real-valued potential per marginal, constrained so that their pointwise sum never exceeds the cost.
The basic identity in this file is the multi-marginal analogue of the transportation-matrix gap formula: the difference between the cost of a plan and the value of a family of potentials is the expectation of the pointwise dual gap. It gives weak duality and complementary slackness. A finite-dimensional minimax argument then proves strong duality and attainment of both problems. In particular, a feasible plan and feasible potentials are simultaneously optimal exactly when every configuration carrying mass saturates the dual constraint.
The finite coupling model and its bridge to the measure-theoretic TauCeti.MultiCoupling API live
in TauCeti.MeasureTheory.OptimalTransport.MultiMarginal.Finite.Basic.
This completes the finite linear-programming part of multi-marginal duality. The index type is assumed nonempty for strong duality: with no marginals the dual has no variables and cannot represent an arbitrary cost on the one-point empty product.
References #
- C. Villani, Optimal Transport: Old and New, Springer, 2009, Chapter 1, for the multi-marginal Kantorovich problem and its marginal-potential dual.
- M. Sion, On general minimax theorems, Pacific J. Math. 8 (1958), 171--176, through
Mathlib.Topology.Sion. TauCeti.MeasureTheory.OptimalTransport.Finite.Duality, for the two-marginal gap and minimax and complementary-slackness arguments generalized here to a finite family.
Adding a coordinatewise constant to the potentials adds the sum of those constants to the dual value.
The finite multi-marginal dual value is continuous in the potentials.
Apply a feasible family of potentials to one configuration.
Lowering every potential preserves dual feasibility.
Shifting each potential by a constant whose total is zero preserves dual feasibility.
Integrating the sum of the coordinate potentials against a coupling gives their dual value. This is the finite change-of-variables identity behind multi-marginal weak duality.
The cost of a plan minus the value of a family of potentials is the mass-weighted sum of the pointwise dual gaps.
Finite multi-marginal weak duality. Every feasible family of potentials has value at most the cost of every feasible plan.
Finite multi-marginal complementary slackness. A feasible plan and feasible family of potentials have the same value exactly when every configuration carrying mass saturates the dual constraint.
A complementary-slackness pair is simultaneously primal- and dual-optimal among all finite multi-marginal plans and all feasible families of potentials.
Attainment on finite spaces #
Finite multi-marginal primal attainment. Every real cost has a minimizing coupling on a nonempty finite family of finite spaces.
Dual attainment #
Shifting the potentials by constants of total zero changes neither dual feasibility nor the dual
value, so an arbitrary feasible family may first be normalised: subtract from each potential its
maximum and return the accumulated total to one coordinate, after which no potential exceeds a
bound M for the cost. A normalised family is then confined to a box: at a marginal point of
zero weight the potential may be lowered outright, and at a point of positive weight that weight
turns a lower bound for the dual value into a lower bound for the potential. Families of value at
least -M therefore have representatives in a compact box, where the dual value is attained.
Finite multi-marginal dual attainment. Every real cost on a nonempty finite family of finite spaces has a maximizing feasible family of marginal potentials.
Strong duality #
Finite multi-marginal Kantorovich duality. For a nonempty finite family of finite spaces, the primal and dual problems have the same value and both attain it.
The common optimal value of the finite multi-marginal primal and dual problems.
A feasible finite multi-marginal plan and potential family are both optimal exactly when their pointwise dual gap vanishes on every configuration carrying mass.