Mi is...a Monge–Kantorovics probléma?

A Monge–Kantorovics probléma

Az előző évtizedben két olyan matematikust is Fields-éremmel díjaztak (Cédric Villani 2010, Alessio Figalli 2018), akiknek munkájában az optimális transzport probléma jelentős szerepet játszott. A probléma születését Gaspard Monge 1781-ben publikált [4] művéhez, (egyik) újászületését pedig Leonyid Vitaljevics Kantorovics 1942-es [3] dolgozatához kötik.

Ebben a rövid írásban megpróbálom bemutatni a transzport probléma Monge- és Kantorovics-féle megfogalmazásait. A probléma történetéről, magáról a problémáról, és annak alkalmazásairól az érdeklődő olvasó többet is megtudhat Cédric Villani [7,8] és Filippo Santambrogio könyveiből [6].

1. A transzport probléma Monge-féle megfogalmazása

Gaspard Monge (1746–1818) hatalmas életművének csak egy apró szeletét képezik az optimális transzporttal kapcsolatos eredmények. Őt tekintik többek közt az ábrázoló geometria megteremtőjének, a differenciálgeometria egyik atyjának, de részt vett a méterrendszer kidolgozásában, sőt végzett fizikai és kémiai kutatásokat is. Tudományos eredményeit a hadviselésben is kamatoztatta, őt bízták meg annak megtervezésével, hogy hogyan érdemes ágyúkat elhelyezni egy erődítményben, később könyvet is írt az ágyúkészítés tudományáról [5]. Ide kívánkozik egy megjegyzés a Monge–Kantorovics probléma másik érintettjéről. Leningrád ostromakor a befagyott Ladoga-tó kiemelt stratégiai fontosságú volt a Vörös Hadsereg számára, ugyanis azon keresztül vezetett az étel és muníció szállítására alkalmas út. Kantorovics feladata volt, hogy kiszámolja a kocsik optimális távolságát és terhelhetőségét a jég vastagsága és a hőmérséklet függvényében [2].

Visszatérve Monge tudományos munkásságára: az optimális transzport probléma motivációját is egy meglehetősen egyszerű (illetve egyszerűnek hangzó) kérdés szolgáltatta. Nagyon elnagyoltan megfogalmazva: ha adott egy halom föld, és egy azzal megegyező térfogatú gödör, akkor hogyan tervezük meg a gödör feltöltését, ha azt a lehető legkevesebb munkával szeretnénk kivitelezni?

MK 1

A problémát Monge geometriai módszerekkel próbálta megfogni: azt vizsgálta, hogy a tömeget milyen pályák (görbék) mentén kell mozgatni. Mielőtt kísérletet tennénk a feladat formalizálására, nézzünk meg egy hasonló, de ránézésre legalábbis jóval egyszerűbb, kérdést. Tegyük fel, hogy van egy teljes páros gráfunk $k$ elemű csúcsosztályokkal (jelölje ezeket $X=\{x_1,\dots,x_k\}$ és $Y=\{y_1,\dots,y_k\}$ ). Tegyük fel továbbá, hogy adott egy $c\colon X\times Y\to\mathbb{R}$ költségfüggvény. Gondoljunk erre úgy, hogy $c(x_i,y_j)$ nem más, mint az $x_i$ pont $y_j$ -vel való párosításának költsége. Kérdés: az összes teljes párosítás közül melyik a minimális összköltségű? Világos, hogy minden teljes párosítás megadható egy $T\colon X\to Y$ bijekcióval, a $T$ párosítás összköltsége pedig nem más, mint $\sum_{i=1}^k c(x_i,T(x_i))$ . Tehát keressük azt a $T$ leképezést, ami ezt az összeget minimalizálja. Létezik ilyen párosítás, hiszen egy véges számhalmaz legkisebb elemét keressük.

