劣モジュラ最適化とは？わかりやすく解説

辞書 類語・対義語辞典 英和・和英辞典 日中中日辞典 日韓韓日辞典 古語辞典

その他の辞書▼
- フランス語辞典
- インドネシア語辞典
- タイ語辞典
- ベトナム語辞典

Weblio 辞書ヘルプ

556の専門辞書や国語辞典百科事典から一度に検索!

無料の翻訳ならWeblio翻訳！

初めての方へ参加元一覧

Weblio 辞書 > 同じ種類の言葉 > 情報 > コンピュータ > 最適化 > 劣モジュラ最適化の意味・解説

OR事典

索引トップ用語の索引ランキングカテゴリー

劣モジュラ最適化

読み方：れつもじゅらさいてきか
【英】：submodular optimization

概要

劣モジュラ最適化とは, 劣モジュラ関数を制約条件または目的関数に含んだ離散最適化を指す. 劣モジュラ関数に関連した最適化問題に対しては, 離散構造を利用した効率的なアルゴリズムが存在することが少なくない. そのため, 劣モジュラ最適化は, 非線形最適化における凸最適化のように, 離散最適化における基本的な位置を占めている.

詳説

　劣モジュラ最適化 (submodular optimization) とは, 劣モジュラ関数 (submodular function) を制約条件または目的関数に含んだ離散最適化を指す. 劣モジュラ最適化は, 非線型最適化における凸最適化のように, 離散最適化における基本的な位置を占めている.

　有限集合 $N\,$ の部分集合族 $\mathcal {D}\subseteq 2^N\,$ が, $\emptyset\,$ と $N\,$ を共に含み, 任意の $X,Y\in\mathcal {D}\,$ に対して $X\cup Y, X\cap Y\in\mathcal {D}\,$ を満たすものとする. このとき, $\mathcal {D}\,$ は分配束をなす. 関数 $f:\mathcal {D}\to\mathbf {R}\,$ が, 任意の $X,Y\in\mathcal {D}\,$ に対して

$f(X)+f(Y)\geq f(X\cup Y)+f(X\cap Y)\,$

を満たすとき, $f\,$ は劣モジュラ関数と呼ばれる. 不等号が常に等号で成立する場合には, $f\,$ をモジュラ関数という. 分配束 $\mathcal {D}\,$ と劣モジュラ関数 $f\,$ の組 $(\mathcal {D},f)\,$ は, $f(\emptyset)=0\,$ のとき, 劣モジュラシステム (submodular system) と呼ばれる. さらに, $\mathcal {D}=2^N\,$ であり, $f\,$ が単調性を有するとき, すなわち任意の $X,Y\subseteq N\,$ に対して $X\subseteq Y \Rightarrow f(X)\leq f(Y)\,$ が成り立つとき, $(N,f)\,$ をポリマトロイド (polymatroid)という.

　オペレーションズ・リサーチにおいて重要な劣モジュラ関数の代表的な例を以下に挙げる.

カット容量関数　有向グラフ $G=(N,A)\,$ において, 各枝 $a\in A\,$ に非負の容量 $c(a)\,$ が与えられているとき, $\textstyle \kappa(X)=\sum\{c(a)\mid a\in \Delta^+X\}\,$ で定義される容量関数 $\kappa:2^N\to\mathbf {R}\,$ は, 劣モジュラ関数となる. ここで, $\Delta^+X\,$ は, $X\subseteq N\,$ から出る枝の集合を表す.

マトロイド階数関数　マトロイド $\mathcal {M}=(N,\mathcal {I})\,$ において, 階数関数 $\rho:2^N\to\mathbf {Z}\,$ を $\rho(X)=\max\{|I|\mid I\subseteq X,\,I\in \mathcal {I}\}\,$ で定めると, $(N,\rho)\,$ はポリマトロイドとなる.

エントロピー関数　有限アルファベットの離散確率変数の集合 $N\,$ に関して, 空でない部分集合 $X\subseteq N\,$ のエントロピーを $\eta(X)\,$ と書き, $\eta(\emptyset)=0\,$ と定めると, $(N,\eta)\,$ はポリマトロイドとなる.

