An efficient integer labeling method for solving systems of nonlinear equations with separable mappings

Homotopy methods are known to be globally convergent algorithms for solving systems of nonlinear equations arising from economic equilibria, game theory, programming problems and network analysis. There are two fundamental types of homotopy methods. Simplicial algorithms are the first type and the second is by solving differential equations. As one of the simplicial type algorithms, an integer labeling method is known which does not require matrix operations. Although simplicial algorithms are efficient for small problems, they become extremely inefficient for large scale problems. This inefficiency is caused by the fact that one n-dimensional rectangle contains n! simplices. In this paper, an efficient integer labeling method is proposed for solving systems of nonlinear equations with separable mappings. For a vector labeling method, an efficient algorithm using a rectangular subdivision has already been proposed by Kojima. For the integer labeling method, however, such a rectangular algorithm has not been proposed because integer labeling on rectangles is essentially impossible. In this paper, the concept ‘rectangular subdivision’ is effectively utilized for reducing the number of function evaluations, while integers are labeled on simplices. A numerical example shows that 100-dimensional problem can be solved by the present method 3000 times faster than the conventional integer labeling method. [In Japanese.]