23. Efficient moment hierarchy for quadratic programming using moment cones
Invited abstract in session MC-11: Advances in conic optimization, stream Conic Optimization.
Monday, 14:00-16:00Room: B100/5017
Authors (first author is the speaker)
| 1. | Shengding Sun
|
| 2. | Fatma Kilinc-Karzan
|
| Carnegie Mellon University |
Abstract
Quadratic programming with quadratic constraints (QCQP) is a fundamental task in optimization that has many applications. The moment sum-of-squares hierarchy is a class of convex, semidefinite programming based relaxations that has been widely studied, and quantitative convergence results are known. However even the second level hierarchy is inefficient to compute in practice for moderate size inputs. We aim to mitigate the computational cost by proposing a more efficient moment hierarchy that only involves a subset of monomials or polynomials. In addition to reduction of the matrix size, it also uses the moment cone formulation instead of the usual localizing matrix, improving efficiency in important cases. We demonstrate its tightness and computational effectiveness in the case of ball constraints. Based on joint work with Fatma Kilinc-Karzan.
Keywords
- Conic and semidefinite optimization
Status: accepted
Back to the list of papers