ABSTRACT. I will recall the fundamental role of nonsmooth automatic differentiation as the core learning mechanism in modern AI. I will then show how a recent idea we developed with E. Pauwels — «Conservative gradients»— helps to understand fundamental phenomena, such as the convergence of learning phases in deep learning, the optimization of learning parameters, the nonsmooth cheap gradient principle, or the differentiation of algorithms.

ABSTRACT. In this presentation, we consider the chemostat system with n species, one limiting substrate, and mutations between species. Such a system is commonly used in population models to describe the behavior of n consumers competing for a same resource (the substrate). We shall first give stability properties of the resulting dynamical system. In particular, global stability at the unique equilibrium point (apart the wash-out) is proved for a constant (sufficiently small enough) dilution rate value. Next, we will introduce feedback controls called auxostats in biotechnology. These controllers allow the regulation of the substrate concentration in the process. We prove that such feedback controls globally stabilize the resulting closed-loop system near a desired equilibrium point. This result is obtained by combining the theory of asymptotically autonomous systems and an explicit computation of solutions to the limit system. The performance of such controllers will be finally illustrated on an optimal control problem of Lagrange type which consists in maximizing the production of species over a given time period with respect to the dilution rate chosen as control variable.

ABSTRACT. Vector-borne diseases have a significant impact on human health worldwide, accounting for 17% of all infectious diseases. These diseases can be caused by parasites, bacteria or viruses and can be transmitted by different types of vectors, such as ticks, fleas or mosquitoes. In this talk, we present the study of optimal vector release strategies for vector-borne diseases such as dengue, Zika, chikungunya and malaria. Two techniques are considered:

-The sterile insect technique (SIT), which involves the release of sterilised male vectors among wild vectors in order to disrupt their reproduction.

- The use of Wolbachia (currently used mainly for mosquitoes), which consists on the release of vectors infected with a bacterium that limits their ability to transmit the pathogen in order to replace the wild population.

In each case, an epidemiological model including humans and vectors is considered. The temporal dynamics of the populations is modelled by a system of ordinary differential equations. However, to simplify the study and given that the duration of the releases is very small compared to the duration of the experiment, the releases are considered instantaneous. Mathematically they are represented by linear combinations of Dirac measures with positive coefficients determining their intensity. We model the question of the optimal mosquito release strategy by an optimal control problem that we solve numerically using ad hoc algorithms, based on writing first-order optimality conditions characterising the best combination of Dirac measures. The objective expressed by the cost function is to reduce the amount of human infections in a fixed time horizon. We then discuss the results obtained, focusing in particular on the complexity and efficiency of the optimal controls and comparing the strategies obtained for the two techniques.

ABSTRACT. A mathematical model describing the process of generating energy from household waste treatment is analyzed. This is in fact an upgraded version of the earlier model introduced in [1]. It is a three-dimensional nonlinear system that depicts the concept of transforming household waste stored in a landfill into energy that flows to a user's network. More precisely, the state of the system describes at a broad scale a process of generating energy E by treating a quota of a waste stock x through K-valorization units (that may also consume a part of the produced energy for their functioning). Our main objective is to maximize the energy produced and transmitted to the user's network. In particular, we investigate the issue of determining an optimal investing strategy that monitors the deployment of treatment plants. Using Pontryagin's maximum principle (PMP, based on the current value-Hamiltonian framework [2]), we characterize, over a fixed time-window [0, T], the optimal investment that maximizes the produced energy while limiting the overall costs. In addition, the efficiency of the suggested optimal control strategy is illustrated throughout this talk using a direct optimization method (implemented in Bocop: optimal control solver).

ABSTRACT. We introduce and analyze a new finite-difference scheme, that we call $\theta$-scheme, for solving monotone second-order mean field games. These games consist of a coupled system of the Fokker-Planck and the Hamilton-Jacobi-Bellman equation. We use the $\theta$-method for discretizing the diffusion terms, that is to say, we approximate them with a convex combination of an implicit and an explicit term. On contrast, we use an explicit centered scheme for the first-order terms. Assuming that the running cost is strongly convex and regular, we first prove the monotonicity and the stability of our $\theta$-scheme, under a CFL condition. Taking advantage of the regularity of the solution of the continuous problem, we estimate the consistency error of the $\theta$-scheme. Our main result is a convergence rate of order $\mathcal{O}(h^r)$ for the $\theta$-scheme, where $h$ is the step length of the space variable and $r \in (0,1)$ is related to the H\"older continuity of the solution (and some of its derivatives) of the continuous problem.

ABSTRACT. We present a stochastic control problem where the probability distribution of the state is constrained to remain in some region of the Wasserstein space of probability measures. Re-formulating the problem as an optimal control problem for a (linear) Fokker-Planck equation, we derive optimality conditions in the form of a mean-field game system of partial differential equations. The effect of the constraint is captured by the presence, in this system, of a Lagrange multiplier which is a non-negative Radon measure over the time interval. Our main result is to exhibit geometric conditions on the constraint, under which this multiplier is bounded and optimal controls are Lipschitz continuous in time. As a consequence we prove that the stochastic control problem with constraints in law, arises as limit of control problems for large number of interacting agents subject to almost-sure constraints.

ABSTRACT. We study a Mean Field Game (MFG) model arising in Economics where each agent chooses its position in space and its level of human capital- i.e. the skills aimed at use in production possessed by each individual- and interacts with the other agents through the human capital. The main goal consists in studying the effect of spatial interaction terms (called in Economics spatial spillovers) on the abilities of each individual, due to the proximity, in terms of spatial distance, of other individuals. The resulting MFG system has a highly non standard structure, that is, a non-separable Hamiltonian and a non-monotone cost. In the talk we describe the economic model, we prove existence to the associated MFG system by a fixed point argument, and we provide some numerical experience. This is a joint work with F. Gozzi (LUISS, Italy) C. Ricci (Pisa, Italy), and G. Zanco (LUISS, Italy). The economic model has been developed through contributions by G. Fabbri (CNRS Grenoble), D. Fiaschi (Pisa, Italy), F. Gozzi (LUISS, Italy).

ABSTRACT. Polynomial optimization methods often encompass many major scalability issues on the practical side. Fortunately, for many real-world problems, we can look at them in the eyes and exploit the inherent data structure arising from the input cost and constraints.

The first part of my talk will focus on the notion of "correlative sparsity", occurring when there are few correlations between the variables of the input problem.

The second part will present a complementary framework, where we show how to exploit a distinct notion of sparsity, called "term sparsity", occurring when there are a small number of terms involved in the input problem by comparison with the fully dense case.

At last but not least, I will present a very recently developed type of sparsity that we call "ideal-sparsity", which exploits the presence of equality constraints.

Several illustrations will be provided on important applications arising from various fields, including robustness of deep networks, quantum entanglement, optimal power-flow, and matrix factorization ranks.

ABSTRACT. The moment-sum-of-squares (moment-sos) hierarchy is one of the most celebrated and widely applied methods for approximating the minimum of an n-variate polynomial over a feasible region defined by polynomial (in)equalities. A key feature of the hierarchy is that it can be formulated as a semidefinite program of size polynomial in the number of variables n. Although this suggests that it may therefore be computed in polynomial time, this is not necessarily the case. Indeed, as O'Donnell and later Raghavendra & Weitz show, there exist examples where the sos-representations used in the hierarchy have exponential bit-complexity. We study the computational complexity of the sos-hierarchy, complementing and expanding upon earlier work of Raghavendra & Weitz. In particular, we establish algebraic and geometric conditions under which polynomial-time computation is possible. As this work is still ongoing, our results should be treated as preliminary.

ABSTRACT. Self-concordant barrier interior point methods (IPMs) solve minimization problems over a polyhedron with linear cost $x \mapsto \langle c, x \rangle$ by considering instead the cost function $x \mapsto f(x) + \eta \langle c, x \rangle$ for a parameter $\eta > 0$ and $f$ a self-concordant barrier. Self-concordant barriers are strictly convex functions which blow up at the border of the feasible set and whose Hessian locally does not change much. For each $\eta > 0$, the parametric problem has a unique minimizer $x(\eta)$, and the curve $\eta \mapsto x(\eta)$ is the \textit{central path}. As $\eta \to +\infty$, the central path converges to an optimal value of the initial linear problem. IPMs follow the central path to find an approximated solution.

One of the major open problems in computational optimization, known as Smale's ninth problem, asks to find a \emph{strongly polynomial algorithm} for linear programming. In this context, making any substantial progress on the understanding of the worst-case number of iterations performed by IPMs is a notorious open question.

