Solving large-scale semidefinite programs in parallel

• 成果类型: Article
• 署名作者: Nayakkankuppam, Madhu V.
• 署名单位: Bloomberg L.P.
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-006-0032-1
• 发表日期: 2007
• 页码: 477-504
• 关键词: algorithm

摘要

We describe an approach to the parallel and distributed solution of large-scale, block structured semidefinite programs using the spectral bundle method. Various elements of this approach (such as data distribution, an implicitly restarted Lanczos method tailored to handle block diagonal structure, a mixed polyhedral-semidefinite subdifferential model, and other aspects related to parallelism) are combined in an implementation called LAMBDA, which delivers faster solution times than previously possible, and acceptable parallel scalability on sufficiently large problems.