Читать книгу Multivalued Maps And Differential Inclusions: Elements Of Theory And Applications - Valeri Obukhovskii - Страница 10

Mathematics is the part of physics in which the experiments are very cheap.

— Vladimir Arnold

Let X and Y be arbitrary sets; a multivalued map (multimap) F of a set X into a set Y is the correspondence which associates to every x ∈ X a nonempty subset F(x) ⊂ Y, called the value (or the image) of x. Denoting by P(Y) the collection of all nonempty subsets of Y we can write this correspondence as

It is clear that the class of multivalued maps includes into itself usual single-valued maps: for them each value consists of a single point.

In the sequel we will denote multimaps by capital letters.

Definition 1.1.1. For any set A ⊂ X the set is called the image of the set A under the multimap F.

Definition 1.1.2. Let F : X → P(Y) be a multimap. The set Γ_F in the Cartesian product X × Y,

is called the graph of the multimap F.

It is worth noting that the concept of a multimap is not something too unusual: after all, we encounter with maps of this kind already in elementary mathematics when trying to invert, for example, such functions as y = x² or y = sin x and others. However, here the “non-singlevaluedness” of the inverse function is perceived, rather, as a negative circumstance: the introduction of such notions as arithmetic value of the square root, or functions of type arcsin, arccos etc. is related precisely with the “liquidation” of this ambiguity.

Consider a few examples of multimaps.

Example 1.1.3. Denote pr₁, pr₂ the projections from X × Y onto X and Y respectively. Each subset Γ ⊂ X × Y such that pr₁ (Γ) = X defines the multimap F : X → P(Y) by the formula . It is clear that the graph Γ_F of the multimap F coincides with Γ.

Example 1.1.4. Define the multimaps of the interval [0, 1] into itself assuming

The graphs of these multimaps are presented in Fig. 1–3.

Fig. 1: Graph F₁

Fig. 2: Graph F₂

Fig. 3: Graph F₃

Denote .

Example 1.1.5. Define the multimap , assuming F(x) = [tan x, +∞) (Fig. 4).

Fig. 4

Example 1.1.6. Define the multimap ,

The graph of the multimap F is shown in the Fig. 5.

Fig. 5

Example 1.1.7. Define the multimap assuming F(x) = [e^−x, 1] (Fig. 6):

Fig. 6

Example 1.1.8. Define the multimap F : ² → P(²) assuming for x = (x₁, x₂) ∈ ²:

The multimap F (but not the graph Γ_F!) is shown in the Fig. 7.

Fig. 7

Example 1.1.9 (Inverse functions). If X, Y are arbitrary sets and f : X → Y is a surjective map then the multimap F : Y → P(X), F(y) = {x|x ∈ X, f(x) = y} is the inverse to f.

Example 1.1.10 (Implicit functions). Let X, Y, Z be arbitrary sets, maps f : X × Y → Z and g : X → Z are such that for every x ∈ X there exists y ∈ Y such that f(x, y) = g(x). The implicit function defined by f and g, in a general case, is the multimap F : X → P(Y), F(x) = {y|y ∈ Y, f (x, y) = g(x)}.

Example 1.1.11. Let X, Y be arbitrary sets, f : X × Y → a function. Let for a certain number r ∈ for every x ∈ X there exists y ∈ Y such that f(x, y) ≤ r. Then the following multimap F_r : X → P(Y) can be defined: F_r(x) = {y|y ∈ Y, f(x, y) ≤ r}.

Example 1.1.12. Generalized dynamical systems.

a) A multivalued translation operator.

Let a set X be the space of states of a certain dynamical system such that being at the initial moment in the state x ∈ X this system may move further along various trajectories. For example, such situation holds if the behavior of the system is governed by a differential equation which does not satisfy the uniqueness of a solution condition or contains a control parameter. A generalized dynamical system is defined if its reachable sets Q(x, t) ⊂ X are given, i.e., the sets of all states into which system can shift in the time t ≥ 0 from the state x ∈ X are indicated. The multimap Q : X × ₊ → P(X) arising in such a manner is called the translation multioperator along the trajectories of the system. Notice that usually the translation multioperator satisfies the natural conditions:

1)Q(x, 0) = {x};

2)Q(x, t₁ + t₂) = Q(Q(x, t₁), t₂) for all x ∈ X; .

b) Multivalued fields of directions.

