{'fraction_non_alphanumeric': 0.06441074211725213, 'fraction_numerical': 0.018163289773408465, 'mean_word_length': 3.669045619927232, 'pattern_counts': {'":': 0, '<': 22, '<?xml version=': 0, '>': 32, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 21, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Projection Algorithms for Finite Sum Constrained Optimization

Parallel and cyclic projection algorithms are proposed for minimizing the sum of a finite family of convex functions over the intersection of a finite family of closed convex subsets of a Hilbert space. These algorithms are of predictor-corrector type, with each main iteration consisting of an inner cycle of subgradient descent process followed by a projection step. We prove the convergence of these methods to an optimal solution of the composite minimization problem under investigation upon assuming boundedness of the gradients at the iterates of the local functions and the stepsizes being chosen appropriately, in the finite-dimensional setting. We also discuss generalizations and limitations of the proposed algorithms and our techniques.


Introduction
We are concerned with a composite minimization problem, that is, we consider the case where the objective function is decomposed into the sum of a finite family of convex functions and the set of constraints is the intersection of finitely many closed convex subsets of a real Hilbert space H. Precisely, the minimization problem under investigation in this paper is of the form (1.1) min where M, N are positive integers, each set C i is a nonempty closed convex subset of H, and each component function f j : H → R is a convex function. We always assume the feasible set C = ∅. Large-scale optimization problems of form (1.1) naturally arise in modern applications, in particular, network design [12,16] and machine learning [14,15,26]. When the constraint of (1.1) is defined explicitly by the system of inequalities, penalty and augmented Lagrangian techniques, as well as proximal and bundle methods can be applied to this problem. However, when projections onto the constraint sets are readily available, the treatment of constraints via projections techniques may be preferable as computationally robust and memory efficient. One approach that allows to apply projection methods to (1.1) is to replace the optimization problem (1.1) with a sequence of CFPs as is done in [13]. Our development is more direct: we build on the ideas of [11] to prove the convergence of subgradient projection techniques that utilize projections onto individual constraint sets. We note that despite a large body of work dedicated to solving convex feasibility problems via projection methods (see [4,5,8,17,23] for recent advancements and [3,7] for textbook exposition) and vast literature on optimization methods that utilize a single projection onto the constraint set (for recent works see, e.g. [18,19,25]), little is done in combining optimization and projection steps on several sets, beyond the aforementioned paper by De Pierro and Helou Neto [11]. Our aim is to make a substantial contribution towards bridging this gap. Recent progress on forcing the convergence of Douglas-Rachford type methods to the smallest norm feasible point [1] also indicates that it may be possible to extend our approach to a larger class of projection techniques.
The convex feasibility problem (CFP) [2,9] is formulated as finding a point x * with the property: Thus, the composite minimization problem (1.1) can alternatively be rephrased as finding a solution to the convex feasibility problem (1.2) which also minimizes the composite function f as defined in (1.1). Consequently, two points should be taken into consideration of algorithmic approaches to (1.1): (a) the descent property of the values of the objective function f , and (b) the (approximate) feasibility of the iterates generated by the algorithm.
To illustrate these points we consider the special case where M = N = 1 and the function f 1 is smooth. In this case, (1.1) is reduced to the constrained convex minimization: The gradient-projection algorithm (GPA) can solve (1.3): GPA generates a sequence {x k } by the recursion process: where the initial guess x 0 ∈ H is chosen arbitrarily, and λ k > 0 is the stepsize. Assume: (A1) The gradient of f 1 , ∇f 1 , is α-Lipschitz (for some α ≥ 0): (A2) The sequence of stepsizes, {λ k }, satisfies the condition: It is then easy to find that both points (a) and (b) hold (actually, (b) holds trivially); moreover, the sequence {x k } generated by GPA (1.4) converges [22,28] weakly to a solution of (1.3) (if any).
Observe that the splitting of the objective function f into the sum of N (simpler) component functions, and the set C of constraints into the intersection of M (simpler) convex subsets aims at providing more efficient algorithmic approaches to (1.1) by utilizing the simpler structures of the component functions {f j } (for instance, the proximal mappings of f j are computable [10]) and of the sets {C i } (for instance, the projections P C i possess closed formulae). This means that when we study algorithms for the composite optimization problem (1.1), we should use individual component functions and individual subsets at each iteration, not the full sum of the component functions {f j }, nor the full intersection of the sets {C i }.
The purpose of this paper is to analyse the convergence of parallel and cyclic projection algorithms for solving the optimization problem (1.1), significantly expanding the results of De Pierro and Helou Neto in [11] who focussed on the sequential projections version of the method. We provide a unified analysis of all three methods in the finite-dimensional setting.
The projection algorithms studied in this paper start with an arbitrary point x 0 ∈ H and produce the iterates x k+1 (k ≥ 0), alternating between subgradient and projection steps.
The generic form of our projection algorithm is as follows.
(Projection algorithm) Here by ∂f j (x) we denote the Moreau-Rockafellar subdifferential of the convex function f j at a point x for any j ∈ {1, . . . , N}, and V k+1 is the (modification of) projection operator, distinguishing the three methods. We have explicitly for k ≥ 0 for sequential projections; for parallel projections. The sequential projection algorithm was introduced by De Pierro and Helou Neto in [11], in this case the projection step is a full cycle of projections onto the M sets whose intersection comprises the feasibility region. Explicitly we have (Sequential projections) In the finite-dimensional case, De Pierro and Helou Neto discussed the convergence properties of the above algorithm (note that generalized the original method slightly, replacing gradients with subgradients; this does not affect the convergence analysis that relies on the convexity of the component objective functions rather than their differentiability). Moreover, they raised several open questions regarding projection algorithms for solving (1.1), one of which is whether the sequential projections in their algorithm can be replaced with the parallel projections. We answer this question in the affirmative, not only for parallel, but also for the cyclic version of the algorithm.
Our main result is the following direct generalization of [11, Theorem 1].
Theorem 1.1. Let dim H < ∞, suppose that the sets C 1 , . . . , C M ⊂ H are closed and convex, and let x 0 ∈ H. Assume that the real-valued convex functions f 1 , . . . , f N are defined on some convex subsets D 1 , . . . , D N of H such that x k,j−1 ∈ D j , j ∈ {1, . . . , N}, k ≥ 0 (for a choice of cyclic, sequential or parallel projection algorithm) and there exist constants L 1 , . . . , L N such that Moreover, assume that the sequence (x k ) (obtained via the chosen method) is bounded and Then the sequence {f (x k )} converges to the optimal value f * := inf x∈C f (x), and every cluster point of {x k } is an optimal solution of (1.1), given that the solution set is nonempty.
Note that our assumptions are standard in the analysis of numerical methods, and can be replaced by more constructive or convenient conditions, with some loss of generality.
The proof of our main result (Theorem 1.1) relies on the key property of asymptotic feasibility (that ensures the cluster points of the iterative sequence converge to the feasible set). We prove asymptotic feasibility for the methods of parallel and cyclic projections in Section 3, and present the complete proof of Theorem 1.1 in Section 4. Note that even though we follow the general framework of De Pierro and Helou Neto, our proofs of asymptotic feasibility for cyclic and parallel projections are based on entirely different ideas.
We begin our discussion with introducing some notation and other preliminary information and results in Section 2, and after presenting the proof of the main results in Sections 3 and 4, provide a discussion of some generalizations including the infinitedimensional setting, and some practical improvements and modifications of the methods.

Notation and Preliminaries
The fundamental tool of our argument in this paper is the concept of projections. Let H be a real Hilbert space with inner product ·, · and norm · , respectively, and let C be a nonempty closed convex subset of H. The (nearest point) projection from H onto C, dented by P C , is defined by The following well-known properties are pertinent to our argument in Section 3.
Proposition 2.1. Let H be a real Hilbert space, and for any closed convex set C ⊆ H let P C be the projector operator defined by (2.1). Then the following properties hold.
for all x, y ∈ H; in particular, P C is nonexpansive, namely, We also define the distance function from a point x ∈ H to a set E ⊆ H as Observe that for a closed convex set C we have d C (x) = x − P C x . As mentioned earlier, the CFP (1.2) can be solved by the projection onto convex sets method (POCS), whose convergence is well-understood in the general context of real Hilbert spaces. We recall the well-known convergence results of two major POCS algorithms [2,9,21,27].
Theorem 2.2. Beginning with an arbitrarily chosen initial guess x 0 ∈ H, we iterate {x k } in either one of the following two projection algorithms: (i) Sequential (cyclic) projections: x k+1 = P C M · · · P C 1 x k ; (ii) Parallel projections: x k+1 = M j=1 β j P C j x k , with β j > 0 for all j and M j=1 β j = 1; Then {x k } converges weakly to a solution of CFP (1.2), given that this solution set is nonempty.
Another key notion in our discussion is that of a convex function and Moreau-Rockafellar subdifferential [6]. Let D be a convex subset of H, and let f : D → R be a convex function.
The set of all subgradients of f at x is called the subdifferential and is denoted by ∂f (x). Let be the set of optimal solutions and the optimal value of the composite minimization problem (1.1), respectively. We shall always assume from now and onwards that S * = ∅.
Two problems are pertinent: (a) The sequence {x k } would (weakly) converge to an optimal solution x * ∈ S * ; (b) The sequence {f (x k )} would converge to the optimal value f * . If the answer to (a) is affirmative, then the answer to (b) is also positive.
The assumptions of Theorem 1.1 play a key role in establishing the aforementioned properties. We state and discuss these assumptions here explicitly for the clarity of exposition.
First, we make a standard assumption on the divergence of the series of diminishing stepsizes used at the gradient cycle of our projection algorithm: we require that The first condition ensures that the steps we make are indeed descent steps, and that the gradient step does not derail our progress with the convergence of projection steps to the feasible set. The second condition ensures that there is no artificial restriction on how far can the sequence of iterates depart from the initial point. The second key assumption is a uniform Lipschitz bound on the components of the objective function. Explicitly, we use the following assumption on the subgradients of our functions, and we also let L := N j=1 L j . Observe that this condition is satisfied naturally when these (real-valued) functions are defined on the whole finite-dimensional space H and the sequence (x k ) is bounded. It is also well-known (see [2,Proposition 7.8]) that the condition of a function having bounded gradients (subdifferentials) on bounded sets is equivalent to the function being bounded on bounded sets in the finite-dimensional setting.

Asymptotic Feasibility of Parallel and Cyclic Projections
We are ready to prove two major technical results that concern the asymptotic feasibility of parallel and cyclic projections (Lemmas 3.1 and 3.6 respectively). Note that the relevant statement for the sequential projections was shown in [11].
3.1. Asymptotic Feasibility for Parallel Projections. Recall that the parallel projection algorithm (PPA) utilizes a convex combination of the projections on the sets C 1 ,. . . , C M on its projection step: Our goal is to prove the following result. We begin with several technical claims that we use in the proof that is deferred to the end of this subsection.
3), and λ k ↓ 0, and that the sequence {x k } generated by the method of parallel projections is bounded. Then {x k } is asymptotically feasible, that is, lim k→∞ d C (x k ) = 0.
The following technical result is used in the subsequent proofs.
(iii) This is a straightforward consequence of (ii).
(iv) This is easily derived from (iii), (i) and the fact that a distance function of a convex set is Lipschitz continuous with Lipschitz constant one: 3) is satisfied, and {x k } is bounded. Then for any ε > 0, there exists δ > 0 such that Since {x k } is a bounded sequence in a finite dimensional space, we may assume that x k l →x. We then get This implies thatx ∈ C j for every j; hence,x ∈ C. This contradicts the fact that We are now ready to prove Lemma 3.1.
Proof of Lemma 3.1. By Lemma 3.3 we have lim inf k→∞ d C (x k ) = 0, hence, we can take k 0 such that d C (x k 0 ) < ε and λ k L < 1 2 ε for all k ≥ k 0 . Let k ≥ k 0 . Consider two cases. Case 1: d C (x k ) < ε. In this case, we have by Lemma 3.2(iii) We now prove, for all i ≥ 0, Hence, (3.6) also holds for i + 1.
Now it turns out from (3.6) that lim sup k→∞ d C (x k ) ≤ 3 2 ε, and Lemma 3.1 is proven. Note that Lemmas 3.3 and 3.1 can be generalized for the infinite-dimensional setting. We discuss this in more detail in Section 5.1.
Remark 3.4. We include a version of Lemma 3.2 for the sequential projection algorithm (SPA) that generates a sequence {x k } via the following iteration process: Lemma 3.5. Let {x k } be generated by (SPA) and assume that the Lipschitz condition (2.3) is satisfied. Then ) and we use the convention The proof of Lemma 3.5 follows the same line of the proof of Lemma 3.2. For instance, part (ii) can be proved by consecutively applying property (iii) of projections in Proposition 2.1 (it is also proved in [11]). Part (iv) can trivially be derived from (iii) by using the Lipschitz-1 property of distance functions.
By Lemma 3.5, we find that the conclusion of Lemma 3.3 holds true also for the SPA.

