General Heuristics for Nonconvex Quadratically Constrained Quadratic Programming
By Jaehyun Park, Stephen P. Boyd. 2017
178 citations recorded by the source corpus.
We introduce the Suggest-and-Improve framework for general nonconvex quadratically constrained quadratic programs (QCQPs). Using this framework, we generalize a number of known methods and provide heuristics to get approximate solutions to QCQPs for which no specialized methods are available. We also introduce an open-source Python package QCQP, which implements the heuristics discussed in the paper.
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
- David Simmons-Duffin
- Shai M. Chester
- David Poland
- Amir-Hossein Karimi
- Cynthia Rudin
- A. Vichi
- S. Rychkov
- Walter Landry
Citations in the corpus
- All Models are Wrong, but Many are Useful: Learning a Variable’s Importance by Studying an Entire Class of Prediction Models Simultaneously (2018, background): “This problem is well-studied, and is related to the trust region problem (Boyd and Vandenberghe, 2004; Pólik and Terlaky, 2007; Park and Boyd, 2017).”
- A survey of algorithmic recourse: definitions, formulations, solutions, and prospects (2020, background): “, solving for integer-based variables [12], solving for additive tree models [16, 48, 169] or neural networks [94], and solving for quadratic objectives and constraints [12, 32, 141].”
- Task Allocation for Mobile Federated and Offloaded Learning with Energy and Delay Constraints (2020, methodology): “The remaining quadratic matrices F , A , (cid:22)A , W and V k are all 0 ( K +1 (cid:2) K +1) According to [19], we can now define the functions F 2 ( (cid:0) ) , f 1 ( (cid:0) ) and f 0 ( (cid:0) ) as shown in (20)-(22).”
- All Models are Wrong but many are Useful: Variable Importance for Black-Box, Proprietary, or Misspecified Prediction Models, using Model Class Reliance (2018, background): “This problem is well studied, and is related to the trust region problem (Boyd and Vandenberghe, 2004; Pólik and Terlaky, 2007; Park and Boyd, 2017).”
- Carving out OPE space and precise O(2) model critical exponents (2019, methodology): “Another heuristic uses the method of semidefinite relaxation, which is standard in the literature on QCQPs [113].”