The Extended Hyperbolic Smoothing Clustering Method

The minimum sum-of-squares clustering problem is considered. 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 resolution method proposed adopts a smoothing strategy using a special C1 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. The use of this technique, called Hyperbolic Smoothing, allows the main difficulties presented by the original problem to be overcome. A simplified version of the algorithm HSC containing only the essentials of the method is presented. For the purpose of illustrating both the reliability and the efficiency of the method, a set of computational experiments was performed, making use of traditional test problems described in the literature. Moreover, a set of computational results produced by a new extended version, XHSC Algorithm, based on an experimental prunning procedure supported by a partition of the set of observations in two non overlapping parts, are also presented, making using of the larger instances of Symmetric Traveling Salesman Problem (TSP).

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