Global optimization of nonlinear semi-infinite programming problems : Applications in power systems and control.
Optimisation globale de programmes non linéaires semi-infinis : Applications aux réseaux électriques et au contrôle de systèmes dynamiques
Résumé
This thesis deals with the computation of global optima of nonlinear semi-infinite programming problems. These mathematical programming problems are particularly difficult because of the infinite number of constraints and the potential nonconvexity of the objective and the constraints: computing an optimum and certifying its global optimality is a scientific challenge. This thesis makes theoretical and practical contributions to address this challenge, with a focus on applications to the optimization of electrical grids and the control of dynamical systems.The first part of the thesis is devoted to convex semi-infinite programming. First, we exhibit a convergence rate for the cutting-plane algorithm, also called the adaptive discretization algorithm, when the objective function is strongly convex. This result holds even though one uses an oracle that approximately solves the separation problem, i.e., the problem of finding the most violated constraint, with a given relative accuracy. Second, we tackle a limitation of the cutting-plane algorithm: feasibility is only achieved asymptotically. Focusing on semi-infinite programs with a quadratically constrained quadratic programming separation problem, we propose an iterative inner-outer approximation algorithm that generates a feasible point at each iteration. This sequence of feasible points converges to an optimum of the semi-infinite program, and the convergence also occurs even when the separation problem is solved approximately. We give two sufficient conditions for this algorithm to converge in one iteration to a global optimum. We benchmark this algorithm with three competing approaches on two different applications. The third chapter of this part consists of an original approach to minimal-time nonlinear control based on convex semi-infinite programming. The applicability of our approach is illustrated by numerical experiments on three different non-polynomial dynamical systems.The second part is concerned with the global optimization of finite and semi-infinite nonconvex optimization problems related to the dispatch of electricity in a power system. First, we tackle the standard AC optimal power flow problem, a quadratically constrained quadratic programming problem with a finite number of constraints. We propose a global optimization algorithm based on a strengthened semidefinite programming relaxation and piecewise linear approximations. This results in an iterative algorithm where the master problems are mixed-integer linear programs. Extensive numerical experiments on a reference benchmark of instances show that this algorithm achieves state-of-the-art performance. Second, we address the numerical issues raised by the semidefinite programming relaxation, the building block of our global optimization algorithm, for instances at a larger scale. We use an unconstrained dual formulation to obtain certified lower bounds. To improve the dual solution returned by an interior-point method, we apply a structured bundle method as a post-processing step. Our numerical experiments on large-scale instances show that this post-processing considerably improves the tightness of the certified dual bounds.Finally, in the last chapter, we integrate some uncertainties regarding loads and fluctuating generation sources in the AC power flow model: we address the adjustable robust AC optimal power flow problem. We reformulate this adjustable robust optimization problem as an equivalent semi-infinite program. We solve this reformulation with an adaptive discretization algorithm based on a deterministic sampling and a homotopy method. Local and global convergence guarantees are given, depending on whether the master problems are solved locally or globally at each iteration. For any positive feasibility tolerance, finite termination is guaranteed. We provide extensive numerical experiments on small- to large-scale instances.
Cette thèse traite de la résolution exacte de problèmes de programmation non linéaire semi-infinie. Ces problèmes sont particulièrement difficiles en raison du nombre infini de contraintes et de la potentielle non convexité de la fonction objectif et des contraintes : calculer un optimum et certifier son optimalité globale constituent un défi scientifique. Cette thèse apporte des contributions théoriques et pratiques pour relever ce défi, et met l'accent sur les applications de la programmation semi-infinie à l'optimisation des réseaux électriques et au contrôle des systèmes dynamiques.La première partie est consacrée à la programmation semi-infinie convexe. Nous démontrons tout d'abord un taux de convergence pour l'algorithme des plans coupants lorsque la fonction objectif est fortement convexe. Ce résultat est valable même si l'oracle utilisé ne résout le problème de séparation, c'est-à-dire le problème de la recherche de la contrainte la plus enfreinte, que de façon approchée avec une précision relative donnée. Dans un deuxième temps, nous cherchons à résoudre un inconvénient majeur de l'algorithme des plans coupants : les points générés par l'algorithme ne sont réalisables qu'asymptotiquement. En nous restreignant aux programmes semi-infinis avec un problème de séparation quadratique sous contraintes quadratiques, nous proposons un algorithme itératif d'approximation interne-externe qui génère une séquence de points réalisables convergeant vers un optimum du problème semi-infini. Nous donnons des conditions suffisantes pour que l'algorithme converge en une seule itération. Nous comparons cet algorithme à trois approches concurrentes, sur des exemples provenant de deux applications différentes. Dans un chapitre dédié, nous appliquons l'optimisation convexe semi-infinie à la résolution de problèmes de contrôle temps-optimal non linéaires.La deuxième partie se concentre sur la résolution exacte de problèmes d'optimisation non convexe finis et semi-infinis liés à la répartition des flux de puissance dans un réseau électrique. Premièrement, nous abordons le problème d'optimisation des flux de puissance en courant alternatif (problème ACOPF, pour AC Optimal Power Flow), un problème avec un nombre fini de contraintes quadratiques non convexes. Nous proposons un algorithme d'optimisation globale fondé sur la relaxation semi-définie, renforcée par de nouvelles coupes et par des approximations linéaires par morceaux des contraintes non convexes. Il en résulte un algorithme itératif dont le problème maître résolu à chaque itération est un programme linéaire en variables mixtes. L'algorithme obtient des résultats à l'état de l'art sur une librairie d'instances de référence du problème ACOPF. Deuxièmement, nous traitons les difficultés numériques rencontrées par les algorithmes de points intérieurs résolvant la relaxation semi-définie pour des instances de grande taille. Nous proposons une formulation duale sans contrainte pour obtenir des bornes inférieures certifiées. Pour améliorer la solution duale calculée par l'algorithme de points intérieurs, nous exécutons une méthode de faisceau structurée en post-traitement. Nos expériences numériques montrent que ce post-traitement améliore sensiblement la précision des bornes duales obtenues pour des problèmes de grande taille.Dans le dernier chapitre, nous intégrons au problème ACOPF des incertitudes liées aux consommations et aux productions intermittentes. Le problème d'optimisation robuste avec recours qui en découle est reformulé en un programme semi-infini. Nous résolvons cette reformulation avec un algorithme de discrétisation adaptatif fondé sur un échantillonnage des scénarios et une méthode d'homotopie. Des garanties de convergence locales et globales sont données, selon que les problèmes maîtres sont résolus localement ou globalement à chaque itération. Nous présentons des expériences numériques sur des instances de grande taille.
Origine : Version validée par le jury (STAR)