ABSTRACT. While the volume of data exchanged on the Internet has considerably increased in recent years, most of it is due to a very small number of content providers (CPs): as of 2015 in North America, Netflix and YouTube were accounting for more than 50% of all traffic. To ensure the right service to their customers, those CPs report the quality provided by the various ISPs. It is then natural to assume that such information will be taken into account by customers when selecting an ISP to subscribe to. This may create an incentive for ISPs to differentiate services and favor big CPs in order to receive the best grades and attract more customers, at the expense of small CPs. Such a differentiated treatment among flows is directly linked to the network neutrality debate. We propose in this paper a model to analyze the decisions of ISPs with regard to service differentiation of CP flows (bandwidth allocation among CPs), in a context of two competing ISPs. Among the key components in such a game among ISPs, will be the user preferences in terms of their interests for the different CPs; we assume a distribution over the subscriber population, leading to a nonatomic congestion game among users over the ISP choice. Based on that distribution and on its competitor’s choice, each ISP has to determine the amount of capacity to devote to each CP. We investigate the strategies of competing ISPs in terms of capacity assignment to user- attractive CPs; should there be a differentiated treatment? What is the impact with respect to a “neutral" sharing, where the capacity used for a CP would be proportional to its total traffic?

ABSTRACT. Mean field games are a good approximation of finite games with a large number of interacting players. The fundamental idea of mean field approximation is that the behavior of a system of N interacting players simplifies as N goes to infinity. In this talk, I will introduce the key concepts behind mean field approximation, by giving some examples of where it can be applied. I will review some of the classical models and their convergence properties. I will try to answer a very natural question: how large should the system be for mean-field to apply? This leads to a follow-up question: can we refine this approximation to make it applicable for 10 players ?

ABSTRACT. Traffic routing in congested networks is a notoriously difficult problem. Even in its convex incarnations, it suffers from the curse of dimensionality (for instance, in the number of origin-destination pairs in the network or the number of paths per O/D pair), limited information at the decision-maker end (be it the network controller or an individual user), delays and asynchronicities, etc. Nevertheless, empirical studies in real-world networks have shown that the gap between optimality and equilibrium (typically referred to as the price of anarchy) is surprisingly small, under both light and heavy traffic. This work focuses on whether these observations can be justified theoretically and what kind of algorithmic schemes can be used to overcome the challenges cited above.

