劣モジュラ関数

OR事典

劣モジュラ関数

読み方：れつもじゅらかんすう
【英】：submodular function

分配束 上の関数 が, 任意の に対して

を満たすとき, を劣モジュラ関数という. 劣モジュラ性は, ネットワークのカット容量関数, マトロイドの階数関数, 多元情報源のエントロピー関数, 協力凸ゲームの特性関数等, オペレーションズ・リサーチの諸分野に現れる基本的な関数に共通する有用な性質である.

「OR事典」の他の用語

グラフ･ネットワーク：

劣モジュラシステム  劣モジュラフロー問題  劣モジュラ最適化  劣モジュラ関数  同形性  基多面体  基族

ウィキペディア

劣モジュラ関数

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/03/14 06:33 UTC 版)

劣モジュラ関数（れつモジュラかんすう、英: submodular function）とは、数学において集合関数の一種で、簡単にいうと、関数に渡される集合に1つ要素が加わった場合に増える関数の値が、もとの集合が大きくなるにつれ小さくなるような関数を指す。集合関数であることを明示して劣モジュラ集合関数ということもある。劣モジュラ関数の概念は一般のベクトル値関数における凸関数の概念と類似した性質を持つため、近似アルゴリズムやゲーム理論、機械学習などの幅広い応用を持つ。

定義

台集合 Ω の冪集合 2^Ω 上の関数 f: 2^Ω → R で 次を満たす関数を劣モジュラ関数と呼ぶ。

劣モジュラ性

任意の集合対 S, T ⊆ Ω に対して、f(S) + f(T) ≥ f(S ∪ T) + f(S ∩ T)

この不等式を劣モジュラ不等式と呼ぶ。 なお、不等号の向きを逆にした不等式を優モジュラ不等式と呼び、それを満たす集合関数を優モジュラ関数と呼ぶ。

また、上記の不等式と以下の 2 つの不等式は同値である。

1. 任意の集合対 $X,Y\subseteq \Omega ,X\subseteq Y$
   この節の加筆が望まれています。

   ロバース拡張

   ベクトル $\mathbf {x} =\{x_{1},x_{2},\ldots ,x_{n}\}$