For a quadratic optimization problem (QOP) with linear equality constraints in continuous nonnegative variables and binary variables, we propose three relaxations in simplified forms with a parameter $\lambda$: Lagrangian, completely positive, and copositive relaxations. These relaxations are obtained by reducing the QOP to an equivalent QOP with a single quadratic equality constraint in nonnegative variables, and applying the Lagrangian relaxation to the resulting QOP. As a result, an unconstrained QOP with a Lagrangian multiplier $\lambda$ in nonnegative variables is obtained. The other two relaxations are a primal-dual pair of a completely positive programming (CPP) relaxation in a variable matrix with the upper-left element set to 1 and a copositive programming (CP) relaxation in a single variable. The CPP relaxation is derived from the unconstrained QOP with the parameter $\lambda$, based on the recent result by Arima, Kim and Kojima. The three relaxations with a same parameter value $\lambda > 0$ work as relaxations of the original QOP. The optimal values $\zeta(\lambda)$ of the three relaxations coincide, and monotonically converge to the optimal value of the original QOP as $\lambda$ tends to infinity under a moderate assumption. The parameter $\lambda$ serves as a penalty parameter when it is chosen to be positive. Thus, the standard theory on the penalty function method can be applied to establish the convergence.
Citation
Research Report B-469, Department of Mathematical and Computing Sciences, Tokyo Institute of Technology, Oh-Okayama, Meguro-ku, Tokyo 152-8552, October 2012