Global optimization problems in robust statistics

Problèmes d’optimisation globale en statistique robuste

Salvador Flores (1, 2)

1 PRES Université de Toulouse
2 AMIS - Anthropologie Moléculaire et Imagerie de Synthèse

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-breakdown point estimators are usually defined as global minima of a non-convex scale of the errors, hence their computation is a challenging global optimization problem. The objective of this dissertation is to investigate the potential contributions of modern global optimization methods to this class of problems. 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 are 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.

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 measure non-convexe des erreurs, leur calcul est donc un problème d’optimisation globale très coûteux. L’objectif de cette thèse est d’étudier les contributions possibles des méthodes d’optimisation globale modernes à l’étude de cette classe de problèmes. 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 nonconvexe 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 des 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.

Mots clés: Robust regression; breakdown point; global optimization; curse of dimensionality; SOCP relaxation; concavity cuts; global optimality conditions

Mots clés: Regression robuste; point de rupture; conditions d’arrêt; optimisation globale; fléau de la dimension; relaxation SOCP; coupes de concavité; conditions d’optimalité globale

Domaines: Analyse numérique [math.NA]; Calcul [stat.CO]; Optimisation et contrôle [math.OC]

Salvador Flores. Global optimization problems in robust statistics. Numerical Analysis [math.NA]. Université toulouse 3 Paul Sabatier, 2011. English. ⟨NNT : ⟩. ⟨tel-01935617⟩