×

zbMATH — the first resource for mathematics

A difference of convex optimization algorithm for piecewise linear regression. (English) Zbl 1438.65121
Summary: The problem of finding a continuous piecewise linear function approximating a regression function is considered. This problem is formulated as a nonconvex nonsmooth optimization problem where the objective function is represented as a difference of convex (DC) functions. Subdifferentials of DC components are computed and an algorithm is designed based on these subdifferentials to find piecewise linear functions. The algorithm is tested using some synthetic and real world data sets and compared with other regression algorithms.

MSC:
65K05 Numerical mathematical programming methods
90C26 Nonconvex programming, global optimization
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] L. T. H. An; P. D. Tao, The DC (difference of convex functions) programming and DCA revisited with DC models of real world nonconvex optimization problems, Annals of Operations Research, 133, 23-46, (2005) · Zbl 1116.90122
[2] K. Bache and M. Lichman, UCI Machine Learning Repository, University of California, Irvine, School of Information and Computer Sciences, http://archive.ics.uci.edu/ml, 2013.
[3] A. M. Bagirov; C. Clausen; M. Kohler, Estimation of a regression function by maxima of minima of linear functions, IEEE Transactions on Information Theory, 55, 833-845, (2009) · Zbl 1367.62085
[4] A. M. Bagirov; C. Clausen; M. Kohler, An algorithm for the estimation of a regression function by continuous piecewise linear functions, Computational Optimization and Applications, 45, 159-179, (2010) · Zbl 1187.90267
[5] A. M. Bagirov; C. Clausen; M. Kohler, An l_{2}-boosting algorithm for estimation of a regression function, IEEE Transactions on Information Theory, 56, 1417-1429, (2010) · Zbl 1366.62056
[6] A. M. Bagirov; B. Karasözen; M. Sezer, Discrete gradient method: A derivative-free method for nonsmooth optimization, Journal of Optimization Theory and Applications, 137, 317-334, (2008) · Zbl 1165.90021
[7] A. M. Bagirov, N. Karmitsa and M. Mäkelä, Introduction to Nonsmooth Optimization, Cham, Springer, 2014. · Zbl 1312.90053
[8] A. M. Bagirov; S. Taheri; J. Ugon, Nonsmooth DC programming approach to the minimum sum-of-squares clustering problems, Pattern Recognition, 53, 12-24, (2016) · Zbl 1412.68200
[9] S. G. Bartels; L. Kuntz; S. Scholtes, Continuous selections of linear functions and nonsmooth critical point theory, Nonlinear Analysis: Theory, Methods & Applications, 24, 385-407, (1995) · Zbl 0846.49005
[10] L. Breiman, J. H. Friedman, C. J. Stone and R. A. Olshen, Classification and Regression Trees, CRC press, 1984. · Zbl 0541.62042
[11] R. Collobert; S. Bengio, SVMTorch: Support vector machines for large-scale regression problems, Journal of Machine Learning Research, 1, 143-160, (2001) · Zbl 1052.68111
[12] V. F. Demyanov and A. M. Rubinov, Constructive Nonsmooth Analysis, Springer, 1995. · Zbl 0887.49014
[13] J. H. Fridedman, Multivariate adaptive regression splines (with discussion), Annals of Statistics, 19, 79-141, (1991) · Zbl 0765.62064
[14] J. Friedman, T. Hastie and R. Tibshirani, The Elements of Statistical Learning, Springer, Berlin, 2001. · Zbl 0973.62007
[15] V. V. Gorokhovik; O. I. Zorko; G. Birkhoff, Piecewise affine functions and polyhedral sets, Optimization, 31, 209-221, (1994) · Zbl 0816.49011
[16] L. Györfi, M. Kohler, A. Krzyźak and H. Walk, A Distribution-Free Theory of Nonparametric Regression, Springer Series in Statistics. Springer, Heldelberg, 2002.
[17] R. Horst; N. V. Thoai, DC programming: Overview, Journal of Optimization Theory and Applications, 103, 1-43, (1999) · Zbl 1073.90537
[18] K. Joki; A. M. Bagirov; N. Karmitsa; M. M. Mäkelä, A proximal bundle method for nonsmooth DC optimization utilizing nonconvex cutting planes, Journal of Global Optimization, 68, 501-535, (2017) · Zbl 1369.90137
[19] D. Meyer, E. Dimitriadou, K. Hornik, A. Weingessel, F. Leisch, C. C. Chang and C. C. Lin, Misc functions of the department of statistics, probability theory group, TU Wien, Package “e1071”, http://cran.r-project.org/web/packages/e1071/e1071.pdf, 2017.
[20] S. Milborrow, Multivariate adaptive regression splines, Package “earth”, http://cran.r-project.org/web/packages/earth/earth.pdf, 2017.
[21] J. Nash; J. Sutcliffe, River flow forecasting through conceptual models part I-A discussion of principles, Journal of Hydrology, 10, 282-290, (1970)
[22] B. Ripley and W. Venables, Feed-forward neural networks and multinomial log-linear models, Package “nnet”, http://cran.r-project.org/web/packages/nnet/nnet.pdf, 2016.
[23] A. J. Smola; B. Schölkopf, A tutorial on support vector regression, Statistics and Computing, 14, 199-222, (2004)
[24] P. D. Tao; L. T. H. An, Convex analysis approach to DC programming: Theory, algorithms and applications, Acta Mathematica Vietnamica, 22, 289-355, (1997) · Zbl 0895.90152
[25] H. Tuy, Convex Analysis and Global Optimization, Nonconvex Optimization and Its Applications, Vol. 22. Kluwer, Dordrecht, 1998. · Zbl 0904.90156
[26] P. H. Wolfe, Finding the nearest point in a polytope, Mathematical Programming, 11, 128-149, (1976) · Zbl 0352.90046
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.