Consider an important way of setting of a generalized dynamical system. Let ⁿ be the state space of a system and for every state x ∈ Rⁿ the set F(x) ⊂ Rⁿ of velocities with which the system can leave x be given. The multimap F : ⁿ → P(ⁿ) which is defined in such a manner is called the multivalued field (multifield) of directions. A function x : Δ → ⁿ, where Δ ⊂ is a certain interval is called an integral curve of the multifield F if at every (or almost every) point t ∈ Δ it has the derivative x′(t) and

for all (or almost all) t ∈ Δ. Such a relation is called a differential inclusion and the integral curve x is its solution.

A sulution x : Δ → ⁿ is the trajectory of a given multifield of velocities. The collection Q(x, t) of points of such trajectories at the moment t emanating from a given point x ∈ ⁿ defines the translation multioperator Q along the trajectories of the multifield F.

Suppose, for example, that considered generalized dynamical system is a control system whose dynamics is governed by a differential equation

where f : ⁿ × ^m → ⁿ is a map, u(t) ∈ ^m a control parameter. The feedback in this system is described by a multimap U : ⁿ → P(^m) which defines for every given state x ∈ ⁿ a set of admissible controls U(x). Then the multifield of directions for a given system is defined by the formula

We will study differential inclusions, control systems and generalized dynamical systems in Chapters 3 and 4 in more detail.

Example 1.1.13. Metric projection. The following notion arises naturally in the theory of best approximations. Let (X, ϱ) be a metric space; C ⊂ X a nonempty closed subset. For x ∈ X, the set (x) of points y ⊂ C such that ϱ(x, y) = ϱ(x, C) is called the metric projection of x onto C. Notice that the set (x) may be empty. If for every x ∈ X the set C is called proximinal. In this case there arises the multimap : X → P(C) which is also called the metric projection. As examples of proximinal sets may be considered compact sets as well as closed convex subsets of reflexive Banach spaces. Metric projections play an important role in various problems of the approximation theory, geometry of Banach spaces, fixed point theory, variational methods. Extensive literature is devoted to the study of their properties (see, e.g., [175], [380]).

Example 1.1.14. Approximate calculations. Suppose that at each point x of a certain set X some number characteristics y(x) = (y₁(x), . . . , y_n(x)) ∈ ⁿ are measured. By the nonhomogeneity of the set X, absolute errors of measurements δ_i (1 ≤ i ≤ n) depend on x : δ_i = δ_i(x). The multimap F : X → P(ⁿ),

is called the field of values of characteristics.

Example 1.1.15. Theory of games.

(a) Zero-sum games.

Notice that first examples and applications of the notion of a multivalued map were connected with the new science, arising in the thirties-forties of the XX century, the theory of games. This branch of mathematics studies the mathematical models of conflict situations, i.e., such collisions in which the interests of participants do not coincide or are directly opposite. Situations of such kind emerge repeatedly in economics, military or political conflicts and in other spheres of human activity. Their simple and visual models are provided by chess, card games etc., from where the name of the discipline comes from. The base of the theory of games was laid by such prominent scientists as J. von Neumann, J.Nash, O.Morgenstern and others.

From the mathematical point of view the behavior of the participants of a conflict situation (let us call them players) is determined by the choice of a strategies, points from a certain sets of admissible strategies. The selection of a strategy completely defines the behavior of a player at each position which can arise in the process of a game. It is easy to see that even in very simple games there is an enormous number of possible strategies and so their analysis is not a very simple matter. What can be the main principles of such analysis?

For simplicity, let us consider the case of a game with two players, or the two-person game. Let all admissible strategies of the first player form a set X and Y be a set of all admissible strategies of the second player. By a game rule of the first player we mean the assignment to each strategy y ∈ Y of the second player the set of best strategies A(y) ⊂ X from which the first player chooses his strategy. Similarly, the game rule for the second player is defined by the sets of his strongest responses B(x) ⊂ Y to the strategies x ∈ X of the first player. This means that the game rule of the first player may be interpreted as the multimap A : Y → P(X), whereas the game rule of the second player is the multimap B : X → P(Y).

For a simple example of constructing of game rules we can consider a zero-sum or antagonistic game. The game of this type is determined by the payoff function f : X × Y → defined on the Cartesian product of the spaces of strategies. It is supposed that after the choice by the first player of his strategy x ∈ X and by the second player of the strategy y ∈ Y, the payoff of the first player is equal to f(x, y) whereas the payoff of the second player is directly opposite and equals −f(x, y). This means that the first player is trying to maximize the value f(x, y) whereas the second one is making efforts to minimize it. In this case the game rules can be given explicitly:

of course, under condition that pointed out maximums and minimums exist.

