「《劣モジュラ最適化》」の版間の差分

2007年7月6日 (金) 18:28時点における版

【れつもじゅらさいてきか (submodular optimization) 】

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

　有限集合構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle N\, } の部分集合族構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \mathcal {D}\subseteq 2^N\, } が, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \emptyset\, } と構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle N\, } を共に含み, 任意の構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle X,Y\in\mathcal {D}\, } に対して構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle X\cup Y, X\cap Y\in\mathcal {D}\, } を満たすものとする. このとき, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \mathcal {D}\, } は分配束をなす. 関数構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f:\mathcal {D}\to\mathbf {R}\, } が, 任意の構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle X,Y\in\mathcal {D}\, } に対して

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f(X)+f(Y)\geq f(X\cup Y)+f(X\cap Y)\, }

を満たすとき, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f\, } は劣モジュラ関数と呼ばれる. 不等号が常に等号で成立する場合には, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f\, } をモジュラ関数という. 分配束構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \mathcal {D}\, } と劣モジュラ関数構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f\, } の組 $({\mathcal {D}},f)\,$ は, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f(\emptyset)=0\, } のとき, 劣モジュラシステム (submodular system) と呼ばれる. さらに, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \mathcal {D}=2^N\, } であり, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f\, } が単調性を有するとき, すなわち任意の構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle X,Y\subseteq N\, } に対して構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle X\subseteq Y \Rightarrow f(X)\leq f(Y)\, } が成り立つとき, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (N,f)\, } をポリマトロイド (polymatroid)という.

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

カット容量関数　有向グラフ構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle G=(N,A)\, } において, 各枝構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle a\in A\, } に非負の容量構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle c(a)\, } が与えられているとき, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \kappa(X)=\sum\{c(a)\mid a\in \Delta^+X\}\, } で定義される容量関数構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \kappa:2^N\to\mathbf {R}\, } は, 劣モジュラ関数となる. ここで, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \Delta^+X\, } は, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle X\subseteq N\, } から出る枝の集合を表す.

マトロイド階数関数　マトロイド構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \mathcal {M}=(N,\mathcal {I})\, } において, 階数関数構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \rho:2^N\to\mathbf {Z}\, } を構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \rho(X)=\max\{|I|\mid I\subseteq X,\,I\in \mathcal {I}\}\, } で定めると, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (N,\rho)\, } はポリマトロイドとなる.

エントロピー関数　有限アルファベットの離散確率変数の集合構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle N\, } に関して, 空でない部分集合構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle X\subseteq N\, } のエントロピーを構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \eta(X)\, } と書き, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \eta(\emptyset)=0\, } と定めると, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (N,\eta)\, } はポリマトロイドとなる.

　有限集合構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle N\, } 上の実数値関数全体のなす線型空間を構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \mathbf {R}^N\, } と表す. ベクトル構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle x\in\mathbf {R}^N\, } は, 部分集合構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle X\subseteq N\, } に対して構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle x(X)=\sum\{x(i)\mid i\in X\}\, } と定義することによって, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle x(\emptyset)=0\, } であるようなモジュラ関数構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle x\, } と同一視される.劣モジュラシステム構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (\mathcal {D},f)\, } は, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \mathbf {R}^N\, } 中の基多面体　(base polyhedron)

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \mbox{B}(f)=\{x\mid x\in\mathbf {R}^N,\;x(N)=f(N),\;\forall X\in\mathcal {D}: x(X)\leq f(X)\} \, }

を定める. 基構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle x\in\mbox{B}(f)\, } と相異なる構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle i,j\in N\, } に対して,

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \tilde{c}(x,i,j)=\min\{f(X)-x(X)\mid i\in X\in\mathcal {D}, j\notin X\}\, }

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

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

