Lovász拡張(Lovász extension)とは、有限集合 $E$ の部分集合の上の関数 $f$($f(\emptyset)=0$)を、$w\in\mathbb R^E$ の値で $E$ を上から切った集合 $S_1\subset\cdots\subset S_n=E$ の上の値 $f(S_i)$ を値の差で重みづけて足し、$\mathbb R^E$ 上の連続な区分的一次関数 $\hat f$ に延ばしたものである。Lovász の定理により、$f$ が劣モジュラであることと $\hat f$ が凸であることは同値で、このとき $\hat f$ は基多面体の支持関数である。$f(\emptyset)=0$ なら $f$ の最小値は $\hat f$ の単位立方体の上の最小値に等しく、これによって劣モジュラ関数の最小化は凸関数の最小化に帰着する。
Lovász拡張(Lovász extension)とは、有限集合 $E$ の部分集合の上の関数 $f$($f(\emptyset)=0$)を、$\mathbb R^E$ 全体の上の連続関数 $\hat f$ に延ばす標準的な方法である。$w\in\mathbb R^E$ の値で $E$ を上から切った集合の列 $S_1\subset S_2\subset\cdots\subset S_n=E$ をとり、$f(S_i)$ を段差 $w$ の値の差で重みづけて足す。部分集合 $A$ を指示ベクトル $\mathbf 1_A$ と同一視すると $\hat f(\mathbf 1_A)=f(A)$ である。
Lovász は、$f$ が 劣モジュラ関数 であることと $\hat f$ が凸関数であることが同値であることを示した(Lov83。GN23 p. 42)。劣モジュラ関数が「離散の凸関数」と呼ばれる理由はここにある。さらに、$f$ の最小値は $\hat f$ の単位立方体 $[0,1]^E$ の上の最小値に等しく、最小値をとる点の水準集合から最小値をとる集合が得られる。これによって劣モジュラ関数の最小化は凸関数の最小化に帰着し、オラクルで与えられた有理数値の関数について多項式時間で解ける。
この記事では、Lovász拡張を定義して基本の性質を示し、凸性の同値(thm-lx-convex)、最小値の一致(thm-lx-min)、最小値と基多面体の上の最大値の等式(thm-lx-minmax)を完全に証明する。そのあとカットの容量などの例を計算し、仮定を外した反例を挙げる。
$E$ を有限集合、$n:=\lvert E\rvert\ge1$ とし、$f\colon2^E\to\mathbb R$ は $f(\emptyset)=0$ をみたすとする。$A\subset E$ の 指示ベクトル $\mathbf 1_A\in\mathbb R^E$ は、$A$ の要素で $1$、ほかで $0$ のベクトルである。$x,w\in\mathbb R^E$ の内積を $w\cdot x$、$x(A):=\sum_{e\in A}x(e)$ と書く。
$w\in\mathbb R^E$ について、$E$ の要素を $w(e_1)\ge w(e_2)\ge\cdots\ge w(e_n)$ と並べ、$S_i:=\{e_1,\dots,e_i\}$ とおく。
$$
\hat f(w):=\sum_{i=1}^{n-1}\bigl(w(e_i)-w(e_{i+1})\bigr)f(S_i)+w(e_n)\,f(E)
$$
で定まる関数 $\hat f\colon\mathbb R^E\to\mathbb R$ を $f$ の Lovász拡張 という。
$w$ に等しい値があると並べ方は 1 通りでないが、$\hat f(w)$ は並べ方によらない(prop-lx-basic (1))。式は GLS88 (10.1.8)(p. 307)と同じで、GLS88 は $w\ge0$ の範囲でこの拡張を考えている(p. 308)。
$w\in\mathbb R^E$ とし、$m:=\min_ew(e)$、$M:=\max_ew(e)$、$\theta\in\mathbb R$ について $L_\theta(w):=\{e\in E\mid w(e)\ge\theta\}$(水準集合)とおく。
(1) $\displaystyle\hat f(w)=\int_m^Mf\bigl(L_\theta(w)\bigr)\,d\theta+m\,f(E)$。とくに $\hat f(w)$ は並べ方によらない。$w\ge0$ なら $\hat f(w)=\int_0^\infty f\bigl(L_\theta(w)\bigr)\,d\theta$ である。
(2) すべての $A\subset E$ で $\hat f(\mathbf 1_A)=f(A)$。
(3) $\lambda\ge0$、$\alpha\in\mathbb R$ について $\hat f(\lambda w)=\lambda\hat f(w)$、$\hat f(w+\alpha\mathbf 1_E)=\hat f(w)+\alpha f(E)$。また $f\mapsto\hat f$ は線形である。
(4) $\emptyset\ne T_1\subsetneq T_2\subsetneq\cdots\subsetneq T_k\subset E$ と $\lambda_1,\dots,\lambda_k>0$ について $\hat f\bigl(\sum_j\lambda_j\mathbf 1_{T_j}\bigr)=\sum_j\lambda_jf(T_j)$。
(5) 並べ方 $\sigma=(e_1,\dots,e_n)$ について、$\sigma$ の 貪欲ベクトル $x^\sigma(e_i):=f(S_i)-f(S_{i-1})$($S_0:=\emptyset$)をとると、$w(e_1)\ge\cdots\ge w(e_n)$ をみたすすべての $w$ で $\hat f(w)=w\cdot x^\sigma$ である。とくに $\hat f$ は連続で、$n!$ 個の錐の上でそれぞれ一次である。
$f$ の 基多面体 を $B(f):=\{x\in\mathbb R^E\mid\text{すべての }A\subset E\text{ で }x(A)\le f(A),\ x(E)=f(E)\}$ とおく(劣モジュラ関数 の定義「拡張ポリマトロイド・ポリマトロイド・基多面体」)。
$f\colon2^E\to\mathbb R$、$f(\emptyset)=0$ について、次の 3 条件は同値である。
(a) $f$ は劣モジュラである。
(b) $\hat f$ は $\mathbb R^E$ の上の凸関数である。
(c) $B(f)$ は空でなく、すべての $w\in\mathbb R^E$ で $\hat f(w)=\max_{x\in B(f)}w\cdot x$ である。
$\hat f$ を $w\ge0$ に制限した形の (a) ⇔ (b) は Lovász による(Lov83。GN23 p. 42 の Theorem。GLS88 p. 308 は、$f$ が劣モジュラなら $\hat f$ は線形計画の値の関数なので凸であり、逆も難しくないと述べている)。(c) は、$\hat f$ が $B(f)$ の 支持関数 であることを述べている。
(a) ⇒ (c):$f$ が劣モジュラなら、劣モジュラ関数 の定理「Edmondsの貪欲法の定理」(1)(2) により、$w$ の値の降順に並べた $\sigma$ の貪欲ベクトル $x^\sigma$ は $B(f)$ に属し、$B(f)$ の上で $w\cdot x$ の最大値をとり、その値は $\sum_{i=1}^{n-1}(w(e_i)-w(e_{i+1}))f(S_i)+w(e_n)f(E)=\hat f(w)$ である。
(c) ⇒ (b):各 $x\in B(f)$ について $w\mapsto w\cdot x$ は一次関数で、一次関数の族の各点での最大値(ここでは最大値が存在する)は凸関数である。
(b) ⇒ (a):$\hat f$ は凸で、prop-lx-basic (3) により正の数倍と可換なので、$u,v\in\mathbb R^E$ について
$$
\hat f(u+v)=2\,\hat f\Bigl(\tfrac12u+\tfrac12v\Bigr)\le\hat f(u)+\hat f(v)
$$
である。$S,T\subset E$ について $u=\mathbf 1_S$、$v=\mathbf 1_T$ とすると $\mathbf 1_S+\mathbf 1_T=\mathbf 1_{S\cap T}+\mathbf 1_{S\cup T}$ である。$\emptyset\ne S\cap T\subsetneq S\cup T$ なら prop-lx-basic (4) から $\hat f(\mathbf 1_S+\mathbf 1_T)=f(S\cap T)+f(S\cup T)$ である。$S\cap T=\emptyset$ なら $\mathbf 1_S+\mathbf 1_T=\mathbf 1_{S\cup T}$ で、値は $f(S\cup T)=f(S\cup T)+f(S\cap T)$、$S\cap T=S\cup T$($S=T$)なら値は $2f(S)$ で、どちらの場合も同じ式が成り立つ。prop-lx-basic (2) と合わせて $f(S\cup T)+f(S\cap T)\le f(S)+f(T)$ を得る。$\square$
$-f$ に当てると、$f$ が優モジュラであることと $\hat f$ が凹関数であることが同値になる($\widehat{-f}=-\hat f$)。$f$ がモジュラ、すなわち $f(A)=x(A)$ なら $\hat f(w)=w\cdot x$ は一次関数である。
$f$ を劣モジュラとし、$w\in\mathbb R^E$ の値の降順に並べた $\sigma$ をとる。このときすべての $v\in\mathbb R^E$ で $\hat f(v)\ge\hat f(w)+x^\sigma\cdot(v-w)$ であり、$x^\sigma$ は $\hat f$ の $w$ での劣勾配である。
prop-lx-basic (5) から $\hat f(w)=w\cdot x^\sigma$、thm-lx-convex (c) と $x^\sigma\in B(f)$ から $\hat f(v)\ge v\cdot x^\sigma$ である。引けばよい。$\square$
$\hat f$ の値と劣勾配は、$w$ の成分を並べ替えたうえで、$f$ の値を $n$ 回($f(S_1),\dots,f(S_n)$)問い合わせるだけで計算できる。これが最小化の算法で使われる(GLS88 p. 311)。
$f\colon2^E\to\mathbb R$、$f(\emptyset)=0$ とし、$\mu:=\min_{S\subset E}f(S)$ とおく。このとき
$$
\min_{w\in[0,1]^E}\hat f(w)=\mu
$$
であり、$w\in[0,1]^E$ が $\hat f(w)=\mu$ をみたすなら、すべての $0< \theta\le1$ で $f\bigl(L_\theta(w)\bigr)=\mu$ である。
この定理は $f$ の劣モジュラ性を使わない(GLS88 (10.2.8)、p. 310。GN23 p. 42 の Lemma)。$f$ が劣モジュラなら左辺は凸関数の立方体の上の最小化になるので、凸関数の最小化の方法(楕円体法 など)で扱える。これが 劣モジュラ関数 の定理「劣モジュラ関数の最小化(主張と所在)」の方針である。
$w\in[0,1]^E$ なら $w\ge0$ で、$\theta>1$ では $L_\theta(w)=\emptyset$ なので、prop-lx-basic (1) から
$$
\hat f(w)=\int_0^1f\bigl(L_\theta(w)\bigr)\,d\theta\ge\int_0^1\mu\,d\theta=\mu
$$
である。一方 prop-lx-basic (2) から、$\mu=f(S)$ となる $S$ について $\hat f(\mathbf 1_S)=\mu$ である。よって最小値は存在して $\mu$ に等しい。
$\hat f(w)=\mu$ とすると $\int_0^1\bigl(f(L_\theta(w))-\mu\bigr)\,d\theta=0$ で、被積分関数は $0$ 以上である。$w$ の成分の値と $0,1$ で区間 $(0,1]$ を有限個の区間 $(a,b]$($a< b$)に分けると、各区間の上で $L_\theta(w)$ は一定である。被積分関数はその区間の上で一定の $0$ 以上の値をとり、積分が $0$ なのでその値は $0$ である。どの $\theta\in(0,1]$ もどれかの区間に入るので、$f(L_\theta(w))=\mu$ である。$\square$
劣モジュラ関数では、最小値は基多面体の上の最大値としても書ける。$x\in\mathbb R^E$ について $x^-(e):=\min\{x(e),0\}$ とおく。
$f$ を劣モジュラ、$f(\emptyset)=0$ とすると
$$
\min_{S\subset E}f(S)=\max_{x\in B(f)}x^-(E)
$$
である。
まず右辺が左辺以下であることを示す。$x\in B(f)$ と $S\subset E$ について $x^-(E)\le x(S)\le f(S)$ は、$x^-(E)\le x^-(S)\le x(S)$ と $B(f)$ の定義から従う。
逆向きを示す。$B(f)$ は空でない(thm-lx-convex (c))。thm-lx-min と thm-lx-convex (c) から
$$
\min_Sf(S)=\min_{w\in[0,1]^E}\hat f(w)=\min_{w\in[0,1]^E}\ \max_{x\in B(f)}w\cdot x
$$
である。劣モジュラ関数 の定理「Edmondsの貪欲法の定理」(3) により $B(f)$ は貪欲ベクトル $x^{\sigma_1},\dots,x^{\sigma_N}$($N=n!$)の凸包であり、$[0,1]^E$ は $\mathbf 1_{A_1},\dots,\mathbf 1_{A_K}$($K=2^n$)の凸包である。行列 $(m_{kl}):=(\mathbf 1_{A_k}\cdot x^{\sigma_l})$ をとると、$w=\sum_kp_k\mathbf 1_{A_k}$、$x=\sum_lq_lx^{\sigma_l}$($p,q$ は確率ベクトル)について $w\cdot x=p^{\mathsf T}(m_{kl})q$ である。よって上の値は行列 $(m_{kl})$ のゲームの $\min_p\max_q$ で、von Neumannのミニマックス定理 により $\max_q\min_p$ に等しい。これを戻すと
$$
\min_Sf(S)=\max_{x\in B(f)}\ \min_{w\in[0,1]^E}w\cdot x=\max_{x\in B(f)}x^-(E)
$$
である。最後の等号は、$w\cdot x=\sum_ew(e)x(e)$ を $w(e)\in[0,1]$ について成分ごとに最小化すると、$x(e)< 0$ で $w(e)=1$、$x(e)\ge0$ で $w(e)=0$ となり、最小値が $x^-(E)$ であることによる。$\square$
右辺の最大値をとる $x$ と、左辺の最小値をとる $S$ の組は、互いの最適性の証明書になる。$x\in B(f)$ と $S$ で $x^-(E)=f(S)$ となれば、どちらもそれぞれの問題の最適解である。
有向グラフ $(V,A)$ と容量 $c\colon A\to\mathbb R_{\ge0}$ について、$f(S)$ を $S\subset V$ から出る弧の容量の和とする($f(\emptyset)=f(V)=0$)。このとき
$$
\hat f(w)=\sum_{a=(u\to v)\in A}c(a)\max\{w(u)-w(v),0\}
$$
である。無向グラフのカットの容量では、各辺 $uv$ を 2 本の弧に替えて $\hat f(w)=\sum_{uv}c(uv)\,\lvert w(u)-w(v)\rvert$ となる。
$f$ について線形なので(prop-lx-basic (3))、弧 1 本 $a=(u\to v)$ の関数 $f_a(S):=1$($u\in S$、$v\notin S$)、$:=0$(それ以外)で確かめればよい。$f_a(V)=0$ なので prop-lx-basic (1) から $\hat f_a(w)=\int_m^Mf_a(L_\theta(w))\,d\theta$ で、被積分関数が $1$ になるのは $w(v)< \theta\le w(u)$ のときだけである。よって $\hat f_a(w)=\max\{w(u)-w(v),0\}$ である。右辺は一次関数の最大値の和なので凸であり、thm-lx-convex と合う。最大流最小カット定理 の命題「双対問題の解からカットを作る」で、双対問題の解を水準で切ってカットを作る議論は、この式と thm-lx-min の証明と同じ形をしている。
$g(0)=0$ の関数 $g$ について $f(S):=g(\lvert S\rvert)$ とする。$w$ の成分を大きい順に $w_{(1)}\ge\cdots\ge w_{(n)}$ と並べると、貪欲ベクトルの成分は $g(k)-g(k-1)$ なので、prop-lx-basic (5) から
$$
\hat f(w)=\sum_{k=1}^n\bigl(g(k)-g(k-1)\bigr)\,w_{(k)}
$$
である。$g(k)=k$ なら $\hat f(w)=\sum_ew(e)$、$g(k)=\min\{k,1\}$ なら $\hat f(w)=w_{(1)}=\max_ew(e)$ で、どちらも凸である。$g(k)=\max\{k-n+1,0\}$、すなわち $f(S)=1$($S=E$)、$0$(それ以外)なら $\hat f(w)=w_{(n)}=\min_ew(e)$ で、$n\ge2$ では凸でない。この $f$ は優モジュラで劣モジュラでない($n\ge2$)。
$E=\{a,b\}$ の上の関数を、値の組 $\bigl(f(\emptyset),f(\{a\}),f(\{b\}),f(E)\bigr)$ で、$w$ を $(w(a),w(b))$ で書く。
| 外した仮定 | 反例 | 成り立たなくなる結論 |
|---|---|---|
| 劣モジュラ(thm-lx-convex (a) ⇒ (b)) | $(0,0,0,1)$ | $\hat f$ が凸であること |
| $f(\emptyset)=0$(thm-lx-min) | $(1,2,2,2)$、$\hat f$ は同じ式で定める | $\min_{[0,1]^E}\hat f=\min f$ |
| $w$ の範囲が $[0,1]^E$(thm-lx-min) | $(0,1,1,2)$、範囲を $\mathbb R^E$ にする | $\inf\hat f=\min f$ |
| 劣モジュラ(thm-lx-minmax) | $(0,0,0,1)$ | 最小値が $B(f)$ の上の最大値に等しいこと |
1 行目:ex-lx-card の最後の場合で $\hat f(w)=\min\{w(a),w(b)\}$ である。$\hat f\bigl(\tfrac12(1,0)+\tfrac12(0,1)\bigr)=\tfrac12$ だが $\tfrac12\hat f(1,0)+\tfrac12\hat f(0,1)=0$ なので、凸でない。
2 行目:定義の式は $f(\emptyset)$ を使わないので、$\hat f(0,0)=0$ である。一方 $\min f=f(\emptyset)=1$ なので、$\min_{[0,1]^E}\hat f\le0< 1$ となって等式が成り立たない。$f$ は劣モジュラ($2+2\ge2+1$)なので、成り立たない原因は $f(\emptyset)\ne0$ だけである。
3 行目:$f(S)=\lvert S\rvert$ で $\hat f(w)=w(a)+w(b)$ はいくらでも小さくなるが、$\min f=0$ である。
4 行目:$f$ は劣モジュラでない($0+0< 1+0$)。$x\in B(f)$ なら $x(a)\le0$、$x(b)\le0$、$x(a)+x(b)=1$ でこれは両立しないので $B(f)=\emptyset$ で、右辺の最大値が存在しない。左辺は $\min f=0$ である。
この拡張は Lovász が 1983 年の論文 Lov83 で劣モジュラ関数と凸関数の橋渡しとして導入した(GN23 p. 42)。$w\ge0$ に限った定義の式と、劣モジュラ関数の最小化への応用は GLS88 §10.1–10.2(pp. 307–311)にある。最小化の組合せ的な算法については 劣モジュラ関数 の節「最小化」を参照。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する