A párosítási feladat semmivel sem lesz bonyolultabb, ha átfogalmazzuk szállítási feladattá: minden $x_i$ raktárnak van $\frac{1}{k}$ súlyú kiszállítandó rakománya, mindegyik $y_j$ bolt éppen $\frac{1}{k}$ súlyú rakományra adott le rendelést, a $c(x_i,y_j)$ mennyiség pedig az egyszerűség kedvért legyen most az $x_i$ raktár és $y_j$ bolt távolsága. Ekkor a szállítás során elvégzett munka nem más, mint $\sum_{i=1}^k c(x_i,T(x_i))\cdot\frac{1}{k}$ . Az azonban komoly nehezítés lenne, ha az egységnyi súlyt nem egyforma darabokra vágnánk szét mindkét oldalon, hanem különböző $m(x_1),\dots,m(x_k)$ és $n(y_1),\dots,n(y_k)$ darabokra. Egy $T\colon X\to Y$ bijekció ebben az esetben csak akkor adna meg jó szállítást, ha a $T(x_i)=y_j$ egyenlőség maga után vonná, hogy $m(x_i)=n(y_j)$ , vagy másképpen felírva

$\displaystyle m(T^{-1}(y_j))=n(y_j)$ minden $\displaystyle ~y_j\in\{y_1,\dots,y_k\}~$ esetén $\displaystyle .$

(1)

Egy ilyen $T$ szállítás költsége az előzőek mintájára

$\displaystyle C(T):=\sum_{i=1}^k c(x_i,T(x_i))\cdot m(x_i).$

(2)

Mivel véges sok ponttal dolgoztunk, és így csak véges sok jó $T$ leképezés lehet, ezért az

$\displaystyle \inf_{m\circ T^{-1}=n} \sum_{i=1}^k c(x_i,T(x_i))\cdot m(x_i)$

(3)

infimum valójában egy minimum. Tehát ha van legalább egy jó szállítás, akkor van optimális is. Vegyük észre, hogy amit itt látunk, az Monge problémájának egy diszkretizált változata: a földkupac és a betemetendő gödör helyett két diszkrét tömegeloszlás van, és keressük azt a $T$ leképezést, ami az egyiket minimális költséggel transzportálja át a másikba. Már ezen a diszkrét eseten jól látszik két probléma

a) Nem feltétlenül van megoldása a Monge által kitűzött problémának, hiszen az alábbi ábrán

MK 2

az (1) feltétel egyetlen olyan leképezésre sem teljesülhet, ami a kék pontokat a piros pontokra képezi.

b) Ha van megoldás, nem feltétlenül egyértelmű.

MK 3

Mivel a piros és kék pontok közötti távolságok egyenlőek, és a mozgatni kívánt súlyok egyenletesen vannak szétosztva, ezért a szaggatott nyilak mentén két különböző optimális transzportot látunk.

Nézzük meg, hogy hogyan lehet felírni az általános problémát. A metrikus tér, amiben dolgozunk, az $n$ -dimenziós euklidészi tér a szokásos távolsággal, a költségfüggvény pedig egy nemnegatív értékű folytonos $c\colon \mathbb{R}^n\times\mathbb{R}^n\to\mathbb{R}$ függvény. A kupacnak és a gödörnek pedig egy-egy Borel valószínűségi mérték felel meg. (Legyen a kupac eloszlásának megfelelő mérték $\mu$ , a gödöré $\nu$ .) A transzport leképezésre vonatkozó (1) feltétel megfelelője az általános esetben az, hogy $T\colon \mathbb{R}^n\to\mathbb{R}^n$ egy olyan mérhető függvény kell legyen, amelyre $\mu(T^{-1}(A))=\nu(A)$ teljesül minden $A\subseteq \mathbb{R}^n$ Borel-halmaz esetén.

Ilyenkor azt mondjuk, hogy a $\nu$ mérték a $\mu$ -nek $T$ -szerinti előretoltja, jelölésben: $T_{\char93 }\mu=\nu$ .

