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

Authors
Citation
P. Tseng, An epsilon-out-of-kilter method for monotropic programming, MATH OPER R, 26(2), 2001, pp. 221-233
Citations number
19
Language
INGLESE
art.tipo
Article
Categorie Soggetti
Mathematics
Journal title
MATHEMATICS OF OPERATIONS RESEARCH
ISSN journal
0364-765X → ACNP
Volume
26
Issue
2
Year of publication
2001
Pages
221 - 233
Database
ISI
SICI code
0364-765X(200105)26:2<221:AEMFMP>2.0.ZU;2-0
Abstract
The out-of-kilter method was first proposed by Fulkerson (1961) for linear- cost network flow and independently by Minty (1961) for piecewise-linear-co st network Row and was then extended by Rockafellar (1984, Section 11K) to piecewise-linear-cost monotropic programming. We propose an extension of th is method, based on Rockafellar's work and on ideas from epsilon -relaxatio n methods for convex-cost network flow (Bertsekas et al. 1997a, De Leone et al. 1999) to monotropic programming in general. The proposed method is ame nable to a complexity analysis and its convergence is based on (essentially ) a monotone decrease in vertical distance to the characteristic curve for each index.