Search

We study a tropical linear regression problem consisting in finding the best approximation of a set of points by a tropical hyperplane. We establish a strong duality theorem, showing that the value of this problem coincides with the maximal radius of a Hilbert's ball included in a tropical polyhedron. We also show that this regression problem is polynomial-time equivalent to mean payoff games. We illustrate our results by solving an inverse problem from auction theory. In this setting, a tropical hyperplane represents the set of equilibrium prices. Tropical linear regression allows us to quantify the distance of a market to the set of equilibria, and infer secret preferences of a decision maker.

International audience

Whereas interior point methods provide polynomial-time linear programming algorithms, the running time bounds depend on bit-complexity or condition measures that can be unbounded in the problem dimension. This is in contrast with the simplex method that always admits an exponential bound. We introduce a new polynomial-time path-following interior point method where the number of iterations also admits a combinatorial upper bound $O(2^{n}n^{15}\log n)$ for an n-variable linear program in standard form. This complements previous work by Allamigeon, Benchimol, Gaubert, and Joswig (SIAGA 2018) that exhibited a family of instances where any path-following method must take exponentially many iterations. The number of iterations of our algorithm is at most $O(n^{15}\log n)$ times the number of segments of any piecewise linear curve in the wide neighborhood of the central path. In particular, it matches the number of iterations of any path following interior point method up to this polynomial factor. The overall exponential upper bound derives from studying the max central path’, a piecewise-linear curve with the number of pieces bounded by the total length of 2n shadow vertex simplex paths. From the existence of a line segment in the wide neighborhood we derive strong implications on the structure of the corresponding segment of the central path. Our algorithm is able to detect this structure from the local geometry at the current iterate, and constructs a step direction that descends along this segment. The bound $O(n^{15}\log n)$ that applies for arbitrarily long line segments is derived from a combinatorial progress measure. Our algorithm falls into the family of layered least squares interior point methods introduced by Vavasis and Ye (Math. Prog. 1996). In contrast to previous layered least squares methods that partition the kernel of the constraint matrix into coordinate subspaces, our method creates layers based on a general subspace providing more flexibility. Our result also implies the same bound on the number of iterations of the trust region interior point method by Lan, Monteiro, and Tsuchiya (SIOPT 2009).

We define and analyze the notion of variational Wardrop equilibrium for nonatomic aggregative games with an infinity of players types. These equilibria are characterized through an infinite-dimensional variational inequality. We show, under monotonicity conditions, a convergence theorem enables to approximate such an equilibrium with arbitrary precision. To this end, we introduce a sequence of nonatomic games with a finite number of players types, which approximates the initial game. We show the existence of a symmetric Wardrop equilibrium in each of these games. We prove that those symmetric equilibria converge to an equilibrium of the infinite game, and that they can be computed as solutions of finite-dimensional variational inequalities. The model is illustrated through an example from smart grids: the description of a large population of electricity consumers by a parametric distribution gives a nonatomic game with an infinity of different players types, with actions subject to coupling constraints., arXiv admin note: substantial text overlap with arXiv:1806.06230

We study polynomial systems with prescribed monomial supports in the Cox rings of toric varieties built from complete polyhedral fans. We present combinatorial formulas for the dimensions of their associated subvarieties under genericity assumptions on the coefficients of the polynomials. Using these formulas, we identify at which degrees generic systems in polytopal algebras form regular sequences. Our motivation comes from sparse elimination theory, where knowing the expected dimension of these subvarieties leads to specialized algorithms and to large speed-ups for solving sparse polynomial systems. As a special case, we classify the degrees at which regular sequences defined by weighted homogeneous polynomials can be found, answering an open question in the Gr\"obner bases literature. We also show that deciding whether a sparse system is generically a regular sequence in a polytopal algebra is hard from the point of view of theoretical computational complexity.

We consider a revenue maximization model, in which a company aims at designing a menu of contracts, given a population of customers. A standard approach consists in constructing an incentive-compatible continuum of contracts, i.e., a menu composed of an infinite number of contracts, where each contract is especially adapted to an infinitesimal customer, taking his type into account. Nonetheless, in many applications, the company is constrained to offering a limited number of contracts. We show that this question reduces to an optimal quantization problem, similar to the pruning problem that appeared in the max-plus based numerical methods in optimal control. We develop a new quantization algorithm, which, given an initial menu of contracts, iteratively prunes the less important contracts, to construct an implementable menu of the desired cardinality, while minimizing the revenue loss. We apply this algorithm to solve a pricing problem with price-elastic demand, originating from the electricity retail market. Numerical results show an improved performance by comparison with earlier pruning algorithms.

