Idempotent analysis

idempotent calculus

A branch of analysis based on replacing the usual arithmetic operations by a new set of basic operations (e.g., such as maximum or minimum), that is, on the concept of an idempotent semi-ring. In particular, idempotent analysis deals with functions taking values in idempotent semi-rings and with the corresponding function spaces (semi-modules). The term "idempotent analysis" (or idempotent calculus) is well established in the literature since the activity of V.P. Maslov and his collaborators (see e.g. [a1], [a2], [a3], [a4], [a5], [a6]).

The theory is well advanced and includes, in particular, idempotent integration theory, linear algebra, spectral theory, and functional analysis. Applications include various optimization problems such as multicriteria decision making, optimization on graphs, discrete optimization with a large parameter (asymptotic problems), optimal design of computer systems and computer media, optimal organization of parallel data processing, dynamic programming, discrete-event systems, computer science, discrete mathematics, mathematical logic, etc. (see, e.g., [a1], [a2], [a3], [a4], [a5], [a6], [a7], [a8], [a9], [a10]).

An impetus to the development of the theory was provided by Maslov's observation that some problems that are non-linear in the traditional sense turn out to be linear over a suitable semi-ring; this linearity considerably simplifies the explicit construction of solutions [a11], [a1], [a2], [a3], [a4], [a5], [a6]. This is a natural analogue of the so-called superposition principle in quantum mechanics (cf. Idempotent superposition principle). In particular, the Bellman equation (which is the main equation in optimal control theory) and its generalizations and the Hamilton–Jacobi equation (cf. also Hamilton–Jacobi theory) can be treated as linear over suitable semi-rings. Maslov's superposition principle leads to a unified approach to various optimization problems and optimal control problems with discrete or continuous state space as well to the corresponding formulas and algorithms (cf. Idempotent algorithm).

The analogy with quantum physics is not limited to the superposition principle. There is a correspondence between important constructions and results over the field of real (or complex) numbers and similar constructions and results over appropriate idempotent semi-rings in the spirit of N. Bohr's correspondence principle (cf. Idempotent correspondence principle).

Basic idempotent semi-rings.

A set $ A $ equipped with binary operations $ \oplus $( addition) and $ \odot $( multiplication) is called an idempotent semi-ring if $ A $ is a semi-ring with idempotent addition (that is, $ a \oplus a = a $ for all $ a \in A $) and neutral elements $ \mathbf{0} $ and $ \mathbf{1} $( cf. Idempotent semi-ring). Typical (and most common) examples are given by the so-called ( $ \max , + $)- semi-ring $ \mathbf R _ { \max } $ and ( $ \min , + $)- semi-ring $ \mathbf R _ { \min } $. Let $ \mathbf R $ be the field of real numbers. Then $ \mathbf R _ { \max } = \mathbf R \cup \{ - \infty \} $ with the operations $ a \oplus b = \max ( a,b ) $ and $ a \odot b = a + b $; $ \mathbf{0} = - \infty $, $ \mathbf{1} = 0 $. Similarly, $ \mathbf R _ { \min } = \mathbf R \cup \{ + \infty \} $ with operations $ \oplus = \min $, $ \odot = + $; in this case, $ \mathbf{0} = + \infty $, $ \mathbf{1} = 0 $. The so-called ( $ \min , \max $)- semi-ring coincides with $ \mathbf R \cup \{ - \infty \} \cup \{ + \infty \} $ with operations $ \oplus = \min $, $ \odot = + $; $ \mathbf{0} = + \infty $, $ \mathbf{1} = - \infty $. The well-known Boolean algebra $ \{ \mathbf{0} , \mathbf{1} \} $ is an example of a finite idempotent semi-ring. Other interesting examples and constructions can be found in [a1], [a2], [a3], [a4], [a5], [a6], [a7], [a8], [a9], [a10].

Idempotent integration and Maslov measures.

See also [a1], [a2], [a3], [a4], [a5], [a6]. Let $ X $ be a locally compact set and $ A = \mathbf R _ { \max } $ the ( $ \max , + $)- idempotent semi-ring. An idempotent analogue of the usual integration can be defined by the formula

$$ \tag{a1 } \int\limits _ { X } ^ \oplus {\varphi ( x ) } {dx } = \sup _ {x \in X } \varphi ( x ) , $$

