平成17（2005）年度　一般研究２実施報告書

課題番号	17−共研−2020			専門分類		2
研究課題名	線形計画問題および半正定値計画問題に対する数値解法の基礎的研究
フリガナ 代表者氏名	ツチヤ　タカシ 土谷　隆			ローマ字		Tsuchiya Takashi
所属機関	統計数理研究所
所属部局	数理・推論研究系
職　　名	教授
所在地
TEL				FAX
E-mail
URL
配分経費	研究費	0千円	旅　費		0千円		研究参加者数	2　人

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

「21世紀の線形計画問題」と呼ばれる一連の凸最適化問題のクラス, 半正定値計画問題および2次錐計画問題に対し, 内点法と呼ばれる多項式解法が確立されたことは, 最近の最適化の大きな進歩の一つである. これらは新たに登場した, 強力で柔軟なモデリングの手段であり, 統計科学や信号処理, パターン認識, ロバスト最適化, 制御, 最適設計などへの応用が現在活発に進められている. これらの最適化問題に対してより強力な解法が得られれば, 我々が用いることができるモデルのクラスが広がることになる.

本申請課題では, 線形計画問題および半正定値計画問題に対する数値解法の基礎および実装技術について, 国際共同研究を行う.　特に, 解法の基礎である内点法の計算複雑度について, 幾何学的立場を通じて理解し、より効率的なアルゴリズムを開発することを目指して研究を進めた.
　
内点法では, 中心曲線といわれる曲線を追跡して最適解を求めるが, 中心曲線を追跡するアルゴリズムの局所的な効率性と直接結びつけられる, アルゴリズム的曲率という概念が定義され, この積分, すなわち, アルゴリズム的曲率を中心曲線に沿って積分することにより, 問題を解く上でのアルゴリズムの効率について定量的な議論ができる. 昨年度、線形計画問題においては、中心曲線のアルゴリズム的全曲率は有限でしかも、線形計画問題の係数行列のみに依存するという意外な事実を我々は証明した. 本年度は、証明を改良し、論文としてまとめた.

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

Renato D.C.Monteiro and Takashi Tsuchiya:
A Strong Bound on the Integral of the Central Path Curvature and its Relationship with the Iteration Complexity of Primal-dual Path-following LP Algorithms.
Research Memorandum No.958, The Institute of Statistical Mathematics,
Tokyo, Japan, September 2005.

土谷 隆:
層別最小二乗法と交差を用いた線形計画問題に対する内点法の解析と中心曲線の幾何学的性質.
日本OR学会第17回RAMPシンポジウム(於 シティ弘前ホテル, 2005年10月)予稿集, pp.~197--211.

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

研究参加者一覧
氏名	所属機関
Monteiro Renato	ジョージア工科大学