The symmetrized tropical semiring is an extension of the tropical semifield, initially introduced to solve tropical linear systems using Cramer's rule. It is equivalent to the real tropical hyperfield, which has been used in the study of tropicalizations of semialgebraic sets. Polynomials over the symmetrized tropical semiring, and their factorizations, were considered by Quadrat. Recently, Baker and Lorscheid introduced a notion of multiplicity for the roots of univariate polynomials over hyperfields. In the special case of the hyperfield of signs, they related multiplicities with Descarte's rule of sign for real polynomials. We investigate here the factorizations of univariate polynomial functions over symmetrized tropical semirings, and relate them with the multiplicities of roots over these semirings. We deduce a Descartes' rule for ``signs and valuations'', which applies to polynomials over a real closed field with a convex valuation and an arbitrary (divisible) value group. We show in particular that the inequality of the Descartes' rule is tight when the value group is non-trivial. This extends to arbitrary value groups a characterization of Gunn in the rank one case, answering also to the tightness question. Our results are obtained using the framework of semiring systems introduced by Rowen, together with model theory of valued fields.

Using order structures in a proof assistant naturally raises the problem of working with multiple instances of a same structure over a common type of elements. This goes against the main design pattern of hierarchies used for instance in Coq's MathComp or Lean's mathlib libraries, where types are canonically associated to at most one instance and instances share a common overloaded syntax.We present new design patterns to leverage these issues, and apply them to the formalization of order structures in the MathComp library. A common idea in these patterns is underloading, i.e., a disambiguation of operators on a common type. In addition, our design patterns include a way to deal with duality in order structures in a convenient way. We hence formalize a large hierarchy which includes partial orders, semilattices, lattices as well as many variants.We finally pay a special attention to order substructures. We introduce a new kind of structure called prelattice. They are abstractions of semilattices, and allow us to deal with finite lattices and their sublattices within a common signature. As an application, we report on significant simplifications of the formalization of the face lattices of polyhedra in the Coq-Polyhedra library.

International audience; We consider a control problem for a heterogeneous population composed of customers able to switch at any time between different contracts, depending not only on the tariff conditions but also on the characteristics of each individual. A provider aims to maximize an average gain per time unit, supposing that the population is of infinite size. This leads to an ergodic control problem for a "mean-field" MDP in which the state space is a product of simplices, and the population evolves according to a controlled linear dynamics. By exploiting contraction properties of the dynamics in Hilbert's projective metric, we show that the ergodic eigenproblem admits a solution. This allows us to obtain optimal strategies, and to quantify the gap between steady-state strategies and optimal ones. We illustrate this approach on examples from electricity pricing, and show in particular that the optimal policies may be cyclic-alternating between discount and profit taking stages.

We introduce a family of cardinality's lower bounds, defined as ratios of norms. We prove that the tightest bound of the family is obtained as a limit case, and involves a Shannon entropy. We then use this entropic lower bound in sparse optimization problems to approximate cardinality requirements. This provides a nonlinear nonconvex relaxed problem, which can be efficiently solved by off-the-shelf nonlinear solvers. In the numerical study, we focus on the case where the optimization is performed on the simplex, and where the classical l1 penalization does not yield sparse solution. The Finance Index Tracking problem is taken as an example and illustrates the efficiency of the proposed approach.

We study a tight Bennett-type concentration inequality for sums of heterogeneous and independent variables, defined as a one-dimensional minimization. We show that this refinement, which outperforms the standard known bounds, remains computationally tractable: we develop a polynomial-time algorithm to compute confidence bounds, proved to terminate with an epsilon-solution. From the proposed inequality, we deduce tight distributionally robust bounds to Chance-Constrained Programming problems. To illustrate the efficiency of our approach, we consider two use cases. First, we study the chance-constrained binary knapsack problem and highlight the efficiency of our cutting-plane approach by obtaining stronger solution than classical inequalities (such as Chebyshev-Cantelli or Hoeffding). Second, we deal with the Support Vector Machine problem, where the convex conservative approximation we obtain improves the robustness of the separation hyperplane, while staying computationally tractable.

We consider a problem where a Principal aims to design a reward function to a field of heterogeneous agents. In our setting, the agents compete with each other through their rank within the population in order to obtain the best reward. We first explicit the equilibrium for the mean-field game played by the agents, and then characterize the optimal reward in the homogeneous setting. For the general case of a heterogeneous population, we develop a numerical approach, which is then applied to the specific case study of the market of Energy Saving Certificates.

Hyperfields and systems are two algebraic frameworks which have been developed to provide a unified approach to classical and tropical structures. All hyperfields, and more generally hyperrings, can be represented by systems. We show that, conversely, we show that the systems arising in this way, called hypersystems, are characterized by certain elimination axioms. Systems are preserved under standard algebraic constructions; for instance matrices and polynomials over hypersystems are systems, but not hypersystems. We illustrate these results by discussing several examples of systems and hyperfields, and constructions like matroids over systems.

