Journal article
A slightly lifted convex relaxation for nonconvex quadratic programming with ball constraints
Mathematical programming, Vol.211(1-2), pp.157-179
05/2025
DOI: 10.1007/s10107-024-02076-1
Abstract
Globally optimizing a nonconvex quadratic over the intersection of m balls in Rn is known to be polynomial-time solvable for fixed m. Moreover, when m=1, the standard semidefinite relaxation is exact. When m=2, it has been shown recently that an exact relaxation can be constructed using a disjunctive semidefinite formulation based essentially on two copies of the m=1 case. However, there is no known explicit, tractable, exact convex representation for m≥3. In this paper, we construct a new, polynomially sized semidefinite relaxation for all m, which does not employ a disjunctive approach. We show that our relaxation is exact for m=2. Then, for m≥3, we demonstrate empirically that it is fast and strong compared to existing relaxations. The key idea of the relaxation is a simple lifting of the original problem into dimension n+1. Extending this construction: (i) we show that nonconvex quadratic programming over ‖x‖≤min{1,g+hTx} has an exact semidefinite representation; and (ii) we construct a new relaxation for quadratic programming over the intersection of two ellipsoids, which globally solves all instances of a benchmark collection from the literature.
Details
- Title: Subtitle
- A slightly lifted convex relaxation for nonconvex quadratic programming with ball constraints
- Creators
- Samuel Burer - University of Iowa
- Resource Type
- Journal article
- Publication Details
- Mathematical programming, Vol.211(1-2), pp.157-179
- DOI
- 10.1007/s10107-024-02076-1
- ISSN
- 0025-5610
- eISSN
- 1436-4646
- Publisher
- Springer Nature
- Number of pages
- 23
- Language
- English
- Electronic publication date
- 03/14/2024
- Date published
- 05/2025
- Academic Unit
- Business Analytics
- Record Identifier
- 9984582458902771
Metrics
16 Record Views