MK 4

Ezek után már könnyű látni, hogy a (2) formula általános megfelelője nem más, mint

$\displaystyle C(T):= \int_{\mathbb{R}^n} c(x,T(x))~\operatorname{d}\mu(x).$

Szemben a fenti (3) diszkrét esettel itt semmilyen egyszerű gondolatmenet nem garantálja, hogy ha egyáltalán van transzport leképezés (azaz a $C$ funkcionál értelmezési tartománya nem üres), akkor az

$\displaystyle \inf_{T_{\char93 }\mu=\nu}C(T)$

infimum valójában egy minimum, tehát hogy a $C$ funkcionál felveszi a minimumát. Olyannyira nem garantálja ezt semmilyen egyszerű gondolatmenet, hogy több mint 200 évet kellett várni a következő szép eredményre: ha a $\mu$ mérték abszolút folytonos az $n$ -dimenziós Lebesgue-mértékre vonatkozóan, akkor létezik optimális transzport leképezés [1].

2. A transzport probléma Kantorovics-féle megfogalmazása

A Monge-probléma egyik nehézsége a „kompaktság hiányában” rejlik, azaz hogy ha adott is a $\mu$ -t $\nu$ -be mozgató transzport leképezéseknek egy $(T_n)_{n\in\mathbb{N}}$ sorozata, nem ismert olyan topológia, amely szerint $(T_n)_{n\in\mathbb{N}}$ -ből kiválasztható konvergens részsorozat. Több mint 150 évvel később Leonyid Kantorovicsnak, a lineáris programozás egyik szülőatyjának sikerült áthidalnia ezt a problémát. A felfedezés fontosságát és hasznosságát jól mutatja, hogy 1975-ben Tjalling Koopmansszal megosztva közgazdasági Nobel-díjjal tüntették ki az erőforrások optimális elosztásának elméletéhez való hozzájárulásáért.

A transzport probléma új, relaxált megfogalmazásánál kibővítette a $C$ funkcionál értelmezési tartományát, és nem csak transzport leképezéseket, hanem úgynevezett transzport terveket is megengedett. Nézzünk egy olyan példát, amit a Monge-féle megfogalmazás szerint nem lehet megoldani.

MK 5

Világos, hogy nincs olyan $T\colon \{A,B,C\}\to\{X,Y,Z\}$ leképezés, amelyik teljesíti az (1) feltételt. Ha meg volna engedve, hogy a kék körökön lévő súlyokat feldaraboljuk, és azokat különböző piros négyzetekbe szállítsuk, az jelentősen megkönnyíteni a dolgunkat. Az alábbi táblázat egy ilyen felosztást mutat.

	X	Y	Z
A	$\frac18$	$\frac18$	$\frac18$
B	0	$\dfrac38$	0
C	0	0	$\frac{2}{8}$

Ha csak egy sort nézünk, azt látjuk, hogy az adott kék körön lévő súlyt hogyan daraboljuk fel, és melyik darabot melyik piros négyzetbe küldjük. Ha csak egy oszlopot nézünk, azt látjuk, hogy az adott piros négyzetbe melyik kék körből mennyi súly érkezik. Adott $c$ költségfüggvény mellett ennek a transzport tervnek a költsége

$\displaystyle c(A,X)\cdot\frac{1}{8}+c(A,Y)\cdot\frac{1}{8}+c(A,Z)\cdot\frac{1}{8}+c(B,Y)\cdot\frac{3}{8}+c(C,Z)\cdot\frac{2}{8}.$

A táblázatra kicsit másképp ránézve egy valószínűségi eloszlást látunk az $\{A,B,C\}\times\{X,Y,Z\}$ halmazon, amelynek egyik peremeloszlása épp a kék eloszlás, a másik pedig a piros eloszlás. Általában persze ilyen eloszlásból nem csak egy van, a fenti szállítási feladatot is sokféleképp meg lehet oldani. A feladat a legkisebb költségű ilyan transzport terv megtalálása.

