Extended Antipodal Theorems
Extended Antipodal Theorems
Annotation
PII
S111111110000081-2-1
DOI
10.33276/S0000081-2-1
Publication type
Article
Status
Published
Authors
Viacheslav Kalashnikov 
Occupation:  Leading researcher
Affiliation: CEMI RAS
Address: Russian Federation, Moscow, Nakhimovsky pr. 47
Nataliya Kalashnykova
Affiliation: Universidad Autónoma de Nuevo León (UANL)
Address: Mexico, San Nicolás de los Garza, NL, Av. Universidad S/N
Adolf J.J. Talman
Affiliation: Tilburg University
Address: Netherlands, Tilburg University, Tilburg, North Brabant
Lilia Alanís-López
Affiliation: Universidad Autónoma de Nuevo León (UANL)
Address: Mexico, San Nicolás de los Garza, NL, Av. Universidad S/N
Edition
Abstract
The paper presents the extensions of both the antipodal (Borsuk–Ulam) theorem and Browder theorem to the cases comprising both a star-shaped domain of the considered mapping and a multi-valued structure of that mapping. Moreover, an explicit algorithm constructing the desired connected path of the zero points of the mapping is developed.
Keywords
Star-shaped domains, antipodal property, nonparallel condition.
Received
31.01.2019
Date of publication
03.02.2019
Number of characters
7934
Number of purchasers
3
Views
230
Readers community rating
0.0 (0 votes)
Cite Download pdf

To download PDF you should sign in

1 Since 1909 when Brouwer proved the first fixed-point theorem namedafter him, the fixed-point results in various settings play an important role in the optimization theory and applications. This technique has proven to be indispensable for the proofs of multiple results related to the existence of solutions to numerous problems in the areas of optimization and approximation theory, differential equations, variational inequalities, complementary problems, equilibrium theory, game theory, mathematical economics, etc. It is also worthwhile to mention that the majority of problems of finding solutions (zero-points) of functions (operators) can be easily reduced to that of discovering of fixed points of properly modified mappings.
2 Not only theoretical but also practical (algorithmic) developments are based on the fixed-point theory. For instance, the well-known simplicial (triangulation) algorithms help one to find the desired fixed points in a constructive way. That approach allows one to investigate the solvability of complicated problems arising in theory and applications.
3 In this extended abstract, by making use of the triangulation technique, we extend some antipodal and fixed-point theorems to the case of non-convex, more exactly, star-shaped sets. Also, similar extensions are made for set-valued mappings defined over star-shaped sets. From now on, we briefly explain the main points of our extensions.
4 The techniques using various fixed-point theorems have always been widely applied in Operations Research, Mathematical Programming, Game Theory, and other areas of optimization. Such techniques are appropriate in establishing the existence of solutions to mathematical programming problems, convex games, mathematical programs with equilibrium constraints (MPEC), to mention only few. Because of that, any extensions of the classical fixed-point theorems (like the Brouwer theorem for single-valued mappings and Kakutani theorem for multi-valued mappings) are interesting and important. In other words, topological tools are of a very high importance and use in the development of optimization theory and applications.
5 The Brouwer fixed-point theorem and the Borsuk-Ulam theorem can be characterized as two most powerful topological tools of extremely similar structure. Most topology textbooks that include these theorems, such as, for example, Krasnosel'skii [1], Herings [2], Yang [3], do not mention that the two are tightly related (for instance, the Borsuk-Ulam theorem implies the Brouwer Fixed Point Theorem).
6 Many fixed-point theorems have been established for the mappings defined on convex domains. However, in many applications and real-life problems, the domains need not be convex; for example, the feasible sets of bilevel programming problems mostly lack this property even for linear bilevel problems (cf., [4]). In this abstract, we outline how we extend the Borsuk-Ulam (antipodal) theorem to more general domains and to the case of multi-valued mappings as well.
7 First, we recall the definition of star-shaped sets and some properties of projections onto them.
8 Definition 1. A star-shaped region centered at x0 in Rn is a set such that for every and one has.
9 Consider Rn with the maximum metric:
10 , where,
11 as well as the norm induced by this metric:
12

13 In order to work with the projections of the points inside and outside a star-shaped subset onto its boundary, we need the following notation.
14 Definition 2. Let D be a closed, bounded, and star-shaped region D centered at x0=0. For any r>0 such that we define the following:
15
  • For \D define
16
  • For, let
17
  • For, let
