大規模問題の分解法とは？わかりやすく解説

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

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

Weblio 辞書ヘルプ

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

無料の翻訳ならWeblio翻訳！

初めての方へ参加元一覧

Weblio 辞書 > 学問 > OR事典 > 大規模問題の分解法の意味・解説

OR事典

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

大規模問題の分解法

読み方：だいきぼもんだいのぶんかいほう
【英】：decomposition method for large-scale problems

概要

非常に多くの変数や制約条件をもつ最適化問題を, 一部の変数または制約条件だけから成る小さな部分問題の列に変換して解く方法. その多くは, 現実の大規模問題がしばしばもつブロック構造を利用している. 単に大規模問題が実際に解けるようになるだけでなく, もとの問題には見られなかった特徴的な構造が部分問題に現れて, 取り扱いが容易になる場合がある. 特に, 各部分問題が独立に解ける場合には, 並列アルゴリズムを構成する有力な手段となる.

詳説

　現実世界で発生する複雑な問題を最適化問題としてモデル化すると，非常に多くの変数や制約条件をもつ大規模問題になることが多い．計算機を用いてその解を求める場合，目的関数や制約条件式がすべて線形であっても，変数や制約条件の数が増えるとともに計算時間は急激に増加する．また，それらの一部に非線形の項が含まれると，問題の解きにくさは飛躍的に増大する．そこで，大規模問題を直接解くのではなく，一部の変数や制約条件だけから成る小規模な，または，解きやすい部分問題を逐次解くことにより，もとの問題の解を得ようとするアルゴリズムが提案されている．それらを一般に大規模問題の分解法 (decomposition method for large-scale problems) と呼ぶ [3]．

　現実の大規模問題は，しばしば特徴的なブロック構造をもつ．たとえば， $n\,$ 個の比較的独立な部分から成るシステムが共通の変数 $x_{0}\,$ を含む場合は，

$\begin{array}{llrll} \mbox{min.} & f_{0}(x_{0}) + & \sum_{j=1}^{n} f_{j}(x_{j})\\ \mbox{s. t.} & g_{0}(x_{0}) & & \leq 0, \\ & g_{j}(x_{0}) + & h_{j}(x_{j}) & \leq 0 & (j = 1, \ldots, n), \end{array}\,$

$(1) \,$

という最適化問題が得られる．この問題は，変数 $x_{0}\,$ を一時的に固定すると，

$\mbox{min.} \quad f_{j}(x_{j}) \quad \mbox{s. t.} \quad g_{j}(x_{0}) + h_{j}(x_{j}) \leq 0, \,$

$(2) \,$

という $n\,$ 個の部分問題に分解される．ベンダース分解法 (Benders decomposition method) はこのような性質を利用しており，関数 $f_{j}\,$ , $h_{j}\,$ が線形ならば，有限回の反復でもとの問題の解に到達できることが知られている．さらに，分解された部分問題はたがいに独立であり，それらは比較的大きい（粒度が粗い）問題となるため， MIMD (multiple instruction stream multiple data stream) 型の並列計算機で効率よく実行できる．

　また，システム全体にまたがる付加的な制約条件が存在する場合は，

$\begin{array}{lrll} \mbox{min.} & f_{0}(x_{0}) + \sum_{j=1}^{n} f_{j}(x_{j}) & & \\ \mbox{s. t.} & g_{0}(x_{0}) + \sum_{j=1}^{n} g_{j}(x_{j}) & \leq 0, \\ & h_{j}(x_{j}) & \leq 0 & (j = 1, \ldots, n), \end{array}\,$

$(3) \,$

という最適化問題が得られるが， $g_{j}\,$ を含む制約条件をラグランジュ緩和により目的関数に組み込み, さらに変数 $x_0\,$ を一時的に固定すると, 問題 (2) に類似した $n\,$ 個の独立な部分問題に分解される．とくにすべての関数が線形ならば，問題 (3) は部分問題の解を用いて効率的に解けることが知られており，ダンツィク・ウルフ分解法 (Dantzig-Wolfe decomposition method) と呼ばれている．

　一方，大規模で複雑な問題から取り扱いやすい構造をもつ部分のみを抽出して部分問題を構成し，これを逐次解くことによりもとの問題の解を得ようとする方法は，分割法 (splitting method) と呼ばれている．分割法は，問題 (1) や (3) のようなブロック構造をもたない問題にも適用可能である．また，並列処理可能な部分問題を構成すれば，それらはしばしば小規模な（粒度の細かい）問題となり，SIMD (single instruction stream multiple data stream) 型の大規模並列計算機を用いて効率的に実行できる．

