Dual-based Newton methods for nonlinear minimum cost network flow problems

Nonlinear network optimization is of great importance not only in theory but also in practical applications. The range of its applications covers a variety of problems which arise in transportation systems, water distribution systems, resistive electrical networks, and so on. There are various methods to solve nonlinear network flow problems, and many of them belong to the class of descent methods which successively generate search directions and perform line searches. This paper proposes an algorithm, based on the Newton method, which exploits the network structure of the problems. The algorithm directly solves the dual problem which, under appropriate conditions, can be formulated as an unconstrained convex minimization problem with a continuously differentiable objective function. It gives a global convergence theorem of the algorithm and present practical strategies for computing search directions and finding steplengths. Some computational results for test problems of up to 4900 nodes and 14490 arcs show the practical efficiency of the proposed algorithm.