最小全域木問題の「凸性」②
前回の記事 の続きです。
前回は、最小全域木を求めるアルゴリズムとその「凸っぽさ」を定義し、離散版の凸関数を定義する必要性を述べた。ここからはいよいよその定義に入る。
3.「離散版」凸関数の定義（M凸関数）
まず、ユークリッド空間で定義された関数$f: \mathbb{R}^N \to \mathbb{R}$の定義は以下のようであった。
定義（凸関数）：$f: \mathbb{R}^N \to \mathbb{R}$が凸関数であるとは、任意の$x,y \in \mathbb{R}^N$および$0 \leq t \leq 1$に対して$f(tx+(1-t)y) \leq tf(x)+(1-t)f(y)$が成り立つことである。
上記の定義の$t$に$\alpha (0 \leq \alpha \leq 1)$と$1- \alpha$を代入して辺々足し合わせると、凸関数では$f(x+\alpha(y-x))+f(y+\alpha(x-y)) \leq f(x)+f(y)$が成り立つことがわかる。つまり、任意の$x,y$を取ったとき、両端$x,y$から$\alpha$だけ「歩み寄った」点$x+\alpha(y-x),y+\alpha(x-y)$での$f$の値の和は、両端での$f$の値の和以下になる。
ところで逆に、$f(x+\alpha(y-x))+f(y+\alpha(x-y)) \leq f(x)+f(y)$が成り立つとき、$f$は凸関数と言えるだろうか。実は$f$が連続であれば凸関数と言える（解析をゴリゴリやると出来るが、本筋から逸れるので省略する）。開区間で定義された凸関数は連続なので、$f: \mathbb{R}^N \to \mathbb{R}$であれば$f(x+\alpha(y-x))+f(y+\alpha(x-y)) \leq f(x)+f(y)$は$f$の凸性と同値になる。
この$f(x+\alpha(y-x))+f(y+\alpha(x-y)) \leq f(x)+f(y)$の方を離散っぽく言い換えることにする。$f$の定義域を$\mathbb{R}^N$ではなく$\mathbb{Z}^N$にすれば離散的になりそうだ。しかし、$x,y \in \mathbb{Z}^N$に対して、たとえば$x+\alpha(y-x)\in \mathbb{Z}^N$とは限らないので工夫が必要である。この辺りに注意して書き換えたのが以下のM凸関数である。
定義（M凸関数）：関数$f:S \subset \mathbb{Z}^N \to \mathbb{R}$がM凸関数であるとは、任意の$x,y \in \mathbb{S}^N$をとったとき、$x_i-y_i >0$をみたす任意の$i$に対して$x_j-y_j <0$をみたす$j$が存在して、
$x+e_i-e_j,y-e_i+e_j \in S \land f(x+e_i-e_j)+f(y-e_i+e_j) \leq f(x)+f(y)$
が成り立つことをいう。ただし、$e_i$は第$i$成分のみ$1$で他は$0$である単位ベクトルである。
凸関数を定義するときに凸集合も定義したのと同様、M凸集合も定義しておく。
定義（M凸集合）：関数$f:S \subset \mathbb{Z}^N \to \mathbb{R}$がM凸集合であるとは、任意の$x,y \in \mathbb{S}^N$をとったとき、$x_i-y_i >0$をみたす任意の$i$に対して$x_j-y_j <0$をみたす$j$が存在して、
$x+e_i-e_j,y-e_i+e_j \in S$
が成り立つことをいう。
定義から明らかに、M凸関数の定義域はM凸集合である。
この定義は一見、随分と本来の凸関数（や凸集合）の定義を弱めたように見える。ある方向$i$に対して、「$i,j$方向に歩み寄って小さくなる方向」$j$が一方向でも存在すればよいことになる。また、$x_i-y_i$と$x_j-y_j $の符号が違う必要があるのがなぜかもまだよくわからない。となると、凸関数のうれしい性質と似たものが復元できるのだろうかと不安になる。
一旦その不安は胸にしまい、以下ではまず全域木の重みがM凸関数になっていることを確認し、そのあとでM凸関数における最適化の様々な性質を見ていく。
4.全域木のM凸性
勘がよい方はもうお気づきのことと思うが、全域木の集合はM凸集合になり、全域木の重み（辺の重みの総和）はM凸関数になる。これは次のようにすればよい：
命題2：グラフ$G=(V,E)$とし、以下では辺の部分集合からなる集合族$2^E$を$\{0,1\}^{|E|} \in \mathbb{Z}^{|E|}$と同一視する：$S \in \{0,1\}^{|E|}$を$E$の部分集合と同一視し、$S_i=1$ならば辺$i$が$S$に含まれていることを表すものとする。
この時以下が成り立つ。
- $\mathcal{S} :=\{S \in 2^E \mid Sは全域木 \}$とすると、$\mathcal{S}$は凸集合である。
- $w:\mathcal{S} \to \mathbb{R}$を$w(S)=（Sの辺の重みの総和）$と定めると、$w$は$S$上のM凸関数である。
命題2の証明は、定理1の証明を思い出すと出来る。定理1では、異なる全域木$S,T$を取ったときに、$e \in S \setminus T$に対して$f \in T \setminus S$をとり、$T \cup e \setminus f$が全域木となることを用いて証明をした。これはそのまま命題2の1.の結果である。
証明
1.) $T,S \in \mathcal{S}$を取る。$S$と$T$の$\{0,1\}^{|E|}$での表現を考えると、$S_i-T_i>0$となる$i$が存在することは、$S \setminus T$が空でないことと同値である。最小全域木の辺数は常に一定なので、この時$T \setminus S$も空でない。ここで定理1の証明と全く同様にして、$T \setminus S$から辺$f$を選び$T \cup e \setminus f$を全域木にできる。$S \cup f \setminus e$が全域木となることも明らかであるから、この$f$が（M凸関数の定義で存在が要請される）$j$に対応する。■
2.) 1.)のように$e,f$を選んだ時、明らかに$w(T \cup e \setminus f)+w(S \cup f \setminus f)=w(T)+w(S)$なので、$w$はM凸関数の定義における不等号（の等号成立条件）をみたす。■
というわけで、最小全域木問題をM凸関数の最小化問題に焼き直すことができた。ここまでくれば、あとはM凸関数の一般的な性質、特に「極小解⇒最小解」を調べればよい。実はもう道具はそろっていて、やはり定理1の証明を一般的に焼き直せばよい。以下ではそれを見ていく。
5.M凸関数の性質
「極小点」は次のように定義するのが自然であろう。
定義（極小点） $S \in \mathbb{Z}$、$f:S \to \mathbb{R}$とする。$x$が$S$における$f$の極小点であるとは、$x+e_i-e_j \in S$をみたす任意の$i,j$に対して、$f(x+e_i-e_j) \geq f(x)$をみたすことをいう。
次の定理は重要である。
定理3 M凸関数において、極小点は最小点である。
参考文献を見たら証明が全カットされていて悲しい気分になった。自分で構成した。
証明 $S$をM凸集合、$f$をM凸関数とする。$x$を$S$における$f$の極小点とし、$y \in S$が$f(x)>f(y)$をみたすと仮定して矛盾を導く。
ここでは$x$と$y$の$L^{\infty}$距離（各成分の差の絶対値の総和$\sum {|x_i-y_i|}$）$d(x,y)$に関する帰納法により、任意の$d(x,y)$で矛盾が生じることをを示す。$d(x,y)=0$で矛盾が生じるのは自明である。$d(x,y) \leq n$で矛盾が生じるとする。$d(x,y)=n+1$として矛盾を導く。
いま$x \neq y$である。$x_i-y_i >0$となる$i$が存在するとして一般性を失わない（必要であれば$x$と$y$を入れ替えればよい）。この時M凸集合およびM凸関数の定義から
$x_j-y_j <0$をみたす$j$が存在して、
$x+e_i-e_j,y-e_i+e_j \in S \land f(x+e_i-e_j)+f(y-e_i+e_j) \leq f(x)+f(y)$
が成り立つ。ここで$x$の極小性より、$f(x+e_i-e_j) \geq f(x)$なので、$f(y-e_i+e_j) \leq f(y)$でなければならない。このとき仮定$f(x)>f(y)$より$f(x)>f(y-e_i+e_j)$である。しかし$L^{\infty}$距離に注目すると、$d(x,y)<d(x,y-e_i+e_j)$なので、帰納法の仮定から矛盾が生じる。ゆえに任意の$d(x,y) \leq n$で矛盾が生じるので、結局任意の$y \in S$に対して$f(x) \leq f(y)$であり$x$が最小点となる。■
この証明の「凸関数っぽい」見方を併記しておく。第3項の最初で述べた通り、（連続版でも）凸関数では「歩み寄ると和が小さくなる」という性質がある。凸関数の極小点$x$と、そうでない点$y$を取ったとき、$x$の近傍からはみ出さない程度の幅で$x,y$同時に歩み寄ると、和は小さくなるが、$x$は極小点なので$y$から歩み寄った点$y'$での関数の値$f(y')$は$f(y)$以下である。$y$を$y'$に入れ替えると$x,y$は近づいていて、同じことを（$x$と$y$の距離）/（$x$の近傍の大きさ）回ぐらい実行すれば$x=y$となり、ゆえに$f(x) \leq f(y)$でなければいけなくなる。
このように見ると、やや弱いように見えたM凸関数の定義は、「極小⇒最小」という意味での凸関数の性質をとらえるには充分であることがわかる。
さらに以上から、定理3の系として定理1が得られる。これにより、最小全域木問題のM凸関数最小化問題としての定式化が無事できた。
以上により、クラスカル法やカラバ法の正当性証明において重要な役割を果たした定理1を、M凸関数の観点から理解することができた。一般化することのメリットは非常に大きく、全域木問題に限らず構造にM凸性を有する問題に対して似たようなアルゴリズムを利用することができる可能性もわかった。
一方で、定理1のみではクラスカル法やカラバ法を導出するにはややギャップがある。定理1によりいわば「極小全域木」をとってくれば良いのだが、クラスカル法やカラバ法では「極小全域木を作る上で『いらない辺』を巧妙に除去できている」ことが本質的に重要であった。このような性質もM凸関数の観点から書き直せないだろうか？
これは、実はM凸関数のカット定理とよばれる定理で記述することができる。しかし、長くなるうえに特にクラスカル法に関してはM♮凸という概念も導入しないといけないので今回は一旦ここで切ろうと思う。