Asymptotic Feasibility for Cyclic Projections.
Recall that the cyclic projection algorithm (CPA) alternates the full sequence of gradient steps with the individual projections on each one of the sets C 1 , . . . , C N , as follows. (CPA) Our goal is to prove the following asymptotic feasibility result that mirrors Lemma 3.1.
Lemma 3.6. Assume dim H < ∞, (2.3), and λ k ↓ 0, and that the sequence {x k } generated by the method of cyclic projections is bounded. Then {x k } is asymptotically feasible, that is, lim k→∞ d C (x k ) = 0.
To prove this lemma, we need several technical claims. First, for any x ∈ X and q ∈ {1, . . . , M} define the exact q-cyclic projection We next show that such cyclic projections bring the iterations closer to the feasible set in a uniform sense.
The function ψ q X is continuous and ψ q X (α) < α for all α > 0. Proof. We assume throughout that the compact convex set X and the index q ∈ {1, . . . , M} are fixed and use the notation ψ := ψ q X . We first show that ψ(α) < α for α > 0. For any closed convex set S we have by Proposition 2.1(iii) hence, for our setting where γ(x) > 0 does not depend on y. Therefore, taking the infimum over y ∈ C, we have for every and so (3.10) d(x, C) > d(P q (x), C) for every x / ∈ C.