ABSTRACT. In a rst part of the work, we focus on the time series analysis of the 246 arteres along the period of interest (2sd Jan 2012, to 31st Dec 2014) which corresponds to 1095 daily measures. However the number of failure is very limited and the times series are almost equal to zero for a long period. age, length). We caracterise some failures by the arteres components (type of cables, Results from machine learning methods (logistic regression, constrained logistic regression, SVR, random forest and neural network) will be presented.

ABSTRACT. Motivated by a wide variety of applications from fraud detection to aviation safety management, unsupervised anomaly detection is the subject of much attention in the machine-learning literature. We developed novel statistical techniques for tackling anomaly detection borrowing concepts and tools from machine-learning and multivariate extreme value analysis both at the same time. Usually, anomaly detection algorithms declared extremes as anomaly, whereas all extremes values are not anomalies. We study the dependance structure of rare events in the context of high dimensional and propose an algorithm to detect this structure under a sparse assumption. This approach can reduce drastically the false alarm rate : anomalies then correspond to the observation of simultaneous very large/extreme values for groups of variables that have not been identified yet. A data-driven methodology for learning the sparse representation of extreme behaviours has been developed in \cite{goix}. An advantage of this method lies in its straightforward interpretability. In addition, the representation of the dependance structure in the extremes thus designed induces a specific notion of (dis-)similarity among anomalies, that paves the way for elaborating visualization tools for operators in the spirit of those proposed for large graphs. We also describe how this approach applies to functional data collected for aircraft safety purposes after an appropriate preliminary filtering stage.

ABSTRACT. This aim of this project is to propose a numerical method to compute an approximation of the optimal maintenance cost for a multi-component equipment subject to random degradation and failures.

ABSTRACT. In this talk, we present a characterization of the weak and strong Pareto fronts for optimal control problems with two objective functions of different nature that need to be minimized simultaneously. One objective is in the classical Bolza form and the other one is defined as a maximum function. Our approach is based on the Hamilton-Jacobi-Bellman framework. First we define an auxiliary optimal control problem without state constraints and show that the weak Pareto front is a subset of the zero level set of the corresponding value function. Then with a geometrical approach we establish a characterization of the Pareto front. Some numerical examples will be considered to show the relevance of our approach.

ABSTRACT. In this talk we introduce a method ensuring robustness properties of bang-bang strategies, for general
nonlinear control systems. Our main idea is to add bang arcs in the form of needle-like variations of
the control. With such bang-bang controls having additional degrees of freedom, steering the control
system to some given target amounts to solving an overdetermined nonlinear shooting problem, what
we do by developing a least-square approach. In turn, we design a criterion to measure the quality of
robustness of the bang-bang strategy, based on the singular values of the end-point mapping, and which
we optimize. Our approach thus shows that redundancy implies robustness, and we show how to achieve
some compromises in practice, by applying it to the attitude control of a 3d rigid body.

ABSTRACT. In many aerospace applications, for both the design of systems and the preparation of a mission, it is required to optimize performance of trajectories. For example, for cost reasons, it is required that a rocket trajectory minimize propellant consumption. Thus, trajectory generation can be reduced to an optimization problem. Direct methods of optimization are generally used to solve the problem offline, ensuring global convergence to optimal solutions. However, when managing dynamic problems such as, for example, an intercept missile dealing with maneuvering targets, precomputed trajectories can quickly lose their optimality, or worse, lead to a failure of the mission. In this uncertain situations, real-time computation (usually in a 1-10 Hz frequency range) of optimal trajectories are needed to ensure achieving the mission. In this work, we address real-time optimal guidance of launch vehicles with the objective of designing a fast autonomous algorithm for optimal control computation. The approach is based on indirect methods generally known to be more precise and faster than direct methods when they are well initialized. We first provide an accurate geometric analysis in the presence of mixed control-state constraints to recover a well-posed framework and correctly apply indirect methods. A practical numerical algorithm is proposed by efficiently combining indirect methods with homotopy procedures, increasing robustness to initialization problems and computational speed. We also consider state and control delays in the dynamic model by introducing a well-posed homotopy framework to recover solutions. All those contributions made possible the development of an efficient C/C++ software, first dedicated to Missile applications, now extended to other aerospace applications such as Reusable Launch Vehicles and Aerial Robotics.

Joint work with Riccardo Bonalli and Emmanuel Trélat

ABSTRACT. We model the day-ahead/intraday trading problem as a two-scale multistage stochastic optimisation problem. We consider a price taker battery owner that can trade in both markets. At time t=0, by trading on the day-ahead market, which is deterministic, he defines a first planning q for the next day. Then, at the beginning of step t he discovers costs on the intraday market and trades a quantity u_t, the quantity going through the system is q_t + u_t.

The problem can be seen as a multistage problem with 25 steps, with a first stage variable of dimension 24. Consequently, solving the extensive formulation is intractable, and a classical dynamic programming (or SDDP like) approach will likely fail. Therefore we propose a decomposition approach by splitting day-ahead and intraday problems. More precisely, the Master problem consists in minimising day-ahead costs plus the expected cost of the intraday market given day-ahead planning q, denoted V(q), that is solving

\min{q} c^T q + V(q) s.t. Aq < b

where function V represents the optimum cost on the intraday market when q has been decided on the day-ahead market. It is polyhedral but hard to compute, as the solution of a parametrised multistage stochastic program, thus it is approximated by cuts.

More precisely we propose a Bundle trust region method to solve the coupled Day-Ahead/Intraday problem. The oracle called to compute new cuts consists in approximately solving the Indraday Problem via an SDDP method. Since the value of the intraday problem and its subgradient are inexact, applying a classic Kelley cut algorithm is not possible and is the prime motivation behind the use of bundles.

In this work we give elements relative to the convergence and accuracy of such an algorithm. We then proceed to compare its performances to frontal extensive and SDDP resolution of the problem as well as other types of oracle.

ABSTRACT. This work describes asynchronous level bundle methods for minimizing complicated nonsmooth convex functions with additive structure. Problems of this type arise, for instance, when one is interested in computing bounds on the solution values of difficult mixed-integer optimization problems such as stochastic integer programs. Existing methods for solving these distributed problems in a general form are synchronous, in the sense that they wait for the answers of all the oracles (black-boxes) before performing a new iteration. In this work, we propose efficient algorithms handling asynchronous oracles working in parallel. We illustrate their practical performance on a Lagrangian decomposition problem.

ABSTRACT. The Stochastic Dual Dynamic Programming (SDDP) algorithm has become one of the main tools to address convex multistage stochastic optimal control problems. Recently a large amount of work has been devoted to improve the convergence speed of the algorithm through cut selection and regularization, or to extend the field of applications to non-linear, integer or risk-averse problems. However one of the main downside of the algorithm remains the difficulty to give an upper bound of the optimal value, usually estimated through Monte Carlo methods and therefore difficult to use in the stopping criterion of the algorithm.

In this paper we show that the Fenchel transform of the cost-to-go function also follow a recursive equation and can thus be approximated by SDDP. Thus we obtain a dual SDDP algorithm that yields a converging exact upper bound for the optimal value of the optimization problem.

Incidently we show how to compute an alternative control policy based on an inner approximation of Bellman value functions instead of the outer approximation given by the standard SDDP algorithm.

We illustrate the approach on an energy production problem involving zones of production and transportation links between the zones. The numerical experiments we carry out on this example show the effectiveness of the method.

ABSTRACT. Influence Diagrams (ID) are a flexible tool to represent discrete stochastic optimization problems, including Markov Decision Process (MDP) and Partially Observable MDP as standard examples. More precisely, given random variables considered as vertices of an acyclic digraph, a probabilistic graphical model defines a joint distribution via the conditional distributions of vertices given their parents. In ID, the random variables are represented by a probabilistic graphical model whose vertices are partitioned into three types : chance, decision and utility vertices. The user chooses the distribution of the decision vertices conditionally to their parents in order to maximize the expected utility. Leveraging the notion of strong junction tree, we present a mixed integer linear formulation for solving an ID, as well as valid inequalities, which lead to a computationally efficient algorithm. We also show that the linear relaxation yields an optimal integer solution for instances that can be solved by the ``single policy update'', the default algorithm for addressing IDs.

ABSTRACT. A dynamic chance constraint is an inequality of the type \begin{equation}\label{dynprob} \mathbb{P}(g_i(x_1,x_2(\xi_1),x_3(\xi_1,\xi_2)\ldots ,x_T(\xi_1,\ldots ,\xi_{T-1}),\xi_1,\ldots ,\xi_T)\leq 0\quad (i=1,\ldots ,m))\geq p, \end{equation} where $(\xi_1,\ldots ,\xi_{T-1})$ is a finite stochastic process, $(x_1,\ldots ,x_T)$ is an adapted process of decision policies depending on previously observed outcomes of the random process, $\mathbb{P}$ is a probability measure and $p\in [0,1]$ is a probability level. A typical example arises in water reservoir control subject to level constraints where (\ref{dynprob}) figures as a constraint in some optimization problem. The talk presents some structural results for the associated probability function assigning to each set of decision policies the probability occuring above. For instance, strong and weak semicontinuity results are provided for the general case depending on whether policies are supposed in $L^p$ or $W^{1,p}$ spaces. For a simple two-stage model corresponding to the one of reservoir control, verifiable conditions for Lipschitz continuity and differentiability of this probability function are derived and endowed with explicit derivative formulae. Numerical results are illustrated for the solution of such two-stage problem.

ABSTRACT. We present a non-asymptotic theoretical analysis of superquantile linear prediction, based on a method originally proposed by Rockafellar, Uryasev and Zabarankin. Super-quantile regression allows one to learn linear predictors with strong guarantees on the test error when the testing distribution may differ from the training distribution. Indeed classical statistical machine learning methods trained using empirical risk minimization work under the assumption that the testing distribution and the training distributions are identical. Should this assumption fail to be satisfied at test time, classical linear predictors may behave unpredictably and perform arbitrarily badly.

The notion of $\alpha$-superquantile allows one to model such catastrophic risks in a precise manner. Instead of minimizing the average of the loss, we then minimize the superquantile of the loss. The associated minimization problem enjoys an intuitive interpretation owing to its Fenchel dual representation. We establish non-asymptotic bounds for kernel-based methods trained by minimizing the new objective, demonstrating the stronger robustness of the approach compared to classical counterparts when the testing distribution departs from the training distribution. We present numerical illustrations using a first-order optimization algorithm in different settings showing the interest of the approach.

ABSTRACT. We consider the Max-Cut problem on an undirected graph $G=(V,E)$ with $|V|=n$ nodes and $|E|=m$ edges. We investigate a linear size MIP formulation, referred to as (MIP-MaxCut), which can easily be derived via a standard linearization technique. However, the efficiency of Branch-and-Bound procedure applied to this formulation does not seem to have been investigated so far in the literature. Branch-and-bound based approaches for Max-Cut usually use the semi-metric polytope which has either an exponential size formulation consisting of the cycle inequalities or a compact size formulation consisting of $O(mn)$ triangle inequalities \cite{BM86}, \cite{network}. However, optimizing over the semi-metric polytope can be computationally demanding due to the slow convergence of cutting-plane algorithms and the high degeneracy of formulations based on the triangle inequalities. In this paper, we exhibit new structural properties of (MIP-MaxCut) that link the binary variables with the cycle inequalities. In particular, we show that fixing a binary variable at 0 or 1 in (MIP-MaxCut) can result in imposing the integrity of several original variables and the satisfaction of a possibly exponential number of cycle inequalities in the semi-metric formulation. Numerical results show that for sparse instances of Max-Cut, our approach exploiting this capability outperforms the branch-and-cut algorithms based on separating cycle inequalities when implemented on the same framework; and even without any extra sophistication, the approach already appears to be competitive with state of-the-art cycle inequalities based branch-and-cut algorithms.

ABSTRACT. The considerations of our work are devoted to the problem of networks link dimensioning. The main application area we investigate are networks that apply Free Space Optics (FSO) - a wellestablished broadband wireless optical transmission technology where the communication links are provided by means of a laser beam sent from the transmitter to the receiver placed in the line of sight. A major disadvantage of FSO links (with respect to fber links) is their sensitivity to weather conditions such as fog, rain and snow, causing substation loss of the transmission power over the optical channel due mostly to absorption and scattering. Thus, although FSO technology allows fast and low-cost deployment of broadband networks, its operation will be affected by this sensitivity, manifested by substantial losses in links' transmission capacity with respect to the nominal capacity. Therefore, a proper approach to FSO network dimensioning should take such losses into account so that the l! evel of carried traffic is satisfactory under all observed weather conditions. To construct our approach we start with building a reference failure set using a set of meteorological records for a given time period against which the network must be protected. Next, the mathematical formulation of the robust network dimensioning problem uses the above failure set, which makes the problem untraceable because of the size of the failure set. All this calls for a more sophisticated approach which uses a cut-generation algorithm. Still the problem remains diffcult and we need to reduce the size of the failure set. We propose to approximate the reference failure set with a so-called K-set, which roughly speaking covers all possible failures involving at most K links. This K-set stands for uncertainty polytope of failures in our case. We have shown that the cut-generation algorithm works quite well for all K-set failure instances. Finally, a substantial part of our work is devoted to present a numerical study of FSO network instances that illustrate the promising effectiveness of the proposed approach.

ABSTRACT. Software Defined Networking (SDN) technologies are radically transforming network architectures by offloading the control plane (e.g., routing, resource allocation) to powerful remote platforms that gather and keep a local or global view of the network status in real-time and push consistent configuration updates to the network equipment. The computation power of SDN controllers fosters the development of a new generation of control plane architecture that uses compute intensive operations. Initial design of SDN architectures [2] had envisioned the use of one central controller. However, for obvious scalability and resiliency reasons, the industry has quickly realized that the SDN control plane needs to be partially distributed in large network scenarios [3]. Hence, although logically centralized, in practice the control plane may consist of multiple controllers each in charge of a SDN domain of the network and operating together, in a flat [4] or hierarchical [5] architecture. In this talk, we propose a distributed algorithm based on the Alternating Direction Method of Multipliers [6] (ADMM) that tackles the multi-path fair resource allocation problem in a distributed SDN control architecture. Our ADMM-based algorithm continuously generates a sequence of resource allocation solutions converging to the fair allocation while always remaining feasible, a property that standard primal-dual decomposition methods often lack. Moreover, it controls the sparsity of the solution to ensure, e.g., small number of path re-sizing, or small number of allocated paths for a same flow. Thanks to the distribution of all computer intensive operations, we demonstrate that we can handle large instances at scale.

ABSTRACT. Nowadays non-cooperative games have many applications. A particular case is the so-called multi-leader disjoint-follower (MLDF) problem where several leaders act according to a Nash equilibrium and having each a number of exclusive followers. In the presentation we consider the mathematical program with complementarity constraints (MPCC) formulation of the bilevel problem corresponding to each leader, see [1]. We focus to the case in which the sets of feasible solutions of the follower do not depend on the variable of the corresponding leader. We show that, generically, good properties such as constraint qualification and non degeneracy of the solutions, are satisfied at each bi-level problem. In particular, given a problem, we obtain that except for a zero-Lebesgue measure set, with at most quadratic perturbations of the involved functions, the MPCC-LICQ for the MPCC as well as the LICQ at solutions of the follower’s problems are satisfied. Using the ideas in [2] it can be shown that these properties will remain stable under small perturbations of the involved functions. We discuss the consequences of this result for the particular MLDF model that appears when agents have to design the contracts they will propose to their clients, knowing that the clients will choose the best option.

References: [1] Aussel, D. and Bouza, G. and Dempe, S. and Lepaul, S.: Multi-leader disjoint-follower game: formulation as a bilevel optimization problem, Preprint No. 2018 - 10, Fakultät für Mathematik und Informatik, TU Bergakademie Freiberg, 2018. [2] Guddat, J., Guerra, F. and Jongen, H. Th.: Parametric optimization: singularities, pathfollowing and jumps. Teubner and John Wiley, Chichester, 1990.

ABSTRACT. With the emergence of the smart grid paradigm, combined with the breakthrough of distributed generation, demand side management has become more important than ever. Since distributed generation is by nature unpredictable, scattered, and irregular, the electricity distribution system undergoes many constraints. It it thus essential to be able to control the demand (and the rest of the production) as much as possible. This work focuses on one specific tool to achieve an efficient management of the demand: time-of-use pricing. Offering differing prices to customers who are going to optimally adapt their consumption is indeed a good way to induce load shifts that are beneficial: in this case, they aim to improve the revenue of an electricity furnisher.

The presented problem is based on Afsar et al.*, but incorporates the management of storage capacities and distributed generation, e.g. solar panels. Furthermore, scenario trees are considered to handle the unpredictability of the distributed generation. However, the inherent complexity of bilevel problems, combined with the potentially huge size of scenario tree-based models, makes the problem hard to solve. This talk addresses the problem with a rolling horizon method, whose efficiency is validated with numerical tests using real data.

*Afşar, S., Brotcorne, L., Marcotte, P., & Savard, G. (2016). Achieving an optimal trade-off between revenue and energy peak within a smart grid environment. Renewable Energy, 91, 293-301.

ABSTRACT. Bilevel programming deals with nested optimization problems involving two players. A leader announces a decision to a follower, who responds by selecting a solution of an optimization problem (low level problem) whose data depend on the decision of the leader. The optimal decision of the leader is the solution of another optimization problem (high level problem) whose data depend on the follower's response.

We study a special class of bilevel problems, in which the value of the low level problem is equal to the evaluation of a certain tropical polynomial, depending on the leader's decision. Tropical geometry allows one to represent the response of the follower to the leader's decision by a polyhedral complex. This is motivated by an application of tropical geometry to an auction problem, introduced by Baldwin and Klemperer, and further developed by Yu and Tran.

Thanks to the tropical approach, we reduce the bilevel problem into a series of optimization subproblems, each one being associated to a cell of the previous polyhedral complex. These cells being a projection of faces of a certain polyhedral, we use a classical face enumeration algorithm developed by Fukuda et al. to define each subproblem. This leads to parametrized complexity results for the bilevel problem, based on the combinatorics of polyhedral complexes.

In particular, we identify a class of bilevel programs that can be solved in polynomial time. This result is also based on discrete convexity results provided by Murota.

We finally present an application to a large scale bilevel problem arising in the optimal pricing of data traffic in a telecom network.

ABSTRACT. We propose and analyze a self-adaptive version of the $(1,\lambda)$ evolutionary algorithm in which the current mutation rate is part of the individual and thus also subject to mutation. A rigorous runtime analysis on the \onemax benchmark function reveals that a simple local mutation scheme for the rate leads to an expected optimization time (number of fitness evaluations) of $O(n\lambda/\log\lambda+n\log n)$. This time is asymptotically smaller than the optimization time of the classic $(1,\lambda)$ EA and $(1+\lambda)$ EA for all static mutation rates and best possible among all $\lambda$-parallel mutation-based unbiased black-box algorithms.

Our result shows that self-adaptation in evolutionary computation can find complex optimal parameter settings on the fly. At the same time, it proves that a relatively complicated self-adjusting scheme for the mutation rate proposed by Doerr et al.~(GECCO~2017) can be replaced by our simple endogenous scheme. Moreover, the paper contributes new tools for the analysis of the two-dimensional drift processes arising in self-adaptive EAs, including bounds on occupation probabilities in processes with non-constant drift.

ABSTRACT. One of the main aims of the PGMO project "Algorithms for Expensive Simulation-Based Optimization Problems" (AESOP, http://aesop.gforge.inria.fr/) is to exploit the Comparing Continuous Optimizers platform (COCO, https://github.com/numbbo/coco) and extend its reach towards the Bayesian/expensive/simulation-based/surrogate-model-based optimization community. In this talk, I will give a short overview of our project progress towards this goal and detail joint work with Pierre Marion, Lu Lin, Anne Auger, and Nikolaus Hansen.

In particular, I will present experimental data about the performance of the well-known Bayesian approaches EGO, Spearmint, TPE, and SMAC and how they compare to other well-performing (blackbox) solvers such as the Covariance Matrix Adaptation Evolution Strategy (CMA-ES), trust region methods like DFO-TR and NEWUOA and the classical Quasi-Newton BFGS. A brief introduction about how the COCO platform works and how COCO displays algorithm performance through a natural extension of the well-known data profiles will complete the talk. This will make the talk accessible to everybody interested in the performance of (blackbox) solvers in continuous domain---with a special focus on recommending well-performing methods for small budgets of function evaluations.

ABSTRACT. Bayesian optimization is widely used to deal with expensive black-box function optimization. It is based on surrogate models, allowing the emulation of the statistical relationship between the design variables and the response (objective function and constraints), to predict its behaviour using a Design of Experiments (DoE). The evaluation cost of the surrogate models is cheaper, so it is possible to evaluate a greater number of design candidates, then via the use of an acquisition function also called infill criterion one can determine the most promising point(s). One of the most popular Bayesian optimization methods is "Efficient Global Optimization"(EGO) developed by Jones et al. . It uses Kriging surrogate model which is based on the Gaussian Process (GP) theory.

Classical Kriging is a GP with a stationary covariance function, inducing a uniform smoothness of the prediction. While it is effective to approximate stationary functions, it causes a major issue in the prediction of non-stationary ones. Indeed, in many design optimization problems, the objective functions or constraints vary with a completely different smoothness along the input space, due to the abrupt change of a physical property for example. The main approaches used to overcome this issue are not applicable for problems with large dimensions (direct formulation of non-stationary covariance function, non-linear mapping of the input space) or for problems with sparse data (local stationary covariance functions).

In this talk, we explore the coupling of Bayesian Optimization and Deep Gaussian Processes (DGP) a class of surrogate models based on the structure of neural networks, where each layer is a GP, to deal with the non-stationary issues. The induced challenges and opportunities of this coupling are investigated. Then, numerical experimentations on single and multi-objective analytical problems are displayed to confirm the interest of DGPs for bayesian optimization.

ABSTRACT. A signed graph is considered structurally balanced if it can be partitioned into a number of clusters, such that positive (negative) links are located inside (in-between) the clusters. Due to the imbalanced nature of real-world networks, various measures have been defined to quantify the amount of imbalance, the simplest consisting in counting the numbers of misplaced links. Such measures are expressed relatively to a graph partition, so processing the graph balance amounts to identifying the partition corresponding to the lowest imbalance measure.

Our goal is to use this paradigm to study the roll-call voting activity of the Members of the European Parliament (MEPs). We want not only to detect groups of MEPs which would be cohesive in terms of votes (i.e groups of antagonistic voters), but also to identify the characteristic ways in which the MEP set is partitioned by these votes. The standard approach to study this type of system is to extract a mean vote similarity network. However, this approach suffers from several limitations. The two main ones are that 1) they rely on some temporal integration of the raw data, which causes some information loss; and/or 2) they identify groups of antagonistic voters, but not the context associated to their occurrence.

