Best ellipsoidal relaxation to solve a nonconvex problem

摘要

We present a new ellipsoidal relaxation of 0–1 quadratic optimization problems. The relaxation and the dual problem are derived. Both these problems are strictly feasible; so strong duality holds, and they can be solved numerically using primal-dual interior-point methods.