International audience; The COVID-19 sanitary crisis has shed an unprecedented light on the role of modellers, mathematicians, computer scientists and data scientists in the monitoring and in the understanding of the dynamics of an epidemic. The general audience became rapidly acquainted with the concepts of R0, of quasi-exponential growth of the number of cases, as well as with the burden that such an explosive dynamics puts on medical structures. But mathematical and computational approaches have even more to offer.From the early stages of the pandemic, many organisational issues arose to cope with the wave of patients, which overwhelmed many hospitals and care structures. Emergency call centres faced a sharp increase in the number of calls, which had to be efficiently sorted according to the urgency of the patient’s condition. The saturation of critical care services led to the need to re-orient incoming patients to other hospitals with available beds, or to organise the transfer of patients from a heavily burdened region to a region under a weaker capacity strain. Hospital services had to find humanly manageable ways to deal with the work surplus, in conditions where health workers were not only at risk of physical and psychological exhaustion, but also at risk of being infected with SARS-CoV-2. In this context, already existing collaborations between mathematicians or computer scientists and medical doctors or emergency call centres gave rise to the extraordinarily quick emergence of tools to help operators and medical staff with logistic decisions.Below, we present four such initiatives, which arose during the first COVID-19 wave in France in 2020. They illustrate what close collaborations between medical staff and researchers from the fields of operations research, modelling of complex dynamics or data sciences can bring to the management of critical situations in health services. Beyond the current pandemic, they also pose the question of how to improve our preparedness to future crises.

It is an open question to determine if the theory of self-concordant barriers can provide an interior point method with strongly polynomial complexity in linear programming. In the special case of the logarithmic barrier, it was shown in [Allamigeon, Benchimol, Gaubert and Joswig, SIAM J. on Applied Algebra and Geometry, 2018] that the answer is negative. In this paper, we show that none of the self-concordant barrier interior point methods is strongly polynomial. This result is obtained by establishing that, on parametric families of convex optimization problems, the log-limit of the central path degenerates to a piecewise linear curve, independently of the choice of the barrier function. We provide an explicit linear program that falls in the same class as the Klee-Minty counterexample, i.e., in dimension $n$ with $2n$ constraints, in which the number of iterations is $\Omega(2^n)$., Comment: 33 pages, 5 figures, 1 table

International audience; A fundamental issue in the analysis of emergency call centers is to estimate the time needed to return to a congestion-free regime after an unusual event with a massive arrival of calls. Call centers can generally be represented by timed Petri nets with a hierarchical structure, in which several layers describe the successive steps of treatments of calls. We study a continuous approximation of the Petri net dynamics (with infinitesimal tokens). Then, we show that a counter function, measuring the deviation to the stationary regime, coincides with the value function of a semi-Markov decision problem. Then, we establish a finite time convergence result, exploiting the hierarchical structure of the Petri net. We obtain an explicit bound for the transience time, as a function of the initial marking and sojourn times. This is based on methods from the theory of stochastic shortest paths and non-linear Perron--Frobenius theory. We illustrate the bound on a case study of a medical emergency call center.

We develop value iteration-based algorithms to solve in a unified manner different classes of combinatorial zero-sum games with mean-payoff type rewards. These algorithms rely on an oracle, evaluating the dynamic programming operator up to a given precision. We show that the number of calls to the oracle needed to determine exact optimal (positional) strategies is, up to a factor polynomial in the dimension, of order R/sep, where the "separation" sep is defined as the minimal difference between distinct values arising from strategies, and R is a metric estimate, involving the norm of approximate sub and super-eigenvectors of the dynamic programming operator. We illustrate this method by two applications. The first one is a new proof, leading to improved complexity estimates, of a theorem of Boros, Elbassioni, Gurvich and Makino, showing that turn-based mean-payoff games with a fixed number of random positions can be solved in pseudo-polynomial time. The second one concerns entropy games, a model introduced by Asarin, Cervelle, Degorre, Dima, Horn and Kozyakin. The rank of an entropy game is defined as the maximal rank among all the ambiguity matrices determined by strategies of the two players. We show that entropy games with a fixed rank, in their original formulation, can be solved in polynomial time, and that an extension of entropy games incorporating weights can be solved in pseudo-polynomial time under the same fixed rank condition., 41 pages, 7 figures

International audience; Hilbertian kernel methods and their positive semidefinite kernels have been extensively used in various fields of applied mathematics and machine learning, owing to their several equivalent characterizations. We here unveil an analogy with concepts from tropical geometry, proving that tropical positive semidefinite kernels are also endowed with equivalent viewpoints, stemming from Fenchel-Moreau conjugations. This tropical analogue of Aronszajn's theorem shows that these kernels correspond to a feature map, define monotonous operators, and generate max-plus function spaces endowed with a reproducing property. They furthermore include all the Hilbertian kernels classically studied as well as Monge arrays. However, two relevant notions of tropical reproducing kernels must be distinguished, based either on linear or sesquilinear interpretations. The sesquilinear interpretation is the most expressive one, since reproducing spaces then encompass classical max-plus spaces, such as those of (semi)convex functions. In contrast, in the linear interpretation, the reproducing kernels are characterized by a restrictive condition, von Neumann regularity. Finally, we provide a tropical analogue of the "representer theorems", showing that a class of infinite dimensional regression and interpolation problems admit solutions lying in finite dimensional spaces. We illustrate this theorem by an application to optimal control, in which tropical kernels allow one to represent the value function.

