山川栄樹,阿部敦
並列計算機CM-5を用いた逐次線形化法に対する数値実験
Abstract:実際に現われる大規模非線形計画問題では、制約条件の大半が線形関数であり、その係数行列が疎であるという性質を持つ場合が多い。逐次線形化法(Successive Linearization Method)
は、反復計算の過程において原問題の疎な性質を保持することによって、現実の大規模問題を効率的に取扱おうとするアルゴリズムである[3]。逐次線形化法のアルゴリズムは、各反復で目的関数，制約条件の双方を線形近似することによって得られる部分問題を解く。ただし、大域的収束性を保証するために、部分問題の目的関数に凸2次項を付加することによって、ステップサイ
ズのコントロールを行う。その際、2次項を分離可能となるように構成すれば、得られた2次計画部分問題は、係数行列の各行ベクトルに対する簡単な演算のみで構成される所謂Row-Action Algorithmを少し修正することにより、効率的に解くことができる。
本論文の目的は、逐次線形化法の部分問題を解くために最も基本的な並列アルゴリズムの一つである射影Jacobi法を用い、これをSIMD(Single Instruction-Multiple Data)型の並列計算機上に実現して、逐次線形化法に対する並列アルゴリズム適用の有効性を数値実験を通して
検証することである。射影Jacobi法自体は、射影SOR(Successive Over Relaxation)法と
ともに線形相補性問題等に対するRow-Action Algorithmの一つとして、古くから研究されている［2]。逐次計算機上での実現を考える場合には、本質的に逐次的な手続きによって構成される
射影SOR法に比べて、射影Jacobi法は必ずしも優れた方法ではない。しかし、細粒度型の大規模並列計算機を用いる場合には、並列化度合が増すにつれて並列アルゴリズム本来の有効性を
発揮できるものと期待される。勿論、実際に十分な並列化効率を引出す為には、係数行列の大半の要素が零であるという現実の大規模問題特有の性質を十分に考慮して、プロセッサの割当てや
データの配置を行うことが必須条件となる。
以下では、先ず第2章において逐次線形化法のアルゴリズムとその性質について簡単に紹介
する。次に第3章において、2次計画部分問題を解くための射影Jacobi法について述べる。第4章では、射影Jacobi法を並列計算機上に実現するに際して、原問題の疎な性質をどのように
利用するかを中心に考える。テスト問題の生成方法と、並列計算機Connection Machine Model CM-5による数値実験結果については、第5章にまとめる。最後に第6章において、数値実験を通じて明らかになった問題点についての考察を行う。