Optimization Online


An optimal first-order primal-dual gap reduction framework for constrained convex optimization

Quoc Tran-Dinh(quoctd***at***email.unc.edu)
Volkan Cevher(volkan.cevher***at***epfl.ch)

Abstract: We introduce an analysis framework for constructing optimal first-order primal-dual methods for the prototypical constrained convex optimization tem- plate. While this class of methods offers scalability advantages in obtaining nu- merical solutions, they have the disadvantage of producing sequences that are only approximately feasible to the problem constraints. As a result, it is theoretically challenging to compare the efficiency of different methods. To this end, we rig- orously prove in the worst-case that the convergence of primal objective residual in first-order primal-dual algorithms must compete with their constraint feasibil- ity convergence, and mathematically summarize this fundamental trade-off. We then provide a heuristic-free analysis recipe for constructing optimal first-order primal-dual algorithms that can obtain a desirable trade-off between the primal objective residual and feasibility gap and whose iteration convergence rates cannot be improved. Our technique obtains a smoothed estimate of the primal-dual gap and drives the smoothness parameters to zero while simultaneously minimizing the smoothed gap using problem first-order oracles.

Keywords: Model-based gap reduction technique; first-order primal-dual meth- ods; augmented Lagrangian; smoothing techniques; separable convex minimiza- tion; parallel and distributed computation

Category 1: Convex and Nonsmooth Optimization

Citation: Tech. Report, October 2015

Download: [PDF]

Entry Submitted: 10/25/2015
Entry Accepted: 10/25/2015
Entry Last Modified: 10/25/2015

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