报告题目:Qualitative Properties of the Minimum Sum-of-Squares Clustering Problem

报告人：Nguyen Dong Yen 教授

报告时间：上午10：30-11：30

报告地点：博B205

题目：Qualitative Properties of the Minimum Sum-of-Squares Clustering Problem

报告人：Nguyen Dong Yen 教授(Institute of Mathematics, Vietnam Academy of Science and Technology.)

地点：浙工大屏峰校区博B205

时间：2017年11月03日  上午10：30-11：30

摘要：  A series of basic qualitative properties of the minimum sum-of-squares clustering problem are established. Among other things, we clarify the solution existence, properties of the global solutions, characteristic properties of the local solutions, locally Lipschitz property of the optimal value function, locally upper Lipschitz property of the global solution map, and the Aubin property of the local solution map. We prove that the problem in question always has a global solution and, under a mild condition, the global solution set is finite and the components of each global solution can be computed by an explicit formula. Based on a newly introduced concept of nontrivial local solution, we get necessary conditions for a system of centroids to be a nontrivial local solution. Interestingly, we are able to show that these necessary conditions are also sufficient ones. Finally, it is proved that the optimal value function is locally Lipschitz, the global solution map is locally upper Lipschitz, and the local solution map has the Aubin property, provided that the original data points are pairwise distinct. Thanks to the obtained complete characterizations of the nontrivial local solutions, one can understand better the performance of not only the $k$-means algorithm, but also of other solution methods for the minimum sum-of-squares clustering problem.

报告人简介

Nguyen Dong Yen 教授(Institute of Mathematics, Vietnam Academy of Science and Technology.)主要研究领域是: Convex Analysis and Optimization. 是国际重要学术期刊(SCI索引)如 SIAM J. Optim等的编委。