International audience; We consider Dynamic programming equations associated to discrete time stochastic control problems with continuous state space, which arise in particular from monotone time discretizations of Hamilton-Jacobi-Bellman equations. We develop and study several numerical algorithms for solving such equations, combining tropical numerical methods and stochastic dual dynamic programming methods. We also compare these algorithms with the point based methods for solving Partially Observable Markov Decision Processes (POMDP).

Une régularisation quadratique pour la tarification de contrats d'électricité

We exhibit a class of classical or tropical posynomial systems which can be solved by reduction to linear or convex programming problems. This relies on a notion of colorful vectors with respect to a collection of Newton polytopes. This extends the convex programming approach of one player stochastic games., Comment: To appear in the proceedings of ICMS 2020

We introduce the notion of firm non-expansive mapping in weak metric spaces, extending previous work for Banach spaces and certain geodesic spaces. We prove that, for firm non-expansive mappings, the minimal displacement, the linear rate of escape, and the asymptotic step size are all equal. This generalises a theorem by Reich and Shafrir., 12 pages. The new Section 3 contains a characterisation of the firm non-expansive mappings of one-dimensional asymmetric normed spaces. The reference list includes new entries. This version has been accepted by Archiv der Mathematik

Adaptive Partition-based Methods (APM) are numerical methods to solve two-stage stochastic linear problems (2SLP). The core idea is to iteratively construct an adapted partition of the space of alea in order to aggregate scenarios while conserving the true value of the cost-to-go for the current first-stage control. Relying on the normal fan of the dual admissible set, we extend the classical and generalized APM method by i) extending the method to almost arbitrary 2SLP, ii) giving a necessary and sufficient condition for a partition to be adapted even for non-finite distribution, and iii) proving the convergence of the method. We give some additional insights by linking APM to the L-shaped algorithm.

Shapley operators of undiscounted zero-sum two-player games are order-preserving maps that commute with the addition of a constant. We characterize the fixed point sets of Shapley operators, in finite dimension (i.e., for games with a finite state space). Some of these characterizations are of a lattice theoretical nature, whereas some other rely on metric or tropical geometry. More precisely, we show that fixed point sets of Shapley operators are special instances of hyperconvex spaces: they are sup-norm non-expansive retracts, and also lattices in the induced partial order. Moreover, they retain properties of convex sets, with a notion of convex hull defined only up to isomorphism. For deterministic games with finite action spaces, these fixed point sets are supports of polyhedral complexes, with a cell decomposition attached to stationary strategies of the players, in which each cell is an alcoved polyhedron of $A_n$ type. We finally provide an explicit local representation of the latter fixed point sets, as polyhedral fans canonically associated to lattices included in the Boolean hypercube.

We show that the multistage linear problem (MSLP) with an arbitrary cost distribution is equivalent to a MSLP on a finite scenario tree. We establish this exact quantization result by analyzing the polyhedral structure of MSLPs. In particular, we show that the expected cost-to-go functions are polyhedral and affine on the cells of a chamber complex, which is independent of the cost distribution. This leads to new complexity results, showing that MSLP is fixed-parameter tractable.

International audience; We report on the porting of the Mathematical Components library (hereafter MC) to the Hierarchy Builder [2] tool (hereafter HB).

We show that the empirical risk minimization (ERM) problem for neural networks has no solution in general. Given a training set $s_1, \dots, s_n \in \mathbb{R}^p$ with corresponding responses $t_1,\dots,t_n \in \mathbb{R}^q$, fitting a $k$-layer neural network $\nu_\theta : \mathbb{R}^p \to \mathbb{R}^q$ involves estimation of the weights $\theta \in \mathbb{R}^m$ via an ERM: \[ \inf_{\theta \in \mathbb{R}^m} \; \sum_{i=1}^n \lVert t_i - \nu_\theta(s_i) \rVert_2^2. \] We show that even for $k = 2$, this infimum is not attainable in general for common activations like ReLU, hyperbolic tangent, and sigmoid functions. A high-level explanation is like that for the nonexistence of best rank-$r$ approximations of higher-order tensors --- the set of parameters is not a closed set --- but the geometry involved for best $k$-layer neural networks approximations is more subtle. In addition, we show that for smooth activations $\sigma(x)= 1/\bigl(1 + \exp(-x)\bigr)$ and $\sigma(x)=\tanh(x)$, such failure to attain an infimum can happen on a positive-measured subset of responses. For the ReLU activation $\sigma(x)=\max(0,x)$, we completely classifying cases where the ERM for a best two-layer neural network approximation attains its infimum. As an aside, we obtain a precise description of the geometry of the space of two-layer neural networks with $d$ neurons in the hidden layer: it is the join locus of a line and the $d$-secant locus of a cone., Comment: 19 pages

