TY - UNPB
T1 - Polyhedral Properties of RLT Relaxations of Nonconvex Quadratic Programs and Their Implications on Exact Relaxations
AU - Qiu, Yuzhou
AU - Yildirim, E Alper
PY - 2023/3/27
Y1 - 2023/3/27
N2 - We study linear programming relaxations of nonconvex quadratic programs given by the reformulation-linearization technique (RLT), referred to as RLT relaxations. We investigate the relations between the polyhedral properties of the feasible regions of a quadratic program and its RLT relaxation. We establish various connections between recession directions, boundedness, and vertices of the two feasible regions. Using these properties, we present necessary and sufficient exactness conditions for RLT relaxations. We then give a thorough discussion of how our results can be converted into simple algorithmic procedures to construct instances of quadratic programs with exact, inexact, or unbounded RLT relaxations.
AB - We study linear programming relaxations of nonconvex quadratic programs given by the reformulation-linearization technique (RLT), referred to as RLT relaxations. We investigate the relations between the polyhedral properties of the feasible regions of a quadratic program and its RLT relaxation. We establish various connections between recession directions, boundedness, and vertices of the two feasible regions. Using these properties, we present necessary and sufficient exactness conditions for RLT relaxations. We then give a thorough discussion of how our results can be converted into simple algorithmic procedures to construct instances of quadratic programs with exact, inexact, or unbounded RLT relaxations.
U2 - https://doi.org/10.48550/arXiv.2303.15073
DO - https://doi.org/10.48550/arXiv.2303.15073
M3 - Preprint
BT - Polyhedral Properties of RLT Relaxations of Nonconvex Quadratic Programs and Their Implications on Exact Relaxations
PB - ArXiv
ER -