Namespaces
Variants
Actions

Difference between revisions of "Idempotent analysis"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (link)
m (tex encoded by computer)
 
Line 1: Line 1:
 +
<!--
 +
i1100201.png
 +
$#A+1 = 163 n = 0
 +
$#C+1 = 163 : ~/encyclopedia/old_files/data/I110/I.1100020 Idempotent analysis,
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
 +
 +
{{TEX|auto}}
 +
{{TEX|done}}
 +
 
''idempotent calculus''
 
''idempotent calculus''
  
Line 10: Line 22:
  
 
==Basic idempotent semi-rings.==
 
==Basic idempotent semi-rings.==
A set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i1100201.png" /> equipped with binary operations <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i1100202.png" /> (addition) and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i1100203.png" /> (multiplication) is called an idempotent semi-ring if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i1100204.png" /> is a [[Semi-ring|semi-ring]] with idempotent addition (that is, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i1100205.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i1100206.png" />) and neutral elements <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i1100207.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i1100208.png" /> (cf. [[Idempotent semi-ring|Idempotent semi-ring]]). Typical (and most common) examples are given by the so-called (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i1100209.png" />)-semi-ring <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002010.png" /> and (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002011.png" />)-semi-ring <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002012.png" />. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002013.png" /> be the field of real numbers. Then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002014.png" /> with the operations <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002015.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002016.png" />; <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002017.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002018.png" />. Similarly, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002019.png" /> with operations <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002020.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002021.png" />; in this case, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002022.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002023.png" />. The so-called (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002024.png" />)-semi-ring coincides with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002025.png" /> with operations <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002026.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002027.png" />; <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002028.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002029.png" />. The well-known [[Boolean algebra|Boolean algebra]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002030.png" /> is an example of a finite idempotent semi-ring. Other interesting examples and constructions can be found in [[#References|[a1]]], [[#References|[a2]]], [[#References|[a3]]], [[#References|[a4]]], [[#References|[a5]]], [[#References|[a6]]], [[#References|[a7]]], [[#References|[a8]]], [[#References|[a9]]], [[#References|[a10]]].
+
A set $  A $
 +
equipped with binary operations $  \oplus $(
 +
addition) and $  \odot $(
 +
multiplication) is called an idempotent semi-ring if $  A $
 +
is a [[Semi-ring|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|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|Boolean algebra]] $  \{ \mathbf{0} , \mathbf{1} \} $
 +
is an example of a finite idempotent semi-ring. Other interesting examples and constructions can be found in [[#References|[a1]]], [[#References|[a2]]], [[#References|[a3]]], [[#References|[a4]]], [[#References|[a5]]], [[#References|[a6]]], [[#References|[a7]]], [[#References|[a8]]], [[#References|[a9]]], [[#References|[a10]]].
  
 
==Idempotent integration and Maslov measures.==
 
==Idempotent integration and Maslov measures.==
See also [[#References|[a1]]], [[#References|[a2]]], [[#References|[a3]]], [[#References|[a4]]], [[#References|[a5]]], [[#References|[a6]]]. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002031.png" /> be a locally compact set and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002032.png" /> the (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002033.png" />)-idempotent semi-ring. An idempotent analogue of the usual integration can be defined by the formula
+
See also [[#References|[a1]]], [[#References|[a2]]], [[#References|[a3]]], [[#References|[a4]]], [[#References|[a5]]], [[#References|[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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002034.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a1)</td></tr></table>
+
$$ \tag{a1 }
 +
\int\limits _ { X } ^  \oplus  {\varphi ( x ) }  {dx } = \sup  _ {x \in X } \varphi ( x ) ,
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002035.png" /> is a continuous or upper [[Semi-continuous function|semi-continuous function]]. This integration is  "linear"  over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002036.png" /> and (a1) can be treated as a limit of Riemann or Lebesgue sums. The set function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002037.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002038.png" />, is called a Maslov <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002040.png" />-measure on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002041.png" />. This function is completely additive: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002042.png" />. An integral with respect to this <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002043.png" />-measure is defined by the formula:
+
where $  \varphi : X \rightarrow A $
 +
is a continuous or upper [[Semi-continuous function|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:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002044.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a2)</td></tr></table>
+
$$ \tag{a2 }
 +
\int\limits _ { X } ^  \oplus  {\psi ( x ) }  {dm _  \varphi  } = \int\limits _ { X } ^  \oplus  {\psi ( x ) \odot \varphi ( x ) }  {dx } .
 +
$$
  
Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002045.png" /> be an arbitrary idempotent semi-ring equipped with its canonical partial order (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002046.png" /> if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002047.png" />, cf. [[Idempotent semi-ring|Idempotent semi-ring]]). Suppose that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002048.png" /> is boundedly complete, i.e. every bounded subset <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002049.png" /> has a least upper bound <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002050.png" />. In this case, idempotent integration and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002051.png" />-measures can be defined by the same formulas (a1), (a2) for an arbitrary set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002052.png" /> and bounded functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002053.png" />. In particular, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002054.png" /> is the (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002055.png" />)-semi-ring <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002056.png" />, then the canonical order is the opposite of the usual ordering of numbers and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002057.png" /> with respect to this usual ordering.
+
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|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.==
 
==Idempotent semi-modules.==
Roughly speaking, semi-modules are  "linear spaces"  over semi-rings. A set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002058.png" /> is called an idempotent semi-module over an idempotent semi-ring <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002059.png" /> (or an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002061.png" />-semi-module) if there is a commutative associative idempotent addition <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002062.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002063.png" /> with a neutral element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002064.png" />, and a multiplication <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002065.png" /> of elements from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002066.png" /> by elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002067.png" /> is defined such that the following properties hold:
+
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) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002068.png" />;
+
i) $  ( \lambda \odot \mu ) \odot v = \lambda \odot ( \mu \odot v ) $;
  
ii) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002069.png" />;
+
ii) $  \lambda \odot ( v _ {1} \oplus v _ {2} ) = \lambda \odot v _ {1} \oplus \lambda _ {2} \odot v _ {2} $;
  
iii) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002070.png" />, for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002071.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002072.png" />. It is often assumed that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002073.png" /> in the sense of the canonical order in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002074.png" /> (where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002075.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002076.png" />).
+
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 <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 $  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|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., [[#References|[a4]]], [[#References|[a5]]], [[#References|[a6]]], [[#References|[a7]]], [[#References|[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 <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).
+
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 operation]]s. Suppose that $  A $
 +
is equipped with a compatible metric; then there is the corresponding uniform metric (cf. also [[Metric|Metric]]) on $  B ( X,A ) $.  
 +
Suppose that $  X $
 +
is a [[Topological space|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|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|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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i110020113.png" /></td> </tr></table>
+
$$
 +
\left ( \varphi , \psi \right ) = \int\limits _ { X } ^  \oplus  {\varphi ( x ) \odot \psi ( x ) }  {dx } ,
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i110020114.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i110020115.png" /> are <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i110020116.png" />-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 [[#References|[a1]]], [[#References|[a2]]], [[#References|[a3]]], [[#References|[a4]]], [[#References|[a5]]], [[#References|[a6]]]. [[#References|[a12]]], [[#References|[a13]]] for details.
+
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 [[#References|[a1]]], [[#References|[a2]]], [[#References|[a3]]], [[#References|[a4]]], [[#References|[a5]]], [[#References|[a6]]]. [[#References|[a12]]], [[#References|[a13]]] for details.
  
 
==Integral operators.==
 
==Integral operators.==
 
See [[#References|[a4]]], [[#References|[a5]]], [[#References|[a6]]], [[#References|[a9]]], [[#References|[a14]]]. It is natural to construct idempotent analogues of integral operators (cf. [[Integral operator|Integral operator]]) in the form
 
See [[#References|[a4]]], [[#References|[a5]]], [[#References|[a6]]], [[#References|[a9]]], [[#References|[a14]]]. It is natural to construct idempotent analogues of integral operators (cf. [[Integral operator|Integral operator]]) in the form
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i110020117.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a3)</td></tr></table>
+
$$ \tag{a3 }
 +
K: \varphi ( y ) \mapsto ( K \varphi ) ( x ) = \int\limits _ { Y } ^  \oplus  {K ( x, y ) \odot \varphi ( y ) }  {dy } ,
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i110020118.png" /> is an element of a space of functions defined on a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i110020119.png" /> and taking their values in an idempotent semi-ring <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i110020120.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i110020121.png" /> is an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i110020122.png" />-valued function on a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i110020123.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i110020124.png" /> is an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i110020125.png" />-valued function on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i110020126.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i110020127.png" />, then (a3) turns into the formula
+
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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i110020128.png" /></td> </tr></table>
+
$$
 +
( 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i110020129.png" />, i.e. <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i110020130.png" /> is an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i110020131.png" />-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.
+
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.==
 
==Fourier–Legendre transform.==
See, e.g., [[#References|[a1]]], [[#References|[a2]]], [[#References|[a3]]], [[#References|[a4]]], [[#References|[a5]]], [[#References|[a6]]]. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i110020132.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i110020133.png" />; <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i110020134.png" /> is treated as a [[Group|group]]. The usual [[Fourier transform|Fourier transform]] is defined by the formula <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i110020135.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i110020136.png" /> is a character of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i110020137.png" />, that is, a solution of the functional equation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i110020138.png" />. The corresponding idempotent analogue (for the case <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i110020139.png" />) has the form
+
See, e.g., [[#References|[a1]]], [[#References|[a2]]], [[#References|[a3]]], [[#References|[a4]]], [[#References|[a5]]], [[#References|[a6]]]. Let $  A = \mathbf R _ { \max  } $,  
 +
$  G = \mathbf R  ^ {n} $;  
 +
$  G $
 +
is treated as a [[Group|group]]. The usual [[Fourier transform|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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i110020140.png" /></td> </tr></table>
+
$$
 +
f ( x + y ) = f ( x ) \odot f ( y ) = f ( x ) + f ( y ) ,
 +
$$
  
so idempotent characters are linear functionals <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i110020141.png" />. This leads to the following transform:
+
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:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i110020142.png" /></td> </tr></table>
+
$$
 +
\varphi ( x ) \mapsto {\widetilde \varphi  } ( \xi ) =
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i110020143.png" /></td> </tr></table>
+
$$
 +
=  
 +
\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|Legendre transform]]. Thus, this transform is an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i110020144.png" />-version of the Fourier transform. Of course, this construction can be generalized to different classes of groups and semi-rings.
+
This is the famous [[Legendre transform|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.==
 
==Basic equations.==
Line 71: Line 231:
 
In the general case, the Hamilton–Jacobi equation has the form
 
In the general case, the Hamilton–Jacobi equation has the form
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i110020145.png" /></td> <td valign="top" style="width:5%;text-align:right;">(a4)</td></tr></table>
+
$$ \tag{a4 }
 +
{
 +
\frac{\partial  S ( x, t ) }{\partial  t }
 +
} + H \left ( {
 +
\frac{\partial  S }{\partial  x }
 +
} , x, t \right ) = 0,
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i110020146.png" /> is a smooth function on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i110020147.png" />. Consider the [[Cauchy problem|Cauchy problem]] for (a4): <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i110020148.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i110020149.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i110020150.png" />. Denote by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i110020151.png" /> the resolving operator, i.e. the mapping that assigns to each given <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i110020152.png" /> the solution <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i110020153.png" /> of this problem at the moment of time <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i110020154.png" />. Then for each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i110020155.png" /> the mapping <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i110020156.png" /> is a linear integral operator over the (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i110020157.png" />)-semi-ring <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i110020158.png" /> in the corresponding <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i110020159.png" />-semi-module. In general, solutions of (a4) are not smooth and the corresponding theory of generalized functions has been constructed.
+
where $  H $
 +
is a smooth function on $  \mathbf R ^ {2n } \times [ 0, T ] $.  
 +
Consider the [[Cauchy problem|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
 
The situation is similar for the Cauchy problem for the homogeneous Bellman equation
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i110020160.png" /></td> </tr></table>
+
$$
 +
{
 +
\frac{\partial  S }{\partial  t }
 +
} + H \left ( {
 +
\frac{\partial  S }{\partial  x }
 +
} \right ) = 0,
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i110020161.png" /></td> </tr></table>
+
$$
 +
S \mid  _ {t = 0 }  = S _ {0} ( x ) ,
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i110020162.png" /> is a convex (not strictly) first-order homogeneous function
+
where $  H : {\mathbf R  ^ {n} } \rightarrow \mathbf R $
 +
is a convex (not strictly) first-order homogeneous function
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i110020163.png" /></td> </tr></table>
+
$$
 +
H ( p ) = \sup  _ {( f, g ) \in V } ( f \cdot p + g ) , \quad f \in \mathbf R  ^ {n} ,  g \in \mathbf R,
 +
$$
  
and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i110020164.png" /> is a compact set in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i110020165.png" />. See [[#References|[a4]]], [[#References|[a5]]], [[#References|[a6]]] for details.
+
and $  V $
 +
is a compact set in $  \mathbf R ^ {n+1 } $.  
 +
See [[#References|[a4]]], [[#References|[a5]]], [[#References|[a6]]] for details.
  
 
====References====
 
====References====
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  S.M. Avdoshin,  V.V. Belov,  V.P. Maslov,  "Mathematical aspects of computing media synthesis"  ''MIEM Publ.''  (1984)  (In Russian)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  V.P. Maslov,  "Méthodes opératorielles" , MIR  (1987)  (In Russian)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  "Mathematical aspects of computer engineering"  V.P. Maslov (ed.)  K.A. Volosov (ed.) , MIR  (1988)  (In Russian)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  "Idempotent analysis"  V.P. Maslov (ed.)  S.N. Samborskii (ed.) , Amer. Math. Soc.  (1992)  (In Russian)</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  V.P. Maslov,  V.N. Kolokoltsov,  "Idempotent analysis and its applications in optimal control" , Nauka  (1994)  (In Russian)</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  V.P. Maslov,  V.N. Kolokoltsov,  "Idempotent analysis and applications" , Kluwer Acad. Publ.  (1996)  (In Russian)</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  F.L. Baccelli,  G. Cohen,  G.J. Olsder,  J.-P. Quadrat,  "Synchronization and linearity: an algebra for discrete event systems" , Wiley  (1992)</TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top">  "Discrete Event Systems"  G. Cohen (ed.)  J.-P. Quadrat (ed.) , ''Lecture Notes in Control and Information Science'' , '''199''' , Springer  (1994)</TD></TR><TR><TD valign="top">[a9]</TD> <TD valign="top">  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)</TD></TR><TR><TD valign="top">[a10]</TD> <TD valign="top">  "Idempotency"  J. Gunawardena (ed.) , ''Publ. I. Newton Institute'' , Cambridge Univ. Press  (in press)</TD></TR><TR><TD valign="top">[a11]</TD> <TD valign="top">  V.P. Maslov,  "New superposition principle for optimization problems"  ''Russian Math. Surveys'' , '''42'''  (1987)  (In Russian)</TD></TR><TR><TD valign="top">[a12]</TD> <TD valign="top">  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)</TD></TR><TR><TD valign="top">[a13]</TD> <TD valign="top">  G.L. Litvinov,  V.P. Maslov,  "Idempotent mathematics: correspondence principle and applications"  ''Russian J. Math. Phys.'' , '''4''' :  4  (1996)  (In Russian)</TD></TR><TR><TD valign="top">[a14]</TD> <TD valign="top">  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)</TD></TR></table>
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  S.M. Avdoshin,  V.V. Belov,  V.P. Maslov,  "Mathematical aspects of computing media synthesis"  ''MIEM Publ.''  (1984)  (In Russian)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  V.P. Maslov,  "Méthodes opératorielles" , MIR  (1987)  (In Russian)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  "Mathematical aspects of computer engineering"  V.P. Maslov (ed.)  K.A. Volosov (ed.) , MIR  (1988)  (In Russian)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  "Idempotent analysis"  V.P. Maslov (ed.)  S.N. Samborskii (ed.) , Amer. Math. Soc.  (1992)  (In Russian)</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  V.P. Maslov,  V.N. Kolokoltsov,  "Idempotent analysis and its applications in optimal control" , Nauka  (1994)  (In Russian)</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  V.P. Maslov,  V.N. Kolokoltsov,  "Idempotent analysis and applications" , Kluwer Acad. Publ.  (1996)  (In Russian)</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  F.L. Baccelli,  G. Cohen,  G.J. Olsder,  J.-P. Quadrat,  "Synchronization and linearity: an algebra for discrete event systems" , Wiley  (1992)</TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top">  "Discrete Event Systems"  G. Cohen (ed.)  J.-P. Quadrat (ed.) , ''Lecture Notes in Control and Information Science'' , '''199''' , Springer  (1994)</TD></TR><TR><TD valign="top">[a9]</TD> <TD valign="top">  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)</TD></TR><TR><TD valign="top">[a10]</TD> <TD valign="top">  "Idempotency"  J. Gunawardena (ed.) , ''Publ. I. Newton Institute'' , Cambridge Univ. Press  (in press)</TD></TR><TR><TD valign="top">[a11]</TD> <TD valign="top">  V.P. Maslov,  "New superposition principle for optimization problems"  ''Russian Math. Surveys'' , '''42'''  (1987)  (In Russian)</TD></TR><TR><TD valign="top">[a12]</TD> <TD valign="top">  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)</TD></TR><TR><TD valign="top">[a13]</TD> <TD valign="top">  G.L. Litvinov,  V.P. Maslov,  "Idempotent mathematics: correspondence principle and applications"  ''Russian J. Math. Phys.'' , '''4''' :  4  (1996)  (In Russian)</TD></TR><TR><TD valign="top">[a14]</TD> <TD valign="top">  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)</TD></TR></table>

Latest revision as of 22:11, 5 June 2020


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)
How to Cite This Entry:
Idempotent analysis. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Idempotent_analysis&oldid=35169
This article was adapted from an original article by G.L. Litvinov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article