[en] A range of procedures in both robustness and diagnostics require optimisation of a target functional over all subsamples of given size. Whereas such combinatorial problems are extremely difficult to solve exactly, something less than the global optimum can be ‘good enough’ for many practical purposes, as shown by example. Again, a relaxation strategy embeds these discrete, high-dimensional problems in continuous, low-dimensional ones. Overall, nonlinear optimisation methods can be exploited to provide a single, reasonably fast algorithm to handle a wide variety of problems of this kind, thereby providing a certain unity. Four running examples illustrate the approach. On the robustness side, algorithmic approximations to minimum covariance determinant (MCD) and least trimmed squares (LTS) estimation. And, on the diagnostic side, detection of multiple multivariate outliers and global diagnostic use of the likelihood displacement function. This last is developed here as a global complement to Cook’s (in J. R. Stat. Soc. 48:133–169, 1986) local analysis. Appropriate convergence of each branch of the algorithm is guaranteed for any target functional whose relaxed form is—in a natural generalisation of concavity, introduced here—‘gravitational’. Again, its descent strategy can downweight to zero contaminating cases in the starting position. A simulation study shows that, although not optimised for the LTS problem, our general algorithm holds its own with algorithms that are so optimised. An adapted algorithm relaxes the gravitational condition itself.
Disciplines :
Mathematics
Author, co-author :
Critchley, Frank; The Open University > Department of Mathematics and Statistics
Schyns, Michael ; Université de Liège - ULiège > HEC - École de gestion de l'ULiège > Informatique de gestion
Haesbroeck, Gentiane ; Université de Liège - ULiège > Département de mathématique > Statistique (aspects théoriques)
Fauconnier, Cécile; Université de Liège - ULiège > HEC - Ecole de Gestion de l'ULg > Informatique de Gestion
Lu, Guobing; University of Bristol
Atkinson, Richard A; University of Birmingham
Wang, Dong Quian; Victoria University of Wellington
Language :
English
Title :
A relaxed approach to combinatorial problems in robustness and diagnostics
Atkinson, A. C.: Masking unmasked. Biometrika 73, 533-541 (1986).
Bazaraa, M. S., Sherali, H. D., Shetty, C. M.: Nonlinear Programming: Theory and Algorithms, 2nd edn. Wiley, New York (1993).
Conn, A. R., Gould, N. I. M., Toint, P. L.: Trust-Region Methods. MPS-SIAM Series on Optimization (2000).
Cook, R. D.: Assessment of local influence (with discussion). J. R. Stat. Soc. B 48, 133-169 (1986).
Critchley, F., Atkinson, R. A., Lu, G., Biazi, E.: Influence analysis based on the case sensitivity function. J. R. Stat. Soc. B 63, 307-323 (2001).
Critchley, F., Schyns, M., Haesbroeck, G., Kinns, D., Atkinson, R. A., Lu, G.: The case sensitivity function approach to diagnostics and robust computation: a relaxation strategy COMPSTAT 2004. In: Antoch, J. (ed.) Proceedings in Computational Statistics, pp. 113-125. Physica-Verlag, Heidelberg (2004).
Danninger, G., Bomze, I.: Using copositivity for global optimality criteria in concave quadratic programming. Math. Program. 62, 575-580 (1993).
Gilley, O. W., Kelley Pace, R.: On the Harrison and Rubinfeld data. J. Environ. Econ. Manag. 31, 403-405 (1996).
Harrison, D., Rubinfeld, D. L.: Hedonic prices and the demand for clean air. J. Environ. Econ. Manag. 5, 81-102 (1978).
Hawkins, D. M.: The Feasible Solution algorithm for least trimmed squares regression. Comput. Stat. Data Anal. 17, 185-196 (1993).
Hawkins, D. M.: The Feasible Solution algorithm for the minimum covariance determinant estimator. Comput. Stat. Data Anal. 17, 197-210 (1994).
Hawkins, D. M., Olive, D. J.: Improved feasible solution algorithms for high breakdown estimators. Comput. Stat. Data Anal. 30, 1-11 (1999).
Hawkins, D. M., Olive, D. J.: Inconsistency of resampling algorithms for high-breakdown regression estimators and a new algorithm. J. Am. Stat. Assoc. 97, 136-147 (2002).
Horst, R., Tuy, H.: Global Optimization. Deterministic Approaches, 3rd edn. Springer, Berlin (2003).
Pardalos, P. M., Rosen, J. B.: Constrained Global Optimization: Algorithms and Applications. Lecture Notes in Computer Science. Springer, New York (1987).
Rousseeuw, P. J.: Multivariate estimation with high breakdown point. In: Grossmann, W., Pflug, G., Vincze, I., Wertz, W. (eds.) Mathematical Statistics and Applications, vol. B, pp. 283-297. Reidel, Dordrecht (1985).
Rousseeuw, P. J., Leroy, A. M.: Robust Regression and Outlier Detection. Wiley, New York (1987).
Rousseeuw, P. J., van Driessen, K.: A fast algorithm for the minimum covariance determinant estimator. Technometrics 41, 212-223 (1999).
Rousseeuw, P. J., van Driessen, K.: Computing LTS regression for large data sets. Data Mining Knowl. Discov. 12, 29-45 (2006).
Sartenaer, A.: Some recent developments in nonlinear optimization algorithms. ESAIM Proc. 13, 41-64 (2003).
Schyns, M., Haesbroeck, G., Critchley, F.: RelaxMCD, smooth optimisation for the minimum covariance determinant estimator. HEC-preprint (2008).