Our contribution generalizes the result in \cite{ref2} which shows that IPMs based on the logarithmic barrier are not strongly polynomial. The authors study parametric families of linear programs with their central paths by looking at their \emph{tropicalization}, \textit{i.e.}~the limit of their log-image. The tropicalization of the central paths is a piecewise linear curve called the tropical central path.

We present our results from \cite{ref3} which show that {\emph no} self-concordant barrier IPM is strongly polynomial. To achieve this, we show that any self-concordant barrier behaves essentially like the logarithmic barrier. We use this to prove that IPMs draw polygonal curves in a multiplicative neighborhood of the central path whose log-limit coincides with the tropical central path, independently of the barrier. We provide an explicit parametric linear program that falls in the same class as the Klee--Minty counterexample, \textit{i.e.}~whose feasible set is a combinatorial cube. Its tropical central path is composed of $2^n-1$ segments. When the parameter is large, the log-image of the trajectory of the IPM approximates the tropical central path, meaning that the IPM must perform that many iterations, thus breaking strong polynomiality.

ABSTRACT. The deterministic p-center problem (PCP) is one of the most studied facility location problems in the literature of location science. It consists in installing p centers out of m available sites, assigning n clients to these p centers in order to minimize the radius which corresponds to the maximum distance or travel time between a client and its closest open site. The incorporation of uncertainty in the (PCP) has important applications in emergency logistics problems. Two approaches can be considered depending on whether the client allocations to the centers are made before or after the uncertainty is revealed. The first case corresponds to single-stage problems while the second case leads to two-stage problems in which the client allocations are recourse variables. In this context, most of the articles have focused on heuristic approaches.

We study the exact solution of the two-stage robust p-center problem (RPCP2) in which the uncertainty on the node demands and the travel times are modeled by box uncertainty sets. The (RPCP2) aims to find a set of p sites for which its regret of the worst-case scenario is minimal. Since a box uncertainty set contains an infinite number of scenarios, the evaluation of the regret is a major challenge when solving the (RPCP2). To make it tractable, we prove that only a finite subset of scenarios can be considered without losing optimality. We use this result to propose three robust formulations based on different deterministic MILP formulations of the (PCP) from the literature. To solve these reformulations, we introduce a column-and-constraint generation algorithm and a branch-and-cut algorithm. Moreover, we highlight how they can be adapted to optimally solve the single-stage problem (RPCP1) for which no exact resolution method has been previously introduced. We present a numerical study to compare the performances of our algorithms on randomly generated instances and a case study from the literature with up to 52 demand nodes. We solve 80 instances for several values of p and number of sites.

ABSTRACT. In the glass industry, visual and thermal properties of the glass sheets are obtained via the deposit of very thin layers of different materials. A standard way to perform this step is the use of a “magnetron,” in which the materials are transferred from cathodes to the sheets using a magnetic field. Different materials can achieve a given property of the glass. Since the cathodes are very expensive, their activation and replacement have to be carefully decided to keep the production costs and the waste of materials low. Due to the complexity of the physical process, the consumption of the cathodes is partly uncertain, which makes finding the best activation and replacement decisions a highly challenging task. In an accurate modeling, the decisions have to be sequentially taken, leading to a multi-stage robust optimization problem. To tackle the over-conservativeness of the current industrial practice, we propose to solve this problem within the framework of finite adaptability, introduced by Bertsimas and Caramanis [1]. It consists in splitting the uncertainty set into finitely many parts and in assigning to each part a constant recourse decision. Recently, Subramanyam et al. [2] proposed an exact method able to solve efficiently finite adaptable two-stage robust problems. First, we show how to reformulate the studied problem in its two-stage version within the setting of Subramanyam et al. Preliminary results clearly demonstrate that finite adaptability brings a significant improvement upon the non-adaptable robust solutions, which are already better than the industrial solutions. Second, to deal with the full problem, we propose a multistage extension of the method by Subramanyam et al. Its theoretical and experimental validation is currently under investigation. Bertsimas and Caramanis have given evidences that in many situations finite adaptability provides a good approximation to the “complete” adaptability. Our last contribution is a theorem in the line of their work, showing that finite adaptability approximates asymptotically complete adaptability under mild continuity conditions.

[1] D. Bertsimas and C. Caramanis. Finite adaptability in multistage linear optimization. IEEE Transactions on Automatic Control, 55(12):2751–2766, 2010. [2] A. Subramanyam, C. E. Gounaris, and W. Wiesemann. K-adaptability in two-stage mixedinteger robust optimization. Mathematical Programming Computation, 12(2):193–224, 2020.

ABSTRACT. The rising share of electrical vehicles leads to challenging optimization problems, like for instance, the operational management of a charging station. The charging station manager has for instance to choose how to allocate power to the various vehicles plugged at each time, while accounting for several potentially contradictory objectives: cost, satisfaction of mobility needs... In a deterministic setting, this problem can be modelled as a linear programming problem. In an uncertain context, it becomes much more involved to model and solve. One of the most impactful and difficult source of uncertainty for operational management of a charging station is the randomness of arrival and departure dates for electrical vehicles. In our linear programming models, this amounts to consider uncertainty for binary-valued parameters u(v,t), where u(v,t) is equal to 1 when vehicle v is plugged at time t, and 0 else.

In this work, we aim at designing a stochastic optimization model for the management of a charging station, under uncertainty on arrival and departure dates, with several objectives. First, we want to account for real-time recourse. Second, we want to enforce non-anticipacivity of our decisions. Third, we wish to design an optimization model which can be solved in reasonable time, even for instances of moderate sizes (few tens of vehicles and time steps), to be consistent with the industrial objectives.

We argue that many classical methods do not satisfy these requirements due to curse ofdimensionality with respect to state dimension (dynamic programming), number of time steps (multi-stage stochastic programming) or noise (scenario based models). Moreover, some stochastic optimization paradigms require to probabilize the uncertainty, which could be costly if statistical models have to be adapted to every single charging station, and dynamically updated.

Robust optimization approach is a more suitable candidate for which uncertainty is easier to model through the specification of an uncertainty set. In order to ensure real-time recourse to avoid over-conservatism, we assume the recourse decisions (power allocation to each plugged vehicle) are in parametric form (feedback), and show that their simplest consistent form is quadratic with respect to the uncertain parameters u(v,t), and non-anticipativity can be ensured by properly constraining our feedback function parameters. We thus obtain a min-max problem, where the lower level problems are non-convex quadratic programming problems with binary variables. Nontheless, we show that by using linear relaxations of the lower level problems (i.e., by enlarging the uncertainty set), and duality-based reformulation techniques, we can recover a tractable single level linear programming problem (with additional dual variables), which solution is feasible and hopefully performant for the original robust optimization problem. Numerical results support the study.

ABSTRACT. We study the linear convergence of the primal-dual hybrid gradient method, also know as Vu-Condat method. After a review of current analyses, we show that they do not explain properly the behavior of the algorithm, even on the most simple problems. We thus introduce the quadratic error bound of the smoothed gap, a new regularity assumption that holds for a wide class of optimization problems including strongly convex-concave saddle point problems and linear programs. Equipped with this tool, we manage to prove tighter convergence rates.

Then, we show that averaging and restarting the primal-dual hybrid gradient allows us to leverage better the regularity constant. We also propose an adaptive way of setting the restarting instants. Numerical experiments on linear and quadratic programs, ridge regression and image denoising illustrate the findings of this work. In particular, we show that on some problems, the rate of convergence of the new method can be faster by orders of magnitude.

ABSTRACT. We study the variational inference problem of minimizing a regularized Rényi divergence over an exponential family, and propose a relaxed moment-matching algorithm, which includes a proximal-like step. Using the information-geometric link between Bregman divergences and the Kullback-Leibler divergence, this algorithm is shown to be equivalent to a Bregman proximal gradient algorithm. This novel point of view allows us to exploit the geometry of our approximate model while using stochastic black-box updates, and allows us to prove strong convergence guarantees including monotonic decrease of the objective, convergence to a stationary point or to the minimizer, and convergence rates. These new theoretical insights lead to a versatile, robust, and competitive method, as illustrated by numerical experiments.

ABSTRACT. In a distributed optimization setting, we present an asynchronous variant of the Bregman proximal-gradient method of Bauschke-Bolte-Teboulle, which only requires relative smoothness of the objective functions. We discuss its convergence, even with arbitrarily long delays. We illustrate its behavior on distributed Poisson inverse problems.

