In a Standard Quadratic Optimization Problem (StQP), a possibly indefinite quadratic form (the simplest nonlinear function) is extremized over the standard simplex, the simplest polytope. Despite of its simplicity, this model is quite versatile.
Here we will focus on Clustering in Social Networks applications in a Machine Learning context.
A fundamental problem arising in social network analysis regards the identification of communities (e.g., work groups, interest groups), which can be modeled naturally with the framework of StQP.
However the problem data are uncertain as the strength of social ties can only be roughly estimated based on observations. Therefore the robust counterpart for these problems refers to uncertainty only in the objective, not in the constraints. It turns out that for the StQP, most of the usual uncertainty sets do not add complexity to the robust counterpart.
On the other hand, it is well known that most probably within this problem class, a generic StQP instance is not too hard to solve as the worst cases are hidden in relatively thin manifolds of the class. These hard instances allow for remarkably rich patterns of coexisting local solutions, which are closely related to practical difficulties in solving StQPs globally.
(based upon joint work with Michael Kahr, Markus Leitner, Werner Schachinger and Reinhard Ullrich [all Univ. Wien])
Venue: MI 02.06.011 ("SFB-Room", Campus Garching)
Date: Monday, April 16th, 2018 (starting at 14:00)