Opportunisme et ordonnancement en optimisation sans dérivées

Ce mémoire traite de comparaisons de stratégies algorithmiques applicables à certains algorithmes d'optimisation de boîtes noires. Une boîte noire est un problème typiquement lourd en temps de calcul, non différentiable, bruité et potentiellement propriétaire. Afin de résoudre ces problèmes, des techniques n'utilisant pas les informations sur les dérivées des expressions algébriques définissant les problèmes ont été conçues. Les méthodes ciblées pour y implémenter les stratégies algorithmiques sont celles figurant dans un cadre de travail spécifique. Les méthodes doivent contenir une étape nécessitant une séquence d'évaluations de la fonction objectif à des points figurant dans une liste prédéterminée. Les méthodes de recherche directe correspondent à ces critères ; elles sont des méthodes contenant une série d'évaluations de points, et basent la détermination de la prochaine liste de candidats sur les valeurs obtenues à ces points. Les méthodes d'optimisation par recherche directe identifiées sont la recherche par coordonnées (CS), la recherche par motifs généralisée(GPS), la recherche par ensembles générateurs (GSS), la recherche directe par treillis adaptatifs (MADS) et le filtrage implicite (IMFIL). La stratégie algorithmique étudiée est la stratégie opportuniste. Elle désigne l'arrêt de l'étape de l'algorithme comprenant une série d'évaluations séquentielles. L'arrêt peut-être fait après un ou plusieurs succès, c'est-à-dire l'évaluation d'un point pour lequel la valeur de la fonction objectif est inférieure à la minimale encourue précédemment dans la résolution. Plusieurs déclinaisons de la stratégie sont identifiées, implémentées et testées sur une batterie de problèmes tests, afin de déterminer numériquement leurs impacts. L'arrêt d'une série d'évaluations implique que l'ordre des points à évaluer impacte la performance de la stratégie opportuniste. On identifie les stratégies d'ordonnancements suivantes afin de les jumeler à la stratégie opportuniste et d'étudier leurs impacts : lexicographique, aléatoire, utilisant la direction du dernier succès et utilisant les modèles. Toutes ces stratégies sont implémentées et testées sur l'ensemble de problèmes tests. Les tests numériques sur un ensemble de problèmes incluant une boîte noire révèlent que l'opportunisme le plus rudimentaire, dont le critère d'arrêt est l'obtention d'un simple succès, est bénéfique à divers degrés pour toutes les méthodes de recherche directe identifiées sauf le filtrage implicite. Les stratégies d'ordonnancement utilisant les modèles, aléatoire et utilisant la direction du dernier succès, forment le classement des stratégies bénéfiques. L'ordonnancement lexicographique jumelé à l'opportunisme nuit aux algorithmes.

Abstract

This work considers algorithmic strategies to implement and compare through various blackbox optimization algorithms. A blackbox is a problem to be minimized which is typically computationally heavy, non-differentiable, noisy and may be driven by a private or legacy code. Solving these problems requires optimization techniques that are not using first-order derivative informations of the analytical functions underlying the blackbox. The methods in which the algorithmic strategies are to be implemented need to fit a specific framework. They must contain a step in which there is a sequence of evaluations of the objective function. Those evaluations are to be made at predetermined list of candidate points. A family of derivative-free methods, the direct search methods, qualifies as methods fitting this framework. Direct search methods choose the next list of candidate points based on the function evaluation values at the current list of candidates. The identified direct search methods for this work include the Coordinate Search (CS), Generalized Pattern Search (GPS), Generative Set Search (GSS), Mesh-Adaptive Direct Search (MADS), and Implicit Filternig (IMFIL). The main algorithmic strategy studied in this work is the opportunistic strategy, which designates the premature ending of the algorithm's step consisting of serial function evaluations. This termination occurs after one or more successes. A success indicates the finding of a candidate point for which the objective function value is improved from the past best known point. Three variations of the opportunistic strategy are identified. The termination of the step implies that the order of in the candidate list affects the performance of the strategy. Four main ordering strategies are identified and teamed with the opportunistic strategy in order to determine what impact does ordering have in this context. Those strategies consist of a lexicographic ordering, a random ordering, an ordering based on the direction of the last success and an ordering based on a quadratic surrogate function. Numerical results are obtained via the resolution of a large problem set including a typical blackbox. The results show that the simplest of the opportunistic strategies, the one that terminates immediately after the identification of a single success, benefits the most to all the methods, beside Implicit Fitlering, for which a standard non-opportunistic use works best. The ordering strategies by order of performance gain is the quadratic surrogate-based, the random and the last success direction-based. Lexicographic ordering mixed with opportunism deteriorates the performance of the methods.