Now let
Observe that explicitly The set X α is compact because it is the intersection of a compact set X with a closed set {d(x, C) ≤ α}, and X α is nonempty for every The function d(P q (x), C) is continuous in x, and since each of the sets X α is compact and nonempty, the supremum in (3.11) is attained, and we have Hence, for every α > 0 there exists x α such that d(x α , C) ≤ α and If ψ(α) = 0, then ψ(α) < α. If ψ(α) > 0, we have x / ∈ C and from (3.10) We next focus on showing that ψ is continuous. Since the function ψ(α) is nondecreasing, and to prove its continuity it is sufficient to show If ψ(ᾱ) = 0, since ψ is nondecreasing, we have 0 ≤ ψ(α) ≤ ψ(ᾱ) = 0, so ψ(α) = 0 for all α ∈ [0,ᾱ] and the first relation in (3.13) holds trivially. Consider the case ψ(ᾱ) > 0. From (3.12) we know that there existsx ∈ X such that d(x, C) ≤ᾱ and d(P q (x), C) = ψ(ᾱ).
Since by our assumption ψ(ᾱ) > 0, we have t 0 ∈ [0, 1). Now take any t 0 ≤ t 1 < t 2 ≤ 1. We have 1]. From this together with the continuity of the distance function we deduce that for every t ∈ [0, 1) there exists a sufficiently large α t <ᾱ such that At the same time, by the continuity of P q (x) for every ε > 0 there exists t ∈ [0, 1) such that This means that for every ε > 0 we can find t and α t such that and therefore we have the desired lim inf α↑ᾱ ψ(α) ≥ ψ(ᾱ).
From (3.12) there exists a sequence x k such that Without loss of generality this sequence {x k } converges to somex ∈ X. By continuity we have where P q is the exact cyclic projection operator defined by (3.7).
Proof. Using the nonexpansivity of the projection operator (Proposition 2.1 (ii)) we have Since λ k ↓ 0, we can always find a sufficiently large number K to ensure the last term is smaller than ε for all k ≥ K.
The next proposition brings us closer to the proof of Lemma 3.6. Without loss of generality we may assume that x k l →x and that (k l mod M) + 1 = q ∈ {1, . . . , M}, so that each x k l is obtained after projecting onto C q . Since the sequence {x k } is bounded, we can define the function ψ = ψ q X (as in Proposition 3.7) on any compact set X that contains {x k } and some point from C which we assumed to be nonempty. By the continuity of ψ proved in Proposition 3.7 we have where the last inequality follows from D > 0 and Proposition 3.7.
Therefore, for sufficiently large k l we have On the other hand, using Proposition 3.8 we deduce that for sufficiently large k l we also have Taking the lower limit, we have lim inf Proof of Lemma 3.6. It is sufficient to show that for any ε > 0 there exists a sufficiently large K such that for k ≥ K we have d(x k , C) < ε. Fix ε > 0. By Proposition 3.7 for every q the function α − ψ q X (α) is continuous and positive on the compact set [ε/2, ε]. Therefore, it attains its minimum, which is also positive, min By Proposition 3.8 there exists K such that By Proposition 3.9 there exists some k 0 ≥ K such that Let q = (k mod M) + 1. Our goal is to show that x k 0 +iM , i ∈ N never leaves the εneighbourhood of C. Assume the contrary. Then for some k ≥ k 0 , (k mod M) + 1 = q we have d(x k , C) ≤ ε, but d(x k+M , C) > ε. Observe that this yields a contradiction.

