decomposition method for large-scale problemsとは何？わかりやすく解説 Weblio辞書

大規模問題の分解法

読み方：だいきぼもんだいのぶんかいほう
【英】：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事典」の他の用語

非線形計画：

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

Weblio日本語例文用例辞書

索引トップ用語の索引ランキング

「decomposition method for large-scale problems」の例文・使い方・用例・文例

「資格商法」とは文字通りには「qualification selling method」という意味であり、根拠のない資格や学位を法外な値段で売る詐欺的ビジネスである。
5 月15 日の午前 8 時30 分から午後 3 時まで、Oceanview 公園で開催される、毎年恒例のWalk for Petsについてのお知らせです。
イベントによる収益金の半分は、捨てられたペットのための保護施設であるHome for Petsに使われ、残りはさまざまな動物福祉団体に分配されます。
年次監査を行うために、Bradford and Partnersの会計士たちが10 月10 日の午前 10 時に当社を訪ねてくる予定です。
Bradfordの新人会計士2 名が今年の監査を担当すると連絡がありました。
こんにちは、Bradfordさん。
昨日 Bradfordさんが受け取られたデスクランプについてお電話を差し上げています。
取り違えてしまって申し訳ありませんが、あのランプは別のお客様に送られるはずのもので、誤って Bradfordさんに配送されました。
Bradfordさんが受け取るはずだった商品は、Anne Keeganさんからの贈り物のご注文でした。
タックマンモデルとは、チームビルディングにおける5段階、すなわち形成(Forming)、混乱(Storming)、統一(Norming)、機能(Performing)、散会(Adjourning)を示すモデルである。
着手する; 〔…の〕端緒を開く〔for〕.
紺《Oxford 大学およびその選手の色標》.
〔音楽会などへの〕優待券, 招待券〔to, for〕.
等位接続詞《and, but, or, for など; ⇔subordinate conjunction》.
【文法】相関語《either と or, the former と the latter など》.
[for a] holiday to [in] France last year. 昨年は休暇をとってフランスへ旅行した.
(最も奥の), foremost (真っ先の).
新大学, 1960 年以降に創設された大学, 板ガラス大学《Oxford, Cambridge のような石造りの ancient universities, 19 世紀に創設された London 大学のような赤れんが造りの redbrick universities に対して言う; 建築様式がふんだんに plate glass を使ってモダンなことから》.
コンセプション岬《California 州にある》.
être for this policy? この政策はどんな存在理由があるのか.

Weblio日本語例文用例辞書はプログラムで機械的に例文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。

>> 「decomposition method for large-scale problems」を含む用語の索引
decomposition method for large-scale problemsのページへのリンク


	Copyright (C) 2024 （社）日本オペレーションズ・リサーチ学会 All rights reserved.
TANAKA Corpus	Tanaka Corpusのコンテンツは、特に明示されている場合を除いて、次のライセンスに従います： Creative Commons Attribution (CC-BY) 2.0 France.
京大-NICT 日英中基本文データ	この対訳データはCreative Commons Attribution 3.0 Unportedでライセンスされています。
	Copyright © 1995-2024 Hamajima Shoten, Publishers. All rights reserved.
	Copyright © Benesse Holdings, Inc. All rights reserved.
	Copyright (c) 1995-2024 Kenkyusha Co., Ltd. All rights reserved.
	日本語ワードネット1.1版 (C) 情報通信研究機構, 2009-2010 License All rights reserved. WordNet 3.0 Copyright 2006 by Princeton University. All rights reserved. License
	Copyright (C) 1994- Nichigai Associates, Inc., All rights reserved. 「斎藤和英大辞典」斎藤秀三郎著、日外アソシエーツ辞書編集部編
	This page uses the JMdict dictionary files. These files are the property of the Electronic Dictionary Research and Development Group, and are used in conformance with the Group's licence.

decomposition method for large-scale problemsとは？ わかりやすく解説

大規模問題の分解法

概要

詳説

「decomposition method for large-scale problems」の例文・使い方・用例・文例

decomposition method for large-scale problemsとは？わかりやすく解説