The (n + 1)2^m-ray algorithm: a new simplicial algorithm for the variational inequality problem on ℝ ^m₊ ×S ⁿ

Abstract

In this paper we propose a variable dimension simplicial algorithm for solving the variational inequality problem on the cross product of the nonnegative orthant ℝ ^m₊ of them-dimensional Euclidean space ℝ^m and then-dimensional unit simplexS ⁿ of ℝⁿ⁺¹. Starting from an arbitrary point (u, v) єℝ ^m₊ ×S ⁿ, the algorithm generates a piecewise linear path in ℝ ^m₊ ×S ⁿ. The path is traced by making alternately linear programming pivot operations and replacement steps in an appropriate simplicial subdivision of ℝ ^m₊ ×S ⁿ. The algorithm differs from the thus far known algorithm in the number of directions in which it may leave the starting point. More precisely, the algorithm has (n+1)2^m rays to leave the starting point whereas the existing algorithm hasn+m+1 rays. A convergence condition is presented and the accuracy estimation of an approximate solution generated is also given.