統計科学における最適化法の研究

统计科学中的优化方法研究

• 批准号: 08780227
• 负责人: 土谷 隆
• 金额: $ 0.64万
• 依托单位: The Institute of Statistical Mathematics
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Encouragement of Young Scientists (A)
• 财政年份: 1996
• 资助国家: 日本
• 起止时间: 1996 至 无数据
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-08780227/
• 关键词: 最適化; 内点法; 正定対称行列; 半正定値計画問題; 線形計画問題

研究成果は以下の通りである。半正定値計画問題に対する主双対内点法について研究した.主双対内点法では,2つの正定対称行列XとSを変数として,元の最適化問題を方程式XS=0の解を求める問題として定式化し,これを解くために,XS=νI(νはパラメータ)として定義される中心曲線を離散的に追跡する.我々は,中心曲線を同値な方程式X^<1/2>SX^<1/2>=νIの解として定式化し,これに対してNewton法を適用する方法を提案し,その多項式性を証明した.この問題は,多変数正規分布の最尤推定などとも関係が深く,統計学への応用が期待されている.線形計画問題min{c^Tx|Ax=b,x【greater than or equal】0}に対する計算複雑度が係数行列Aのみに依存する多項式内点法について研究し,これまで得られている最良のアルゴリズムである,VavasisとYeのアルゴリズムを改良することに成功した.彼らのアルゴリズムは,探索方向を計算する上で,事前にX_Aなる係数行列Aのデータから計算される定数を必要とした.この定数の計算は容易ではなく,これがアルゴリズムを実用化する上で問題となった.我々は,この定数を計算しなくても同様のアルゴリズムが構成可能であることを示した.その他の研究:内点法に関連した力学系の漸近的挙動を解析した論文,Karmarkar法の挙動を解析した論文,アフィンスケーリング法の超一次収束性を証明した論文などを出版した.また,"Interior Point Methods of Mathematical Programming"(T.Terlaky,ed.,Kluwer Academic Publisher)において,アフィンスケーリング法に関する一章を著した.今回はアルゴリズムを中心に研究を展開したが,今後は応用にも力点をおいて研究を進めたい.

The research results are as follows. The positive semidefinite programming problem is studied by the principal double interior point method. The main double interior point method is called the column X

项目成果

R.D.C.Monteiro,T.Tsuchiya: "Limiting Behavior of the Derivatives of Certain Trajectories Associated with a Monotone Horizontal Linear Complementarity Problem" Mathematics of Operations Research. vol.21. 793-814 (1996)

R.D.C.Monteiro，T.Tsuchiya：“与单调水平线性互补问题相关的某些轨迹导数的极限行为”运筹学数学。

M.Muramatsu,T.Tsuchiya: "Convergence Analysis of the Projective Scaling Algorithm Based on a long-step Homogeneous Affine Scaling Algolithm" Mathematical Programming. vol.72. 291-305 (1996)

M.Muramatsu，T.Tsuchiya：“基于长步齐次仿射缩放算法的投影缩放算法的收敛性分析”数学规划。

N.Megiddo,S.Mizuno,T.Tsuchiya: "A Modified Layered-Step Interior-Point Algorithm for hinear Programming" Mathematical Programming to appear.

N.Megiddo，S.Mizuno，T.Tsuchiya：“线性规划的改进的分层步内点算法”数学规划出现。

M.Muramatsu,T.Tsuchiya: "An Affine Scaling Method with an Infeasible Starting Point : Convergence Analysis Under Nondegeneracy Assumption" Annals of Operations Research. vol.62. 325-355 (1996)

M.Muramatsu，T.Tsuchiya：“具有不可行起点的仿射标度方法：非简并假设下的收敛分析”运筹学年鉴。

A.El-Bakry,R.A.Tapia,T.Tsuchiya,Y.Zhang: "On the Formulation of the Newton Interior-Point Method for Nonlinear Programming" Journal of Optimization Theory and Applications. vol.89. 507-541 (1996)

A.El-Bakry、R.A.Tapia、T.Tsuchiya、Y.Zhang：“非线性规划牛顿内点法的公式”优化理论与应用杂志。