From asymptotic feasibility to convergence
In the previous section we have shown that all three algorithms (cyclic, sequential and parallel projections) satisfy the asymptotic feasibility property, i.e. under the standard assumptions the sequence of iterates (x k ) satisfies In this final technical section we prove that this property yields the convergence of the iterative sequence to the optimal solution, which we make precise in Lemma 4.2. We then briefly explain the proof of Theorem 1.1 that is based on this result and on the aforementioned property of asymptotic feasibility.
Our next statement is a useful estimate that will be utilized heavily in the subsequent analysis. Our proof is a minor modification of [20, Lemma 2.1].
Lemma 4.1. Let {x k } ∞ k=0 be generated by any of the three projection algorithms, and assume that the condition (2.3) is satisfied. Set L = N i=1 L i . Then, for each x ∈ C, we have Proof. Let V be one of the three operators considered for our projection step, Observe that V is nonexpansive, and hence for x ∈ C ⊆ Fix V , On the other hand, for each 1 ≤ j ≤ N and x ∈ C, we have Using the Lipschitz bound (2.3) and the subdifferential inequality we obtain Adding up the above inequalities over j = 1, 2, · · · , N yields In view of (4.2), to show (4.1) it remains to bound the last two terms in (4.3). From the Lipschitz bound (2.3) we have Also observe that where v k,l ∈ ∂f l (x k,l−1 ). We hence obtain the desired bound   Then the following conclusions are satisfied: Proof. From Lemma 4.1 we have With no loss of generality, we may assume x k i →x; thenx ∈ C by (4.5). Use (4.6) with k and x replaced with k i andx, respectively, to get (noting that λ k i → 0 and (f (x k i )) is bounded) It turns out that x k i +1 →x. Returning to (4.7), we immediately find that x k+1 −x k → 0.
(ii) We have a subsequence Due to boundedness, we may also assume x k i → x ′ . By part (i), x ′ ∈ C and we therefore On the other hand, if lim inf k→∞ f (x k ) > f * , then there exist some ε 0 > 0 and k ′ ≥ 0 such that f (x k ) > f * + ε 0 and λ k L 2 < ε 0 for all k ≥ k ′ . It then turns out from (4.1) that, for x ∈ S * and k ≥ k ′ , This implies that the series ∞ k=k ′ λ k < ∞, which contradicts (2.2). So we must have We finish this section with the proof of Theorem 1.1. The proof that we provide below contains a point that is essentially different from that of [11], which makes us successfully remove the assumption in [11,Theorem 1] and in [20,Proposition 2.3] that the optimal solution set S * be bounded. Note that this condition is equivalent to ( [24]) the condition that the objective function f satisfies the coercivity property: f (x) → ∞ as x → ∞.
Proof of Theorem 1.1. It is sufficient to prove that the following two claims are true under the conditions of Theorem 1.1 (that H is finite-dimensional, the sequence {x k } is bounded, and the two conditions (2.2) and (2.3) are satisfied): (i) lim k→∞ d S * (x k ) = 0; in other words, every cluster point of {x k } is an optimal solution of (1.1); Observe that (ii) is an immediate consequence of (i) due to the continuity of the objective function f . We hence focus on proving (i).
Observe that for each ε > 0 and each k ∈ N exactly one of the two possibilities holds: First consider case (1). By (4.1), we get . Since λ k → 0, we may assume λ k L 2 < ε. We then get for sufficiently large k We now turn to consider case (2) which is valid infinitely often as lim inf k→∞ f (x k ) = f * . Define It is easy to see that ϕ k (ε) is decreasing in k and ε > 0, respectively. Let It is not hard to find that Indeed, if η := lim ε↓0 ϕ(ε) > 0, we can find ε 0 > 0 such that ϕ(ε) > 1 2 η for all 0 < ε < ε 0 . Upon taking a positive sequence ε 0 > ε i → 0, we get a subsequence for all i. Assuming that {x k i } converges to somex ∈ C, we obtain the following contradiction: Hence, (4.12) is proven.

