Relaxations of KKT conditions do not strengthen finite RLT and SDP-RLT bounds for nonconvex quadratic programs
E. Alper Yıldırım
What the paper says
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.
Evidence weight
Balanced mode · F 0.40 / M 0.15 / V 0.05 / R 0.40
| F · citation impact | 0.50 × 0.4 = 0.20 |
| M · momentum | 0.50 × 0.15 = 0.07 |
| V · venue signal | 0.50 × 0.05 = 0.03 |
| R · text relevance † | 0.50 × 0.4 = 0.20 |
† Text relevance is estimated at 0.50 on the detail page — for your query’s actual relevance score, open this paper from a search result.