where $ \varphi : X \rightarrow A $ is a continuous or upper semi-continuous function. This integration is "linear" over $ A $ and (a1) can be treated as a limit of Riemann or Lebesgue sums. The set function $ B \rightarrow m _ \varphi ( B ) = \sup _ {x \in B } \varphi ( x ) $, where $ B \subset X $, is called a Maslov $ A $- measure on $ X $. This function is completely additive: $ m _ \varphi ( \cup B _ \alpha ) = \oplus _ \alpha m _ \varphi ( B _ \alpha ) $. An integral with respect to this $ A $- measure is defined by the formula:

$$ \tag{a2 } \int\limits _ { X } ^ \oplus {\psi ( x ) } {dm _ \varphi } = \int\limits _ { X } ^ \oplus {\psi ( x ) \odot \varphi ( x ) } {dx } . $$

Let $ A $ be an arbitrary idempotent semi-ring equipped with its canonical partial order ( $ a \cle b $ if and only if $ a \oplus b = b $, cf. Idempotent semi-ring). Suppose that $ A $ is boundedly complete, i.e. every bounded subset $ B \subset A $ has a least upper bound $ \sup B $. In this case, idempotent integration and $ A $- measures can be defined by the same formulas (a1), (a2) for an arbitrary set $ X $ and bounded functions $ X \rightarrow A $. In particular, if $ A $ is the ( $ \min , + $)- semi-ring $ \mathbf R _ { \min } $, then the canonical order is the opposite of the usual ordering of numbers and $ \int _ {X} ^ \oplus {\varphi ( x ) } {dx } = \inf _ {x \in X } \varphi ( x ) $ with respect to this usual ordering.

Idempotent semi-modules.

Roughly speaking, semi-modules are "linear spaces" over semi-rings. A set $ V $ is called an idempotent semi-module over an idempotent semi-ring $ A $( or an $ A $- semi-module) if there is a commutative associative idempotent addition $ \oplus $ in $ V $ with a neutral element $ \mathbf{0} $, and a multiplication $ \odot $ of elements from $ V $ by elements of $ A $ is defined such that the following properties hold:

i) $ ( \lambda \odot \mu ) \odot v = \lambda \odot ( \mu \odot v ) $;

ii) $ \lambda \odot ( v _ {1} \oplus v _ {2} ) = \lambda \odot v _ {1} \oplus \lambda _ {2} \odot v _ {2} $;

iii) $ \mathbf{0} \odot v = \lambda \odot \mathbf{0} = \mathbf{0} $, for all $ \lambda, \mu \in A $, $ v,v _ {1} ,v _ {2} \in V $. It is often assumed that $ \sup _ \alpha \{ \lambda _ \alpha \} \odot v = \sup _ \alpha \{ \lambda _ \alpha \odot v \} $ in the sense of the canonical order in $ A $( where $ v \in V $ and $ \sup _ \alpha \{ \lambda _ \alpha \} \in A $).

The simplest $ A $- semi-module is the direct sum (product) $ A ^ {n} = \{ {( a _ {1} \dots a _ {n} ) } : {a _ {j} \in A } \} $. The set of all endomorphisms $ A ^ {n} \rightarrow A ^ {n} $ coincides with the non-commutative idempotent semi-ring $ { \mathop{\rm Mat} } _ {n} ( A ) $ of all $ A $- valued matrices (cf. Idempotent semi-ring, Example 4). Every element $ a \in A $ is "non-negative" : $ \mathbf{0} \cle a $ because $ \mathbf{0} + a = a $. So, the theory of $ A $- valued matrices is an analogue of the well-known Perron–Frobenius theory of non-negative matrices (see, e.g., [a4], [a5], [a6], [a7], [a9]). For example, if $ A = \mathbf R _ { \max } $( or $ \mathbf R _ { \min } $), then for every endomorphism $ K $ of $ A ^ {n} $( $ n \geq 1 $) there exist a non-trivial sub-semi-module $ S \subset A ^ {n} $( an "eigenspace" ) and element $ \lambda \in A $( an "eigenvalue" ) such that $ Kv = \lambda \odot v $ for all $ v \in S $. Similar results are valid for the semi-modules of bounded or continuous functions discussed below.

