A challenge to huge scale semidefinite programs-exploiting sparsity, parallel computation and polynomial optimization problems

对大规模半定规划的挑战——利用稀疏性、并行计算和多项式优化问题

• 批准号: 19310096
• 负责人: KOJIMA Masakazu
• 金额: $ 12.65万
• 依托单位: Tokyo Institute of Technology
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (B)
• 财政年份: 2007
• 资助国家: 日本
• 起止时间: 2007 至 2009
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-19310096/
• 关键词: 最適化; 半正定値計画問題; 並列計算; 多項式; 疎性; 数理計画

We studied primal-dual interior-point methods for solving a semidefinite program which is one of the most important optimization problems having lots of applications in various fields of science and engineering, and developed a software package SDPA based on them. SDPA solves larger scale problems in shorter time than the existing software packages. As applications of SDPA, we provided SparsePOP for polynomial optimization problems and SFSDP for large scale sensor network localization problems.

半定规划是科学和工程领域中最重要的优化问题之一，本文研究了半定规划的原-对偶邻域点法，并在此基础上开发了一个软件包SDPA。SDPA比现有的软件包在更短的时间内解决更大规模的问题。作为SDPA的应用，我们提供了用于多项式优化问题的SparsePOP和用于大规模传感器网络定位问题的SFSDP。

项目成果

SDPA Project: Solving Large-scale Semidefinite Program

SDPA 项目：求解大规模半定规划

• 发表时间: 2007
• 期刊: J. of the Operations Research Society of Japan 50
• 作者: K. Nakabayashi;B.K. Sahoo;K. Tone;K. Fujisawa
• 通讯作者: K. Fujisawa

最適化問題に対する並列計算技術の適用

并行计算技术在优化问题中的应用

• 发表时间: 2007
• 期刊: オペレーションズ・リサーチ 52
• 作者: B.K. Sahoo;K. Tone;藤澤克樹
• 通讯作者: 藤澤克樹

Duality in the Positive Semidefinite Natrix Completion and Its Application to SDPs

正半定Natrix补全的对偶性及其在SDP中的应用

• 发表时间: 2009
• 作者: Tone K.;Avkiran NK;Tsutsui M;Masakazu Kojima
• 通讯作者: Masakazu Kojima

半正定値行列補完における双対性とそのSDPへの応用

半正定矩阵补全的对偶性及其在 SDP 中的应用

• 发表时间: 2009
• 作者: Fukuyama H;Weber WL;小島政和
• 通讯作者: 小島政和

拡散過程の生存確率に対する半正定値計画を用いた数値計算手法

扩散过程生存概率的半定规划数值计算方法

• 发表时间: 2008
• 期刊: Transactions of the Operations Research Society of Japan Vol. 51
• 作者: K. Suzuki;N. Miyoshi;K. Kojima
• 通讯作者: K. Kojima