A DC optimization approach for constrained clustering with \(\ell_1\)-norm. (English) Zbl 1497.49021
Summary: One of the challenges in optimizing clustering problems is requirement of differ-entiability. Clustering is a popular approach that classifies a given data into different groups , based on some common properties. It is a basic foundation of machine learning , facility location and image processing. Although the problem is nonsmooth, we used Nesterov partial smooth-ing technique to approximate nondifferentiable convex functions by smooth convex functions with Lipschitz continuous gradients. In this paper, we mainly focused in modelling and solving clustering problems that identify some nodes as cluster centers among others and minimize the overall \(\ell_1\) distance of the clusters. In addition, since the algorithm starts with any initial clus-ter centers penalty parameter is used to push centers to real node. As a result, a DCA based algorithms were implemented that find optimal cluster centers in reasonable iteration time.
MSC:
| 49J52 | Nonsmooth analysis |
| 49J53 | Set-valued and variational analysis |
| 90C31 | Sensitivity, stability, parametric optimization |
| 90C26 | Nonconvex programming, global optimization |
References:
| [1] | L. T. H. An, M. T. Belghiti, P. D. Tao: A new efficient algorithm based on DC programming and DCA for clustering. J. Glob. Optim.,27,(2007), 503-608. · Zbl 1198.90327 |
| [2] | An, L.T.H., Minh, L.H., Tao, P.D., New and efficient DCA based algorithms for minimum sum-of-squares clustering. Pattern Recognit, Ann. New York Acad. Sci.,47,(2014),388-401. · Zbl 1326.68225 |
| [3] | L. T. H. An, and L. H. Minh, Optimization based DC programming and DCA for hierarchical clustering. European J. Oper. Res.183(2007), 1067-1085. · Zbl 1149.90117 |
| [4] | L. T. H. An, and P. D. Tao, Convex analysis approach to D.C. programming: Theory, algorithms and applications.Acta Math. Vietnam.22(1997), 289-355. · Zbl 0895.90152 |
| [5] | A. Bagirov, Long Jia, I. Ouveysi, and A.M. Rubinov, Optimization based clustering algorithms in Multicast group hierarchies, in: Proceedings of the Australian Telecommunications, Networks and Applications Conference (ATNAC), (2003), Melbourne Australia (published on CD, ISNB 0-646-42229-4). |
| [6] | Bagirov, A., Taheri, S., Ugon, J., Nonsmooth DC programming approach to the minimum sum-of-squares clustering problems , Pattern Recognit,53,(2016), 12-24. · Zbl 1412.68200 |
| [7] | Barbosa, G. V., Villas-Boas, S. B., Xavier, A. E., Solving the two-level clustering problem by hyperbolic smoothing approach, and design of multicast networks, In: Selected Proceedings, WCTR RIO, 2013 |
| [8] | B. S. Mordukhovich and N. M. Nam,An Easy Path to Convex Analysis and Applications, Morgan & Claypool Publishers, San Rafael, CA, 2014. · Zbl 1284.49002 |
| [9] | Nam, N.M., Rector, R.B., Giles, D., Minimizing differences of convex functions with applications to facility location and clustering , J. Optim. Theory Appl.,173,(2017) ,255-278. · Zbl 1388.90097 |
| [10] | Nam N. M., Geremew, W., Reynolds, R., & Tran, T. (2018).Nesterov’s smoothing technique and minimizing differences of convex functions for hierarchical clustering.Optimization Letters.12(3), 455-473. · Zbl 1418.90203 |
| [11] | Y. Nesterov: Smooth minimization of non-smooth functions. Math. Program.103, 127-152 (2005). · Zbl 1079.90102 |
| [12] | R. T. Rockafellar,Convex Analysis, Princeton University Press, Princeton, NJ, 1970. · Zbl 0193.18401 |
| [13] | T. Pham Dinh and H. A. Le Thi, A d.c. optimization algorithm for solving the trust-region subproblem, SIAM J. Optim.,8, (1998), 476-505. · Zbl 0913.65054 |
| [14] | Geremew, W., Nam, N.M., Semenov, A., Boginski, V., & Pasiliao, E. (2018).A DC programming approach for solving multicast network design problems via the Nesterov smoothing technique.Journal of Global Optimization.72(4), 705-729. · Zbl 1422.90058 |
| [15] | N. M. Nam, R.B. Rector, D. Giles: Minimizing Differences of Convex Functions with Applications to Facility Location and Clustering, Math. Program,173, (2017), 255-278. · Zbl 1388.90097 |
| [16] | H.A. LE THI AND T. PHAM DINH, DC Programming and DCA: Thirty Years of, Math. Program.,169, (2018) , 5-68. · Zbl 1387.90197 |
| [17] | Anuj Bajaj, Boris S. Mordukhovich, Nguyen Mau Nam, and Tuyen Tran., Solving Multifacility Location Problems by DC Algorithms, J. Optim., 2019. |
| [18] | Yu. Nesterov, Lectures on Convex Optimization, 2nd edition, Springer, Cham, Switzerland, 2018 · Zbl 1427.90003 |
| [19] | Nguyen, P.A., Le Thi, H.A, DCA approaches for simultaneous wireless information power transfer in MISO secrecy channel., Optim Eng , 2020. |
| [20] | Mau Nam Nguyen, Hoai An Le Thi, Giles Daniel, Thai An Nguyen, Smoothing techniques and difference of convex functions algorithms for image reconstructions, Optimization,(2019), 1-33 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
