ON THE REDUCTION OF DUALITY GAP IN BOX CONSTRAINED NONCONVEX QUADRATIC PROGRAM

In this paper, we investigate in this paper the reduction of the duality gap between box constrained nonconvex quadratic programming and its semidefinite programming (SDP) relaxation (or Lagrangian dual). Characterizing the zero duality gap by a set of saddle-point-type conditions, we propose a parameterized distance measure δ(θ) between a polyhedral set C and a perturbed nonconvex set Λ(θ) to measure the dissatisfaction degree of the optimality conditions for zero duality gap. An underestimation of the duality gap is then derived which leads to a reduction of the duality gap proportional to δ²(θ*) for the identified best parameter θ*. This reduction of duality gap can be extended to the cases with both box and linear equality constraints. We demonstrate that the computation of δ(θ*) can be reduced to the cell enumeration of hyperplane arrangement in discrete geometry. In particular, we show that the reduction of duality gap can be achieved in polynomial time for a fixed degeneracy degree of the modified coefficient matrix determined from SDP relaxation.