We consider a resource allocation problem involving a large number of agents with individual constraints subject to privacy, and a central operator whose objective is to optimize a global, possibly nonconvex, cost while satisfying the agents constrai
nts, for instance an energy operator in charge of the management of energy consumption flexibilities of many individual consumers. We provide a privacy-preserving algorithm that does compute the optimal allocation of resources, avoiding each agent to reveal her private information (constraints and individual solution profile) neither to the central operator nor to a third party. Our method relies on an aggregation procedure: we compute iteratively a global allocation of resources, and gradually ensure existence of a disaggregation, that is individual profiles satisfying agents private constraints, by a protocol involving the generation of polyhedral cuts and secure multiparty computations (SMC). To obtain these cuts, we use an alternate projection method, which is implemented locally by each agent, preserving her privacy needs. We adress especially the case in which the local and global constraints define a transportation polytope. Then, we provide theoretical convergence estimates together with numerical results, showing that the algorithm can be effectively used to solve the allocation problem in high dimension, while addressing privacy issues.
The problem of computing the smallest fixed point of an order-preserving map arises in the study of zero-sum positive stochastic games. It also arises in static analysis of programs by abstract interpretation. In this context, the discount rate may b
e negative. We characterize the minimality of a fixed point in terms of the nonlinear spectral radius of a certain semidifferential. We apply this characterization to design a policy iteration algorithm, which applies to the case of finite state and action spaces. The algorithm returns a locally minimal fixed point, which turns out to be globally minimal when the discount rate is nonnegative.
Tropical polyhedra have been recently used to represent disjunctive invariants in static analysis. To handle larger instances, tropical analogues of classical linear programming results need to be developed. This motivation leads us to study the trop
ical analogue of the classical linear-fractional programming problem. We construct an associated parametric mean payoff game problem, and show that the optimality of a given point, or the unboundedness of the problem, can be certified by exhibiting a strategy for one of the players having certain infinitesimal properties (involving the value of the game and its derivative) that we characterize combinatorially. We use this idea to design a Newton-like algorithm to solve tropical linear-fractional programming problems, by reduction to a sequence of auxiliary mean payoff game problems.
Molecular circadian clocks, that are found in all nucleated cells of mammals, are known to dictate rhythms of approximately 24 hours (circa diem) to many physiological processes. This includes metabolism (e.g., temperature, hormonal blood levels) and
cell proliferation. It has been observed in tumor-bearing laboratory rodents that a severe disruption of these physiological rhythms results in accelerated tumor growth. The question of accurately representing the control exerted by circadian clocks on healthy and tumour tissue proliferation to explain this phenomenon has given rise to mathematical developments, which we review. The main goal of these previous works was to examine the influence of a periodic control on the cell division cycle in physiologically structured cell populations, comparing the effects of periodic control with no control, and of different periodic controls between them. We state here a general convexity result that may give a theoretical justification to the concept of cancer chronotherapeutics. Our result also leads us to hypothesize that the above mentioned effect of disruption of circadian rhythms on tumor growth enhancement is indirect, that, is this enhancement is likely to result from the weakening of healthy tissue that are at work fighting tumor growth.
We discuss the tropical analogues of several basic questions of convex duality. In particular, the polar of a tropical polyhedral cone represents the set of linear inequalities that its elements satisfy. We characterize the extreme rays of the polar
in terms of certain minimal set covers which may be thought of as weighted generalizations of minimal transversals in hypergraphs. We also give a tropical analogue of Farkas lemma, which allows one to check whether a linear inequality is implied by a finite family of linear inequalities. Here, the certificate is a strategy of a mean payoff game. We discuss examples, showing that the number of extreme rays of the polar of the tropical cyclic polyhedral cone is polynomially bounded, and that there is no unique minimal system of inequalities defining a given tropical polyhedral cone.
We give a characterization of the minimal tropical half-spaces containing a given tropical polyhedron, from which we derive a counter example showing that the number of such minimal half-spaces can be infinite, contradicting some statements which app
eared in the tropical literature, and disproving a conjecture of F. Block and J. Yu. We also establish an analogue of the Minkowski-Weyl theorem, showing that a tropical polyhedron can be equivalently represented internally (in terms of extreme points and rays) or externally (in terms of half-spaces containing it). A canonical external representation of a polyhedron turns out to be provided by the extreme elements of its tropical polar. We characterize these extreme elements, showing in particular that they are determined by support vectors.
We study the max-plus or tropical analogue of the notion of polar: the polar of a cone represents the set of linear inequalities satisfied by its elements. We establish an analogue of the bipolar theorem, which characterizes all the inequalities sati
sfied by the elements of a tropical convex cone. We derive this characterization from a new separation theorem. We also establish variants of these results concerning systems of linear equalities.
The celebrated upper bound theorem of McMullen determines the maximal number of extreme points of a polyhedron in terms of its dimension and the number of constraints which define it, showing that the maximum is attained by the polar of the cyclic po
lytope. We show that the same bound is valid in the tropical setting, up to a trivial modification. Then, we study the natural candidates to be the maximizing polyhedra, which are the polars of a family of cyclic polytopes equipped with a sign pattern. We construct bijections between the extreme points of these polars and lattice paths depending on the sign pattern, from which we deduce explicit bounds for the number of extreme points, showing in particular that the upper bound is asymptotically tight as the dimension tends to infinity, keeping the number of constraints fixed. When transposed to the classical case, the previous constructions yield some lattice path generalizations of Gales evenness criterion.
We study the growth rate of a cell population that follows an age-structured PDE with time-periodic coefficients. Our motivation comes from the comparison between experimental tumor growth curves in mice endowed with intact or disrupted circadian clo
cks, known to exert their influence on the cell division cycle. We compare the growth rate of the model controlled by a time-periodic control on its coefficients with the growth rate of stationary models of the same nature, but with averaged coefficients. We firstly derive a delay differential equation which allows us to prove several inequalities and equalities on the growth rates. We also discuss about the necessity to take into account the structure of the cell division cycle for chronotherapy modeling. Numerical simulations illustrate the results.
Caratheodorys, Hellys and Radons theorems are three basic results in discrete geometry. Their max-plus counterparts have been proved by various authors. In this paper, more advanced results in discrete geometry are shown to have also their max-plus c
ounterparts: namely, the colorful Caratheodory theorem and the Tverberg theorem. A conjecture connected to the Tverberg theorem -- Sierksmas conjecture --, although still open for the usual convexity, is shown to be true in the max-plus settings.
