UNIVERSITY OF

ILLINOIS LIBRARY

AT URBAN- CHAMPAIGN

BOOKSTACKS

Digitized by the Internet Archive

in 2011 with funding from

University of Illinois Urbana-Champaign

http://www.archive.org/details/approximatefixed393blai

. /•:>

Faculty Working Papers

APPROXIilATE FIXED POINTS IN RECTANGULAR ARRAYS

Charles Blair

#393

College of Commerce and Business Administration

University of Illinois at Urbana-Champaign

FACULTY WORKING PAPERS College of Commerce and Business Administration University of Illinois at Urbana-Champaign

April 15, 1977

APPROXIIIATE FIXED PODJTS IN RECIAIIGULAR ARRAYS

Charles Blair

#393

Approximate Fixed Points in Rectangular Arrays

by

Charles Blair*

Department of Business Administration

University of Illinois

April, 1977

*Assistant Professor

Abstract An extension of Kuhn's "Cubical Sperner Lemma" is used to present two algorithms for locating approximate fixed points.

Introduction

Let f: [0, 1] ^ [0, 1] be continuous. The natural way to find a point X such that f (x) is close to x would be something like this: compute f(l/2). If it is greater than 1/2, confine your search to [1/2, 1]. Otherwise search in [0, 1/2]. Next compute f(3/A) in the first case or f(l/4) in the second case... Each computation cuts the size of the interval under consideration in half .

The same idea applies in n dimensions. Let f: [0,1] -> [0, 1] be continuous. By the Brouwer theorem, there is an x such that f(x) = x. Divide the unit cube into two rectangles R, , R„ according to whether X >^ 1/2 oC x^ £ 1/2. Let B(R^) be the boundary of R^ and assume f has been computed there. It may be the case that every continuous function g: R^ ->- [0, 1]''^ for which g(x) = f (x) on B(R ) has a fixed point. In that case f must have a fixed point in R and R may be ignored. If this is not the case then f must have a fixed point in R„ and R^ may be ignored. In general:

Proposition: Let Re [o, 1] be an n-dimensional rectangle and f : R -^ [0, 1]*^ be such that every h: R ->■ [0, 1]" for which h(x) = f (x) on B(R) has a fixed point in R. Let R = R U R„ where R and R are two n-dimensional rectangles whose interiors are disjoint. Then either (i) every g: R^ -> [0, 1] for which g(x) = f(x) on E(Rp has a fixed point in R , or (ii) every g: R„ -»- [0, 1] for which g(x) = f(x) on B(R„) has a fixed point in R^.

Proof; If (i) and (ii) fail there are g^: R^ -^ [0, 1]" and g„: R- ->■ [0, 1] without fixed points, which agree with f on B(R,) {j B(R ). But then we could define h: R -^ [0, 1] by h(x) «■ g, (x) for x in R and h(x) = g„Cx) for x in R . h would not have a fixed point, con- tradicting our hypothesis. Q.E.D.

-2-

The key point here is that knowing the values of f on the "small" subset B(R )U B(R ) enables us to cut our search space in half by con- fining our subsequent hunt for a fixed point to R in case (i) and to R in case (ii) .

In practice one computes approximate fixed points, i.e., points x for which f(x) is close to x. The information at hand is the values of f(x) on a rectangular grid, a finite subset of [0,1] , e.g.

0 < a. < k a. integer?

The main purpose of this paper is to show how the"bifurcation" idea described above may be used to compute approximate fixed points. Approximate Fixed Points in Rectangular Arrays

Rectangular grids were discussed by Kuhn [2] and we essentially follow his treatment.

By uniform continuity there is an integer k such that jx-y| j< —

implies |f{x) - f (y) | ^ e. Approximate fixed points for f are obtained

by locating a subcube of edge length t- with vertices in A^ such that,

for each 1 ^ i ^ n, tnere are vertices of the cube x., y such that

the ith component of x. (respectively y.) is 2l (resp. _£) the ith

component of f (x ) (respectively f(y,)). If x is any point of such a cube

then j (ith component of x) - (ith component of f(x))} <^ e + -j-* so x may

be considered an approximate fixed point.

An Extension of the "Cubical Sperner Lemma"

