Exactness conditions for the dual Lagrangian bound of separable quadratically constrained quadratic programming problems

Abstract In this paper we consider nonconvex diagonal Quadratically Constrained Quadratic Programming (QCQP) problems, where at least one constraint is strictly convex. A lower bound for such problems can be computed through a Lagrangian relaxation, where all constraints, except the strictly convex constraint, are moved into the objective function, suitably weighted by a vector of Lagrange multipliers. The search for the best (largest) Lagrangian bound leads to the definition of the dual Lagrangian problem. The aim of this paper is to provide sufficient as well as necessary and sufficient conditions under which exactness of the dual Lagrangian bound (i.e., the equivalence of its optimal value with the optimal value of the original nonconvex problem) is guaranteed. Some of these conditions are based on the solution of linear feasibility problems defined over the space of the Lagrange multipliers, some others on the solution of convex problems over the same space. We specialize the results proved for general diagonal QCQPs to the special case where the constraints are linear, ball and reverse ball constraints, i.e., the Hessian matrices of the constraint quadratic functions are null matrices (linear constraints), identity matrices (ball constraints), and the opposite of identity matrices (reverse ball constraints). We show that in this special case the conditions can be evaluated much more efficiently. Finally, we perform experiments over random instances to identify relevant factors which affect both exactness of the dual Lagrangian bound and the ability of detecting such exactness through the proposed sufficient conditions.