최적수송

최적설계 수치해석 통계 마지막 수정: 2026-08-18 04:12:20

1. 개요[편집]

최적수송 Optimal Transport
물음	모래더미 μ 를 구덩이 ν 로 가장 싸게 옮기려면?
몽주(1781)	수송 사상 T 를 찾는다 — 비볼록, 존재 보장 없음
칸토로비치(1942)	수송 계획 π 를 찾는다 — 선형계획, 해 존재
쌍대	φ(x) + ψ(y) ≤ c(x,y) 아래 ∫φdμ + ∫ψdν 최대화
브레니에 정리	c = ‖x−y‖²/2 면 최적 사상은 볼록함수의 기울기
이산 버전	수송 문제 = LP, 균등 주변분포면 할당 문제
거리	와서스타인 거리

최적수송은 한 측도를 다른 측도로 옮기는 방법 중 총 수송비가 최소인 것을 찾는 문제다. 몽주가 1781년 흙더미를 성벽 자리로 옮기는 토목 문제(“déblais et remblais”)로 제기한 이래, 240년 동안 해석학·확률론·PDE·경제학·기계학습이 각자의 이유로 같은 문제에 몰려든 희귀한 사례다.

문제의 재료는 세 개뿐이다. 출발 측도 $\mu$ , 도착 측도 $\nu$ (둘 다 총질량 1이라 하자), 그리고 한 단위를 $x$ 에서 $y$ 로 옮기는 비용 $c(x,y)$ . 이 셋만으로 최적수송이 정의되고, 그 최적값이 $\mu$ 와 $\nu$ 사이의 거리로 승격되면 와서스타인 거리가 된다. 이 문서는 문제와 그 구조를, 저 문서는 거리로서의 성질을 다룬다.

핵심 줄거리는 한 문장이다. 몽주의 원래 형태는 아름답지만 풀리지 않고, 칸토로비치의 완화는 못생겼지만 선형계획이라 풀리며, 놀랍게도 2차 비용에서는 완화한 답이 원래 형태의 답과 일치한다.¹

2. 몽주 문제 — 사상을 찾으면 왜 안 되는가[편집]

몽주의 형태는 각 흙알갱이가 갈 곳을 딱 하나로 지정하는 수송 사상(transport map) $T$ 를 찾는 것이다.

