Lagrangian decomposition of block-separable mixed-integer all-quadratic programs

• 成果类型: Article
• 署名作者: Nowak, N
• 署名单位: Humboldt University of Berlin
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-003-0500-9
• 发表日期: 2005
• 页码: 295-312
• 关键词: trust region subproblems; semidefinite; relaxation

摘要

The purpose of this paper is threefold. First we propose splitting schemes for reformulating non-separable problems as block-separable problems. Second we show that the Lagrangian dual of a block-separable mixed-integer all-quadratic program (MIQQP) can be formulated as an eigenvalue optimization problem keeping the block-separable structure. Finally we report numerical results on solving the eigenvalue optimization problem by a proximal bundle algorithm applying Lagrangian decomposition. The results indicate that appropriate block-separable reformulations of MIQQPs could accelerate the running time of dual solution algorithms considerably.