離散凸解析のはなし

日曜数学Advent Calendar 2021

本記事は、 日曜数学Advent Calendar 2021 の20日目の記事です。

日曜数学Advent Calendar 2021 では、これまでにも様々な分野の記事が投稿されておりますので、チェックしてみてください。

昨日の記事は、ふくま@とぽろじい～数学自由研究～さんの、「 【代数的トポロジー】柔らかくない？トポロジー「奇数次元球面の有理ホモトピー群」(前編) 」でした。

はじめに

離散凸解析について書く理由

　普段は数論が好きで趣味で勉強をしているのですが、今回は一風異なったお題「離散凸解析」について、触りだけ紹介したいと思います。数式は少なめでお気持ち的な話になっていると思いますので、さらっと読みながしてください。
　離散凸解析については、離散最適化的なことを研究していた学生時代に存在を知り、その後長い間触れていなかったのですが、昨今の機械学習ブームで離散凸解析に親和性のある劣モジュラ最適化の書籍を見かけ、久しぶりに学習するモチベーションが生まれました。学習した内容のアウトプットの一貫として、備忘録的なものを作っており、離散凸に興味を持たれる方も居るのではないかと思い、公開することにしました。
　今回は、離散凸解析の雰囲気を味わって貰うことを目的とした記述となっているため、精緻な記述は参考文献として挙げた室田一雄先生の書籍などを参照して頂ければと思います。

歴史

離散凸解析は、東大の室田一雄先生が提唱された概念です。そこに至るまでには様々な概念がありました。歴史的には以下のような流れなっています。

離散凸解析の着想

最適化で解きやすい問題とはなんだろうと考えたとき、どういう形で分けられるかを考えてみましょう。

凸の概念

最適化問題で良くあるのが、ある関数の最小値を求める問題です。
そこで以下のようなことが考えられます。

• 連続で解きやすい問題は凸性があり、凸性が無いと難しい
• 離散の世界では、グラフの問題だと、最短経路問題は簡単で、巡回セールスマン問題は難しい
• ここから、最短経路は凸、巡回セールスマンは非凸という感じがする

離散凸性をどう定義するか

• 凸性を拡張した概念にする
• 離散凸性を最適化が機能するよう定義したい
• 以下の凸関数に期待される基本的な性質を満たしたい
  • (Convex) 実行可能領域は凸多面体。幾何的性質から最適化問題の性質が分かる
  • (LocalOpt) 局所最適が大域最適
  • (DualPair) 双対問題（ルジャンドル変換）があり、表裏の関係で、裏の裏は表
  • (MinMax) 主問題と双対問題の最適値が一致する（双対定理）
  • (Separate) 双対定理の背後に分離超平面の存在（Farkasの補題）がある

離散凸解析の提唱と整理

• 離散で解きやすい問題はマトロイド(組み合わせ論)＋凸性(解析的)があるのだが、統一的なフレームワークが無かったので、東大の室田一雄先生などにより作られたのが離散凸解析の理論
• 良い感じの概念として以下が導入された
  • マトロイドは、M凸性(MはMatroid)
  • 劣モジュラは、L凸性(LはLattice)
• 通常の凸解析の定理が移植された
  • 最小性（局所最適が大域最適）、共役性（双対問題）、双対定理など
• 最適化アルゴリズムの構築
• 応用
  • OR(Operations Research)、制御、ゲーム理論、経済、数学

M凸／L凸関数の性質

以下のように離散凸関数としてふさわしい性質を持つ

• 凸拡張可能性
  • 任意のM凸関数とL凸関数は凸拡張可能（線形補間すると連続の凸になる）
• 局所最適性＝大域的最適性
  • M凸関数は、$f(x)\le f(y) (\forall y \in dom f)$ $\Leftrightarrow f(x) \le f(x- \chi_i + \chi_j) (\forall i,j \in { 1,2, \ldots ,n})$
  • Ｌ凸関数は、$f(p)\le f(q) (\forall q \in dom f)$ $\Leftrightarrow g(p) \le g(p+ \chi_X) (\forall X \subset { 1,2, \ldots ,n})$
• （離散）分離定理
  • マトロイドや劣モジュラ集合関数に対する既存の双対定理・分離定理の拡張
• 共役性
  • $f$の共役関数は
  • 整数値M凸（L凸）関数の共役関数は、整数値L凸（M凸）関数となる

劣モジュラとは

劣モジュラの定義

以下の不等式を満たす集合関数$f$は劣モジュラ性を満たしているといい、これを満たす集合関数を劣モジュラ（submodular function)とよぶ。

$f(S) +f(T) \ge f(S \cup T) + f(S \cap T), (\forall S, T \subseteq V)$

• 劣モジュラ関数を線型補間する拡張をロヴァース拡張（Lovász extension）という
• ロヴァース拡張が凸関数であることと、集合関数が劣モジュラ関数であることは同値
• また、以下の条件と上記劣モジュラ関数の条件は同値
  • $f(S \cup {i}) - f(S) \ge f(T \cup {i}) - f(T)$, $(\forall S \subseteq T \subseteq B$, $\forall i \in V\backslash T)$
  • 直感的には、同じ要素を加えたとしても、より大きな集合に加えた場合の方が情報量が少ないというイメージ

【余談】数学セミナー2022年1月号を読んで気付きましたが、ここで名前が出てくるLovászさんは今年アーベル賞を受賞されていますね。

劣モジュラ関数の例

• 無向グラフが与えられたときに、選択したノード集合とその補集合との間の枝の数を返す関数はカット関数と呼ばれ、劣モジュラ関数であることが知られている
• 有限個の要素集合と、それらの一部をそれぞれ含むような要素の数を返す関数をカバー関数という
• グラフカット、構造正則化においては、最小化問題となる

あとがき

　今回は離散凸解析について雑多に紹介しました。M凸に関する話が書けなかったので、さらに興味のある方は、ぜひ参考文献を見ていただけると良いかと思います。