Idempotent analysis and its applications. Appendix by Pierre Del Moral. Transl. from the Russian by V. E. Nazaikinskij. (English) Zbl 0941.93001

Kolokoltsov, V. N.; Maslov, V. P.

Mathematics and its Applications (Dordrecht). 401. Dordrecht: Kluwer Academic Publishers. xii, 305 p. (1997).

A previous version of this book appeared in Russian [Idempotent analysis and its applications to optimal control (1994; Zbl 0857.49022)] where the themes of the first three chapters of this book were treated. The first two chapters explain the ideas of the theory. The rest of the volume can be seen as applications. Let us review the chapters.
Chapter one is a general introduction to idempotent analysis. First idempotent semigroups and semirings \(A\) are defined. An idempotent linear algebra which is analoguous to the usual one for vector spaces can be developed. A linear equation in the corresponding semimodule can be seen as solving graph optimization algorithms. The form of the general solution to this Bellman equation is characterized. One has to compute the power of an operator and take the limit when it tends to infinity. Practical algorithms will require that the operator is nilpotent and some characterizations for nilpotency are obtained in terms of paths of associated circuits (the components of the matrix of the operator are weights of arcs in the circuit) or in terms of its (unique) eigenvalue. The solution can also be obtained by the Ford-Lee algorithm. Several motivating fields of applications are presented (production scheduling, queueing system, Petri nets, networks). An order is naturally associated to idempotent semigroups and if they have a metric, one wants the topologies to be compatible in a sense which is given. This leads to idempotent metric semigroups and to idempotent metric semirings where linear functionals are defined. Theorem 1.5 is important as representing linear functionals via lower-semicontinuous functions which can be associated to \(A\)-valued measures in analogy to the usual Riesz theorem. An idempotent integral can be defined and properties are provided. An inner product analogous to the \(L^2\) inner product and weak convergence are introduced; it is seen that the Fourier transformation in this framework (where some of its properties still hold) becomes a Legendre transformation. So, out of the topology on idempotent semirings one can generate an analysis formally similar to the conventional one.
Chapter two studies operators on idempotent semimodules. First, it is seen that all continuous linear operators are integral operators. Necessary and sufficient conditions for a kernel to specify such an operator are given and weak and strong convergence of operator families are characterized in terms of kernels. Next, invertible operators are just those which are compositions of diagonal matrices and permutations of the elements of the basis. It is seen how the effect of automorphisms on operators gets reflected on the associated kernel. Compact operators are defined and their kernel characterization provided. Next, using the Frobenius-Perron result concerning the spectral properties of matrices with positive entries, it is seen that the spectrum of a continuous linear mapping \(A^n\to A^n\) contains generically a single nonzero eigenvalue. This result is extended to compact operators on spaces of smooth functions under stronger nondegeneracy conditions. These conditions allow to provide information on powers of these operators (spectral criterion, finiteness of the Neumann series). In a similar vein, if the kernel \(b(x, y)\) associated to the operator \(B\) (\(x\in X\), \(y\in X\) and \(X\) is compact) attains its minimum on the diagonal, this minimum is the eigenvalue of \(B\) and \(B^n\) converges to an operator with separated kernel as \(n\) tends to infinity; one term is the eigenvector of \(B\). In general, the multiplicity of minima on the diagonal controls the eigenspace dimension of \(B\) and the minimum value determines the eigenvalue of \(B\). A section shows how some optimization problems in economics (turnpike theorems) and the asymptotic properties of the solutions can be reduced to the framework of idempotent analysis and how the spectral theory of the chapter allows to recover known results. A last part considers nonlinear but homogeneous versions of such optimization problems in a stochastic context (applicable to controlled Markov jump processes, stochastic differential games…) and the spectral properties of the Bellman operator are used again.
The next chapter treats generalized solutions to Bellman’s differential equation. First, it is shown heuristically how this equation appears in the calculus of variations, optimal control problems (a specific cost function allows to cast such problems in the previous class) and differential games. The authors point out difficulties concerning the regularity of the equation and a fortiori of the solution. Since the equation is not linear, extended solutions in the distributional sense cannot be introduced a priori but using a method of Hopf, one adds a small term (characterized by a small parameter \(h\)) to Bellman’s equation (one gets a Burgers equation) and one performs a coordinate transformation making it linear (one gets a heat equation) and then one lets \(h\) tend to zero and generalized solutions can be obtained. It is seen that the transformation takes the standard semiring \(\mathbb{R}^+\) into a nonstandard one but the important observation is that the operator \(R\) generating the solution to Bellman’s equation from an initial function is linear with respect to \(\oplus= \min\) and \(\odot= +\). This allows to define weak solutions which solve the Cauchy problem of Bellman’s equation. Existence and uniqueness of a local solution are obtained under regularity and convexity assumptions on the Hamiltonian. On the other hand, the critical points of the Hamiltonian determine the number of eigenfunctions of \(R\) (the solutions to the stationary problem). It is also seen that the solutions to discretised versions tend weakly to the original differential Bellman equation. The rest of the chapter presents miscellaneous aspects: 1) A section goes back to the nonlinear stochastic framework and shows some approximation results for the solution to Bellman’s equation when the random perturbations are small (an example from quantum mechanics is presented). 2) Another section presents the results of the authors [Russ. Acad. Sci., Dokl., Math. 45, No. 3, 522-527 (1992); translation from Dokl. Akad. Nauk, Ross. Akad. Nauk 324, No. 1, 29-34 (1992; Zbl 0796.49025)] where the dynamics of Pareto sets in multicriteria optimization is described using a Bellman equation. 3) A section is devoted to solving the stationary Bellman equation subject to boundary conditions, under some assumptions on the Hamiltonian, in a space of distributions whose elements \(f\) are differentiable at a point if there exists a differentiable function \(\phi\) such that \(f-\phi\) is minimum at this point; this condition characterizes continuity of the operations \(\oplus\), \(\odot\) in a suitable topology. 4) Another section gives conditions guaranteeing existence and uniqueness of a solution to the stochastic Bellman equation. 5) Next, the turnpike theorem of the previous chapter is generalized to an infinite-dimensional context: sufficient conditions so that the Bellman operator \(R\) has asymptotically a factorizable kernel are given. 6) The results of a publication of D. Bronshtejn and A. S. Cherevatskij [Sov. Math. Dokl. 43, No. 2, 572-575 (1991); translation from Dokl. Akad. Nauk SSSR 317, No. 5, 1037-1041 (1991; Zbl 0770.34020)] are presented; one wishes to solve a boundary value problem for an ODE by minimizing an idempotent integral (the cost). 7) One explains how to recover the solution to the differential Bellman equation from a discretized version and the associated discrete idempotent measures.
Chapter four investigates the form of solutions to a Schrödinger type equation \[ h{\partial u\over\partial t}= H\Biggl(t,x, -h{\partial\over\partial x}\Biggr) u \] where \(x\in \mathbb{R}^n\). One looks for asymptotic solutions of the form \[ u(t,x)= A(t,x)\exp(- S(t, x)/h). \] But instead of considering additive perturbation terms one seeks solutions with a multiplicative correction term of the form \((1+ O(h))\). The solutions of this type are called multiplicative asymptotics when they exist, which will be the case when the Hamiltonian H is a tunnel-type Hamiltonian. In contrast to the additive perturbation case, in adding solutions the one with largest entropy \(S\) will be retained so that we have an idempotent superposition principle. \(S\) solves a Bellman equation and the methods of idempotent analysis can be applied for obtaining this unique solution. In this sense, one talks of the quantization of the Bellman equation. So, the sections study several types of potentials and in particular the double-well potential; the tunnel effect is quantified and the transition time is calculated using eigenfunctions corresponding to the energies. A bibliography with 235 entries ends this part.
An appendix of around sixty pages is added. It has been written by Pierre Del Moral and it explains the results of his thesis [Résolution particulaire des problèmes d’estimation et d’optimisation non linéaires, Toulouse (1994)]. A connection between estimation problems and optimization problems can be established by using the integration theory of Maslov. One introduces a measurable space where the background space is the set “of all possible controls” and the associated \(\sigma\) algebra contains those which are “interesting”. (Note that this is quite abstract and specific cases should have been detailed at this stage.) A Maslov measure on this space is a performance measure. From here, a theory and a formalism (based on idempotent analysis) are developed which illuminate the above mentioned connection. An application of particle methods in filtering to optimization problems using this point of view is highlighted. A bibliography with 51 entries closes this section.
A fairly modest index ends this volume.
This excellent book is well written and shows that the formalism of idempotent analysis has many original implications whose importance should not be underestimated.

Reviewer: A.Akutowicz (Berlin)

MSC:

93-02	Research exposition (monographs, survey articles) pertaining to systems and control theory
20M99	Semigroups
49L20	Dynamic programming in optimal control and differential games
93B28	Operator-theoretic methods
81Q20	Semiclassical techniques, including WKB and Maslov methods applied to problems in quantum theory
47D99	Groups and semigroups of linear operators, their generalizations and applications
93E10	Estimation and detection in stochastic control theory

Keywords:

Duhamel integral; Schrödinger equation; idempotent analysis; graph optimization; Bellman equation; operators; integral operators; spectrum; eigenvalue; transformation; Cauchy problem; random perturbations; quantum mechanics; turnpike theorem; multiplicative asymptotics; tunnel effect; particle methods; filtering

Citations:

Zbl 0857.49022; Zbl 0796.49025; Zbl 0770.34020