Canonical dual solutions for fixed cost quadratic programs

This chapter presents a canonical dual approach for solving a mixedinteger quadratic minimization problem with fixed cost terms. We show that this well-known NP-hard problem in R²ⁿ can be transformed into a continuous concave maximization dual problem over a convex feasible subset of Rⁿ with zero duality gap. The resulting canonical dual problem can be solved easily, under certain conditions, by traditional convex programming methods. Both existence and uniqueness of global optimal solutions are discussed. Application to a decoupled mixed-integer problem is illustrated and analytic solutions for both a global minimizer and a global maximizer are obtained. Examples for both decoupled and general nonconvex problems are presented. Furthermore, we discuss connections between the proposed canonical duality theory approach and the classical Lagrangian duality approach. An open problem is proposed for future study.