1.1. General duality 23 the other hand, if ζ is nonpositive (dμ ⊗ dν-everywhere), the supremum is clearly obtained for π = 0. Thus, sup π∈M+(X×Y ) X×Y [ϕ(x) + ψ(y) − c(x, y)] dπ(x, y) = 0 if (ϕ, ψ) ∈ Φc, +∞ else. Plugging this into (1.8), we obtain (1.8) = sup (ϕ,ψ)∈Φc J(ϕ, ψ), as desired. Exercise 1.7 (Finite-dimensional linear programming). Linear pro- gramming consists in the study of the minimization or maximization of linear problems subject to inequalities defined by linear functions. The standard duality relation of linear programming in Rn asserts that for any b ∈ Rm, c ∈ Rn, A ∈ Mm×n(R), sup Ax≤b c · x = inf y≥0, AT y=c b · y, where AT denotes the transpose of A, and the notation y ≥ 0 means that all components of y are nonnegative. (i) Recover this relation by a minimax principle. (ii) (tedious!) Formally recover the Kantorovich duality as a continuous limit of it. A solution can be found in [126]. Remark 1.8. This connection is no accident: Kantorovich is considered as the inventor of linear programming (at the end of the thirties)! 1.1.6. A rigorous minimax principle. There are several quite general theorems of convex analysis, which yield rigorous minimax principles. Fol- lowing a suggestion by Brenier, we shall use here a simple but most useful one, that can be found at the very beginning of Br´ ezis [64]. To state it conveniently, we introduce the concept of Legendre-Fenchel transform, as follows. Let E be a normed vector space, and Θ a convex function on E with values in R ∪ {+∞}. Recall that the convexity assumption means ∀(z1,z2,λ) ∈ E ×E ×[0, 1], Θ(λz1 +(1−λ)z2) ≤ λΘ(z1)+(1−λ)Θ(z2), with the obvious extension of the operations of R to R ∪ {+∞}. Then the Legendre-Fenchel transform of Θ is the function Θ∗, defined on the topological dual E∗ of E by the formula Θ∗(z∗) = sup z∈E z∗,z − Θ(z) .

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 2003 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.