Generalizations
In this section we discuss the extent to which our results can be directly generalized to the infinite-dimensional Hilbert space setting, and provide several extensions of the proposed algorithms.

5.1.
Infinite-dimensional real Hilbert space. We first consider the infinite-dimensional setting. We clarify the generalizations of our main technical results in the next remark and then present the generalization explicitly in Theorem 5.2.
Remark 5.1. Note that Lemmas 3.1 and 3.3 remain valid in the infinite-dimensional case. In the proof of Lemma 3.3, we may assume that subsequence x k l →x weakly. Using the weak lower-semicontinuity of the convex function M j=1 β j d 2 C j , we still get (3.4). In Lemma 3.1, if dim H = ∞, it turns out that x * ∈ C for all x * ∈ ω w (x k ), the set of all weak cluster points of {x k }. Indeed, if x k i → x * weakly, then the weak lowersemicontinuity of the distance function d C implies that Hence, x * ∈ C.
Lemma 4.2(ii) also remains valid for the case of parallel projections. In fact, in this case, we have x k i → x ′ weakly, and from the proof of Lemma 4.2(ii), we get It is unclear if the asymptotic regularity of {x k } (i.e., Lemma 4.2(i)) remains valid if dim H = ∞.
Based on Remark 5.1 we can state the following (incomplete) result in a general Hilbert space which may be infinite-dimensional.
Theorem 5.2. Let {x k } be the sequence generated by the parallel projection algorithm in a general Hilbert space H. Assume (2.2) and (2.3). Then there exists a subsequence {x k j } of {x k } such that {x k j } converges weakly to an optimal solution x * ∈ S * , and {f (x k j )} converges to the optimal value f * . If, in addition, the limit of the full sequence {f (x k )} exists as k → ∞, then the full sequence {x k } converges weakly to the optimal solution x * , and {f (x k )} converges to the optimal value f * .
Proof. By Remark 5.1, we have a subsequence {x k j } of {x k } such that We may also assume that x k j → x * weakly as j → ∞. Notice that x * ∈ C again by Remark 5.1. So the weak lower-semicontinuity, we get It turns out that f (x * ) = f * .

