週刊 spaghetti_source

subgradient representation of matroid intersection theorem

21:03

今回は劣微分によるマトロイド交差定理の表現を紹介します．この形でマトロイド交差定理を説明している文献を見たことがありませんが，従来表現から簡単に出るので特に新しくはありません．ただ，自分の肌には良くあう理解です．

以下では，まず劣微分について簡単に復習し，その後，マトロイド交差定理を表現します．

劣微分

まずは連続の場合から復習します．関数 f: V→R の点xにおける劣微分とは，点xでfを下から支持する超平面のことです．式で書くと次のようになります：

　∂f := { p \in V^* : (p,y-x) ≦f(y)-f(x) for all y }

(・,・)はペアリング（内積）です．任意の点で劣微分がとれることと，凸であることはほとんど同値（端点だけ例外）となります．病的な境界の関数を考えると違いが出てくるのですが，実用上は「凸解析＝劣微分がとれる関数クラスの理論」と思ってほぼ正しいです．

劣微分と最適化の繋がりで最も重要なのは次の命題です：

命題． 0∈∂f(x) であることと，x が f の大域最適解であることは同値．

（∵ z軸に並行な接平面がとれる＝自分より下が居ない．//）

このことは「0∈∂f(x)」が「x が最適である証拠」だということを主張しています．逆に，最適の証拠がとれない場合には，劣微分を用いて最適解方向へ x を更新することが可能です：

命題 [see: Boyd 2003]． 任意の 0≠p∈∂f(x) について，あるh > 0が存在して，d(x*, x - h p) < d(x*, x)．ここで x* はある大域最適解．

（∵ d(x*, x-hp) を計算する．やるだけなので省略．//）

※微分可能の場合によく使う勾配方向への更新では必ず目的関数値が減少しますが，劣微分方向への更新では減少しない例が作れます．それでも，x 自体は最適解へと近づきます．これは「劣勾配法の強収束性」と呼ばれています．

これらのことから，標語的に

　凸関数 <=> 劣微分存在 <=> 大域最適が計算可

という関係が成り立ちます．

さて，劣微分に関する重要な性質として，次の定理（劣微分の和公式）があります．

定理．[Moreau-Rockafeller; see: Winfried 2007] f, g を凸関数とする．弱い仮定のもとで ∂(f + g) = ∂f + ∂g．

一般の f, g で ⊇ 側の包含関係は従いますが，逆側が従うのが凸関数の良いところです．証明は凸集合の分離定理（Hahn-Banach）を用います．

※弱い仮定は「エピグラフに対して凸分離定理が成り立つ」程度の仮定で，通常は成立すると思ってよい．

マトロイド

さて，ここからが本題です．マトロイドに関して劣微分の議論を導入します．関数を考えるので，マトロイドよりもM凸関数を考えたほうが自然です．関数 f がM凸であるとは，任意の x, y と i ∈ supp(x-y) について，ある j ∈ supp(y-x) が存在して

　f(x) + f(y) ≧ f(x-ei+ej) + f(y+ei-ej)

が成り立つことをいいます．たとえばマトロイドに対して f を次のように定義するとM凸関数になります．

• f(x) = -|x| if x 独立, +∞ if x 従属

※一般に，M凸関数の実行定義域（値が有限をとる点）全体はマトロイド（の拡張）となります．マトロイドはM凸関数の実行定義域のことだ，と思っておいて大丈夫です．

M凸関数 f の劣微分はどうなるでしょうか．結論から言うと，これは

　∂f(x) = { p ∈ R^n | p(j) - p(i) ≦ f(x-i+j) - f(x) }

となります．最適性条件 0 ∈ ∂f(x) を書き下すと，上の式で p = 0 とおいて

　0 ≦ f(x-i+j) - f(x) (for all i, j)

となります．これはM凸関数についてよく知られている最適性条件です（実際は：最適性条件から劣微分を出すほうが易しい）．

最適でない場合の更新ですが，連続関数と違い，劣微分方向に進むことはできません．そのかわり，劣微分方向で整数格子上の一番近い点へと丸めることで，いわゆる「マトロイド上の貪欲法」が出てきます（減り幅最大の方向に進む）．つまりマトロイド貪欲は劣勾配法の一種と言えます．

続いて，マトロイド交差問題は次のように表現できます：f, g M凸関数について

　min f(x) + g(x)

x が f, g どちらかの実行定義域（独立集合）を外れると全体が無限大に飛ぶので，共通実行定義域（＝共通独立集合）に入ることが x の条件です．このことから，確かにマトロイド交差問題を表していることがわかります．

この問題の最適性条件を見るために ∂(f + g) について考えます．実は，マトロイド交差定理は，Moreau-Rockafellerの定理の離散版と言えます：

定理 [Matroid Intersection; see: Murota 2003]． f, g をM凸関数とする．∂(f + g) = ∂f + ∂g．

（∵Frank's weight splittingを使う）

※M凸でない関数和では成り立ちません．例えば

　f(x,y) = |x + y - 1| (… M凸)

　g(x,y) = |x - y| (… L凸)

はどちらも連続の意味では凸関数ですが，離散に制限すると和公式が成立しません．実際 f + g は (0,0) で最小値 1 を達成するので 0 が(f + g)の劣微分に入るはずですが，f の (0,0) での劣微分は (-1,-1) の一点のみ，g の (0,0) での劣微分は { (t,-t) | -1 ≦ t ≦ 1 } なので，和でゼロは作れません．

...

劣微分からアルゴリズムへ

和公式が成り立つことを信じると，マトロイド交差アルゴリズムが自然に導出できます．最適性条件 0 ∈ ∂(f + g) = ∂f + ∂g は，ある p が存在して p ∈ ∂f, -p ∈∂g となることと同値です．これをM凸の劣微分の式とあわせると

　p(j) - p(i) ≦ f(x-i+j) - f(x)

　p(i) - p(j) ≦ g(x-i+j) - g(x)

となります．ポイントは，この不等式系は最短路問題の双対 [Cormen-Leiserson-Rivest-Stein 2009] となっていることです．すなわち，グラフ G を「辺 (i,j) のコストが f(x-i+j) - f(x)，(j,i) のコストが g(x-i+j) - g(x) となるグラフ（＝交換グラフ）」とすると，p が存在することはグラフが負サイクルをもたないことと同値となり，負サイクルがないときは p として最短路長がとれます（適当に p(s) = 0としてよい）．

逆に，負サイクルがあった場合，そのサイクルから劣微分の元を構成することができます．すなわち，負サイクルキャンセルアルゴリズムは，適当な劣微分（負サイクル）による劣勾配法とみなせます．

...

まとめ

• マトロイド交差定理は ∂(f + g) = ∂f + ∂g と表現可能．
  ※連続凸なら常に成り立つが離散凸では成り立つとは限らない．
• f+g の最小値を求めるために ∂(f+g) = ∂f+∂g = 0 とすると，交差問題の最適性条件（交換グラフに負閉路なし）が出る．
• 負閉路がある場合にそれにそってキャンセルするのは，劣勾配法の一種．

参考文献

• S. Boyd (2003): "Subgradient methods", Notes for EE392o, Stanford University, Autumn, 2003.
• S. Winfried (2007): "Nonsmooth Analysis", Springer Berlin Heidelberg.
• K. Murota (2003): "Discrete Convex Analysis", Society for Industrial and Applied Matheamtics.
• T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein (2009): "Introduction to Algorithm", The MIT Press, 3rd ed.

• S. Boyd (2003):