Optimisation de boîtes noires à précision variable

Ce projet s'insère dans le cadre d'un domaine de mathématiques appliquées qu'on appelle optimisation. Il s'agit de l'étude de problèmes dans lesquels on souhaite maximiser ou minimiser une certaine quantité d'intérêt qu'on nommera fonction objectif, tout en respectant certaines limitations éventuelles qu'on désignera par contraintes. Dans notre cadre d'étude, la fonction objectif est une boîte noire, terme désignant une fonction dont la forme analytique est inconnue. La seule information qu'on puisse obtenir est la valeur qu'elle prend lorsqu'on l'évalue en un point, sans qu'on sache comment cette valeur a été calculée. Ainsi, il faut trouver un point minimisant la valeur renvoyée, et ce sans connaître le comportement de la fonction. Enfin, on supposera dans ce projet que les valeurs renvoyées par la fonction objectif ne sont pas exactes. L'objectif de ce travail est d'optimiser des fonction dites bruitées, et dont l'amplitude du bruit est réglable. Toute évaluation de la fonction objectif renvoie la véritable valeur de la fonction plus une erreur aléatoire. L'amplitude du bruit sera alors l'écart-type de cette erreur. Ainsi, une boîte noire à précision variable est une fonction inconnue (dont on ne peut pas prédire le comportement) qui ne peut jamais être évaluée de façon certaine, à cause d'une erreur aléatoire apparaissant à chaque évaluation, mais dont on peut limiter l'amplitude en réglant la précision du calcul. On dispose ici d'un «levier» de précision, offrant un compromis entre garantie de qualité de la valeur observée (à haute précision) au prix d'un grand temps de calcul, et incertitude entourant la valeur renvoyée (à faible précision) mais obtenue rapidement. Les recherches résumées dans ce document ont pour but de proposer une façon d'optimiser de telles fonctions, c'est-à-dire un moyen de trouver un point minimisant la valeur exacte qu'elles devraient renvoyer en l'absence d'erreur. Un tel point devrait également pouvoir être calculé de façon efficace, en un temps raisonnable et un effort de calcul faible. Pour cela, nous exploitons la précision variable pour toujours estimer la fonction objectif avec une précision au juste nécessaire : suffisamment grande pour affirmer qu'un point est meilleur qu'un autre, et assez basse pour que ces calculs soient les plus rapides possibles.

Abstract

This document aims to introduce the reader to some research in a sub-topic in optimisation, a field of applied mathematics which tries to maximise or minimise a quantity named objective function. This quantity depends on some variables that can be chosen by the optimiser. Usually, one may exploits its knowledge of the structure of the function to make the optimisation as fast as possible. For example, knowing that a given variable unconditionally diminishes the objective while augmenting, one can decide to maximise that variable. One may also think about the derivatives of the function, as knowing these helps to easily find some promising directions to search on. In blackbox optimisation, the topic this work will discuss, such knowledge in intractable. When the objective is a blackbox, its behaviour cannot be recovered from observations and calculus. As this kind of function is naturally hard to minimise, finding efficient ways to perform it is the main goal of this field. In addition to these difficulties, one may face an harder blackbox problem named noisy blackbox problem. In this context, the blabkbox to optimise is noisy, which means any value it returns is possibly inaccurate. The value given to the optimiser is the real value one should expect, plus a random error. We will denote by magnitude of the noise the standard deviation of these errors. It will be assumed that the magnitude can be chosen by the optimiser, with the drawback that the lower the desired magnitude is, the higher the computation time is. Then, this document studies noisy blackboxes with adaptive precision : functions with unpredictable behaviour (blackboxes) which return inaccurate values (because the functions are noisy) but with a controllable amount of noise (as the precision is adaptive). The main goal of this research is to find an efficient way to minimise such a function. By minimising, we mean finding a set of variables which have the lowest expected returned value: assuming that the errors are void in average, we target the lowest real, non-noisy, value returned by the function. To reach that goal, the adaptive precision tradeoff have been useful. We tried to perform any calculus at the lowest precision acceptable, in order to make the computation as fast as possible, but accurate enough to ensure the optimisation determines with few risks where the interesting solutions are.