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

 

課題番号

16−共研−2014

専門分類

2

研究課題名

線形計画問題および半正定値計画問題に対する数値解法の基礎的研究

フリガナ

代表者氏名

ツチヤ　タカシ

土谷　隆

ローマ字

Tsuchiya Takashi

所属機関

統計数理研究所

所属部局

予測制御研究系

職　　名

教授

所在地

TEL

FAX

E-mail

URL

配分経費

研究費

0千円

旅　費

0千円

研究参加者数

4　人

 

 

 

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

1990年代の最適化の大きな進歩の一つは,旧来の線形計画問題に加え21世紀の線形計画問題と呼ばれ
る一連の凸最適化問題のクラス,半正定値計画問題および2次錐計画問題に対して内点法と呼ばれる多
項式解法が確立され,実用化の途についたということである。これらは新たに登場した,強力で柔軟
なモデリングの手段であり,統計科学や信号処理,パターン認識,ロバスト最適化,制御,最適設計な
どへの応用が現在活発に進められている。これらの最適化問題に対してより強力な解法が得られれば,
我々が用いることができるモデルのクラスが広がることになる。本共同研究の目的は,これらの問題に
対する数値解法の基礎および実装技術に関して,国際共同研究を行うことである。本研究では特に内点
法の反復回数の中心曲線上の積分による評価に焦点を絞って研究を進めた。線形計画問題に対する主
双対内点法の反復回数と中心曲線の幾何学的性質の関係の解析を進め,中心曲線のアルゴリズム的曲
率を定義し,内点法の反復回数はアルゴリズム的曲率の積分でよく近似できることを明らかにした。そ
して中心曲線の全曲率が係数行列Aの条件数の対数と非負変数の3.5乗の積の定数倍で上から押さえら
れることの証明を与えた(現在論文を執筆中)。線形計画問題においては係数行列Aのみに依存する多
項式アルゴリズムが存在することが知られているが,それに対応する問題の構造を幾何学的立場から
理解する手がかりを得たものとして,本研究で得られた結果は興味深いものである。また,アルゴリ
ズムの反復回数という離散量について幾何学的立場から定量的に解析した研究は少なく,今後アルゴ
リズムの数理の研究として対称錐計画問題への一般化や微分幾何学的立場からの解析などいろいろな
方向へと研究を発展させることができる可能性がある。

 

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

[論文]
R.D.C.Monteiro and T.Tsuchiya:A new itreration-complexity bound for the MTY predictor-corrector
algorithm for linear programming.SIAM Journal on Optimization,Vol.15(2004/2005),pp.319-347.
T.Tsuchiya:Complexity analysis of interior-point algorithms and geometric properties of the central
trajectory for linear programming.To appear in Oberwolfach Report,2005.
[研究発表]
土谷　隆:線形計画問題に対する内点法の計算複雑度と中心曲線の幾何学的性質。超ロバスト計算原理
セミナー,東京大学,2005.12.14.
T.Tsuchiya:Complexity analysis of interior-point algorithms and geometric properties of the central
trajectory for linear programming.Optimization and Applications,Oberwolfach,Germany,2005.1.11.
T.Tsuchiya:Theoretical Analysis and Applications of Primal-dual Interior-point algorithms for linear
and second-order cone programming.The Art of Statistical Metaware,The Institute of Statistical
Mathematics,2005.3.15.
R.D.C.Monteiro and T.Tsuchiya:線形計画問題に対する内点法の計算複雑度と中心曲線の幾何学的性質
について。最適化:モデリングとアルゴリズム,統計数理研究所,2005.3.23.

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

 

研究参加者一覧

氏名

所属機関

Zhaosong Lu

ジョージア工科大学

Jerome O’Neal

ジョージア工科大学

Renato D. C. Monteiro

ジョージア工科大学