An epsilon-out-of-kilter method for monotropic programming

The out-of-kilter method was first proposed by Fulkerson for linear-cost network flow and independently by Minty for piecewise-linear-cost network flow and was then extended by Rockafellar to piecewise-linear-cost monotropic programming. We propose an extension of this method, based on Rockafellar's work and on ideas from epsilon–relaxation methods for convex-cost network flow 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.