Online Second-order Methods for Time-Varying Equality-Constrained Optimization

En optimisation convexe en temps réel (OCT), des décisions séquentielles sont prises par un agent, qui cherche à minimiser une fonction de coût déterminée par l’environnement. L’agent ne considère que de l’information passée du problème. La performance des algorithmes d’OCT est mesurée en comparant les coûts engendrés par la séquence de décisions choisie par l’algorithme et une séquence de référence. La métrique qui définit cette comparaison se nomme le regret. Si la séquence de référence employée est la séquence de décisions optimales pour chaque ronde et que le regret de l’algorithme est sous-linéaire, la moyenne temporelle du regret tend vers zéro lorsque l’horizon temporel tend vers l’infini. Ce faisant, la séquence de décisions de l’algorithme devient optimale en moyenne. Cette garantie de performance justifie l’utilisation d’algorithmes d’OCT dans des environnements variables, incertains ou antagonistes. Si plusieurs procédés décisionnels peuvent être modélisés dans ce contexte, plusieurs applications réelles nécessitent que la séquence décisionnelle respecte des contraintes. Ces contraintes surviennent dans des problèmes tel que l’écoulement de puissance optimal dans les réseaux électriques; réseaux qui possèdent des limites physiques et de sécurité inhérentes. Violer ces contraintes de sécurité peut entraîner des conséquences désastreuses sur le réseau, dont des dommages sévères à l’infrastructure électrique. Pour de telles applications, des algorithmes d’OCT possédant à la fois un regret et une violation des contraintes (la distance minimale à l’ensemble réalisable d’une décision) sous-linéaires est l’objectif de conception. Dans ce mémoire, plusieurs algorithmes d’OCT utilisant de l’information sur la dérivée seconde qui admettent des contraintes linéaires d’égalité variant dans le temps sont présentés. Tous ces algorithmes possèdent des bornes supérieures sous-linéaires sur leur regret et leur violation des contraintes. Les deux algorithmes principaux de ce mémoire, la méthode de Newton en temps-réel projetée et la méthode des points intérieurs en temps réel pour les contraintes d’égalité variant dans le temps, admettent une fonction objectif variant dans le temps et des inégalités généralisées, respectivement. Finalement, la performance supérieure de ces algorithmes par rapport à des algorithmes existants lorsqu’appliqués à des problèmes d’optimisation en temps réel pour l’allocation de ressources sur réseau et pour l’écoulement de puissance optimal, est illustrée en simulation. Le but visé par ce mémoire est de faire un pas vers le développement d’algorithmes d’OCT pouvant simultanément traiter des fonctions objectif, des contraintes d’égalité, et des contraintes généralisées variant toutes dans le temps. Ce faisant, une telle approche permettrait d’élargir énormément le champ d’application des algorithmes d’OCT.