Bierlaire, M., and Crittin, F. (2006)
Solving noisy large scale fixed point problems and systems of nonlinear equations, Transportation Science 40(1):44-63.
Many complex transportation models can be formulated as fixed-point problems. Typical examples are the “equilibrium-like” models, motivated by the need to capture the interaction between the transport supply (that is, the infrastructure) and transport demand (that is, travelers’ behavior) in various ways. In this paper, we propose a new approach for solving fixed-point problems and, equivalently, systems of nonlinear equations. It is a generalization of secant methods, and uses several previous iterates to generate a linear approximation of the nonlinear function. Although it belongs to the quasi-Newton family of methods, our algorithm is matrix free, allowing it to solve large-scale systems of equations without derivative and without any particular assumption about the structure of the problem or its Jacobian. Computational experiments on standard problems show that this algorithm outperforms classical, large-scale quasi-Newton methods in terms of efficiency and robustness. Its numerical performances are similar to Newton- Krylov methods currently considered as the best algorithms to solve large-scale nonlinear systems of equations. Furthermore, our approach, using multiple previous iterates to build a linear approximation of the nonlinear function, exhibits robust behavior in the presence of noise in the equations, which makes it particularly well adapted to transportation problems. We run our algorithm on a simple origin-destination (OD) matrix estimation problem and on some instances of the consistent anticipatory route guidance (CARG) problem, to illustrate the applicability of the proposed method and to show its significant superiority to the classical method of successive averages (MSA). Regarding size, we were able to solve a CARG problem with more than 120,000 variables. We were also able to solve classical problems with up to two million variables.