Relaxation methods for monotropic programs

Research output: Contribution to journalArticlepeer-review

7 Scopus citations


We propose a dual descent method for the problem of minimizing a convex, possibly nondifferentiable, separable cost subject to linear constraints. The method has properties reminiscent of the Gauss-Seidel method in numerical analysis and uses the ε-complementary slackness mechanism introduced by D.P. Bertsekas, P.A. Hosein and P. Tseng to ensure finite convergence to near optimality. As special cases we obtain the methods of Bertsekas et al. for network flow programs and the methods in P. Tseng and D.P. Bertsekas for linear programs.

Original languageEnglish (US)
Pages (from-to)127-151
Number of pages25
JournalMathematical Programming
Issue number2
StatePublished - Feb 1990
Externally publishedYes

ASJC Scopus subject areas

  • Software
  • General Mathematics


Dive into the research topics of 'Relaxation methods for monotropic programs'. Together they form a unique fingerprint.

Cite this