Optimization Online


A Block Successive Upper Bound Minimization Method of Multipliers for Linearly Constrained Convex Optimization

Mingyi Hong(mhong***at***umn.edu)
Tsung-Hui Chang(tsunghui.chang***at***ieee.org)
Xiangfeng Wang(wangxf***at***smail.nju.edu.cn)
Meisam Razaviyayn(meisam***at***umn.edu)
Shiqian Ma(sqma***at***se.cuhk.edu.hk)
Zhi-Quan Luo(luozq***at***umn.edu)

Abstract: Consider the problem of minimizing the sum of a smooth convex function and a separable nonsmooth convex function subject to linear coupling constraints. Problems of this form arise in many contemporary applications including signal processing, wireless networking and smart grid provisioning. Motivated by the huge size of these applications, we propose a new class of first order primal-dual algorithms called the block successive upper-bound minimization method of multipliers (BSUM-M) to solve this family of problems. The BSUM-M updates the primal variable blocks successively by minimizing locally tight upper-bounds of the augmented Lagrangian of the original problem, followed by a gradient type update for the dual variable in closed form. We show that under certain regularity conditions, and when the primal block variables are updated in either a deterministic or a random fashion, the BSUM-M converges to the set of optimal solutions. Moreover, in the absence of linear constraints, we show that the BSUM-M, which reduces to the block successive upper-bound minimization method, is capable of linear convergence without strong convexity.

Keywords: Block successive upper-bound minimization, alternating direction method of multipliers, randomized block coordinate descent

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Category 2: Convex and Nonsmooth Optimization (Nonsmooth Optimization )


Download: [PDF]

Entry Submitted: 01/27/2014
Entry Accepted: 01/27/2014
Entry Last Modified: 01/27/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