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

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

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

大規模な最適化問題を計算機で効率よく解くソフトウエア・パッケージの開発を目的とする。そのパッケージには，アフィンスケーリング法と主双対内点法に基づくアルゴリズムを含む。対象とする最適化問題は，線形計画問題，二次計画問題，線形相補性問題である。


線形計画問題を解く内点法のパッケージ開発のために必要な基礎研究を行った．特に大規模な問題を効率よく解くために，アルゴリズムの理論的な収束性の解析，初期内点の選び方，疎行列により表現される連立一次方程式の効率解法に関する研究を行った．
アルゴリズムの収束性については，大域的な収束性，多項式オーダ性，局所的超一次収束に関する研究をおこなった。また、実際の数値計算では連立方程式を正確に解くことが困難であることから、近似計算を使った場合についてその収束性を解析した。その結果、連立方程式を不正確に解いても内点法として大域的に収束し、解を求められることが判明した。また、多項式オーダで収束するために必要な連立方程式の解の精度を明らかにした。
さらに、内点法の収束速度を高めるために層分割を使ったアルゴリズムを研究した。このアルゴリズムは、未知のおおきな定数の値を前もって求める必要があり、実際に適用する上で大きな障害となっていた。このような未知数を必要としない新しいアルゴリズムを開発し、その収束速度を求めた。

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

S. Mizuno, and F. Jarre, Global and Polynomial-Time Convergence of an Infeasible-Interior-Point ALgorithm Using Inexact Computation, Research Memorandum 605, (1996).
S. Mizuno, N. Megiddo, and T. Tsichiya, A Linear Programming Instance with many crossover events, IBM Research Report, (1995)
水野真治、離散構造とアルゴリズム４第2章線形相補性問題の内点法、近代科学社1995
吉瀬章子、小島政和、N.Megiddo,水野真治、野間俊人、線形計画問題に対する主双対内点法とその相補性問題への拡張、日本オペレーションズリサーチ学会研究発表会，1995年10月

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

最適化問題を解く内点法の研究と新しいアルゴリズムの開発を行う。そして，アルゴリズムの収束性を理論的に明らかにする。また，計算効率をあげるための数値計算法と大規模スペース行列の研究を行う。
ソフトウエア・パッケージの開発に統計数理研究所の計算機を利用する。統計数理研究所の教官と共同して行い，２ヶ月に１回程度セミナーを統計数理研究所または所外の参加者の所属する大学で行う。また，外国人研究員Florian Jarreとは，e-mailを通じて情報交換と研究を行う。

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