Ph.D
Group : Graphs, ALgorithms and Combinatorics
Hypercubes latins maximin pour l’échantillonnage de systèmes complexes
Starts on 01/10/2014
Advisor : TOMASIK, Joanna
[RIMMEL Arpad et WEISSER Marc-Antoine]
Funding : Contrat doctoral uniquement recherche
Affiliation : Centrale Supélec
Laboratory :
Defended on 24/01/2018, committee :
Directeur de thèse :
- Mme Joanna TOMASIK CentraleSupélec
Rapporteurs :
- M. Jarosław BYRKA University of Wrocław
- M. Tristan CAZENAVE Université Paris-Dauphine
Examinateurs :
- Mme Cristina BAZGAN Université Paris-Dauphine
- M. Yannis MANOUSSAKIS Université Paris-Sud
- M. Arpad RIMMEL CentraleSupélec
- M. Marc-Antoine WEISSER CentraleSupélec
- M. Bertrand LE CUN Google Inc.
Research activities :
Abstract :
A Latin Hypercube Design (LHD) is a set of n points in dimension k with integer coordinates contained in a hypercube of size n k , such that its points do not share a coordinate on any dimension. In maximin LHDs the separation distance, i.e. the minimal distance between two points, is maximal. Maximin LHDs are widely used in metamodeling thanks to their space filling and noncollapsing properties which make them appropriate for sampling. As most work concerning LHDs focused on heuristic algorithms to produce them, we decided to make a detailed study of this problem, including its complexity, approximability, and the design of practical heuristic algorithms. To conduct this study, we generalized the maximin LHD construction problem by defining the maximin partial Latin Hypercube completion problem: given a partial LHD (an LHD with missing points), complete it with the maximum separation distance possible. The subproblem where the partial LHD is initially empty corresponds to the classical LHD construction problem. We studied the complexity of the completion problem and proved its NP-completeness for all norms in dimensions k ≥ 3, and for usual norms (i.e. norms Lp, with p ∈ N and norm L∞) on the plane. As we did not determine the complexity of the subproblem, we searched for performance guarantees of algorithms which may be designed for both problems. On the one hand, we found that the completion problem is inapproximable for all norms in dimensions k ≥ 3. We also gave a weaker inapproximation result for norm L∞ in dimension k = 2. On the other hand, we designed an approximation algorithm for the construction problem which we proved using two new upper bounds we introduced. Besides the theoretical aspect of this study, we worked on heuristic algorithms adapted for these problems, focusing primarily on the Simulated Annealing metaheuristic. We proposed a new evaluation function for the construction problem and new mutations for both the construction and completion problems, improving the results found in the literature. We observed that the behaviour of the completion problem changed depending on the number of points in the initial pLHD, calling for the use of different mutations. Taking advantage of this fact, we enriched the Simulated Annealing algorithm by using a bandit method to choose the most appropriate mutation on the fly, outperforming both mutations for intermediate number of points preset.