Let $ X $ be a set and denote by $ B ( X,A ) $ the set of all bounded mappings (functions) $ X \rightarrow A $( i.e. mappings with order-bounded images), equipped with the natural structure of an $ A $- semi-module. If $ X $ is finite, $ X = \{ x _ {1} \dots x _ {n} \} $, then $ B ( X,A ) $ can be identified with the semi-module $ A ^ {n} $. Actually, $ B ( X,A ) $ is an idempotent semi-ring with respect to the corresponding pointwise operations. Suppose that $ A $ is equipped with a compatible metric; then there is the corresponding uniform metric (cf. also Metric) on $ B ( X,A ) $. Suppose that $ X $ is a topological space and denote by $ C ( X,A ) $ the sub-semi-module of continuous functions in $ B ( X,A ) $; if $ X $ is locally compact (cf. Locally compact space), it is natural to construct the $ A $- semi-module $ C _ {\mathbf{0} } ( X,A ) $ of all continuous $ A $- valued functions with compact supports endowed with the natural topology. There are many other interesting idempotent function spaces, including analogues of the Sobolev spaces (the so-called Maslov spaces).

By the idempotent correspondence principle, many important concepts, ideas and results can be converted from usual functional analysis to idempotent analysis. For example, an idempotent scalar product can be defined as

$$ \left ( \varphi , \psi \right ) = \int\limits _ { X } ^ \oplus {\varphi ( x ) \odot \psi ( x ) } {dx } , $$

where $ \varphi $, $ \psi $ are $ A $- valued functions belonging to an idempotent function space. There are analogues for the well-known theorems of Riesz, Hahn–Banach and Banach–Steinhaus; it is possible to treat dual spaces, operators, and distributions (generalized functions), etc.; see [a1], [a2], [a3], [a4], [a5], [a6]. [a12], [a13] for details.

Integral operators.

See [a4], [a5], [a6], [a9], [a14]. It is natural to construct idempotent analogues of integral operators (cf. Integral operator) in the form

$$ \tag{a3 } K: \varphi ( y ) \mapsto ( K \varphi ) ( x ) = \int\limits _ { Y } ^ \oplus {K ( x, y ) \odot \varphi ( y ) } {dy } , $$

where $ \varphi ( y ) $ is an element of a space of functions defined on a set $ Y $ and taking their values in an idempotent semi-ring $ A $, $ ( K \varphi ) ( x ) $ is an $ A $- valued function on a set $ X $ and $ K ( x, y ) $ is an $ A $- valued function on $ X \times Y $. If $ A = \mathbf R _ { \max } $, then (a3) turns into the formula

$$ ( K \varphi ) ( x ) = \sup _ {y \in Y } \{ K ( x, y ) + \varphi ( y ) \} . $$

Formulas of this type are standard in optimization problems. The operator defined by (a3) is linear over $ A $, i.e. $ K $ is an $ A $- endomorphism of the corresponding semi-module (function space). Actually, every linear operator acting in an idempotent function space and satisfying some natural continuity-type conditions can be presented in the form (a3). This is an analogue of the well-known Schwartz kernel theorem.

Fourier–Legendre transform.

See, e.g., [a1], [a2], [a3], [a4], [a5], [a6]. Let $ A = \mathbf R _ { \max } $, $ G = \mathbf R ^ {n} $; $ G $ is treated as a group. The usual Fourier transform is defined by the formula $ \varphi ( x ) \mapsto {\widetilde \varphi } ( \xi ) = \int _ {G} e ^ {i \xi \cdot x } {\varphi ( x ) } {dx } $, where $ e ^ {i \xi \cdot x } $ is a character of $ G $, that is, a solution of the functional equation $ f ( x + y ) = f ( x ) f ( y ) $. The corresponding idempotent analogue (for the case $ A = \mathbf R _ { \max } $) has the form

$$ f ( x + y ) = f ( x ) \odot f ( y ) = f ( x ) + f ( y ) , $$

so idempotent characters are linear functionals $ x \mapsto \xi \cdot x = \xi _ {1} x _ {1} + \dots + \xi _ {n} x _ {n} $. This leads to the following transform:

$$ \varphi ( x ) \mapsto {\widetilde \varphi } ( \xi ) = $$

$$ = \int\limits _ { G } ^ \oplus {\xi \cdot x \odot \varphi ( x ) } {dx } = \sup _ {x \in G } ( \xi \cdot x + \varphi ( x ) ) . $$

This is the famous Legendre transform. Thus, this transform is an $ \mathbf R _ { \max } $- version of the Fourier transform. Of course, this construction can be generalized to different classes of groups and semi-rings.

Basic equations.