　分割法は，線形方程式に対する反復法として，線形代数の分野において古くから研究されている．行列 $M\,$ とベクトル $q\,$ により定義される線形方程式

$M x + q = 0\,$

に対して，条件 $M = B + C\,$ を満たす行列 $B\,$ , $C\,$ を選び，方程式

$B x + C x^{(k)} + q = 0 \,$

$(4) \,$

の解を $x^{(k+1)}\,$ とおくことにより点列 $\{ x^{(k)} \}\,$ を生成する方法は，行列分割法 (matrix splitting method) と呼ばれる．行列 $B\,$ を (ブロック) 対角行列に選べば方程式 (4) は並列的に解けるので，大規模問題に対する効率的な解法を得る．行列分割法は，線形相補性問題や線形変分不等式問題にも拡張できる．

　一般の凸計画問題に対しても，分割法に基づくアルゴリズムを構成できる．凸計画問題は，最適性条件を考慮すると，ある写像 $F: \mathbf{R}^{n} \rightarrow \mathbf{R}^{n}\,$ を用いて

$\mbox{find} \quad x \in \mathbf{R}^{n} \quad \mbox{s. t.} \quad 0 \in F(x), \,$

$(5) \,$

と記述される．条件 $F = G + H\,$ を満たす写像 $G\,$ , $H\,$ を選び，部分問題

$\mbox{find} \quad x \in \mathbf{R}^{n} \quad \mbox{s. t.} \quad 0 \in G(x) + H(x^{(k)}), \,$

$(6) \,$

の解を $x^{(k+1)}\,$ とする反復法は，作用素分割法 (operator splitting method) と呼ばれる．写像 $G\,$ が分離可能ならば部分問題 (6) は並列的に解けるので，大規模な凸計画問題に対する効率的な解法が得られる．

　問題 (5) に対する有力な反復法に，近接点法 (proximal point method) がある．近接点法では，単調非減少な正定数の列 $\{ \lambda^{(k)} \}\,$ を定め，問題

$\mbox{find} \quad x \in \mathbf{R}^{n} \quad \mbox{s. t.} \quad ( x^{(k)} - x ) \, / \, \lambda^{(k)} \in F(x),\,$

の解を $x^{(k+1)}\,$ とおく．作用素分割法や近接点法は，一般的な最適化問題のクラスである変分不等式問題にも拡張できる．また，これらの方法を組合せることによりさまざまな並列アルゴリズム(parallel algorithm (nonlinear programming)) を構成できることが知られている．このような考え方に基づく並列アルゴリズムについては，参考文献 [1, 2, 4] に詳しい解説がある．

参考文献

[1] D. P. Bertsekas and J. N. Tsitsiklis, Parallel and Distributed Computation: Numerical Methods, Prentice-Hall, 1989.

[2] Y. Censor and S. A. Zenios, Parallel Optimization: Theory, Algorithms, and Applications, Oxford University Press, 1997.

[3] J. F. Shapiro, Mathematical Programming: Structures and Algorithms, John Wiley & Sons, 1979.

[4] 山下栄樹，福島雅夫，「数理計画における並列計算」，朝倉書店，2001．

「OR事典」の他の用語

非線形計画：

大域的収束性大域的最適化大域的最適解大規模問題の分解法安定性理論実行可能集合局所的最適解

>> 「大規模問題の分解法」を含む用語の索引
大規模問題の分解法のページへのリンク

辞書ショートカット

1 OR事典

カテゴリ一覧

＋ビジネス

＋業界用語

＋コンピュータ

＋自動車・バイク

＋船

＋建築・不動産

＋ヘルスケア

＋スポーツ

＋辞書・百科事典

すべての辞書の索引

Weblioのサービス

大規模問題の分解法のお隣キーワード

大域最適解

大域的収束性

大域的最適化

大域的最適解

大数の法則

大規模問題の分解法

大選挙区制

天候デリバティブ

季節調整法

検索ランキング

大規模問題の分解法のページの著作権
Weblio 辞書情報提供元は参加元一覧にて確認できます。


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

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

ご利用にあたって

・Weblio辞書とは

・検索の仕方

・利用規約

・プライバシーポリシー

・サイトマップ

便利な機能

・ウェブリオのアプリ

・画像から探す

お問合せ・ご要望

・お問い合わせ

会社概要

・公式企業ページ

・会社情報

・採用情報

ウェブリオのサービス

・Weblio 辞書

・類語・対義語辞典

・英和辞典・和英辞典

・Weblio翻訳

・日中中日辞典

・日韓韓日辞典

・フランス語辞典

・インドネシア語辞典

・タイ語辞典

・ベトナム語辞典

・古語辞典

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

©2025 GRAS Group, Inc.RSS