Premium
Computing equilibria on large multicommodity networks: An application of truncated quadratic programming algorithms
Author(s) -
Dembo Ron S.,
Tulowitzki Ulrich
Publication year - 1988
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230180403
Subject(s) - quadratic programming , rate of convergence , convergence (economics) , mathematical optimization , sequence (biology) , mathematics , overhead (engineering) , algorithm , nonlinear programming , quadratic equation , scheme (mathematics) , nonlinear system , computer science , linear programming , computer network , channel (broadcasting) , mathematical analysis , physics , geometry , quantum mechanics , biology , economics , genetics , economic growth , operating system
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.