In this article we consider a consistent convex feasibility problem in a real Hilbert space defined by a finite family of sets @math . We are interested, in particular, in the case where for each @math , @math , @math is a cutter and @math is a proximity function. Moreover, we make the following assumption: the computation of @math is at most as difficult as the evaluation of @math and this is at most as difficult as projecting onto @math . We study a double-layer fixed point algorithm which applies two types of controls in every iteration step. The first one -- the outer control -- is assumed to be almost cyclic. The second one -- the inner control -- determines the most important sets from those offered by the first one. The selection is made in terms of proximity functions. The convergence results presented in this manuscript depend on the conditions which first, bind together the sets, the operators and the proximity functions and second, connect the inner and outer controls. In particular, weak regularity (demi-closedness principle), bounded regularity and bounded linear regularity imply weak, strong and linear convergence of our algorithm, respectively. The framework presented in this paper covers many known (subgradient) projection algorithms already existing in the literature; for example, those applied with (almost) cyclic, remotest-set, maximum displacement, most-violated constraint and simultaneous controls. In addition, we provide several new examples, where the double-layer approach indeed accelerates the convergence speed as we demonstrate numerically.
We would like to begin with two important general observations regarding the types of convergence one could expect. The first is that in the infinite dimensional setting, in view of Hundal's counterexample, it may happen that even for basic cyclic or parallel projection methods the convergence can only be in the weak topology; see @cite_29 and @cite_34 . Moreover, the result of [Theorem 1.4] BauschkeDeutschHundal2009 shows that norm convergence can be far away from a linear rate. Furthermore, it can be arbitrarily slow. See also @cite_2 in this connection. Thus both norm and linear convergence require some additional assumptions to which we refer in general as bounded regularity and bounded linear regularity.
@cite_29 @cite_34 @cite_2
2100904599 2782375002 1549918636 2962853966
Recently, Hundal has constructed a hyperplane H , a cone K, and a starting point y0 in ‘2 such that the sequence of alternating projections ((PK PH ) n y0)n∈N converges weakly to some point in H ∩ K, but not in norm. We show how this construction results in a counterexample to norm convergence for iterates of averaged projections; hence, we give an a:rmative answer to a question raised by Reich two decades ago. Furthermore, new counterexamples to norm convergence for iterates of <rmly nonexpansive maps (=a la Genel and Lindenstrauss) and for the proximal point algorithm (= al a G@ uler) are provided. We also present a counterexample, along with some weak and norm convergence results, for the new framework of string-averaging projection methods introduced by Extensions to Banach spaces and the situation for the Hilbert ball are discussed as well. ? 2003 Elsevier Ltd. All rights reserved. MSC: 47H09; 47J25; 90C25 Recently, there has been significant progress in the development of distributed first-order methods. In particular, (2015) on the one hand and Qu and Li (2017) and (2016) on the other hand propose two different types of methods that are designed from very different perspectives. They achieve both exact and linear convergence when a constant step size is used—a favorable feature that was not achievable by most prior methods. In this paper, we unify, generalize, and improve convergence speed of the methods by (2015), Qu and Li (2017), and (2016), when the underlying network is static and undirected. We first carry out a unifying primal-dual analysis that sheds light on how these methods compare. The analysis reveals that a major difference between the methods is on how the primal error affects the dual error along iterations. We, then, capitalize on the insights from the analysis to derive a novel method that can reduce the negative effect of the primal error on the dual error. We establish for the proposed generalized method global R-linear convergence rate under strongly convex costs with Lipschitz continuous gradients. The formulation @math minx,yf(x)+g(y),subjecttoAx+By=b,where f and g are extended-value convex functions, arises in many application areas such as signal processing, imaging and image processing, statistics, and machine learning either naturally or after variable splitting. In many common problems, one of the two objective functions is strictly convex and has Lipschitz continuous gradient. On this kind of problem, a very effective approach is the alternating direction method of multipliers (ADM or ADMM), which solves a sequence of f g-decoupled subproblems. However, its effectiveness has not been matched by a provably fast rate of convergence; only sublinear rates such as O(1 k) and @math O(1 k2) were recently established in the literature, though the O(1 k) rates do not require strong convexity. This paper shows that global linear convergence can be guaranteed under the assumptions of strong convexity and Lipschitz gradient on one of the two functions, along with certain rank assumptions on A and B. The result applies to various generalizations of ADM that allow the subproblems to be solved faster and less exactly in certain manners. The derived rate of convergence also provides some theoretical guidance for optimizing the ADM parameters. In addition, this paper makes meaningful extensions to the existing global convergence theory of ADM generalizations. In this paper, we analyze the convergence of the alternating direction method of multipliers (ADMM) for minimizing a nonconvex and possibly nonsmooth objective function, ( (x_0, ,x_p,y) ), subject to coupled linear equality constraints. Our ADMM updates each of the primal variables (x_0, ,x_p,y ), followed by updating the dual variable. We separate the variable y from (x_i )’s as it has a special role in our analysis. The developed convergence guarantee covers a variety of nonconvex functions such as piecewise linear functions, ( _q ) quasi-norm, Schatten-q quasi-norm ( (0<q<1 )), minimax concave penalty (MCP), and smoothly clipped absolute deviation penalty. It also allows nonconvex constraints such as compact manifolds (e.g., spherical, Stiefel, and Grassman manifolds) and linear complementarity constraints. Also, the (x_0 )-block can be almost any lower semi-continuous function. By applying our analysis, we show, for the first time, that several ADMM algorithms applied to solve nonconvex models in statistical learning, optimization on manifold, and matrix decomposition are guaranteed to converge. Our results provide sufficient conditions for ADMM to converge on (convex or nonconvex) monotropic programs with three or more blocks, as they are special cases of our model. ADMM has been regarded as a variant to the augmented Lagrangian method (ALM). We present a simple example to illustrate how ADMM converges but ALM diverges with bounded penalty parameter ( ). Indicated by this example and other analysis in this paper, ADMM might be a better choice than ALM for some nonconvex nonsmooth problems, because ADMM is not only easier to implement, it is also more likely to converge for the concerned scenarios.