An ϵ-Out-of-Kilter Method for Monotropic Programming

The out-of-kilter method was first proposed by Fulkerson (1961) for linear-cost network flow and independently by Minty (1961) for piecewise-linear-cost network flow and was then extended by Rockafellar (1984, Section 11K) to piecewise-linear-cost monotropic programming. We propose an extension of this method, based on Rockafellar's work and on ideas from ϵ-relaxation methods for convex-cost network flow (Bertsekas et al. 1997a, De Leone et al. 1999) to monotropic programming in general. The proposed method is amenable to a complexity analysis and its convergence is based on (essentially) a monotone decrease in vertical distance to the characteristic curve for each index.