Printer Friendly

Multiresolution Analysis Applied to the Monge-Kantorovich Problem.

1. Introduction

The optimal transport problem was first formulated by Monge in 1781 and concerned finding the optimal way in the sense of minimal transportation cost of moving a pile of soil from one site to another. This problem was given a modern formulation in the work of Kantorovich in 1942 and so is now known as the Monge-Kantorovich problem.

On the other hand, a big advantage over schemes of approximation was given in the seminal article [1]; it introduced approximation schemes for infinite linear program; in particular, it showed that under suitable assumptions the program's optimum value can be finite-dimensional linear programs and that, in addition, every accumulation point of a sequence of optimal solutions for the approximating programs is an optimal solution for the original problem. An example given in this article is the Monge-Kantorovich mass transfer (MK) problem on the space itself, where the underlying space is compact.

In [2], a general method of approximation for the MK problem is given, where X and Y are Polish spaces; however, this method is noneasier implementation. Later, in [3], a scheme of approximation of MK problem is provided, which consists in giving a sequence of finite transportation problems underlying original MK problem (the space is compact); nevertheless, a general procedure is given, but the examples are in a two-dimensional cube and use the dyadic partition of the cube for approximation. Our objective is to give other families to approximate this kind of problems, based on Haar type multiresolution analysis (MRA). The advantage of using this technique is that we select a multiresolution analysis that is constructed according to the symmetries of the underlying space. Therefore, the new schemes of approximation take a lot of characteristics of the space into consideration. Note that the dyadic partition of the cube is a particular case of the MRA type Haar using translations and dilations of the underlying space.

The MRA is an important method to approximate functions in different context (signal processing, differential equations, etc.). In particular, we focus on Haar type MRA on [R.sup.n]; the constructions of this kind of MRA are associated with the symmetries of the spaces; thus the approximations are related to the geometrical properties of the space. In this construction, the symmetries that we use are general dilations, rotations, reflections, translations, and so forth; for more details, see [4-6].

The main objective of this paper is giving a scheme of approximation of the MK problem based on the symmetries of the underlying spaces. We take a Haar type MRA constructed according to the geometry of our spaces. Thus, applying the Haar type MRA based on symmetries to the MK problem, we obtain a sequence of transportation problems that approximate the original MK problem for each level of MRA. Moreover, the optimal solutions of each level solution converge in the weak sense to the optimal solution of original problem.

This paper is organized as follows. In Section 2, we introduce the basic elements of the Haar type multiresolution analysis and we give some examples of this kind of MRA. In Section 3, we present the approximation of probability measures using Haar type MRA. In Section 5, we apply the Haar type multiresolution analysis to MK problem for each level of this MRA; thus for each level, this new problem is equivalent to transport problem. Moreover, we prove that the optimal solution of MK problems is equal to the limit of the optimal solutions of underlying transportation problems when the level of the MRA goes to infinity. Finally, we give an illustrative example of this method.

2. Haar Type Multiresolution Analysis

We introduce the basic concepts of Haar type multiresolution analysis, following Grochenig and Madych in [4] and Guo et al. in [5]. Similar results have been obtained independently by Krishtal et al. to be published in [6].

Let [GAMMA] be a lattice such that [GAMMA] = M[Z.sup.n] for any M [member of] G[L.sub.n](R). The classical multiresolution analysis (MRA) associated with a sequence of dilations [{[a.sup.j]}.sub.j[member of]z] = A, where [absolute value of det a] [less than or equal to] 1, is a sequence [{[V.sub.j]}.sub.j [member of] Z] of closed subspaces of [L.sup.2]([R.sup.n]), which satisfies the following conditions:

(i) [V.sub.k] c [V.sub.k+1].