ABSTRACT. The Newton method is an iterative method to solve smooth non-linear optimization problemsor equations. For unconstrained optimization problems, under some convexy and regularity conditions, local quadratic convergence can be established. Global convergence can be furtherobtained by using a line search procedure.

In this work [1], we generalize this method to convex stochastic control problems, wherethe decision variable is a stochastic process. We show that the Newton step can be crucially interpreted as the solution of an auxiliary Linear-Quadratic stochastic control problem which approximates the original problem around the current iterate, and which can be explicitly solved,by introducing a Riccati Backward Stochastic Differential Equation. This gives a practical and efficient way to compute the Newton step, by solving only (Backward) Stochastic Differential Equations, using for instance Monte-Carlo regression techniques.

Regarding the theoretical convergence properties, we show that, even under strong regularity assumptions, Lispchitz-continuity of the second order derivative does not hold in general, which prevents us from establishing local quadratic convergence of the method in the space of square integrable processes. To overcome this issue, we show that under some boundedness assumptions,the problem can be posed in an alternative vector space in which the second-order derivative becomes Lipschitz continuous: the space of essentially bounded stochastic processes. Using an adaptation of the line-search procedure, we design a globally convergent algorithm in the space of bounded processes, with quadratic convergence in a neighbourhood of the optimal solution,and with arithmetic convergence outside.

The algorithm is used to solve a stochastic controlproblem aiming at controlling a large population of batteries in order to help balancing the electricity grid, using a methodology proposed in [2].

References [1] E. Gobet & M. Grangereau, Newton method for stochastic control problems. To appear in SIAM Journal on Control and Optimization (SICON), 2021. [2] E. Gobet & M. Grangereau, Federated stochastic control of numerous heterogeneous energy storage systems, 2021

ABSTRACT. Airline companies use revenue management techniques in their daily operations to a great extent, but they frequently overlook ancillaries revenue. Ancillaries are non-core products, such as on-board (i.e. Wi-Fi, additional baggage) or post-flight (i.e. insurance, car rental) services, that account for an increasing share of airlines revenue. Most of the time, these products have a quasi-zero marginal cost, so the production cost of one additional item is negligible. An important aspect of ancillaries is that they are lost if they are not bought. For instance, food will eventually expire, and services like additional baggage are lost when the flight departs. Hence, in this context, it's very meaningful to make use of revenue management. These additional products are also seen as very important by some customers. As a consequence, the latest developments in the airline industry have the objective of pushing their purchase. Ancillaries can be combined into a single commodity called bundle, which will offer a set of ancillaries at a single price. This bundling strategy increases demand and overall profit by sacrificing the individual ancillary profit margin. In particular, web sales are well adapted to the proposal of a few bundles to the client.

The main challenge of this approach lies in the pricing and assortment of the bundles offered for sale. The difficulty arises from the structure of the problem, since only 3 or 4 bundles of a combinatorially large number can be proposed to purchase. An important aspect to take into account is the diversity of the proposed bundles. Ideally, we want to propose to customers a set of diverse and relevant bundles. Another challenge that we face is the destroy ancillary value effect. This effect occurs if we don't take into consideration that ancillaries can be sold individually at a later time. This loss of value is linked to the observation that customers' price sensitivity is lower at check-in time than at selling time. It could be because they have forgotten how much they have already spent or due to unforeseen circumstances when they purchased the ticket.

In this work, we present a revenue management model based on a Nested Multinomial Logit customer choice model that does not destroy ancillaries value. Therefore, we introduce a two stage booking process where we take into account the selling time and the check-in time.

Numerical experiments highlight the efficiency and diversity of the suggested bundles of the proposed model.

