Mathematics of Operations Research August 1989 [antikvár]

mathematics of operations research Vol. 14, No. 3. August 1989 PriiiKd in U.S.A. A SIMPLICIAL ALGORITHM FOR STATIONARY POINT PROBLEMS ON POLYTOPES*^ A. J. J. TALMAN* and Y. YAMAMOTO® A simplicial variable dimension restart algorithm for the stationary point problem or variational inequality problem on a polytope is proposed. Given a polytope C in R" and a continuous function /¦.€-> R", find a point jc in C such that f(x) ¦ x > f(x) ¦ x for any point X in C. Starting from an arbitrary point v in C, die algorithm generates a piecewise linear path of points in C. This path is followed by alternating linear programming pivot steps to follow a linear piece of the path and replacement steps in a simplicial subdivision of C. Within a finite number of function evaluations and linear programming pivot steps the algorithm finds an approximate stationary point. The algorithm leaves the starting point v along a ray pointing to one of the vertices w of C. The vertex w is obtained from the optimum solution of the linear programming problem maximize f(u) • x subject to x e C. 1. Introduction. In order to compute zero points of continuous functions on the Euclidean space R", many so-called simphcial variable dimension algorithms have been introduced. Such an algorithm subdivides R" into «-dimensional simphces and searches for a simplex that contains an approximate zero point or solution. Starting in an arbitrarily chosen grid point of the triangulation the algorithm generates, through alternating linear prograimning pivot steps in a system of typically n + 1 Unear equations and replacement steps in the triangulation, a sequence of adjacent simplices of varying dimension. Given some coercivity condition the algorithm then generates within a finite number of steps an approximate solution. When the accuracy is not satisfactory, the algorithm can be restarted at the approximate solution with a finer triangulation in the hope that within a small number of iterations a better approximate solution is found. Simplicial variable dimension restart algorithms dilfer from each other in the number of rays along which the algorithm may leave the starting point. Such an algorithm with n + 1 rays, the (n -I- l)-ray algorithm, was proposed in van der Laan and Talman [12]. The 2n-ray algorithm was also introduced in [12], the 2"-ray algorithm in [18], and the (3" - l)-ray algorithm in [10]. A unifying approach for these algorithms was given in van der Laan and Talman [13], see also Yamamoto [19]. In [13] the piecewise linear (abbreviated by pi) path traced by the algorithm when generating the sequence of adjacent simplices of varying dimetision is interpreted as a curve of stationary points to the underlying problem with respect to an expanding set containing the starting point in its interior. For the nonlinear complementarity problem on the «-dimensional unit simplex and the cross product of several unit simphces, S, simplicial restart algorithms have also •Received July 8, 1986; revised April 13, 1988. AMS !980 subject classification. Primary: 49D35. Secondary: 90C30, 90C33. lAOR 1973 subject classification. Main: Programming: Nonlinear. OR/MS Index 1978 subject classification. Primary: 654 Programming/Nonlinear/Algorithms. Key words. Stationary point, variational inequality, simplicial algorithm, piecewise linear approximation, triangulation. ^This research is part of the VF-program "Equilibrium and Disequilibrium in Demand and Supply" which has been approved by the Netherlands Ministry of Education and Sciences. *Tilburg University. 'University of Tsukuba. 383