×

Locating hyperplanes to fitting set of points: a general framework. (English) Zbl 1458.90467

Summary: This paper presents a family of methods for locating/fitting hyperplanes with respect to a given set of points. We introduce a general framework for a family of aggregation criteria, based on ordered weighted operators, of different distance-based errors. The most popular methods found in the specialized literature, namely least sum of squares, least absolute deviation, least quantile of squares or least trimmed sum of squares among many others, can be cast within this family as particular choices of the errors and the aggregation criteria. Unified mathematical programming formulations for these methods are provided and some interesting cases are analyzed. The most general setting give rise to mixed integer nonlinear programming problems. For those situations we present inner and outer linear approximations to assess tractable solution procedures. It is also proposed a new goodness of fitting index which extends the classical coefficient of determination and allows one to compare different fitting hyperplanes. A series of illustrative examples and extensive computational experiments implemented in are provided to show the applicability of the proposed methods.

MSC:

90B85 Continuous location
62J05 Linear regression; mixed models
90C26 Nonconvex programming, global optimization

Software:

CRIO; VanHuffel
PDF BibTeX XML Cite
Full Text: DOI arXiv

References:

[1] Amaldi, E.; Coniglio, S.; Taccari, L., Discrete optimization methods to fit piecewise affine models to data points, Comput. Oper. Res., 75, 214-230, (2016) · Zbl 1349.68209
[2] Atkinson, A. C.; Cheng, T. C., Computing least trimmed squares regression with the forward search, Stat. Comput., 9, 251-263, (1999)
[3] Balas, E., Disjunctive programming, Ann. Discrete Math., 5, 3-51, (1979) · Zbl 0409.90061
[4] Bargiela, A.; Hartley, J. K., Orthogonal linear regression algorithm based on augmented matrix formulation, Comput. Oper. Res., 20, 8, 829-836, (1993) · Zbl 0783.90121
[5] Bertsimas, D.; King, A.; Mazumder, R., Best subset selection via a modern optimization Lens, Ann. Stat., 44, 2, 813-852, (2016) · Zbl 1335.62115
[6] Bertsimas, D.; Mazumder, R., Least quantile regression via modern optimization, Ann. Stat., 42, 6, 2494-2525, (2014) · Zbl 1302.62154
[7] Bertsimas, D.; Shioda, R., Classification and regression via integer optimization, Oper. Res., 55, 2, 252-271, (2007) · Zbl 1167.90593
[8] Blanco, V.; Puerto, J.; El-Haj Ben-Ali, S., Revisiting several problems and algorithms in continuous location with ℓ_{τ} norms, Comput. Optim. Appl., 58, 3, 563-595, (2014) · Zbl 1297.90073
[9] Blanco, V., Puerto, J., Salmerón, R., 2016. A general framework for locating hyperplanes to fitting set of points. available at. https://arxiv.org/abs/1505.03451.
[10] Boggs, P. T.; Rogers, J. E., Orthogonal distance regression, Contemp. Math., 112, 183-194, (1990)
[11] Bradley, P. S.; Mangasarian, O. L., K-plane clustering, J. Global Opt., 16, 1, 23-32, (2000) · Zbl 0990.90135
[12] Carrizosa, E.; Conde, E.; Fernández, F. R.; Muñoz, M.; Puerto, J., Pareto optimality in linear regression, J. Math. Anal. Appl., 190, 129-141, (1995) · Zbl 0820.62062
[13] Carrizosa, E.; Plastria, F., The determination of a “least quantile of squares regression line” for all quantiles, Comput. Stat. Data Anal., 20, 5, 467-479, (1995) · Zbl 0900.62351
[14] Cavalier, T.; Melloy, B., An iterative linear programming solution to the Euclidean regression model, Comput. Oper. Res., 18, 8, 655-661, (1991) · Zbl 0741.90094
[15] Diaz-Báñez, J. M.; Mesa, J. A.; Schöbel, A., Continuous location of dimensional structures, Eur. J. of Oper. Res, 152, 1, 22-44, (2004) · Zbl 1040.90021
[16] Drezner, Z.; Steiner, S.; Wesolowsky, G. O., On the circle closest to a set of points, Comput. Oper. Res, 29, 6, 637-650, (2002) · Zbl 0994.90088
[17] Durbin, J.; Watson, G. S., Testing for serial correlation in least squares regression II, Biometrika, 38, 159-178, (1951) · Zbl 0042.38201
[18] Edgeworth, F. Y., On observations relating to several quantities, Hermathena, 6, 279-285, (1887)
[19] Fernández, E.; Pozo, M. A.; Puerto, J., Ordered weighted average combinatorial optimization: formulations and their properties., Discrete Appl. Math., 169, 97-118, (2014) · Zbl 1296.90111
[20] Fernández, E.; Pozo, M. A.; Puerto, J.; Scozzari, A., Ordered weighted average optimization in multiobjective spanning tree problems, Eur. J. Oper. Res., 260, 886903, 886-903, (2017) · Zbl 1403.90637
[21] Fletcher, P. T., Geodesic regression and the theory of least squares on Riemannian manifolds, Int. J. Comput. Vis., 105, 171-185, (2013) · Zbl 1304.62092
[22] Francis, R. L.; Lowe, T. J.; Tamir, A., Aggregation error bounds for a class of location models, Oper. Res., 48, 2, 294-307, (2000) · Zbl 1106.90355
[23] Gauss, C. F., Theoria Motus Corporum Coelestium in Sectionibus Conicis Solum Ambientium (Theory of the Motion of the Heavenly Bodies Moving about the Sun in Conic Sections), (1809), Dover Publications Mineola
[24] Giloni, A.; Padberg, M., Alternative methods of linear regression, Math. Comput. Model., 35, 3-4, 361-374, (2002) · Zbl 1010.62063
[25] Grzybowski, J.; Nickel, S.; Pallaschke, D.; Urbański, R., Ordered Median functions and symmetries, Optimization, 60, 801-811, (2011) · Zbl 1229.90074
[26] Hampel, F. R., Beyond location parameters: robust concepts and methods, Bull. Int. Stat. Inst., 46, 375-382, (1975) · Zbl 0349.62029
[27] Hoerl, A.; Kennard, R., Ridge regression, Encyclopedia of Statistical Sciences, vol. 8, 129-136, (1988), Wiley New York
[28] Hofmann, M.; Gatu, C.; Kontoghiorghes, E. J., An exact least trimmed squares algorithm for a range of coverage values., J. Comput. Graph Stat., 19, 1, 191-204, (2010)
[29] Humphreys, R. M., Studies of luminous stars in nearby galaxies. I. supergiants and o stars in the milky way, Astrophys. J. Suppl. S., 38, 309-350, (1978)
[30] Lee, S.; Grossmann, I., New algorithms for nonlinear generalized disjunctive programming, Comput. Chem. Eng., 24, 2125-2214, (2000)
[31] Love, R. F.; Morris, J. G., Modelling inter-city road distances by mathematical functions, Oper. Res. Q, 23, 1, 61-71, (1972) · Zbl 0231.90059
[32] Mangasarian, O. L., Arbitrary-norm separating plane, Oper. Res. Lett., 24, 1-2, 15-23, (1999) · Zbl 1028.90037
[33] Marín, A.; Nickel, S.; Puerto, J.; Velten, S., A flexible model and efficient solution strategies for discrete location problems, Discrete Appl. Math., 157, 5, 1128-1145, (2009) · Zbl 1163.90609
[34] McKean, J. W.; Sievers, G. L., Coefficients of determination for least absolute deviation analysis, Stat. Probab. Lett., 5, 1, 49-54, (1987) · Zbl 0612.62105
[35] Megiddo, N.; Tamir, A., Finding least-distance lines, SIAM J. Algebraic Discrete Methods, 4, 2, 207-211, (1983) · Zbl 0517.05007
[36] Miller, A., Subset Selection in Regression, (2002), CRC Press Washington · Zbl 1051.62060
[37] Miyashiro, R.; Takano, Y., Mixed integer second-order cone programming formulations for variable selection in linear regression, Eur. J. Oper. Res., 247, 3, 721-731, (2015) · Zbl 1346.90616
[38] Narula, S. C.; Wellington, J. F., Multiple criteria linear regression, Eur. J. Oper. Res., 181, 2, 767-772, (2007) · Zbl 1131.62308
[39] Nickel, S.; Puerto, J., A unified approach to network location, Networks, 34, 283-290, (1999) · Zbl 0948.90086
[40] Nickel, S.; Puerto, J., Location Theory: A Unified Approach, (2005), Springer Verlag · Zbl 1229.90001
[41] Pinson, P.; Nielsen, H.; Madsen, H.; Nielsen, T., Local linear regression with adaptive orthogonal Fitting for the wind power application, Stat. Comput, 58, 1, 59-71, (2008)
[42] Rousseeuw, P., Least Median of squares regression, J. Am. Stat. Assoc., 79, 871-880, (1984) · Zbl 0547.62046
[43] Rousseeuw, P.; Leroy, A., Robust Regression and Outlier Detection, (2003), Wiley New York
[44] Rousseeuw, P. J., Multivariate estimation with high breakdown point, Math. Stat. App. B, 283-297, (1983)
[45] Schöbel, A., Locating least-distant lines with block norms, Stud. Locat. Anal., 10, 139-150, (1996) · Zbl 0904.90101
[46] Schöbel, A., Locating line segments with vertical distances, Stud. Locat. Anal., 11, 143-158, (1997) · Zbl 0928.90053
[47] Schöbel, A., Locating least distant lines in the plane, Eur. J. Oper. Res, 106, 1, 152-159, (1998)
[48] Schöbel, A., Locating Lines and Hyperplanes: Theory and Algorithms, (1999), Kluwer Academic Publishers · Zbl 0918.90102
[49] Stone, M., Cross-validatory choice and assessment of statistical predictions, J. R. Stat. Soc. B, 36, 111-147, (1974) · Zbl 0308.62063
[50] Thoai, R., D.C. programming: an overview, J. Optimiz. Theory Appl., 193, 1, 1-43, (1999)
[51] Van Huffel, S.; Vanderwalle, J., The total least squares problem: computational aspects and analysis, SIAM Front. Appl. Math., (1991), ISBN: 978-0-89871-275-9
[52] Ward, J. E.; Wendell, R. E., A new norm for measuring distance which yields linear location models, Oper. Res, 28, 836-844, (1980) · Zbl 0443.90029
[53] Ward, J. E.; Wendell, R. E., Using block norms for location modeling, Oper. Res., 33, 1074-1090, (1985) · Zbl 0582.90026
[54] Yager, R. R.; Beliakov, G., OWA operators in regression problems, IEEE Trans. Fuzzy Syst., 18, 1, 106-113, (2010)
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.