We propose a generic multistage stochastic model for the Alternating Current Optimal Power Flow (AC OPF) problem for radial distribution networks, to account for the random electricity production of renewable energy sources and dynamic constraints of storage systems. We consider single-phase radial networks. Radial three-phase balanced networks (medium-voltage distribution networks typically have this structure) reduce to the former case. This induces a large scale optimization problem, which, given the non-convex nature of the AC OPF, is generally challenging to solve to global optimality. We derive a priori conditions guaranteeing a vanishing relaxation gap for the multi-stage AC OPF problem, which can thus be solved using convex optimization algorithms. We also give an a posteriori upper bound on the relaxation gap. In particular, we show that a null or low relaxation gap may be expected for applications with light reverse power flows or if sufficient storage capacities with low cost are available. We illustrate our results on a problem of planning of a realistic distribution feeder on one day, taking into account the uncertainty associated with distributed solar production, and diffuse storage systems. We show theoretically a vanishing relaxation gap for this problem, when the installed solar capacity does not exceed local consumption, independently of the scenarios of solar production that are considered. Then, we illustrate numerically the quality of the a posteriori bound on the relaxation gap for higher installed capacities of distributed generation. Scenario trees for solar production are constructed from a stochastic model, by a quantile-based algorithm.

International audience; It has been observed that the very important motion planning problem of robotics mathematically speaking boils down to the problem of finding a section to the path-space fibration, raising the notion of topological complexity, as introduced by M. Farber. The above notion fits the motion planning problem of robotics when there are no constraints on the actual control that can be applied to the physical apparatus. In many applications, however, a physical apparatus may have constrained controls, leading to constraints on its potential future dynamics. In this paper we adapt the notion of topological complexity to the case of directed topological spaces, which encompass such controlled systems, and also systems which appear in concurrency theory. We study its first properties, make calculations for some interesting classes of spaces, and show applications to a form of directed homotopy equivalence.

International audience; Tropical geometry has been recently used to obtain new complexity results in convex optimization and game theory. In this paper, we present an application of this approach to a famous class of algorithms for linear programming, i.e., log-barrier interior point methods. We show that these methods are not strongly polynomial, by constructing a family of linear programs with 3r + 1 inequalities in dimension 2r for which the number of iterations performed is in Ω(2 r). The total curvature of the central path of these linear programs is also exponential in r, disproving a continuous analogue of the Hirsch conjecture proposed by Deza, Terlaky, and Zinchenko. These results are obtained by analyzing the tropical central path, which is the piecewise linear limit of the central paths of parameterized families of classical linear programs viewed through "logarithmic glasses." This allows us to provide combinatorial lower bounds for the number of iterations and the total curvature, in a general setting.

virtual conference; International audience; In poor data and urgent decision-making applications, managers need to make decisions without complete knowledge of the system dynamics. In biodiversity conservation, adaptive management (AM) is the principal tool for decision-making under uncertainty. AM can be solved using simplified Mixed Observable Markov Decision Processes called hidden model MDPs (hmMDPs) when the unknown dynamics are assumed stationary. hmMDPs provide optimal policies to AM problems by augmenting the MDP state space with an unobservable state variable representing a finite set of predefined models. A drawback in formalising an AM problem is that experts are often solicited to provide this predefined set of models by specifying the transition matrices. Expert elicitation is a challenging and time-consuming process that is prone to biases, and a key assumption of hmMDPs is that the true transition matrix will be included in the candidate model set. We propose an original approach to build a hmMDP with a universal set of predefined models that is capable of solving any 2-state n-action AM problem. Our approach uses properties of the transition matrices to build the model set and is independent of expert input, removing the potential for expert error in the optimal solution. We provide analytical formulations to derive the minimum set of models to include into an hmMDP to solve any AM problems with 2 states and n actions. We assess our universal AM algorithm on two species conservation case studies from Australia and randomly generated problems.

We develop a new iterative method based on Pontryagin principle to solve stochastic control problems. This method is nothing else than the Newton method extended to the framework of stochastic controls, where the state dynamics is given by an ODE with stochastic coefficients. Each iteration of the method is made of two ingredients: computing the Newton direction, and finding an adapted step length. The Newton direction is obtained by solving an affine-linear Forward-Backward Stochastic Differential Equation (FBSDE) with random coefficients. This is done in the setting of a general filtration. We prove that solving such an FBSDE reduces to solving a Riccati Backward Stochastic Differential Equation (BSDE) and an affine-linear BSDE, as expected in the framework of linear FBSDEs or Linear-Quadratic stochastic control problems. We then establish convergence results for this Newton method. In particular, sufficient regularity of the second-order derivative of the cost functional is required to obtain (local) quadratic convergence. A restriction to the space of essentially bounded stochastic processes is needed to obtain such regularity. To choose an appropriate step length while fitting our choice of space of processes, an adapted backtracking line-search method is developed. We then prove global convergence of the Newton method with the proposed line-search procedure, which occurs at a quadratic rate after finitely many iterations. An implementation with regression techniques to solve BSDEs arising in the computation of the Newton step is developed. We apply it to the control problem of a large number of batteries providing ancillary services to an electricity network.

