A parallel implementation for solving large-scale Semidefinite Programs having sparse Schur complement matrix

求解具有稀疏Schur补矩阵的大规模半定规划的并行实现

• 批准号: 21710148
• 负责人: YAMASHITA Makoto
• 金额: $ 1.83万
• 依托单位: Tokyo Institute of Technology
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Young Scientists (B)
• 财政年份: 2009
• 资助国家: 日本
• 起止时间: 2009 至 2011
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-21710148/
• 关键词: 応用数学; ハイパフォーマンスコンピューティング; 数理最適化; 並列計算; 半正定値計画問題; センサーネットワーク

The reduction in computation time for solving Semidefinite Programs is essential to many applications like sensor network localization problems and polynomial optimizations. We focus on the sparsity of the Schur complement matrix, which occupies most computation time. We estimate the computation cost of each element of the matrix and propose efficient parallel schemes. From numerical results, we verified that the parallel schemes successfully reduce the computation time.

减少求解半定程序的计算时间对于传感器网络定位问题和多项式优化等许多应用至关重要。我们重点关注 Schur 补矩阵的稀疏性，它占据了大部分计算时间。我们估计矩阵每个元素的计算成本并提出有效的并行方案。从数值结果来看，我们验证了并行方案成功地减少了计算时间。

项目成果

Latest developments in the SDPA Family for solving large-scale SDPs,inHandbook on Semidefinite, Cone and Polynomial Optimization : Theory, Algorithms, Software and Applicationsedited by Miguel F. Anjos and Jean B. Lasserre

SDPA 系列用于解决大规模 SDP 的最新进展，参见《半定、圆锥和多项式优化手册：理论、算法、软件和应用》，由 Miguel F. Anjos 和 Jean B. Lasserre 编辑

• 发表时间: 2011
• 作者: Makoto Yamashita;Katsuki Fujisawa;Mituhiro Fukuda;Kazuhiro Kobayashi;Kazuhide Nakta;Maho Nakata
• 通讯作者: Maho Nakata

Parallel Software for Semidefinite Programming with Sparse Schur complement Matrix

稀疏 Schur 补矩阵半定规划并行软件

• 发表时间: 2009
• 作者: M. Yamashita;K. Fujisawa;M. Fukuda;Y. Futakata;K. Kobayashi;M. Kojima;K. Nakata;M. Nakata
• 通讯作者: M. Nakata

主双対内点法に対する高速化・並列化の技術

原对偶内点法加速和并行化技术

• 发表时间: 2010
• 期刊: オペレーションズ・リサーチ
• 作者: Takashima;R.;Kuno;Y.;Omoto;A. and Tanaka;S.;山下真
• 通讯作者: 山下真

Ellipsoid-type Confidential Bounds on Semi-algebraic Sets via SDP Relaxation

通过SDP松弛的半代数集的椭球型保密界

• 发表时间: 2011
• 作者: Makoto Yamashita;Katsuki Fujisawa;Mituhiro Fukuda;Kazuhide Nakata;Maho Nakata;八木恭子・高嶋隆太;Makoto Yamashita and Masakazu Kojima
• 通讯作者: Makoto Yamashita and Masakazu Kojima

Parallel Computation for SDPs Focusing on the Sparsity of Schur Complements Matrices

关注 Schur 补矩阵稀疏性的 SDP 并行计算

• 发表时间: 2011
• 作者: Makoto Yamashita;Katsuki Fujisawa;Mituhiro Fukuda;Kazuhide Nakata;Maho Nakata
• 通讯作者: Maho Nakata