Large-Scale Quadratically Constrained Quadratic Program via Low-Discrepancy Sequences
Abstract
We consider the problem of solving a large-scale Quadratically Constrained Quadratic Program. Such problems occur naturally in many scientific and web applications. Although there are efficient methods which tackle this problem, they are mostly not scalable. In this paper, we develop a method that transforms the quadratic constraint into a linear form by a sampling a set of low-discrepancy points. The transformed problem can then be solved by applying any state-of-the-art large-scale solvers. We show the convergence of our approximate solution to the true solution as well as some finite sample error bounds. Experimental results are also shown to prove scalability in practice.
Cite
Text
Basu et al. "Large-Scale Quadratically Constrained Quadratic Program via Low-Discrepancy Sequences." Neural Information Processing Systems, 2017.Markdown
[Basu et al. "Large-Scale Quadratically Constrained Quadratic Program via Low-Discrepancy Sequences." Neural Information Processing Systems, 2017.](https://mlanthology.org/neurips/2017/basu2017neurips-largescale/)BibTeX
@inproceedings{basu2017neurips-largescale,
title = {{Large-Scale Quadratically Constrained Quadratic Program via Low-Discrepancy Sequences}},
author = {Basu, Kinjal and Saha, Ankan and Chatterjee, Shaunak},
booktitle = {Neural Information Processing Systems},
year = {2017},
pages = {2297-2307},
url = {https://mlanthology.org/neurips/2017/basu2017neurips-largescale/}
}