半正定値計画問題に対する高速数値計算手法に関する基礎研究

点击翻译按钮获取中文摘要

本研究の目的『主双対内点法を半正定値計画問題を解く実用的な数値解法として発展させる』に沿って以下の研究を行った.1.研究代表者の小島等のグループが提案した線形計画問題の高速解法を半正定値計画問題に拡張し,その実験用ソフトウエアをMathematicaを用いて試作し,Power Machintosh状で改良のための数値実験を行った.2.上記1で試作したソフトウエアを改良し,C++言語で書き直し,3種類のワークステイションSPARC Station,Silicon Graphis,SONY RISC NEWSに実装した.この際,大規模な半正定値計画問題を計算効率よく高速に解くため,過疎なデータ構造を扱えるような工夫を組み込んだ.このソフトウエアは誰でも使えるように公開している.3.上記2のソフトウエアを組み合わせ最適化問題(グラフ分割問題,2次割り当て問題,最大クリーク問題等)や非凸2次計画問題から生ずるさまざまな半正定値計画問題に適用し,計算実験を続けている.4.これまでの実験を等して,提案した方法は局所的な収束性に難があることが判明した.これを改良するために2つの方法(a)予測子修正子法の組み込み(b)新しい探索方向を提案し,その理論的な基礎作りをした。