We propose a stochastic control problem to control cooperatively Thermostatically Controlled Loads (TCLs) to promote power balance in electricity networks. We develop a method to solve this stochastic control problem with a decentralized architecture, in order to respect privacy of individual users and to reduce both the telecommunications and the computational burden compared to the setting of an omniscient central planner. This paradigm is called federated learning in the machine learning community, see [YFY20], therefore we refer to this problem as a federated stochastic control problem. The optimality conditions are expressed in the form of a high-dimensional Forward-Backward Stochastic Differential Equation (FBSDE), which is decomposed into smaller FBSDEs modeling the optimal behaviors of the aggregate population of TCLs of individual agents. In particular, we show that these FBSDEs fully characterize the Nash equilibrium of a stochastic Stackelberg differential game. In this game, a coordinator (the leader) aims at controlling the aggregate behavior of the population, by sending appropriate signals, and agents (the followers) respond to this signal by optimizing their storage system locally. A mean-field-type approximation is proposed to circumvent telecommunication constraints and privacy issues. Convergence results and error bounds are obtained for this approximation depending on the size of the population of TCLs. A numerical illustration is provided to show the interest of the control scheme and to exhibit the convergence of the approximation. An implementation which answers practical industrial challenges to deploy such a scheme is presented and discussed.

We study timed Petri nets, with preselection and priority routing. We represent the behavior of these systems by piecewise affine dynamical systems. We use tools from the theory of nonexpansive mappings to analyze these systems. We establishan equivalence theorem between priority-free fluid timed Petri nets and semi-Markov decision processes, from which we derive the convergence to a periodic regime and the polynomial-time computability of the throughput. More generally, we develop an approach inspired by tropical geometry, characterizing the congestion phases as the cells of a polyhedral complex. We illustrate these results by a current application to the performance evaluation of emergency call centers in the Paris area. We show that priorities can lead to a paradoxical behavior: in certain regimes, the throughput of the most prioritary task may not be an increasing function of the resources., Comment: To appear in a special issue of Fundamenta Informaticae

This note discusses some aspects of the asymptotic behaviour of nonexpansive maps. Using metric functionals, we make a connection to the invariant subspace problem and prove a new result for nonexpansive maps of $\ell^{1}$. We also point out some inaccurate assertions appearing in the literature on this topic., The reference list was updated and Remark 3.2 was included in this version

We introduce the flag-approximability of a convex body to measure how easy it is to approximate by polytopes. We show that the flag-approximability is exactly half the volume entropy of the Hilbert geometry on the body, and that both quantities are maximized when the convex body is a Euclidean ball. We also compute explicitly the asymptotic volume of a convex polytope, which allows us to prove that simplices have the least asymptotic volume., 15 pages, 2 figures

International audience; Let P(t) be an n × n (complex) exponentially parameterized pentadiagonal matrix. In this article, using a theorem of Akian, Bapat, and Gaubert, we present explicit formulas for asymptotics of the moduli of the eigenvalues of P(t) as t → ∞. Our approach is based on exploiting the relation with tropical algebra and the weighted digraphs of matrices. We prove that this asymptotics tends to a unique limit or two limits. Also, for n − 2 largest magnitude eigenvalues of P(t) we compute the asymptotics as n → ∞, in addition to t. When P(t) is also symmetric, these formulas allow us to compute the asymptotics of the 2‐norm condition number. The number of arithmetic operations involved, does not depend on n. We illustrate our results by some numerical tests.

International audience; We portray the evolution of the Covid-19 epidemic during the crisis ofMarch-April 2020 in the Paris area, by analyzing the medical emergencycalls received by the EMS of the four central departments of this area(Centre 15 of SAMU 75, 92, 93 and 94). Our study reveals strongdissimilarities between these departments. We show that the logarithmof each epidemic observable can be approximated by a piecewise linearfunction of time. This allows us to distinguish the different phasesof the epidemic, and to identify the delay between sanitary measuresand their influence on the load of EMS. This also leads to analgorithm, allowing one to detect epidemic resurgences. We rely on atransport PDE epidemiological model, and we use methods fromPerron-Frobenius theory and tropical geometry.; Nous décrivons l'évolution de l'épidémie de Covid-19 dans l'agglomération parisienne, pendant la crise de Mars-Avril 2020, en analysant les appels d'urgence au numéro 15 traités par les SAMU des quatre départements centraux de l'agglomération (75, 92, 93 et 94). Notre étude révèle de fortes disparités entres ces départements. Nous montrons que le logarithme de toute observable épidémique peut être approché par une fonction du temps linéaire par morceaux. Cela nous permet d'identifier les différentes phases d'évolution de l'épidémie, et aussi d'évaluer le délai entre la prise de mesures sanitaires et leur effet sur la sollicitation de l'aide médicale urgente. Nous en déduisons un algorithme permettant de détecter une resurgence éventuelle de l'épidémie. Notre approche s'appuie sur un modèle d'EDP de transport de l'évolution épidémique, ainsi que sur des méthodes de théorie de Perron-Frobenius et de géométrie tropicale.

