Toriskia 's Blog

13 篇文章 · 12 个标签 · 6 个友链

← 返回文章列表

2026.03.30

Kantorovich-Rubinstein 对偶性

优化

一、Lagrange Duality#

1. 原问题定义#

min⁡xf0(x)s.t.{fi(x)≤0,i=1,…,mhj(x)=0,j=1,…,p\min_{x} f_0(x) \quad \text{s.t.} \quad \begin{cases} f_i(x) \leq 0, & i = 1, \ldots, m \\ h_j(x) = 0, & j = 1, \ldots, p \end{cases}

2. Lagrangian 函数#

L(x,λ,ν)=f0(x)+∑i=1mλifi(x)+∑j=1pνjhj(x)L(x, \lambda, \nu) = f_0(x) + \sum_{i=1}^m \lambda_i f_i(x) + \sum_{j=1}^p \nu_j h_j(x)

3. 对偶问题#

定义对偶函数为：

g(λ,ν)=inf⁡xL(x,λ,ν)g(\lambda, \nu) = \inf_{x} L(x, \lambda, \nu)

这个函数有两个性质：

  1. g(λ,ν)g(\lambda, \nu) 是一个凹函数。

    给定一个 xx，L(x,λ,ν)L(x, \lambda, \nu) 是 λ\lambda 和 ν\nu 的仿射（线性）函数，而 g(λ,ν)g(\lambda, \nu) 是一系列仿射函数的下包络线，因此 gg 是一个凹函数。

  2. 对于任何 λ≥0\lambda \geq 0 和任意 ν\nu，有 g(λ,ν)≤p∗g(\lambda, \nu) \leq p^*，其中 p∗p^* 是原问题的最优值。

    g(λ,ν)≤L(x∗,λ,ν)≤f0(x∗)=p∗g(\lambda, \nu) \leq L(x^*, \lambda, \nu) \leq f_0(x^*) = p^*

由此可见 g(λ,ν) g(\lambda, \nu) 是原问题的一个下界。定义对偶问题为：

max⁡λ,νg(λ,ν)s.t.λ≥0\max_{\lambda, \nu} g(\lambda, \nu) \quad \text{s.t.} \quad \lambda \geq 0

这是一个凸优化问题。

对于最优解 (λ∗,ν∗)(\lambda^*, \nu^*)，有 g(λ∗,ν∗)≤p∗g(\lambda^*, \nu^*) \leq p^*，这被称为弱对偶性。如果取等号成立则称为强对偶性。

强对偶性的一个充分不必要条件是 Slater 条件：如果原问题是一个凸优化问题，并且存在一个严格可行点（即满足 fi(x)<0f_i(x) < 0 和 hj(x)=0h_j(x) = 0 的点），则强对偶性成立。

在强对偶性成立的情况下，可以通过求解对偶问题来得到原问题的最优值。

二、KKT 条件#

KKT 条件是原问题的必要条件。在 LL 对 xx 可微的前提下，对于一个可行点 x∗x^*，如果存在 λ∗≥0\lambda^* \geq 0 和 ν∗\nu^* 满足以下条件：

  1. 原始可行性 fi(x∗)≤0,hj(x∗)=0f_i(x^*) \leq 0, \quad h_j(x^*) = 0
  2. 对偶可行性 λi∗≥0,∀i\lambda_i^* \geq 0, \quad \forall i
  3. 互补松弛 λi∗fi(x∗)=0,∀i\lambda_i^* f_i(x^*) = 0, \quad \forall i
  4. 梯度条件 ∇L(x∗,λ∗,ν∗)=∇f0(x∗)+∑i=1mλi∗∇fi(x∗)+∑j=1pνj∗∇hj(x∗)=0\nabla L(x^*, \lambda^*, \nu^*) = \nabla f_0(x^*) + \sum_{i=1}^m \lambda_i^* \nabla f_i(x^*) + \sum_{j=1}^p \nu_j^* \nabla h_j(x^*) = 0

则称 (x∗,λ∗,ν∗)(x^*, \lambda^*, \nu^*) 满足 KKT 条件。

其中，互补松弛条件表明对于每个不等式约束，要么 λi∗=0\lambda_i^* = 0（约束不活跃），要么 fi(x∗)=0f_i(x^*) = 0（约束活跃）。

可以这样理解：

f0(x∗)=g(λ∗,ν∗)=inf⁡x{f0(x)+∑i=1mλi∗fi(x)+∑j=1pνj∗hj(x)}≤f0(x∗)+∑i=1mλi∗fi(x∗)+∑j=1pνj∗hj(x∗)≤f0(x∗)\begin{aligned} f_0(x^*) &= g(\lambda^*, \nu^*) \\ &= \inf_{x} \left\{f_0(x) + \sum_{i=1}^m \lambda_i^* f_i(x) + \sum_{j=1}^p \nu_j^* h_j(x)\right\} \\ &\leq f_0(x^*) + \sum_{i=1}^m \lambda_i^* f_i(x^*) + \sum_{j=1}^p \nu_j^* h_j(x^*) \\ &\leq f_0(x^*) \end{aligned}

不等号必须取等号，因此立刻得到互补松弛条件 λi∗fi(x∗)=0\lambda_i^* f_i(x^*) = 0。

三、Kantorovich-Rubinstein 对偶性#

1. 对偶形式#

在 Wasserstein GAN 中，生成器的目标是最小化 Wasserstein 距离：

W(P,Q)=inf⁡γ∈Π(P,Q)E(x,y)∼γ[∥x−y∥]=inf⁡γ∈Π(P,Q)∑x,yγ(x,y)c(x,y)W(P,Q)=\inf_{\gamma\in\Pi(P,Q)} \mathbb E_{(x,y)\sim\gamma}\big[\|x-y\|\big] = \inf_{\gamma\in\Pi(P,Q)} \sum_{x, y} \gamma(x, y) c(x, y)

约束条件为：

γ(x,y)≥0,∑yγ(x,y)=P(x),∑xγ(x,y)=Q(y)\gamma(x, y) \geq 0, \quad \sum_{y} \gamma(x, y) = P(x), \quad \sum_{x} \gamma(x, y) = Q(y)

这是一个线性规划问题，所有变量就是不同 x,yx, y 对应的 γ(x,y)\gamma(x, y)，（不严谨的推导）套用上述 Lagrange Duality：

L(γ,λ,ν1,ν2)=∑x,yγ(x,y)c(x,y)+∑x,yλ(x,y)(−γ(x,y))+∑xν1(x)(P(x)−∑yγ(x,y))+∑yν2(y)(Q(y)−∑xγ(x,y))=∑x,yγ(x,y)[c(x,y)−λ(x,y)−ν1(x)−ν2(y)]+∑xν1(x)P(x)+∑yν2(y)Q(y)\begin{aligned} L(\gamma, \lambda, \nu_1, \nu_2) &= \sum_{x, y} \gamma(x, y) c(x, y) + \sum_{x, y} \lambda(x, y) (-\gamma(x, y)) + \sum_{x} \nu_1(x) \left(P(x) - \sum_{y} \gamma(x, y)\right) + \sum_{y} \nu_2(y) \left(Q(y) - \sum_{x} \gamma(x, y)\right) \\ &= \sum_{x, y} \gamma(x, y) \left[c(x, y) - \lambda(x, y) - \nu_1(x) - \nu_2(y)\right] + \sum_{x} \nu_1(x) P(x) + \sum_{y} \nu_2(y) Q(y) \end{aligned}

可以证明强对偶性满足。KKT 条件告诉我们：

{γ(x,y)≥0,∑yγ(x,y)=P(x),∑xγ(x,y)=Q(y)λ(x,y)≥0λ(x,y)γ(x,y)=0c(x,y)−λ(x,y)−ν1(x)−ν2(y)=0\begin{cases} \gamma(x, y) \geq 0, \quad \sum_{y} \gamma(x, y) = P(x), \quad \sum_{x} \gamma(x, y) = Q(y) \\ \lambda(x, y) \geq 0 \\ \lambda(x, y) \gamma(x, y) = 0 \\ c(x, y) - \lambda(x, y) - \nu_1(x) - \nu_2(y) = 0 \end{cases}

对偶形式为：

max⁡ν1,ν2∑xν1(x)P(x)+∑yν2(y)Q(y)s.t.ν1(x)+ν2(y)≤c(x,y)\max_{\nu_1, \nu_2} \sum_{x} \nu_1(x) P(x) + \sum_{y} \nu_2(y) Q(y) \quad \text{s.t.} \quad \nu_1(x) + \nu_2(y) \leq c(x, y)

2. 一个函数能给出下界#

假设 ff 是一个 1-Lipschitz 函数，即：

∣f(x)−f(y)∣≤c(x,y)|f(x) - f(y)| \leq c(x, y)

令：

ν1(x)=f(x),ν2(y)=−f(y)\nu_1(x) = f(x), \quad \nu_2(y) = -f(y)

显然满足 ν1(x)+ν2(y)=f(x)−f(y)≤c(x,y)\nu_1(x) + \nu_2(y) = f(x) - f(y) \leq c(x, y)，因此 ff 可以给出一个下界：

sup⁡∥f∥L≤1[∑xf(x)P(x)−∑yf(y)Q(y)]≤W(P,Q)\sup_{\|f\|_L \leq 1}\left[\sum_{x} f(x) P(x) - \sum_{y} f(y) Q(y)\right] \leq W(P, Q)

3. 最优解可以压缩成一个函数#

固定 ν2\nu_2：

ν1(x)≤inf⁡y[c(x,y)−ν2(y)]\nu_1(x) \leq \inf_{y} \left[c(x, y) - \nu_2(y)\right]

记 f(x)=RHSf(x) = \text{RHS}，我们先证明，如果 cc 是一个度量：

c(x,y)=d(x,y)c(x, y) = d(x, y)

那么 ff 是 1-Lipschitz 的：

首先根据三角不等式：

d(x,z)−ν2(z)≤d(x,y)+d(y,z)−ν2(z)d(x, z) - \nu_2(z) \leq d(x, y) + d(y, z) - \nu_2(z)

两边同时对 zz 取 inf：

inf⁡z[d(x,z)−ν2(z)]≤d(x,y)+inf⁡z[d(y,z)−ν2(z)]\inf_{z} \left[d(x, z) - \nu_2(z)\right] \leq d(x, y) + \inf_{z} \left[d(y, z) - \nu_2(z)\right]

因此

f(x)≤d(x,y)+f(y)f(x) \leq d(x, y) + f(y)

同理 f(y)≤d(x,y)+f(x)f(y) \leq d(x, y) + f(x)，所以 ∣f(x)−f(y)∣≤d(x,y)|f(x) - f(y)| \leq d(x, y)。

一方面：

ν1(x)≤f(x)\nu_1(x) \leq f(x)

另一方面：

f(x)=inf⁡y[c(x,y)−ν2(y)]≤c(x,x)−ν2(x),⇒ν2(y)≤−f(y)f(x) = \inf_{y} \left[c(x, y) - \nu_2(y)\right] \leq c(x, x) - \nu_2(x), \quad \Rightarrow \quad \nu_2(y) \leq -f(y)

结合起来，存在一个 1-Lipschitz 函数 f(x)f(x) 使得：

W(P,Q)=max⁡ν1,ν2∑xν1(x)P(x)+∑yν2(y)Q(y)≤∑xf(x)P(x)−∑yf(y)Q(y)W(P, Q) = \max_{\nu_1, \nu_2} \sum_{x} \nu_1(x) P(x) + \sum_{y} \nu_2(y) Q(y) \leq \sum_{x} f(x) P(x) - \sum_{y} f(y) Q(y)

4. 结论#

以上结果说明

  1. 只要 ff 是 1-Lipschitz 的，ν1=f,ν2=−f\nu_1=f, \nu_2=-f 就是对偶问题的一个下界。
  2. 对偶问题的任意一个解 (ν1,ν2)(\nu_1, \nu_2) 都可以找到一个 1-Lipschitz 函数 ff 以给出不弱于 (ν1,ν2)(\nu_1, \nu_2) 的解 (f,−f)(f, -f)。

因此：

W(P,Q)=sup⁡∥f∥L≤1[∑xf(x)P(x)−∑yf(y)Q(y)]W(P, Q) = \sup_{\|f\|_L \leq 1}\left[\sum_{x} f(x) P(x) - \sum_{y} f(y) Q(y)\right]

或者

W(P,Q)=sup⁡∥f∥L≤1Ex∼P[f(x)]−Ey∼Q[f(y)]W(P, Q) = \sup_{\|f\|_L \leq 1} \mathbb E_{x \sim P}[f(x)] - \mathbb E_{y \sim Q}[f(y)]

这就是 Kantorovich-Rubinstein 对偶性，也是 Wasserstein GAN 的理论基础。