The Least Trimmed Squares estimator in linear regression: classical algorithms and mathematical programming formulations

In this work, we first review the problem of regression in data analysis and the way it is generally addressed, having a fixed number of sample observations, in a non-Bayesian setting.We then go on to highlight the limitations posed by the standard techniques to estimate the regression coefficients and illustrate the potentially severe impact of the presence of outliers on the accuracy of the estimate, proposing an alternative robust regression approach based on the LTS estimator. After outlining several algorithms presented in relevant literature, both heuristic and exact, that try to overcome the combinatorial complexity of LTS estimation, we try to approach the LTS problem from the perspective and with the tools of operations research, reformulating it as a Mixed Integer Programming problem. We conclude with computational work on several datasets, which compares the performance of a MIQP (Mixed Integer Quadratic Programming) formulation and a MINLP (Mixed Integer Non-Linear Programming) one for the LTS problem in a Branch-and- Bound search carried out with the FICO Xpress commercial optimizer.

In questo lavoro analizziamo il problema di regressione in analisi dei dati e il modo in cui è generalmente trattato, avendo un numero prefissato di campioni, in un setting non-Bayesiano. Proseguiamo evidenziando le limitazioni degli approcci standard per la stima dei coefficienti di regressioni, e illustriamo l'impatto potenzialmente significativo della presenza di outliers sull'accuratezza della stima, proponendo un approaccio alternativo basato sulla regressione robusta e sullo stimatore LTS. Dopo aver ripercorso vari algoritmi per LTS presentati in letteratura, sia euristici che esatti, che provano ad aggirare la complessità combinatoria della stima LTS, ci interfacciamo con il problema dalla prospettiva della ricerca operativa e con gli strumenti di questa, riformulandolo come problema di Programmazione Intera Mista. Concludiamo con dei test computazionali su vari datasets, paragonando la performance di una formulazione MIQP (Programmazione Quadratica Intera Mista) e di una MINLP (Programmazione Non-Lineare Intera Mista) per il problema LTS in una ricerca Branch-and-Bound effettuata con il solutore commerciale FICO Xpress.