Optimization Online


Trust your data or not - StQP remains StQP: Community Detection via Robust Standard Quadratic Optimization

Immanuel M. Bomze (immanuel.bomze***at***univie.ac.at)
Michael Kahr (m.kahr***at***univie.ac.at)
Markus Leitner (markus.leitner***at***univie.ac.at)

Abstract: We consider the Robust Standard Quadratic Optimization Problem (RStQP), in which an uncertain (possibly indefinite) quadratic form is extremized over the standard simplex. Following most approaches, we model the uncertainty sets by ellipsoids, polyhedra, or spectrahedra, more precisely, by intersections of sub-cones 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 uncertainty sets, and present conditions under which the RStQP reduces to a single 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, conic optimization, graph clustering, social networks

Category 1: Robust Optimization

Category 2: Nonlinear Optimization (Quadratic Programming )

Category 3: Linear, Cone and Semidefinite Programming (Other )

Citation: Bomze, I. M., Kahr, M., Leitner, M. (2018). Trust your data or not - StQP remains StQP: Community Detection via Robust Standard Quadratic Optimization. Tech. report (1), Vienna, Austria, April 2018.

Download: [PDF]

Entry Submitted: 04/23/2018
Entry Accepted: 04/23/2018
Entry Last Modified: 09/09/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society