(ii) [bar.[[union].sub.j[member of] Z] [V.sub.j] = [L.sup.2]([R.sup.n]).

(iii) [[intersection].sub.j[member of]Z] [V.sub.j] = {0}.

(iv) [mathematical expression not reproducible].

(v) There exists [phi] [member of] [V.sub.0] such that {[T.sub.[gamma]], [gamma] [member of] [GAMMA], is an orthonormal basis for [V.sub.0].

Let B be a finite subgroup of G[L.sub.n](R) such that [absolute value of det b] = 1 for all b [member of] B and [GAMMA] = B([GAMMA]). The operator generator by the dilations [D.sub.b], b [member of] B, and the translations [T.sub.[gamma]], [gamma] [member of] [GAMMA] form a group. The relation

[mathematical expression not reproducible]. (1)

allows us to define the operation to B x [GAMMA] given by

(c, [tau]) x (b, [gamma]) = (cb, [b.sup.-1] [tau] + [gamma]) (2)

and we obtain a new group denoted by B[GAMMA]. The B[GAMMA]-invariant spaces are the closed subspaces V of [L.sup.2]([R.sup.n]) such that [D.sub.b][T.sub.[gamma]] f [member of] V whenever f [member of] V, b [member of] B, and [gamma] [member of] [GAMMA]. This leads us to the following version of (v):

(v') There exists [phi] [member of] [V.sub.0] such that {[D.sub.b][T.sub.[gamma]] [phi]}, b [member of] B and [gamma] [member of] [GAMMA], is an orthonormal basis for [V.sub.0].

In consequence, we have the following concept.

Definition 1. Let A = [{[a.sup.j]}.sub.i [member of] Z] be dilatation set, let B be a finite subgroup of G[L.sub.n](R) with [absolute value of det b] = 1, and let [GAMMA] be a complete lattice such that [GAMMA] = B([GAMMA]). The multiresolution analysis associated with the dilation set A and the group B or AB-MRA is a collection [{[V.sub.j]}.sub.j[member of]Z] of closed subspaces of [L.sup.2]([R.sup.n]), which satisfies conditions (i), (ii), (iii), (iv), and (v').

The classical MRA is considered as an AB-MRA when B is the trivial group. Note that the space [V.sub.0] is not generated by the [GAMMA]-translations of the single scaling function [phi]; however, the relation [D.sub.b][T.sub.[gamma]] [phi] = [T.sub.b[gamma]] [D.sub.b][phi] and the conditions B([GAMMA]) = [GAMMA] imply that the functions [D.sub.b][phi], with b [member of] B, are the generators of [V.sub.0]. Also, we have the following set:

[[GAMMA].sup.j] = {[a.sup.j][gamma] : [gamma] [member of] [gamma]} (3)

Note that [[GAMMA].sup.j] [subset] [[GAMMA].sup.j+1] and B[[GAMMA].sup.j] = [GAMMA].

We consider the scaling function [phi] = E[[chi].sub.[DELTA]], where [[chi].sub.[DELTA]] is the characteristic function of [DELTA] [subset] [R.sup.n], E [member of] R, and [parallel][phi][parallel][sub.2] = 1. The region [DELTA] satisfies

[mathematical expression not reproducible] (4)

where int [[DELTA].sub.[alpha]] [intersection] int [[DELTA].sub.[alpha]'] = 0 for [alpha] [not equal to] [alpha]' and [[DELTA].sub.[alpha]] is the action of [alpha] = (b, [gamma]) on [DELTA]. In addition, the symbol [[DELTA].sup.j.sub.[alpha]] denotes the translation and scaling of the region [DELTA] by [alpha] and [a.sup.j], respectively. Thus, the function [mathematical expression not reproducible] is denoted by [[phi].sup.j.sub.[alpha]]. And so we have the following relation:

[mathematical expression not reproducible]. (5)

Finally, we define [P.sup.j] as the orthogonal projection from [L.sup.2]([R.sup.n]) to [V.sub.j] which is given by

[P.sub.j]f = [summation over ([alpha][member of]B[GAMMA])] <f, [[phi].sup.j.sub.[alpha]]> [[phi].sup.j.sub.[alpha]] (6)

for all f [member of] [L.sup.2]([R.sup.n]).

We show some examples of the multiresolution analysis associated with the dilation set A and the finite group B:

(1) We take a matrix [mathematical expression not reproducible], of symmetries of unit square; thus,

[mathematical expression not reproducible], (7)

and [b.sub.i] = -[b.sub.i-4] for 4 [less than or equal to] i [less than or equal to] 7. Let [[DELTA].sub.0] be the triangular region with vertices in (0, 0), (1/2,0), and (1/2,1/2); we denote [mathematical expression not reproducible], then the system

{[D.sub.b] [T.sub.k] [phi] : b [member of] B, k [member of] [Z.sup.2]} (8)

is an orthogonal basis for its closed span [V.sub.0]. The space [V.sub.0] is the subspace of [L.sup.2]([R.sup.2]), consisting of all square integrable functions that are constant on each [Z.sup.2]-translate of the triangles [[DELTA].sub.i], 1 [less than or equal to] i [less than or equal to] 7. Thus, the spaces [mathematical expression not reproducible], consist of all functions in [L.sup.2]([R.sup.2]), which are constant in each [q.sup.-j] [Z.sup.2]-translate of the triangles [q.sup.-1] [[DELTA].sub.i], 1 [less than or equal to] i [less than or equal to] 7, in consequence [V.sub.j] [subset] [V.sub.j+1]. Hence, {[V.sub.j]} is an AB-MRA with [phi] as a scaling function.

Figure 1 is reproduced from Krishtal et al. (2007) [under the Creative Commons Attribution License/public domain].

(2) Let B be the group generated by the matrix [mathematical expression not reproducible]. This group has order of 6 and is the counter-clockwise rotation by [pi]/3 radians. Consider the hexagon with vertices in set

[mathematical expression not reproducible]. (9)

Let [[DELTA].sub.0] be the triangle with vertices in (0, 0), ([square root of 3]/2, 0), and ([square root of 3]/4, 3/4). We define [mathematical expression not reproducible]. The set of all functions that are constant on [GAMMA]-translates of triangles [[DELTA].sub.i], 0 [less than or equal to] i [less than or equal to] 5, is the space [V.sub.0] [subset] [L.sup.2] ([R.sup.2]). Moreover, the elements of [GAMMA] translate the center of the hexagon to the point of [GAMMA], and so we have a partition of [R.sup.2]. Let [mathematical expression not reproducible]. The MRA {[V.sub.j]} is obtained by the system

[mathematical expression not reproducible] (10)

where the spaces [V.sub.j] are [q.sup.-j]-dilatation of [V.sub.0], for j [member of] Z. Figure 2 can be found in [6].

3. Approximation of Measures Using Multiresolution Analysis

3.1. Absolutely Continuous Measures with respect to Lebesgue Measures. We consider the following conditions:

([A.sub.1]) X is a compact subset of [R.sup.n].

([A.sub.2]) The measure [mu] is absolutely continuous with respect to [lambda], where [lambda] is the Lebesgue measure.

Condition ([A.sub.2]) guarantees the existence of functions f [member of] [L.sup.1](X), where f is the Radon-Nikodym derivative with respect to Lebesgue measure [lambda].

In this analysis, we also assume the following extra condition:

(A3) The functions f also belong in [L.sup.2]([X.sub.k]).

Notice that

f [member of] [L.sup.1] (X) [intersection] [L.sup.2] (X) [subset] [L.sup.2] ([R.sup.n]). (11)

Let {[V.sub.j]} be an AB-MRA on [R.sup.n]; the elements of {[V.sub.j]} are given by scaling functions [phi] = [E.sub.1] [[chi].sub.[DELTA]], the latice [GAMMA], finite group [B.sub.1], and dilatation A = {[a.sup.j.sub.1]}.

Remark 2. Note that the classical multiresolution analysis of Haar on [L.sup.2]([R.sup.2]) is a particular case of AB-MRA on [R.sup.2], where the complete lattice is [GAMMA] = [Z.sup.2], the group B is trivial, and the dilation associated is A = {[2.sup.-j] (1,1)}. In this case, we have that scaling function is [[phi].sub.[DELTA]], where [DELTA] = [0,1] x [0,1] is the fundamental domain associated with the action of [GAMMA] on [R.sup.2].

We denote by [P.sub.j] the projection from [L.sup.2]([R.sup.n]) into [V.sub.j], which is given by

[P.sub.j] f = [summation over ([alpha][member of](B[GAMMA]).sup.j]) <f, [[phi].sup.j.sub.[alpha]]> [[phi].sup.j.sub.[alpha]] (12)

for all f [member of] [L.sup.2]([R.sup.n]). Moreover, if the function f has support in X, then the above sum is finite, since X is compact.

From now on, we shall only functions with support in the compact set X and we have [L.sup.2](X) [subset] [L.sup.2]([R.sup.n]); that is, each function f [member of] [L.sup.2](X) can be considered in [L.sup.2] ([R.sup.n]), where f(x) = 0 if x [not member of] X.

We know that the AB-MRA is dense in [L.sup.2](X); thus we have that

[[parallel][p.sup.j] f - f [parallel].sub.2] [right arrow] 0, when j [right arrow] [infinity] (13)

Using the fact that X is compact, we obtain that

[mathematical expression not reproducible] (14)

From the above equation, we define the approximation of the measure to the level j by

d[[mu].sub.j] = [P.sub.j]f d[lambda], (15)

which are measures in X for each j. Now we want to prove that these measures are probability measures.

Definition 3. The expectation E with respect to Lebesgue measure [lambda] of function f is defined by

[mathematical expression not reproducible], (16)

where f is a Lebesgue measurable function. Also, the conditional expectation of f given A, with A being a Lebesgue measurable set, is defined by E[f | A] = E[f x [[chi].sub.A]].

In particular, the expectation on the Lebesgue measure [lambda] satisfies the following property.

Theorem 4. Consider that j [member of] Z is fixed and f [member of] [L.sup.2]([R.sup.n]). Then E[[P.sub.j]f] = E[f], where [P.sub.j] is the projection of the level j associated with AB-MRA {[V.sub.j]}.

Proof. We take f [member of] [L.sup.2]([R.sup.n]); now we calculate E[[P.sub.j]f]; thus

[mathematical expression not reproducible] (17)

We have that the functions [mathematical expression not reproducible] is the translation and dilation of the fundamental region [DELTA] and [E.sub.j] = [lambda][([[DELTA].sup.j.sub.[alpha]]).sup.-1/2]; this value does not depend on a. From this, we have that

[mathematical expression not reproducible]. (18)

Using the above equations, we have that

[mathematical expression not reproducible]. (19)

Moreover, using the fact that [[DELTA].sup.j.sub.[alpha]] [intersection] [[DELTA].sup.j.sub.[beta]] = 0 for [alpha] = [beta], it is clear that

[mathematical expression not reproducible]. (20)

As immediate consequence of the previous theorem, we get the following result.

Corollary 5. We suppose that the measure [mu] on X satisfies ([A.sub.1])-([A.sub.2]); then the sequences of probability measures {[[mu].sup.j]} [subset] [M.sup.+](X) given by (15) converge to [mu] in [L.sup.1] and [L.sup.2] sense.

3.2. Non-Absolutely-Continuous Measures with respect to Lebesgue Measure. Now, we consider that [mu] is a probability measure on the compact set X, which is unnecessarily absolutely continuous measure with respect to Lebesgue measure [lambda]. Note that each element of sequence (15) can be written by

[mathematical expression not reproducible] (21)

for all Borel measurable sets U on X. Moreover, these approximations are well defined for every measure [mu] on X.

Definition 6. Let {[[mu].sub.n]; n [greater than or equal to] 0} be a sequence of probability measures on a metric space (X, d). We say that converges weakly to [mu] and denote [mathematical expression not reproducible] for all bounded continuous functions f on M, where [mu](f) = [[integral].sub.M] f d[mu].

Theorem 7. Given a measure p on the compact set X, the sequence of measures {[[mu].sup.j]}} on X defined in (21) converge weakly to measure [mu].

Proof. Let f : X [right arrow] R be a continuous and bounded real function. From the fact that X is compact, we obtain that f is absolutely continuous function on X; thus, given [member of] > 0, there exists [delta] > 0 such that

[absolute value of x - y] < [delta] implies [absolute value of f (x) - f (y)] < [epsilon]/2 (22)

We take [j.sub.0] [member of] Z such that for all x,y [member of] [[DELTA].sup.j.sub.[alpha]] implies [absolute value of x- y] < [delta] for all j [greater than or equal to] [j.sub.0] and [alpha] [member of] B[GAMMA]. Moreover, we know that there exist [[alpha].sub.1], ..., [[alpha].sub.r] [member of] B[GAMMA] such that

[mathematical expression not reproducible]. (23)

In consequence, we obtain the following relations:

[mathematical expression not reproducible]; (24)

we take an element [mathematical expression not reproducible] to obtain the following relations:

[mathematical expression not reproducible]. (25)

Therefore,

[mathematical expression not reproducible]. (26)

4. Discretization of the Monge-Kantorovich Problem Using Multiresolution Analysis

Let M(X x Y) be the linear space of finite signed on X x Y and let [M.sup.+] (X x Y) be the set of all nonnegative measures in M(X x Y). Given [mu] [member of] M(X x Y), we denote by [[PI].sub.1][mu] and [[PI].sub.2][mu] the marginal of [mu] on X and Y, respectively; that is,

[mathematical expression not reproducible] (27)

for all sets A and B, such that [v.sub.1] and [v.sub.2] are measurable, respectively.

The Monge-Kantorovich mass transfer problem is given as follows:

[mathematical expression not reproducible] (28)

A measure [mu] [member of] M(X x Y) is said to be a feasible solution for MK problem if it satisfies (28) and <[mu], c> is finite. The MK problem is called consistent if the set of feasible solutions is nonempty, in which case its optimal value is defined as

inf (MK) = inf {<[mu], c> : [mu] is a feasible solution for MK} (29)

It is said that the MK problem is solvable if there is a feasible solution [[mu].sup.*] that attains the optimal value. In this case, [[mu].sup.*] is called an optimal solution for the MK problem and the value inf (MK) is written as min(MK) = ([[mu].sup.*], c).

Note that since [v.sub.1] and [v.sub.2] are probability measures, a feasible solution for MK is also a probability measure. Moreover, if c is a continuous function on X x Y and X and Y are compact subsets on [R.sup.n], then the product measure [mu] := [v.sub.1] x [v.sub.2] is a feasible solution. Therefore the MK problem is consistent, and so the MK problem is solvable in this case.

We assume the following conditions: X and Y are compact subsets of [R.sup.n] and c : X x Y [right arrow] R is abounded continuous function.

Let {[V.sub.j]} and {[V'.sub.j]} be AB-MRA on [R.sup.n] with scaling functions [mathematical expression not reproducible], finite groups [B.sub.1] and [B.sub.2], and dilatations [A.sub.1] = {[a.sup.j.sub.1]} and [A.sub.2] = {[a.sup.j.sub.2]}, respectively. We can obtain a new AB-MRA {[V.sup.*.sb.j]} on [R.sup.2n] with scaling functions [mathematical expression not reproducible], finite group B = [B.sub.1] x [B.sub.2], and dilatation {[a.sup.j.sub.1] x [a.sup.j.sub.2]}. The projections of these AB-MRA to the level j are denoted by [P.sup.j.sub.1], [P.sup.j.sub.2], and [Q.sup.j].

Now we proceed to discretization of the MK-problem using the results of Section 2; then we have that [[mu].sup.j], [v.sup.j.sub.1], and are the projections to level j of the respective AB-MRA; thus, using these measures, we obtain the discretization of the MK-problem in the level j, which is given by

[mathematical expression not reproducible]. (30)

We shall give explicit expressions for the discretization of the measures and the cost function associated with MK-problem using the AB-MRA, which are given by

[mathematical expression not reproducible] (31)

where [[mu].sup.j.sub.[alpha],[beta]], [a.sup.j.sub.[alpha],[beta]] and [b.sub.[alpha],[beta]] are nonnegative real numbers. Now we calculate <[[mu].sup.j], c>; thus

[mathematical expression not reproducible], (32)

and hence, using the above equation and the orthonormality of family {[[phi].sup.j.sub.1,[alpha]] [[phi].sup.j.sub.2,[beta]]}, we obtain

[mathematical expression not reproducible]. (33)

We consider that [[alpha].sub.i] is a fixed element in [(B[[GAMMA].sub.1]).sup.sub.0] and we have that [mathematical expression not reproducible] is the region associated with [[alpha].sub.i] for i = 1,..., r; then we obtain

[mathematical expression not reproducible]. (34)

On the other hand, we have that

[mathematical expression not reproducible] (35)

From the above equations, we have that the condition [mathematical expression not reproducible] is equivalent to

[mathematical expression not reproducible]. (36)

Analogously, for all the elements [[beta].sub.1],..., [[beta].sub.s] of [(B[[GAMMA].sub.2]).sup.j.sub.0], we have that

[mathematical expression not reproducible]. (37)

Using Theorem 4, we obtain that

[mathematical expression not reproducible] (38)

In summary, we have that the M[K.sup.j] problem given by (30) is equivalent to the following problem:

[mathematical expression not reproducible] (39)

The problem MK[D.sup.j], given the above system, has a feasible solution, so we know that c is bounded. Then we have that the problem MK[D.sup.j] has an optimal solution; for more details, see Chapter 10 in [7].

Let [[mu].sub.*] be the optimal solution of MK problem given in (28). We use the optimal solution [[mu].sub.*] to induce a sequence of measures [[mu].sup.j.sub.*] such that [[mu].sup.j.sub.*] = [Q.sup.j] [[mu].sup.j.sub.*] (see Section 3.2). Let [[eta].sup.j.sub.*] be the optimal solution of M[K.sup.j] problem given in (30).

For j [member of] Z, we defined the following [sigma]-algebras:

[mathematical expression not reproducible] (40)

where [<[A.sub.i]>.sub.i[member of]I] denotes the [sigma]-algebra generated by the sets [A.sub.i] with i [member of] I and the lattices B[[GAMMA].sup.j.sub.1], B[[GAMMA].sup.j.sub.2], and B[[GAMMA].sup.j] are defined as in (3).

Definition 8. Let F be a sub-a-algebra of F, and let X [member of] [L.sup.1] be a random variable. We say that the random variable X' is the conditional expectation of X with respect to F' and denote it by E[X | F'] if and only if

(i) X' [member of] [L.sup.1].

(ii) X' is F'-measurable.

(iii) E[X'[[chi].sub.A]] = E[X[[chi].sub.A]], for all a [member of] F'.

Remark 9. Given f [member of] [L.sup.1]([X.sub.1] x [X.sub.2]), we have that

E [/| [F.sup.j]] = E [[Q.sup.j] (f)]. (41)

There are analogous results for [P.sup.j.sub.1] and [P.sup.j.sub.2] through the conditional expectations of [F.sup.j.sub.1] and [F.sup.j.sub.2], respectively.

Proposition 10. Let [mu] be a feasible solution of the MK problem; then [[mu].sup.j] is a feasible solution of the MK[D.sup.j]-problem.

Proof. We suppose that [mu] satisfies (28). Then we have the following relations:

[mathematical expression not reproducible] (42)

where [[(B[GAMMA]).sup.j.sub.0]][sub.[alpha]] = {([alpha],[beta]) [member of] [(B[GAMMA]).sup.j.sub.0] : a is fixed} and E a measurable set. Similarly, we obtain that [[PI].sub.2] [[mu].sup.j](E) = [v.sup.j.sub.2] (E). Therefore the result is as follows.

Remark 11. If [[mu].sub.*] is an optimal solution of the MK problem, then [[mu].sup.j.sub.*] is a feasible solution of the MK[D.sup.j]-problem.

Proposition 12. Given E [member of] [F.sup.j.sub.1] and F [member of] [F.sup.j.sub.2], one has

[mathematical expression not reproducible], (43)

where [mu] and [[eta].sup.j] are feasible solutions of the MK and M[K.sup.j] problems, respectively.

Proof. Let [[DELTA].sup.j.sub.[alpha]], be a generator element of [sigma]-algebra [F.sup.j]. Then

[mathematical expression not reproducible] (44)

In above equation, we use the fact that [mathematical expression not reproducible]. Analogously, we have that [[eta].sup.j]([R.sup.n] x F) = [mu]([R.sup.n] x F).

Definition 13. Let (X, [tau]) be a topological space, and let F be [sigma]-algebra on X that contains the topology [tau]. Let M be a collection of measures defined on F. The collection M is called tight if, for any [epsilon] > 0, there is a compact subset [K.sub.[epsilon]] of X such that, for all measures [mu] [member of] M, [absolute value of [mu]](X \ [K.sub.[epsilon]]) < [epsilon], where is the total variation measure of [mu].

Proposition 14. Consider the sequence {[[eta].sup.j.sub.*]} of probability measures, where [[eta].sup.j.sub.*] is the optimal solution of M[K.sup.j] for each j [member of] Z. Then there exists a subsequent [mathematical expression not reproducible] and a probability measure [mathematical expression not reproducible] weakly. Moreover, the probability measure [[eta].sub.*] is an optimal solution of MK.

Proof. We know that [X.sub.1] and [X.sub.2] are compact sets, provided that the measures {[[mu].sup.j.sub.*]} are tight for each j [member of] Z. Now, using Prokhorov's Theorem (for details, see Chapter 1 in [8]), there exists a subsequence [mathematical expression not reproducible] and a probability measure [mathematical expression not reproducible] weakly.

Notice that [mathematical expression not reproducible] is an optimal solution of [mathematical expression not reproducible]; thus, we obtain

[mathematical expression not reproducible]. (45)

Using the Theorem, we have that [mathematical expression not reproducible] weakly. From this fact, it is clear that [[eta].sub.*] is a feasible solution of M[K.sup.j].

Now, we consider [[mu].sub.*] as the optimal solution of MK. from Proposition 10, we have that [[mu].sup.j.sub.*] is feasible solution of M[K.sup.j]. It follows that

<[[eta].sup.j].sub.*], c> [less than or equal to] <[[mu].sup.j.sub.*], c>; (46)

taking the limit when j [right arrow] [infinity], we have

<[[eta].sub.c], c> [less than or equal to] <[[mu].sub.*], c>; (47)

On the other hand, [[eta].sub.*] is a feasible solution of MK; then

<[[mu].sub.*], c> [less than or equal to] <[[eta].sub.*], c>, (48)

which completes the proof of the theorem.

5. An Illustrative Example of This Method

In this section, we present an example of the ideas presented in the previous section. Let C be the square with vertices in the points

[mathematical expression not reproducible] (49)

and let H be a hexagon with vertices being in set

[mathematical expression not reproducible] (50)

We consider the function c : C x H [right arrow] R defined by c(x, y) = [[parallel]x - y[parallel].sup.2]. We claim to solve the following problem:

[mathematical expression not reproducible], (51)

where [[lambda].sub.1] and [[lambda].sub.2] are the normalized Lebesgue measures to C and H, respectively; that is, [[lambda].sub.1] (C) = [[lambda].sub.2] (H) = 1. We consider the following AB-MRA on [L.sup.2]([R.sup.2]):

(1) {[V.sup.j.sub.1]}, where the fundamental region is [[DELTA].sub.1] = [0,1/2] x [0,1/2] and the scaling function [[phi].sub.1] = 2[[chi].sub.[0,1/2] x [0,1/2]], the lattice is [[GAMMA].sub.1] = [Z.sup.2], the finite group [B.sub.1] is the trivial group, and the dilation [A.sub.1] = {[2.sup.-j](1,1)}.

(2) {[V.sup.j.sub.2]}, where the scaling function [mathematical expression not reproducible], with [A.sub.2] being the triangle with vertices in [mathematical expression not reproducible]; the finite group [B.sub.2] is the rotation group of a regular hexagon with vertices in the unit circle; the scaling is given by [A.sub.2] = {[a.sup.j]}, where [mathematical expression not reproducible].

We denote by [C.sup.j.sub.m] and [T.sup.j.sub.n] the squares and the triangles associated with level j of the multiresolution analysis presented above. Since c is a continuous function in each pair of sets [mathematical expression not reproducible] are the centroids of [C.sup.j.sub.m] and [T.sup.j.sub.n], respectively.

In particular, we present a discretization of MK problem given by (51) for the level j = 2; the graphical description of the process of discretization is given in Figure 3 (which was generated using Mathematica 11.1.0).

Using {[V.sup.j.sub.1]} and {[V.sup.j.sub.2]} in C and H, respectively, notice that C is the union of congruent squares [{[C.sup.2.sub.m]}.sup.64.sub.m=1] with disjoined interiors. Similarly, the hexagon H is the union by congruent equilateral triangles [{[T.sup.2.sub.n]}.sup.96.sub.n=1], with disjoined interiors. Note that [lambda]([C.sup.2.sub.m]) = 1/64 and [lambda]([T.sup.2.sub.n]) = 1/96.

In consequence, a discrete approximation for the problem defined in (51) is as follows:

[mathematical expression not reproducible]. (52)

The optimal solution of this linear programming problem is 4.02996. In Table 1 we present the solution for some levels.

6. Conclusions

The application of the Haar type multiresolution analysis (MRA) to the problem of Monge-Kantorovich allows us to obtain a discretization scheme for this problem at each level of the MRA; moreover, this MRA is based on the symmetries of the underlying space. This is an advantage because it provided us a natural method of discretization based on the geometry. Each level of the MRA induces a soluble finite linear programming problem. So, we obtain a sequence of optimal solutions of these transport problems and this sequence converges weakly to the optimal solution of the original problem.

https://doi.org/10.1155/2018/1764175

Conflicts of Interest

The authors declare that there are no conflicts of interest regarding the publication of this article.

Acknowledgments

This work was partially supported by the CONACYT project, Mexico. The second author is grateful to Instituto Politecnico Nacional, Mexico, for financial support for development of this work.

References

[1] O. Hernandez-Lerma and J. B. Lasserre, "Approximation schemes for infinite linear programs," SIAM Journal on Optimization, vol. 8, no. 4, pp. 973-988,1998.

[2] J. Gonzelez-Hernendez, J. R. Gabriel, and O. Hernandez-Lerma, "On solutions to the mass transfer problem," SIAM Journal on Optimization, vol. 17, no. 2, pp. 485-499, 2006.

[3] J. R. Gabriel, J. Gonzelez-Hernendez, and R. R. Lopez-Martinez, "Numerical approximations to the mass transfer problem on compact spaces," IMA Journal of Numerical Analysis, vol. 30, no. 4, pp. 1121-1136, 2010.

[4] K. Grochenig and W. R. Madych, "Multiresolution analysis, Haar bases, and self-similar tilings of Rn" Institute of Electrical and Electronics Engineers Transactions on Information Theory, vol. 38, no. 2, pp. 556-568, 1992.

[5] K. Guo, D. Labate, W.-Q. Lim, G. Weiss, and E. Wilson, "Wavelets with composite dilations and their MRA properties," Applied and Computational Harmonic Analysis, vol. 20, no. 2, pp. 202-236, 2006.

[6] I. A. Krishtal, B. D. Robinson, G. L. Weiss, and E. N. Wilson, "Some simple Haar-type wavelets in higher dimensions," The Journal of Geometric Analysis, vol. 17, no. 1, pp. 87-96, 2007.

[7] S. Bazaraa Mokhtar, J. John, and D. Hanif, Linear Programming and Network Flows, Wiley, 2009.

[8] P. Billingsley, Convergence of Probability Measures, Wiley, New York, NY, USA, 1968.

Armando Sanchez-Nungaray (iD), (1) Carlos Gonzalez-Flores, (2) and Raquiel R. Lopez-Martinez (1)

(1) Facultad de Matematicas, Universidad Veracruzana, Xalapa, VER, Mexico

(2) Escuela Superior de Ingeniera Mecanica y Electrica, Instituto Politecnico Nacional, Mexico City, Mexico

Correspondence should be addressed to Armando Sanchez-Nungaray; armsanchez@uv.mx

Received 17 February 2018; Accepted 4 April 2018; Published 3 June 2018

Academic Editor: Turgut Ozic

Caption: Figure 1

Caption: Figure 2

Caption: Figure 3
Table 1

Level            Solution

[MK.sup.1]   4.037306413676646
[MK.sup.2]   4.029959684992724
[MK.sup.3]   4.026748275774876
COPYRIGHT 2018 Hindawi Limited
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2018 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Title Annotation:Research Article
Author:Sanchez-Nungaray, Armando; Gonzalez-Flores, Carlos; Lopez-Martinez, Raquiel R.
Publication:Abstract and Applied Analysis
Article Type:Report
Date:Jan 1, 2018
Words:5480
Previous Article:Optimal Rational Approximations by the Modified Fourier Basis.
Next Article:Time Scale Inequalities of the Ostrowski Type for Functions Differentiable on the Coordinates.
Topics:

Terms of use | Privacy policy | Copyright © 2019 Farlex, Inc. | Feedback | For webmasters