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

Định lý Brenier

Phát biểu

Cho μ,ν\mu,\nu là các độ đo xác suất trên Rn\mathbb R^n có mô men bậc hai hữu hạn, và giả sử μ\mu liên tục tuyệt đối đối với độ đo Lebesgue. Với chi phí toàn phương c(x,y)=∣x−y∣2c(x,y) = |x-y|^2 tồn tại một hàm lồi φ:Rn→R\varphi:\mathbb R^n\to\mathbb R, duy nhất sai khác một hằng số cộng, sao cho T=∇φT = \nabla \varphi xác định hầu khắp nơi theo μ\mu, thỏa mãn T#μ=νT_{\#}\mu=\nu, và là nghiệm tối ưu (về bản chất là duy nhất) của cả bài toán Kantorovich lẫn bài toán gốc của Monge.

Vì sao đúng?

Bất kỳ kế hoạch tối ưu nào đối với một chi phí lồi chặt như ∣x−y∣2|x-y|^2 đều được hỗ trợ trên một tập **đơn điệu chu trình theo cc**: không phép ghép lại hữu hạn nào của các cặp có thể làm giảm tổng chi phí. Với chi phí toàn phương, tính đơn điệu chu trình của một tập các cặp (xi,yi)(x_i,y_i) hóa ra chính xác là điều kiện tồn tại một hàm lồi φ\varphi sao cho yiy_i nằm trong vi phân dưới của nó tại xix_i với mọi ii — đây chính là định lý Rockafellar đặc trưng các tập đơn điệu chu trình như là vi phân dưới của các hàm lồi. Vì μ\mu liên tục tuyệt đối, một hàm lồi khả vi hầu khắp nơi theo μ\mu (định lý Alexandrov), biến vi phân dưới đa trị thành một ánh xạ gradient thực sự T=∇φT=\nabla\varphi.

Phác thảo chứng minh

(Phác thảo, theo Brenier 1991.) Bước 1: đối ngẫu Kantorovich với c=∣x−y∣2c=|x-y|^2 cho phép viết lại các thế tối ưu qua φ(x)=12∣x∣2−φ~(x)\varphi(x)=\tfrac12|x|^2-\tilde\varphi(x) sao cho φ\varphi lồi và biến đổi Legendre φ∗(y)=sup⁡x(x⋅y−φ(x))\varphi^*(y)=\sup_x(x\cdot y-\varphi(x)) đóng vai trò thế thứ hai; ràng buộc đối ngẫu trở thành chính xác y∈∂φ(x)y\in\partial\varphi(x) trên giá của một γ\gamma tối ưu. Bước 2: định lý Rockafellar khẳng định mọi tập con đơn điệu chu trình của Rn×Rn\mathbb R^n\times\mathbb R^n nằm trong đồ thị của ∂φ\partial\varphi với một hàm lồi nửa liên tục dưới φ\varphi nào đó; giá của kế hoạch tối ưu là đơn điệu chu trình vì γ\gamma cực tiểu hóa ∫∣x−y∣2 dγ\int|x-y|^2\,d\gamma, nên không phép ghép lại hữu hạn nào giữa hữu hạn cặp trên giá có thể làm giảm ngặt ∑i∣xi−yi∣2\sum_i|x_i-y_i|^2. Bước 3: vì μ≪\mu\ll Lebesgue, φ\varphi khả vi hầu khắp nơi theo μ\mu nhờ định lý Alexandrov, nên γ\gamma tập trung trên đồ thị {(x,∇φ(x))}\{(x,\nabla\varphi(x))\}, tức γ=(id,∇φ)#μ\gamma=(\mathrm{id},\nabla\varphi)_{\#}\mu. Điều này cho ra một ánh xạ tối ưu tất định T=∇φT=\nabla\varphi, nên nó cũng giải bài toán Monge, và bất kỳ ánh xạ tối ưu nào khác đều phải trùng với nó hầu khắp nơi theo μ\mu nhờ tính lồi chặt của chi phí.

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