학술논문
Iteration-complexity of block-decomposition algorithms and the alternating direction method of multipliers.
Document Type
Journal
Author
Monteiro, Renato D. C. (1-GAIT-I) AMS Author Profile; Svaiter, Benar F. (BR-IMPA) AMS Author Profile
Source
Subject
47 Operator theory -- 47J Equations and inequalities involving nonlinear operators
47J25Iterative procedures
49Calculus of variations and optimal control; optimization -- 49M Numerical methods
49M27Decomposition methods
65Numerical analysis -- 65K Mathematical programming, optimization and variational techniques
65K10Optimization and variational techniques
90Operations research, mathematical programming -- 90C Mathematical programming
90C25Convex programming
47J25
49
49M27
65
65K10
90
90C25
Language
English
Abstract
Using results from their papers [SIAM J. Optim. {\bf 20} (2010), no.~6, 2755--2787; MR2721154 (2012e:90185); SIAM J. Optim. {\bf 21} (2011), no.~4, 1688--1720; 2869513 ] the authors deal with algorithmic methods for monotone inclusion problems of the form $$ 0\in T(x,y)\coloneq \left\{\pmatrix F_x(x,y)+a\\ F_y(x,y)+b\endpmatrix \colon \ a\in A(x),\ b\in B(y)\right\},$$ where for finite-dimensional inner product spaces $X$ and $Y$, $F=(F_x,F_y)\:X\times Y\to X\times Y$ is a continuous map, and $A\:X\rightrightarrows X$ and $B\:Y\rightrightarrows Y$ are maximal monotone operators. The point of this paper is to construct (as a framework, as the authors write) a block-decomposition method with the aim that each of the single-block systems must only be solved in an approximate sense, and then to derive convergence results. As a background of their method, the authors use Rockafellar's proximal point method in a version called the hybrid proximal extragradient method, as given in papers by M.~V. Solodov and B.~F. Svaiter [cf. Numer. Funct. Anal. Optim. {\bf 22} (2001), no.~7-8, 1013--1035; MR1871872 (2002h:49018)]. Some applications supplement the theory: first, they show the ergodic iteration-complexity of the Douglas-Rachford splitting method, and second, they can handle the alternating direction method of Lagrange multipliers as a special case of their results applied to a class of convex optimization problems under some additional conditions.