International audience

The entropic barrier, studied by Bubeck and Eldan (Proc. Mach. Learn. Research, 2015), is a self-concordant barrier with asymptotically optimal self-concordance parameter. In this paper, we study the tropicalization of the central path associated with the entropic barrier, i.e., the logarithmic limit of this central path for a parametric family of linear programs defined over the field of Puiseux series. Our main result is that the tropicalization of the entropic central path is a piecewise linear curve which coincides with the tropicalization of the logarithmic central path studied by Allamigeon et al. (SIAM J. Applied Alg. Geom., 2018). One consequence is that the number of linear pieces in the tropical entropic central path can be exponential in the dimension and the number of inequalities defining the linear program., 9 pages

By studying the intrinsic polyhedral structure of multistage stochastic linear problems (MSLP), we show that a MSLP with an arbitrary cost distribution is equivalent to a MSLP on a finite scenario tree. More precisely, we show that the expected cost-to-go function, at a given stage, is affine on each cell of a chamber complex i.e., on the common refinement of the complexes obtained by projecting the faces of a polyhedron. This chamber complex is independent of the cost distribution. Furthermore, we examine several important special cases of random cost distributions, exponential on a polyhedral cone, or uniform on a polytope, and obtain an explicit description of the supporting hyperplanes of the cost-to-go function, in terms of certain valuations attached to the cones of a normal fan. This leads to fixed-parameter tractability results, showing that MSLP can be solved in polynomial time when the number of stages together with certain characteristic dimensions are fixed.

Let $F(x, y) \in \mathbb{C}[x,y]$ be a polynomial of degree $d$ and let $G(x,y) \in \mathbb{C}[x,y]$ be a polynomial with $t$ monomials. We want to estimate the maximal multiplicity of a solution of the system $F(x,y) = G(x,y) = 0$. Our main result is that the multiplicity of any isolated solution $(a,b) \in \mathbb{C}^2$ with nonzero coordinates is no greater than $\frac{5}{2}d^2t^2$. We ask whether this intersection multiplicity can be polynomially bounded in the number of monomials of $F$ and $G$, and we briefly review some connections between sparse polynomials and algebraic complexity theory., v1: 18 pages; v2: minor revision, additional remarks and an example, 21 pages, 1 figure

In this paper we provide a new graph theoretic proof of the tropical Jacobi identity, recently obtained in [AGN16]. We also develop an application of this theorem to optimal assignments with supervisions. That is, optimally assigning multiple tasks to one team, or daily tasks to multiple teams, where each team has a supervisor task or a supervised task., The first author was supported by INRIA postdoctoral fellowship and SCE Young research grant. The second author was supported by a public grant as part of the Investissement d'avenir project, reference ANR-11-LABX-0056-LMH, LabEx LHM. The third author was supported by EPSRC Grant EP/P019676/1

We portray the evolution of the Covid-19 epidemic during the crisis of March-April 2020 in the Paris area, by analyzing the medical emergency calls received by the EMS of the four central departments of this area (Centre 15 of SAMU 75, 92, 93 and 94). Our study reveals strong dissimilarities between these departments. We provide an algorithm, based on a piecewise linear approximation of the logarithm of epidemic observables, allowing one to monitor the epidemic. Our methods combine ideas from several elds of mathematics: tropical geometry, PerronFrobenius theory, probability and optimization, transport PDE in population dynamics.; Nous décrivons l'évolution de l'épidémie de Covid-19 dans l'agglomération parisienne, pendant la crise de Mars-Avril 2020, en analysant les appels d'urgence au numéro 15 traités par les SAMU des quatre départements centraux de l'agglomération (75, 92, 93 et 94).Notre étude révèle de fortes disparités entres ces départements. Nous donnons un algorithme, utilisant une approximation linéaire par morceaux du logarithme des observables épidémiques, qui permet de surveiller l'évolution. Nos méthodes sont inspirées par plusieurs domaines des mathématiques: géométrie tropicale, théorie de Perron--Frobenius, probabilités et optimisation, modèles d'EDP de transport en dynamique de population.

