2023/03/12 by Yuzhou Qiu, Qiu, Yuzhou, E. Alper Yıldırım +1
Biochemistry, Genetics and Molecular Biology · Computer Science · Engineering · #90C20 #90C22 #90C26 #Advanced Control Systems Optimization #FOS: Mathematics #Formal Methods in Verification #Optimization and Control (math.OC) #Peroxisome Proliferator-Activated Receptors
paper · pdf · doi:10.48550/arxiv.2303.06761
openalex publication_date 2023/03/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
Quadratic programs with box constraints involve minimizing a possibly nonconvex quadratic function subject to lower and upper bounds on each variable. This is a well-known NP-hard problem that frequently arises in various applications. We focus on two convex relaxations, namely the RLT (Reformulation-Linearization Technique) relaxation and the SDP-RLT relaxation obtained by adding semidefinite constraints to the RLT relaxation. Both relaxations yield lower bounds on the optimal value of a quadratic program with box constraints. We present complete algebraic descriptions of the set of instances that admit exact RLT relaxations as well as those that admit exact SDP-RLT relaxations. We show that our descriptions can be converted into algorithms for efficiently constructing instances with exact or inexact relaxations.