A dual reformulation and solution framework for regularized convex clustering problems

J. Pi, Honggang Wang and Panos M. Pardalos

European Journal of Operational Research, 2021, vol. 290, issue 3, 844-856

Abstract: Clustering techniques are powerful tools commonly used in statistical learning and data analytics. Most of the past research formulates clustering tasks as a non-convex problem, where a global optimum often cannot be found. Recent studies show that hierarchical clustering and k-means clustering can be relaxed and analyzed as a convex problem. Moreover, sparse convex clustering algorithms are proposed to extend the convex clustering framework to high-dimensional space by introducing an adaptive group-Lasso penalty term. Due to the non-smoothness nature of the associated objective functions, there are still no efficient fast-convergent algorithms for clustering problems even with convexity. In this paper, we first review the structure of convex clustering problems and prove the differentiability of their dual problems. We then show that such reformulated dual problems can be efficiently solved by the accelerated first-order methods with the feasibility projection. Furthermore, we present a general framework for convex clustering with regularization terms and discuss a specific implementation of this framework using L1,1-norm. We also derive the dual form for the regularized convex clustering problems and show that it can be efficiently solved by embedding a projection operator and a proximal operator in the accelerated gradient method. Finally, we compare our approach with several other co-clustering algorithms using a number of example clustering problems. Numerical results show that our models and solution methods outperform all the compared algorithms for both convex clustering and convex co-clustering.

Keywords: Global optimization; Convex clustering; Mathematical programming; Gradient descent; Duality (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221720307967
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:290:y:2021:i:3:p:844-856

DOI: 10.1016/j.ejor.2020.09.010

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().