Solving the Minimum Sum-of-Squares Clustering Problem by Hyperbolic Smoothing and Partition into Boundary and Gravitational Regions

This article considers the minimum sum-of-squares clustering (MSSC)problem. The mathematical modeling of this problem leads to a min − sum − min formulation which, in addition to its intrinsic bi-level nature, has the significant characteristic of being strongly nondifferentiable. To overcome these difficulties, the proposed resolution method, called Hyperbolic Smoothing, adopts a smoothing strategy using a special C∞ differentiable class function. The final solution is obtained by solving a sequence of low dimension differentiable unconstrained optimization subproblems which gradually approach the original problem. This paper introduces the method of partition of the set of observations into two non overlapping groups: ”data in frontier” and ”data in gravitational regions”. The resulting combination of the two methotologies for the MSSC problem has interesting properties, which drastically simplify the computational tasks.

Keywords: Cluster Analysis, Pattern Recognition, Min-Sum- Min Problems, Nondifferentiable Programming, Smoothing.