On s’intéresse dans cette thèse à l’introduction d’aléatoire dans des algorithmes d’optimisation numérique étant par ailleurs déterministes. Notre étude se concentre sur les méthodes d’optimisation sans dérivées, un sous-domaine de l’optimisation numérique dans lequel l’information locale
fournie par les dérivées ne peut être exploitée algorithmiquement. Pour pallier ce manque d’information, de telles méthodes effectuent généralement de nombreux appels à la fonction objectif. L’objectif de cette thèse est d'étudier les réductions potentielles de cette consommation en appels de fonction à travers l’utilisation d’éléments aléatoires, sans compromettre les garanties
théoriques des algorithmes considérés.
La première partie de cette thèse introduit les méthodes de recherche directe, qui forment l'une des principales catégories d'algorithmes d'optimisation sans dérivées. Une variante de recherche directe basée sur des directions aléatoires est présentée, et analysée grâce à la notion de descente probabiliste, que l'on introduira. De ce concept découle la convergence presque sûre de notre algorithme, ainsi que des résultats de complexité au pire cas qui se vérifient avec une probabilité écrasante. La technique utilisée pour obtenir ces derniers se révèle suffisamment générale pour s'appliquer à un large éventail d'algorithmes basés sur des propriétés probabilistes. Nous prolongeons ensuite notre étude afin de pouvoir traiter des contraintes simples sur les variables du problème, ce qui nous permet de comparer notre implémentation à un solveur commercial de référence. On observe alors que la réduction du nombre d'évaluations de fonctions requis par l'algorithme induit un gain considérable en performance par rapport aux algorithmes déterministes classiques, et ce que le problème soit avec ou sans contraintes.
La seconde partie de cette thèse a pour but d'exploiter le gain réalisé dans la partie précédente en considérant des aspects locaux d'ordre deux. Elle débute par une étude précise des propriétés déterministes nécessaires pour établir des résultats dits du second ordre. Par la suite, nous présentons une nouvelle technique qui vise à séparer les aspects d'ordres un et deux. Une telle stratégie permet notamment d'introduire de l'aléatoire sur le premier ordre sans compromettre les résultats déterministes du second, ce qui s'avère une nouvelle fois plus performant qu'une variante purement déterministe. Nous concluons notre travail en décrivant une classe de propriétés aléatoires d'ordre deux qui recoupe plusieurs techniques couramment employées. |
In this thesis, we investigate the introduction of random elements within otherwise deterministic optimization schemes. Our study focuses on derivative-free algorithms, a field of numerical optimization in
which the unavailability of derivatives as an algorithmic tool often induces an important computational expense in terms of calls to the objective function. The thesis studies possible reduction of this cost through
randomization, with an emphasis on the preservation of theoretical guarantees.
In a first part, this thesis reviews the class of direct-search methods, one of the main classes of derivative-free algorithms. We present a direct-search instance based on randomly generated directions. By introducing the concept of probabilistic descent, we are able to establish almost-sure convergence of the proposed framework, as well as to derive a worst-case complexity analysis holding with overwhelming probability. The latter study is shown to be applicable to a wide range of algorithms relying on probabilistic properties. Extensions of the proposed scheme so as to handle simple constraints on the optimization variables are described, and the resulting implementation is compared with a state-of-the-art commercial solver. In both unconstrained and constrained cases, the economy in function calls allowed by the introduction of randomness yields a superior performance over deterministic algorithms.
The second part of the thesis builds on this lower consumption to consider additional local information of second-order type. We provide a thorough study of the deterministic properties that have to be satisfied to ensure so-called second-order guarantees. Then, we develop an original technique to dissociate first and second-order aspects. Such a strategy allows to consider random first-order quality and deterministic second-order one, and proves again to be beneficial in a non-convex setting. A promising investigation on random second-order features that encompasses several known techniques concludes the study. |