　有限集合 $N\,$ 上の実数値関数全体のなす線型空間を $\mathbf {R}^N\,$ と表す. ベクトル $x\in\mathbf {R}^N\,$ は, 部分集合 $X\subseteq N\,$ に対して $\textstyle x(X)=\sum\{x(i)\mid i\in X\}\,$ と定義することによって, $x(\emptyset)=0\,$ であるようなモジュラ関数 $x\,$ と同一視される.劣モジュラシステム $(\mathcal {D},f)\,$ は, $\mathbf {R}^N\,$ 中の基多面体　(base polyhedron)

$\mbox{B}(f)=\{x\mid x\in\mathbf {R}^N,\;x(N)=f(N),\;\forall X\in\mathcal {D}: x(X)\leq f(X)\} \,$

を定める. 基 $x\in\mbox{B}(f)\,$ と相異なる $i,j\in N\,$ に対して,

$\tilde{c}(x,i,j)=\min\{f(X)-x(X)\mid i\in X\in\mathcal {D}, j\notin X\}\,$

で定義される量を交換容量と呼ぶ.

　基多面体上では, 貪欲アルゴリズムによって, 線型目的関数の最適化が可能である. 一般に, 楕円体法を通じて, 最適化問題と分離問題とが計算量の多項式性という観点からは等価であるという原理に基づいて, 強多項式時間で劣モジュラ関数の最小化が可能であることが示されている [3] . しかし, 楕円体法は実際上効率的とは言い難く, 組合せ的な多項式時間アルゴリズムの開発が望まれていた. 2000年前後に, Iwata-Fleischer-Fujishige[6]とSchrijver[7]によって独立に解決された.

　有向グラフ $G=(N,A)\,$ と, $f(N)=0\,$ を満たす $N\,$ 上の劣モジュラシステム $(\mathcal {D},f)\,$ を考える. 各枝 $a\,$ の始点を $\partial^+a\,$ , 終点を $\partial^-a\,$ と書き, $X\subseteq N\,$ から出る枝の集合を $\Delta^+X\,$ , 入る枝の集合を $\Delta^-X\,$ と表す. 任意の $\varphi\in\mathbf {R}^A\,$ に対して, 境界 $\partial\varphi\in\mathbf {R}^N\,$ を $\partial\varphi(X)=\varphi(\Delta^+X)-\varphi(\Delta^-X)\,$ で定める. 劣モジュラフロー問題 (submodular flow problem) とは, 枝流量の上下限 $\bar {c},\underline {c}\in\mathbf {R}^A\,$ と費用 $d\in\mathbf {R}^A\,$ が与えられたとき,

$\min\{\sum_{a\in A}d(a)\varphi(a)\mid\partial\varphi\in\mbox{B}(f),\; \forall a\in A: \underline {c}(a)\leq\varphi(a)\leq\bar {c}(a)\}\,$

を求める問題である [1] . 特に, $f\,$ がモジュラ関数の場合には, 最小費用フロー問題となることに注意する.

　劣モジュラフロー問題は, 任意の $X\in\mathcal {D}\,$ に対して $\underline {c}(\Delta^+X)-\bar {c}(\Delta^-X)\leq f(X)\,$ が成立するとき, かつそのときに限り, 実行可能解を有する. さらに, $\bar {c},\underline {c},f\,$ が整数値関数であれば, 整数実行可能解が存在する.

　実行可能解 $\varphi\,$ は, 以下の条件を満たす $p\in\mathbf {R}^N\,$ が存在するとき, かつそのときに限り, 最適解である. ただし, 各枝 $a\in A\,$ に対して $d_p(a)=d(a)+p(\partial^+a)-p(\partial^-a)\,$ と定める.

任意の $a\in A\,$ に対して, $d_p(a)>0\Rightarrow\varphi(a)=\underline {c}(a)\, \,$ , および $d_p(a)<0 \Rightarrow \varphi(a)=\bar {c}(a)\,$ .

任意の相異なる $i,j\in N\,$ に対して, $p(j)<p(i)\Rightarrow \tilde{c}(\partial\varphi,i,j)=0\,$ .

さらに, $d\,$ が整数値関数の場合には, $p\,$ を整数値関数に限ることができる.

　最小費用フロー問題の解法を一般化することによって, 劣モジュラフロー問題を解くアルゴリズムが提案されている [5] . これらの組合せ的なアルゴリズムは, いずれも劣モジュラシステム $(\mathcal {D},f)\,$ に関する交換容量を計算する手続きの存在を仮定している. 交換容量の計算は, 定義より明らかなように, 劣モジュラ関数の最小化になっており, 楕円体法を用いれば強多項式時間で可能なことが知られている. しかし, 劣モジュラフロー問題の応用に際しては, 問題の特殊性を活かした組合せ的な手続きが設計できる場合が少なくない.

