MathLabs
Định lýĐã chứng minh

Định lý đối ngẫu Kantorovich

Phát biểu

Với các độ đo xác suất μ\mu trên XX, ν\nu trên YY (không gian Ba Lan) và một hàm chi phí cc liên tục, bị chặn dưới, bài toán Kantorovich bằng một bài toán đối ngẫu cực đại hóa trên các cặp thế Kantorovich φ:X→R\varphi:X\to\mathbb R, ψ:Y→R\psi:Y\to\mathbb R thỏa mãn φ(x)+ψ(y)≤c(x,y)\varphi(x) + \psi(y) \le c(x,y) tại mọi điểm: min⁡γ∈Π(μ,ν)∫X×Yc dγ  =  sup⁡φ(x)+ψ(y)≤c(x,y)(∫Xφ dμ+∫Yψ dν),\min_{\gamma\in\Pi(\mu,\nu)}\int_{X\times Y} c\,d\gamma \;=\; \sup_{\varphi(x)+\psi(y)\le c(x,y)}\left(\int_X\varphi\,d\mu+\int_Y\psi\,d\nu\right), và cả cực tiểu lẫn cực đại đều đạt được.

Vì sao đúng?

Hãy hình dung φ(x)\varphi(x) là mức giá thu khi lấy khối lượng tại xx và ψ(y)\psi(y) là mức giá trả khi giao tại yy, trong một thị trường phi tập trung gồm các hãng vận chuyển độc lập. Không hãng nào có thể sinh lời bằng cách phá giá tuyến đường trực tiếp: mua ở giá φ(x)\varphi(x) rồi bán ở giá ψ(y)\psi(y) không bao giờ có thể tốt hơn việc thực sự chuyển khối lượng và trả c(x,y)c(x,y) — đúng bằng ràng buộc φ(x)+ψ(y)≤c(x,y)\varphi(x)+\psi(y)\le c(x,y). Trong một thị trường cân bằng tối ưu, đẳng thức φ(x)+ψ(y)=c(x,y)\varphi(x)+\psi(y)=c(x,y) xảy ra đúng dọc theo những tuyến đường thực sự được một kế hoạch tối ưu sử dụng.

Phác thảo chứng minh

Với các độ đo rời rạc hữu hạn μ=∑ipiδxi\mu=\sum_i p_i\delta_{x_i}, ν=∑jqjδyj\nu=\sum_j q_j\delta_{y_j}, bài toán Kantorovich chính là quy hoạch tuyến tính hữu hạn min⁡∑i,jcijγij\min \sum_{i,j} c_{ij}\gamma_{ij} với ràng buộc γij≥0\gamma_{ij}\ge0, ∑jγij=pi\sum_j\gamma_{ij}=p_i, ∑iγij=qj\sum_i\gamma_{ij}=q_j. Bài toán đối ngẫu của nó chính xác là max⁡∑ipiφi+∑jqjψj\max \sum_i p_i\varphi_i+\sum_j q_j\psi_j với ràng buộc φi+ψj≤cij\varphi_i+\psi_j\le c_{ij} với mọi i,ji,j — mỗi biến đối ngẫu ứng với một ràng buộc biên gốc. Bài toán gốc khả thi (khớp nối tích piqjp_iq_j luôn hoạt động) và bị chặn dưới bởi 00, còn đa diện khả thi {γij≥0}∩Π(μ,ν)\{\gamma_{ij}\ge0\}\cap\Pi(\mu,\nu) compact, nên đối ngẫu mạnh của quy hoạch tuyến tính cho hai giá trị tối ưu bằng nhau, và cả hai đều đạt được. Điều này chứng minh chính xác định lý trong trường hợp rời rạc; phát biểu tổng quát trên không gian Ba Lan suy ra từ cùng khuôn mẫu gốc-đối ngẫu, áp dụng đối ngẫu Fenchel–Rockafellar cho các phiếm hàm lồi trên Cb(X×Y)C_b(X\times Y) (Kantorovich 1942; xem Villani 2009, Định lý 5.10, để có lập luận đầy đủ).

Chủ đề chứa định lý này

Vận tải tối ưu

Chứng minh từng bước

Chưa có chứng minh từng bước cho định lý này.

Tài liệu tham khảo

  1. Cédric Villani (2009). Optimal Transport: Old and New
  2. Marco Cuturi (2013). Sinkhorn Distances: Lightspeed Computation of Optimal Transport · arXiv:1306.0895
  3. Yann Brenier (1991). Polar Factorization and Monotone Rearrangement of Vector-Valued Functions · DOI:10.1002/cpa.3160440402
  4. John Lott, Cédric Villani (2009). Ricci Curvature for Metric-Measure Spaces via Optimal Transport