Théorie de l'optimisation sans dérivées dans le cas discontinu

Cette thèse vise à développer des algorithmes d’optimisation aptes à minimiser une fonction objectif présentant des discontinuités. Ce manuscrit propose d’abord une introduction aux concepts fondamentaux de l’optimisation discontinue, accompagné d’une revue de littérature, puis reprend le contenu de nos travaux de recherche sur le comportement de la méthode de recherche directe (« Direct Search Method », DSM) dans ce contexte. Notre première contribution est de rouvrir une discussion sur un travail pionnier dans l’étude de DSM dans un contexte discontinu, « Analysis of direct searches for discontinuous functions », Mathematical Programming Volume 133, pp. 299–325, 2012. Cette référence a identifié une condition technique sur le comportement de DSM qui permet d’étendre les résultats connus dans le cas continu vers le cas discontinu. Malheureusement, le théorème énoncé par les auteurs pour s’assurer que cette condition technique est vérifiée comporte une erreur. Nous mettons en évidence ce problème via un contre-exemple, puis adaptons DSM afin de le surmonter. Nous poursuivons avec une étude plus poussée des propriétés théoriques de DSM dans des cadres présentant des discontinuités potentielles. Pour ce faire, nous identifions une nouvelle adaptation de DSM permettant de garantir qu’elle génère une solution locale au problème d’optimisation. Nous prouvons également que ce résultat est plus fort que ceux énoncés dans d’autres travaux de la littérature, et obtenu sous des hypothèses de travail plus faibles. Enfin, nous introduisons le cadre de l’optimisation partitionnée, pour permettre à DSM de traiter efficacement des problèmes de grande dimension dans lesquels les discontinuités de la fonction objectif ne dépendent que de quelques-unes des variables. Nous optimisons ces variables par DSM, et en parallèle nous traitons toutes les autres avec un algorithme d’optimisation classique. Nous commençons par développer le cadre théorique, et nous prouvons que cette stratégie identifie une solution locale du problème. Ensuite, nous proposons plusieurs tests numériques pour confirmer qu’il est plus efficace de suivre cette stratégie que d’optimiser toutes les variables par une méthode d’optimisation sans dérivées. En complément, nous terminons par une illustration de l’optimisation partitionnée appliquée à une classe de problèmes issus du contrôle optimal, où seuls quelques états affectent un coût de Mayer discontinu et où toutes les autres variables (d’état et de contrôle) affectent un coût de Lagrange lisse.

Abstract

This thesis lies in the field of derivative-free optimization, and aims to extend the usual methods in the literature to the cases where the objective function is possibly discontinuous. This manuscript first introduces the fundamental concepts involved in discontinuous optimization, accompanied by a literature review. Then, it summarizes the content of my research papers about the behaviour of the Direct Search Method (DSM) in this context. The first part of this thesis discusses a former work that contributed to shape discontinuous optimization, “Analysis of direct search methods for discontinuous functions”, Mathematical Programming Volume 133, pp. 299–325, 2012. The authors identified a technical condition about DSM which allows to relax the continuity assumption in most results from the literature, so they remain valid in the discontinuous case. Nevertheless, this technical condition may be difficult to satisfy and the related theorem provided by the authors is incorrect. The thesis highlights this error via a counterexample, and corrects it by adapting DSM. The second part of the manuscript strengthens the theoretical properties for DSM. It is proven that under an adaptation explicitly constructed, DSM generates a local solution to the optimization problem, and this result holds true even in discontinuous cases. It is also proven that the assumptions this adaptation relies on are weaker and more generic than in former work from the literature. Finally, the manuscript introduces the framework of partitioned optimization to allow DSM to solve large scale problems where the discontinuities in the objective function depend only on a subset of the variables. The idea is that in such cases, it is more efficient to address these variables via DSM and to leave all the others to an usual algorithm relying on derivatives. This hybrid strategy still identifies a local solution to the optimization problem. It is also proven that the required structure on the optimization problem is common, as it is indeed met in several classes of problems. Last, some numerical examples are provided, highlighting that the strategy under discussion is indeed more efficient than regular methods from the literature. In addition, the manuscript proposes an illustration of the application of partitioned optimization to a class of optimal control problems where only the Mayer cost (depending on the state of the sytem at a few times) has discontinuities, while the Lagrange cost (depending on all others variables) is smooth.