  Clustering may be the most fundamental problem in unsupervised learning which
is still active in machine learning research because its importance in many
applications. Popular methods like K-means, may suffer from instability as they
are prone to get stuck in its local minima. Recently, the sum-of-norms (SON)
model (also known as clustering path), which is a convex relaxation of
hierarchical clustering model, has been proposed in [7] and [5] Although
numerical algorithms like ADMM and AMA are proposed to solve convex clustering
model [2], it is known to be very challenging to solve large-scale problems. In
this paper, we propose a semi-smooth Newton based augmented Lagrangian method
for large-scale convex clustering problems. Extensive numerical experiments on
both simulated and real data demonstrate that our algorithm is highly efficient
and robust for solving large-scale problems. Moreover, the numerical results
also show the superior performance and scalability of our algorithm compared to
existing first-order methods.
