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

详细信息    查看全文

• 作者：Ivo Nowak
• 关键词：semidefinite programming ; quadratic programming ; combinatorial optimization ; non ; convex programming ; decomposition
• 刊名：Mathematical Programming
• 出版年：2005
• 出版时间：March 2005
• 年：2005
• 卷：102
• 期：2
• 页码：295-312
• 全文大小：201 KB
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Calculus of Variations and Optimal Control
  Mathematics of Computing
  Numerical Analysis
  Combinatorics
  Mathematical and Computational Physics
  Mathematical Methods in Physics
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1436-4646

文摘

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.