×

zbMATH — the first resource for mathematics

Nonsmooth DC programming approach to clusterwise linear regression: optimality conditions and algorithms. (English) Zbl 1390.90436
Summary: The clusterwise linear regression problem is formulated as a nonsmooth nonconvex optimization problem using the squared regression error function. The objective function in this problem is represented as a difference of convex functions. Optimality conditions are derived, and an algorithm is designed based on such a representation. An incremental approach is proposed to generate starting solutions. The algorithm is tested on small to large data sets.

MSC:
90C26 Nonconvex programming, global optimization
90C56 Derivative-free methods and methods using generalized derivatives
Software:
Algorithm 39; DGM; UCI-ml
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] An, L.T.H.; Tao, P.D., the DC (difference of convex functions) programming and DCA revisited with DC models of real world nonconvex optimization problems, Ann. Oper. Res., 133, 23-46, (2005) · Zbl 1116.90122
[2] UCI Machine Learning Repository. University of California, School of Information and Computer Sciences, Irvine, CA, 2013. Available at
[3] Bagirov, A.M.; Karasözen, B.; Sezer, M., discrete gradient method: derivative-free method for nonsmooth optimization, J. Optim. Theory Appl., 137, 317-334, (2008) · Zbl 1165.90021
[4] Bagirov, A.M.; Ugon, J.; Mirzayeva, H., nonsmooth nonconvex optimization approach to clusterwise linear regression problems, Eur. J. Oper. Res., 229, 132-142, (2013) · Zbl 1317.90242
[5] Bagirov, A.M.; Karmitsa, N.; Mäkelä, M., Introduction to Nonsmooth Optimization, (2014), Springer, Cham · Zbl 1312.90053
[6] Bagirov, A.M.; Ugon, J.; Mirzayeva, H.G., an algorithm for clusterwise linear regression based on smoothing techniques, Optim. Lett., 9, 2, 375-390, (2015) · Zbl 1311.90106
[7] Bagirov, A.M.; Ugon, J.; Mirzayeva, H.G., nonsmooth optimization algorithm for solving clusterwise linear regression problems, J. Optim. Theory Appl., 164, 3, 755-780, (2015) · Zbl 1311.65067
[8] Bagirov, A.M.; Taheri, S.; Ugon, J., nonsmooth DC programming approach to the minimum sum-of-squares clustering problems, Pattern Recognit., 53, 12-24, (2016) · Zbl 1412.68200
[9] Clusterwise Regression Datasets, Available at , 2015
[10] Carbonneau, R.A.; Caporossi, G.; Hansen, P., globally optimal clusterwise regression by mixed logical-quadratic programming, Eur. J. Oper. Res., 212, 213-222, (2011)
[11] Carbonneau, R.A.; Caporossi, G.; Hansen, P., extensions to the repetitive branch and bound algorithm for globally optimal clusterwise regression, Comput. Oper. Res., 39, 2748-2762, (2012) · Zbl 1251.90313
[12] Clarke, F.H., Optimization and Nonsmooth Analysis, (1983), Wiley, New York · Zbl 0727.90045
[13] Demyanov, V.F.; Rubinov, A.M., Constructive Nonsmooth Analysis, (1995), Peter Lang, Frankfurt am Main · Zbl 0887.49014
[14] DeSarbo, W.S.; Cron, W.L., A maximum likelihood methodology for clusterwise linear regression, J. Classif., 5, 249-282, (1988) · Zbl 0692.62052
[15] DeSarbo, W.S.; Oliver, R.L.; Rangaswamy, A., A simulated annealing methodology for clusterwise linear regression, Psychometrika, 54, 707-736, (1989)
[16] Trajectory clustering using mixtures of regression models, in Proceedings of the ACM Conference on Knowledge Discovery and Data Mining, S. Chaudhuri and D. Madigan, eds., Association for Computing Machinery, New York, 1999, pp. 63-72
[17] Garcìa-Escudero, L.A.; Gordaliza, A.; Mayo-Iscar, A.; San Martin, R., robust clusterwise linear regression through trimming, Comput. Statist. Data Anal., 54, 3057-3069, (2010) · Zbl 1284.62198
[18] Horst, R.; Thoai, N.V., DC programming: overview, J. Optim. Theory and Appl., 103, 1-43, (1999) · Zbl 1073.90537
[19] Preda, C.; Saporta, G., clusterwise PLS regression on a stochastic process, Comput. Statist. Data Anal., 49, 99-108, (2005) · Zbl 1429.62299
[20] Rockafellar, R.T., Convex Analysis, (1970), Princeton University Press, Princeton, NJ · Zbl 0229.90020
[21] Späth, H., algorithm 39: clusterwise linear regression, Computing, 22, 367-373, (1979) · Zbl 0387.65028
[22] Tao, P.D.; An, L.T.H., convex analysis approach to DC programming: theory, algorithms and applications, Acta Math. Vietnam., 22, 289-355, (1997)
[23] Tuy, H., Convex Analysis and Global Optimization, (1998), Kluwer Academic Publishers, Dordrecht · Zbl 0904.90156
[24] Wedel, M.; Kistemaker, C., consumer benefit segmentation using clusterwise linear regression, Int. J. Res. Mark., 6, 45-59, (1989)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.