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

Immanuel M. Bomze (), Michael Kahr () and Markus Leitner ()
Additional contact information
Immanuel M. Bomze: Department of Statistics and Operations Research, University of Vienna, 1090 Wien, Austria; Vienna Center of Operations Research, University of Vienna, 1090 Wien, Austria; Research Platform Data Science @ Uni Vienna, University of Vienna, 1090 Wien, Austria;
Michael Kahr: Department of Statistics and Operations Research, University of Vienna, 1090 Wien, Austria
Markus Leitner: Department of Supply Chain Analytics, Vrije Universiteit Amsterdam, 1081 HV Amsterdam, Netherlands

Mathematics of Operations Research, 2021, vol. 46, issue 1, 301-316

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.

Keywords: robust optimization; quadratic optimization; community detection; social networks (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://doi.org/10.1287/moor.2020.1057 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:46:y:2021:i:1:p:301-316

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().