Abstract We consider the problem of minimizing a (possibly nonconvex) quadratic function over a (possibly unbounded) polyhedron, referred to as a quadratic program. By incorporating the first-order optimality conditions, a quadratic program can be formulated as an optimization problem with complementarity constraints. We investigate the effect of incorporating optimality conditions on the strength of linear and semidefinite programming (SDP) relaxations based on the reformulation-linearization technique (RLT relaxation), and the Shor relaxation combined with the RLT relaxation (SDP-RLT relaxation). We establish that the RLT and SDP-RLT bounds arising from the complementarity formulation do not strengthen finite RLT and SDP-RLT bounds arising from the original formulation. On the other hand, the complementarity formulation may yield strictly tighter lower bounds for quadratic programs with a finite optimal value, but unbounded RLT and SDP-RLT relaxations. We present several classes of instances of quadratic programs to illustrate the behavior of the relaxations arising from the complementarity formulation. In particular, our examples reveal that the complementarity formulation should be used with some caution as it may even fail to yield a valid lower bound for unbounded quadratic programs.
E. Alper Yıldırım (2026) studied this question.