　有向グラフ構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle G=(N,A)\, } と, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f(N)=0\, } を満たす構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle N\, } 上の劣モジュラシステム構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (\mathcal {D},f)\, } を考える. 各枝構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle a\, } の始点を構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \partial^+a\, } , 終点を構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \partial^-a\, } と書き, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle X\subseteq N\, } から出る枝の集合を構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \Delta^+X\, } , 入る枝の集合を構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \Delta^-X\, } と表す. 任意の構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \varphi\in\mathbf {R}^A\, } に対して, 境界構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \partial\varphi\in\mathbf {R}^N\, } を構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \partial\varphi(X)=\varphi(\Delta^+X)-\varphi(\Delta^-X)\, } で定める. 劣モジュラフロー問題 (submodular flow problem) とは, 枝流量の上下限構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \bar {c},\underline {c}\in\mathbf {R}^A\, } と費用構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle d\in\mathbf {R}^A\, } が与えられたとき,

構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \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] . 特に, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f\, } がモジュラ関数の場合には, 最小費用フロー問題となることに注意する.

　劣モジュラフロー問題は, 任意の構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle X\in\mathcal {D}\, } に対して構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \underline {c}(\Delta^+X)-\bar {c}(\Delta^-X)\leq f(X)\, } が成立するとき, かつそのときに限り, 実行可能解を有する. さらに, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \bar {c},\underline {c},f\, } が整数値関数であれば, 整数実行可能解が存在する.

　実行可能解構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \varphi\, } は, 以下の条件を満たす構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle p\in\mathbf {R}^N\, } が存在するとき, かつそのときに限り, 最適解である. ただし, 各枝構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle a\in A\, } に対して構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle d_p(a)=d(a)+p(\partial^+a)-p(\partial^-a)\, } と定める.

任意の構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle a\in A\, } に対して, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle d_p(a)>0\Rightarrow\varphi(a)=\underline {c}(a)\, \, } , および構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle d_p(a)<0 \Rightarrow \varphi(a)=\bar {c}(a)\, } .

任意の相異なる構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle i,j\in N\, } に対して, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle p(j)<p(i)\Rightarrow \tilde{c}(\partial\varphi,i,j)=0\, } .

さらに, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle d\, } が整数値関数の場合には, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle p\, } を整数値関数に限ることができる.

　最小費用フロー問題の解法を一般化することによって, 劣モジュラフロー問題を解くアルゴリズムが提案されている [5] . これらの組合せ的なアルゴリズムは, いずれも劣モジュラシステム構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle (\mathcal {D},f)\, } に関する交換容量を計算する手続きの存在を仮定している. 交換容量の計算は, 定義より明らかなように, 劣モジュラ関数の最小化になっており, 楕円体法を用いれば強多項式時間で可能なことが知られている. しかし, 劣モジュラフロー問題の応用に際しては, 問題の特殊性を活かした組合せ的な手続きが設計できる場合が少なくない.

　劣モジュラ関数構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle f\, } の最小値を達成する構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle X\in\mathcal {D}\, } の全体は, 構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \mathcal {D}\, } の部分分配束をなす. バーコフ(G. Birkhoff)の表現定理より, この部分分配束は構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle 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, North-Holland, 1991.

