Contact : pierre-yves.bouchet@polymtl.ca
Directeur : Charles Audet
On considère dans ce projet une fonction lipschitzienne f de IR^n dans IR, dont on souhaite trouver le minimum via une méthode algorithmique n'exploitant jamais les valeurs prises par f. À défaut, nous ne considérons n'avoir accès qu'à des évaluations bruitées aléatoirement de la fonction, et dont l'amplitude du bruit est réglable. Cela se traduit par le fait qu'en tout point x, on puisse définir une valeur σ > 0 pour récupérer une observation de la variable aléatoire f_σ(x) ∼ N(f(x),σ^2). On souhaite également que la méthode travaille le plus possible avec de grandes valeurs de σ. L'idée derrière la méthode est d'exploiter les mécaniques de l'algorithme d'optimisation déterministe MADS, en le modifiant de façon à le rendre apte à raisonner sous incertitude. Ce projet est soutenu par un besoin sur des applications réelles, puisque dans certains problèmes d'ingénierie il est impossible d'évaluer exactement les valeurs de l'objectif qu'on souhaite optimiser; à la place on ne peut que l'approximer à une précision arbitraire, mais plus la précision est grande plus le temps de calcul croît : on cherche donc à rester le plus possible à faible précision. Ce projet est bien avancé, et soutenu par un Cahier du Gerad et un article en cours de relecture à SIOPT dans lequel nous montrons que la méthode offre une sensible économie de temps de calcul.
Lorsque l'objectif est estimé par un tirage Monte-Carlo, notre moyen actuel de faire concorder le cas réel à notre théorie est de supposer que toute évaluation de l'objectif est bruitée par une loi normale de type N(0, C/N) où C est une constante et N le nombre de tirages Monte-Carlo choisi. Cette constante C est choisie comme étant très grande. Or, ceci est une surestimation du bruit, car on connaît de nombreux exemples dans lesquels le bruit affectant les évaluations de f au point x est plutôt de la forme N(0, C(x)/N), avec C(x) pouvant être bien plus petit que la majoration C retenue dans la méthode. L'idée de ce projet est de chercher un moyen d'exploiter le fait qu'on puisse avoir C(x) « C, même si la fonction C(.) est inconnue. Quelques pistes seraient de prédire C(x) via des modèles, par exemple. L'extension aux cas contraints est aussi envisageable.
La résolution pratique des problèmes de contrôle optimal passe par une discrétisation en temps du problème. Ce faisant, la trajectoire issue d'un contrôle donné suit le schéma de discrétisation retenu; mais le calcul de cette trajectoire impose de définir chaque état comme une variable du modèle, contrainte par les équations données par la discrétisation. Ainsi, le modèle d'optimisation contient des variables de contrôle et des variables d'états, toutes traitées de la même façon (alors qu'en théorie, seules les variables de contrôle sont à manipuler puisque celles d'états sont fixées par le schéma). Lorsqu'on ajoute des contraintes d'états, le problème devient fortement restreint par ces contraintes, et la recherche d'un contrôle optimal est occultée par le besoin des solveurs de trouver des trajectoires réalisables. Il en résulte des performances pouvant être décevantes, même sur des cas simples. Des tests préliminaires montrent qu'utiliser MADS avec la stratégie de barrière progressive permet de construire des trajectoires intéressantes. L'idée est alors de développer une variante de MADS pour ces problèmes spécifiques, bien plus rapide que l'algorithme générique, en exploitant la riche structure à disposition. Une variante serait de conserver l'usage des gradients, mais d'intégrer aux algorithmes une idée analogue à la barrière progressive.
Le projet précédent ne répond pas à toutes les problématiques de contrôle optimal présentant des discontinuités. Face à un tel problème, il est commun d'adapter la modélisation afin de gérer un cas lisse : par exemple, si un problème consiste à maximiser la partie entière d'une fonctionnelle donnée, il est équivalent de maximiser la fonctionnelle. On fait ainsi disparaître la discontinuité du problème. Or, dans certains cas, une telle astuce de modélisation est inexacte; la discontinuité est intrinsèque au problème. Dans un tel cas, les résolutions des variantes lisses des problèmes sont non-optimales, et il est pertinent d'envisager de résoudre directement le problème complexe non lisse. L'idée est là encore d'adapter un algorithme d'optimisation sans dérivées à ce type de problème, en exploitant la structure bien plus riche qu'une boîte noire mais en conservant la résilience de la méthode aux discontinuités.
Dans ce projet de transport optimal, on considère avoir un nombre m de mesures de probabilités définies sur IR^n. On définit également une fonction de distance sur l'espace de ces mesures : la distance de Wasserstein, qui se calcule via la résolution d'un problème de transport optimal. L'objectif de projet est de calculer efficacement une mesure barycentrique, c'est à dire une mesure minimisant la somme des distances au carré avec les m mesures données. Ce problème est difficile car il s'agit d'un problème d'optimisation dans lequel chaque évaluation d'une solution consiste à résoudre un autre problème d'optimisation. Dans le cas où les mesures sont toutes discrètes, des méthodes exactes efficaces existent mais elles restent coûteuses. À contrario, des heuristiques existent mais n'ont pas de garantie de proposer une solution réalisable. Nous avons développé une nouvelle heuristique offrant une telle garantie, sans toutefois être plus lente que les autres. Nos tests montrent qu'elle a des performances au moins aussi bonnes que les autres (mais avec de meilleures garanties théoriques) et un temps de calcul pratique équivalent; pour un manque d'optimalité inférieur à 1%. Un article de conférence est soumis et sera présenté à CPAIOR2020. Une extension pour un journal est prévue. Ce projet est développé avec le prof. Stefano Gualandi, de l'université de Pavie, en parallèle de mon doctorat.