Nézzük hogyan írható át a Kantorovics-féle megfogalmazás az általános esetre. Legyen $\mu$ és $\nu$ két Borel valószínűségi mérték $\mathbb{R}^n$ -en, az ezen mértékekhez tartozó transzport tervek halmazát jelölje $C(\mu,\nu)$ . Ezek tehát azok a $\pi$ mértékek a szorzat téren, amelyeknek marginálisai $\mu$ és $\nu$

$\displaystyle \pi(A\times X)=\mu(A)\qquad\pi(X\times A)=\nu(A).$

Fontos megjegyezni, hogy a $C(\mu,\nu)$ halmaz sosem üres, hiszen $\mu$ és $\nu$ szorzatmértéke benne van. Egy $\pi\in C(\mu,\nu)$ transzport terv költsége

$\displaystyle C(\pi)=\int_{X\times X}c(x,y)~\pi(dx,dy),$

a feladatunk pedig a $C\colon C(\mu,\nu)\to\mathbb{R}$ funkcionál minimalizálása. Azaz keressük azt a $\widehat{\pi}$ transzport leképezést, amelyre

$\displaystyle C(\widehat{\pi})=\min_{\pi\in C(\mu,\nu)}C(\pi).$

Szemben a Monge-féle megfogalmazással, ez a minimalizálási feladat mindig megoldható. (Legalábbis abban a speciális esetben, amit itt tárgyalunk, tehát amikor az alaptér $\mathbb{R}^n$ , a költségfüggvény pedig egy folytonos nemnegatív függvény.) Ennek az az oka, hogy a transzport tervek tere sokkal jobb tulajdonságokkal rendelkezik, mint a transzport leképezéseké.

Nagyon vázlatosan a következőről van szó: az egyszerűség kedvéért tegyük fel, hogy van legalább egy $\pi$ , amelyre $C(\pi)$ nem végtelen. Ekkor az

$\displaystyle m:=\inf_{\pi\in C(\mu,\nu)}C(\pi)$

infimum egy nemnegatív valós szám, így van olyan $C(\mu,\nu)$ -ben haladó $(\pi_n)_{n\in\mathbb{N}}$ sorozat, amelyre $C(\pi_n)\to m.$ Azt kell megmutatunk, hogy maga a $(\pi_n)_{n\in\mathbb{N}}$ sorozat valamilyen értelemben konvergál egy $C(\mu,\nu)$ -beli elemhez.

Ehhez szükségünk van a következő fogalomra: valószínűségi mértékek egy $\mathcal{M}$ mértékcsaládját feszesnek nevezzük, ha minden $\varepsilon>0$ számhoz van olyan $K_{\varepsilon}$ kompakt halmaz, hogy minden $\eta\in\mathcal{M}$ esetén $\eta(K_{\varepsilon})\geq 1-\varepsilon$ .

Megmutatjuk, hogy a $(\pi_n)_{n\in\mathbb{N}}$ sorozat (mint mértékcsalád) feszes. Tudjuk, hogy a $\pi_n$ mértékek marginálisai $\mu$ és $\nu$ . Azt könnyű belátni, hogy minden $\varepsilon>0$ -hoz léteznek olyan $K_{\mu,\varepsilon}$ és $K_{\nu,\varepsilon}$ kompakt halmazok, amelyekre $\mu(K_{\mu,\varepsilon}) \geq 1-\frac{\varepsilon}{2}$ és $\nu(K_{\nu,\varepsilon})\geq 1-\frac{\varepsilon}{2}$ . Az ezekből képzett $K_{\varepsilon}:=K_{\mu,\varepsilon}\times K_{\nu,\varepsilon}$ kompakt halmazok pedig garantálják $(\pi_n)_{n\in\mathbb{N}}$ feszességét. Ezen a ponton használhatjuk Prokhorov híres tételét, nevezetesen hogy a feszesség miatt a sorozatból kiválasztható gyengén konvergens részsorozat. (Emlékeztetünk, hogy $\eta_n$ gyengén konvergál $\eta$ -hoz, ha minden folytonos korlátos függvény $\eta_n$ szerinti integráljaiból kapott sorozat konvergál a függvény $\eta$ szerinti integráljához.) Jelölje a konvergens részsorozat limeszét $\widehat{\pi}$ . Könnyen igazolható, hogy $\widehat{\pi}\in C(\mu,\nu)$ . A bizonyítás befejezéséhez elég megmutatni, hogy