[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.

@@ 3行目: / 3行目: @@
 　[[劣モジュラ最適化]] (submodular optimization) とは, [[劣モジュラ関数]] (submodular function) を制約条件または目的関数に含んだ離散最適化を指す. 劣モジュラ最適化は, 非線型最適化における凸最適化のように, 離散最適化における基本的な位置を占めている.
-　有限集合 $<math>N</math>$ の部分集合族 $<math>\D\subseteq 2^N</math>$ が, $<math>\emptyset</math>$ と $<math>N</math>$ を共に含み, 任意の $<math>X,Y\in\D</math>$ に対して $<math>X\cup Y, X\cap Y\in\D</math>$ を満たすものとする. このとき, $<math>\D</math>$ は分配束をなす. 関数 $<math>f:\D\to\R</math>$ が, 任意の $<math>X,Y\in\D</math>$ に対して
+　有限集合 <math>N\, </math> の部分集合族 <math>\mathcal {D}\subseteq 2^N\, </math> が, <math>\emptyset\, </math> と <math>N\, </math> を共に含み, 任意の <math>X,Y\in\mathcal {D}\, </math> に対して <math>X\cup Y, X\cap Y\in\mathcal {D}\, </math> を満たすものとする. このとき, <math>\mathcal {D}\, </math> は分配束をなす. 関数 <math>f:\mathcal {D}\to\mathbf {R}\, </math> が, 任意の <math>X,Y\in\mathcal {D}\, </math> に対して
-:<math>f(X)+f(Y)\geq f(X\cup Y)+f(X\cap Y)</math>
+:<math>f(X)+f(Y)\geq f(X\cup Y)+f(X\cap Y)\, </math>
-を満たすとき, $<math>f</math>$ は劣モジュラ関数と呼ばれる. 不等号が常に等号で成立する場合には, $<math>f</math>$ をモジュラ関数という. 分配束 $<math>\D$</math> と劣モジュラ関数 $<math>f</math>$ の組 $<math>(\D,f)$</math> は, $<math>f(\emptyset)=0</math>$ のとき, [[劣モジュラシステム]] (submodular system) と呼ばれる. さらに, <math>$\D=2^N$</math> であり, $<math>f$</math> が単調性を有するとき, すなわち任意の $<math>X,Y\subseteq N$</math> に対して $<math>X\subseteq Y \Rightarrow f(X)\leq f(Y)</math>$ が成り立つとき, $<math>(N,f)$</math> を[[ポリマトロイド]] (polymatroid)という.
+を満たすとき, <math>f\, </math> は劣モジュラ関数と呼ばれる. 不等号が常に等号で成立する場合には, <math>f\, </math> をモジュラ関数という. 分配束 <math>\mathcal {D}\, </math> と劣モジュラ関数 <math>f\, </math> の組 <math>(\mathcal {D},f)\, </math> は, <math>f(\emptyset)=0\, </math> のとき, [[劣モジュラシステム]] (submodular system) と呼ばれる. さらに, <math>\mathcal {D}=2^N\, </math> であり, <math>f\, </math> が単調性を有するとき, すなわち任意の <math>X,Y\subseteq N\, </math> に対して <math>X\subseteq Y \Rightarrow f(X)\leq f(Y)\, </math> が成り立つとき, <math>(N,f)\, </math> を[[ポリマトロイド]] (polymatroid)という.
 　オペレーションズ・リサーチにおいて重要な劣モジュラ関数の代表的な例を以下に挙げる.
-'''カット容量関数'''　有向グラフ $<math>G=(N,A)$</math> において, 各枝 $<math>a\in A</math>$ に非負の容量 $<math>c(a)$</math> が与えられているとき, $<math>\kappa(X)=\sum\{c(a)\mid a\in \Delta^+X\}</math>$ で定義される容量関数 <math>$\kappa:2^N\to\R</math>$ は, 劣モジュラ関数となる. ここで, $<math>\Delta^+X</math>$ は, $<math>X\subseteq N</math>$ から出る枝の集合を表す.
+:'''カット容量関数'''　有向グラフ <math>G=(N,A)\, </math> において, 各枝 <math>a\in A\, </math> に非負の容量 <math>c(a)\, </math> が与えられているとき, <math>\kappa(X)=\sum\{c(a)\mid a\in \Delta^+X\}\, </math> で定義される容量関数 <math>\kappa:2^N\to\mathbf {R}\, </math> は, 劣モジュラ関数となる. ここで, <math>\Delta^+X\, </math> は, <math>X\subseteq N\, </math> から出る枝の集合を表す.
-'''マトロイド階数関数'''　マトロイド $<math>\M=(N,\I)$</math> において, 階数関数 $<math>\rho:2^N\to\Z$ を $\rho(X)=\max\{|I|\mid I\subseteq X,\,I\in \I\}</math>$ で定めると, $<math>(N,\rho)</math>$ はポリマトロイドとなる.
+:'''マトロイド階数関数'''　マトロイド <math>\mathcal {M}=(N,\mathcal {I})\, </math> において, 階数関数 <math>\rho:2^N\to\mathbf {Z}\, </math> を <math>\rho(X)=\max\{|I|\mid I\subseteq X,\,I\in \mathcal {I}\}\, </math> で定めると, <math>(N,\rho)\, </math> はポリマトロイドとなる.
-'''エントロピー関数'''　有限アルファベットの離散確率変数の集合 $<math>N</math>$ に関して, 空でない部分集合 $<math>X\subseteq N</math>$ のエントロピーを $<math>\eta(X)$</math> と書き, $<math>\eta(\emptyset)=0</math>$ と定めると, $<math>(N,\eta)</math>$ はポリマトロイドとなる.
+:'''エントロピー関数'''　有限アルファベットの離散確率変数の集合 <math>N\, </math> に関して, 空でない部分集合 <math>X\subseteq N\, </math> のエントロピーを <math>\eta(X)\, </math> と書き, <math>\eta(\emptyset)=0\, </math> と定めると, <math>(N,\eta)\, </math> はポリマトロイドとなる.
-　有限集合 $<math>N</math>$ 上の実数値関数全体のなす線型空間を $<math>\R^N</math>$ と表す. ベクトル $<math>x\in\R^N</math>$ は, 部分集合 $<math>X\subseteq N</math>$ に対して $<math>x(X)=\sum\{x(i)\mid i\in X\}</math>$ と定義することによって, $<math>x(\emptyset)=0</math>$ であるようなモジュラ関数 $<math>x</math>$ と同一視される.劣モジュラシステム $<math>(\D,f)</math>$ は, $<math>\R^N</math>$ 中の[[基多面体]]　(base polyhedron)
+　有限集合 <math>N\, </math> 上の実数値関数全体のなす線型空間を <math>\mathbf {R}^N\, </math> と表す. ベクトル <math>x\in\mathbf {R}^N\, </math> は, 部分集合 <math>X\subseteq N\, </math> に対して <math>x(X)=\sum\{x(i)\mid i\in X\}\, </math> と定義することによって, <math>x(\emptyset)=0\, </math> であるようなモジュラ関数 <math>x\, </math> と同一視される.劣モジュラシステム <math>(\mathcal {D},f)\, </math> は, <math>\mathbf {R}^N\, </math> 中の[[基多面体]]　(base polyhedron)
-:<math>\b(f)=\{x\mid x\in\R^N,\;x(N)=f(N),\;\forall X\in\D: x(X)\leq f(X)\} </math>
+:<math>\mbox{B}(f)=\{x\mid x\in\mathbf {R}^N,\;x(N)=f(N),\;\forall X\in\mathcal {D}: x(X)\leq f(X)\} \, </math>
-を定める. 基 $<math>x\in\b(f)</math>$ と相異なる $<math>i,j\in N</math>$ に対して,
+を定める. 基 <math>x\in\mbox{B}(f)\, </math> と相異なる <math>i,j\in N\, </math> に対して,
-:<math>\tilde{c}(x,i,j)=\min\{f(X)-x(X)\mid i\in X\in\D, j\notin X\}</math>
+:<math>\tilde{c}(x,i,j)=\min\{f(X)-x(X)\mid i\in X\in\mathcal {D}, j\notin X\}\, </math>
@@ 36行目: / 36行目: @@
 　基多面体上では, 貪欲アルゴリズムによって, 線型目的関数の最適化が可能である. 一般に, 楕円体法を通じて, 最適化問題と分離問題とが計算量の多項式性という観点からは等価であるという原理に基づいて, 強多項式時間で劣モジュラ関数の最小化が可能であることが示されている [3] . しかし, 楕円体法は実際上効率的とは言い難く, 組合せ的な多項式時間アルゴリズムの開発が望まれている. (ごく最近, Iwata-Fleischer-FujishigeとSchrijverによって独立に解決された. )
-　有向グラフ $<math>G=(N,A)</math>$ と, $<math>f(N)=0</math>$ を満たす $<math>N</math>$ 上の劣モジュラシステム $<math>(\D,f)</math>$ を考える. 各枝 $<math>a</math>$ の始点を $<math>\partial^+a</math>$, 終点を $<math>\partial^-a</math>$ と書き, $<math>X\subseteq N</math>$ から出る枝の集合を $<math>\Delta^+X</math>$, 入る枝の集合を $<math>\Delta^-X</math>$ と表す. 任意の $<math>\varphi\in\R^A</math>$ に対して, 境界 $<math>\partial\varphi\in\R^N</math>$ を $<math>\partial\varphi(X)=\varphi(\Delta^+X)-\varphi(\Delta^-X)</math>$ で定める. [[劣モジュラフロー問題]] (submodular flow problem) とは, 枝流量の上下限 $<math>\uc,\lc\in\R^A</math>$ と費用 $<math>d\in\R^A</math>$ が与えられたとき,
+　有向グラフ <math>G=(N,A)\, </math> と, <math>f(N)=0\, </math> を満たす <math>N\, </math> 上の劣モジュラシステム <math>(\mathcal {D},f)\, </math> を考える. 各枝 <math>a\, </math> の始点を <math>\partial^+a\, </math>, 終点を <math>\partial^-a\, </math> と書き, <math>X\subseteq N\, </math> から出る枝の集合を <math>\Delta^+X\, </math>, 入る枝の集合を <math>\Delta^-X\, </math> と表す. 任意の <math>\varphi\in\mathbf {R}^A\, </math> に対して, 境界 <math>\partial\varphi\in\mathbf {R}^N\, </math> を <math>\partial\varphi(X)=\varphi(\Delta^+X)-\varphi(\Delta^-X)\, </math> で定める. [[劣モジュラフロー問題]] (submodular flow problem) とは, 枝流量の上下限 <math>\bar {c},\underline {c}\in\mathbf {R}^A\, </math> と費用 <math>d\in\mathbf {R}^A\, </math> が与えられたとき,
-:<math>\min\{\sum_{a\in A}d(a)\varphi(a)\mid\partial\varphi\in\b(f),\;
+:<math>\min\{\sum_{a\in A}d(a)\varphi(a)\mid\partial\varphi\in\mbox{B}(f),\;
-\forall a\in A: \lc(a)\leq\varphi(a)\leq\uc(a)\}</math>
+\forall a\in A: \underline {c}(a)\leq\varphi(a)\leq\bar {c}(a)\}\, </math>
-を求める問題である [1] . 特に, $<math>f</math>$ がモジュラ関数の場合には, 最小費用フロー問題となることに注意する.
+を求める問題である [1] . 特に, <math>f\, </math> がモジュラ関数の場合には, 最小費用フロー問題となることに注意する.
-　劣モジュラフロー問題は, 任意の $<math>X\in\D</math>$ に対して$<math>\lc(\Delta^+X)-\uc(\Delta^-X)\leq f(X)</math>$ が成立するとき, かつそのときに限り, 実行可能解を有する. さらに, $<math>\uc,\lc,f</math>$ が整数値関数であれば, 整数実行可能解が存在する.
+　劣モジュラフロー問題は, 任意の <math>X\in\mathcal {D}\, </math> に対して<math>\underline {c}(\Delta^+X)-\bar {c}(\Delta^-X)\leq f(X)\, </math> が成立するとき, かつそのときに限り, 実行可能解を有する. さらに, <math>\bar {c},\underline {c},f\, </math> が整数値関数であれば, 整数実行可能解が存在する.
-　実行可能解 $<math>\varphi</math>$ は, 以下の条件を満たす $<math>p\in\R^N</math>$ が存在するとき, かつそのときに限り, 最適解である. ただし, 各枝 $<math>a\in A</math>$ に対して$<math>d_p(a)=d(a)+p(\partial^+a)-p(\partial^-a)</math>$ と定める.
+　実行可能解 <math>\varphi\, </math> は, 以下の条件を満たす <math>p\in\mathbf {R}^N\, </math> が存在するとき, かつそのときに限り, 最適解である. ただし, 各枝 <math>a\in A\, </math> に対して<math>d_p(a)=d(a)+p(\partial^+a)-p(\partial^-a)\, </math> と定める.
-*任意の $<math>a\in A</math>$ に対して, $<math>d_p(a)>0\Rightarrow\varphi(a)=\lc(a)</math>$, および$<math>d_p(a)<0 \Rightarrow \varphi(a)=\uc(a)</math>$.
+*任意の <math>a\in A\, </math> に対して, <math>d_p(a)>0\Rightarrow\varphi(a)=\underline {c}(a)\, \, </math>, および<math>d_p(a)<0 \Rightarrow \varphi(a)=\bar {c}(a)\, </math>.
-*任意の相異なる $<math>i,j\in N</math>$ に対して, $<math>p(j)<p(i)\Rightarrow \tilde{c}(\partial\varphi,i,j)=0</math>$.
+*任意の相異なる <math>i,j\in N\, </math> に対して, <math>p(j)<p(i)\Rightarrow \tilde{c}(\partial\varphi,i,j)=0\, </math>.
-さらに, $<math>d</math>$ が整数値関数の場合には, $<math>p</math>$ を整数値関数に限ることができる.
+さらに, <math>d\, </math> が整数値関数の場合には, <math>p\, </math> を整数値関数に限ることができる.
-　最小費用フロー問題の解法を一般化することによって, 劣モジュラフロー問題を解くアルゴリズムが提案されている [5] . これらの組合せ的なアルゴリズムは, いずれも劣モジュラシステム $<math>(\D,f)</math>$ に関する交換容量を計算する手続きの存在を仮定している. 交換容量の計算は, 定義より明らかなように, 劣モジュラ関数の最小化になっており, 楕円体法を用いれば強多項式時間で可能なことが知られている. しかし, 劣モジュラフロー問題の応用に際しては, 問題の特殊性を活かした組合せ的な手続きが設計できる場合が少なくない.
+　最小費用フロー問題の解法を一般化することによって, 劣モジュラフロー問題を解くアルゴリズムが提案されている [5] . これらの組合せ的なアルゴリズムは, いずれも劣モジュラシステム <math>(\mathcal {D},f)\, </math> に関する交換容量を計算する手続きの存在を仮定している. 交換容量の計算は, 定義より明らかなように, 劣モジュラ関数の最小化になっており, 楕円体法を用いれば強多項式時間で可能なことが知られている. しかし, 劣モジュラフロー問題の応用に際しては, 問題の特殊性を活かした組合せ的な手続きが設計できる場合が少なくない.
-　劣モジュラ関数 <math>$f</math>$ の最小値を達成する $<math>X\in\D</math>$ の全体は, $<math>\D</math>$ の部分分配束をなす. バーコフ(G. Birkhoff)の表現定理より, この部分分配束は $<math>N</math>$ の適当な部分集合への分割と各成分間の半順序関係によって表すことができる. この原理に基づいて劣モジュラ関数で記述された離散システムを分解する手法を総称して[[基本分割]] (principal partition) と呼ぶ.
+　劣モジュラ関数 <math>f\, </math> の最小値を達成する <math>X\in\mathcal {D}\, </math> の全体は, <math>\mathcal {D}\, </math> の部分分配束をなす. バーコフ(G. Birkhoff)の表現定理より, この部分分配束は <math>N\, </math> の適当な部分集合への分割と各成分間の半順序関係によって表すことができる. この原理に基づいて劣モジュラ関数で記述された離散システムを分解する手法を総称して[[基本分割]] (principal partition) と呼ぶ.

「《劣モジュラ最適化》」の版間の差分

2007年7月6日 (金) 18:28時点における版

案内メニュー

検索