Immanuel Bomze (VCOR/ISOR and DataScience@UniWien) based upon joint work with
Michael Kahr, Markus Leitner, Werner Schachinger and Reinhard Ullrich (all Univ.Wien)

April 3, 2018 – 11:30 AM

DIISM, Artificial Intelligence laboratory (room 201), Siena SI

Description

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 nonconvex continuous optimization model is quite versatile and can even serve to solve discrete problems like the Maximum-Clique-Problem. 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.