In the framework of idempotent analysis, the Hamilton–Jacobi equation and the Bellman equation and its generalizations can be treated as linear.

In the general case, the Hamilton–Jacobi equation has the form

$$ \tag{a4 } { \frac{\partial S ( x, t ) }{\partial t } } + H \left ( { \frac{\partial S }{\partial x } } , x, t \right ) = 0, $$

where $ H $ is a smooth function on $ \mathbf R ^ {2n } \times [ 0, T ] $. Consider the Cauchy problem for (a4): $ S ( x, 0 ) = S _ {0} ( x ) $, $ 0 \leq t \leq T $, $ x \in \mathbf R ^ {n} $. Denote by $ U _ {t} $ the resolving operator, i.e. the mapping that assigns to each given $ S _ {0} ( x ) $ the solution $ S ( x, t ) $ of this problem at the moment of time $ t $. Then for each $ t $ the mapping $ U _ {t} $ is a linear integral operator over the ( $ \min , + $)- semi-ring $ \mathbf R _ { \min } $ in the corresponding $ \mathbf R _ { \min } $- semi-module. In general, solutions of (a4) are not smooth and the corresponding theory of generalized functions has been constructed.

The situation is similar for the Cauchy problem for the homogeneous Bellman equation

$$ { \frac{\partial S }{\partial t } } + H \left ( { \frac{\partial S }{\partial x } } \right ) = 0, $$

$$ S \mid _ {t = 0 } = S _ {0} ( x ) , $$

where $ H : {\mathbf R ^ {n} } \rightarrow \mathbf R $ is a convex (not strictly) first-order homogeneous function

$$ H ( p ) = \sup _ {( f, g ) \in V } ( f \cdot p + g ) , \quad f \in \mathbf R ^ {n} , g \in \mathbf R, $$

and $ V $ is a compact set in $ \mathbf R ^ {n+1 } $. See [a4], [a5], [a6] for details.

References

[a1]	S.M. Avdoshin, V.V. Belov, V.P. Maslov, "Mathematical aspects of computing media synthesis" MIEM Publ. (1984) (In Russian)
[a2]	V.P. Maslov, "Méthodes opératorielles" , MIR (1987) (In Russian)
[a3]	"Mathematical aspects of computer engineering" V.P. Maslov (ed.) K.A. Volosov (ed.) , MIR (1988) (In Russian)
[a4]	"Idempotent analysis" V.P. Maslov (ed.) S.N. Samborskii (ed.) , Amer. Math. Soc. (1992) (In Russian)
[a5]	V.P. Maslov, V.N. Kolokoltsov, "Idempotent analysis and its applications in optimal control" , Nauka (1994) (In Russian)
[a6]	V.P. Maslov, V.N. Kolokoltsov, "Idempotent analysis and applications" , Kluwer Acad. Publ. (1996) (In Russian)
[a7]	F.L. Baccelli, G. Cohen, G.J. Olsder, J.-P. Quadrat, "Synchronization and linearity: an algebra for discrete event systems" , Wiley (1992)
[a8]	"Discrete Event Systems" G. Cohen (ed.) J.-P. Quadrat (ed.) , Lecture Notes in Control and Information Science , 199 , Springer (1994)
[a9]	P.I. Dudnikov, S.N. Samborskii, "Endomorphisms of semimodules over semirings with an idempotent operation" Math. USSR Izv. , 38 (1991) pp. 91–105 (In Russian)
[a10]	"Idempotency" J. Gunawardena (ed.) , Publ. I. Newton Institute , Cambridge Univ. Press (in press)
[a11]	V.P. Maslov, "New superposition principle for optimization problems" Russian Math. Surveys , 42 (1987) (In Russian)
[a12]	G.L. Litvinov, V.P. Maslov, "Correspondence principle for idempotent calculus and some computer applications" J. Gunawardena (ed.) , Idempotency , Publ. I. Newton Institute , Cambridge Univ. Press (in press)
[a13]	G.L. Litvinov, V.P. Maslov, "Idempotent mathematics: correspondence principle and applications" Russian J. Math. Phys. , 4 : 4 (1996) (In Russian)
[a14]	M.A. Shubin, "Algebraic remarks on idempotent semirings and the kernel theorem in spaces of bounded functions" V.P. Maslov (ed.) S.N. Samborskii (ed.) , Idempotent analysis , Amer. Math. Soc. (1992) pp. 151–166 (In Russian)