International audience; We consider a network of prosumers involved in peer-to-peer energy exchanges, with differentiation price preferences on the trades with their neighbors, and we analyze two market designs: (i) a centralized market, used as a benchmark, where a global market operator optimizes the flows (trades) between the nodes, local demand and exibility activation to maximize the system overall social welfare; (ii) a distributed peer-to-peer market design where prosumers in local energy communities optimize selfishly their trades, demand, and exibility activation. We first characterize the solution of the peer-to-peer market as a Variational Equilibrium and prove that the set of Variational Equilibria coincides with the set of social welfare optimal solutions of market design (i). We give several results that help understanding the structure of the trades at an equilibrium or at the optimum. We characterize the impact of preferences on the network line congestion and renewable energy surplus under both designs. We provide a reduced example for which we give the set of all possible generalized equilibria, which enables to give an approximation of the price of anarchy. We provide a more realistic example which relies on the IEEE 14-bus network, for which we can simulate the trades under dierent preference prices. Our analysis shows in particular that the preferences have a large impact on the structure of the trades, but that one equilibrium (variational) is optimal. Finally, the learning mechanism needed to reach an equilibrium state in the peer-to-peer market design is discussed together with privacy issues.

We introduce tropical spectrahedra, defined as the images by the nonarchimedean valuation of spectrahedra over the field of real Puiseux series. We provide an explicit polyhedral characterization of generic tropical spectrahedra, involving principal tropical minors of size at most 2. One of the key ingredients is Denef-Pas quantifier elimination result over valued fields. We obtain from this that the nonarchimedean valuation maps semialgebraic sets to semilinear sets that are closed. We also prove that, under a regularity assumption, the image by the valuation of a basic semialgebraic set is obtained by tropicalizing the inequalities which define it., Comment: v1: 23 pages, 3 figures; v2: 25 pages, 4 figures, stronger results in Section 4 + new example + minor revisions; v3: 31 pages, 4 figures, new theorem in Section 5 + more discussion in Sections 2 and 4

Linear complementarity programming is a generalization of linear programming which encompasses the computation of Nash equilibria for bimatrix games. While the latter problem is PPAD-complete, we show that the analogue of this problem in tropical algebra can be solved in polynomial time. Moreover, we prove that the Lemke--Howson algorithm carries over the tropical setting and performs a linear number of pivots in the worst case. A consequence of this result is a new class of (classical) bimatrix games for which Nash equilibria computation can be done in polynomial time.

We establish a generalized Perron-Frobenius theorem, based on a combinatorial criterion which entails the existence of an eigenvector for any nonlinear order-preserving and positively homogeneous map \begin{document}$ f $\end{document} acting on the open orthant \begin{document}$ \mathbb{R}_{ >0}^n $\end{document} . This criterion involves dominions, i.e., sets of states that can be made invariant by one player in a two-person game that only depends on the behavior of \begin{document}$ f $\end{document} "at infinity". In this way, we characterize the situation in which for all \begin{document}$ \alpha, \beta > 0 $\end{document} , the "slice space" \begin{document}$ \mathcal{S}_\alpha^\beta : = \{ x \in \mathbb{R}_{ >0}^n \mid \alpha x \leqslant f(x) \leqslant \beta x \} $\end{document} is bounded in Hilbert's projective metric, or, equivalently, for all uniform perturbations \begin{document}$ g $\end{document} of \begin{document}$ f $\end{document} , all the orbits of \begin{document}$ g $\end{document} are bounded in Hilbert's projective metric. This solves a problem raised by Gaubert and Gunawardena (Trans. AMS, 2004). We also show that the uniqueness of an eigenvector is characterized by a dominion condition, involving a different game depending now on the local behavior of \begin{document}$ f $\end{document} near an eigenvector. We show that the dominion conditions can be verified by directed hypergraph methods. We finally illustrate these results by considering specific classes of nonlinear maps, including Shapley operators, generalized means and nonnegative tensors.

We show that a neural network whose output is obtained as the difference of the outputs of two feedforward networks with exponential activation function in the hidden layer and logarithmic activation function in the output node, referred to as log-sum-exp (LSE) network, is a smooth universal approximator of continuous functions over convex, compact sets. By using a logarithmic transform, this class of network maps to a family of subtraction-free ratios of generalized posynomials (GPOS), which we also show to be universal approximators of positive functions over log-convex, compact subsets of the positive orthant. The main advantage of difference-LSE networks with respect to classical feedforward neural networks is that, after a standard training phase, they provide surrogate models for a design that possesses a specific difference-of-convex-functions form, which makes them optimizable via relatively efficient numerical methods. In particular, by adapting an existing difference-of-convex algorithm to these models, we obtain an algorithm for performing an effective optimization-based design. We illustrate the proposed approach by applying it to the data-driven design of a diet for a patient with type-2 diabetes and to a nonconvex optimization problem.

International audience; We show that an order antimorphism on a finite-dimensional cone having no one-dimensional factors is homogeneous of degree −1. A consequence is that the existence of an order antimorphism on a finite-dimensional cone implies that the cone is a symmetric cone.