Difference between revisions of "Idempotent analysis"
(Importing text file) |
m (link) |
||
Line 34: | Line 34: | ||
The simplest <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002077.png" />-semi-module is the direct sum (product) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002078.png" />. The set of all endomorphisms <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002079.png" /> coincides with the non-commutative idempotent semi-ring <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002080.png" /> of all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002081.png" />-valued matrices (cf. [[Idempotent semi-ring|Idempotent semi-ring]], Example 4). Every element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002082.png" /> is "non-negative" : <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002083.png" /> because <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002084.png" />. So, the theory of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002085.png" />-valued matrices is an analogue of the well-known Perron–Frobenius theory of non-negative matrices (see, e.g., [[#References|[a4]]], [[#References|[a5]]], [[#References|[a6]]], [[#References|[a7]]], [[#References|[a9]]]). For example, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002086.png" /> (or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002087.png" />), then for every endomorphism <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002088.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002089.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002090.png" />) there exist a non-trivial sub-semi-module <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002091.png" /> (an "eigenspace" ) and element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002092.png" /> (an "eigenvalue" ) such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002093.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002094.png" />. Similar results are valid for the semi-modules of bounded or continuous functions discussed below. | The simplest <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002077.png" />-semi-module is the direct sum (product) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002078.png" />. The set of all endomorphisms <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002079.png" /> coincides with the non-commutative idempotent semi-ring <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002080.png" /> of all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002081.png" />-valued matrices (cf. [[Idempotent semi-ring|Idempotent semi-ring]], Example 4). Every element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002082.png" /> is "non-negative" : <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002083.png" /> because <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002084.png" />. So, the theory of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002085.png" />-valued matrices is an analogue of the well-known Perron–Frobenius theory of non-negative matrices (see, e.g., [[#References|[a4]]], [[#References|[a5]]], [[#References|[a6]]], [[#References|[a7]]], [[#References|[a9]]]). For example, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002086.png" /> (or <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002087.png" />), then for every endomorphism <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002088.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002089.png" /> (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002090.png" />) there exist a non-trivial sub-semi-module <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002091.png" /> (an "eigenspace" ) and element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002092.png" /> (an "eigenvalue" ) such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002093.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002094.png" />. Similar results are valid for the semi-modules of bounded or continuous functions discussed below. | ||
− | Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002095.png" /> be a set and denote by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002096.png" /> the set of all bounded mappings (functions) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002097.png" /> (i.e. mappings with order-bounded images), equipped with the natural structure of an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002098.png" />-semi-module. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002099.png" /> is finite, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i110020100.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i110020101.png" /> can be identified with the semi-module <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i110020102.png" />. Actually, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i110020103.png" /> is an idempotent semi-ring with respect to the corresponding pointwise | + | Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002095.png" /> be a set and denote by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002096.png" /> the set of all bounded mappings (functions) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002097.png" /> (i.e. mappings with order-bounded images), equipped with the natural structure of an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002098.png" />-semi-module. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002099.png" /> is finite, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i110020100.png" />, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i110020101.png" /> can be identified with the semi-module <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i110020102.png" />. Actually, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i110020103.png" /> is an idempotent semi-ring with respect to the corresponding [[pointwise operation]]s. Suppose that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i110020104.png" /> is equipped with a compatible metric; then there is the corresponding uniform metric (cf. also [[Metric|Metric]]) on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i110020105.png" />. Suppose that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i110020106.png" /> is a [[Topological space|topological space]] and denote by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i110020107.png" /> the sub-semi-module of continuous functions in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i110020108.png" />; if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i110020109.png" /> is locally compact (cf. [[Locally compact space|Locally compact space]]), it is natural to construct the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i110020110.png" />-semi-module <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i110020111.png" /> of all continuous <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i110020112.png" />-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|idempotent correspondence principle]], many important concepts, ideas and results can be converted from usual [[Functional analysis|functional analysis]] to idempotent analysis. For example, an idempotent scalar product can be defined as | By the [[Idempotent correspondence principle|idempotent correspondence principle]], many important concepts, ideas and results can be converted from usual [[Functional analysis|functional analysis]] to idempotent analysis. For example, an idempotent scalar product can be defined as |
Revision as of 22:48, 29 November 2014
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 equipped with binary operations
(addition) and
(multiplication) is called an idempotent semi-ring if
is a semi-ring with idempotent addition (that is,
for all
) and neutral elements
and
(cf. Idempotent semi-ring). Typical (and most common) examples are given by the so-called (
)-semi-ring
and (
)-semi-ring
. Let
be the field of real numbers. Then
with the operations
and
;
,
. Similarly,
with operations
,
; in this case,
,
. The so-called (
)-semi-ring coincides with
with operations
,
;
,
. The well-known Boolean algebra
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 be a locally compact set and
the (
)-idempotent semi-ring. An idempotent analogue of the usual integration can be defined by the formula
![]() | (a1) |
where is a continuous or upper semi-continuous function. This integration is "linear" over
and (a1) can be treated as a limit of Riemann or Lebesgue sums. The set function
, where
, is called a Maslov
-measure on
. This function is completely additive:
. An integral with respect to this
-measure is defined by the formula:
![]() | (a2) |
Let be an arbitrary idempotent semi-ring equipped with its canonical partial order (
if and only if
, cf. Idempotent semi-ring). Suppose that
is boundedly complete, i.e. every bounded subset
has a least upper bound
. In this case, idempotent integration and
-measures can be defined by the same formulas (a1), (a2) for an arbitrary set
and bounded functions
. In particular, if
is the (
)-semi-ring
, then the canonical order is the opposite of the usual ordering of numbers and
with respect to this usual ordering.
Idempotent semi-modules.
Roughly speaking, semi-modules are "linear spaces" over semi-rings. A set is called an idempotent semi-module over an idempotent semi-ring
(or an
-semi-module) if there is a commutative associative idempotent addition
in
with a neutral element
, and a multiplication
of elements from
by elements of
is defined such that the following properties hold:
i) ;
ii) ;
iii) , for all
,
. It is often assumed that
in the sense of the canonical order in
(where
and
).
The simplest -semi-module is the direct sum (product)
. The set of all endomorphisms
coincides with the non-commutative idempotent semi-ring
of all
-valued matrices (cf. Idempotent semi-ring, Example 4). Every element
is "non-negative" :
because
. So, the theory of
-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
(or
), then for every endomorphism
of
(
) there exist a non-trivial sub-semi-module
(an "eigenspace" ) and element
(an "eigenvalue" ) such that
for all
. Similar results are valid for the semi-modules of bounded or continuous functions discussed below.
Let be a set and denote by
the set of all bounded mappings (functions)
(i.e. mappings with order-bounded images), equipped with the natural structure of an
-semi-module. If
is finite,
, then
can be identified with the semi-module
. Actually,
is an idempotent semi-ring with respect to the corresponding pointwise operations. Suppose that
is equipped with a compatible metric; then there is the corresponding uniform metric (cf. also Metric) on
. Suppose that
is a topological space and denote by
the sub-semi-module of continuous functions in
; if
is locally compact (cf. Locally compact space), it is natural to construct the
-semi-module
of all continuous
-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
![]() |
where ,
are
-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
![]() | (a3) |
where is an element of a space of functions defined on a set
and taking their values in an idempotent semi-ring
,
is an
-valued function on a set
and
is an
-valued function on
. If
, then (a3) turns into the formula
![]() |
Formulas of this type are standard in optimization problems. The operator defined by (a3) is linear over , i.e.
is an
-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 ,
;
is treated as a group. The usual Fourier transform is defined by the formula
, where
is a character of
, that is, a solution of the functional equation
. The corresponding idempotent analogue (for the case
) has the form
![]() |
so idempotent characters are linear functionals . This leads to the following transform:
![]() |
![]() |
This is the famous Legendre transform. Thus, this transform is an -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
![]() | (a4) |
where is a smooth function on
. Consider the Cauchy problem for (a4):
,
,
. Denote by
the resolving operator, i.e. the mapping that assigns to each given
the solution
of this problem at the moment of time
. Then for each
the mapping
is a linear integral operator over the (
)-semi-ring
in the corresponding
-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
![]() |
![]() |
where is a convex (not strictly) first-order homogeneous function
![]() |
and is a compact set in
. 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) |
Idempotent analysis. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Idempotent_analysis&oldid=35169