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.
Tropical Reproducing Kernels and Optimization Aubin-Frankowski, Pierre-Cyril; Gaubert, Stéphane
Integral equations and operator theory,
06/2024, Letnik:
96, Številka:
2
Journal Article
Recenzirano
Odprti dostop
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.
We consider semidifferentiable (possibly nonsmooth) maps, acting on a subset of a Banach space, that are nonexpansive either in the norm of the space or in Hilbert's or Thompson's metric inherited ...from a convex cone. We show that the global uniqueness of the fixed point of the map, as well as the geometric convergence of every orbit to this fixed point, can be inferred from the semidifferential of the map at this point. In particular, we show that the geometric convergence rate of the orbits to the fixed point can be bounded in terms of Bonsall's nonlinear spectral radius of the semidifferential. We derive similar results concerning the uniqueness of the eigenline and the geometric convergence of the orbits to it, in the case of positively homogeneous maps acting on the interior of a cone, or of additively homogeneous maps acting on an AM-space with unit. This is motivated in particular by the analysis of dynamic programming operators (Shapley operators) of zero-sum stochastic games.
We show that the sequence of moduli of the eigenvalues of a matrix polynomial is log-majorized, up to universal constants, by a sequence of “tropical roots” depending only on the norms of the matrix ...coefficients. These tropical roots are the non-differentiability points of an auxiliary tropical polynomial, or equivalently, the opposites of the slopes of its Newton polygon. This extends to the case of matrix polynomials some bounds obtained by Hadamard, Ostrowski and Pólya for the roots of scalar polynomials. We also obtain new bounds in the scalar case, which are accurate for “fewnomials” or when the tropical roots are well separated.
We establish a characterization of the vertices of a tropical polyhedron defined as the intersection of finitely many half-spaces. We show that a point is a vertex if, and only if, a directed ...hypergraph, constructed from the subdifferentials of the active constraints at this point, admits a unique strongly connected component that is maximal with respect to the reachability relation (all the other strongly connected components have access to it). This property can be checked in almost linear-time. This allows us to develop a tropical analogue of the classical double description method, which computes a minimal internal representation (in terms of vertices) of a polyhedron defined externally (by half-spaces or hyperplanes). We provide theoretical worst case complexity bounds and report extensive experimental tests performed using the library TPLib, showing that this method outperforms the other existing approaches.
If A is a nonnegative matrix whose associated directed graph is strongly connected, the Perron-Frobenius theorem asserts that A has an eigenvector in the positive cone, (\mathbb R^{+})^n. We ...associate a directed graph to any homogeneous, monotone function, f: (\mathbb R^{+})^n \rightarrow (\mathbb R^{+})^n, and show that if the graph is strongly connected, then f has a (nonlinear) eigenvector in (\mathbb R^{+})^n. Several results in the literature emerge as corollaries. Our methods show that the Perron-Frobenius theorem is ``really'' about the boundedness of invariant subsets in the Hilbert projective metric. They lead to further existence results and open problems.
Game theory has proven to be a valuable tool to study strategic electricity consumers enrolled in a demand response (DR) program. Among the different billing mechanisms proposed, the hourly billing ...model is of special interest as an intuitive and fair mechanism. We focus on this model and answer to several theoretical and practical questions. First, we prove the uniqueness of the consumption profile corresponding to the Nash equilibrium and we analyze its efficiency by providing a bound on the price of anarchy. Next, we address the computational issue of this equilibrium profile by providing results on the convergence rates of two decentralized algorithms to compute the equilibrium: the cycling best response dynamics and a projected gradient descent method. Last, we simulate this DR framework in a stochastic environment where the parameters depend on forecasts. Numerically, we show the relevance of an online DR procedure which reduces the impact of inaccurate forecasts in comparison to a standard offline procedure.
Circadian rhythm and cell population growth Clairambault, Jean; Gaubert, Stéphane; Lepoutre, Thomas
Mathematical and computer modelling,
04/2011, Letnik:
53, Številka:
7
Journal Article
Recenzirano
Odprti dostop
Molecular circadian clocks, that are found in all nucleated cells of mammals, are known to dictate rhythms of approximately 24 h (
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 tumor 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 is at work fighting tumor growth.
Matrix versions of the Hellinger distance Bhatia, Rajendra; Gaubert, Stephane; Jain, Tanvi
Letters in mathematical physics,
08/2019, Letnik:
109, Številka:
8
Journal Article
Recenzirano
Odprti dostop
On the space of positive definite matrices, we consider distance functions of the form
d
(
A
,
B
)
=
tr
A
(
A
,
B
)
-
tr
G
(
A
,
B
)
1
/
2
,
where
A
(
A
,
B
)
is the arithmetic mean and
G
(
A
,
B
)
...is one of the different versions of the geometric mean. When
G
(
A
,
B
)
=
A
1
/
2
B
1
/
2
this distance is
‖
A
1
/
2
-
B
1
/
2
‖
2
,
and when
G
(
A
,
B
)
=
(
A
1
/
2
B
A
1
/
2
)
1
/
2
it is the Bures–Wasserstein metric. We study two other cases:
G
(
A
,
B
)
=
A
1
/
2
(
A
-
1
/
2
B
A
-
1
/
2
)
1
/
2
A
1
/
2
,
the Pusz–Woronowicz geometric mean, and
G
(
A
,
B
)
=
exp
(
log
A
+
log
B
2
)
,
the log Euclidean mean. With these choices,
d
(
A
,
B
) is no longer a metric, but it turns out that
d
2
(
A
,
B
)
is a divergence. We establish some (strict) convexity properties of these divergences. We obtain characterisations of barycentres of
m
positive definite matrices with respect to these distance measures. One of these leads to a new interpretation of a power mean introduced by Lim and Palfia, as a barycentre. The other uncovers interesting relations between the log Euclidean mean and relative entropy.
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 appeared 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.
PDF
