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.

Abstract

In online convex optimization (OCO), an agent makes sequential decisions using only prior information with the goal of minimizing an environment-determined loss function. The performance of OCO algorithms is measured by comparing the loss suffered by the decision sequence made by the algorithm and a benchmark decision sequence which is captured by a performance indicator called regret. If the benchmark used is the round-optimal solution and the regret of the OCO algorithm is sublinear, the time-averaged difference between the algorithm’s suffered loss and that of the round-optimal decisions goes to zero as the time horizon goes to infinity. This makes the algorithm’s decision sequence optimal, on average. This performance guarantee motivates the use of OCO algorithms in changing, uncertain, or adversarial environments. While many sequential decision making processes can be modelled within this context, many real-world problems also require decisions to satisfy constraints. These constraints arise in problems such as the optimal power flow in electric power systems where the grid has inherent physical and safety limits. Violating these safety constraints can be catastrophic for the grid operator, potentially damaging electrical infrastructure. For such applications, OCO algorithms possessing simultaneous sublinear regret and constraint violation – a decision’s distance from feasibility – are the design objective. In this work, multiple OCO algorithms leveraging second-order information and admitting time-varying linear equality constraints are presented. These algorithms all possess sublinear dynamic regret and constraint violation bounds. The differences between these algorithms reside in the types of constraints they consider. The two main algorithms of this Master’s thesis, the online projected Newton’s method (OPEN-M) and the online interior-point method for time-varying equality constraints (OIPM-TEC) admit a time-varying loss function and generalized inequalities, respectively. These algorithms are shown to outperform previous OCO algorithms from the literature in online network resource allocation and online optimal power flow problems. The hope for this Master’s thesis is for it to become a building-block towards the development of online optimization algorithms capable of simultaneously tackling time-varying loss functions, time-varying equality constraints and time-varying generalized inequalities; in the process, immensely expanding the real-world applicability of OCO approaches.