Seminar: Alireza Yazdani (TU Eindhoven) and Jesse van Rhijn (University of Twente), 2 PhD-talks

 
Zoom link: 
https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09 
(Meeting ID: 849 0964 5595, Passcode: 772448)

Speaker: Alireza Yazdani (TU Eindhoven) 

Title: A Clustering-based Uncertainty Set for Robust Optimization

Abstract:

In this paper, we introduce a new approach for constructing data-driven uncertainty sets in robust optimization through volume-based clustering, which we termed minimum volume norm-based clustering. This clustering approach provides greater flexibility in capturing diverse data patterns and extends the concept of minimum volume ellipsoid clustering by incorporating norm-based shapes for subregions alongside ellipsoids. We present a mixed-integer conic optimization model for minimum volume norm-based clustering, enabling customizable cluster shapes based on any vector norm in $\mathbb{R}^d$. The model we propose has the ability to detect outliers and identify overlapped clusters. Due to the computational complexity of the model, we develop an efficient iterative approximation algorithm to find near-optimal minimum-volume clusters. We compare the performance of the developed algorithm with commonly used clustering methods in the literature, such as K-means and Gaussian mixtures model clustering, to show the algorithm's efficiency in clustering data. Additionally, we conduct experiments to demonstrate the effectiveness of our approach in generating uncertainty sets. We compare the results of our method's generated uncertainty set with those from the literature. We compare the performance of the solutions generated from our method's constructed uncertainty set with others from the literature. By conducting these experiments, we demonstrate that our proposed method leads to less conservative solutions in robust optimization problems.

Video:

Speaker: Jesse van Rhijn (University of Twente)

Title: Complexity of Local Search for Euclidean Clustering Problems

Abstract:

In Euclidean clustering problems, one is given a set of d-dimensional points, and is asked to partition the set into clusters such that the points within a cluster are close by some measure. A natural measure is the squared Euclidean distance between two objects, used in the well-studied k-Means clustering problem. For this problem, local search algorithms are among the most popular methods for practical use. We show that the simplest local search method for k-Means clustering, the Hartigan-Wong method, is PLS-complete, even for k = 2. This shows that finding locally optimal clusterings under this method is as hard as for any local search problem. The same methods we use in our proofs can be easily adapted to yield PLS-completeness for Squared Euclidean Max Cut under the Flip neighborhood, which is equivalent to Min Sum 2-Clustering.

Paper available at https://arxiv.org/abs/2312.14916

Video:

Slides:
Slides