In this work, we propose a novel method taking advantage of multiplex signed graphs to solve both these issues. It consists in first partitioning separately each layer which models a single roll-call as a signed unweighted graph, before grouping these partitions by similarity. We show the interest of our approach by applying it to a European Parliament dataset and by comparing the results with those obtained through a standard approach in our previous work.

ABSTRACT. Dealing with delays in project scheduling is often a hard task, especially when the decision maker wants to avoid re-scheduling jobs. We define a project scheduling problem under uncertainty with a deadline constraint, where the objective is to favor anchored jobs, i.e., jobs with a start time that is guaranteed to remain unchanged whatever the delays in the uncertainty set. We show that this problem is equivalent to a Longest Path Network Interdiction problem in an appropriate acyclic digraph. We further analyze the complexity of the problem, depending on precedence constraints and the uncertainty set.

ABSTRACT. We study two classes of zero-sum stochastic games with compact action sets and a finite product state space. These two classes assume a communication property on the state spaces of the players. For strongly communicating on one side games, we prove the existence of the uniform value. For weakly communicating on both sides games, we prove that the asymptotic value, and therefore the uniform value, may fail to exist.

ABSTRACT. A location game is a competition between a finite number of players who select simultaneously a location in order to attract as many consumers as possible. In a random location games, we consider that sellers have small differentiation, and consumers have specific preferences for this differences. Because firms can not determine this preferences, they act as if the choice of consumers were driven by a random variable. We investigate the impact of such randomness in the Nash equilibrium of the game.

ABSTRACT. We study the links between the values of stochastic games with varying stage duration $h$, the corresponding Shapley operators $\T$ and $\T _h= h\T + (1-h ) Id$ and the solution of the evolution equation $\dot f_t = (\T - Id )f_t$. Considering general non expansive maps we establish two kinds of results, under both the discounted or the finite duration framework that apply to the class of ``exact" stochastic games. On the one hand, for a fixed horizon or discount factor, the value converges as the stage duration go to 0. On the other hand, the asymptotic behavior of the value as the horizon goes to infinity, or as the discount factor goes to 0, does not depend on the stage duration. Finally these properties imply the existence of the value of the finite duration or discounted continuous time game (associated to a continuous time Markov process), as the limit of the value of any discretization with vanishing mesh.

ABSTRACT. The abstract of the IRSDI project HYPTSER is attached

ABSTRACT. See pdf.

ABSTRACT. After the installation of 300.000 smart meters "Linky" between 2009 and 2011 in the area of Lyon and Tours, the authorities have decided to generalize these meters throughout the territory. By 2021, 35 million meters should be replaced in French households by Linky meters, allowing electricity operators to record electricity consumption. For an operator like EDF with 27 millions of residential dwellings, these new smart meters represent a great opportunity to gather customer consumption data and therefore to improve client knowledge. Indeed, so far, customer data were recorded only every six months, while with the smart meter, the data can be taken up to every second. In practice, EDF plans to access the data every half hour, which means 17472 measures per year for each of the 27 million clients. Nevertheless, this data flood may also be a drawback since they represent a mass of data to store and manage. To this end, it will be necessary to build « summaries » of these data, and one of the way to achieve that is to cluster the data. However, because of the nature of the data, which are time series for each customer, the interest in the simultaneous clustering of customers and time increases considerably. We have proposed a new co-clustering methodology [1], based on the functional latent block model (funLBM), which allows to build "summaries" of these large consumption data through co-clustering. The funLBM model extends the usual latent block model to the functional case by assuming that the curves of one block live in a low-dimensional functional subspace. Thus, funLBM is able to model and cluster large data set with high-frequency curves. A SEM-Gibbs algorithm is proposed for model inference and an ICL criterion is derived to address the problem of choosing the number of row and column groups. Numerical experiments on simulated and original Linky data show the usefulness of the proposed methodology. An R package for func- tional data co-clustering has been developed. This package is called funLBM and is available on CRAN. Recently, an extension of this model to peak like curves has been developed using wavelet analysis.

ABSTRACT. Streaming data are data that are generated continuously from a vast variety of sources. With all new technologies and so many portable devices data are collected and generated in real time. Also, the high pace of development, trading, and business demand that these data should be used instantly, so important decisions can be made in a short time. Streaming data are processed in near real-time applications and processing is done record by record or over sliding time windows. Building prediction models in a streaming setting is a challenging task. Many companies, in order to find the best prediction model, organize competitions where they publish some of their data and give a task to competitors to build a model. Until now this is done only for static datasets. In this work, we propose a platform for data science competitions on data streams. The platform has been built on top of the pillars of Information Flow Processing[1]: processing on-the-fly, high availability and scalability. The platform is implemented using several new big data technologies such as Kafka, gRPC, Protobuf, Spark, and MongoDB. When the competition is scheduled, the system will pull data from sources, generate the stream according to competition setting and provide it to multiple competitors. Competitors will build their model and submit the predictions which are evaluated immediately. The platform supports several types of competitions: regression and classification, single or multi-label and competitors can use different languages: Python, Java and, R. We plan to run competitions on real use cases provided by EDF such as Forecast and Disaggregation[2].

References [1] M. Stonebraker, U. Çetintemel, and S. Zdonik, “The 8 requirements of real-time stream processing,” ACM Sigmod Record, vol. 34, no. 4, pp. 42–47, 2005. [2] J. Z. Kolter and M. J. Johnson, “Redd: A public data set for energy disaggregation research,” in Workshop on Data Mining Applications in Sustainability (SIGKDD), San Diego, CA, vol. 25, no. Citeseer. Citeseer, 2011, pp. 59–62.

ABSTRACT. Viability of an Open Set for Stochastic Control Systems

ABSTRACT. We consider the regularity problem for time-optimal trajectories of a single-input control-affine system on a $n$-dimensional manifold. We prove that, under generic conditions on the drift and the controlled vector field, any control $u$ associated with an optimal trajectory is smooth out of a countable set of times. More precisely, there exists an integer $K$, only depending on the dimension $n$, such that the non-smoothness set of $u$ is made of isolated points, accumulations of isolated points, and so on up to $K$-th order iterated accumulations.

ABSTRACT. Many cancer treatments are administered at the maximal tolerated dose, and eventually fail as the tumor becomes resistant. Adaptive therapy, a new kind of cancer therapy, aims at delaying the emergence of resistance by delivering smaller or less frequent doses. The precise schedule and dosage depend on each patient’s response to the treatment. Experimental results are highly promising, but protocols and models are still crude. An ongoing PGMO project aims at clarifying why and when adaptive therapy should be expected to improve on current therapies, and how to choose optimally the timing and dosage of drug delivery. A preliminary step is to establish sound models of adaptive therapy. In this talk, we will discuss modelling choices, such as the basic tumor growth model, the number of cell types, the degree of resistance of resistant cells, the treatment effect on the irrigation of the tumor, the way to model the tumor spatial structure, and the impact of these choices on the optimal treatment.

ABSTRACT. We propose a method to solve exactly the verification problem for a subclass of discrete-time affine dynamical systems. Once formulated as an optimization problem with dynamical system constraints, we truncate the infinite sequences present in the constraints set at a rank valid for all possible initial conditions. The construction of this rank uses classical tool form matrix theory and semi-definite programming.

ABSTRACT. See joint document

ABSTRACT. This paper studies two classes of nonmonotone variational inequality problems called restricted co-coercive ones and restricted strongly monotone ones. Their relations with each other and with strongly monotone and co-coercive variational inequalities are presented. In particular, if a restricted co-coercive variational inequality satisfies a so called restricted linear growth condition, then it is also restricted strongly monotone. The relation between restricted strongly monotone variational inequalities and the so-called restricted secant inequality and restricted convex functions in recent research work on nonconvex optimization is also discussed. Non pseudomonotone examples of both restricted co-coercive and restricted strongly monotone variational inequalities are given. The convexity and connectedness of the solution set of a restricted co-coercive problem are studied. The linear transformation of a strongly monotone variational inequality problem is shown to be a monotone and restricted co-coercive in some special cases. Finally, the convergence of proximal projection methods for restricted co-coercive variational inequality problems is proved and, furthermore, if it satisfies the restricted linear growth condition, it has a linear convergence rate.

ABSTRACT. Exact sparse optimization problems (also known as sparsity-constrained problems) can be formulated as the minimization of a criterion under a constraint that the $l_0$ ``norm'' be less than a given integer, that measures the sparsity of the solution. Since the $l_0$ ``norm'' is not convex, such problems do not generally display convexity properties, even if the criterion to minimize is convex.

One route to attack such problems is to replace the sparsity constraint by a convex penalizing term, that will induce sparsity. Thus doing, we lose the original exact sparse optimization problems, but we gain convexity (benefiting especially of duality tools with the Fenchel conjugacy).

We propose another route, where we lose convexity but where we gain at keeping the original exact sparse optimization formulation. For this purpose, we introduce an adapted conjugacy, induced by a novel coupling, the Fenchel coupling after primal normalization. This coupling has the property of being constant along primal rays, like the $l_0$ ``norm''. Thus equipped, we present a way to build a dual problem, that is a lower bound of the original exact sparse optimization problem. We illustrate our result on the classical least squares regression sparse optimization problem.

ABSTRACT. Coordinate descent methods decompose a large optimization problem into a sequence of one-dimensional optimization problems. The algorithm was first described for the minimization of quadratic functions by Gauss and Seidel. Coordinate descent methods have become unavoidable in machine learning because they are very efficient for key problems, namely Lasso, logistic regression and support vector machines. Moreover, the decomposition into small subproblems means that only a small part of the data is processed at each iteration and this makes coordinate descent easily scalable to high dimensions.

One of the main ingredients of an efficient coordinate descent solver is its ability to compute efficiently partial derivatives of the objective function. In the case of least squares for instance, this involves the definition of a vector of residuals that will be updated during the run of the algorithm. As this operation needs to be performed at each iteration, and millions of iterations are usually needed, the residual update and directional derivative computation must be coded in a compiled programming language.

The algorithm we implemented is described in [Fercoq and Bianchi, A Coordinate Descent Primal-Dual Algorithm with Large Step Size and Possibly Non Separable Functions] and can be downloaded on https://bitbucket.org/ofercoq/cd_solver. It deals with residual updates and dual variable duplication in a generic fashion and includes a modelling interface in Python for the definition of the optimization problem.

ABSTRACT. Finding the minimum of a multivariate real polynomial is a well-known hard problem with various applications. We present a polynomial time algorithm to approximate such lower bounds via sums of nonnegative circuit polynomials (SONC). As a main result, we carry out the first large-scale comparison of SONC, using this algorithm and different geometric programming (GP) solvers, with the classical sums of squares (SOS) approach, using several of the most common semidefinite programming (SDP) solvers. SONC yields bounds competitive to SOS in several cases, but using significantly less time and memory. In particular, SONC/GP can handle much larger problem instances than SOS/SDP.

ABSTRACT. This work presents a convex-optimization-based framework for analysis and control of nonlinear partial differential equations. The approach uses a particular weak embedding of the nonlinear PDE, resulting in a linear equation in the space of Borel measures. This equation is then used as a constraint of an infinite-dimensional linear programming problem (LP). This LP is then approximated by a hierarchy of convex, finite-dimensional, semidefinite programming problems (SDPs). In the case of analysis of uncontrolled PDEs, the solutions to these SDPs provide bounds on a specified, possibly nonlinear, functional of the solutions to the PDE; in the case of PDE control, the solutions to these SDPs provide bounds on the optimal value of a given optimal control problem as well as suboptimal feedback controllers. The entire approach is based purely on convex optimization and does not rely on spatio-temporal gridding, even though the PDE addressed can be fully nonlinear. The approach is applicable to a very broad class nonlinear PDEs with polynomial data. Computational complexity is analyzed and several complexity reduction procedures are described. Numerical examples demonstrate the approach.