5.2.
Relaxing the Assumptions. We have mentioned earlier that it is possible to replace the Lipschitz condition 2.3 by the assumption that the components of the objective functions are bounded on bounded sets.
All information that is available is given by the inequality where {µ k } satisfies the condition: (5.5) µ k ∈ R (∀k ≥ 0) and lim k→∞ µ k = 0 and {β k } satisfies the conditions: However, the conditions (5.5) and (5.6) are insufficient to imply from (5.4) that lim k→∞ α k exists, as shown by the example below.
Remark 5.5. A sufficient condition for {α k } to be convergent is that µ k ≥ 0 for all sufficiently large k. In this case, the inequality (5.4) implies for all large enough k. This together with the assumption of {β k } ∈ ℓ 2 is sufficient to imply that lim k→∞ α k exists.
Returning to the sequence {x k }, we can't get any convergence information from the inequality (5.3) since we do not know for what k, x k is feasible (i.e., x k ∈ C); in other words, we do not know for what k, f (x k ) − f * ≥ 0.
The following is another partial answer to the open question set forth in Remark 5.3.
Proposition 5.6. Under the conditions of Theorem 1.1, if {x k } has at most finitely many cluster points, then {x k } converges to an optimal solution of (1.1). In particular, if f is strictly convex, then {x k } converges to the unique optimal solution of (1.1).
Proof. Assume that {x k } has m cluster points, where m ≥ 1 is an integer. We shall prove m = 1 by contradiction. Suppose m > 1 and let ξ 1 , · · · , ξ m be the m distinct cluster points of {x k }. Let ε satisfy the condition: Define N i := {k ∈ N : x k − ξ i < ε}, i = 1, 2, · · · , m. It is easy to see that {N i } are mutually disjoint: N i ∩ N j = ∅ for all i = j, and N \ ∪ m i=1 N i is at most a finite set. Therefore, we may assume that We then take an integer k 0 big enough so that Next we take a smallest integer k ′ > k 0 such that , we arrive at the contradiction: Consequently, we must have m = 1; equivalently, the full sequence {x k } converges.
Remark 5.7. The conclusions of Proposition 5.6 hold true in a more general case where the sequence {x k } has a set of cluster points which is strongly isolated in the sense that Here ω(x k ) is the set of cluster points of {x k }. Indeed, let 0 < ε < 1 2 δ and let k 0 satisfy (5.8). Due to the compactness of {x k } ∞ k=1 , we can find an integer m ≥ 1 with the property We may assume #ω(x k ) > m (the case where #ω(x k ) ≤ m being proven in Proposition 5.6). Consequently, there exists a ball B(x i , ε) (for some 1 ≤ i ≤ m) which contains at least two points of ω(x k ), ξ 1 and ξ 2 (say). It turns out from the definition of δ that This is a contradiction as 2ε < δ.
Proof. In this case, every x k+1 = P C x k,N is feasible (i.e., x k+1 ∈ C). Hence f (x k ) − f * ≥ 0 and the inequality (5.3) implies that Therefore, the convergence of the series ∞ k=0 λ 2 k < ∞ implies that lim k→∞ x k − x * exists for each x * ∈ S * , which in turns implies that {x k } converges since we have proved that every cluster point of {x k } is in S * .
Consider the case of the parallel projections algorithm where the stepsizes are not diminishing. We have the result below. Proposition 5.9. Let {x k } be generated by the parallel projection algorithm with nondiminishing stepsize sequence {λ k }. Then where λ = lim sup k→∞ λ k .
Proof. Suppose (5.10) were not true; then For any ε > 0, findx ∈ C and k ≥ 1 such that • λ k < λ + 2ε L 2 for all k ≥ k 0 . These combining with (5.11) imply that (5.12) f Now applying (4.1) and using (5.12) we further obtain, for all k ≥ k 0 , It turns out that Hence, {λ k } must be in ℓ 1 , a contradiction to the assumption that {λ k } is nondiminishing.
Remark 5.10 (Unrestricted and random projections). Note that the cyclic projection algorithm can be generalized to an unrestricted version, where the order of the projections is not sequential, but is determined by a mapping φ : N → {1, . . . , M}, defined so that each of the sets C 1 , C 2 , . . . , C M feature in this algorithm infinitely many times. If there is a uniform bound on the gap between the number of steps separating the next nearest appearance of the same set in the sequence, then our analysis of the method of cyclic projections can be generalized to include this version of the method. It remains to be seen if the convergence still holds without this assumption, and whether some probabilistic bounds can be obtained for a randomized version of the method.

