PGMODays 2020
Tuesday 01st december, 2020
Event online
Program :
- Tristan Garrec, PGMO PhD Prize lecture
- Maturin Massias, PGMO PhD Prize lecture
- Online interactive poster session
PGMO Projects Poster session 2020
Analysis of a two-stage probabilistic programming model - Room Claude Berge
We present a simple two-stage probabilistic programming problem. Structural properties of the underlying probability function are briefly discused. Finally a global solution to the problem is explicitly identified.
René Henrion (Weierstrass Institute Berlin), Wim van Ackooij (EDF R&D)
Distributed Optimization with Flexible Communications - Room Jean-Jacques Moreau
In distributed optimization for large-scale learning, a major performance limitation comes from the communications between the different entities. When computations are performed by workers on local data while a coordinator machine coordinates their updates to minimize a global loss, we present an asynchronous optimization algorithm that efficiently reduces the communications between the coordinator and workers. This reduction comes from a random sparsification of the local updates. We show that this algorithm converges linearly in the strongly convex case and also identifies optimal strongly sparse solutions. We further exploit this identification to propose an automatic dimension reduction, aptly sparsifying all exchanges between coordinator and workers.
Franck Iutzeler (Univ. Grenoble Alpes)
Optimal Control Techniques for Sampled-Data Control Systems with Medical Applications - Room Jean-Jacques Moreau
In biomechanics, recent mathematical models allow one to predict the muscular force response to functional electrical stimulations. The main concern of the present paper is to deal with the computation of optimized electrical pulses trains (for example in view of maximizing the final force response). Using the fact that functional electrical stimulations are modeled as Dirac pulses, our problem is rewritten as an optimal control problem where the control is a piecewise constant function with a finite number of discontinuities. We propose direct and indirect schemes and a finer study consisting in analyzing the mathematical properties of the control problem.
Toufik Bakir (UBFC), Piernicola Bettiol (LMBA), Bernard Bonnard (UBFC & INRIA), Loic Bourdin (xLIM) and Jérémy Rouot (ISEN)
Multivariate degradation with dynamic covariates and imperfect maintenance - Room Jean-Jacques Moreau
The project is centered on the degradation and predictive maintenance strategy of the steam generators of nuclear power plants. These heat exchangers are affected by clogging, which may induce safety and performance issues. Three different degradation indicators can be punctually measured in order to assess the clogging level, which depends on design and operation conditions that are heterogeneous over the different steam generators. The degradation phenomenon can be prevented by different types of maintenance actions (chemical cleaning processes).
The aim of the study is to be able to assess and predict the evolution of the degradation in order to develop an efficient predictive maintenance strategy. To that aim, we have developed a general framework for modelling multivariate degradation processes with dynamic covariates and imperfect maintenance.
Olivier Gaudoin (Université Grenoble Alpes)
Interactive Methods and Preference Elicitation for Solving Hard Multi-Objective Combinatorial Optimization Problems - Room Claude Berge
In this project, we consider multi-objective problems where the decision maker's preferences are represented by a non-linear aggregation function whose parameters are initially not known. More precisely, we focus on rank-dependent aggregators such as ordered weighted averages (OWA) and Choquet integrals which are non-linear scalarizing functions that assign weights to ranks rather than to objectives in the aggregation process, so as to control the importance attached to the bottom performance or to any other order statistics; for instance, an OWA operator with decreasing weights helps promoting balanced solutions while ensuring overall efficiency. In this setting, we propose new interactive heuristic methods consisting in combining regret-based preference elicitation and heuristic search so as to quickly focus the search on the most promising solutions. For OWA operators and Choquet integrals, the proposed methods run in polynomial time and are guaranteed to generate no more than a polynomial number of queries. We perform numerical tests comparing our methods to different interactive solving methods in order to show the practical efficiency of our approach in terms of number of queries, computation time and gap to optimality.
Thibaut Lust (Sorbonne University)
Optimal Resource Allocation in Micro-organisms under Changing Environment - Room Claude Berge
Photosynthetic microorganisms are known to adjust their photosynthetic capacity according to light intensity. This so-called photoacclimation process may correspond at equilibrium to the optimal behavior in order to maximize growth. But its dynamics under varying condition remains less understood. To tackle this problem, we propose here a resource allocation model, at coarse-grained, to represent microalgae growth and photoacclimation. Using the Pontryagin maximum principle and numerical simulations, we determine the optimal strategy of resource allocation in order to optimize microalgal growth rate over a time horizon. We show that, after a transient, the optimal trajectory approaches the optimal steady state, a behavior known as the turnpike property. Then, the model is fitted with experimental data, resulting in a bi-level optimization problem which is solved numerically. The fitted trajectory represents well a Dunaliella tertiolecta culture facing a light down-shift. Finally, we compute the optimal trajectory under day/night cycle and show that the synthesis of the photosynthetic apparatus starts a few hours before dawn. This anticipatory behavior has actually been observed both in the laboratory and in the field. This shows the algal predictive capacity and the interest of our method which predicts this phenomenon.
Terence Bayen (University of Avignon)
Planning energy investment under uncertainty - Room Marcel Boiteux
We consider stochastic programming models for energy optimization problems with investment decisions of the here-and-now type and generation variables of recourse. The resulting problem is coupled both along scenarios and along power plants. To achieve decomposition, we combine the Progressive Hedging algorithm to deal with scenario separability, and an inexact bundle method to hablde separability for different power plants in each scenario subproblem. By suitably combining these approaches, we obtain two primal-dual methods to compute an approximate solution to the original problem.
Felipe Atenas (Unicamp), Welington de Oliveira (MINES ParisTech, PSL – Research University, CMA – Centre de Mathematiques Appliquées), Claudia Sagastizábal (Unicamp) and Wim van Ackooij (EDF R&D)
Hyperbolic polynomials : algorithms and implementations - Room Jean-Jacques Moreau
A real univariate polynomial is hyperbolic whenever all its roots are real or, in other words, if it equals the characteristic polynomial of a real symmetric matrix.
This property can be extended to the multivariate case via the classical algebraic tool of symmetric determinantal representations. By the way, not every multivariate hyperbolic polynomial admits such a representation/certificate. Hyperbolic Programming (HP) is the natural convex optimization problem asking to minimize a linear function over the hyperbolicity cone of a multivariate hyperbolic polynomial. HP generalizes Linear (LP) and Semidefinite Programming (SDP), central problems in mathematics and its applications. The goal of this project is to contribute to the following two research directions:
(1) the development of symbolic-numerical algorithms and implementations for the general HP problem, and
(2) efficient computation of hyperbolicity certificates such as symmetric determinantal representations.
The two questions above are highly related since when a polynomial has a symmetric determinantal representation or, more generally, when its hyperbolicity cone is a section of the cone of positive semidefinite matrices, then the associated HP problem reduces to a SDP problem.
Simone Naldi (Université de Limoges)
Long-term Unit Commitment Problem with Optimal Zone Configuration: a Case Study in Martinique - Room Marcel Boiteux
Island regions are not interconnected with the mainland and the isolation of these regions has brought challenges to the electric power systems. For instance, the power grids in island regions are more fragile to the rapid variance of the electricity consumption or production than the continental grid. Meanwhile, more intermittent renewable energy, such as wind and solar, has been connected to the power grid. Some of the overseas territories of France are island territories in the Atlantic, Pacific and Indian Oceans.
In this work, we propose a long-term unit commitment (UC) model with simplified network (zone) constraints to apply in these areas.
One of the main purposes of this work is to examine whether a better zonal configuration could help to increase the performance of the long-term UC model. Also, by applying this long-term UC model, we can create a robust generation plan for these territories and would be able to test, for instance, whether a larger amount of renewable energy could be introduced in these areas and whether the performance of the system could be improving by constructing a new transmission line.
Hong Cai, Loïc Quéval, Martin Hennebel (CentraleSupélec, University Paris-Saclay)
Sequential Learning over Implicit Feedback for Robust Large-Scale Recommender Systems - Room Jean-Jacques Moreau
In this work, we propose a theoretically founded sequential strategy for training large-scale Recommender Systems (RS) over implicit feedback mainly in the form of clicks. The proposed approach consists in minimizing pairwise ranking loss over blocks of consecutive items constituted by a sequence of non-clicked items followed by a clicked one for each user. Parameter updates are discarded if for a given user the number of sequential blocks is below or above some given thresholds estimated over the distribution of the number of blocks in the training set. This is to prevent from updating the parameters for an abnormally high number of clicks over some targeted items, mainly due to bots; or very few user interactions. Both scenarios affect the decision of RS and imply a shift over the distribution of items that are shown to the users. We provide a proof of convergence of the algorithm to the minimizer of the ranking loss, in the case where the latter is convex. Furthermore, experimental results on five large-scale collections demonstrate the efficiency of the proposed algorithm concerning the state-of-the-art approaches, both regarding different ranking measures and computation time.
Aleksandra Burahnikova, Yury Maximov (Skoltech Institut) and Massih-Reza Amini (University Grenoble Alpes)
Maintenance planning for hydropower plants - Room Marcel Boiteux
Presentation of a project on optimization of the maintenance planning of hydropower production systems.
Louise Fournon (ENPC)
First and second order necessary conditions in optimal control of evolution systems - Room Jean-Jacques Moreau
We provide second order necessary optimality conditions for a class of infinite dimensional optimal control problems under functional pure state constraints together with end point constraints. Using tools of second order variational analysis, we derive necessary optimality conditions in the form of a maximum principle and a second order variational inequality. These results can be applied to optimal control models involving PDEs.
Marco Mazzola (IMJ-PRG, Sorbonne Université), Hélène Frankowska (CNRS, IMJ-PRG, Sorbonne Université) and Elsa Maria Marchini (Politecnico di Milano)
New approaches of bidding and contract problems: use of non-self Nash games and Radner equilibrium concept - Room Marcel Boiteux
This is the presentation for our PGMO-IROE project 2019-35 entitled "New approaches of bidding and contract problems: use of non-self Nash games and Radner equilibrium concept
Didier Aussel (University of Perpignan), Wim van Ackooij (EDF R&D), Juan Pablo (Federal University of Rio de Janeiro), Claudia Sagastizabal (University of Campinas, Sao Paulo) and Olivier Beaude (EDF R&D)
Regret Bounds for Kernel-Based Reinforcement Learning - Room Jean-Jacques Moreau
We consider the exploration-exploitation dilemma in finite-horizon reinforcement learning problems whose state-action space is endowed with a metric. We introduce Kernel-UCBVI, a model-based optimistic algorithm that leverages the smoothness of the MDP and a non-parametric kernel estimator of the rewards and transitions to efficiently balance exploration and exploitation. Unlike existing approaches with regret guarantees, it does not use any kind of partitioning of the state-action space. For problems with $K$ episodes and horizon $H$, we provide a regret bound of $\widetilde{O}\left( H^3 K^{\frac{2d}{2d+1}}\right)$, where $d$ is the covering dimension of the joint state-action space. We empirically validate Kernel-UCBVI in continuous MDPs with sparse rewards.
Omar Darwiche Domingues, Pierre Menard (INRIA), Matteo Pirotta (Facebook), Emilie Kaufmann (CNRS & ULille (CRIStAL), Inria Lille) and Michal Valko (DeepMind Paris)
Online learning for min-max discrete problems - Room Claude Berge
We study various discrete nonlinear combinatorial optimization problems in an online learning framework. In the first part, we address the question of whether there are negative results showing that getting a vanishing (or even vanishing approximate) regret is computational hard. We provide a general reduction showing that many (min-max) polynomial time solvable problems not only do not have a vanishing regret, but also no vanishing approximation α-regret, for some α (unless NP=BPP). Then, we focus on a particular min-max problem, the min-max version of the vertex cover problem which is solvable in polynomial time in the offline case. The previous reduction proves that there is no (2−ϵ)-regret online algorithm, unless Unique Game is in BPP; we prove a matching upper bound providing an online algorithm based on the online gradient descent method. Then, we turn our attention to online learning algorithms that are based on an offline optimization oracle that, given a set of instances of the problem, is able to compute the optimum static solution. We show that for different nonlinear discrete optimization problems, it is strongly NP-hard to solve the offline optimization oracle, even for problems that can be solved in polynomial time in the static case (e.g. min-max vertex cover, min-max perfect matching, etc.). On the positive side, we present an online algorithm with vanishing regret that is based on the follow the perturbed leader algorithm for a generalized knapsack problem.
Evripidis Bampis (LIP6 UPMC), Dimitris Christou (NTUA), Bruno Escoffier (Sorbonne Université) and Kim Thang Nguyen (IBISC, University Paris-Saclay)
The polyhedral structure of multistage stochastic linear problem with general cost distribution - Room Claude Berge
By studying the intrinsic polyhedral structure of multistage stochastic linear problems (MSLP), we show that a MSLP with an arbitrary cost distribution is equivalent to a MSLP on a finite scenario tree. More precisely, we show that the expected cost-to-go function, at a given stage, is affine on each cell of a chamber complex i.e., on the common refinement of the complexes obtained by projecting the faces of a polyhedron. This chamber complex is independent of the cost distribution. Furthermore, we examine several important special cases of random cost distributions, exponential on a polyhedral cone, or uniform on a polytope, and obtain an explicit description of the supporting hyperplanes of the cost-to-go function, in terms of certain valuations attached to the cones of a normal fan. This leads to fixed- parameter tractability results, showing that MSLP can be solved in polynomial time when the number of stages together with certain characteristic dimensions are fixed.
Mael Forcier (ENPC), Stéphane Gaubert (INRIA) and Vincent Leclere (ENPC)
Online Search with a Hint - Room Claude Berge
Outline of our project and results so far.
Spyros Angelopoulos (CNRS and Sorbonne University)
Integrated Optimal pricing and location of electric vehicle charging stations - Room Marcel Boiteux
We propose a bi-level optimization model to determine optimal pricing, sizing, and location of Electric Vehicle (EV) charging stations by taking into account the behavior of EV users. This is done by adopting a recent approach called preference-list or rank-based method which characterizes users by a set of distinct ordered sets of predefined preferences or products. In the upper-level of the bi-level model, the service provider is in charge of making decisions on the price, size, and location of the charging stations to maximize its profit. In the lower level, EV users select their first available charging stations from their preference list. We present two methods, i.e., KKT-based method and cutting plane method to solve the problem. The cutting plane method is used for solving only small problem instances in order to validate the solution obtained using the KKT-based method. The bi-level model and the optimization methods are demonstrated by performing several numerical experiments on a randomly generated set of problem instances.
Alemseged Weldeyesus (University of Edinburgh), Ikram Bouras, Luce Brotcorne (INRIA Lille) and Miguel F Anjos (University of Edinburgh)
Modelling and Solving Energy Problems with SMS++ - Room Marcel Boiteux
The optimization of energy systems is a complex task which involves the modelling of sophisticated multi-level nonlinear stochastic problems and the development of algorithms to solve them. On the one hand, modelling these problems is not a simple task as they present a convoluted nested structure that must capture phenomena at time resolutions spanning from minutes to
decades. Moreover, certain versatility is desirable to consider characteristics of different systems. On the other hand, efficiently implementing algorithms to solve them is particularly challenging, especially if modelling flexibility is required and distributed computation is used to exploit HPC systems, which is necessary to tackle real-world instances. In order to facilitate the implementation and maintenance of such models and general and adaptable algorithms for solving them, the innovative, open-source Structured Modelling System++ (SMS++) is being developed. In this talk, we will present an overview of the SMS++ system, including recent improvements concerning the handling of uncertainty and how we deal with complex long-term
optimization problems.
Antonio Frangioni and Rafael Lobato (Università di Pisa)
L'argumentation autour du véhicule électrique dans les corpus des grands débats nationaux - Room Marcel Boiteux
It is today a fact that the web is a privileged medium for governments around the world to consult citizens on political and societal topics and analyze the corresponding submitted data. Using Natural Language Processing (NLP) software to create synthetic views from this data which is abundant and heterogeneous remains a non-trivial challenge. In this project, we leverage data collected by the French government and civil groups in 2019: the Great National Debate (Grand Débat National), the True Debat (Vrai Débat) and Listen the France (Entendre la France). Our aim was to detect opinions expressed in those online debates on the specific topic of the electric vehicle, and extract arguments. To this end, we proceed with manual annotation of data, from which we trained and evaluated Machine Learning tools: a classifier for Opinion Mining (Bayes and SVM) and a Named Entity Recognizer (Rasa NLU) to detect claims and arguments.
Damien Nouvel and Johanna Cordova (INaLCO)
Complexity Results for Common Due Date Scheduling Problems with Interval Data and Minmax Regret Criterion - Room Claude Berge
We consider the problem of scheduling independent jobs with a common due date on a single machine with the objective of maximizing the number of early jobs. The processing times are uncertain and take any value from a certain job dependent interval. For measuring the quality of an algorithm for that problem with imprecise data we use the concept of minimizing the maximum regret. We present complexity results and some dominance properties.
Imed Kacem and Hans Kellerer