La gestion des groupes de variables en recherche directe

La Recherche par Coordonnées (CS), la Recherche par Motifs Généralisée (GPS) et la Recherche Directe sur Treillis Adaptatif (MADS) sont des exemples d'algorithmes robustes en optimisation non lin´eaire et non lisse. Afin d'améliorer la solution courante, ces méthodes utilisent des directions d'exploration qui affectent soit une seule variable à la fois (CS), soit plusieurs variables à la fois (GPS et MADS). Nous nous proposons ici de formaliser et généraliser ces approches, à travers le concept de “groupes” de variables : chaque groupe, gérée par l'algorithme de manière ´evolutive, génère des points d'essai en ne modifiant que les variables le concernant. Cela permet la construction d'un voisinage particulier potentiellement fructueux : dans le cas de variables de positionnement par exemple, cela permet de d´eplacer des objets ou des collections d'objets de manière individuelle. On utilise pour cette étude le logiciel NOMAD développé par Le Digabel (2009), qui est une implémentation écrite en C++ des tout derniers algorithmes de ce type, à savoir BIMADS et ORTHOMADS, respectivement introduits par Audet et al. (2008d) et Abramson et al. (2009b). Ces méthodes sont conçues pour l'optimisation de boîtes noires : les évaluations des fonctions relatives aux objectifs et contraintes sont le résultat d'un processus opaque, typiquement un code informatique. Par conséquent, ces fonctions peuvent ˆetre non lisses, non linéaires, non convexes ou discontinues, avec possiblement des domaines de d´efinition très fragmentés. Nous souhaitons également nous atteler à la résolution de problématiques concrètes liées à ce type d'optimisation : nous traiterons en particulier le cas d'un problème de localisation de balises à rayonnement gamma, sur des cartes en deux dimensions à domaines réalisables très fragmentés. Ce projet, mené en collaboration avec l'Institut de recherche d'HYDROQUE BEC (IREQ), vise à améliorer la pr´ecision de l'estimation du manteau neigeux et de l'équivalent Eau-Neige, afin de gérer les prévisions hydriques tout au long de l'année, et plus particulièrement aux moments critiques tels que la fonte des neiges printanière.

Abstract

Coordinate Search (CS), Generalized Pattern Search (GPS) and Mesh Adaptive Direct Search (MADS) are examples of robust algorithms for nonsmooth nonlinear optimization. To improve the current solution, these methods use exploratory directions that affect either a single variable at a time (CS), or several variables at once (GPS and MADS). We will formalize and generalize these approaches, through the concept of “groups” of variables : each group, managed by the algorithm dynamically, generates trial points by only changing the variables concerning them. This allows the construction of a particular and potentially fruitful neighborhood : for example, in the case of positioning variables, the algorithm can move objects or collections of objects sequentially. We use for this research the software NOMAD developed by Le Digabel (2009), which is an C++ implementation of the very latest MADS algorithms, namely BIMADS and ORTHOMADS, respectively introduced by Audet et al. (2008d) and Abramson et al. (2009b). These methods are designed for blackbox optimization : the evaluations of the objective and constraint functions are the result of an opaque process, typically a computer code. Therefore, these functions may be nonsmooth, non-linear, non-convex or discontinuous, with possibly highly fragmented domains. We aim to solve practical issues linked to this type of optimization : we will focus on the case of a gamma-monitoring beacons location problem, on two-dimensional maps with very fragmented domains. This project, in collaboration with the Research Institute of HYDRO-QUEBEC (IREQ), aims to improve the snowpack estimate accuracy in order to manage the hydrological forecast throughout the year, especially at critical times such as spring snowmelt.