　劣モジュラ関数 $f\,$ の最小値を達成する $X\in\mathcal {D}\,$ の全体は, $\mathcal {D}\,$ の部分分配束をなす. バーコフ(G. Birkhoff)の表現定理より, この部分分配束は $N\,$ の適当な部分集合への分割と各成分間の半順序関係によって表すことができる. この原理に基づいて劣モジュラ関数で記述された離散システムを分解する手法を総称して基本分割 (principal partition) と呼ぶ.

参考文献

[1] J. Edmonds and R. Giles, "A min-max relation for submodular functions on graphs," in Studies in Integer Programming, P. L. Hammer, E. L. Johnson, and B. H. Korte, eds., North-Holland, 185-204, 1977.

[2] S. Fujishige, Submodular Functions and Optimization, 2nd ed., Elsevier, 2005.

[3] M. Grötschel, L. Lov\'asz and A. Schrijver, Geometric Algorithms and Combinatorial Optimization, Springer-Verlag, 1988.

[4] 伊理正夫, 藤重悟, 大山逹雄, 『グラフ・ネットワーク・マトロイド』, 産業図書, 1986.

[5] 岩田覚, 「劣モジュラ流問題」, 藤重悟編　『離散構造とアルゴリズム Ⅵ』, 近代科学社, 第4章，127-170, 1999.

[6] S.Iwata, L.Fleischer and S.Fujishige, A combinatorial strongly polynomial algorithm for minimizing submodular functions, Journal of ACM 48 (2001) , 761--777.

[7] A.Schrijver, A combinatorial algorithm minimizing submodular functions in strongly polynomial time, Journal of Combinatorial Theory, Ser. B, 80 (2000) , 346--355.

「OR事典」の他の用語

グラフ･ネットワーク：

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

ジム・スタインマン

劣モジュラ最適化と同じ種類の言葉

最適化に関連する言葉

非線形最適化蟻コロニー最適化劣モジュラ最適化(れつもじゅらさいてきか) 制約なし最適化(せいやくなしさいてきか) 地理的最適化(ちりてきさいてきか)

>>同じ種類の言葉 >>コンピュータに関連する言葉

>> 「劣モジュラ最適化」を含む用語の索引
劣モジュラ最適化のページへのリンク

辞書ショートカット

1 OR事典

カテゴリ一覧

＋ビジネス

＋業界用語

＋コンピュータ

＋自動車・バイク

＋船

＋建築・不動産

＋ヘルスケア

＋スポーツ

＋辞書・百科事典

すべての辞書の索引

Weblioのサービス

「劣モジュラ最適化」の関連用語

1

アルゴリズム

12% |||||

2

組合せ最適化

百科事典

12% |||||

3

劣モジュラ関数

百科事典

10% |||||

劣モジュラ最適化のお隣キーワード

割当て市場ゲーム

加法型効用関数

加重平均資本コスト

劣モジュラシステム

劣モジュラフロー問題

劣モジュラ最適化

劣モジュラ関数

効率的フロンティア

効率的市場

検索ランキング

劣モジュラ最適化のページの著作権
Weblio 辞書情報提供元は参加元一覧にて確認できます。


	Copyright (C) 2025 （社）日本オペレーションズ・リサーチ学会 All rights reserved.

ビジネス｜業界用語｜コンピュータ｜電車｜自動車・バイク｜船｜工学｜建築・不動産｜学問
 文化｜生活｜ヘルスケア｜趣味｜スポーツ｜生物｜食品｜人名｜方言｜辞書・百科事典

ご利用にあたって

・Weblio辞書とは

・検索の仕方

・利用規約

・プライバシーポリシー

・サイトマップ

便利な機能

・ウェブリオのアプリ

・画像から探す

お問合せ・ご要望

・お問い合わせ

会社概要

・公式企業ページ

・会社情報

・採用情報

ウェブリオのサービス

・Weblio 辞書

・類語・対義語辞典

・英和辞典・和英辞典

・Weblio翻訳

・日中中日辞典

・日韓韓日辞典

・フランス語辞典

・インドネシア語辞典

・タイ語辞典

・ベトナム語辞典

・古語辞典

・おすすめのプログラミングスクール情報「Livifun」

©2025 GRAS Group, Inc.RSS