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

This article considers the minimum sum of distances clustering (MSDC) problem, where the distances are measured through the L1 or Manhattan metric. 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 uses also 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 MSDC problem has interesting properties: complete differentiability and drastic simplification of computational tasks.

Keywords: Cluster Analysis, Min-Sum-Min Problems, Manhattan Metric, Nondifferentiable Programming, Smoothing.