Search

This thesis addresses large-scale stochastic optimization programs arising from investment problems in power systems. This work has been motivated by the numerical complexity of stochastic investment problems that are solved in prospective studies conducted by RTE (Réseau de Transport d'Electricité), the French transmission system operator. Considering a network, these problems consist of investing on production capacities on the nodes or transmission capacities on the arcs in order to satisfy demands during a discrete time horizon. We model stochastic demands, weather forecasts or operational costs by a finite number of random scenarios. We focus on two particular numerically challenging optimization problems.Firstly, we present an enhanced Benders decomposition algorithm to solve large-scale two-stage linear stochastic programs formulated with a large discrete set of scenarios. Such problems arise in prospective studies performed at RTE but models are currently limited in the number of scenarios to maintain reasonable computing times. The proposed algorithm relies on a partition of the subproblems into separated batches and a modified stopping criterion. This stopping criterion allows to solve only a few subproblems at most iterations. We also present a generic framework to stabilize the proposed algorithm, and show its efficiency on an extensive numerical study. We show, on the tested instances, that our algorithm can be up to 25 times faster than Benders decomposition with level bundle stabilization or 5 times faster than Benders decomposition with in-out stabilization and static cut aggregation.Secondly, we study a stochastic expansion planning problem taking into account a network reliability constraint. This constraint aims at limiting the expected number of nodes and time steps at which the demand is not fully satisfied in an optimal solution. We show that adding such a constraint, involving variables from different scenarios, leads to a bilevel formulation of the problem. We also show that despite the objective functions are the same in both levels, the problem is not equivalent to its high-point relaxation. As the resulting problem is a very large-scale mixed-integer bilevel program, we do not expect classical bilevel algorithms to solve real-life instances. We introduce a heuristic method based on Benders decomposition and on a binary search on the total investment costs to find feasible solutions. We show that the proposed heuristic is able to find feasible solutions on randomly generated instances with up to several million variables and constraints.; Cette thèse s'intéresse à la modélisation et la résolution de problèmes d'optimisation stochastique de grande taille provenant de problèmes d'investissements dans les réseaux électriques. Ces travaux ont été motivés par la complexité numérique des problèmes d'investissement stochastiques résolus dans le cadre d'études prospectives menées à RTE (Réseau de Transport d'électricité), le gestionnaire de réseau électrique français. A partir d'un réseau, ces problèmes modélisent des investissement sur des capacités de production sur les noeuds, ou des capacités de transport sur les arcs pour satisfaire des demandes en électricité sur un horizon de temps donné avec des pas de temps discrets. Les demandes en électricité, les prévision météorologiques ou les coûts opérationnels sont aléatoires et modélisés par un ensemble fini de scénarios d'aléas. On s'intéresse à deux problèmes particuliers.Premièrement, nous présentons un algorithme amélioré basé sur une décomposition de Benders pour résoudre de grand problèmes linéaires stochastiques à deux étapes modélisés avec un ensemble fini de scénarios. De tels modèles sont utilisés dans les études prospectives menées à RTE mais les résolutions actuelles sont limitées dans le nombre de scénarios apparaissant dans les modèles pour conserver des temps de calculs raisonnables. L'algorithme proposé est basé sur une partition des sous-problèmes et sur une modification du critère d'arrêt. Le critère d'arrêt proposé permet de ne résoudre qu'un petit sous-ensemble de sous-problèmes à la plupart des itérations de l'algorithme. Nous présentons aussi une méthode générique pour stabiliser notre algorithme, et montrons son efficacité au travers d'une étude numérique étendue. Les résultats montrent que l'algorithme proposé peut être jusqu'à 25 fois plus rapide qu'un algorithme de faisceaux (level bundle) et jusqu'à 5 fois plus rapide qu'un algorithme basé sur la décomposition de Benders avec une stabilisation in-out et une méthode statique d'agrégation de coupes.Deuxièmement, nous étudions un modèle d'expansion de réseau stochastique prenant en compte une contrainte de fiabilité. Cette contrainte à pour but de limiter, en moyenne sur les scénarios d'aléas, le nombre de noeuds et de pas de temps auxquels la demande n'est pas entièrement satisfaite dans une solution du problème. Nous montrons que le fait d'ajouter une telle contrainte, qui prend en compte des variables provenant de différents scénarios dans sa formulation, implique de modéliser le problème comme un problème bi-niveaux. Les fonctions objectifs sont les mêmes dans les deux niveaux du problème. Malgré cette structure particulière, nous montrons que le problème n'est pas équivalent à sa high-point relaxation. Le problème obtenu est un très grand problème bi-niveaux en variables mixtes, et les algorithmes classiques pour résoudre ces problèmes ne sont pas en mesure de résoudre des problèmes de cette taille. Nous présentons une méthode heuristique basée sur une décomposition de Benders et une dichotomie sur les coûts d'investissements pour trouver des solutions réalisables de ce problème. Cette méthode est capable de trouver des solutions réalisables sur des problèmes générés aléatoirement avec plusieurs millions de variables et contraintes.

Due to non-invasiveness and excellent time resolution, magneto- and electroencephalography (M/EEG) have emerged as tools of choice to monitor brain activity. Reconstructing brain signals from M/EEG measurements can be cast as a high dimensional ill-posed inverse problem. Typical estimators of brain signals involve challenging optimization problems, composed of the sum of a data-fidelity term, and a sparsity promoting term. Because of their notoriously hard to tune regularization hyperparameters, sparsity-based estimators are currently not massively used by practitioners. The goal of this thesis is to provide a simple, fast, and automatic way to calibrate sparse linear models. We first study some properties of coordinate descent: model identification, local linear convergence, and acceleration. Relying on Anderson extrapolation schemes, we propose an effective way to speed up coordinate descent in theory and practice. We then explore a statistical approach to set the regularization parameter of Lasso-type problems. A closed-form formula can be derived for the optimal regularization parameter of L1 penalized linear regressions. Unfortunately, it relies on the true noise level, unknown in practice. To remove this dependency, one can resort to estimators for which the regularization parameter does not depend on the noise level. However, they require to solve challenging "nonsmooth + nonsmooth" optimization problems. We show that partial smoothing preserves their statistical properties and we propose an application to M/EEG source localization problems. Finally we investigate hyperparameter optimization, encompassing held-out or cross-validation hyperparameter selection. It requires tackling bilevel optimization with nonsmooth inner problems. Such problems are canonically solved using zeros order techniques, such as grid-search or random-search. We present an efficient technique to solve these challenging bilevel optimization problems using first-order methods., Grâce à leur caractère non invasif et leur excellente résolution temporelle, la magnéto- et l'électroencéphalographie (M/EEG) sont devenues des outils incontournables pour observer l'activité cérébrale. La reconstruction des signaux cérébraux à partir des enregistrements M/EEG peut être vue comme un problème inverse de grande dimension mal posé. Les estimateurs typiques des signaux cérébraux se basent sur des problèmes d'optimisation difficiles à résoudre, composés de la somme d'un terme d'attache aux données et d'un terme favorisant la parcimonie. À cause du paramètre de régularisation notoirement difficile à calibrer, les estimateurs basés sur la parcimonie ne sont actuellement pas massivement utilisés par les praticiens. L'objectif de cette thèse est de fournir un moyen simple, rapide et automatisé de calibrer des modèles linéaires parcimonieux. Nous étudions d'abord quelques propriétés de la descente par coordonnées : identification du modèle, convergence linéaire locale, et accélération. En nous appuyant sur les schémas d'extrapolation d'Anderson, nous proposons un moyen efficace d'accélérer la descente par coordonnées en théorie et en pratique. Nous explorons ensuite une approche statistique pour calibrer le paramètre de régularisation des problèmes de type Lasso. Il est possible de construire des estimateurs pour lesquels le paramètre de régularisation optimal ne dépend pas du niveau de bruit. Cependant, ces estimateurs nécessitent de résoudre des problèmes d'optimisation "non lisses + non lisses". Nous montrons que le lissage partiel préserve leurs propriétés statistiques et nous proposons une application aux problèmes de localisation de sources M/EEG. Enfin, nous étudions l'optimisation d'hyperparamètres, qui comprend notamment la validation croisée. Cela nécessite de résoudre des problèmes d'optimisation à deux niveaux avec des problèmes internes non lisses. De tels problèmes sont résolus de manière usuelle via des techniques d'ordre zéro, telles que la recherche sur grille ou la recherche aléatoire. Nous présentons une technique efficace pour résoudre ces problèmes d'optimisation à deux niveaux en utilisant des méthodes du premier ordre.