ABSTRACT. The Standard Quadratic Programming (StQP) problem~\cite{Bom1998} consists of finding a (global) minimizer of a quadratic form over the standard simplex. Hence, it can be written in the following form: \begin{eqnarray}\label{eq:StQP} \mbox{\textbf{StQP}}: \left\{\begin{array}{l} \min f(x)= x^T Q x\\ \ \mbox{s.t.}\ e^T x = 1, x \geq 0, \end{array} \right. \end{eqnarray} where $Q \in \re^{n \times n}$ is a symmetric matrix and $e$ being the $n$-dimensional vector of ones. %and $\Delta$ is the standard simplex in a Euclidean space $\re^n$, i.e., %\begin{align}\label{eq:setS} %\Delta = \{ x\in \re^n: x\geq 0,\: e^T x = 1\}, %\end{align} %with $e$ being the $n$-dimensional vector of ones. %StQP~\eqref{eq:StQP} has an optimal solution, as its objective function is continuous and its feasible set is nonempty and compact.

%The name was coined by Bomze in~\cite{Bom1998}, where it is shown that a wide number of applications can be recast as an StQP~\cite{BoEi,BDKQ,BoKl,BoLT,MoSt}, including the so-called Maximum Clique Problem that is quite relevant in computer vision, pattern recognition and robotics, portfolio selection problems, and testing matrix copositivity.

Finding a global optimal solution to StQP~\eqref{eq:StQP} when $Q$ is an indefinite matrix, or even giving a certificate of global optimality for a locally computed solution, is known to be NP-hard~\cite{Gondzio2021}.

We introduce a new sequential algorithm for the StQP, which exploits a formulation of StQP as a Linear Program with Linear Complementarity Constraints (LPLCC). The algorithm is finite and guarantees at least in theory a $\delta$-approximate global minimum for an arbitrary small $\delta$, which is a global minimum in practice. The sequential algorithm has two phases. In Phase~1, Stationary Points (SP) with strictly decreasing objective function values are computed. Phase~2 is designed for giving a certificate of global optimality for the last SP computed in Phase~1. Two different Nonlinear Programming Formulations for LPLCC are proposed for each one of these phases, which are solved by efficient enumerative methods. Computational experiments with a number of test problems from known sources indicate that the two-phase sequential algorithm is, in general, efficient in practice. Furthermore, the algorithm seems to be an efficient way to study the copositivity of a matrix by exploiting an StQP with this matrix.

ABSTRACT. We consider the quadratic optimization problem that consists in minimizing a quadratic function of mixed-integer and bounded variables under quadratic inequalities. We devise a global solution method that mixes interval branch-and-bound methods with quadratic convex reformulation. We moreover make the whole method rigourous in order tu certify the computed optimal solution value. We illustrate the results of the obtained method and focus on the impact of rigor.

ABSTRACT. In [1], we introduce a new approach to apply the boosted difference of convex functions algorithm (BDCA) for solving non-convex and non-differentiable problems involving difference of two convex functions (DC functions). Supposing the first DC component differentiable and the second one possibly non-differentiable, the main idea of BDCA is to use the point computed by the DC algorithm (DCA) to define a descent direction and perform a monotone line search to improve the decreasing the objective function accelerating the convergence of the DCA. However, if the first DC component is non-differentiable, then the direction computed by BDCA can be an ascent direction and a monotone line search cannot be performed. Our approach uses a non-monotone line search in the BDCA (nmBDCA) to enable a possible growth in the objective function values controlled by a parameter. Under suitable assumptions, we show that any cluster point of the sequence generated by the nmBDCA is a critical point of the problem under consideration and provide some iteration-complexity bounds. Furthermore, if the first DC component is differentiable, we present different iteration-complexity bounds and prove the full convergence of the sequence under the Kurdyka-Lojasiewicz property of the objective function. Some numerical experiments show that the nmBDCA outperforms the DCA such as its monotone version.

ABSTRACT. Some airlines use the preferential bidding system to construct the schedules of their pilots. In this system, the pilots bid on the different activities and the schedules that lexicographically maximize the scores of the pilots according to their seniority are selected. A sequential approach to solve this maximization problem is natural: the problem is first solved with the bids of the most senior pilot; then it is solved with those of the second most senior without decreasing the score of the most senior, and so on. The literature admits that the structure of the problem somehow imposes such an approach.

The problem can be modeled as an integer linear lexicographic program. We propose a new exact method, which relies on column generation for solving its continuous relaxation. To design this column generation, we prove that bounded linear lexicographic programs admit ``primal-dual'' feasible bases, and we show how to compute such bases efficiently.

Another contribution on which our exact method relies consists in the extension of standard tools for resource-constrained longest path problems to their lexicographic versions. This is useful in our context since the generation of new columns is modeled as a lexicographic resource-constrained longest path problem.

Numerical experiments show that this new method is already able to solve industrial instances provided by Air France, with up to 100 pilots. By adding a last ingredient in the resolution of the longest path problems, which exploits the specificity of the preferential bidding system, the method achieves for these instances computational times that are compatible with operational constraints.

ABSTRACT. A coflow identifies a group of datacenter network flows sharing a common goal [1]. In data- intensive computing frameworks it represents the data transfer phase acting as synchronization barrier between successive computation phases occurring in different physical nodes. The Coflow Completion Time (CCT) is the time by which the last flow of a coflow is completed. Minimizing the average CCT of a coflow batch is NP-hard and inapproximable below a factor 2, with best to date deterministic approximation ratio of 4 [2,3]. While minimizing the average CCT increases the rate of computing jobs dispatched in a datacenter, it entails potential unfairness among different flows due to starvation. Fairness has thus been studied in the context of coflow scheduling: in this context, the efficiency/fairness tradeoff balances the system performance, i.e., the average CCT, versus the individual coflow performance. The standard notion of coflow fairness is defined by using the notion of coflow progress, i.e., by guaranteeing a minimum resource allocation to coflows scheduled concurrently [4]. Any further performance optimization, e.g., minimization of average CCT or maximization of port utilization, is usually pursued on top of this baseline constant non-pre-emptive rate allocation. In this work we introduce a fairness framework where the notion of progress corresponds to the average rate granted to a coflow while in service. It is controlled via the inverse metric, e.g., the slowdown, which measures the additional delay on the data transfer time of a coflow compared to isolation, i.e., when a coflow is scheduled alone in the datacenter fabric. A slowdown constraint provides a single parameter control able to strike the trade-off between average CCT and the individual coflow slowdown. The first contribution we discuss is a fully polynomial time algorithm, namely MPS (Minimum Primal Slowdown): it provides an accurate estimation of the minimum feasible slowdown for a batch of coflows. Second, we introduce the CoFair scheduler to extend the family of the primal-dual algorithms [3,5]: by using the output of MPS, it produces a primal-feasible σ- order. Finally, a simple order-preserving work-conserving transmission policy realizes the rate allocation for the actual coflow scheduling. CoFair is tested against state of the art coflow schedulers demonstrating more effective in attaining a flexible performance-fairness tradeoff [6]. [1] M. Chowdhury and I. Stoica, “Coflow: A networking abstraction for cluster applications,” in Proc. of ACM HotNets, Redmond, Washington, 2012. [2] S. Ahmadi, S. Khuller, M. Purohit, and S. Yang, “On scheduling coflows,” Algorithmica, vol.82, no.12, dec. 2020. [3] S. Agarwal, S. Rajakrishnan, A. Narayan, R. Agarwal, D. Shmoys, and A. Vahdat, “Sincronia: Near-optimal network design for coflows,” in Proc. of ACM SIGCOMM, 2018. [4] W. Wang, S. Ma, B. Li, and B. Li, “Coflex: Navigating the fairness-efficiency tradeoff for coflow scheduling,” in Proc. of IEEE INFOCOM, Atlanta, GA, USA, 1–4 May 2017. [5] M. Mastrolilli, M. Queyranne, A. S. Schulz, O. Svensson, and N. A. Uhan, “Minimizing the sum of weighted completion times in a concurrent open shop,” Operations Research Letters, vol. 38, no. 5, 2010. [6] F. De Pellegrini, et al. “Fair Coflow Scheduling via Controlled Slowdown,” arXiv, arXiv:2208.06513, 2022.

ABSTRACT. Medical evacuation is a key element in a military operation. This study proposes a new way to dimension medical evacuation (MEDEVAC), such as wounded transportation and medical teams. Each wounded type has its own medical protocol, with different steps and due dates. Dimensioning MEDEVAC corresponds to find the proper number of transport teams and medical teams that allows a scheduling saving every one.

The formalism from literature called Synchronous Dataflow Graphs (SDF) ~\cite{ref1} is a Petri-net capable of representing a deterministic flow of tokens on a graph. The SDF formalism is a timed event graph with production and consumption weights on the arcs. Each task in the SDF graph is defined by an execution time. A task is executed if the number of tokens present on each of its incoming arcs is greater or equal than the corresponding consumption weights. At the end of its execution, this task produces on its outgoing arcs a number of tokens equal to the corresponding weights.

Our new formalism enriches the Synchronous Dataflow Graphs model with colored tokens, which depict the severity of the wounded and the medical teams they must go, and with a constraint on weights such that no loss or gain of tokens happens after a task's execution. Other properties were studied: dimensions of tasks which allow multiple execution of the same task with different starting time.

Our new formalism inherits from SDF properties, which allows a simple estimation of consistency and liveness ~\cite{ref2}. Consistency determines whether a graph is well constructed. Liveness determines the absence of deadlock during its execution. This formalism also provides various approaches to determine a lower bound of the throughput.

This presentation introduces the Colored-Conservative SDF (Co2SDF) formalism, the consistency verification and the possibilities to evaluate and optimize a MEDEVAC with a Co2SDF.

\begin{thebibliography}{00}

\bibitem{ref1}

Edward Ashford Lee and David G Messerschmitt, Static scheduling of synchronous data flow programs for digital signal processing, \emph{IEEE Transactions on computers}, 100, 1, 24--35,1987.

\bibitem{ref2}

Abir Benabid-Najjar, Claire Hanen, Olivier Marchetti and Alix Munier-Kordon, Periodic schedules for bounded timed weighted event graphs, \emph{IEEE Transactions on Automatic Control}, 57, 5, 1222-1232, 2012.

\end{thebibliography}

ABSTRACT. Image reconstruction plays an important role in a number of modern activities, such as experimental verification of radiotherapy. Mathematically, image reconstruction can be viewed as a least squares problem, but with the caveat that the `optimal' solution is not necessarily the cleanest image. Several approaches have been suggested to deal with this issue. In this talk, we review some of these approaches and present the results of comprehensive numerical testing comparing different approaches.

ABSTRACT. This work proposes a novel energy conservation measure that optimizes the planning of heating and cooling systems for tertiary sector buildings. It consists of a model-based predictive control approach that employs a grey-box model built from the building and weather data that predicts the building heat load and indoor temperature. Different from classical optimization approaches where the discretized differential algebraic equations are integrated into the optimization formulation, our model is calibrated using black-box multiobjective optimization, which allows for decoupling the predictive model from the optimization problem, thus having more flexibility and reducing the total computational time. Moreover, rather than requiring the angle of solar radiation, solar orientation and solar masks to calculate the radiation data, our approach requires only a simple model of the solar irradiance. The calibrated model is then used by heating and cooling optimization strategies that aim at reducing the energy consumption of the building in the next day while satisfying the indoor thermal constraints. Results from a case study of a commercial building during heating and cooling seasons show that the proposed approach was able to yield up to 12% of energy savings.

ABSTRACT. In simulation-based optimization, one is often faced with constraints that stem from physical processes, and are expressed under the form of differential equations. Recent interest in machine learning architectures based on differential equations has generated renewed interest for this class of problems. Indeed, it gave rise to several complex optimization formulations where the dynamics play a prominent role and the objective function can be viewed as the result of an expensive procedure, typically not directly available to the optimizer.

In this talk, we investigate constrained optimization problems where the objective function is the result of a blackbox simulation, but the dynamics expressed in the constraints are available as a white box. We provide an algorithmic framework that is equipped with theoretical guarantees, even when the objective function cannot be accessed directly, and stochastic estimates are available instead. We also illustrate the performance of our algorithm on task involving neural architectures inspired by differential equations.

ABSTRACT. The \emph{non-dominated sorting genetic algorithm II} (NSGA-II)~\cite{DebPAM02} is the most intensively used multi-objective evolutionary algorithm (MOEA) in real-world applications. Only very recently, the first mathematical runtime analysis for this algorithm was conducted~\cite{ZhengLD22}. In this talk, we report on the follow-up work conducted in the second author's M2 internship. In~\cite{DoerrQ22ppsn}, we conducted the first runtime analysis on a bi-objective benchmark having multimodal objectives. It shows that the NSGA-II admits very similar performance guarantees as those shown earlier~\cite{DoerrZ21aaai} for the simple GSEMO algorithm. Our experimental investigation finds that with crossover, the NSGA-II becomes much faster than the GSEMO on this benchmark. We give a mathematical proof for this speed-up in~\cite{DoerrQ22arxivcrossover}. Building on a careful analysis of the population dynamics, in~\cite{DoerrQ22arxivLB}, we prove the first lower bounds on the runtime of the NSGA-II. They show that the previous analysis of the mutation-only version of the NSGA-II on the \omm and \ojzj benchmarks are asymptotically tight.

This work is part of the PGMO-funded project \emph{Understanding and Developing Evolutionary Algorithms via Mathematical Runtime Analyses} (PI: Benjamin Doerr). The M2 internship of the second author was funded by this PGMO project.

ABSTRACT. With the recent successes of Deep Learning on a wide range of applications, automatic design of neural networks has gained attention. Automated Deep Learning aims to decrease the need for human expertise by automatically designing an optimal architecture and choose the right hyper-parameters for a given problem. This optimization problem is characterized by an expensive, black-box and noisy loss function, associated with a mixed-variable search space. In this work, we propose a graph-based search space for the automatic design of neural networks. We defined each network as a Directed Acyclic Graph (DAG) where the nodes represent the operations. Our search space is flexible compared to those from the literature. Each node can take the value of various typical neural network operations as well as state-of-the-art layers such as the self-attention from the Transformer model. The graph itself (size, connections) and the nodes can be optimized. Moreover, the search space encompasses the architectures defined by a single DAG but also architectures containing DAGs and perhaps other parameters to optimize. We can then define search spaces generalizing more complex architectures. Based on this search space, we implemented a genetic algorithm with specific evolutionary operators efficient with the DAG encoding. We designed these operators to alternatively and/or hierarchically find the best architecture and hyper-parameters. To speed up the optimization, we took advantage of the HPC clusters owned by Electricite De France (EDF). We applied our optimization scheme to several short-term load forecasting use cases from EDF, with different timelines, load signals and frequencies. In every use case, we found in less than 72 hours of computation, neural networks able to challenge or even outperform the handcrafted models designed by EDF experts.

ABSTRACT. Optimization problems are omnipresent in different scientific disciplines, as well as in numerous real world scenarios. Very often, these problems have to be treated as a black box (e.g., too complex to be solved analytically, unavailable derivatives, etc). The only information we have access to are specific solution candidates and their qualities, i.e., the pairs of (x, f(x)) that we can use to guide the search towards a good estimate of the optimal solution.

Given a wide range of black-box optimization algorithms (most notably, but not limited to, population-based iterative heuristics) designed for different problems in mind, a meta-optimization problem arises: how does one select the best suited algorithm for a specific problem? This is well known as the algorithm selection (AS) problem. At first, AS has relied on inherently biased human expert knowledge; automating this process has thus turned out to be a crucial step in gaining efficiency and performance. However, only knowing what the problem at hand is can often be insufficient, as different approaches might be more suitable depending on different instances of the same problem; this has paved a way towards per-instance algorithm selection.

To automatically recommend a good algorithm for a given problem instance, we first need to characterize the instance, which is typically done by extracting landscape features using exploratory landscape analysis tools, again only based on what we have access to in a black-box setting: solution candidates and their qualities. Naturally, this induces a computational overhead cost that we cannot afford in most real world applications, where each function evaluation requires expensive simulations or physical experiments.

We therefore propose a different perspective in which we take into account how instance landscapes look from the point of view of the optimization algorithm itself, and we build an AS pipeline on top of those locally observed features. To this end, we coin the term per-run algorithm selection for a process in which we extract landscape features from the samples observed by a default algorithm, and use that knowledge to recommend the best suited algorithm for the remainder of the search (until the total budget is exhausted).

We present first results in this direction for a portfolio of different black-box optimization heuristics, but more importantly, we show that this approach can be generalized to other scenarios, such as selection of acquisition functions in Bayesian optimization, in which on-the-fly choices lead to performance gains.

ABSTRACT. For large-scale optimization, popular approaches such as the ADMM and the Progressive Hedging algorithm exploit separable structures by solving in parallel individual sub-problems which are then coordinated by performing a simple algebraic step (typically, a projection onto a linear subspace)

While parallelism is the strength of all Douglas-Rachford-like splitting methods, their weak points are the adjustment of certain proximal parameter and the lack of a fully implementable stopping test. These difficulties, which date back to Spingarn's method of partial inverses, stem from the very design of these approaches, which were created to find zeroes of operators.

We discuss how to endow some splitting methods with an optimization perspective that introduces knowledge about the objective function throughout the iterative process. The resulting new family of methods à la bundle incorporates a projective step to coordinate parallel information while allowing the variation of the proximal parameters and the construction of a reliable stopping test. A Bundle Progressive Hedging algorithm, derived from the general theory, illustrates the interest of proposal. Credit to co-authors will be given during the talk

ABSTRACT. In mathematical epidemiology, the transmission of a disease is evaluated in compartments which correspond to a partition of the population. This partition es determined by the different states of the disease. We work with optimal control problems which consist in minimizing the maximum over a time interval of a state for compartmental dynamics. This work has been motivated by the so-called overcrowding problem, which is a significant issue for hospitals. More precisely, the objective is to minimize the peak of infections in order to keep the health system below saturation levels.

In the particular case of the SIR dynamic, a control affecting the transmission rate is introduced. We will present the optimal solution we called NSN strategy by null-singular-null. We compare this strategy to other in literature.

In a more general case, we present numerical solution using reformulations and Bocop solver. Taking advantage of the analytical solution of the SIR model, we evaluate the numerical performance of these reformulations for this kind of problems.

ABSTRACT. The last decades witnessed a considerable progress in experimental and clinical immunology as well as in modeling the immune system dynamics. The progress in cancer dynamics modeling motivated researchers to apply control approaches in order to schedule cancer treatments using optimal control strategies. Many works have been carried out in order to design cancer treatment protocols using mathematical models. One of the main complexities of such models is the presence of different types of uncertainties, which remains less considered in the literature.

This presentation will focus on the importance of parametric uncertainties considerations in the design of optimal cancer drugs protocoles. Therefore, it will firstly adress the use of the moment optimization framework for solving optimal control problems. The latter being appropriate for the use of stochastic parametric uncertainties, it’s efficiency will be investigated for cancer drugs schedules design. Secondly, this presentation will adress a new probabilistic certification framework, that is based on chance-constrained optimization, in order to design optimal control profiles in the presence of parametric uncertainties.

ABSTRACT. The dynamical system analyzed in this work represents a simplified version of a bioprocess used in scientific research and in the chemical and pharmaceutical industries for the production of value-added chemical compounds. The model is two-fold. On one side, it considers a "self- replicator" bacterial model representing the main cellular functions involved in growth and chemical production: metabolism and production of proteins [2]. On the other hand, it models a continuous bioprocess, a production scheme ocurring in a bioreactor that allows steady-state operation for long periods of time, avoiding shutdown for cleaning and maintenance. The study of steady-state equilibria, that is connected with the use of constant controls, is crucial and related to the turnpike phenomenon in optimal control (e.g., when maximising dynamically the growth the bacteria). A typical situation is indeed as follows [1]: optimising the equilibrium wrt. to the constant control provides a hyperbolic equilibrium of the underlying Hamiltonian singular dynamics described by Pontrjagin maximum principle. This is a strong motivation to study the stability properties of the equilibria the system. These equilibria are parameterised by the control, and their existence is described by a series of strict polynomial inequalities in terms of the system parameters. Their local stability can be assessed by means of the well-known Routh-Hurwitz stability criterion that yields an additional inequality. By leveraging the degree pattern of the specific allocation resource, we simplify significantly the first steps of the so-called "Cylindrical Algebraic Decomposition" algorithm [3] and are able to prove local stability of the equilibria of interest for a dense subset of the parameters, including the control.

References [1] J.-B. Caillau, W. Djema, J.-L. Gouzé, S. Maslowskaya, J.-B. Pomet, Turnpike property in optimal microbial metabolite production, J. Optim. Theory Appl., 194:375–407, 2022. [2] N. Giordano, F. Mairet, J.-L. Gouzé, J. Geiselmann, H. de Jong, Dynamical allocation of cellular resources as an optimal control problem: Novel insights into microbial growth strategies, PLoS Computational Biology, 2016. [3] RAGlib – A library for real solving polynomial systems of equations and inequalities. www- polsys.lip6.fr/ ̃safey/RAGLib/distrib.html

ABSTRACT. HiGHS has emerged in the past couple of years as the world's best open-source linear optimization software. Its interior point (IPM) solver for linear programming (LP) problems was written by Lukas Schork. Recently, this was identified by the PyPSA power system analysis team as being vastly more efficient than other open-source solvers for their energy system modelling problems. Indeed, for many problems, the performance of the HiGHS IPM solver was comparable with that of Gurobi. The absence of satisfactory open-source LP solvers has been a serious limitation on the development of open-source energy modelling systems that are crucial for stakeholders who cannot afford commercial software, such as non-governmental organizations, early-stage companies, and government ministries in lower income countries.

As well as introducing HiGHS, this talk will discuss why its IPM solver performs so much better than other open-source solvers for energy system modelling problems, why the HiGHS IPM solver is wholly uncompetitive with Gurobi for some instances, and the plans for addressing this.

ABSTRACT. Has nonlinear programming become boring? Indeed, most of the theoretical developments have been made during the 1980s and 1990s, culminating in the release of easy-to-use nonlinear optimization solvers (Ipopt, Knitro) now widely adopted by the community. There is a consensus that interior-point method (IPM) is among the most robust methods to solve nonlinear problem. IPM solves a nonlinear problem by solving its Karush-Kuhn-Tucker (KKT) equations using a homotopy method, leading to the resolution of one linear system at each iteration of the algorithm. Hence, in a large-scale setting, all the computational complexity is delegated to the sparse linear solver being employed under the hood. That component is the principal limiting factor when it comes to solve very large-scale nonlinear problems (with more than 1 millions variables and constraints), as commonly encountered in the optimization of energy systems. In this talk, we present a method to harness the structure of the nonlinear problem (degrees of freedom, potential arrowhead structure) to alleviate the limitation of interior-point in the very large-scale regime. The method has been implemented in MadNLP, a flexible interior-point solver developed entirely in Julia. We demonstrate the numerical capability of MadNLP in a HPC setting by bringing a practical way to accelerate IPM on Graphical Processing Units (GPU), paving the way to use IPM on future exascale supercomputers. We assess the performance of the method on various use-cases coming from the optimization of energy systems, notably (1) nonlinear problems with graph-structure (optimal powerflow) (2) nonlinear problems with a two-stage stochastic structure (stochastic optimal powerflow) (3) nonlinear problems with a dynamic structure (linear-quadratic MPC).

ABSTRACT. This presentation deals with Optimal Control Problems (OCPs) with pure state and input constraints. One of the available approaches to solve these problems consists of adapting Interior Point Methods (IPMs) to state and input constrained OCPs [1, 2, 3]. However, adapting IPMs to OCPs is not straightforward and has not been wholly performed. Indeed, to be complete, this adaptation requires proving two things. Firstly, the optimal trajectories of the penalized problem strictly satisfy the constraints. Secondly, it requires establishing the convergence of the method to a point satisfying the first-order optimality conditions, that is, to prove the convergence of state, control, adjoint state, and constraint multipliers in function space. In the case of control constraints, several works have proven convergence of control, state, and adjoint state when using IPMs and have provided a primal and a primal-dual solving algorithm. In addition, previous work has proven the convergence of control and state variables for pure state constraints but not for the adjoint state or the constraint multipliers. The contribution of this work is to fill this gap by proving both interiority of the penalized trajectories and convergence of control, state, adjoint state, and constraint multipliers. To do so, sufficient conditions on penalty functions guaranteeing the interiority of local optimal solutions are exhibited, and we prove that logarithmic functions satisfy these conditions. In addition, we prove that the derivative of the penalty functions associated with any local optimal solutions satisfies a uniform boundedness property. Using some standard compactness argument with these uniform boundedness properties allows to prove strong, weak, or weak * convergence, depending on the case, of these derivatives to the constraints multipliers. Then, the convergence of the adjoint state stems from the convergence of the state, control, and constraint multipliers. Finally, this paper provides a primal-dual solving algorithm based on Two Point Boundary Value Problems solver.

ABSTRACT. The optimal power flow (OPF) problem concerns the problem of determining the operational efficiency of power systems through the objective of minimising operating costs, subject to power flow constraints and demands given throughout a transmission network. OPF problems have a high level of practical importance, and a vast amount of research has studied them in the last 50 years.

OPF problems are typically modelled as mathematical programs with a large number of non-linear constraints, such as those involving bilinear terms, which are notoriously difficult to solve. Recently, a number of relaxation approaches have been presented for solving non-linear programs with bilinear terms, such as binary expansions and McCormick envelopes. These approaches allow solvers to find under- and over-estimators for the bilinear terms in the non-linear constraints.

The advantage of binary expansions is that the accuracy of the estimators can be set by the user. However, increasing accuracy leads to a significant increase in the number of complicating binary variables present in the expansion. Hence, efficiently solving more accurate relaxations is key to finding solutions to OPF problems effectively. Decomposition techniques which mitigate the effect of binary variables, such as combinatorial Benders decomposition (CBD), have been shown to be effective for problems with similar structures.

We first compare different linear relaxations of OPF problems, showcasing how CBD can be used to find arbitrarily accurate solutions efficiently. Afterwards, we apply the relaxation approach to a multi-network OPF problem, where nodes in different networks can be connected. This leads to a tree-based model, where each node of the tree is solved using decomposition.

ABSTRACT. The moment-SOS hierarchy has proved relevant to address AC-OPF (Alternative Current - Optimal Power Flow) problems. However, obtaining the convergence of the hierarchy may require to go beyond the first step d=1 of the sequence of SDP relaxations (e.g. up to d=3 in some references), and thus to solve semidefinite programs whose size grows exponentially with the value of d. Thus, the application of the hierarchy to large scale problems (with n > 10.000 variables) remains a challenging task.

In this talk, we present some prospective techniques to tackle further steps (d > 1) of the hierarchy for large scale problems. In particular, we consider exploiting the sparsity of the problem, and its possible combination with decomposition techniques.

ABSTRACT. The robust solution of large-scale nonlinear programming (NLP) is still a challenging task today, notably when it comes to guarantee the iterates remains feasible with relation to a set of nonlinear constraints (potentially nonconvex). It is well-known that one can guarantee feasibility by using a subtle arrangement of line-search or trust-region techniques, but feasibility may be difficult to maintain if the problem is highly nonconvex. In this work, we propose to maintain feasibility by exploiting spectral information about the Jacobian of the nonlinear constraints. Using a smooth approximation of the min operator, one can constrain the minimum eigenvalue to be greater than a given threshold. As a result, we can force the algorithm to remain feasible with some controllable margin. We reuse the results of Lewis and Sendov (2001) to evaluate the first- and second-order derivatives of the spectral constraints, allowing us to cast the model as a generic nonlinear problem. We present numerical results on the popular optimal power flow problem (OPF), where we use the newly introduced spectral constraints to guarantee we satisfy strictly the physical constraints of the problem. We show the method is numerically tractable.

ABSTRACT. This talk is concerned with mean field games in which the players do not know the repartition of the other players. First a case in which the players do not gain information is studied. Results of existence and uniqueness are discussed. Then, a case in which the players observe the payments is investigated. A master equation is derived and partial results of uniqueness are given for this more involved case.

ABSTRACT. In this talk, I will present how Mean Field Games allow to scale multi-agent systems to an infinite number of agents, and how Reinforcement Learning can scale Mean Field Games in terms of model complexity. I will first explain what are Mean Field Games and present different definitions and their corresponding settings. I will then introduce two algorithms to find Nash equilibrium in Mean Field Games: Fictitious Play (FP) and Online Mirror Descent (OMD), that both converge to the Nash equilibrium under the monotonicity condition. Finally, I will present how these two algorithms can be adapted to model-free environments using Deep Reinforcement Learning. This problem was particularly challenging because FP and OMD both require summing or averaging quantities, a difficult operation with non-linear functions such as Neural Networks.

ABSTRACT. Recently there is a rising interest in the research of mean-field optimization, in particular because of its role in analysing the training of neural networks. In this talk, by adding the Fisher Information (in other word, the Schrodinger kinetic energy) as the regularizer, we relate the mean-field optimization problem with a so-called mean field Schrodinger (MFS) dynamics. We develop a free energy method to show that the marginal distributions of the MFS dynamics converge towards the unique minimizer of the regularized optimization problem. We shall see that the MFS is a gradient flow on the probability measure space. Finally we propose a Monte Carlo method to sample the marginal distributions of the MFS dynamics.

ABSTRACT. We consider the subgradient method with constant step size for minimizing locally Lipschitz semi-algebraic functions. In order to analyze the behavior of its iterates in the vicinity of a local minimum, we introduce a notion of discrete Lyapunov stability and propose necessary and sufficient conditions for stability.

ABSTRACT. We consider a stochastic minimization problem in the nonsmooth and nonconvex setting which applies for instance to the training of deep learning models. A popular way in the machine learning community to deal with this problem is to use stochastic gradient descent (SGD). This method combines both subgradient sampling and backpropagation, which is an efficient implementation of the chain-rule formula on nonsmooth compositions. Due to the incompatibility of these operations in the nonsmooth world, SGD can generate artificial critical points in the optimization landscape which does not guarantee the convergence of the method. We will explain in this talk how the model of Conservative Gradients is compatible with subgradient sampling and backpropagation, allowing to obtain convergence results for nonsmooth SGD. By means of definable geometry, we will emphasize that functions used in machine learning are locally endown with geometric properties of piecewise affine functions, allowing to interprete the chain-rule as a projection formula. In this setting, chain-ruling nonsmooth functions and sampling subgradients output conservative gradients, justifying the use of SGD in deep learning. As an additional consequence of the definable setting, subgradient sequences are generally gradient sequences, and artificial critical points are hardly attained when performing SGD in practice.

ABSTRACT. In the first part of this work, We refine the so-called projection formula of Bolte et al. to the case of locally Lipschitz continuous functions definable in a o-minimal structure, by establishing a Lipschitz-like condition on the (Riemannian) gradients of two adjacent stratas.

In the second part of this work, we analyze the stochastic subgradient descent (SGD) in a neighborhood of an active strict saddle, a notion that was introduced in the work of Davis and Drusvyatskiy. An active strict saddle is a Clarke critical point of a function f, that is lying on a manifold M such that: i) f varies smoothly on M ii) f restricted to M it admits a direction of negative curvature, iii) f varies sharply outside of M. Davis and Drusvyatskiy have previously shown that generically (in the sense of linear perturbations) the only Clarke critical points that a semialgebraic (or more generally definable), weakly convex function might have are local minima and active strict saddles.

We introduce two additional assumption on the active manifold: the Verdier and the angle condition. Under these, and assuming that the perturbation sequence of the SGDis omnidirectional, we show that the probability to converge to an active strict saddle is zero. Furthermore, we show that both of our conditions are generic in the class of weakly convex, semialgebraic functions. As a consequence, we can interpret our results as the fact that the SGD on a generic, semialgebraic and weakly convex function converges to a local minimum.

ABSTRACT. According to the International Energy Agency (IEA), the buildings and construction sector accounted for 36% of final energy use and 39% of energy and process-related carbon dioxide (CO2) emissions in 2018. Almost 40% of CO2 emissions come from the building industry and space heating is the most important end-use in the residential sector (68% in Europe).

The current energy transition towards low-carbon and renewable sources (with more electric uses, as heat pumps and electric vehicles) is expected to come from the aggregation of basic low voltage power supply grids, known as microgrids, which associate local energy production with storage capacities and energy consumers. Buildings equipped in such way are then expected to become 'Smart' actors in terms of local energy management and service supply inside their walls but also outside (through exchanges with their neighborhood). In terms of energy, Smart buildings could actively dispatch its power generation, control storage capacities and also manage its energy demand. Indeed, efficiency could be gained through consumption reduction and self-consumption rate could increase through techniques such as load shifting, to better match the demand with the renewable power generation. The role of the occupants, that is the consum'actors, could be key to achieve these goals.

The service improvement thanks to Smart Buildings should be evaluated by cost-benefit analyses through performance indicators. These indicators can be of different nature : economic (for instance through the electrical bill change), environmental (the carbon foot print of the used electricity), related to services to the grid (such as load shedding during peak periods) or to well-being measures (such as user satisfaction, comfort or new user services). Data availability is key in order to be able to optimise for a given service, and this data can be of different types: weather forecasts, energy consumption, energy production, room temperature, the grid energy mix, to mention a few.

In order to enable the development and test of new optimisation solutions for Smart Buildings, the Energy4Climate center builds building-size demonstrators of different kinds (tertiary, residential, 100% electric, electric-thermic) and collects multi-parameter data that are available for the scientific and industrial communities.

ABSTRACT. The problem of designing and sizing a hydrogen injection pipeline network is to find both a network topology and the diameter dimensions of each pipe section for hydrogen distribution. We consider that the diameters of the pipes can only take a few possible values. This realistic assumption allows us to reformulate the degree-6 used polynomial model into a quadratic one whose continuous relaxation is moreover a convex optimization problem. We implement the global solution method based on our discrete-diameter models, together with heuristics. We then comprare our results with existing solution methods on randomly generated instances and on a case study based on realistic data.

ABSTRACT. We consider the problem of jointly optimizing the daily production planning and energy supply management of an industrial complex, with manufacturing processes, renewable energies and energy storage system. It is naturally formulated as a mixed-integer multistage stochastic problem. This problem is challenging for three main reasons: there is a large number of time steps (typically 24), the renewable energy are uncertain and uncontrollable, and we need binary variables modeling hard constraints. We discuss various solution strategies, in particular Model Predictive Control, Dynamic Programming, and heuristics based on the Stochastic Dual Dynamic Programming algorithm.

We compare these strategies on two variants of the problem: with or without day-ahead energy purchases. Without day-ahead purchases, although it is clear taking uncertainties into consideration is a necessity, MPC has the best results, beating stochastic heuristics. However, with day-ahead purchases and therefore decisions at t=0 impacting the whole horizon, stochastic heuristics perform better than MPC.

ABSTRACT. Cancer exhibits intra-tumor heterogeneity of gene expression that can be profiled using single-cell RNA sequencing technology. ’Precision’ treatment strategies attempt to exploit this heterogeneity for treatment recommendations tailored to patient-specific heterogeneity patterns (signatures). Identification of treatment-relevant signatures requires their observation across multiple patients. However, inter-patient heterogeneity makes direct integration of gene expression data across patients, and subsequent identification of signatures in the integrated dataset, unreliable. For the case of glioblastoma, Neftel et al have circumvented this problem using an approach that first heuristically determines a candidate set of patient-specific signatures, and then identifies similar candidates across patients, to obtain biologically validated results. We expand and improve upon this approach using: (i) a statistically well-founded approach to score general signatures in individual patients, (ii) robust ranks instead of normalized RNA expression levels, (iii) a straightforward extension of the patient-specific score to a global score across all patients, and (iv) a gradient structure of the global score function. Since the problem is highly complex, we use randomized search. Our greedy algorithm identifies local optima by starting 10,000 times from a random seed signature, and then iteratively moving to the best signature in its neighborhood, using an efficient partial evaluation of the objective function, until convergence. Out of the seven 50-gene signatures that we found in the glioblastoma dataset of 7,167 genes and 6,855 cells, five had a high degree of similarity to all eight of the metaprograms from the original study, with some of our signatures including genes from two metaprograms simultaneously. Gene set enrichment analysis of one of the remaining two signatures identified a specific neuronal process, reasonably expected in the context of glioblastoma. Our approach is free from ad-hoc thresholds, simple, transparent, robust, and can yield biologically plausible results. We believe that our approach allows for bypassing the need for a complicated process of generating individual signatures in every sample and their further integration, hence being a useful addition to the tool-belt of methods tackling the signature search problem.

ABSTRACT. Although many high-grade serous ovarian cancer (HGSOC) patients initially respond to chemotherapy, eventually patients will develop recurrent disease and resistance to the treatment. On a cellular level, the resistance may be explained by a sub-population of cells within the highly heterogeneous tumor tissue that survives the effects of the drug and subsequently propagates. It is assumed that the survival of this cell sub- population is due to the activity or inhibition of specific cellular processes, which are characterized by the expression of a particular set of genes. Thanks to the recently established single-cell RNA-seq (scRNA-seq) technologies, the analysis of the inter- and intra-tumoral heterogeneity has become possible at the level of individual cells, enabling the identification and transcriptional characterization of different sub-populations of cells. Our objective is to identify the mechanisms of chemotherapy resistance. To address this challenge, we have a unique scRNA-seq dataset of 57 samples from 42 patients before and after chemotherapy. The key challenges are that 1) we do not have resistance labels for the cells and 2) we do not know which genes may be implicated in the resistance. Therefore, our strategy is 1) to find general patterns of gene expression (gene signatures) across different sub-populations of cells (describing several cellular processes of the iden- tity and state of the cells) and 2) from this set of gene signatures, identify those that underlie the resistance mechanisms. For our first objective, we have selected non-negative matrix factorization (NMF) to decompose the gene expression of each cell into a linear combination over latent factors, each latent factor representing a gene signature. To circumvent the prominent problem of batch effects between samples, we applied NMF to each sample individually, and merged the samples only on the basis of the inferred gene signatures. Preliminary results on our data show several signatures that are unique to samples, as well as some signatures that are found across different samples. In our future work, we hope to be able to associate some of these signatures to chemotherapy resistance.

ABSTRACT. Many cancer treatments are administered at a high dose, and are initially successful, but eventually fail as the tumor becomes resistant. When a cure is unlikely, an alternative is to try to simply stabilize the tumour, through a moderate, time-varying, patient specific dose. The hope is to diminish both treatment toxicity and selection for resistance to treatment, allowing us to control the tumor for a longer time. Some experimental results are promising.

This may be understood theoretically through mathematical models with treatment sensitive and treatment resistant cells. If these cells are in competition, killing too many sensitive cells may boost the growth of resistant cells, and lead to a shorter survival time. In simple models, if resistant cells are fully resistant, and death occurs when the tumor reaches a critical size, it may be shown that treatments aiming at tumor stabilization are superior to more aggressive treatments. This follows from simple comparison principles. However, more realistic variants of this problem would benefit from an optimal control approach. We will discuss some of these variants, with the hope of generating collaborations.

ABSTRACT. The long-term operation of hydro and thermal power stations can be cast as a multistage stochastic optimization program—as in the case of the Brazilian interconnected power system. This illustrative problem setting commonly features seasonal periodicity arising from climate and/or energy consumption patterns. The traditional approach is to consider a large but finite horizon, which breaks this property. We propose an infinite horizon approach, allowing for further exploitation of the periodicity in the solution process. Additionally, this setting avoids terminal boundary conditions and introduces questions regarding the limit behavior of solutions over time. We present solution algorithms for such problems and showcase numerical examples, including simple deterministic examples that nonetheless exhibit complex behavior.

ABSTRACT. In this talk, we present a novel optimization dispatch of grid-connected mini-grids with joint chance constraints. In the context of sub-Saharan Africa, operators of grid-connected mini-grids face the following uncertainties: intermittent renewable energies supply, demand, frequency and duration of main-grids blackouts . These uncertainties pose new challenges to the classical power system's operation tasks. We present an optimal dispatch with an islanding strategy, which makes sure that the operator uses planned reserves during the entire period of the main grid outage, such that customers enjoy a given p-reliability level of electricity supply. Results and comparison with deterministic approaches are presented. Also open problems and future work with probabilistic bilevel programs will be discussed.

ABSTRACT. The problem of reservation in a large distributed system is analyzed via a new mathematical model. A typical application is a station-based car-sharing system which can be described as a closed stochastic network where the nodes are the stations and the customers are the cars. The user can reserve the car and the parking space. In the paper, we study the evolution of the system when the reservation of parking spaces and cars is effective for all users. The asymptotic behavior of the underlying stochastic network is given when the number N of stations and the fleet size increase at the same rate. The analysis involves a Markov process on a state space with dimension of order N^2. It is quite remarkable that the state process describing the evolution of the stations, whose dimension is of order N, converges in distribution, although not Markov, to a non-homogeneous Markov process. We prove this mean-field convergence. We also prove, using combinatorial arguments, that the mean-field limit has a unique equilibrium measure when the time between reserving and picking up the car is sufficiently small. This result extends the case where only the parking space can be reserved.

ABSTRACT. In order to understand better how and why crossover can be beneficial in evolutionary optimization, we consider the BoundMax benchmark. This generalization of the well-known OneMax function has increasing fitness only as long as the number of 1-bits does not exceed a given parameter B and is negative, otherwise. The unique optimum is the string of B 1-bits followed by n−B 0-bits. The literature gives a runtime bound of Θ(n^2) for the (1+1) EA on this benchmark. Part of the difficulty when optimizing this problem lies in having to improve individuals that already have the correct number of 1s and 0s but not at the correct positions. Then, to progress, two bits must flip in the same iteration. The experimental literature proposes balanced operators, preserving the number of 1s, as a remedy. We analyze how balanced mutation and balanced crossover operators in different settings optimize the problem. With the best combination of operators, we achieve an optimization time in O(n log n). As an additional contribution we analyze and discuss different balanced crossover operators from the literature.

ABSTRACT. The cardinality of a vector is the number of its non-zero elements. In numerous fields such as machine learning, finance or energy, it is proved very useful to control the cardinality of decision vector in related sparse optimization problems. Several approaches have been proposed to deal with such very challenging nonconvex problems. Replacing cardinality by the convex approximation based on $L_1$ norm leads to tractable problems but solutions obtained are far from the expected one. In addition, this classical approach fails over the probability simplex.

We propose an novel approach to cardinality for dealing with sparse optimization problems \cite{EDF_Report} based on nonconvex continuous approximations of cardinality guarantying a more precise sparsity level than convex relaxation. Defining a family of ratios of norms, we prove that its limit is a lower bound of cardinality involving Shannon entropy. The result can also be stated by using Jensen's inequality. The related optimization problems can be solved by using nonlinear solvers like IPOPT. Some numerical experiments on the Finance Index Tracking problem illustrate the efficiency of the proposed approach.

ABSTRACT. Many modern optimization problems involve in the objective function solution mappings or optimal-value functions of other optimization problems. In most/many cases, those solution mappings and optimal-value functions are nonsmooth, and the optimal-value function is also possibly nonconvex (even if the defining data is smooth and convex). Moreover, stemming from solving optimization problems, those solution mappings and value-functions are usually not known explicitly, via any closed formulas.

We present an approach to regularize and approximate solution mappings of fully parametrized convex optimization problems that combines interior penalty (log-barrier) with Tikhonov regularization. Because the regularized solution mappings are single-valued and smooth under reasonable conditions, they can also be used to build a computationally practical smoothing for the associated optimal-value function and/or solution mapping.

Applications are presented to two-stage (possibly nonconvex) stochastic programming, and to a certain class of hierarchical decision problems that can be viewed as single-leader multi-follower games.

ABSTRACT. Introduced in the 1970's by Martinet for minimizing convex functions and extended shortly afterward by Rockafellar towards monotone inclusion problems, the proximal point algorithm turned out to be a viable computational method for solving various classes of optimization problems, in particular with nonconvex objective functions.

We propose first a relaxed-inertial proximal point type algorithm for solving optimization problems consisting in minimizing strongly quasiconvex functions whose variables lie in finitely dimensional linear subspaces. The method is then extended to equilibrium problems where the involved bifunction is strongly quasiconvex in the second variable.

Possible modifications of the hypotheses that would allow the algorithms to solve similar problems involving quasiconvex functions are discussed, too. Numerical experiments confirming the theoretical results, in particular, that the relaxed-inertial algorithms outperform their 'pure' proximal point counterparts, are provided, too.

ABSTRACT. Commonly, decomposition and splitting techniques for optimization problems strongly depend on convexity. Implementable splitting methods for nonconvex and nonsmooth optimization problems are scarse and often lack convergence guarantees. One exception is the Progressive Decoupling Algorithm (PDA)[Rockafellar, R.T. Set-Valued Var. Analysis 27, 863--893 (2019)], which has local convergence should convexity be elicitable. In this work we furnish the PDA with a descent-test and extend the method to accommodate a broad class of nonsmooth optimization problems with non-elicitable convexity. More precisely, we focus on the problem of minimizing the difference of convex and weakly convex functions over a linear subspace. This framework allows covering, in particular, a family of stochastic programs with nonconvex recourse and statistical estimation problems for supervised learning.

ABSTRACT. A variety of problems in modern applications of optimization require a selection of a 'sparse' solution, a vector with preferably few nonzero entries. Such problems may originate from very different applications in computational statistics, signal or image processing or compressed sensing, finance, machine learning and discrete optimal transport, to mention just a few. Sparse approximation problems are often solved with dedicated and highly specialised first-order methods of optimization.

In this talk I will argue that these problems may be very efficiently solved by the more reliable optimization techniques which involve some use of the (inexact) second-order information as long as this is combined with appropriately chosen iterative techniques of linear algebra, such as for example methods from the Krylov-subspace family. Two particular classes of methods, the Newton Conjugate Gradient and the Interior Point Method will be interpreted as suitable homotopy type approaches and will be applied to solve problems arising from: compressed sensing, multi-period portfolio optimization, classification of data coming from functional Magnetic Resonance Imaging, restoration of images corrupted by Poisson noise, classification via regularized logistic regression, and discrete optimal transport. In all these cases, the performance of the proposed methods will be compared against competitive first-order methods. Computational evidence will be provided to demonstrate that specialized second-order methods compare favourably and often outperform the cutting-edge first-order methods.

For more details, see:

[1] V. De Simone, D. di Serafino, J. Gondzio, S. Pougkakiotis, and M. Viola, Sparse approximations with interior point methods, SIAM Review (accepted 24 Nov 2021). https://arxiv.org/abs/2102.13608

[2] F. Zanetti and J. Gondzio, A sparse interior point method for linear programs arising in discrete optimal transport, Tech Report (22 June 2021). https://arxiv.org/abs/2206.11009