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

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

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

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


線形計画問題を解く内点法のパッケージ開発のために必要な基礎研究を行った．大規模な問題を効率よく解くために，アルゴリズムの理論的な収束性の解析，初期内点の選び方，疎行列により表現される連立一次方程式の効率解法に関する研究を行った．
今年度は、特に初期点の選び方に関する研究を重点的に行った。そして、勝手な初期点を使うために、自己双対システムを使う方法を研究した。そのようなアプローチとして、Ye, Todd, Mizunoにより提案された方法と、Nesterov,Todd,Yeにより提案された異なる2つの方法があるが、その間の違いと共通点を明らかにした。そして、ある種の内点法では、2つの方法がまったく同じ点列を生成することを示した。
また、大規模な連立線形方程式を効率よく解くために、近似計算を使う内点法を提案し、その収束性を理論的に解析した。そして、非常にマイルドな条件のもとで、大域的に収束することを示すことができた。

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

N. Megiddo, S. Mizuno and T. Tsuchiya: A Modified Layered Step Interior-Point Methods for Linear Programming; Mathematical Programming, Vol.82, No.3 (1998) 339-355.
J. Stoer, M. Wechs, and S. Mizuno: High Order Infeasible-Interior-Point Methods for Solving Sufficient Linear Complementarity Problems; Mathematics of Operations Research, Vol.23, No. 4 (1998) 832-862 .
水野 眞治: ホモトピー法と内点法; 統計数理, Vol.46, No.2 (1998) 283-396.
土谷 隆：半正定値計画問題に対する主双対内点法の自己双対な探索方向族について、統計数理, Vol.46, No.2 (1998) 283-396.

S. Mizuno: Global Convergence of an Inexact Infeasible-Interior-Point Algorithm for LP; International Comference on NLP and VI, Hong Kong (December, 1998) .

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

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

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