On the Semidefinite Representability of Continuous Quadratic Submodular Minimization With Applications to Pricing and Moment Problems

We study continuous quadratic submodular minimization with bounds and provide a polynomially sized semidefinite relaxation, which is provably tight for dimension n <= 3. Via an explicit counterexample for n = 4, we show that the relaxation is not tight in general, although it remains empirically tight on randomly generated instances. We apply the relaxation to multi-product pricing and 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.

Article

Download

View PDF