Premium
A Newton method for convex separable network flow problems
Author(s) -
Klincewicz John G.
Publication year - 1983
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.3230130310
Subject(s) - quadratic growth , separable space , mathematical optimization , flow network , mathematics , computer science , algorithm , simple (philosophy) , convergence (economics) , matrix (chemical analysis) , multiplier (economics) , newton's method , key (lock) , convex function , regular polygon , matrix completion , mathematical analysis , geometry , quantum mechanics , physics , nonlinear system , philosophy , materials science , computer security , macroeconomics , economic growth , composite material , epistemology , gaussian , economics
Previous feasible direction algorithms for convex, separable network flow problems that have appeared in the literature have all been linearly convergent. In this paper we propose an approximate implementation of the quadratically convergent Newton algorithm. The key to this implementation is a conjugate direction method that determines second‐order dual multiplier estimates at each iteration. This method exploits the network structure in a way that allows certain crucial matrix‐vector products to be computed in a simple pass through the arcs. Since this novel approach requires no matrix storage to compute these products, the algorithm can be used for large‐scale problems. Some computational experience with this new algorithm is reported.