Dual multilevel optimization

• 成果类型: Article
• 署名作者: Davis, Timothy A.; Hager, WilliamW.
• 署名单位: State University System of Florida; University of Florida; State University System of Florida; University of Florida
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-006-0022-3
• 发表日期: 2008
• 页码: 403-425
• 关键词: sparse; factorization; scheme; set

摘要

We study the structure of dual optimization problems associated with linear constraints, bounds on the variables, and separable cost. We show how the separability of the dual cost function is related to the sparsity structure of the linear equations. As a result, techniques for ordering sparse matrices based on nested dissection or graph partitioning can be used to decompose a dual optimization problem into independent subproblems that could be solved in parallel. The performance of a multilevel implementation of the Dual Active Set algorithm is compared with CPLEX Simplex and Barrier codes using Netlib linear programming test problems.