Optimization Online


A Primal-Dual Algorithmic Framework for Constrained Convex Minimization

Quoc Tran-Dinh(quoc.trandinh***at***epfl.ch)
Volkan Cevher(volkan.cevher***at***epfl.ch)

Abstract: We present a primal-dual algorithmic framework to obtain approximate solutions to a prototypical constrained convex optimization problem, and rigorously characterize how common structural assumptions affect the numerical efficiency. Our main analysis technique provides a fresh perspective on Nesterov's excessive gap technique in a structured fashion and unifies it with smoothing and primal-dual methods. For instance, through the choices of a dual smoothing strategy and a center point, our framework subsumes decomposition algorithms, augmented Lagrangian as well as the alternating direction method-of-multipliers methods as its special cases, and provides optimal convergence rates on the primal objective residual as well as the primal feasibility gap of the iterates for all.

Keywords: Primal-dual method; optimal first-order method; augmented Lagrangian; alternating direction method of multipliers; separable convex minimization; monotropic programming; parallel and distributed algorithm.

Category 1: Convex and Nonsmooth Optimization

Citation: Tech. Report, EPFL-REPORT-199844

Download: [PDF]

Entry Submitted: 06/22/2014
Entry Accepted: 06/23/2014
Entry Last Modified: 06/22/2014

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 Optimization Society