Non-convex relaxation of convex constrained quadratic programming using hyper complex number

摘要

This paper addresses the convex constrained quadratic minimization problem. A sort of non-convex relaxation problems in which each real variable is expanded to hyper complex number is defined. The relaxation problem includes SDP relaxation problem as a special case. Therefore, this formulation connects the original problem and the convex relaxation problem continuously. It is shown that lie feasible reagion of non-convex relaxation problem in two dimensional complex number has "monotonically decreasing path" between feasible solutions of original problem. Numerical experiments for 0-1 quadratic minimization problem reveals that the availability of non-convex relaxations based on the derived property.