18 The antipodal property is the key feature of the functions examined in the Brouwer and Borsuk-Ulam theorems.
19 Definition 3. Let be a closed star-shaped set and a continuous function. The function is said to have the antipodal property, if for every it holds that if, and whenever.
20 The well-known extension of the antipodal property is the nonparallel condition defined below.
21 Definition 4. Let be a closed star-shaped set and a continuous function. This function satisfies the nonparallel condition if for every the following relationships are true: for all, one has if, and otherwise, that is, whenever.
22 We say that satisfies a weak nonparallel condition if for all c>0, it holds: if, and otherwise, that is, whenever.
23 Similar to the constructive proofs presented in [5 – 6], we deduce important existence results concerning zero points.
24 Theorem 1. Let be a closed star-shaped set and a continuous function that satisfies the weak nonparallel condition. Then there exists a point such that
25 The above results is now extended to multi-valued mappings. In order to do that, we refer to the distance between sets as introduced in [8] – [10].
26 Definition 5. Let A, B be arbitrary subsets of Rn. The distance between these subsets is defined as follows:
27

28 Now we can extend the antipodal and nonparallel conditions to the case of multi-valued mappings defined on star-shaped sets.
29 Definition 6. Let be a closed star-shaped set and a multi-valued mapping. The mapping is said to have the antipodal property if for every, one has if, and whenever; here,
30 Definition 7. Let be a closed star-shaped set and a multi-valued mapping. The mapping satisfies the nonparallel condition if for every and, it holds for all and whenever. Otherwise, ifthen for any and. If the above inequalities are claimed for (only) c>0 we say that p satisfies the weak nonparallel condition.
31 Now first, we demonstrate that the problem of finding zeros of a multi-valued mapping defined on a closed bounded star-shaped subset D of Rn satisfying the nonparallel condition can be reduced to the problem of finding zeros of an extended multi-valued mapping boasting the antipodal property on some cube Cn(r).
32 Lemma 1. Let be a closed star-shaped set and a multi-valued mapping satisfying the weak nonparallel condition. Then can be extended to a mapping with the antipodal property and such that whenever.
33 Now the main result obtained for the multi-valued mappings on star-shaped set follows.
34 Theorem 2. Let be an upper-semicontinuous mapping defined on a star-shaped set D and satisfying the weak nonparallel condition. Then there exists a point such that.
35 The abstract finishes with an extension of the nonparallel condition-related result for mappings defined on a star-shaped set times an interval and having convex compact subsets of Rn as its values. Moreover, we will study a connected set of zero points intersecting both and, in order to extend the Browder theorem.
36 Theorem 3. Let be a multi-valued mapping from to where and D be a compact star-shaped subset of Rn with respect to the origin. Suppose that the following conditions hold for p:
37
  1. The mapping is upper-semicontinuous.
38
  1. For every, the restriction defined by satisfies the nonparallel condition. Then there exists a connected subset Z in such that, and whenever (x,t)then 0∈p(x,t).
39 The paper presents the extensions of both the antipodal (Borsuk–Ulam) theorem and Browder theorem to the cases comprising both a star-shaped domain of the considered mapping and a multi-valued structure of that mapping. Moreover, an explicit algorithm constructing the desired connected path of the zero points of the mapping is developed.
40 The properties of the latter algorithm are used in the proof of the extended Browder Theorem, similar to the existence proofs in the pioneering papers by Todd [7], van der Laan and Talman [5] – [6].
41 In our future research, we are going to extend the above-mentioned results to other classes of nonconvex domains of the examined multi-valued mappings.
42 Acknowledgements
43 The research activity of the first author was financially supported by the R&D Department “Optimization and Data Science” of the Tecnológico de Monterrey (ITESM), Campus Monterrey, as well as by the SEP-CONACYT Projects CB-2013-01-221676 and FC-2016-01-1938 (Mexico).

References

1. Krasnosel’skii, M.A. Topological Methods in the Theory of Nonlinear Integral Equations, Pergamon Press, Oxford, 1964.

2. Herings, P.J.-J. Static and Dynamic Aspects of General Equilibrium Theory, Kluwer Academic Publishers, Boston, 1996.

3. Yang, Z.F. Computing Equilibria and Fixed Points, Kluwer Academic Publishers, Boston, 1999.

4. Dempe, S. Foundations of Bilevel Programming, Kluwer Academic Publishers, Boston, 2002.

5. van der Laan, G., Talman, A.J.J. A class of simplicial restart fixed-point algorithms without an extra dimension, Mathematical Programming, 1981, 20: 33–48.

6. van der Laan, G. Existence and approximation of zeros, Mathematical Programming, 1984, 28: 1–24.

7. Todd, M.J. Improving the convergence of fixed-point algorithms, Mathematical Programming Study, 1978, 7: 151–179.

8. Munkres, J.R. Topology, Prentice Hall, Upper Saddle River, 2000.

9. Searcóid, M.Ó. Metric Spaces, Springer Undergraduate Mathematics Series, vol. 106. Springer, Berlin, 2007.

10. Isac, G., Bulavsky,V.A., Kalashnikov,V.V. Complementarity, Equilibrium, Efficiency and Economics, Kluwer Academic Publishers, Boston, 2002.