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

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

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

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


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

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

S. Mizuno, F. Jarre, and J. Stoer: A Unified Approach to Infeasible-Interior-Point Algorithms via Geometrical Linear Complementarity Problems: Applied Mathematics and Optimization Vol. 33, No.3(May, 1996) 315-341.
S. Mizuno and F. Jarre: An Infeasible-Interior-point Algorithm Using Projections onto a Convex Set; Annals of Operations Research Vol.21, No.2(May 1996) 382-400.
S. Mizuno: Infeasible-Interior-Point Algorithms; in T. Terlaky ed., Interior Point Methods in Mathematical Programming, Kluwer Academic Publishers(1996).
S. Mizuno and F. Jarre: Global and Polynomial-Time Convergence of an Infeasible-Interior-Point Algorithm using Inexact Computation; International Symposium on Optimization and Computation, Hayama, Japan, (August 12-16, 1996).

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

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

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