Seminars

During the last decades the importance of considering data uncertainty in optimization problems has become increasingly apparent, since small fluctuations of input data may lead to comparably bad decisions in many practical problems when uncertainty is ignored. If the probability distribution of the uncertain data is not known (or cannot be estimated with sufficient precision), a common technique is to estimate bounds on the uncertain data and to identify optimal solutions that are robust against data fluctuations within these bounds. This approach leads to the robust optimization paradigm that allows to consider uncertain objectives and constraints [1].

Optimization problems where only the objective is uncertain arise, for instance, prominently in the analysis of social networks. This stems from the fact that the strength of social ties (i.e., the amount of influence individuals exert on each other) or the willingness of individuals to adopt and share information can, for example, only be roughly estimated based on observations. A fundamental problem arising in social network analysis regards the identification of communities (e.g., work groups, interest groups), which can be modeled as a Dominant Set Clustering Problem [5,6,7] which in turn leads to a Standard Quadratic Optimization Problems (StQP); see [2]. Here the link strengths enter the objective while the constraints are familiar probability constraints, so that they can be considered certain.

Hence we investigate data uncertainty in the objective function of StQPs, considering different uncertainty sets, and derive implications for the complexity of robust variants of the corresponding deterministic counterparts. We can show that considering data uncertainty in a StQP results in another StQP of the same complexity if ellipsoidal, spherical or boxed uncertainty sets are assumed [4]. Moreover we discuss implications when considering polyhedral uncertainty sets, and derive rigorous bounds for this case, based upon copositive optimization [3].

Keywords: Graph clustering, community detection, dominant set, robust optimization, quadratic optimization.

References:

[1] Ben-Tal A, El Ghaoui L, Nemirovski AS (2009) Robust optimization. Princeton Series in Applied Mathematics (Princeton NJ: Princeton University Press).

[2] Bomze IM (1998) On standard quadratic optimization problems. Journal of Global Optimization 13(4):369–387.

[3] Bomze IM (2012) Copositive optimization – Recent developments and applications. European Journal of Operational Research 216(3):509–520.

[4] Bomze IM, Kahr M, Leitner M (2021) Trust your data or not – StQP remains StQP: Community Detection via Robust Standard Quadratic Optimization. Mathematics of Operations Research  46:301-316.

[5] Pavan M, Pelillo M (2007) Dominant sets and pairwise clustering. IEEE Transactions on Pattern Analysis and Machine Intelligence 29(1):167–172.

[6] Rota Bulò S, Pelillo M (2017) Dominant-set clustering: A review. European Journal of Operational Research 262(1):1–13.

[7] Rota Bulò S, Pelillo M, Bomze IM (2011) Graph-based quadratic optimization: A fast evolutionary approach. Computer Vision and Image Understanding 115(7):984–995.