This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Kiwiel, K. C. Articles by Lindberg, P. O. Search for Related Content

Lagrangian Relaxation via Ballstep Subgradient Methods

Systems Research Institute, Newelska 6, 01-447 Warsaw, Poland
Department of Mathematics, Linköping University, S-58183 Linköping, Sweden
Department of Mathematics, Linköping University, S-58183 Linköping, Sweden
kiwiel{at}ibspan.waw.pl
tolar{at}math.liu.se
polin{at}math.liu.se

We exhibit useful properties of ballstep subgradient methods for convex optimization using level controls for estimating the optimal value. Augmented with simple averaging schemes, they asymptotically find objective and constraint subgradients involved in optimality conditions. When applied to Lagrangian relaxation of convex programs, they find both primal and dual solutions, and have practicable stopping criteria. Up until now, similar results have only been known for proximal bundle methods, and for subgradient methods with divergent series stepsizes, whose convergence can be slow. Encouraging numerical results are presented for large-scale nonlinear multicommodity network flow problems.

Key Words: convex programming; nondifferentiable optimization; subgradient optimization; Lagrangian relaxation; level projection methods
History: Received: January 10, 2004; revision received: August 23, 2006;