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

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

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

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


線形計画問題を解く内点法のパッケージ開発のために必要な基礎研究を行った．特に大規模な問題を効率よく解くために，アルゴリズムの理論的な収束性の解析，初期内点の選び方，疎行列により表現される連立一次方程式の効率解法に関する研究を行った．
センターパスを追跡する新しい内点法を提案した．その特徴は，センターパスを高次のオーダーで近似することである．その結果，提案した方法が局所的に解へ超一次収束することを明らかにした．
また，線形計画問題を解く内点法と方程式系を解く不動点アルゴリズムの関係を調べ、インフィーシブル内点法が一種の不動点アルゴリズムとなることを示した．

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

J. Stoer, M. Wechs, and S. Mizuno: High Order Infeasible-Interior-Point Methods for Solving Sufficient Linear Complementarity Problems; to appear in Mathematics of Operations Research.
水野 眞治: 不動点アルゴリズムと内点法; 統計数理に投稿中

S. Mizuno and F. Jarre: Global and Polynomial-Time Convergence of an Infeasible-Interior-Point Algotithm using Inexact Computation; 16th International Symposium on Mathematical Programming, Lausanne, Switzerland (August 24-29, 1997).

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

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

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