Computing equilibria on large multicommodity networks: An application of truncated quadratic programming algorithms

Publisher Website
Google Scholar
Abstract
We present a general scheme for improving the asymptotic behavior of a given nonlinear programming algorithm without incurring a significant increase in storage overhead. To enhance the rate of convergence we compute search directions by partially solving a sequence of quadratic programming (QP) problems as suggested by Dembo [6]. The idea is illustrated on a class of extremely large nonlinear programming problems arising from traffic equilibrium calculations using both the Frank‐Wolfe and PARTAN algorithms to partially solve the QP subproblems. Computational results indicate that the convergence rate of the underlying algorithm is indeed enhanced significantly when Frank‐Wolfe is used to solve the QP subproblems but only marginally so in the case of PARTAN. It is conjectured, and supported by the theory [11], that with better algorithms for the QP subproblems the improvements due to the proposed framework would be more marked.