Optimization Online


Approximate Primal Solutions and Rate Analysis in Dual Subgradient Methods

Angelia Nedich(angelia***at***uiuc.edu)
Asuman Ozdaglar(asuman***at***mit.edu)

Abstract: We study primal solutions obtained as a by-product of subgradient methods when solving the Lagrangian dual of a primal convex constrained optimization problem (possibly nonsmooth). The existing literature on the use of subgradient methods for generating primal optimal solutions is limited to the methods producing such solutions only asymptotically (i.e., in the limit as the number of subgradient iterations increases to infinity). Furthermore, no convergence rate results are known for these algorithms. In this paper, we propose and analyze dual subgradient methods using averaging to generate approximate primal optimal solutions. These algorithms use a constant stepsize as opposed to a diminishing stepsize which is dominantly used in the existing primal recovery schemes. We provide estimates on the convergence rate of the primal sequences. In particular, we provide bounds on the amount of feasibility violation of the generated approximate primal solutions. We also provide upper and lower bounds on the primal function values at the approximate solutions. The feasibility violation and primal value estimates are given per iteration, thus providing practical stopping criteria. Our analysis relies on the Slater condition and the inherited boundedness properties of the dual problem under this condition.

Keywords: nondifferentiable optimization, subgradient methods, averaging, approximate primal solutions, convergence rate

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Category 2: Convex and Nonsmooth Optimization (Nonsmooth Optimization )

Category 3: Nonlinear Optimization (Constrained Nonlinear Optimization )

Citation: LIDS Technical Report 2753, Massachusetts Institute of Technology, Lab. for information and Decision Systems, March 2007

Download: [PDF]

Entry Submitted: 03/29/2007
Entry Accepted: 03/29/2007
Entry Last Modified: 03/29/2007

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society