Optimization Online


Iteration-complexity of block-decomposition algorithms and the alternating minimization augmented Lagrangian method

Renato D.C. Monteiro(monteiro***at***isye.gatech.edu)
Benar F. Svaiter(benar***at***impa.br)

Abstract: In this paper, we consider the monotone inclusion problem consisting of the sum of a continuous monotone map and a point-to-set maximal monotone operator with a separable two-block structure and introduce a framework of block-decomposition prox-type algorithms for solving it which allows for each one of the single-block proximal subproblems to be solved in an approximate sense. Moreover, by showing that any method in this framework is also a special instance of the hybrid proximal extragradient (HPE) method introduced by Solodov and Svaiter, we derive corresponding convergence rate results. We also describe some instances of the framework based on specific and inexpensive schemes for solving the single-block proximal subproblems. Finally, we consider some applications of our methodology to: i) propose new algorithms for the monotone inclusion problem consisting of the sum of two maximal monotone operators, and; ii) study the complexity of the classical alternating minimization augmented Lagrangian method for a class of linearly constrained convex programming problems with proper closed convex objective functions.

Keywords: block-decomposition, alternating minimization, complexity, augmented lagrangian, splitting methods, monotone inclusion, convex programming

Category 1: Convex and Nonsmooth Optimization

Category 2: Complementarity and Variational Inequalities


Download: [PDF]

Entry Submitted: 08/22/2010
Entry Accepted: 08/23/2010
Entry Last Modified: 08/22/2010

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