=Paper=
{{Paper
|id=Vol-1987/paper73
|storemode=property
|title=Polyhedral Complementarity and Fixed Points Problem of Decreasing Regular Mappings on Simplex
|pdfUrl=https://ceur-ws.org/Vol-1987/paper73.pdf
|volume=Vol-1987
|authors=Vadim I. Shmyrev,Ruslan Yu. Simanchev,Inna V. Urazova,Alexander K. Skiba,Stepan P. Sorokin,Maxim V. Staritsyn,Alexander S. Strekalovsky,Anna Tatarczak,Nikolay P. Tikhomirov,Dmitry V. Aron,Alexey A. Tret'yakov,Sergey Trofimov,Aleksey Ivanov,Yury Fettser,Tatiana S. Zarodnyuk,Alexander Yu. Gornov,Anton S. Anikin,Evgeniya A. Finkelstein,Elena S. Zasukhina,Sergey V. Zasukhin,Vitaly Zhadan,Anna V. Zykina,Olga N. Kaneva
}}
==Polyhedral Complementarity and Fixed Points Problem of Decreasing Regular Mappings on Simplex==
https://ceur-ws.org/Vol-1987/paper73.pdf
Polyhedral Complementarity and Fixed Points Problem
of Decreasing Regular Mappings on Simplex
Vadim I. Shmyrev
Sobolev Institute of Mathematics, Russian Academy of Sciences
4 Acad. Koptyug avenue, 630090 Novosibirsk, Russia.
Novosibirsk State University,
2 Pirogova street, 630090 Novosibirsk, Russia.
shmyrev.vadim@mail.ru
Abstract
A new development of polyhedral complementarity investigation is pre-
sented. This consideration extends the author’s original approach to
the equilibrium problem in a linear exchange model and its variations.
Two polyhedral complexes in duality and a cells correspondence are
given. The problem is to find a point of intersection of the cells corre-
sponding each other . This is a natural generalization of linear comple-
mentarity problem. Now we study arising point-to-set mappings with-
out the original exchange model. The potentiality for a special class
of regular mappings is proved. As a result the fixed point problem of
mapping reduces to an optimization problem . Two finite algorithms
for this problem are considered.
1 Introduction
It is known that the problem of finding an equilibrium in a linear exchange model can be reduced to the linear
complementarity problem [Eaves, 1976]. The polyhedral complementarity approach [Shmyrev, 1983] is based on
a fundamentally different idea, that reflects more the character of economic equilibrium as a concordance the
consumers’ preferences with financial balances. In algorithmic aspect it may be treated as a realization of the
main idea of the simplex-method of linear programming. It has no analogues and makes it possible to obtain
the finite algorithms not only for the linear exchange model [Shmyrev, 1985], but also for some of it’s variations
[Shmyrev, 2008], (more references one can find in [Shmyrev, 2016]). The simplest algorithms are those for a
model with fixed budgets, known more as Fisher’s problem. The convex programming reduction of it , given
by Eisenberg and Gale [Eisenberg & Gale, 1959], is well known . This result has been used by many authors to
study computational aspects of the problem. Some review of that can be found in [Devanur et al., 2008]. The
polyhedral complementarity approach has given an alternative reduction of the Fisher’s problem to a convex
program [Shmyrev, 1983],[Shmyrev, 2006]. Only the well known elements of transportation problem algorithms
are used in the procedures obtained by this way [Shmyrev, 2009]. These simple procedures can be used for
getting iterative methods for more complicate models [Shmyrev, 1996], [Shmyrev, 2016].
Copyright ⃝
c by the paper’s authors. Copying permitted for private and academic purposes.
In: Yu. G. Evtushenko, M. Yu. Khachay, O. V. Khamisov, Yu. A. Kochetov, V.U. Malkova, M.A. Posypkin (eds.): Proceedings of
the OPTIMA-2017 Conference, Petrovac, Montenegro, 02-Oct-2017, published at http://ceur-ws.org
511
Ω1
Ξ6
Ω5
Ω7 x∗ is the solution
Ω4 x∗ ∈ Ω6 ∩ Ξ6
Ω3
x∗
Ξ2 Ω6
Ξ7 Ξ3 Ω2
Ξ4
Ξ1
Ξ5
Figure 1: Polyhedral complementarity
By the given approach we try to study a mathematical fundamental principle of the proposed finite algorithms
ignoring an original economic model. We consider a class of piecewise constant multivalued mappings on the
simplex in Rn , which possess some monotonicity property . The potentiality of these mappings is proved
[Shmyrev, 2017]. This makes possible to reduce a fixed point problem to two optimization problems which are
in duality similarly to dual linear programming problems. Two finite algorithms presented here are based on the
ideas of suboptimization [Rubinstein, 1971].
2 Polyhedral Complementarity Problem
We consider polyhedrons in Rn . Let two polyhedral complexes ω and ξ with the same number of cells r be
given . Let R ⊂ ω × ξ be a one-to-one correspondence : R = {(Ωi , Ξi )}ri=1 with Ωi ∈ ω, Ξi ∈ ξ.
We say that the complexes ω and ξ are in duality by R if the subordination of cells in ω and the subordination
of the corresponding cells in ξ are opposite each other:
Ωi ≺ Ωj ⇐⇒ Ξi ≻ Ξj .
The polyhedral complementarity problem is to find a point that belongs to both cells of some pair (Ωi , Ξi ):
p∗ is the solution ⇐⇒ p∗ ∈ Ωi ∩ Ξi for some i.
This is natural generalization of linear complementarity, where ( in nonsingular case) the complexes are formed
by all faces of two simplex cones.
Figure 1 shows an example of the polyhedral complementarity problem. Each of two complexes has 7 cells.
There is a unique solution of the problem — the point x∗ that belongs to Ω6 and Ξ6 .
3 Polyhedral Complementarity on Simplex
Let σ be the unit simplex in Rn :
{ ∑
n }
σ = p ∈ R+ |
n
pj = 1 .
j=1
We consider on σ two polyhedral complexes in duality ω = {Ωi } and ξ = {Ξi }.The cell of full dimension of the
complex ω is defined by the condition p ∈ σ and a system of linear inequalities of the form :
∑ ∑
hj pj + hk pk ≥ γ, (1)
j∈S k∈S
/
where S ̸= ∅, S ⊂ J = {1, ..., n} and
hj > 0, j ∈ S, hk < 0, k ∈
/ S.
512
p3 p3
G
Ω2
1
c
c12 Ω12
c2 Ω1
p1 p2 p1 p2
Complex ξ Complex ω
Figure 2: Polyhedral complexes in exchange model
Fig.2 illustrate the polyhedral complexes for a model with 3 commodities and 2 consumers. Each of both
complexes has 17 cells. Fig.3 illustrate the arising complementarity problem. The point c12 ∈ Ω12 is it’s
solution: .
p3
Ω2
c1
c12
Ω12
Ω1
c2
p1 p2
Figure 3: Complementarity problem: c12 is the solution.
For the faces points of the cell some of inequalities (1) become equalities. For a face of dimension (n − 2) there
is only one equality and so we obtain a subdivision J into S and J \ S.
It is assumed that the cells {Ωi } form a subdivision of the simplex σ and the cells {Ξi } form a subdivision of
it’s interior σ ◦ .
The cells {Ξi } of full dimension are defined by the inequalities of the form:
pj /pk ≥ γjk . (2)
A vertex of ξ will be given by a collection of (n − 1) linearly independent equations obtained from inequalities
(2). With such a collection we can associate a graph with a set of vertexes J and a set of edges (j, k) corre-
sponding to the selected inequalities. It is easy to see, that to obtain an edge of ξ we have to remove one edge of
the graph. In this way we obtain two connected components and also a subdivision J into two subsets Q and J \Q.
Concordance condition. The subdivision for an edge of the complex ξ is the same as that for the
corresponding cell of the complex ω .
4 Monotone Regular Mappings
◦
1 . Monotonicity property.
For the problem under consideration it is naturally to introduce piecewise constant point-to-set mapping G,
which for every point of the relative interior of a cell Ω ∈ ω assigns the corresponding cell Ξ ∈ ξ: G(p) = Ξ for
all p ∈ Ω◦ . So the polyhedral complementarity problem becomes the fixed point one: we have to find p ∈ G(p).
It is clear, that the fixed point of the mapping G will be also the fixed point of it’s restriction G◦ on σ ◦ .
A key feature of the considered fixed point problem is a specific monotonicity property of arising mappings.
513
Definition 1. We say that cells Ω1 , Ω2 ∈ ω are adjacent, if they have common (n − 2)-dimensional face.
Let the cells Ω1 , Ω2 be adjacent and q 1 , q 2 are the corresponding vertexes of ξ. Let h be a vector, for which
the inequality (h, Ω◦2 − Ω◦1 ) ≥ 0 holds.
Definition 2. The mapping G is locally decreasing, if for each two adjacent Ω1 , Ω2 the inequality
(h, q 2 − q 1 ) ≤ 0 is valid.
For a positive vector q = (q1 , ..., qn ) we introduce the vector ln q = (ln q1 , ..., ln qn ).
Definition 3. The mapping G is locally logarithmically decreasing, if
(p2 − p1 , ln q 2 − ln q 1 ) ≤ 0, ∀p1 ∈ Ω1 , p2 ∈ Ω2 .
In what follows we consider a narrower class of regular mappings for which in the inequalities (1) we have:
hj = 1, j ∈ S,
hk = −1, k∈
/ S,
and −1 ≤ γ ≤ 1. So (1) becomes ∑ ∑
pj − pk ≥ γ.
j∈S k∈S
/
It can be proofed, that for regular mappings the subclass of locally decreasing mappings coincides with the
subclass of locally logarithmically decreasing mappings.
2◦ . Reduction to the optimization problem.
Definition 4. A mapping G is named potential if there exists piecewise linear concave function f on σ such
that
∀p ∈ σ ∂f (p) = {ln q + tθ|q ∈ G(p), t ∈ R1 , }
where θ = (1, ..., 1) and ∂f (p) is the subdifferential of the function f at the point p.
The main feature of the considered fixed point problem is the fact that logarithmically decreasing mappings
are potential [Shmyrev, 2017]. We have as a corollary that locally logarithmically decreasing mappings are
logarithmically decreasing in the large :
(p2 − p1 , ln q 2 − ln q 1 ) ≤ 0, ∀p1 , p2 ∈ σ, ∀q 1 ∈ G(p1 ), q 2 ∈ G(p2 ).
This allows us to reduce the fixed point problem to the optimization one.
For p > 0 we introduce the function h(p) = (p, ln p) and consider the function
φ(p) = h(p) − f (p),
where f (p) is the potential function of the mapping G◦ .
Theorem 1. The fixed point of G◦ coincides with the minimum point of the convex function φ(p) on σ ◦
The function φ is very simple and the suboptimization approach [Rubinstein, 1971] can be used to minimize
it . In this way we obtain the finite algorithm for the fixed point searching.
Another algorithm for the problem can be obtained if we take into account that the mapping G and the
inverse mapping G−1 have the same fixed points. For the introduced concave function f we can consider the
conjugate function f ∗ :
f ∗ (y) = inf {(y, z) − f (z)}
z
Theorem 2. The fixed point of G is the maximum point of the concave function ψ(q) = f ∗ (ln q) on σ ◦ .
◦
514
It can be shown that for the functions φ(p) and ψ(q) there is a duality relation as for dual programs of linear
programming:
Proposition. For all p, q ∈ σ ◦ the inequality
φ(p) ≥ ψ(q)
holds . If this inequality turns into equality then p = q .
Corollary. φ(r) = ψ(r) if the point r is the fixed point of the mapping G
3◦ . Algorithms.
The mentioned theorems allow us to propose two finite algorithms for searching fixed points.
Algorithmically they are based on the ideas of suboptimization [Rubinstein, 1971], which were used for mini-
mization quasiconvex functions on a polyhedron. In considered case we exploit the fact that the complexes ω
and ξ define the cells structure on σ ◦ similarly to the faces structure of a polyhedron.
For implementation of the algorithms one does not need to have function φ(p) and f ∗ (y) explicit. We just need
to be able to verify the inequality defining cells Ω ∈ ω and Ξ ∈ ξ.
We now describe the general scheme of the algorithm that is based on the theorem 1. The other one using
the theorem 2 is quite similar.
Consider a couple of two cells Ω ∈ ω, Ξ ∈ ξ corresponding each other. Let L, M be their affine hulls
respectively. It can be shown that L ∩ M is singleton. Let r be the point of this intersection.
Theorem 3. The point r is the minimum point of the function φ(p) on L and the maximum point of the function
ψ(q) on M .
On the current k-step of the process there are two cells Ωk ∈ ω, Ξk ∈ ξ corresponding each other and two
points pk ∈ Ωk , q k ∈ Ξk . We consider affine hulls Lk ⊃ Ωk , Mk ⊃ Ξk and obtain the point of their intersection
rk . For this we need descriptions of these sets.
As it was mentioned before, with an edge of ξ we associate a graph with two connected components and a
subdivision J into two subsets Q and J \ Q. For a cell of higher dimension the associated graph will have more
components, that will entail an increase of the sets number in the subdivision of J. Let τ be the number of
connected components of the associated graph for the cell Ξk and J = Q1 ∪Q2 , ∪..., Qτ is the obtained subdivision
of J. It is easy to verify that the linear system for Lk is going to be equivalent to this one :
∑
pj = αν , ν = 1, ..., τ. (3)
j∈Qν
The conditions for the cell Ξk define coordinates qj on each connected component up to a positive multiplier:
qj = tν qjk , j ∈ Qν .
To obtain the coordinates of the point rk we need to put pj = qj in corresponding equation (3), which gives the
multiplier tν .
For the obtained point rk can be realized two cases.
(i) rk ∈
/ Ωk . Since rk is a minimum point on Lk for the strictly convex function φ(p), the value of the function
will diminish for the moving point p(t) = (1 − t)pk + trk ) when t increases in [0,1]. In considered case this point
reaches a face of Ωk at t = t∗ < 1 . This face we take as Ωk+1 , that determines the cell Ξk+1 . We accept
pk+1 = p(t∗ ), q k+1 = q k and pass to the next step.
It should be noted that the dimension of the cell Ω reduces. It will certainly be rk ∈ Ωk when the current cell
Ωk degenerates into a point and we have rk = pk . But it can occur earlier.
(ii) rk ∈ Ωk . In this case we can assume pk = rk . Otherwise, we can simply replace pk by rk with a decrease
of the function’s φ(p) value. If rk ∈ Ξk , then rk is the required fixed point. Otherwise, we are looking for the
maximum t∗ , at which point q(t) = (1 − t)q k + trk is still in the Ξk . At t = t∗ the point q(t) reaches a face
of the cell Ξk , which is accepted as Ξk+1 . The corresponding cell of the complex ω will be Ωk+1 . We accept
pk+1 = pk , q k+1 = q(t∗ ) and pass to the next step.
Nondegeneracy condition. The dimension of the current cells Ωk , Ξk at each step of the process changes
per unit.
Under this condition the value of the difference φ(pk ) − ψ(q k ) decreases at each step of the process and we
use this to prove the finiteness of the process.
515
Acknowledgments.
This work was supported by the Russian Foundation for Basic Research, project 16-01-00108 .
References
[Rubinstein, 1971] Rubinstein G.Sh., Shmyrev V. I. Methods for minimization quasiconvex function on poly-
hadron (in Russian). Optimization 1(18). 82–117
[Shmyrev, 2017] Shmyrev V. I. Polyhedral complementarity on simplex. Potentiality of regular mappings (in
Russian).J. Appl. Indust. Math. . to appear.
[Shmyrev, 1996] Shmyrev V. I., Shmyreva N. V. An iterative algorithm for searching an equilibrium in the linear
exchange model. Sib.Adv.Math. 6, 1. 87–104
[Shmyrev, 2009] Shmyrev V. I. An algorithm for finding equilibrium in the linear exchange model with fixed
budgets.Journal of Applied and Industrial Mathematics 3(4). 505–518
[Shmyrev, 2006] Shmyrev V. I. An algorithmic approach for searching an equilibrium in fixed budget exchange
models. In Driessen, T. S., van der Laan, G. , Vasil’ev, V. A., Yanovskaya, E. B. (eds.) Russian
Contributions to Game Theory and Equilibrium Theory. (pp. 217–235). Berlin, Germany: Springer.
[Shmyrev, 2016] Shmyrev Vadim I. (2016) An Iterative Approach for Searching an Equilibrium in Piecewise
Linear Exchange Model. In Kochetov, Yu. et al. (Eds.) DOOR-2016. LNCS (Lecture Notes in Computer
Sciences). ( vol. 9869, pp. 61-72). Heidelberg, Germany : Springer.
[Shmyrev, 2008] Shmyrev V. I. A generalized linear exchange model. J. Appl. Indust. Math. 2, 1. 125–142
[Shmyrev, 1985] Shmyrev V. I. An algorithm for the search of equilibrium in the linear exchange model. Sibirian
Math. J. 26. 288–300
[Shmyrev, 1983] Shmyrev V. I. On an approach to the determination of equilibrium in elementary exchange
models, Sov. Math. Dokl. 27, 1, 230–233
[Eaves, 1976] Eaves, B. C. A finite algorithm for linear exchange model. J. Math. Econom. 3(2), 197–204 .
[Eisenberg & Gale, 1959] E. Eisenberg and D. Gale.: Consensus of subjective probabilities: The pari-mutuel
method. The Annals of Mathematical Statistics 30(1). 165–168
[Devanur et al., 2008] Devanur, N. R., Papadimitriou, C. H., Saberi, A., Vazirani, V. V. Market equilibrium via
a primal–dual algorithm for a convex program.Journal of the ACM (JACM), 55(5). Article 22
516