\inf_{T_\#\mu = \nu} \int_{\mathcal{X}} c\bigl(x, T(x)\bigr)\, d\mu(x)

여기서 $T_\#\mu = \nu$ 는 밀어내기(pushforward) 조건 — 모든 가측집합 $B$ 에 대해 $\mu(T^{-1}(B)) = \nu(B)$ — 이며, ” $T$ 로 옮기고 나면 정확히 $\nu$ 가 된다”는 뜻이다.

이 형태의 문제는 두 가지다.

해가 아예 없을 수 있다. $\mu = \delta_0$ , $\nu = \frac12\delta_{-1} + \frac12\delta_{1}$ 을 보자. $T$ 는 함수이므로 원점의 질량 전부를 한 점으로 보낼 수밖에 없고, 그러면 $\nu$ 의 절반만 채워진다. 사상은 질량을 쪼갤 수 없다. 이산 측도끼리, 혹은 원자를 가진 측도가 끼면 즉시 터진다.
제약 집합이 볼록이 아니다. $T_\#\mu = \nu$ 를 만족하는 사상들의 모임은 볼록집합이 아니라서 변분법의 표준 무기(직접법·볼록해석)가 하나도 안 통한다. 칸토로비치가 등장하기까지 160년 가까이 존재성조차 손을 못 댔던 이유다.

3. 칸토로비치 완화 — 계획으로 바꾸면 선형계획[편집]

칸토로비치(1942)의 처방은 “질량을 쪼갤 수 있게 해 주자”는 것이다. 사상 대신 수송 계획(transport plan), 즉 주변분포가 $\mu,\nu$ 인 결합측도 $\pi$ 를 찾는다.

\mathrm{OT}(\mu,\nu) \;=\; \min_{\pi \in \Pi(\mu,\nu)} \int c(x,y)\, d\pi(x,y), \qquad \Pi(\mu,\nu) = \{\pi \ge 0:\ \pi(\cdot\times\mathcal{Y}) = \mu,\ \pi(\mathcal{X}\times\cdot) = \nu\}

$\pi(A\times B)$ 는 ” $A$ 에서 퍼서 $B$ 에 붓는 양”이다. 사상 $T$ 는 $\pi = (\mathrm{id},T)_\#\mu$ 로 계획에 포함되므로 완화가 맞고, 아까 터진 예제도 이제 $\pi = \frac12\delta_{(0,-1)} + \frac12\delta_{(0,1)}$ 로 멀쩡히 풀린다.

바뀐 것은 문제의 종류다. 목적함수가 $\pi$ 에 대해 선형이고 제약도 선형이라 이건 무한차원 선형계획이다. 게다가 $\Pi(\mu,\nu)$ 는 항상 공집합이 아니고( $\pi = \mu\otimes\nu$ 가 늘 있다), 볼록이며, 약*위상에서 콤팩트다. $c$ 가 하반연속이고 아래로 유계이면 직접법이 그대로 먹혀 최소해가 존재한다. “볼록하지 않은 문제를 볼록 완화해 놓고 보니 완화가 정확하더라”는 최적화의 흔한 서사인데, 여기서는 그 정확성이 정리로 증명된다는 점이 특별하다.

4. 쌍대 문제 — 이삿짐센터 사장의 관점[편집]

무한차원이든 유한차원이든 LP의 쌍대를 취하는 것은 국룰이다. 칸토로비치 쌍대는 이렇게 생겼다.

\mathrm{OT}(\mu,\nu) = \sup_{\varphi(x) + \psi(y) \le c(x,y)} \left\{ \int \varphi\, d\mu + \int \psi\, d\nu \right\}

경제학적 독법이 유명하다. 내가 직접 옮기는 대신 업자를 부른다고 하자. 업자는 $x$ 에서 짐을 실을 때 $\varphi(x)$ , $y$ 에 내릴 때 $\psi(y)$ 를 청구한다. 제약 $\varphi(x)+\psi(y)\le c(x,y)$ 는 “어떤 구간에서도 내가 직접 옮기는 것보다 비싸면 안 된다”는 경쟁 조건이고, 업자는 그 조건 아래 총 수입을 최대화한다. 강쌍대성은 그 최댓값이 정확히 최소 수송비라는 뜻이다.

여기서 결정적인 구조가 하나 나온다. $\psi$ 가 주어졌을 때 제약을 만족하는 가장 큰 $\varphi$ 는 자동으로 결정된다.

\varphi(x) = \psi^c(x) := \inf_{y}\ \bigl[\, c(x,y) - \psi(y) \,\bigr]

이 연산을 $c$ -변환이라 하고, 어떤 함수의 $c$ -변환으로 표현되는 함수를 $c$ -오목(c-concave)이라 한다. 최적 쌍대해 $(\varphi,\psi)$ 는 항상 $\varphi = \psi^c$ , $\psi = \varphi^c$ 를 만족하도록 잡을 수 있으며, 이 최적해를 칸토로비치 퍼텐셜이라 부른다.² $c(x,y) = -\langle x,y\rangle$ 로 놓으면 $\psi^c = -(-\psi)^*$ 가 되어, 부호 규약만 빼면 $c$ -변환이 곧 르장드르-펜셸 변환이다 — 볼록해석의 켤레는 최적수송 쌍대의 특수 사례인 셈이다.

상보 여유(complementary slackness)도 그대로다. 최적 $\pi$ 의 지지집합 위에서는 부등식이 등식이 된다.

(x,y) \in \operatorname{supp}\pi \ \Longrightarrow\ \varphi(x) + \psi(y) = c(x,y)

여기서 최적 $\pi$ 의 지지집합이 $c$ -순환 단조(c-cyclically monotone)라는 성질이 따라온다 — 그 위의 점 $(x_1,y_1),\dots,(x_N,y_N)$ 을 아무렇게나 골라 목적지를 순환 치환해도 총비용이 줄어들지 않는다는 조건이다. 적절한 가정 아래 역도 성립해서, “짐 몇 개를 서로 바꿔 보내 더 싸지는 경우가 없다”는 조합적 조건이 곧 전역 최적성이 된다.

5. 브레니에 정리 — 2차 비용의 기적[편집]

이제 이 분야를 1980년대에 되살린 정리. 비용을 $c(x,y) = \tfrac12\|x-y\|^2$ 로 두자. 제곱을 전개하면

\tfrac12\|x-y\|^2 = \tfrac12\|x\|^2 + \tfrac12\|y\|^2 - \langle x,y\rangle

이고 앞의 두 항은 $\pi$ 의 주변분포로 결정되는 상수다. 따라서 수송비 최소화 = 상관 $\int\langle x,y\rangle d\pi$ 최대화이며, $c$ -오목성은 $u(x) := \tfrac12\|x\|^2 - \varphi(x)$ 가 볼록이라는 조건으로 번역된다.

브레니에 정리(1987/91). $\mu,\nu$ 가 2차 적률을 갖고 $\mu$ 가 르베그 측도에 절대연속이면, 2차 비용 최적수송 계획은 유일하고 그것은 사상 $T$ 로 유도되며, 그 사상은 어떤 볼록함수 $u$ 의 기울기다.

T = \nabla u, \qquad (\nabla u)_\#\mu = \nu

칸토로비치 완화가 원래 몽주 문제의 해를 준다는 것이 이 정리의 요점이고, 동시에 “볼록함수의 기울기로 밀어내는 사상”이 유일하다는 강력한 구조 정리이기도 하다. 1차원으로 내리면 볼록함수의 기울기 = 단조증가 함수이므로, 최적 사상은 그냥 누적분포함수를 맞춰 주는 단조 재배열이 된다. 와서스타인 거리의 1차원 닫힌 형태가 여기서 나온다.

$\mu = f\,dx$ , $\nu = g\,dy$ 로 밀도가 있으면 밀어내기 조건을 변수변환으로 쓸 수 있고, 그 결과가 몽주-암페르 방정식이다.

f(x) = g\bigl(\nabla u(x)\bigr)\, \det D^2 u(x)

$u$ 가 볼록이면 $D^2u \succeq 0$ 이라 이 완전비선형 방정식은 타원형이 되고, 최적수송은 경계 조건이 좀 특이한( $\nabla u(\Omega) = \Omega'$ , 이른바 제2 경계값 문제) 타원형 PDE 풀기가 된다. 카파렐리의 정칙성 이론이 이 위에서 전개되며, 수치적으로는 광각 유한차분·뉴턴법 계열이 쓰인다. 몽주-암페르 방정식 자체는 별도 주제라 여기서는 위치만 잡아 둔다.

6. 동적 형식 — 베나무-브레니에[편집]

지금까지는 “누가 어디로 가는가”만 봤지 “어떻게 가는가”는 안 봤다. 베나무와 브레니에(2000)는 2차 최적수송이 유체역학 문제와 정확히 같다는 것을 보였다.

W_2^2(\mu,\nu) \;=\; \inf_{\rho, v}\ \int_0^1\!\!\int_\Omega \rho\,\|v\|^2\, dx\, dt \quad\text{s.t.}\quad \partial_t \rho + \nabla\cdot(\rho v) = 0,\ \ \rho_0 = \mu,\ \rho_1 = \nu

즉 질량을 연속방정식에 따라 흘려보내되 운동에너지 총량을 최소화하는 흐름이 최적수송이고, 그 최적 흐름은 압력 없는 무점성 유동이라 입자들이 직선 등속으로 움직인다(변위 보간, $\rho_t = ((1-t)\mathrm{id} + tT)_\#\mu$ ).

수치적으로도 이 형태가 값을 한다. 원래 형태는 $(\rho,v)$ 에 대해 비볼록이지만, 운동량 $m = \rho v$ 로 바꾸면 목적함수가 $\int \|m\|^2/\rho$ 가 되어 $(\rho,m)$ 에 대해 결합 볼록이고 제약은 선형이다. 그래서 교대방향 승수법이나 증대 라그랑주로 바로 풀린다. 정적 문제를 시공간 문제로 차원을 하나 올려 볼록성을 얻는 거래인 셈. 이 관점에서 $W_2$ 는 확률측도 공간 위의 리만 거리처럼 행동하고, 확산 방정식이 엔트로피의 $W_2$ -기울기흐름이라는 오토(Otto)의 그림으로 이어진다.

7. 이산 문제 — 결국 수송 문제이자 할당 문제[편집]

실제로 계산할 때는 두 측도가 유한 개의 점질량이다. $\mu = \sum_i a_i\delta_{x_i}$ , $\nu = \sum_j b_j\delta_{y_j}$ 이면 문제는 그냥 유한 LP다.

\min_{P \ge 0}\ \langle C, P\rangle \quad\text{s.t.}\quad P\mathbf{1} = a,\ \ P^\top\mathbf{1} = b

이것이 운영과학의 고전인 수송 문제(transportation problem)이며, 제약행렬이 이분 그래프의 접속행렬이라 전체 단모듈성을 갖는다. 따라서 $a,b$ 가 정수면 꼭짓점이 전부 정수이고, LP를 풀면 정수해가 공짜로 나온다 — 정수 제약을 따로 걸 필요가 없다.

$n = m$ 이고 $a = b = \frac1n\mathbf{1}$ 인 특수한 경우가 특히 유명하다. 이때 실행가능 영역은 (스케일 $1/n$ 을 빼면) 이중 확률행렬 전체가 이루는 버코프 다면체이고, 버코프-폰 노이만 정리에 의해 그 꼭짓점은 정확히 순열행렬이다. 즉 균등 주변분포 최적수송의 최적해는 항상 일대일 매칭이고, 문제는 할당 문제로 환원된다. 여기서 헝가리안 알고리즘이 $O(n^3)$ 에 답을 준다.

방법	적용	대략적 비용
헝가리안 / JV	균등 주변분포, 일대일 매칭	$O(n^3)$
네트워크 심플렉스	일반 수송 문제	실무 표준, 대략 $O(n^3\log n)$ 급
범용 LP(내점법)	일반	희소성 못 살리면 손해
싱크혼(엔트로피 정규화)	근사, 미분 가능	반복당 $O(nm)$

$n$ 이 몇 만을 넘어가는 순간(이미지 히스토그램만 해도 그렇다) 정확해는 사실상 포기하고 엔트로피 정규화로 간다. 그 계열의 이야기 — 싱크혼-크노프 반복, $\varepsilon$ -스케일링, 싱크혼 발산, 미분 가능성 — 는 엔트로피 정규화 문서가 통째로 다루므로 여기서 반복하지 않는다. 이 문서에서 기억할 것은 정확한 최적수송은 조합 최적화 문제이고, 그래서 답이 극단적으로 희소하며 미분이 안 된다는 사실뿐이다.

8. 어디에 쓰이나[편집]

최적수송이 유행하게 된 이유는 “두 분포를 비교하되 겹치지 않아도 의미 있는 값이 나오고, 비교하면서 대응 관계까지 같이 나온다”는 두 가지다. 후자가 특히 실용적이다 — 거리만 주는 발산과 달리, 최적수송은 $\pi$ 라는 대응표를 덤으로 준다.

색 이전·톤 매칭. 두 영상의 픽셀 색 분포를 3차원 점구름으로 보고 한쪽을 다른 쪽으로 수송한다. 1차원 히스토그램 정합의 자연스러운 다차원 확장이며, 실무에서는 계산이 싼 슬라이스드 근사를 자주 쓴다.
도메인 적응. 소스 도메인의 특징 분포를 타깃 도메인으로 수송하고 라벨을 그 대응을 따라 옮긴다. 수송 계획이 곧 소스-타깃 샘플 대응표라 라벨 전파가 자연스럽다.
메시 이동(r-adaptivity). 격자점을 새로 만들지 않고 옮기기만 해서 해상도를 재배분할 때, “목표 밀도 함수로 균등 격자를 수송”하는 문제로 정식화하면 몽주-암페르 방정식 하나를 풀면 된다. 격자가 뒤집히지 않는다는 것(볼록함수의 기울기는 단조 사상이라 야코비안 행렬식이 음수가 될 수 없다)이 이 접근의 결정적 장점이라 기상 모델과 대기 시뮬레이션에서 채택됐다.
유동장 재구성·입자 추적. 두 시각의 입자 분포를 잇는 대응을 최적수송으로 추정한다. PIV류에서 상관 기반 정합이 실패하는 큰 변위 영역의 대안으로 연구된다.
기계학습 전반. 생성모형의 손실, 분포 정렬, 라벨 없는 정합, 군집화 확장. 이쪽은 와서스타인 거리 문서에 모아 두었다.

9. 함정[편집]

차원의 저주는 그대로 있다. 표본 $n$ 개로 추정한 최적수송비는 차원 $d$ 에서 $n^{-1/d}$ 정도로만 수렴한다. 고차원에서 “표본으로 추정한 와서스타인 거리”를 그대로 믿으면 안 되는 이유이며, 슬라이스드 근사나 엔트로피 정규화가 통계적으로도 도움이 되는 지점이다.
비용을 잘못 고르면 전부 무의미하다. 최적수송은 $c$ 를 통해서만 기하를 본다. 픽셀 인덱스 차이를 비용으로 쓰면 “픽셀 좌표의 기하”를 재는 것이지 “영상의 의미”를 재는 게 아니다.
1차 비용( $c=\|x-y\|$ )은 사상이 유일하지 않다. 일직선상에 놓인 질량은 어떻게 이어 붙여도 총비용이 같다. 이 경우 최적수송은 벡터장 문제(베크만 문제)로 다시 쓰는 편이 낫고, 브레니에 정리도 그대로는 적용되지 않는다.³
질량이 안 맞으면 정의부터 안 된다. 총량이 다른 두 측도는 $\Pi(\mu,\nu)$ 가 공집합이다. 주변분포 제약을 KL 벌점 등으로 완화한 불균형 최적수송이 이 지점의 표준 처방이다.⁴

10. 관련 문서[편집]

칸토로비치는 이 완화를 2차대전 중 소련의 자원 배분 문제를 풀다가 얻었고, 사실상 선형계획법을 단치히보다 먼저 발견한 셈이 됐다. 정작 본인은 최적수송을 “수송 문제의 일반화” 정도로 봤고, 이것이 몽주의 200년 묵은 문제의 정답이라는 인식은 한참 뒤에 자리잡았다. 1975년 노벨경제학상은 자원의 최적 배분 이론에 대한 것이었지, “저 무한차원 LP가 예쁘다”는 이유가 아니었다. ↩
$c$ -오목성은 볼록해석의 오목성을 비용함수 $c$ 에 맞춰 일반화한 것이다. 실제로 $c$ -변환을 두 번 하면 $\psi^{cc} \ge \psi$ 이고 $\psi^{ccc} = \psi^c$ 라, 르장드르-펜셸 변환의 $f^{**}\le f$ , $f^{***}=f^*$ 구조가 그대로 복사된다. 볼록해석을 배운 사람이 최적수송 쌍대를 처음 볼 때 “어디서 본 것 같은데” 싶은 게 착각이 아닌 이유. ↩
몽주가 원래 다룬 비용이 하필 이 1차 비용이었다. 즉 몽주는 자기 문제 중 유난히 퇴화가 심한 버전을 골라 놓고 200년을 기다린 셈이고, 이론이 깔끔하게 풀린 건 그가 다루지 않은 2차 비용 쪽이었다. 수학사에서 흔한 종류의 아이러니. ↩
불균형 최적수송은 “질량을 버리거나 만들어 내는 데도 값을 매긴다”는 발상이다. 세포 계보 추적처럼 개체 수가 실제로 변하는 데이터에서는 이쪽이 오히려 물리적으로 옳다. 그리고 이 완화를 하면 싱크혼 꼴 반복이 그대로 살아남는다는 것이 실무적으로 제일 반가운 부분. ↩