A new development of polyhedral complementarity investigation is presented. 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 corresponding each other . This is a natural generalization of linear complementarity problem. Now we study arising point-to-set mappings without 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.
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],
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
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)}ir=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: The polyhedral complementarity problem is to find a point that belongs to both cells of some pair (Ωi, Ξi): Ωi ≺ Ωj ⇐⇒ Ξi ≻ Ξj . 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
Let σ be the unit simplex in Rn : σ = { p ∈ Rn+ | ∑n pj = 1}.
j=1 ∑ hj pj +
∑ hkpk ≥ γ, j∈S
k∈=S hj > 0, j ∈ S,
hk < 0, k ∈/ S. 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 : where S ̸= ∅, S ⊂ J = {1, ..., n} and (1) c12
c1 p1
c2 Complex ξ Ω2
Ω12
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) corresponding 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
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.
Let the cells Ω1, Ω2 be adjacent and q1, q2 are the corresponding vertexes of ξ. Let h be a vector, for which the inequality (h, Ω2◦ − Ω1◦) ≥ 0 holds.
De nition 2. The mapping G is locally decreasing, if for each two adjacent Ω1, Ω2 the inequality (h, q2 − q1) ≤ 0 is valid.
For a positive vector q = (q1, ..., qn) we introduce the vector ln q = (ln q1, ..., ln qn).
De nition 3. The mapping G is locally logarithmically decreasing, if (p2 − p1, ln q2 − ln q1) ≤ 0, ∀p1 ∈ Ω1, p2 ∈ Ω2.
In what follows we consider a narrower class of regular mappings for which in the inequalities (1) we have: and −1 ≤ γ ≤ 1. So (1) becomes hj = 1, hk = −1, j ∈ S, k ∈/ S, ∑ 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.
De nition 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 q2 − ln q1) ≤ 0, ∀p1, p2 ∈ σ, ∀q1 ∈ G(p1), q2 ∈ 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 xed 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) = inzf{(y, z) − f (z)} Theorem 2. The xed point of G◦ is the maximum point of the concave function ψ(q) = f ∗(ln q) on σ◦.
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 xed point of the mapping G
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 minimization 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, qk ∈ Ξ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 = α , j∈Q ν = 1, ..., τ.
(3) The conditions for the cell Ξk define coordinates qj on each connected component up to a positive multiplier: k qj = t qj , 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∗), qk+1 = qk 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)qk + 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, qk+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) − ψ(qk) decreases at each step of the process and we use this to prove the finiteness of the process. This work was supported by the Russian Foundation for Basic Research, project 16-01-00108 .