a a Fix f: [0,1]" -> [0, 1]". As before A^ ={(—',..., ^)j

0 < a, < k, a. integer} for some fixed k. S, , . . . S are fixed subsets of A, . — 1—1 In Tc

For 1 <^ j_< n a j -dimens ional rectangle I'fill be defined as a non- degenerate j-dimensional rectangular subset of [0, 1] each of whose

* These figures can be sharpened.

-3-

vertices is In A, . A j-dimensional rectangle is not a (j+1) -dimensional rectangle. A j-dimensional cube will be a j-dimensional rectangle with each edge of length — .

The boundary B(R) of a j-dimensional rectangle R is the union of the (j-l)-dimensional faces of R.

For each j, we define* two families of j-dimensional cubes, the j-fixed cubes and the special j-fixed cubes. We proceed by induction:

A 1— fixed cube is a 1-dimensional cube (i.e. a line segment of length — ) such that exactly one of the two vertices is a member of S . A special 1-fixed cube is a 1-fixed cube both of whose vertices are members of S^.

For j > 1 a j-fixed cube is a j-dimensional cube which contains an

odd number of special (j-l)-fixed cubes. A special j-fixed cube is a

j-fixed cube all of whose vertices are members of S . , , .

1+1

Example: for n = k = 2. If S^ = {(0, 0), (1/2, 1/2)} and S^ = {(0, 0), (0, 1/2), (1/2, 1/2)} then {(0,0), (1/2, 0)} is a 1-fixed cube while {(0, 0), (0, 1/2)} is a special 1-fixed cube. The 2-dimensional cube {(0, 0), (0, 1/2), (1/2, 0), (1/2, 1/2)} is not a 2-fixed cube since it also contains the special 1-fixed cube {(0, 1/2), (1/2, 1/2)}. If S were changed to {(0, 0), (0, 1/2)} we would have a 2-fixed cube.

Theorem 1: If R is any j-dimensional rectangle the boundary B(R) contains an even number of (j-1) fixed cubes. Proof: Each (j-2) dimen- sional cube in B(R) is contained in exactly two (j-1) dimensional cubes in B(R). Therefore:

\ /no. of special (j-2) fixed j j ino. of special (j-2) -j / ycubes in Q / ,^— \fixed cubes in B(R) /

Q is (j-1) dim. cube in B(R)

* A similar definition is used in Wolsey [H].

-4-

So the nmnber of odd terras, which correspond to (3-l)-fixed cubes, must

be even, Q.E.D.

Corollary: For each 1 j^ i ji j a j-f Ixed cube contains vertices x , y

such that x^ e S^ and y. i S..

i i i 1

Proof: We argue by induction on j. For j=l this is immediate. For

j > 1 a j-fixed cube contains at least one special (j-l)-fixed cube, so

we have members and non-members of S 5...S._^ , by induction hypothesis,

as well as members of S . . By Theorem 1, the j— fixed cube contains an

J

even number of (j-l)-fixed cubes, so it must contain at least one (j-1)-

fixed cube that is not special. This implies there is a vertex which is

not in S. . Q.E.D. J

If S. = {xeA, jith component of x >^ ith component of f (x)} then an n-fixed cube qualifies, by our corollary, as an approximate fixed point in the sense of the preceding section.

Theorem 2 : For any j-dimensional rectangle R the parity of the number of j-fixed cubes in R is the parity of the number of special (j-l)-fixed cubes in B(R).

Proof: Each (j-l)-dim. cube in B(R) is in exactly one j-dim.

cube in R. Each (j-l)-dim. cube not in B(R) is in exactly two j-dim.

cubes in R. Therefore:

no, of special \ _ /no. of special (j-l)-fixed| (j-l)-fixed cubes in QJ \cubes in B(R) /

_i

+ "> /no. of special (j-1)- \ Jj^fixed cubes not in B(R)/

Q is a j-fixed \ "> (no, of special (j-1)-

cube in R

Each odd term on the left corresponds to a j-fixed cube. Q.E.D, The original "cubical Sperner leuma" [2] dealt with the sets S. described previously. These had the special property that 5.3

n

-5-

{x|ith component of x = 1} and S.O {xjith component of x = 0} = 0,

Corollary [2, 4]: If the special property on S. holds, then [0, 1]

contains an odd number of n-f ixed cubes .

Proof: We argue by induction on n. The case n = 1 is immediate.

For n > 1 we show that the boundary of [0, 1] has an odd number of

special (n-l)-fixed cubes and apply theorem 1. A direct consequence

of the definitions is that the only special (n-l)-fixed cubes in B([0, 1] )

are the (n-l)-fixed cubes in {xjnth components of x = 1}. By induction

hypothesis there are an odd number of these. Q.E.D.

Applications of Theorem 1_ _to_ Fixed-Point Algorithms

Theorem 2 suggests several methods of locating approximate fixed

points. We describe two in detail: 1. Bifurcation. This is the method

described in the introduction. Starting with [0, l] and the S. defined

previously, we have shown that the boundary of [0, i] has an odd number

of special (n-l)-fixed points. Take any (n-D- dimensional rectangle which

divides [0, 11 into n-dimensional rectangles R^ , R„. One of R, , R_

1a 1 /

will have an odd number of special (n-l)-fixed cubes in its boundary, so theorem 2 says that rectangle has an approximate fixed point. We then divide that rectangle into two rectangles, one of which must contain an odd number of special (n~l)-fixed cubes in its boundary, etc- If at each step we divide the rectangle into halves as nearly equal as possible, v;e will obtain an n-f ixed cube after at most n(log k +1) divisions.

Note that finding the parity of the number of special (n-l)-fixed cubes in B(R) never requires evaluation of f in the interior of R. It is not always necessary that f be evaluated at every point of B(R) either. For example, continuity considerations may enable one to locate an (n-1) dijaensional rectangle T in B(R) such that THA-^^^S, for some i ^ n-1.

-6-

m this case, T contains no (n-l)-fixed cubes by the corollary to theorem

1, If tHA-CIS then theorem 2 says we need only compute the parity of k n

the number of special (n-2)-fLxed cubes in B(T). Undoubtedly other refinements are also possible.

2. "Wandering Willie"'* The proof of theorem 2 says things about the number of n-fixed cubes by looking at special (n-l)-flxed cubes and assoc- iating two n-dimensional cubes if they liave a special (n-l)-fixed cube in common. This suggests that a n-fixed cube may be located by wandering through a sequence of special (n-l)-fixed cubes in some manner. One first has to locate an (n-l)-fixed cube and there are other complications.

For convenience, a point in A is a 0-dimensional cube and a special 0-fixed cube is a member of S , Also define D, = {xe[0, 1] | last"n-i-l

components of x are 1}, Thus DC_S. for i > i + 2. D , = D = [0, 1] .

1 J — n-l n

The algorithm generates a sequence of cubes G. of dimension d, as follows:

Step 1 [initialize]: C^ = {(1,...!)}. d^ = 0. i = 1.

Step 2 [wandering attempt]: Let r = d . Try to find a (r + 1)-

dimensional cube ECD which has C, as a face but such that C. _ / E and

r 1 1-1

C._. is not a r-dimensional face of E, If there is no such E go to step

5, otherwise go to step 3.

Step 3 [successful wander]: Try tc find a special r-flxed face of E

that is not among C j...,C . If there is no such face go to step 4.

Otherwise let C.,,=any such face. G.,,=r. Increase i by 1 and return x+1 - 1+1

to step 2.

Step 4 [discovery of special (r + l)-flxed cube]: Let C ,= E.

d.,T = r+1. If d.,,rn stop. Otherwise increase i by 1 and return to x+1 1+1

step 2.

*A similar algorithm has been developed by Wolsey [4].

_7-

Step 5 [smashing into the boundary of D ] : Try to locate a special

(r-l)-fixed face of C, that is not aniong C, ,...C.. If there is none, stop,

Otherwise let C^.^ = any such face, d,,, = r--l , Increase i by 1 and i+1 i+1

return to step 2.

Example: We illustrate "Wandering Willie" for n = 2, k = 3. The points of A, will be abbreviated by capital letters as sho\.m in the diagram:

A	B	C	D
E	V	G	H
J	K	L	M
N	P	Q	R

Thus D corresponds to (1, 1), N corresponds to (0, 0), L corresponds to (2/3, 1/3) and so forth. Let f be such that S = {B, D, F, H, L, M, R} and S^ = {A, B, C, D, E, F, G, H, L}. Then the sequence of cubes C. generated by "Wandering Willie" is:

D(l); CD(4); GH(3) ; GL(3); FG(3); BC(3); B(5); AB(4); EF(3); EFJK(4). EFJK is a 2-fixed cube.

Here we indicate a cube by its vertices and the numbers in parentheses refer to the steps generating the cubes.

Theorem 3^: Wandering Willie halts after a finite number of steps at a n-fixed cube.

Proof (outline): First one shows by induction on L that if C , ...C are the first L cubes generated by W. W. then (a) C , . . .C are all

X JLi

different (b) for 1 < i< L C. is a special d. -fixed cube contained in D , .

— — XI d

(c) if E is a j -dimensional cube in D. which does not have C as a (j-l)-dimensional face, then C^ , . . .C contains an odd number of (j-1)- dimensional faces of E iff. E = C. and either C. was introduced by step 4 or C was introduced at step 5. The induction involves many individually

-8-

simple cases and we omit the details.

Once (a), (b), (c) are established it follows that w. w. can never halt in step 5 (we oiil.y included this possibility for expository reasons). If C, is such that step 2 fails when i = L, C^ cannot have been introduced

L L,

by step 4. So, by (c), an even numboa" of special (d - l)-fixed faces of

Li

C appear in C , ...C . By (b) C has an odd number of special (d, - 1)-

Li S. Li Li Li

fixed faces, so there must be at least one fresh face xjaiting at step 5.

Since w. w. must halt eventually, by (a), and it does not halt in step 5 it must wander into an n-fixed cube. Q.E.D.

We believe that the "worst case" behavior of bifurcation is superior to Wandering Willie in this sense: For any f , bifurcation (where we divide the cube into nearly equal halves at each stage) will locate a n-fixed cube after evaluating f at _< (1 + 4/(1 - (1/2)'^"'"'") (k + l)"""""" of the (k + 1) points of A^. We conjecture that there is a 0 < 9 < 1 independent of k such that functions f can be constructed for which Wandering Willie (or similar algorithnis on aimplexes) will evaluate f at ^k + 1) points before finding an approximate fixed point. [specifically, we conjecture that we may take 6 >^ (1/3)'^].

However, we believe the "typical case" behavior of Wandering Willie will be reasonable. It is clear that unrefined bifurcation is not

practical, since even a single division requires computation of f at

n-1 (k + 1) points.

Hybrids are also a possibility. One idea would be a bifurcation

search on /^ for saiall k. This would locate a "large" n-fixed cube J.

We could then introduce a finer rectangular subdivision only on J. If

fortunate, B(J) would have an odd nuuiber of speciaJ (a-1) -fixed points

with respect to the fine sxibdivision . If this happens, bifurcation can

*This figure can be sharpened.

-9-

be performed on J. If unfortunate, v/e would have to hunt for another large cube (which we hope is close to J) suitable for a second bifurcation.

Another possible algorithm would add (n-1) diiuensional dividing planes on [0, 1]" one at a time, presunably having the next dividing plane pass through the n-flxed cube* currently located. This would be in the spirit of the "eccentric barycentric" adaptive algorithm of Zangwill [5]. Both of the hybrids sacrifice the "worst case" bound of pure bifurcation. Concluding Remarks

A bifurcation algorithm is possible on a simplex. The result analogous to theorem 2 is:

Theorem 4^: Let a subdivided n-dimensional simpley. be arbitrarily labelled with {1, 2,...n+l}. The parity of the number of completely labelled subsimplices is the parity of the number of (n-l)-dimensional stmplices In the boundary which have labels {1, 2,..-,n}. Proof as for theorems 1 and 2. However, the subdivision has to be chosen rather caref ull^;^ .

The similarity between the proofs of theorems 1, 2, and 4 and the "standard" proofs of Sperfijer's Lemma in [1] and [3] should be mentioned. It must be grudgingly admitted that the definition of n-fixed cubes was chosen to make these proofs work.

.All the theorems and algorithms discussed here depended essentially on an arbitrary ordering of the co-ordinates of 'the cube or, equivalently , on a specific order for S ,...S . This is also the xase for many of the algorithms in the literature, and we believe this may be more than an aesthetic defect.

*In this case, we are relaxing the requirement that the edges of the cube are all of equal length.

References

1. Fan, K. Convex Sets and their applications. Argonne National Lab SuTTuner Lectures 1959.

2. Kuhn, H. W. "Some Combinatorial LencQas in Topology", IBM Journal of Research and DevelopToent, k (1960), pp. 508-524,

3. Stoer, J. & Witzgall, C. Convexity and Optimization in Finite Dimensions I^, pp. 126-127, Springer-Verlsg 1970.

4. Wolsey, L.A., "Cubical Sperner Lemmas as applications of generalized complementary pivoting", CORi; discussion paper no. 7507, March 1975.

5. Zangwill, W.I., "An Eccentric Bgrycentric Fixed Point Algorithzn," University of Illinois Business Administration, December 1975, to appear in Math of Operations Research.