×

A penalized method for multivariate concave least squares with application to productivity analysis. (English) Zbl 1394.90457

Summary: We propose a penalized method for the least squares estimator of a multivariate concave regression function. This estimator is formulated as a quadratic programming (QP) problem with \(O(n^2)\) constraints, where \(n\) is the number of observations. Computing such an estimator is a very time-consuming task, and the computational burden rises dramatically as the number of observations increases. By introducing a quadratic penalty function, we reformulate the concave least squares estimator as a QP with only non-negativity constraints. This reformulation can be adapted for estimating variants of shape restricted least squares, i.e., the monotonic-concave/convex least squares. The experimental results and an empirical study show that the reformulated problem and its dual are solved significantly faster than the original problem. The Matlab and R codes for implementing the penalized problems are provided in the paper.

MSC:

90C25 Convex programming
90C20 Quadratic programming
62G08 Nonparametric regression and quantile regression
62G05 Nonparametric estimation
62F30 Parametric inference under constraints
62J02 General nonlinear regression

Software:

Matlab; R; LPbook; TVAL3
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Aït-Sahalia, Y.; Duarte, J., Nonparametric option pricing under shape restrictions, Journal of Econometrics, 116, 9-47 (2003) · Zbl 1016.62121
[2] Andor, M.; Hesse, F., The StoNED age: The departure into a new era of efficiency analysis? A Monte Carlo comparison of StoNED and the “oldies” (SFA and DEA), Journal of Productivity Analysis, 41, 85-109 (2014)
[3] Badinelli, R. D., Optimal safety stock investment through subjective evaluation of stockout costs, Decision Sciences, 17, 3, 312-328 (1986)
[4] Birke, M.; Dette, H., Estimating a convex function in nonparametric regression, Scandinavian Journal of Statistics, 34, 384-404 (2007) · Zbl 1142.62019
[5] Chen, C. F.; Rothschild, R., An application of hedonic pricing analysis to the case of hotel rooms in Taipei, Tourism Economics, 16, 3, 685-694 (2010)
[6] Cheng, X.; Bjørndal, E.; Bjørndal, M., Cost efficiency analysis based on the DEA and StoNED models: Case of norwegian electricity distribution companies, (11th Proceedings of the IEEE International Conference on European Energy Market (EEM) (2014)), 1-6
[7] Corazza, M.; Fasano, G.; Gusso, R., Particle swarm optimization with non-smooth penalty reformulation, for a complex portfolio selection problem, Applied Mathematics and Computation, 224, 611-624 (2013) · Zbl 1335.91061
[8] D’Halluin, Y.; Forsyth, P. A.; Labahn, G., A penalty method for American options with jump diffusion processes, Numerische Mathematik, 97, 2, 321-352 (2004) · Zbl 1126.91036
[9] Dantzig, G. B.; Fulkerson, D. R.; Johnson, S. M., On a linear-programming, combinatorial approach to the traveling-salesman problem, Operations Research, 7, 1, 58-66 (1959) · Zbl 1414.90211
[10] Dantzig, G.; Fulkerson, R.; Johnson, S., Solution of a large-scale traveling salesman problem, Journal of the Operations Research Society of America, 393-403 (1954) · Zbl 1414.90372
[11] Di Pillo, G.; Grippo, L., Exact penalty functions in constrained optimization, SIAM Journal on Control and Optimization, 27, 6, 1333-1360 (1989) · Zbl 0681.49035
[12] Dykstra, R. L., An Algorithm for restricted least squares regression, Journal of the American Statistical Association, 78, 384, 837-842 (1983) · Zbl 0535.62063
[13] Dykstra, R. L.; Robertson, T., An algorithm for isotonic regression for two or more independent variables, The Annals of Statistics, 10, 3, 708-716 (1982) · Zbl 0485.65099
[14] Eskelinen, J.; Kuosmanen, T., Intertemporal efficiency analysis of sales teams of a bank: Stochastic semi-nonparametric approach, Journal of Banking & Finance, 37, 12, 5163-5175 (2013)
[15] Espinet, J. M.; Saez, M.; Coenders, G.; Fluvia, M., Effect on prices of the attributes of holiday hotels: A hedonic prices approach, Tourism Economics, 9, 2, 165-177 (2003)
[16] Fiacco, A. V.; McCormick, G. P., Nonlinear programming: Sequential unconstrained minimization techniques, Classics in applied mathematics, Vol. 4 (1968), SIAM: SIAM Philadelphia, PA · Zbl 0193.18805
[17] Fraser, D. A.; Massam, H., A mixed primal-dual bases algorithm for regression under inequality constraints: Application to concave regression, Scandinavian Journal of Statistics, 16, 65-74 (1989) · Zbl 0672.62077
[18] Gelman, A.; Hill, J., Data analysis using regression and multilevel/hierarchical models (2007), Cambridge University Press: Cambridge: Cambridge University Press: Cambridge New York
[20] Groeneboom, P.; Jongbloed, G.; Wellner, J.a., Estimation of a convex function: Characterizations and asymptotic theory, Annals of Statistics, 29, 6, 1653-1698 (2001) · Zbl 1043.62027
[21] Hannah, L. A.; Dunson, D. B., Multivariate convex regression with adaptive partitioning, The Journal of Machine Learning Research, 14, 3261-3294 (2013) · Zbl 1318.62225
[22] Hanson, D.; Pledger, G., Consistency in concave regression, The Annals of Statistics, 4, 6, 1038-1050 (1976) · Zbl 0341.62034
[23] Hildreth, C., Point estimates of ordinates of concave functions, Journal of the American Statistical Association, 49, 267, 598-619 (1954) · Zbl 0056.38301
[24] Hoerl, A. E.; Kennard, R. W., Ridge regression: Biased estimation for non-orthogonal problems, Technometrics, 12, 1, 55-67 (1970) · Zbl 0202.17205
[25] Holloway, C. A., On the estimation of convex functions, Operations Research, 27, 2, 401-407 (1979) · Zbl 0408.90066
[26] Hu, X. M.; Ralph, D., Convergence of a penalty method for mathematical programming with complementarity constraints, Journal of Optimization Theory and Applications, 123, 2, 365-390 (2004)
[27] Keshvari, A.; Kuosmanen, T., Stochastic non-convex envelopment of data: Applying isotonic regression to frontier estimation, European Journal of Operational Research, 231, 2, 481-491 (2013) · Zbl 1317.62035
[28] Kuosmanen, T., Representation theorem for convex nonparametric least squares, Econometrics Journal, 11, 2, 308-325 (2008) · Zbl 1141.91640
[29] Kuosmanen, T., Stochastic semi-nonparametric frontier estimation of electricity distribution networks: Application of the StoNED method in the Finnish regulatory model, Energy Economics, 34, 6, 2189-2199 (2012)
[30] Kuosmanen, T.; Kortelainen, M., Stochastic non-smooth envelopment of data: Semi-parametric frontier estimation subject to shape constraints, Journal of Productivity Analysis, 38, 1, 11-28 (2012)
[31] Lee, C. Y.; Johnson, A. L.; Moreno-Centeno, E.; Kuosmanen, T., A more efficient algorithm for convex nonparametric least squares, European Journal of Operational Research, 227, 2, 391-400 (2013) · Zbl 1292.90234
[32] Li, C.; Yin, W.; Jiang, H.; Zhang, Y., An efficient augmented Lagrangian method with applications to total variation minimization, Computational Optimization and Applications, 56, 3, 507-530 (2013) · Zbl 1287.90066
[33] Mammen, E., Nonparametric regression under qualitative smoothness assumptions, The Annals of Statistics, 19, 2, 741-759 (1991) · Zbl 0737.62039
[34] Marcotte, P.; Zhu, D. L., Exact and inexact penalty methods for the generalized bilevel programming problem, Mathematical Programming, 74, 141-157 (1996) · Zbl 0855.90120
[35] Meyer, M. C., An extension of the mixed primal-dual bases algorithm to the case of more constraints than dimensions, Journal of Statistical Planning and Inference, 81, 13-31 (1999) · Zbl 1057.62510
[36] Meyer, M. C., A test for linear versus convex regression function using shape-restricted regression, Biometrika, 90, 1, 223-232 (2003) · Zbl 1034.62057
[37] Meyer, M. C., Consistency and power in tests with shape-restricted alternatives, Journal of Statistical Planning and Inference, 136, 3931-3947 (2006) · Zbl 1103.62035
[38] Nemirovskii, A. S.; Polyak, B. T.; Tsybakov, A. B., Convergence rate of nonparametric estimates of maximum-likelihood type, Problems of Information Transmission, 21, 258-271 (1985) · Zbl 0616.62048
[39] (Ray, S. C.; Kumbhakar, S. C.; Dua, P., Benchmarking for performance evaluation (2015), Springer)
[40] Rigall-I-Torrent, R.; Fluvià, M., Managing tourism products and destinations embedding public good components: A hedonic approach, Tourism Management, 32, 2, 244-255 (2011)
[41] Seijo, E.; Sen, B., Nonparametric least squares estimation of a multivariate convex regression function, Annals of Statistics, 39, 3, 1633-1657 (2011) · Zbl 1220.62044
[42] Semere, M., Determinants of hotel room rates in stockholm: A hedonic pricing approach (2014), Södertörn University
[43] Thrane, C., Examining the determinants of room rates for hotels in capital cities: The oslo experience, Journal of Revenue and Pricing Management, 5, 4, 315-323 (2007)
[44] Tibshirani, R., Regression shrinkage and selection via the lasso, Journal of the Royal Statistical Society Series B (Methodological), 58, 1, 267-288 (1996) · Zbl 0850.62538
[45] Vanderbei, R. J., Linear programming: Foundations and extensions. Linear programming: Foundations and extensions, Second Edition, International Series in Operations Research & Management Science, vol. 37 (2001), Kluwer Academic Publishers: Kluwer Academic Publishers Boston, MA · Zbl 1043.90002
[46] Wang, Y.; Wang, S.; Dang, C.; Ge, W., Nonparametric quantile frontier estimation under shape restriction, European Journal of Operational Research, 232, 3, 671-678 (2014) · Zbl 1305.62177
[47] Varian, H., The nonparametric approach to production analysis, Econometrica: Journal of the Econometric Society (1984) · Zbl 0558.90024
[48] Varian, H. R., The nonparametric approach to demand analysis, Econometrica, 50, 4, 945-973 (1982) · Zbl 0483.90006
[49] Zhou, H.; Lange, K., A path algorithm for constrained estimation, Journal of Computational and Graphical Statistics, 22, 2, 261-283 (2013)
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.