The authors give sufficient conditions for the convex hull of a lifted sparse nonconvex quadratic program over the unit hypercube to be SOC-representable and identify structural cases yielding a polynomial-size SOC formulation whose optimum matches the original problem.
On the Semidefinite Representability of Continuous Quadratic Submodular Minimization With Applications to Moment Problems
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
We study continuous quadratic submodular minimization with bounds and propose a polynomially sized semidefinite relaxation, which is provably tight for dimension $n \le 3$ and empirically tight for larger $n$. We apply the relaxation to two moment problems arising in distributionally robust optimization and the computation of covariance bounds. Accordingly, this research advances the ongoing study of continuous submodular minimization and opens new application areas therein.
fields
math.OC 1years
2025 1verdicts
UNVERDICTED 1representative citing papers
citing papers explorer
-
A second-order cone representable class of nonconvex quadratic programs
The authors give sufficient conditions for the convex hull of a lifted sparse nonconvex quadratic program over the unit hypercube to be SOC-representable and identify structural cases yielding a polynomial-size SOC formulation whose optimum matches the original problem.