Preprint
Extended Triangle Inequalities for Nonconvex Box-Constrained Quadratic Programming
ArXiv.org
Cornell University
01/15/2025
DOI: 10.48550/arxiv.2501.09150
Abstract
Let Boxn={x∈Rn:0≤x≤e}, and let QPBn denote the convex hull of {(1,x′)′(1,x′):x∈Boxn}. The quadratic programming problem min{x′Qx+q′x:x∈Boxn} where Q is not positive semidefinite (PSD), is equivalent to a linear optimization problem over QPBn and could be efficiently solved if a tractable characterization of QPBn was available. It is known that QPB2 can be represented using a PSD constraint combined with constraints generated using the reformulation-linearization technique (RLT). The triangle (TRI) inequalities are also valid for QPB3, but the PSD, RLT and TRI constraints together do not fully characterize QPB3. In this paper we describe new valid linear inequalities for QPBn, n≥3 based on strengthening the approximation of QPB3 given by the PSD, RLT and TRI constraints. These new inequalities are generated in a systematic way using a known disjunctive characterization for QPB3. We also describe a conic strengthening of the linear inequalities that incorporates second-order cone constraints. We show computationally that the new inequalities and their conic strengthenings obtain exact solutions for some nonconvex box-constrained instances that are not solved exactly using the PSD, RLT and TRI constraints
Details
- Title: Subtitle
- Extended Triangle Inequalities for Nonconvex Box-Constrained Quadratic Programming
- Creators
- Kurt M AnstreicherDiane Puges
- Resource Type
- Preprint
- Publication Details
- ArXiv.org
- DOI
- 10.48550/arxiv.2501.09150
- ISSN
- 2331-8422
- Publisher
- Cornell University; Ithaca, New York
- Language
- English
- Date posted
- 01/15/2025
- Academic Unit
- Business Analytics
- Record Identifier
- 9984773412802771
Metrics
14 Record Views