【研究分野】社会システム工学

【研究領域課題番号】11680441 (KAKENデータベースで見る）

【研究キーワード】

半正定値計画問題 / 非凸型最適化問題 / 2次計画問題 / 緩和 / 数理計画法 / 組合せ最適化 / 主双対内点法

【研究成果の概要】

主として以下の課題(a)および(b)に関して研究を行った.
(a)逐次半正定値計画緩和の並列計算アルゴリズムを実装し,その数値計算実験を大規模に行った.その結果,計算時間においては最大128台のCPUを並列に稼動し,約100倍の高速化を実現した.問題の規模も従来の単一CPUによる計算アルゴリズムでは解き得なかった大規模な問題を扱うことが出来た.さらに,ほとんどの問題において精度の高い近似最適値が得られた.これにより,2年間の研究で設定した研究成果が得られたと言って良い.
(b)より大規模な問題に計算効率よく逐次半正定値緩和を適用するために,半正定値計画問題に対する計算手法そのものを高速化する研究を行い予備実験を行った.その結果,特殊な疎なデータ構造を持つ問題に対しては,提案した方法が極めて有効に働くことを検証した.

【研究種目】基盤研究(C)

【研究期間】1999 - 2000

【配分額】3,300千円 (直接経費: 3,300千円)