Trust Your Data or Not—StQP Remains StQP: Community Detection via Robust Standard Quadratic Optimization

Author(s)
Immanuel Bomze, Michael Kahr, Markus Leitner
Abstract

We consider the robust standard quadratic optimization problem (RStQP), in which an uncertain (possibly indefinite) quadratic form is optimized over the standard simplex. Following most approaches, we model the uncertainty sets by balls, polyhedra, or spectrahedra, more generally, by ellipsoids or order intervals intersected with subcones of the copositive matrix cone. We show that the copositive relaxation gap of the RStQP equals the minimax gap under some mild assumptions on the curvature of the aforementioned uncertainty sets and present conditions under which the RStQP reduces to the standard quadratic optimization problem. These conditions also ensure that the copositive relaxation of an RStQP is exact. The theoretical findings are accompanied by the results of computational experiments for a specific application from the domain of graph clustering, more precisely, community detection in (social) networks. The results indicate that the cardinality of communities tend to increase for ellipsoidal uncertainty sets and to decrease for spectrahedral uncertainty sets.

Organisation(s)
Department of Statistics and Operations Research, Research Network Data Science, Research Platform Governance of digital practices
External organisation(s)
Vrije Universiteit Amsterdam
Journal
Mathematics of Operations Research
Volume
46
Pages
301-316
No. of pages
16
ISSN
0364-765X
DOI
https://doi.org/10.1287/moor.2020.1057
Publication date
09-2020
Peer reviewed
Yes
Austrian Fields of Science 2012
101015 Operations research
Keywords
ASJC Scopus subject areas
General Mathematics, Computer Science Applications, Management Science and Operations Research
Portal url
https://ucrisportal.univie.ac.at/en/publications/80df4c0d-b2cd-4dfb-9b4f-ed396e3b25c7