Relaxed Projection Algorithms
Here we briefly outline ideas of relaxed projection approaches that can be used whenever the projections may be expensive or unavailable, but an approximation is reasonably easy to compute. This can be considered in a general framework of cutters (e.g. see [7]). We consider the most popular implementation of cutters via the subgradients of constraint functions.
Assume each C i is a level set of a convex function, that is, where c i : H → R ∪{∞} is a convex function which is subdifferentiable on an open convex set that contains C i . Recall that the subdifferential of c i at x ∈ dom c i is defined by In this setting we are able to replace projections onto the C ′ i s with projections onto half-spaces, which then have closed formulae.
We consider the relaxed parallel projection algorithm (RPPA) and the relaxed sequential projection algorithm (RSPA) which generate a sequence {x k } by the following iteration processes: x k,j = x k,j−1 − λ k v k,j , v k,j ∈ ∂f j (x k,j−1 ), j = 1, 2, · · · , N, and, respectively, x k,j = x k,j−1 − λ k v k,j , v k,j ∈ ∂f j (x k,j−1 ), j = 1, 2, · · · , N, x k+1 = P C k M · · · P C k 1 x k,N , where β i > 0 and sum to one: M i=1 β i = 1, and C k i is a half-space defined by (6.2) C k i := {x ∈ H : c i (x k ) + ξ k i , x − x k ≤ 0}, ξ k i ∈ ∂c i (x k ) for i = 1, · · · , M. Note that C k i ⊃ C i for each i and k. Indeed, if x ∈ C i (i.e., c i (x) ≤ 0), then by the subdifferential inequality, we get i (for RPPA) or T k := P C k M · · · P C k 1 (for RSPA).
Then T k is nonexpansive (as a convex combination (or composite) of projections). Moreover, we can rewrite x k+1 = T k x k,N . Note that First we consider the sequence {x k } generated by the (RPPA). An immediate analysis shows that Lemma 4.1 remains valid for the (RPPA), and Lemma 3.2 valid for the (RPPA) as well with C j replaced with C k j for each j. We now verify Lemma 3.3 for the (RPPA). As a matter of fact, we can follow the same way of the proof of Lemma 3.2, and (3.3) to get Since {x k } is a bounded sequence in a finite dimensional space, we may assume that x k l →x. We then get (for distance functions are 1-Lipschitz continuous) (6.4) d C k l j (x) → 0, j = 1, 2, · · · , M.
Since z j,l ∈ C k l j , we have (6.6) c j (x k l ) + ξ k l j , z j,l − x k l ≤ 0. Noting the boundedness of (ξ k j ) and using the facts z j,l →x and x k l →x, we immediately obtain that the second term in the last relation tends to zero as l → ∞. Consequently, we get c j (x) ≤ 0 for each j; that is, x ∈ C.
Next consider the sequence {x k } generated by the (RSPA). In this case we still have Lemma 4.1 valid for the (RSPA). Moreover, Lemma 3.5 remains valid for the (RPPA) with C j replaced with C k j for each j. To see Lemma 3.3 is also valid for the (RSPA), we find that the relation (6.3) for the (RPPA) is replaced by the relation below for the (RSPA): Assuming x k l →x as l → ∞, we get d C k l j (P C k l j−1 · · · P C k l 1x ) → 0 as l → ∞ for each j = 1, 2, · · · , M. It then turns out that we can find z j,k l ∈ C k l j such that z j,k l →x as l → ∞ for each j = 1, 2, · · · , M. Namely, (6.4)-(6.5) remain valid. Then again from (6.6), we derive thatx ∈ C.
Finally, the proof of Theorem 1.1 can easily be repeated to prove the convergence of the (RPPA) and (RSPA), which is stated below. (i) lim k→∞ d S * (x k ) = 0; in other words, every cluster point of {x k } is an optimal solution of (1.1); (ii) lim k→∞ f (x k ) = f * .