Move one pile of earth onto another at least cost. With the right cost the best plan is the gradient of a convex function, and that function solves a nonlinear second-order equation. This chapter states the pieces and checks the ones that can be checked on a finite example.
Take two distributions of mass, f on a region X and g on Y, with equal totals, and a cost c(x, y) of moving a unit from x to y. Monge's original problem asks for a map T from X to Y that carries f onto g and minimises the total cost ∫ c(x, T(x)) f(x) dx. Kantorovich's relaxation lets mass at one point split among several; a plan is then a joint distribution with the right two marginals. The review frames the plan version through a shipping company that must move goods from warehouses to shops.
On a finite example the plan is a matching, and the whole subject can be run by brute force. That is what the checker does: six integer points in the plane, all 720 matchings, quadratic cost.
With cost |x − y|², optimal plans have a property called cyclical monotonicity: no rearrangement of the targets among any cycle of the sources lowers the cost. A theorem the review credits to Rockafellar says such a set is contained in the graph of the subdifferential of a convex function. So the optimal map is T = ∇φ with φ convex (Brenier's theorem, under conditions the review states and this page does not reprove).
Checked: for the seeded six-point instance the brute-force optimal plan maximises Σ ⟨yi, xi⟩ over every rearrangement of its own targets — cyclical monotonicity, tested on 720 permutations — and the worst plan does not have the property. In one dimension the optimal matching is the sorted one, which held on 40 random six-point sets; the order-reversing matching cost more (20 against 0 on the example printed).
The dual problem prices the move: find functions u(x) and v(y) with u(x) + v(y) ≤ c(x, y), maximising Σ u + Σ v. Any admissible pair gives a lower bound on every plan's cost. Given u, the best v is the c-transform v*(y) = minx [c(x, y) − u(x)], and for the quadratic cost this is, up to rearrangement of terms, a Legendre transform.
Checked: the Hungarian algorithm's potentials on the same instance are admissible, tight on the matched pairs, and sum to 1303, which is the brute-force minimum, so strong duality holds there with nothing to spare. Raising one potential by 1 breaks admissibility. Applying the c-transform to an admissible pair gave an admissible pair that is nowhere smaller; with max in place of min the result was not admissible.
If T = ∇φ carries f onto g, conservation of mass says g(∇φ(x)) det D²φ(x) = f(x). That is a Monge–Ampère equation, with the convexity of φ as the condition that selects the right solution. Where φ is not smooth the equation has to be read in a weak sense; the review uses the Alexandrov sense and a maximal-monotone one. How regular φ is, and under what conditions on f, g and the shapes of X and Y, is where Caffarelli's regularity theory enters. This page does not state those theorems and does not test them.
Checked, with Gaussians: in one dimension the affine map between two Gaussians satisfies the equation to 8×10−17 at 81 points. In the plane, with covariances S1 and S2, the map T x = A x with A = S1−1/2(S11/2 S2 S11/2)1/2 S1−1/2 satisfies it to 4×10−17 on 169 points, and A is symmetric positive definite, so T is the gradient of the convex function x·A x/2. The control is a different map, S21/2 Q S1−1/2 with Q a rotation: it pushes the density forward just as well (error 2×10−17) but is not symmetric, so it is not the gradient of any convex function. That is the point of the control: pushing the mass forward is not what makes a map optimal; being a convex gradient is.
Cost |x − y|. Move [−2, −1] onto [1, 2]. Every matching pays the same, because every unit crosses the whole gap; on the checker's grids all 200 random matchings cost exactly 27, whereas the quadratic cost separates them and the sorted matching is the cheapest. Optimal maps for the linear cost are therefore not unique, which is one reason the quadratic case is the clean one.
A target with a gap. Send [−1, 1], density 1, onto [−2, −1] ∪ [1, 2], density 1, by T(x) = x + sign(x). It is monotone, and its Jacobian is 1 away from 0, so the equation holds there. The potential φ(x) = |x| + x²/2 has second difference 1 away from 0 and about 1 + 2/h at 0 — the second derivative carries a point mass of weight 2 there. So with a non-convex target the potential is not smooth, and the equation holds in the Alexandrov sense rather than classically. The control (the value at 0 is not the almost-everywhere value 1) fails as it should.
Examples, not theorems. Nothing here proves that optimal plans exist, are unique, are maps, or are regular, and nothing tests Caffarelli's regularity theory itself; that needs the review's hypotheses and an analysis a finite grid does not carry. The Gaussian and one-dimensional examples are the cases where a closed form exists. Where this page says “Brenier” or “Alexandrov”, it follows the review's statement of those results.
One structural remark, labelled as such. The c-transform has the same functional form as a Legendre transform, and Legendre transforms turn up elsewhere in the corpus. That is a shared functional form, not a shared invariant: nothing here connects the transport problem to any other chapter's quantity.
L. A. Caffarelli, The Monge–Ampère Equation and Optimal Transportation, an
elementary review (Lecture Notes in Mathematics 1813; read in full, supplied as a PDF). That
review credits the convex-potential theorem to Rockafellar, spelling it “Rockafeller”,
and treats the linear-cost and non-convex-target examples. · Checks:
book7/ch-optimal-transport-verify.py, standard library only, seeded.