Therefore, while the elaboration of suitable strategies, each of the players should analyze the multimaps A : X → P(Y) and B : Y → P(X). The consideration of the question how these multimaps may be used for the searching of optimal strategies for each player is postponed till the fourth chapter.

(b) Games with a complete information.

The language of multivalued maps allows also to simulate some game situations in the following way. Let X be a set of game positions partitioned into n subsets X₁, . . . , X_n in accordance with the number of players. For each player, a certain preference relation is given on X which allows him to compare positions from the point of view of their utility. Let {a} be any singleton, a ∉ X and F : X → P(X ∪ a) a multimap such that a ∈ F(x) implies F(x) = {a}. Let an initial position x₀ ∈ X_i be given, then the i-th player makes his move choosing a position x₁ in the set F(x₀). If x₁ ∈ Xj then the j-th player chooses a position in the set F(x₁) and so on. The game is over if any player chooses a position x such that F(x) = {a}. The goal of the game for an individual player may be formulated as, for example, the obtaining of a position being as profitable as possible at least once during the game.

Example 1.1.16. Mathematical economics.

(a) Multifunctions of productivity and demand.

Let an economic system include n categories of goods whose prices p = (p₁, . . . , p_n) can vary in frameworks of a set Δ ⊂ ⁿ. Let an enterprise–producer has a certain compact set Y ⊂ ⁿ of possible production plans for the output of goods (a technological set). The component y_j of the vector y ∈ Y corresponds to the amount of the j-th commodity produced in accordance with this plan. The profit of the producer after the realization of the plan y equals . Be guided by considerations to obtain the maximal gain under the prices p ∈ Δ, the producer will choose production plans from the set

The multimap Ψ : Δ → P(ⁿ) defined in such a way is called the productive multifunction of the enterprise.

On the other hand, let at given prices p ∈ Δ for the enerprise-customer a compact set X(p) ⊂ ⁿ of consumption vectors be accessible. The component xj of the vector x ∈ X(p) corresponds to the consumption of the j-th product. The preference of one or other consumption vectors is characterized by a certain function u : ⁿ → which is called the utility index. Trying to purchase at the given prices the most useful collection of goods, the customer will make his choice in the set

The multimap Φ : Δ → P(ⁿ) is called the demand multifunction of the customer.

A more detailed description of an economic model of that type and an application of the multimaps techniques to the finding of an equilibrium in it will be carried out in the fourth chapter.

(b) Economic dynamics.

Suppose that in an economic system a vector x_(t) ∈ ⁿ characterizes the collection of goods produced by the moment t during the preceding unit time interval (for example, a year). A part of this collection, y_(t) comes to consumption, whereas the remaining part z_(t) = x_(t) → y_(t) is spend to the accumulation, i.e., serves as the resource for the obtaining a new outcome vector x_(t+1). The pair (y_(t), z_(t)) is called the state of economics at the moment t. By investing the resource z_(t) into accumulation, it is possible to produce by the moment t + 1 one of collections of goods in the frameworks of a certain set B_t(z_(t)) ⊂ ⁿ. The multimap B_t : ⁿ → P(ⁿ) called productive characterizes the technology of the system at the moment t. So, starting from the state of economics y_(t), z_(t) it is possible to obtain by the next moment one of states filling the set

Multimaps A_t : ⁿ × ⁿ → P(ⁿ × ⁿ) play an important role in the study of models of mathematical economics.

Example 1.1.17. Non-smooth optimization.

In contemporary optimization theory it is necessary very often to find the maximums and minimums of functions which are not differentiable. Functions of that kind arise, for example, while the transfer to suprema and infima of families of smooth functions. (So “classical” non-differentiable at zero function y = | x | can be obtained as a supremum of functions y = x and y = −x). For the searching of extrema of such functions, the notion of a derivative must be extended.

Let, for example, E be a finite-dimensional linear space; f : E → a convex functional. For a given x ∈ E the set ∂f(x) ⊂ E of all points ξ ∈ E such that for all v ∈ E we have

is called the subdifferential of a functional f at x.

So, for a given functional instead of an ordinary derivative we have to deal with a modified derivative, expressed by the multimap x → ∂f(x). The classical Fermat rule in this situation takes the following form: if x₀ is a point of a local extremum of a functional f then 0 ∈ ∂f(x₀).

It is easy to see that for the function y = | x | the subdifferential is evaluated by the formula:

Concerning the problems of non-smooth analysis and methods for their solving see the monographs [24], [26], [27], [62], [104], [117], [118], [119], [120], [129], [216], [310], [311], [367] and others.