A fast and cheap approach for strengthening Lagrangian bound for the generalized Celis-Dennis-Tapia subproblem

In this paper, we consider the generalized Celis-Dennis-Tapia problemwhich is the problem of minimizing a nonconvex quadratic function subject totwo quadratic inequality constraints, one of which being convex. When there isa positive duality gap, by exploiting an equivalent form of the dual Lagrangianproblem, we propose to improve the dual bound by adding one or two linear cutsto the Lagrangian relaxation. The present work is motivated by and generalizesthe results of [۱۴] for the problem with two strictly convex quadratic constraints.Our main contribution is to show that one can include the feasible region in a con-vex set and then follow the approach in [۱۴] to construct the linear cuts based onsupporting hyperplanes of the convex set. Numerical experiments are conductedto assess the quality of the proposed bounds.

کلیدواژه ها:

quadratically constrained quadratic programming ، Celis-Dennis-Tapia problem ، dual Lagrangian bound ، Supporting hyperplane