Problèmes d'optimisation globale en statistique robuste
Institution:
Toulouse 3Disciplines:
Directors:
Abstract EN:
Robust statistics is a branch of statistics dealing with the analysis of data containing contaminated observations. The robustness of an estimator is measured notably by means of the breakdown point. High-breahdown point estimators are usuallly defined as global minima of a non-convex scale of the erros, hence their computation is a challenging global optimization problem. The objective of this dissertation is to investigate the potential distribution of modern global optimization methods to this class of problem. The first part of this thesis is devoted to the tau-estimator for linear regression, which is defined as a global minimum of a nonconvex differentiable function. We investigate the impact of incorporating clustering techniques and stopping conditions in existing stochastic algorithms. The consequences of some phenomena involving the nearest neighbor in high dimension on clustering global optimization algorithms is thoroughly discussed as well. The second part is devoted to deterministic algorithms for computing the least trimmed squares regression estimator, Which is defined through a nonlinear mixed-integer program. Due to the combinatorial nature of this problem, we concentrated on obtaining lower bounds to be used in a branch-and-bound algorithm. In particular, we propose a second-order cone relaxation that can be complemented with concavity cuts that we obtain explicitly. Global optimality conditions are also provided.
Abstract FR:
La statistique robuste est une branche de la statistique qui s'intéresse à l'analyse de données contenant une proportion significative d'observations contaminées avec des erreurs dont l'ampleur et la structure peuvent être arbitraires. Les estimateurs robustes au sens du point de rupture sont généralement définis comme le minimum global d'une certaine mesure non-convexe des erreurs, leur calcul est donc un problème d'optimisation globale très couteux. L'objectif de cette thèse est d'étudier les contributions possibles des méthodes d'optimisation globales modernes à l'étude de cette classe de problème. La première partie de la thèse est consacrée au tau-estimateur pour la régression linéaire robuste, qui est défini comme étant un minimum global d'une fonction non-convexe et dérivable. Nous étudions l'impact des techniques d'agglomération et des conditions d'arrêt sur l'efficacité des algorithmes existants. Les conséquences de certains phénomènes liés au voisin le plus proche en grande dimension sur ces algorithmes agglomératifs d'optimisation globale sont aussi mises en évidence. Dans la deuxième partie de la thèse, nous étudions des algorithmes déterministes pour le calcul de l'estimateur de moindres carrés tronqués, qui est défini à l'aide d'un programme en Nombres entiers non linéaire. En raison de sa nature combinatoire, nous avons dirigé nos efforts vers l'obtention de bornes inférieures pouvant être utilisées dans un algorithme du type branch-and-bound. Plus précisément, nous proposons une relaxation par un programme sur le cône de deuxième ordre, qui peut être renforcée avec des coupes dont nous présentons l'expression explicite. Nous fournissons également des conditions d'optimalité globale.