0–1 optimization of quadratic form by expanding the parameter space

This paper is concerned with 0–1 quadratic optimization problems. We formulate and analyze a class of nonconvex relaxation problems which includes the original problem and the SDP relaxation problem as extreme cases. The effects of expanding the parameter space of decision variables to a space of hypercomplex number are investigated. Especially, we focus on nonconvex relaxation problems which do not have a large gap between the original problem. It is shown that the relaxation problem in complex variable is the strongest nonconvex relaxation among the relaxations (in our formulation) in which the value of the objective function can change monotonically while the decision variables move continuously between any two feasible solutions of the original problem.