View source for 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|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. [[#References|[a1]]], [[#References|[a2]]], [[#References|[a3]]], [[#References|[a4]]], [[#References|[a5]]], [[#References|[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|dynamic programming]], discrete-event systems, computer science, discrete mathematics, [[Mathematical logic|mathematical logic]], etc. (see, e.g., [[#References|[a1]]], [[#References|[a2]]], [[#References|[a3]]], [[#References|[a4]]], [[#References|[a5]]], [[#References|[a6]]], [[#References|[a7]]], [[#References|[a8]]], [[#References|[a9]]], [[#References|[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 [[#References|[a11]]], [[#References|[a1]]], [[#References|[a2]]], [[#References|[a3]]], [[#References|[a4]]], [[#References|[a5]]], [[#References|[a6]]]. This is a natural analogue of the so-called superposition principle in quantum mechanics (cf. [[Idempotent superposition principle|Idempotent superposition principle]]). In particular, the [[Bellman equation|Bellman equation]] (which is the main equation in optimal control theory) and its generalizations and the Hamilton–Jacobi equation (cf. also [[Hamilton–Jacobi theory|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|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|Idempotent correspondence principle]]).

==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]]].

==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

<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>

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:

<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>

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.

==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:

i) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002068.png" />;

ii) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/i/i110/i110020/i11002069.png" />;

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" />).

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 operations. 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

<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>

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.

==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

<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>

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

<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>

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.

==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

<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>

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:

<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>

<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>

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.

==Basic equations.==
In the framework of idempotent analysis, the Hamilton–Jacobi equation and the [[Bellman equation|Bellman equation]] and its generalizations can be treated as linear.

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>

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.

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>

<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>

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

<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>

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.

====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>