ABSTRACT. We consider the problem of finding exact sums of squares (SOS) decompositions for certain classes of non-negative multivariate polynomials, relying on semidefinite programming (SDP) solvers.

We start by providing a hybrid numeric-symbolic algorithm computing exact rational SOS decompositions for polynomials lying in the interior of the SOS cone. It computes an approximate SOS decomposition for a perturbation of the input polynomial with an arbitrary-precision SDP solver. An exact SOS decomposition is obtained thanks to the perturbation terms.

We prove that bit complexity estimates on output size and runtime are both polynomial in the degree of the input polynomial and simply exponential in the number of variables.

Next, we apply this algorithm to compute exact Polya and Putinar's representations respectively for positive definite forms and positive polynomials over basic compact semi-algebraic sets.

Our algorithms are implemented in the Maple package RealCertify. We compare the performance of RealCertify with existing methods in computer algebra, including cylindrical algebraic decomposition and critical point method.

ABSTRACT. Energy systems are extremely complex; planning their improvement over multiple decades necessarily also requires computing optimal tactical/operational decisions spanning from years to minutes. Decomposition methods are the only way to tame the corresponding huge-scale optimization problems, especially since uncertainty has necessarily to be explicitly modeled at several levels. However, what is needed is not just one decomposition approach, but a hierarchical combination of different decomposition methods (say, Lagrangian and Benders' ones), resulting in a heterogeneous at least three-level decomposition approach. Efficiently implementing such an algorithm is an Herculean task, especially if modelling flexibility is required and distributed computation is used to exploit HPC systems, which is necessary to tackle real-world instances.

Under the auspices of several PGMO projects and one H2020 project, the innovative, open-source Structured Modeling System++ (SMS++) is being developed. Aim of SMS++ is to facilitate the implementation of general and flexible algorithms for structured optimization problems, such as the (Uncertain) Unit Commitment problem. The ultimate aim is that of being able to developing multi-level decomposition approaches where, say, the (U)UC is "just the lower level", while further levels regarding the long-term management of energy reservoirs and even changes of the energy system as a whole can be taken into account. We will present the current state of the SMS++ system, focussing on its features that are more relevant for the implementation of multi-level decomposition approaches to hard (energy) problems.

ABSTRACT. The classical Unit Commitment problem (UC) can be essentially described as the problem of establishing the energy output of a set of generation units over a time horizon, in order to satisfy a demand for energy, while minimizing the cost of generation and respecting technological restrictions of the units (e.g., minimum on/off times, ramp up/down constraints). The UC is typically modelled as a (large scale) mixed integer program and its deterministic version, namely the version not considering the presence of uncertain data, has been object of wide theoretical and applied studies over the years.

Traditional (deterministic) models for the UC assume that the net demand for each period is perfectly known in advance. However, in practice, the demand is dictated by the amounts that can be sold by the producer at given prices on the day-ahead market, leading to strategic bidding problems. One difficulty therefore arises if the optimal production dictated by the optimal solution to the UC problem cannot be sold at the producer's desired price on the market, leading to a possible loss. Another strategy could be to bid for additional quantities at a higher price to increase profit, but that could lead to infeasibilities in the production plan. Furthermore, the mechanism of the bidding market considered has a considerable impact on the spot prices and the quantities bought to retailers and producers, complexifying the structure of the problem. We consider Price Coupling of Regions (PCR) as bidding market, a coupling that links national day-ahead markets in order to increase the global welfare.

Our aim is to model and solve the UC problem with a second level of decisions ensuring that the produced quantities are cleared at market equilibrium in a coupled day-ahead market. In their simplest form, market equilibrium constraints are equivalent to the first-order optimality conditions of a linear program. The UC in contrast is usually a mixed-integer nonlinear program (MINLP), that is linearized and solved with traditional Mixed Integer (linear) Programming (MIP) solvers. Taking a similar approach, we are faced to a bilevel optimization problem where the first level is a MIP and the second level linear.

In this talk, we assume that demand curves and offers of competitors in the market are known. The market considered is a PCR of the EU that considers several day-ahead markets coupled through a transmission network. Following the classical approach for these models, we present the transformation of the problem into a single-level program by rewriting and linearizing the first-order optimality conditions of the second level. A discretization of the possible optimal spot prices is made and valid inequalities are proposes to obtain a tight MILP formulation. Some aggregation and disaggregation techniques taking advantage of the properties of PCR improves considerably the computation times. A heuristic applicable to special ordered sets is also presented to reduce the number of binary variables when discretizing a continuous variable.

ABSTRACT. Rising concerns about climate change and global warming have led to an increasing use of renewable energies which are commonly characterized by intermittent power generations. The resulting growing share of renewables then requires more and more flexibility from energy systems. Electrical Energy Storage (EES) technologies represent high-value solutions for enabling this system flexibility. In addition, not only do storage devices can help integrate more renewable energies but they may offer a great range of services. Besides, the energy storage market is growing fast and competitive EES technologies have to meet key expectations among: being low-cost, sustainable, offering short response time and proving to be efficient. Experts claim that today most commercial interest is in battery storage. However, there exists numerous EES technologies - mechanical, electrochemical, electrical and thermal - and none has proven to outperform all technologies in all applications yet. By now, the selection and the sizing of a EES depend on the target system structure and settings. Moreover, studies reported that the so-called hybrid storage solutions - which are based on a diverse EES portfolio - could be the most likely to compete successfully. Deciding a system tailor made EES based design (technologies selection and sizing) may be critical. The present work aims at proposing a decision support approach for designing EES systems through simulations by means of Stochastic Optimization.

ABSTRACT. In railway scheduling, the rolling stock scheduling problem adresses the assignment of train paths to physical unsplittable rolling stock units, hence defining a sequence of trains for each unit in order to cover the passenger demand. In practice, this problem is solved several months in advance. However, changes may occur afterwards, either prior or during operations. It is then necessary to adapt the rolling stock scheduling to the new context with a re-optimisation process. Our goal is to compute a nominal schedule designed to be adaptive to a set of known demand scenarii, with minimal mean deviation over the scenarii. In other words, an adaptive solution is a nominal solution that will not change much regardless of the scenarii. This work focuses on the rolling stock scheduling problem with scenarii corresponding to an increasing or decreasing passenger demand for a small set of trains, requiring more or less rolling stock units than in the nominal situation. A feasible ! solution for our problem contains a nominal rolling stock schedule and a collection of adapted rolling stock schedules, one for each considered scenario. We propose a MILP where the vertices correspond to the trains, and each edge represents a succession of two potential trains covered by the same rolling stock unit. We duplicate the nominal variables for each scenario, and define the deviation between the nominal and an adapted schedule as the structural differences between their graphs. The objective contains a quadratic criteria controlling the mean expected deviation. We illustrate the correctness and efficiency of the model by computational experiments.

ABSTRACT. Companies face the challenge of managing large quantities of maintenance interventions. Walking can reduce the time required for parking and reduce the use of expensive and polluting car transport. Furthermore car journeys in big cities take longer in ever increasing traffic. This paper propose a model for multimodal routing problems with 2 levels of optimization. The first level computes the walking routing with clustering and TSP algorithms. The second level computes the car routing with LNS approach.

ABSTRACT. Green and electrical routing problems attract a growing attention. We consider the electrical Vehicle Scheduling Problem (eVSP). A set of trips must be operated by a fleet of electrical vehicles. Each trip is scheduled between an origin and a destination at a given time. Vehicles have a limited battery capacity. Inbetween two trips, a vehicle can go to a station to charge its battery. Costs are associated to vehicle use and distance traveled. The objective is to build a sequence of trips and recharge followed by each vehicle in order to operate all trips at minimum cost. We propose an exact column generation approach to the eVSP. Numerical benchmark on instances of the literature demonstrate the efficiency of our approach. Our pricing algorithm, and more precisely the way it encodes energy consumption information in an ad-hoc algebraic structure, plays a key role in the efficiency of our column generation.

ABSTRACT. Given a directed graph $G=(V,A)$, capacity and cost functions on $A$, a root $r$, a subset $T \subset V$ of terminals, and an integer $k$, we aim at selecting a minimum cost subset $A'\subseteq A$ such that for every subgraph of $G'=(V,A')$ obtained by removing $k$ arcs from $A'$ it is possible to route one unit of flow from $r$ to each terminal while respecting the capacity constraints. We focus on the case where the input graph $G$ is planar and propose a tabu search algorithm whose main procedure takes advantage of planar graph duality properties.

ABSTRACT. Contextual Bandits have been studied extensively for the past ten years, with many variants. They are an extension of Multi-Armed Bandits where information is shared among the arms. In the game we consider, at each time $t$, a set of contexts proper to each arm is drawn $(X_{ta} ; a \in [K])$. The expected rewards are the scalar product between those context vectors and some unknown vector $\beta$.

To deal with the exploration-exploitation tradeoff, optimistic strategies are one solution to ensure optimal upper bounds for regret. As first contribution, we prove under some realistic assumptions on the context distributions, that enforcing exploration in the game we propose is unnecessary. Whatever the strategy followed, the regret upper bound is of optimal order. As a second contribution, we detail the constant associated to the regret bound when following a greedy strategy, which echoes previous bounds found in UCB for MAB.

ABSTRACT. In the stochastic stationary multi-armed bandit setting, the Thompson Sampling algorithm exhibits excellent results in practice and it has been proved to be asymptotically optimal \cite{kaufmann2012thompson}. The extension of Thompson Sampling algorithm to the switching multi-armed bandit problem, proposed in \cite {mellor2013thompson}, is a Thompson Sampling equiped with the well-known Bayesian online change point detector \cite{adams2007bayesian}. In \cite{alami:hal-01811697}, the authors have proposed an another extension of the previous approach by leveraging the Bayesian aggregation of a growing number of experts seen as learners. Experiments provide some evidences that in practice, the proposed algorithm compares favorably with the previous version of Thompson Sampling for the switching multi-armed bandit problem, while it outperforms clearly other algorithms of the state-of-the-art. This has led us to consider the question of proving the optimality of this kind of approaches to catch the change points in a non-stationary decision making paradigm. In this talk, we will give the first mathematical intuitions behind the hypothetical optimality of the Thompson Sampling for the switching environment and highlight its impressive experimental results.

ABSTRACT. Intelligent transportation systems are now able to record large amounts of data about traffic conditions, and especially speed profiles. Using data science and optimization techniques, we propose a stochastic data-based traffic model that preserves the energy consumption distribution. From the speed profiles we construct (speed, acceleration) distributions, and apply a clustering method (k-means [1]) to obtain a manageable sized model. Different times of the day with similar speed patterns and traffic behavior are thus grouped together in a single cluster. To preserve geometrical aspect of the (speed, acceleration) distributions, we used the Wasserstein distance [2, 3] in the k-means algorithm. We tested our model with data from the traffic simulator SUMO [4] as well as with real traffic data from smartphone application "GECO air". The results show that with a small number of clusters the model is able to provide an accurate estimation of the energy consumption distribution. We plan to use this model to develop an energy management system for hybrid vehicles that is able to handle traffic conditions.

ABSTRACT. The correlation clustering problem [1] consists in partitioning the vertices of a graph such that the sum of the positive weights between the clusters and the negative weights inside the clusters is minimized. In this work, we study a variation of this problem in which a set of vertices called mediators is additionally identified.

ABSTRACT. Short-term models for the next two days of production of a unit are typically expressed as a conjunction of time series constraints on a same time series telling how much must be produced by a given unit every half hour. To ease the challenge of simultaneously satisfying all expressed constraints we produce a database of parameterised linear and non linear invariants where 70% of linear invariants are proven to be sharp.

ABSTRACT. We address a scheduling and energy source assignment problem abstracted from several applications including data centers, smart buildings, hybrid vehicles and manufacturing. We present upper and lower bounding procedures based on different decomposition approaches. In this talk, the merits and drawbacks of the different approaches are analyzed.

ABSTRACT. Membrane gas separation processes are a rapidly spreading technology with applications to numerous industrial sectors: energy, chemistry, pharmacy, electronics, aeronautics, etc [1].Indeed, membrane separation combines a series of key advantages, since they can result in energy efficient, small sized and environmental friendly processes. Nevertheless, to obtain these advantages, it is necessary to design multistage processes, that is determining the necessary number and types of membrane modules, their sizes, interconnections and operating conditions.The underlying optimization problem is a non-convex MINLP [2]. Even if in the last decades,several optimization based strategies were proposed, all of them present limitations in terms of design and/or operating condition possibilities. Furthermore, they have not been tested on a significant number of case studies to prove their general validity [3]. For these reasons, the current industrial practice is still based on experience and simulation based approaches, that are very time-consuming and often do not produce good results in terms of product quality and process cost.The aim of our project IMPRESS, is to propose a critical comparison of current optimization-based process synthesis approaches on a significant number of case studies to assess their advantages and inconveniences. In this presentation, we will introduce the underlying mathematical model and some general ideas we matured from the research we already developed. More specifically, we will present some of the results we obtained on a case-study from the current literature and on an industrial application [4].

References: [1] R. W. Baker, Membrane Technology and Applications, (2004) 2nd Ed. John Wiley Sons,Chichester, England. [2] L. T. Biegler, Nonlinear Programming: Concepts, Algorithms, and Applications to Chemical Processes, (2010) MOS-SIAM Series on Optimization. [3] Q. Chen and I. E. Grossmann, Recent developments and challenges in optimization-based process synthesis, Ann. Rev. Chem. Biomolec. Eng. (2017) 8 (1), 249–283. [4] A. Ramirez-Santos, M. Bozorg, B. Addis, V. Piccialli, C. Castel, and E. Favre. Optimization of multistage membrane gas separation processes. Example of application to CO2 capture from blast furnace gas, J. of Membrane Science, (2018) 566, 346–366.

ABSTRACT. In this work, we consider a firm using on-site generation of renewable energy to supply power for its manufacturing processes, in coordination with grid energy. Hence, two sources of energy are available to supply production power: the on-site generated renewable energy, free of use but available in a limited time-varying quantity, and the grid electricity, virtually available at any required level but incurring a unit cost per kWh purchased. If the renewable source provides more energy than needed for production in a period, the energy surplus can be sold. The availability of the on-site generated energy renders the production costs variable, inciting to produce more when more renewable energy is generated. To do that, the firm can adjust its production capacity, typically by modifying the shift planning. We focus on a mid-term capacity management, production and inventory planning. The firm has to satisfy a time-varying demand, known on a given time horizon, either from stock or by producing directly at the period when the demand occurs. Our purpose is to find a production planning of minimal cost, taking into account production and holding cost, extra capacity installation and energy issues.

ABSTRACT. \documentclass[11pt,a4paper]{article} \usepackage{graphicx} \usepackage{ dsfont } % uncomment according to your operating system: % ------------------------------------------------ \usepackage[latin1]{inputenc} %% european characters can be used (Windows, old Linux) %\usepackage[utf8]{inputenc} %% european characters can be used (Linux) %\usepackage[applemac]{inputenc} %% european characters can be used (Mac OS) % ------------------------------------------------ \usepackage[T1]{fontenc} %% get hyphenation and accented letters right \pagestyle{empty} %% no page numbers! \usepackage{fullpage} \begin{document} \thispagestyle{empty}

\title{\textbf{Self-contracted curves and extensions.}} \author{Aris Daniilidis$^1$\quad \underline{Sebasti\'an Tapia}$^2$\\ \small $^1$Universidad de Chile, Chile, {\tt arisd@dim.uchile.cl}\\ \small $^2$Universidad de Chile, Chile, {\tt stapia@dim.uchile.cl} } \date{} % <--- leave date empty \maketitle\thispagestyle{empty} %% <-- you need this for the first page

{{\bf Key words}: Gradient flows, self-contracted curves, rectifiability.}\\[2em]

A class of curves encompassing all orbits generated by a gradient flow of a quasiconvex potential, has been defined in \cite{first}. These curves are called self-contracted curves and enjoy the following simple metric definition: Let $\gamma:I\subset\mathds{R}\to(X,d)$ be a curve where $I$ is an interval and $(X,d)$ is a metric space. The curve $\gamma$ is called self-contracted if for every $t_1

\[d(\gamma(t_1),\gamma(t_3))\geq d(\gamma(t_2),\gamma(t_3)).\] In \cite{firstalmost}, when the ambient space is the Euclidean space $\mathds{R}^n$, an upper bound for the length of the aforementioned curves is given depending only on the dimension $n$ and the diameter of the convex hull of the image of the curve. This result has important consequences in the study of convergence of the proximal algorithm method or even in dynamics given by a convex foliation. Recently, two extensions of the class of self-contracted curves were defined in \cite{second} ($\lambda$-curves and $\lambda$-eels) and many open questions arise out of this generalization. In this talk we shall present the main idea of \cite{zero} and we show how this idea can be used for the study of rectifiability for $\lambda$-curves, with $\lambda<1/d$. We shall also present the main obstacle to get a complete result (without a restriction on the valued of the parameter $\lambda$). Finally, we will also show some results for $\lambda$-eels.

\begin{thebibliography}{00} \bibitem{zero} P. Manselli, C. Pucci. Maximum length of steepest descent curves for quasi-convex functions. Geometriae Dedicate, 38 (1991), pp. 211-227.

\bibitem{first} A. Daniilidis, O. Ley, S. Saboureau. Asymptotic behaviour of self-contracted planar curves and gradient orbits of convex functions. Journal de Math\'ematiques Pures et Appliqu\'ees. 94 (2010), 183-199

\bibitem{firstalmost} A. Daniilidis, G. David, E. Durand, A. Lemenant. Rectifiability of self-contracted curves in the Euclidean space and applications. Journal of Geometrical Analysis. 25 (2015), pp. 1211-1239.

\bibitem{second} A. Daniilidis, E. Durand, R. Deville. Metric and geometric relaxations of self-contracted curves. Journal of Optimization Theory and Applications. (2018), to appear. \end{thebibliography}

\end{document}

ABSTRACT. In recent years, techniques based on convex optimization that produce converging hierarchies of lower bounds for polynomial optimization problems (POPs) have gained in popularity. At their heart, these hierarchies rely on Positivstellensatze from the end of the 20th century (e.g., due to Putinar and Schmudgen) that certify positivity of polynomials on an arbitrary basic semialgebraic set. In the first part of this talk, we show that such hierarchies could in fact be designed from much more limited Positivstellensatze dating back to the beginning of the 20th century that certify positivity of polynomials globally. In the second part of this talk, we present a converging hierarchy for lower bounds on POPs that only requires the ability to multiply polynomials together and check nonnegativity of the resulting polynomial’s coefficients. In this way, it is “optimization-free” unlike previous hierarchies that, for the most part, rely on sum of squares certificates and hence semidefinite programming.

ABSTRACT. We propose a new viewpoint on variational mean-field games with diffusion and quadratic Hamiltonian. We show the equivalence of such mean-field games with a relative entropy minimization at the level of probabilities on curves. We also address the time-discretization of such problems, establish Gamma-convergence results as the time step vanishes and propose an efficient algorithm relying on this entropic interpretation as well as on the Sinkhorn scaling algorithm

ABSTRACT. see attached file

ABSTRACT. We will consider first-order Mean Field Games (MFG) with quadratic hamiltonian and local coupling. In this case, the density of agents is the solution of a variational problem where it minimizes its total kinetic energy and a congestion cost. Using time discretization and flow interchange techniques (originally introduced by Matthes, McCann and Savaré for the study of gradient flows), we are able to provide $L^\infty$ bounds on the density of agents. In the case where the density of agents is forced to stay below a given threshold (a model studied by Cardaliaguet, Mészàros and Santambrogio), leading to the apperance of a pressure force, the same techniques lead to a $L^\infty(H^1)$ bound on the pressure, improving known results.

With these estimates at our disposal, we are able to give a strong Lagrangian interpretation of the MFG and ensure regularity of the value function.

ABSTRACT. Textual data streams are ubiquitous nowadays and there is still room for advanced techniques to track the information flow. More precisely, we aim at studying the intertwining between the topical evolution and special texts that influence this evolution, in collaboration with EDF R&D. In this project we focus on novelty detection, that is the identification of new topics over a time-dependent corpus. More precisely the problem is to learn how to detect new information from a document stream. After a first study of the subject leveraging topic models we tackle here how different document representations may help on the detection of novelties. For this purpose, we use different representation schemes that embed the textual information into a vector space endowed by a more or less rich algebraic structure. This way working on documents can be easily performed by using basic vector operations (e.g., pairwise comparison becomes a dot product). We then assume that novelty is connected to aberrant observations: new documents that are projected far away in the vector space are assumed to carry new information. We present the results of experiments that involve several different ways to project the documents, at different granularity levels, into the vector space. Starting from word embedding model such as the ones proposed on and infersent we show on a public data set composed of abstracts of scientific articles that the tested approaches based on document embedding methods perform as well as LDA-based models.

ABSTRACT. Our research deals with the estimation of the worldwide number of passengers by Origin-Destination (O-D) pairs, on a monthly basis, in the airline industry. Deducting an O-D matrix from partial data on segments doesn't constitute a new issue by itself but the problem is particularly difficult in the airline industry because of its extremely huge size.Our problem can be stated as follows. Knowing the amount of passengers leaving and arriving to each airport, an estimated number of passengers on each flight, lower bound (limit below which the flight is cancelled) and upper bound (capacity of the plane) on the number of passengers that can be transported on each direct flight, the possible itineraries for each O-D pair and the probability of using them (estimated by statistical methods), find the number of passengers for each O-D pair. The problem has been modeled as a mathematical program for which different objective functions, corresponding to standard norms, have been considered : L1, L2 norms. The formulations with the L1 norm corresponds to a linear program while the L2 norm induces a convex quadratic program. Each formulation has been solved using an optimization software (Cplex) on randomly generated instances, and on a real-life one provided by the company Amadeus. The formulation with the L2 norm has been also solved with a lagrangean relaxation approach. Statistical outputs measuring the deviation to the real O-D matrix (for the randomly generated instances), or to the estimated number of passengers (for the real-life instance) have been generated. The numerical results show that, for randomly generated instances, both in terms of the O-D matrices quality and processing times, the L2 norm formulation behaves surprisingly better than the linear one. This formulation has allowed to solve a real-life instance dealing with 234 airports, 5315 legs (direct flights) and 200410 itineraries in less than 1mn. Numerical sensitivity analysis have been also conducted to empirically estimated the variation to the optimal solution values when some of the model data vary.

ABSTRACT. Obtaining a very large volume of real data is complicated in some settings, for instance in the detection of target in clouds. This limitation makes difficult the use of machine learning methods, whether they are "deep" or not. The objective of this project is to propose and validate techniques for increasing the size of the databases of cloud data by texture analysis and resynthesis.

As part of this project, we studied techniques for Generative Adversial Network synthesis, a methodology introduced by Goodfellow in 2014. The principle is simple: to synthesize objects of a given class, we will build a function that transforms white noise into a synthetic object so that a computer has difficulty distinguishing between real objects and synthetized objects. To do this, on modify alternatively the synthesis functionand the detection algorithm. The most interesting results in our seeting have been obtained by using neural networks in both steps.

In this study, we uses a database public cloud (Singapore Whole Sky Imaging) to learn from GAN generating patches. We will present a comparison of possible architectures in terms of synthesis quality and representativeness for the detection.

ABSTRACT. We consider the task of optimizing an aircraft climb trajectory where the system dynamics are unknown. The standard approach adopted by control engineers in this kind of setting is to gather data from the system, use it to identify its dynamics and solve a surrogate optimal control problem cast using the identified model. In this situation, it is important to prevent the optimized trajectory from going too far away from the domain occupied by the data used to derive the dynamics model, as the later is not guaranteed to be valid outside this region. This motivates the need for a proximity indicator between a given trajectory and a set of recorded reference trajectories. In this presentation, we propose a probabilistic criterion for such a purpose, based on the marginal density functions of an underlying random process supposed to have generated the recorded data. For practical applications, a class of estimators based on the aggregation of multivariate density estimators is defined and proved to be consistent. We then introduce it as a penalty term in the optimal control problem. Our approach is illustrated with an aircraft minimal consumption problem and data from real recorded flights. We observe in our numerical results the expected trade-off between the minimal consumption and the trajectory likelihood.

ABSTRACT. A common assumption in physiology about human motion is that the realized movements are done in an optimal way. The problem of recovering of the optimality principle leads to the inverse optimal control problem. Formally, in the inverse optimal control problem we should find a cost-function such that under the known dynamical constraint the observed trajectories are minimizing for such cost. In this paper we analyze the inverse problem in the case of finite horizon linear-quadratic problem. In particular, we treat the injectivity question, i.e. whether the cost corresponding to the given data is unique, and we propose a cost reconstruction algorithm. In our approach we define the canonical class on which the inverse problem is either injective or admit a special structure, which can be used in cost reconstruction.

ABSTRACT. Seismic acquisition aims to collect data for imaging the subsurface of the Earth. At sea,
these data are acquired by towing a large spread of sensors behind a seismic vessel sailing along
pre-defined straight acquisition lines [1]. In-between each nominal line, a line change is performed.
This maneuver stands as non-productive phase, which contributes significantly to the
acquisition time and cost. Designing efficient line changes is a difficult and challenging task
in survey area of complex sea currents. It relies on on-board operator experience to find an
optimal trajectory for the vessel, which, at the same time, minimizes the duration of the turn
while protecting the integrity of the in-sea equipment.
To support marine operations, we propose to reformulate the problem in optimal control
frame. A standard problem in optimal control [2, 3] is to seek for minimum length curves
among those with bounded curvature that join two endpoints with given tangents. This is the
so-called unicycle vehicle problem with two controls: one control is the angle and the other is
the longitudinal speed. This is the simplest possible vehicle, without trail (see [4, 5, 6, 7] for
generalizations, motion planning and complexity of such systems). The aim of our study is to
determine the optimal track of a ship towing long underwater cables, dealing with a minimum
time problem for a system with a trail, together with a curvature constraint on the trail itself.
Such a constraint is responsible for additional difficulties (see, e.g., [8]).

ABSTRACT. Multistage stochastic optimization problems are, by essence, complex because their solutions are indexed both by stages (time) and by uncertainties (scenarios). Hence, their large scale nature makes decomposition methods appealing. We present, in an unified framework, three main approaches and methods to decompose multi-stage stochastic optimization problems for numerical resolution: time decomposition (and state-based resolution methods, like Stochastic Dynamic Programming, in Stochastic Optimal Control); scenario decomposition (like Progressive Hedging in Stochastic Programming); spatial decomposition (like Dual Approximate Dynamic Programming). We point on the difficulties raised by the mixing of such methods to tackle large scale problems. We provide illustrations for the management of new energy systems (smart grids).

ABSTRACT. We provide a method to decompose multistage stochastic optimization problems by time blocks. Our framework covers both stochastic programming and stochastic dynamic programming. We formulate multistage stochastic optimization problems over a so-called history space, with solutions being history feedbacks. We prove a general dynamic programming equation, with value functions defined on the history space. Then, we consider the question of reducing the history using a compressed ``state'' variable. This reduction can be done by time blocks, that is, at stages that are not necessarily all the original unit stages. We prove a reduced dynamic programming equation. Then, we apply the reduction method by time blocks to two time-scales stochastic optimization problems and to a novel class of so-called decision hazard decision problems, arising in many practical situations, like in stock management.

ABSTRACT. We consider a stochastic optimization problem where different units are connected together via a network. Each unit is a (small) control system, located at a node. Each unit state evolution is affected by uncertainties and by controls from the neighbor units transmitted through edges. Static constraints couple all units at each time. We formulate a global stochastic optimization problem. We propose two decomposition methods, whether we decouple the constraints by prices or by quantities. We show that the global Bellman function can be bounded above by a sum of quantity-decomposed nodal value functions, and below by a sum of price-decomposed nodal value functions. We provide conditions under which these nodal value functions can be computed by dynamic programming. We illustrate these results with numerical studies that tackle the decentralized optimization of urban micro-grids.

ABSTRACT. Answering connectivity queries in real algebraic sets is a key algorithmic challenge for motion planning. All known algorithms run in time which is exponential in the dimension of the ambient space (and polynomial in the maximum of the degrees of the input polynomials).

In this talk, we focus on real algebraic sets defined by quadrics under some genericity assumptions (smoothness). I will present a new algorithm which runs in time {\em subexponential} in the dimension of the ambient space, polynomial in the maximum of the degrees of the input polynomials and exponential in the number of equations.

ABSTRACT. The positive semidefinite rank of a convex body C is the size of its smallest positive semidefinite formulation. We show that the positive semidefinite rank of any convex body C is at least sqrt(log d) where d is the smallest degree of a polynomial that vanishes on the boundary of the polar of C. This improves on the existing bound which relies on results from quantifier elimination. Our proof relies on the Bezout bound applied to the Karush-Kuhn-Tucker conditions of optimality. We discuss the connection with the algebraic degree of semidefinite programming and show that the bound is tight (up to constant factor) for random spectrahedra of suitable dimension.

ABSTRACT. 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 repre- sentation/certificate. Hyperbolic Programming (HP) is the natural convex optimization problem asking to minimize a linear function over the hyperbolicity cone of a multivariate hyperbolic poly- nomial. 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:

• the development of symbolic-numerical algorithms and implementations for the general Hyperbolic Programming problem, and • efficient computation of hyperbolicity certificates such as symmetric determinantal repre- sentations.

The two items 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.

ABSTRACT. Network routing is an already well-studied problem: the routers in the network know which path a packet must follow in order to reach its destination. Trac engineering attempts to tune the routing to meet some requirements, such as avoiding congestion or a reducing end-to-end delays. Several approaches have been devised to perform these adaptations, but only few of them deal with the uncertainty in some parameters. Mostly, the uncertainty lies in the demand, the total amount of trac that goes through the network; however, links and nodes may also fail. Robust routing approaches have been proposed to tackle this issue: indeed, they consider that trac matrices are not know precisely but that they lie in an uncertainty space that can be analytically described [1]. Oblivious routing is the extreme case where the uncertainty space is the whole set of possible trac matrices and the prescribed routing must be as close as possible to the optimum routing, whatever trac matrix eectively occurs. It has been proved that oblivious routing achieves a polylogarithmic competitive ratio with respect to congestion [2]. Several variants of robust or oblivious routing approaches will be considered and compared on series of realistic instances, some of which are based on Orange network topologies. Future works include dealing with other sources of uncertainty (for instance, survivability to failures [3]) within a common robustness framework.

ABSTRACT. The past few decades reveal a rapid increase in terms of data transfer and number of wireless devices connected to the network. As exhibited in [1], statistics show an important annual growth to 2020. This increase motivated network operators to work on Heterogeneous Network (HetNet) that creates some new challenges (resources management, ooad, network access mechanism...). One can nd a survey on HetNet access point selection issues in [2]. In this work, based on [3], we propose a method to optimize the Radio Access Technologies (RATs) selection and resource allocation in multi-technology wireless networks during a time period. We optimize it on a realistic topology of Base Stations (BS) with overlaps of the cellular coverage and dynamic users trac (arrival and departure). The optimization takes into account the requested services, dierent users' contract and user satisfaction. Furthermore, in the proposed approach, we added constraints to ban the session drops and handovers for static users. For each instant we formulate the problem as a linear optimization problem and we optimize it successively. The aim of the optimization is to jointly maximize the overall user satisfaction and the number of users connected. Comparing to a legacy approach, numerical results show that our solution outperforms in terms of user satisfaction.

ABSTRACT. One of the most studied problems that arise in the elds of Network Function Virtualization (NFV) and Software Dened Networking (SDN) is the Virtual Network Function Placement and Routing Problem (VNFP-RP). In this talk we adress a very general VNFP-RP problem, involving node and function capacity constraints, latency constraints, anti-anity rules, multi commodity ow constraints and total order constraints. Our objective is to minimize the function placement costs in addition to the node activation costs. We show that the problem is NP-hard and we model the problem as an Integer Linear Program (ILP). We propose various valid inequalities and a Benders decomposition scheme allowing us to solve the problem, within a Branch and Benders cut algorithm. Finally, we provide numerous computational results to compare some variants of the proposed formulations and show very signicant improvements over an approach based on automatic Benders cuts (generated with Cplex)

ABSTRACT. We present an algorithmic approach to compute stochastic bounds for the max flow of a network with discrete random capacity.

ABSTRACT. We present an approach to provide stochastic bounds for stochastic perts or task graphs completion time when the elementary delays are stochastic and not independent.

ABSTRACT. In the tropical semifield (R,max,+), a polynomial in the indeterminate x corresponds to the maximum of an arbitrary number of affine functions in x (with integer slopes). Likewise, a tropical polynomial in x1,...,xn is a maximum of finitely many affine functions of x=(x1,...,xn). For given n pairs of polynomials in n variables, (Pi,Qi), finding the points x where Pi and Qi are equal for all 1<= i<= n (the "tropical zeroes") is fundamental problem which arises in tropical geometry, in the study of amoebas (images by the valuation) of semialgebraic sets over a real nonarchimedean field. Here, we study the situation in which, for each 1<= i<= n, one of the two polynomials, say Pi, has only one monomial, meaning that it reduces to a single affine function. We call "one-versus-all" the polynomial systems of this kind. This is motivated by performance evaluation issues, since the computation of stationary regimes of discrete event systems with priorities reduces to the solution of one-versus-all systems (Allamigeon, Boeuf and Gaubert, 2015). Fixed point equation arising in the solution of Markov decision processes are also special cases of one-versus-all problems.

We show that the idea of tropical polyhedral homotopy, developed by Jensen for a different class of systems (Jensen, 2016), can be extended to solve a class of one-versus-all tropical polynomial systems which includes Markov decision processes. Then, we show that the dual of Jensen's homotopy is equivalent to a policy improvement algorithm, which coincides with a simplex algorithm implemented with the shadow vertex pivoting rule. We show that the same remains true if the tropical polynomials (Pi,Qi) of the system satisfy a certain condition involving colored sets of point configurations. We study properties of such configurations and provide a necessary condition for the the method to work, using results on supporting hyperplanes to convex bodies (Cappell, Goodman, Pach, Pollack, Sharir, 1996).

ABSTRACT. We study the online maximum matching problem in a model in which the edges are associated with a known recourse parameter $k$. An online algorithm for this problem has to maintain a valid matching while edges of the underlying graph are presented one after the other. At any moment the algorithm can decide to include an edge into the matching or to exclude it, under the restriction that at most $k$ such actions per edge take place, where $k$ is typically a small constant. This problem was introduced and studied in the context of general online packing problems with recourse by Avitabile et al. [AMP13], whereas the special case $k=2$ was studied by Boyar et al. [BFKL17].

In the first part of this work, we consider the edge arrival model, in which an arriving edge never disappears from the graph. Here, we first show an improved analysis on the performance of the algorithm AMP given in [AMP13], by exploiting the structure of the matching problem. In addition, we extend the result of [BFKL17] and show that the greedy algorithm has competitive ratio $3/2$ for every even $k$ and ratio $2$ for every odd $k$. Moreover, we present and analyze an improvement of the greedy algorithm which we call $L$-Greedy, and we show that for small values of $k$ it outperforms the algorithm of [AMP13]. In terms of lower bounds, we show that no deterministic algorithm better than $1+1/(k-1)$ exists, improving upon the lower bound of $1+1/k$ shown in [AMP13].

The second part of this work is devoted to the edge arrival/departure model, which is the fully dynamic variant of online matching with recourse. The analysis of $L$-Greedy and AMP carry through in this model; moreover we show a lower bound of $\frac{k^2-3k+6}{k^2-4k+7}$ for all even $k \ge 4$. For $k\in\{2,3\}$, the competitive ratio is $3/2$.

ABSTRACT. The Covariance Matrix Adaptation Evolution Strategy (CMA-ES) is a derivative-free randomized heuristic for numerical optimization. Several variants of this algorithm have been proposed in the literature. Fitting these variants into a modular approach, new variants not previously studied by human experts can be efficiently analyzed. Going beyond such a static approach, we investigate in this work the potential of an adaptive configuration, which in addition allows to adjust the algorithm to the state of the optimization process. We show that switching the configuration only once can already result in significant performance gains.

The presentation is based on the paper [Sander van Rijn, Carola Doerr, Thomas Bäck: Towards an Adaptive CMA-ES Configurator. PPSN (1) 2018: 54-65].

ABSTRACT. The PGMO SOOT project focuses on situations where the input of an optimization problem changes over time, and a solution has to be maintained all along the time horizon. In such situations, where a sequence of solutions has to be computed, there is usually a (potentially high) transition cost between consecutive solutions. So, besides the intrinsic quality of solutions, we are interested in the stability of the sequence of solutions over time (minimizing transition costs). Recent articles consider such a model of optimization over time, where the goal is to find a sequence of solutions optimizing a function which aggregates quality of solutions and transition costs. Building on this, I will present in this talk some results obtained in the SOOT project for a matching problem over time. I will also present some on-going work on the topic of the project.

ABSTRACT. The presentation starts with a brief introduction of topology optimization as a mathematical tool for optimal design of mechanical components. Although now routinely used in the industry, software for topology optimization suffers from limitations, in particular when used for complex three-dimensional structures. Our aim is to design an interior point method for the solution of large scale three-dimensional topology optimization problems. The linear systems arising in the method are solved by a Krylov subspace method preconditioned by geometric multigrid. We will explain the (expected as well as unexpected) difficulties connected with switching from two-dimensional topology optimization to three dimensions, where the dimension of a practical problem reaches tens or even hundreds of millions variables.

ABSTRACT. Optimal shape design problems in fluid mechanics have wide and valuable applications in aerodynamic and hydrodynamic problems such as the design of car hoods, airplane wings, inlet shapes for jet engines, etc. The majority of works dealing with optimal design of flow domains fall into the category of shape optimization and are limited to determine the optimal shape of an existing boundary. It is only recently that topological optimization has been developed and used in fluid design problems. It can be used to design features within the domain allowing new boundaries to be introduced into the design.

We propose in this work a new approach based on the topological sensitivity analysis. The studied problem is concerned with an optimal shape design problem in fluid mechanics. The fluid flow is governed by the Stokes equations. The theoretical analysis and the numerical simulation are discussed in two and three-dimensional cases. The proposed approach is based on a sensitivity analysis of a design function with respect to the insertion of a small obstacle in the fluid flow domain. An asymptotic expansion is derived for a large class of cost functions using small topological perturbation technique. A fast and accurate numerical algorithm is proposed. The efficiency of the method is illustrated by some numerical examples.

ABSTRACT. Non-destructive testing is an essential tool to assess the safety of the facilities within nuclear plants. In particular, conductive deposits on U-tubes in steam generators constitute a major danger as they may block the cooling loop. To detect these deposits, eddy-current probes are introduced inside the U-tubes to generate currents and measuring back an impedance signal. Based on the work of \cite{Jiang}, we develop a shape optimization technique with regularized gradient descent to invert these measurements and recover the deposit shape. To deal with the unknown, and possibly complex, topological nature of the latter, we propose to model it using a level set function as it is introduced in \cite{Allaire}. The methodology is first validated on synthetic axisymmetric configurations and fast convergence in ensured by careful adaptation of the gradient steps and regularization parameters. We then consider a more realistic modeling that incorporates the support plate and the presence of imperfections on the tube interior section. We employ in particular an asymptotic model to take into account these imperfections and treat them as additional unknowns in our inverse problem. A multi-objective optimization strategy, based on the use of different operating frequencies, is then developed to solve this problem. We shall present various numerical examples with synthetic data showing the viability of our approach.

ABSTRACT. We consider a mean-field game model where the payoff depends on a fixed parameter, that is unknown to players. Players receive a stream of private signals on this parameter along the game. We derive a mean field system satisfied by the equilibrium payoff of the game with fixed duration. Under some monotonicity assumption, we prove the uniqueness of the solution. As an example, we consider a product differentiation model, in which players are firms that sell the same product and the unknown parameter represents the preferences of the consumer on the features of the product.

ABSTRACT. In this work we consider finite Mean Field Games (MFGs), i.e. with finite time and finite states. We adopt the framework introduced in Gomes et al. (2010) and study two seemly unexplored subjects. In the first one, we analyse the convergence of the fictitious play learning procedure, inspired by the results in continuous MFGs. In the second one, we consider the relation of some finite MFGs and continuous first order MFGs. Namely, given a continuous first order MFG problem and a sequence of refined space/time grids, we construct a sequence finite MFGs whose solutions admit limits points and every such limit point solves the continuous first order MFG problem.

ABSTRACT. We look at the long time behavior of potential Mean field games (briefly MFG) using some standard tools from weak KAM theory. We first show that the time-dependent minimization problem converges to an ergodic constant -\lambda, then we provide a class of examples where the value of the stationary MFG minimization problem is strictly greater than -\lambda. This will imply that the trajectories of the time-dependent MFG system do not converge to static equilibria.

ABSTRACT. Two important elements have driven recent innovation in the field of regression: sparsity-inducing regularization, to cope with high-dimensional problems; multi-task learning through joint parameter estimation, to augment the number of training samples. Both approaches complement each other in the sense that a joint estimation results in more samples, which are needed to estimate sparse models accurately, whereas sparsity promotes models that act on subsets of related variables. This idea has driven the proposal of block regularizers such as L1 / Lq norms, which however effective, require that active regressors strictly overlap. In this paper, we propose a more flexible convex regularizer based on unbalanced optimal transport (OT) theory. That regularizer promotes parameters that are close, according to the OT geometry, which takes into account a prior geometric knowledge on the regressor variables. We derive an efficient algorithm based on a regularized formulation of optimal transport, which iterates through applications of Sinkhorn's algorithm along with coordinate descent iterations. The performance of our model is demonstrated on regular grids and complex triangulated geometries of the cortex with an application in neuroimaging.

ABSTRACT. This paper deals with supervised classification and feature selection. A classical approach is to project data on a low dimensional space with a strict control on sparsity. This results in an optimization problem minimizing the within sum of squares in the clusters (Frobenius norm) with an L_1 penalty in order to promote sparsity. It is well known though that the Frobenius norm is not robust to outliers. In this paper, we propose an alternative approach with an L_1 norm minimization both for the constraint and the loss function. Since the L_1 criterion is only convex and not gradient Lipschitz, we advocate the use a Douglas-Rachford approach. Unfortunately there is no proximity operator available for the linear form. We take advantage of the particular form of the cost and, using a change of variable, we provide a new efficient tailored primal Douglas-Rachford splitting algorithm. We also provide an efficient classifier in the projected space based on medoid modeling. The resulting algorithm, based on alternating minimization and primal Douglas-Rachford splitting, is coined ADRS. Experiments on biological data sets and computer vision dataset show that our method significantly improves the results obtained with a quadratic loss function.

ABSTRACT. We replace the L1 objective function in the Basis Pursuit problem by a Huber loss function, and derive necessary and sufficient conditions for exact recovery of an individual sparse vector. The work builds upon linear programming duality, convex duality and a classical quadratic perturbation result. Numerical examples are also given.

ABSTRACT. In this talk, we present the time minimal control problem about the saturation of a pair of spins of the same species but with inhomogeneities on the applied RF-magnetic field, in relation with the contrast problem in MRI. We make a complete analysis based on geometric control to classify the optimal syntheses in the single spin case, to pave the road to analyze the case of two spins. This points out the phenomenon of bridge, which consists in linking two singular arcs by a bang arc to bypass some singularities of the singular extremal flow. In the case of two spins, the question about global optimality is more intricate. The Bocop software is used to determine local minimizers for physical test cases and Linear Matrix Inequalities approach is applied to estimate the global optimal value and validate the previous computations. This is complemented by numerical investigations combining shooting and continuation methods implemented in the HamPath software to analyze the structure of the time minimal solution with respect to the set of parameters of the species. This reveals new complex structures, compare to the single spin case.

ABSTRACT. In this talk, we consider deterministic optimal control problems of finite time horizon in the context of differential games and nonanticipative strategies. We are interested in both unconstrained and state-constrained problems with non-linear dynamics. Our approach is based on Hamilton-Jacobi framework. We characterize the value functions of such problems as unique solutions of an appropriate Hamilton-Jacobi-Issac equation in the sense of viscosity. In the case of state-constrained problems, the epigraphs of the value functions can be described by auxiliary optimal control problems free of state constraints, and for which the value functions are Lipschitz continuous and can be characterized, without any additional assumption, as unique viscosity solutions to the present Hamilton-Jacobi-Issac equations. Besides, we present several trajectory reconstruction procedures and discuss con- vergence results of these algorithms. Finally, some numerical examples are considered for the illustration of the theoretical results.

ABSTRACT. A dual receding horizon output feedback controller for a general non linear stochastic system with imperfect information is presented. The novelty of this controller is that stabilization is treated, inside the optimization problem, as a negative drift constraint on the control that is taken from the theory of stability of Markov chains. The dual effect is then created by maximizing the Fisher Information Matrix over the stabilizing controls which makes the global algorithm easier to tune than our previous algorithm. We use a particle filter for state estimation to handle nonlinearities and multimodality. The performance of this method is demonstrated on the challenging problem of terrain aided navigation.

ABSTRACT. This work presents an analysis leading to the optimal mini-batch size for SAGA, a recent stochastic variance reduced method used for training many machine learning models without tuning any stepsize parameter. This study is based bounding the expected smoothness constant, a new notion of smoothness of stochastic functions. With this bound we can calculate practical approximations to optimal mini-batch sizes and stepsizes of SAGA and other stochastic gradient algorithms.

ABSTRACT. We propose dynamic sampled stochastic approximation methods for regularized stochastic convex optimization problems with a heavy-tailed distribution with finite second moments. Typically, it is assumed an oracle with an upper bound σ^2 on its variance (OUBV). Differently, we assume an oracle with multiplicative noise, where the variance may not be uniformly bounded over the feasible set. This includes the case of linear regression where the covariance matrix is affected by noise. With respect to tolerance, our methods achieve optimal iteration complexity and (near) optimal oracle complexity on the smooth convex and smooth strongly-convex classes improving upon Ghadimi and Lan [Math. Program., 156:59-99, 2016] and Byrd et al. [Math. Program., 34:127-155, 2012] where it is assumed an OUBV. Our methods possess a variance localization property: our bounds depend only on local variances σ(x∗)^2 at solutions x∗ and the per unit distance multiplicative variance σ^2_L (typically of the order of the Lipschitz constant). Moreover, we show there exist policies such that our bounds resemble, up to numerical constants, those obtained in the mentioned papers if it was assumed an OUBV but with the replacement σ^2:=σ(x∗)^2 in terms of variance at solutions. Our bounds are thus sharper since typically max{σ(x∗)^2,σ^2_L} << σ^2. We also discuss related results in the setting where the Lipschitz constant is unknown. Philip Thompson by Fondation Mathematique Jacques Hadamard at CREST-ENSAE, France (under contract with the École Polytechnique).

ABSTRACT. Many nonconvex optimization problems can be solved using the Majorization-Minimization (MM) algorithm that consists in upper bounding, at each iteration of the algorithm, the objective function by a surrogate that is easier to minimize. When the objective function can be expressed as a large sum of individual losses, incremental version of the MM algorithm is often used. However, in many cases of interest (Generalized Linear Mixed Model or Variational Bayesian inference) those surrogates are intractable. In this contribution, we propose a generalization of incremental MM algorithm using Monte Carlo approximation of these surrogates. We establish the convergence of our unifying scheme for possibly nonconvex objective. Finally, we apply our new framework to train a logistic regression and a Bayesian neural network on the MNIST dataset and compare its convergence behaviour with state-of-the-art optimization methods.

ABSTRACT. A Generalized Additive Game (GAG) \cite{cesari2015gag1} is a Transfarable Utility (TU-)game $(N,v)$ where each player in $N$ is provided with an \textit{individual value} and the worth $v(S)$ of a coalition $S \subseteq N$ is obtained as the sum of the individual values of players in another subset $\mathcal{M}(S)\subseteq N$. Based on conditions on the map $\mathcal{M}$ (which associates to each coalition $S$ a set of beneficial players $\mathcal{M}(S)$ not necessarily included in $S$), in this paper we characterize classes of GAGs that satisfy properties like monotonicity, superadditivity, (total) balancedness and population monotonicity, for all positive vectors of individual values. We also illustrate the application of such conditions on $\mathcal{M}$ over particular GAGs studied in the literature (for instance, the generalized airport games \cite{norde2002}, the graph colouring games \cite{deng2000, hamers2014} and the link-connection games \cite{moretti2017link}). In particular, using such conditions, we can easily show that link-connection games (that are cost games where the players are different service providers that may cooperate in order to satisfy a demand of economic exchange between pairs of nodes of a network) are monotonic, superadditive, totally balanced and pmas-admissable (i.e., they admit a \textit{population monotonic allocation scheme}\cite{sprumont}).

ABSTRACT. A standard result from auction theory  is that bidding truthfully in a second price auction is a weakly dominant strategy, or, in the language of digital advertising, 'the cost per mille (eCPM) is  equal to the click through rate (CTR) times the cost per clicks (CPC)'.
However, such assertion is incorrect if the buyers are subject to ROI constraints. More generally, several predictions derived by the traditional auction theory literature  fail to apply in the presence of such constraint. This is what we propose to discuss in this article.

We formalize the notion of ROI constrained auctions and derive a Nash equilibrium for second price auctions. We then extend this result to any combination of first and second price payment rules and  do an asymptotic analysis of the equilibrium as the number of bidders increases. Further we expose a revenue equivalence property, and finish with a proposal for a dynamic extension of the bidder ROI constrained optimization problem. 
 

ABSTRACT. In a context of competition, information – who knows what and before whom – plays a crucial role. Here, we concentrate on three models where the concept of information is present: Kuhn’s extensive tree model (K-model), Alos-Ferrer, Ritzberger infinite tree model (AFR-model) and Witsenhausen model (W-model).

The model proposed by Witsenhausen has the following main ingredients: a set of agents taking decisions in a decision space, Nature taking decisions in a sample space, configuration space which is the product of the decision space by sample space equipped with a measure, information fields that are sigma-fields on the configuration space and strategies that are mea- surable mappings from configurations to actions w.r.t. information fields. W-model deals with information in all generality. Thus, it allows to look at a problem without a priori knowing the order in which decisions were made by agents. In the subclass of causal systems, there is at least one ordering in which agents take their decisions consistently with the given information.

The extensive form is the most richly structured way to describe game situations. In his model Kuhn uses the language of graph theory to define main ingredients of the game: players, game tree, information sets and strategies. The infinite tree AFR-model generalizes K-model to any possible tree: infinite (repeated games), transfinite (long cheap talk) and even continuous (stochastic games). The authors develop the refined partition approach that proves to be useful for giving a simple equivalent condition for a player to have perfect recall. To tame the zoo of infinite trees, authors use the language of set theory constructing not trees, but posets, thus elaborating the most general framework to describe tree structures in games existing up to now.

We study whether AFR and W-models have the same potential to model games. First, we embed the subclass of causal W-models into the AFR-formalism by building an AFR-tree and translating definitions of information and strategies from W-formalism to AFR-formalism. Second, we move in the opposite direction.

ABSTRACT. We introduce a Beta version of HIG, the Instances Generator for the Hydro Unit Commitment problem.

ABSTRACT. Managing the hydroelectricity produced by the plants in hydro valleys is called the hydro unit commitment problem (HUCP). Solving efficiently and rapidly HUCP, especially when considering the optimization of cascaded reservoirs, is particularly difficult. The main reason for this mostly arises from the need to model reality as accurately as possible. One particular way of dealing with this difficulty is by disposing of an a priori discretization, i.e., considering a specific set of operational points, typically chosen in order to have maximal efficiency (highest derivatives). It is intuitive that a decomposition method is a valid strategy to tackle the hydro valley HUCP problem. However, it is also clear that the effeectiveness of the method is subject to the efficiency of solving the obtained subproblems. Our main postulate is that a two-reservoir hydro unit commitment problem (2R-HUCP) is the essential building stone of these subproblems and can be handled efficiently. We propose a Lagrangian decomposition for the complete hydro cascade system, obtaining subproblems modeled as 2R-HUCP. In addition, we propose an efficient approach based on Dynamic Programming for solving the subproblems, extending a path formulation for the single reservoir hydro unit commitment problem presented in W. van Ackooijet al. 2018.

ABSTRACT. Electric vehicles (EVs) are one of the promising solutions to face environmental and energy concerns. One of the major barriers towards the large scale adoption of EVs is the lack of charging stations to recharge vehicles during long-distance trips. We consider the problem of optimizing the deployment of an infrastructure based on fast charging stations in order to enable EV drivers to carry out long-distance trips. We focus on incorporating into the optimization problem modeling two important features: the dynamic multi-period aspect of the problem and the uncertainty on the future recharging demand. To achieve this, we propose a multi-stage stochastic programming approach in which the uncertainties are represented through a scenario tree. To solve the resulting large-size mixed-integer linear program, we develop two solution algorithms: an exact solution method based on a Benders decomposition and a heuristic one based on a genetic algorithm. Our numerical results show that both methods performs well as compared to a stand-alone mathematical programming solver. Moreover, we provide the results of additional simulation experiments showing the practical benefit of the proposed multi-stage stochastic programming model as compared to a simpler multi-period deterministic model.

ABSTRACT. Electric Vehicles (EV) are having more and more impact on urban systems, both when driving (e.g. noise and pollution) and when charging (potential impact on the electrical grid). For the grid, the flexibility of EV charging – in time of operation and level of power – makes it a great actor in "Demand Response" mechanisms (thanks to charging scheduling) which is an emerging field in "smart grids". For this reason, there is a need to design incentive mechanisms.

ABSTRACT. This work addresses the problem of nding an ecient strategy for charging an electric vehicule (EV). This problem can be solved by a greey approach (i.e. charging the vehicule as soon as it arrives) but the more EVs penetrate the car market, the more this strategy might overload the electric distribution grid at commuting hours. To overcome this, one can postpone the charging during night or during low prices period of the electric market. Inspired to work of [1], we developed an algorithm that optimizes the charging strategy to minimize the charging cost based on day-ahead prices. It has to : - satisfy different constraints : operating constraints, battery power level, quality of service for the car owner...; - operate in an uncertain environment : unknown car departure or arrival time, unknown house consumption... We detail the problem as a Markov decision process under uncertainty. We applied an A3C reinforcement learning algorithm (as described in [2]) to learn an effcient charging strategy. We use a variation of the algorithm using LSTM [3] to cope with temporal consistency of decisions. We present some preliminary results on real data showing the improvement of the strategy over the learning iterations.

ABSTRACT. Electronic array-antennas offer new possibilities for optimization over traditional rotating antennas, thanks to bi-dimensional beam-forming and beam-steering capabilities. Modern radars must perform multiple tasks simultaneously. Minimization of the search time-budget frees resources for target tracking, identification, environment analysis among others... Design of radar covers can be viewed as an optimization problem: minimization of the search time-budget under detection constraints. This problem is closely related to combinatorial spatial problems, such as set covering, and can be solved by integer programming methods.

ABSTRACT. We aim to design a radar network which maximizes the detection probability of the worst threatening trajectory from a source to a target. In game theory, we represent it as a non-cooperative zero-sum game: a first player chooses a setting for the network, and the other player chooses a trajectory from an admissible class with full information over the network. The players' objective is respectively to maximize and minimize the path cost.

In comparison with [1], we added blindness maps depending on the distance and the radial speed, which are functions of internal parameters of the radars that can be optimized: PRI (Pulse Repetition Interval) and frequency. We also take into account RCS (Radar Cross Section) and a complex geometry with DEM (Digital Elevation Map) and Earth curvature.

The profile of the cost function with regard to the direction of movement is non-convex, which is significant only with a curvature penalization. For that, we chose the Dubins model, in which the curvature radius is bounded. The computation of optimal trajectories is performed with a specialized variant of the Fast-Marching algorithm [2]. We showcase new phenomena such as spiraling threatening trajectories, trajectories dodging radars through their blind distances, and hiding from valley to valley.

The optimization of the radar network (positioning and internal parameters) is a difficult problem (non-convex, non-differentiable), solved with optimization algorithms such as CMA-ES.

ABSTRACT. The CMA-ES algorithm is a continuous domain, stochastic optimization algorithm addressing problems in a derivative-free setting. The quadratic space and time complexity of the method limits its applicability for problems with increasing dimensionality.

We present alternatives of CMA-ES that have been recently proposed for problems in large dimensions and outline the principal ideas of each approach. The performance of these variants and of the gradient based L-BFGS algorithm in terms of runtime is compared in different experimental settings. For this, we use a newly introduced benchmarking testbed for black-box optimizers, which is also outlined and extends the standard COCO BBOB testbed in dimensions up to 640.

Optimization techniques find extensive application in radar technologies. One domain is the multiple transmit multiple receive (MIMO) radar technology, that requires the use of phase-coded waveforms with low correlation properties, e.g. for good spatial resolution and interference rejection. We focus on this application formulated as a black-box optimization problem, where we compare the obtained results of methods mentioned above. We also sketch another radar application for phase-only pattern synthesis of phased-array antennas.

ABSTRACT. Cloud Data Centers (CDCs) are data centers that adopt the cloud computing paradigm, according to which applications are virtualized and run in a number of distributed physical servers that may be located very distant from each other, even in distinct continents. Studies on the optimal management of CDCs have commonly focused just on minimizing the total power consumption, deciding how to switch on and o the physical servers composing the CDCs depending on the workload. However, switching the servers causes large temperature transitions in the hardware, which can sensibly increase the failure rates of components and lead to an increase in the maintenance costs. In this work, we propose a new optimization model for managing CDCs that jointly minimizes the power consumption and the maintenance costs, derived through a material-based fatigue model that expresses the costs incurred to repair the hardware, as a consequence of the variation over time of the server power states. A major objective has been to investigate what is the impact of the maintenance costs on the total costs and whether it is beneficial to leverage the tradeoff between electricity consumption and maintenance costs. Computational results, obtained over a set of scenarios from a real CDC, show that the original heuristic that we propose to solve the optimization model largely outperforms two benchmark algorithms, which instead either target the load balancing or the energy consumption of the servers.

ABSTRACT. Nowadays, the cloud service providers are focusing much of importance in having data centers (DC) with ecient energy consumption so as to reduce the energy costs which is a major contributor of their total operational costs. In this context, we design a capacity planning framework (CPF) for energy-ecient DCs. Technically, the proposed CPF performs an integrated oine VM placement (VMP) solution. The VMP is the way toward selecting which virtual machines (VMs) ought to be found at each physical machine (PM) in a DC. The VMP problem can be seen as a variant of the binpacking problem [1]. The individual PMs can be considered as bins. Similarly, the VMs can be considered as objects to be packed into these bins. Several formulations have been proposed to model and solve the bin-packing problems, most of which are based on the Linear Programming (LP) techniques [1]. In this work, the proposed VMP placement approach is formalized as a Two-Objective Integer Linear Programming model (TOILP). The TOILP model aims at maximizing the number of hosted virtual machine requests while the energy consumption is reduced through the minimization of the used physical machines number. To the best of our knowledge, this is the first attempt in which such objectives are considered in a CPF. To assess the performances of the proposed solution, extensive simulation scenarios has been established in a homogeneous DC, considering additional realistic VMs' [2] and PMs' configurations. Through the simulation results, it was observed that with the proposed CPF, the number of used PMs can be minimized with a gain up to 15% [3] while meeting all the VM resource requirements, compared to a one which only considered the satisfaction of the VMs.

ABSTRACT. Managing the energy consumption of data centers can be done using virtualization and turning on and off Virtual Machines in order to reduce the energy consumption while guaranteeing a given quality of service. We study hysteresis policies in which activation and deactivation decisions of Virtual Machines depend on thresholds on the system load. This work aims at computing the optimal thresholds once costs and performance parameters are fixed.

ABSTRACT. In this talk we first establish a review of existing results concerning most critical elements of single objective optimization problems. We will present some motivations, definitions, and results concerning most critical elements of multiobjective optimization problems.