Ivo Nowak
Preprint series: Institut für Mathematik, Humboldt-Universität
zu Berlin (ISSN 0863-0976), 22 pages
MSC 2000
-
90C11 Mixed integer programming
-
90C22 Semidefinite programming
Abstract
The
purpose of this paper is threefold. First 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. Second we propose splitting schemes for reformulating non-separable
problems as block-separable problems. 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.
Keywords:semidefinite
programming,quadratic programming,combinatorial optimization,non-convex
programming,decomposition