$\displaystyle \liminf_{n\to\infty}C(\pi_n)\geq C(\widehat{\pi}).$

Ha a $c$ költségfüggvény korlátos és folytonos, akkor ez a gyenge konvergencia definíciójából és a $\widehat{\pi}$ választásából azonnal következik, ha nem, akkor egy standard határátmenetet használó okoskodással vissza lehet vezetni a problémát a folytonos korlátos esetre.

Ezzel vázlatosan megmutattuk, hogy az általunk vizsgált esetben a Kantorovich-féle probléma megoldható. A fenti okoskodás lépései akkor is működtek volna, ha $\mathbb{R}^n$ helyett egy szeparábilis teljes metrikus teret tekintettünk volna, a $c$ költségfüggvényről pedig alulról félig folytonosságot tettünk volna fel.

A cikket egy egyszerű észrevétellel zárjuk, amely kapcsolatot teremt a probléma két megfogalmazása között. Tegyük fel először, hogy $T$ egy transzport leképezés, azaz $T_\char93 \mu=\nu$ , és tekintsük az $(\operatorname{Id},T)(x,y):=(x,T(y))$ hozzárendeléssel megadott $(\operatorname{Id},T)\colon \mathbb{R}^n\times\mathbb{R}^n\to\mathbb{R}$ függvényt.

Ekkor $\pi:=(\operatorname{Id},T)_\char93 \mu\in C(\mu,\nu)$ és $C(\pi)=C(T)$ , és az $(\operatorname{Id},T)_\char93 \mu$ mérték a $T$ grafikonjára van koncentrálva. Megfordítva, ha $\pi\in C(\mu,\nu)$ egy olyan mérték, amely egy függvény grafikonjára van koncentrálva, akkor van olyan $T$ transzport leképezés, amelyre $(\operatorname{Id},T)_\char93 \mu=\pi$ .

A cikk az ITM és az NKFIH ÚNKP-19-4-BGE-1 és PD128374 kódszámú projektjeinek, valamint az MTA Bolyai János Kutatási Ösztöndíjának támogatásával készült.

Irodalomjegyzék

: [1] L. C. Evans, W. Gangbo, Differential Equations Methods for the Monge–Kantorovich Mass Transfer Problem, Memoirs of the American Mathematical Society No. 137, 1999.; [2] B. Gustafsson, Scientific Computing: A Historical Perspective, Texts in Computational Science and Engineering, Springer, 2018.; [3] L. Kantorovich, On translation of mass, C.R. Doklady. Acad Sci USSR. 1942;37 199–201.; [4] G. Monge, Mémoire sur la théorie des déblais et des remblais. De l’Imprimerie Royale; 1781.; [5] G. Monge, Description de l'art de fabriquer des canons, Éditeur: Imprimerie du comité de salut publique, Paris, Publication: an 2 de la république francaise (1793–1794).; [6] F. Santambrogio, Optimal transport for applied mathematicians. Birkäuser Springer, Basel, 2015.; [7] C. Villani, Topics in Optimal Transportation. American Mathematical Society, 2003.; [8] C. Villani, Optimal Transport: Old and New, Volume 338. Springer Verlag.