平成6（1994）年度　共同研究Ｂ実施報告書

課題番号	6−共研−1			専門分類		2
研究課題名	内点法による最適化パッケージの開発
フリガナ 代表者氏名	ミズノ　シンジ 水野　眞治			ローマ字
所属機関	統計数理研究所
所属部局	予測制御研究系
職　　名	助教授
所在地
TEL				FAX
E-mail
URL
配分経費	研究費	0千円	旅　費		0千円		研究参加者数	7　人

研究目的と成果（経過）の概要

大規模な最適化問題を計算機で効率よく解く内点法によるソフトウェア・パッケージの開発を行う。


線形計画問題を解く内点法のパッケージ開発のために必要な基礎研究を行った．特に大規模な問題を効率よく解くために，アルゴリズムの理論的な収束性の解析，初期内点の選び方，疎行列により表現される連立一次方程式の効率解法に関する研究を行った．
アルゴリズムの収束性については，大域的な収束性，多項式オーダ性，局所的超一次収束に関する研究をおこなった．内点法の初期点とし実行可能内点を選ぶと理論的に収束性がよいけれども，そのためには人工問題を使う必要がある．しかし，人工問題を使うと，問題の規模が大きくなる，あるいはビッグエムと呼ばれる大きな係数を必要とするために実際の計算効率が悪くなる．
そこで，実行可能とは限らない初期点を使うが，人工問題を必要としないインフィージブル内点法について，その収束性に関する研究を行った．疎行列で表現される連立一次方程式の解法については，QM分解を使う方法を採用し，その理論的な解析を行った．
また，凸集合への直交射影を使うことにより，センターパスの近接点に戻る新しいアルゴリズムを提案し，そのアルゴリズムの収束性について理論的に解析した．

当該研究に関する情報源（論文発表、学会発表、プレプリント、ホームページ等）

S. Mizuno, F. Jarre, and J. Stoer, A Unified Approach to Infeasible-Interior- Point Algorithms via Geometrical Linear Complementarity Problems, to appear in Applied Mathematics and Optimization
F. Jarre et al., A QMR-based Interior-Point Algorithm for Solving Linear Programs, Research Memorandum, (1995).

S. Mizuno and F. Jarre: An Infeasible-Interior-Point Algorithms Using Projections onto a Convex Set, 15th International Symposium on Mathematical Programming, August 1995.

研究会を開催した場合は、テーマ・日時・場所・参加者数を記入してください。

線形・非線形計画問題を解く内点法の研究と新しいアルゴリズムの開発を行う。また、計算効率をあげるための数値計算法と大規模スパース行列の研究を行う。ソフトウェア・パッケージの開発に統計数理研究所の計算機を利用し、月１回程度セミナーを統数研において開催する。

研究参加者一覧
氏名	所属機関
小島　政和	東京工業大学
田辺　國士	統計数理研究所
土谷　隆	統計数理研究所
野間　俊人	防衛庁
Jarre　Florian	Wurzburg University
吉瀬　章子	筑波大学