2015/07/02 by Dimitri P. Bertsekas, Bertsekas, Dimitri P.
Computer Science · Mathematics · Physics and Astronomy · #Advanced Optimization Algorithms Research #Complex Network Analysis Techniques #FOS: Mathematics #Numerical Analysis (math.NA) #Optimization and Control (math.OC) #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1507.00702
openalex publication_date 2015/07/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider Newton methods for common types of single commodity and multi-commodity network flow problems. Despite the potentially very large dimension of the problem, they can be implemented using the conjugate gradient method and low-dimensional network operations, as shown nearly thirty years ago. We revisit these methods, compare them to more recent proposals, and describe how they can be implemented in a distributed computing system. We also discuss generalizations, including the treatment of arc gains, linear side constraints, and related special structures.