Approximate Primal Solutions and Rate Analysis for Dual Subgradient Methods
Top Cited Papers
- 1 January 2009
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Optimization
- Vol. 19 (4), 1757-1780
- https://doi.org/10.1137/070708111
Abstract
In this paper, we study methods for generating approximate primal solutions as a byproduct of subgradient methods applied to the Lagrangian dual of a primal convex (possibly nondifferentiable) constrained optimization problem. Our work is motivated by constrained primal problems with a favorable dual problem structure that leads to efficient implementation of dual subgradient methods, such as the recent resource allocation problems in large-scale networks. For such problems, we propose and analyze dual subgradient methods that use averaging schemes to generate approximate primal optimal solutions. These algorithms use a constant stepsize in view of its simplicity and practical significance. We provide estimates on the primal infeasibility and primal suboptimality of the generated approximate primal solutions. These estimates are given per iteration, thus providing a basis for analyzing the trade-offs between the desired level of error and the selection of the stepsize value. Our analysis relies on the Slater condition and the inherited boundedness properties of the dual problem under this condition. It also relies on the boundedness of subgradients, which is ensured by assuming the compactness of the constraint set.Keywords
This publication has 17 references indexed in Scilit:
- Lagrangian Relaxation via Ballstep Subgradient MethodsMathematics of Operations Research, 2007
- Layering as Optimization Decomposition: A Mathematical Theory of Network ArchitecturesProceedings of the IEEE, 2007
- Non-euclidean restricted memory level method for large-scale convex optimizationMathematical Programming, 2004
- The Ordered Subsets Mirror Descent Optimization Method with Applications to TomographySIAM Journal on Optimization, 2001
- The volume algorithm: producing primal solutions with a subgradient methodMathematical Programming, 2000
- Ergodic, primal convergence in dual subgradient schemes for convex programmingMathematical Programming, 1999
- Rate control for communication networks: shadow prices, proportional fairness and stabilityJournal of the Operational Research Society, 1998
- Ergodic convergence in subgradient optimizationOptimization Methods and Software, 1998
- A Lagrangean Relaxation Scheme for Structured Linear Programs With Application To Multicommodity Network FlowsOptimization, 1997
- Convergence of some algorithms for convex minimizationMathematical Programming, 1993