{'fraction_non_alphanumeric': 0.07570115018290874, 'fraction_numerical': 0.02896879016577135, 'mean_word_length': 3.594095382286147, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 22, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 10, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Dykstra splitting and an approximate proximal point algorithm for minimizing the sum of convex functions

We show that Dykstra's splitting for projecting onto the intersection of convex sets can be extended to minimize the sum of convex functions and a regularizing quadratic. We give conditions for which convergence to the primal minimizer holds so that more than one convex function can be minimized at a time, the convex functions are not necessarily sampled in a cyclic manner, and the SHQP strategy for problems involving the intersection of more than one convex set can be applied. When the sum does not involve the regularizing quadratic, we discuss an approximate proximal point method combined with Dykstra's splitting to minimize this sum.


Introduction
Throughout this paper, let X be a finite dimensional Hilbert space. Consider the problem of minimizing the sum of convex functions (1.1) where h i : X → R ∪ {∞} are closed proper convex functions. The aim of this paper is to combine Dykstra's splitting and an approximate proximal point algorithm in order to minimize (1.1).
1.1. Dykstra's algorithm. For closed convex sets C i , where i ∈ {1, . . . , r}, Dykstra's algorithm [Dyk83] solves the problem where δ Ci (·) is the indicator function of the set C i . Note that (1.2) is also equivalent to the problem of projecting the point x 0 onto ∩ r i=1 C i . The projection onto the intersection ∩ r i=1 C i may be difficult, but each step of Dykstra's algorithm requires only the projection onto one set C i at a time. Its convergence to a primal minimizer without constraint qualifications was established in [BD85]. Separately, Dykstra's algorithm was rediscovered in [Han88], who noticed that it is block coordinate minimization on the dual problem, and proved the convergence to a primal minimizer, but under a constraint qualification. This dual perspective was also noticed by [GM89], who built on [BD85] and used duality to prove the convergence to a primal minimizer without constraint qualifications.
Dykstra's algorithm can be made into a parallel algorithm by using the product space approach largely attributed to [Pie84]. But this parallelization is slower than the original Dykstra's algorithm because the dual variables are not updated in a Gauss Seidel manner. (In other words, the dual variables are not updated with the most recent values of the other dual variables.) It was also noticed in [HD97] (among other things) that the projections onto the sets C i need not be performed in a cyclic manner to achieve convergence. In [Pan16], we studied a SHQP (supporting halfspace and quadratic programming) heuristic for improving the convergence of Dykstra's algorithm by noticing that the projection operations onto the sets C i generate halfspaces containing C i , and the intersection of these halfspaces can be a better approximate of ∩ r i=1 C i than each C i alone. We now refer to the natural extension of Dykstra's algorithm for minimizing min x 1 2 x where h i (·) are generalized to be closed convex functions, as Dykstra's splitting. Instead of projections, one now uses proximal mappings. (See (2.10) for an example.) Dykstra's splitting was studied in [Han89] and [Tse93] for the case of r ≥ 2, and they proved the convergence (to the primal minimizer) under constraint qualifications. It was also proved in [BC08] that Dykstra's splitting converges for the case of r = 2 without constraint qualifications. Dykstra's algorithm is related to the method of alternating projections for finding a point in the intersection more than one closed set. For more information on the various topics in Dykstra's algorithm mentioned so far, we refer to [Deu01a,Deu01b,BC11,ER11].
1.2. Block coordinate minimization. For the problem of minimizing f (x) + g(x), where f (·) is smooth and g(·) is block separable, one strategy is to minimize one block of the variables at a time, keeping the others fixed. This strategy is called block coordinate minimization, or alternating minimization. Nonasymptotic convergence rates of O(1/k) to the optimal value were obtained for when the smooth function is not known to be strongly convex in [BT13,Bec15]. We refer to these papers for more on the history of block coordinate minimization.
The smooth portion of the dual problem in Dykstra's algorithm is a specific quadratic function, so block coordinate minimization for this problem coincides with a block coordinate proximal gradient approach in [TY09b,TY09a]. Convergence properties of minimizing over more than one block at a time were discussed. There is too much recent research on block coordinate minimization and block coordinate proximal gradient, so we refer the reader to the two recent references [Wri15,HWRL17] and their references within.
1.3. Proximal point algorithm. The proximal point algorithm attributed to [Mar70,Roc76] is a method for finding minimizers of min x f (x) by creating a sequence {x j } j such that It was noticed in [Han89] that one can use the proximal point algorithm to solve (1.1) by approximately solving a sequence of problems of the form (1.3) using Dykstra's algorithm. The rules there for moving to a new proximal center x j involves finding a primal feasible point that satisfies the optimality conditions approximately. But such a feasible point might not be found in a finite number of iterations when some of the functions h i (·) are indicator functions, so a separate rule for moving the proximal center is needed.
1.4. Other methods for minimizing the sum of functions. When the constraint sets are either too big and have to be split up as the intersection of more than 1 set, or when these constraint sets are only revealed as the algorithm is run, it is beneficial to write these problems in the form (1.1) where two or more of the h i (·) are indicator functions. In such a case, as remarked in [Ned11], the accelerated methods of [Nes04] and further developed by [BT09,Tse08] do not immediately apply (to the primal problem). We now recall other methods and observations on minimizing (1.1) when more than one of the functions h i (·) are indicator functions and the algorithm can operate on a few of the functions h i (·) at a time. As we have seen earlier, Dykstra's algorithm is one such example.
In the case where all the functions h i (·) in (1.1) are indicator functions, then this problem coincides with the problem of finding a point in the intersection of convex sets, which is a problem of much interest on its own. (See for example [ER11,BB96,Deu01b].) We refer to this as the convex feasibility problem. The convex feasibility problem can be solved by the method of alternating projections and the Douglas-Rachford method. A discussion of the effectiveness of methods for the convex feasibility problem is [CCC + 12].
Beyond the convex feasibility problem, various extensions of the subgradient method in [NP09,RNV09,Ned11] can solve problems of the form (1.1). Another recent development is in superiorization (See for example [CDH10]), where an algorithm for the convex feasibility problem is perturbed to try to reduce the value of the objective function. The result is an algorithm that seeks feasibility at a rate comparable to algorithms for the feasibility problem, while achieving a superior objective value to what an algorithm for the feasibility problem alone would achieve. A comparison of projected subgradient methods and superiorization is given in [CDH + 14].
A typical assumption on the constraint sets is that they have a Lipschitzian error bound, which is also equivalent to the stability of the intersection under perturbations. See for example [BBL99,BD05,NY04,Kru06].
Lastly, another method for minimizing (1.1) is the ADMM [BPC + 10]. The ADMM is an effective method, but we feel that Dykstra's splitting still has its own value. For example, as we shall see later, the different agents can minimize in any order, and convergence doesn't even require the existence of a dual minimizer. In problems where the different agents are assumed not to be able to freely communicate between each other or if communications between two agents are one dimensional, methods derived from subgradient algorithms can still be a method of choice [Ned15], even though many algorithms are preferred over the subgradient algorithm in large scale problems with less restrictive communcation requirements [Nes04].
We refer to the survey [CP11] for other proximal techniques for minimizing (1.1).  .3) is any number greater than or equal to 2, and (C) h i (·) can be any closed convex function instead of the indicator function.
As mentioned earlier, [BD85] and [GM89] have features (A) and (B), [Han89] has (B) and (C), and [BC08] has (A) and (C). We are not aware of Dykstra's splitting being proved to have features (A), (B) and (C). In addition, our analysis incorporates these features that are now rather standard in block coordinate minimization algorithms.
(D) the convex functions h i (·) are not necessarily sampled in a cyclic manner like in [HD97], (E) more than one convex function h i (·) can be minimized at one time in the Dykstra's splitting, and (F) the SHQP strategy in [Pan16] is applied.
The proof is largely adapted from [GM89]. This paper also updates the discussion of the SHQP strategy in [Pan16] by pointing out that if the convex functions δ * Ci (·) are not necessarily sampled in a cyclic manner, then we just need one set of the formC n,w in Algorithm 2.1 instead of multiple sets of this type as was done in [Pan16].
Secondly, in Section 4, we show that one can minimize problems of the form (1.1) where the feasible region is a compact set by combining Dykstra's splitting on problems of the kind (1.3) and an approximate proximal point algorithm where the proximal center is moved once the KKT conditions are approximately satisfied. The compactness of the feasible region allows us to remove the constraint qualifications on the constraint sets for our results.
In Section 3, we show that if a dual minimizer exists and some processing is performed so that the dual multipliers related to the indicator functions are uniformly bounded throughout all iterations, an O(1/n) convergence of the dual problem (which leads to an O(1/ √ n) convergence to the primal minimizer) can be attained.
1.6. Notation. We use "∂" to refer to either the subdifferential of a convex function, or the boundary of a set, which should be clear from context. The conjugate δ * C (·) of the indicator function has the form δ * C (y) = sup x∈C y, x , and is also known as the support function.

Dykstra splitting for the sum of convex functions
Consider the primal problem where X is a finite dimensional Hilbert space, and (A1) f i : X → R are convex functions such that domf i (·) = X for all i ∈ {1, . . . , r 1 }. (A2) g i : X → R are lower semicontinuous convex functions for all i ∈ {r 1 + 1, . . . , r 2 }. (A3) C i are closed convex subsets of X for all i ∈ {r 2 + 1, . . . , r}.
In this section, we generalize the proof in [GM89] to show that Dykstra's splitting algorithm can be used to minimize problems of the form (2.1).
We note that the functions δ Ci (·) and f i (·) can be written as g i (·). But as we will see later, we will treat the functions of the three types differently in Algorithm 2.1. For convenience of future discussions, let h : X → R and h i : X → R be the convex functions defined by so that the objective function in (2.1) can be written simply as 1 2 x − x 0 2 + h(x).
2.1. Algorithm description and commentary. The (Fenchel) dual of problem (2.1) is where F : X r → R is defined by By weak duality, we have β ≤ α. (Actually β = α is true; We will see that later.) IfC is any closed convex set such thatC ⊂C, where the setC is defined bȳ then problem (2.1) has the same (primal) minimizer as The dual of (PC ) is As detailed in [Pan16], this observation leads us to construct a setC n,w that changes in each iteration of our extended Dykstra's algorithm in Algorithm 2.1 below.
Algorithm 2.1. (Extended Dykstra's algorithm) Consider the problem (2.1) along with the associated problems (2.2), (2.5) and (2.6). Set some number M ∈ R + ∪ {∞}, and letw be a positive integer. Our extended Dykstra's algorithm is as follows: 01 Define the set H 1,0 to be H 1,0 = X. 02 Let z 1,0 ∈ X r+1 be the starting dual vector for (2.6), and let z 1,0 For w = 1, 2, . . . ,w 06 Choose a subset S n,w ⊂ {1, . . . , r + 1}. 07 If r + 1 ∈ S n,w , then Dual decrease with SHQP steps 08 ChooseC n,w to be any set such thatC ⊂C n,w ⊂ H n,w−1 . 09 Let H n,w be H n,w−1 . 16 End If 17 End For Aggregating variables 18 Find z n+1,0 ∈ X r+1 and H n+1,0 ⊃C such that We list some observations of Algorithm 2.1. The choice of S n,w in line 6 of Algorithm 2.1 allows for more than one block of z to be minimized in (2.7). If w = r + 1, the sets S n,w are chosen to be {w}, and r 1 = r 2 = 0, then Algorithm 2.1 reduces to the extended Dykstra's algorithm that was discussed in [Pan16].
Remark 2.2. (Choice of H n,w ) An easy choice for H n,w in line 11 of Algorithm 2.1 is to choose a halfspace with outward normal z n,w r+1 that supports the setC n,w . Another example of H n,w is the intersection of the halfspace mentioned earlier with a small number of halfspaces containingC defined in (2.4) that will allow H n,w to approximateC well.
We have the following identities to simplify notation: (2.9b) Proof. By taking the optimality conditions in (2.7) with respect to z i for i ∈ S n,w , we deduce (a). The equivalences of (a), (b) and (c) is standard.
Dykstra's algorithm is traditionally written in terms of solving for the primal variable x. For completeness, we show the equivalence between (2.7) and the primal minimization problem.
Proposition 2.4. (On solving (2.7)) If a minimizer z n,w for (2.7) exists, then the x n,w in (2.9b) satisfies (2.10) Conversely, if x n,w solves (2.10) with the dual variables {z n,w i } i∈Sn,w satisfying Proof. For the first part, note that For the second part, note that the first part of (2.11) implies that x n,w ∈ ∂h * i (z n,w i ), while the second part of (2.11) implies that 0 lies in the subdifferential of the objective function in (2.7).
Remark 2.5. (Information needed to calculate (2.7)) We note that in (2.7), one only needs to have knowledge of the variables v n,w−1 and z n,w−1 i for i ∈ S n,w . Thus Dykstra's splitting may be suitable for problems where the communication costs is high compared to the costs of solving the proximal problems.
Remark 2.6. (On line 18 of Algorithm 2.1) If M = ∞ in Algorithm 2.1, then z n+1,0 and H n+1,0 can be set to be z n,w and H n,w respectively. We had to add this line to Algorithm 2.1 because the boundedness condition (2.8c) is necessary for our O(1/n) convergence result in Section 3. This detail can be skipped for the discussions in this section and Section 4.
We need the following fact before we discuss how to find z n+1,0 and H n+1,0 satisfying (2.8).
. Moreover, the inequality is strict if, for example, z 1 = 0, z 2 = 0 and H 1 H 2 . This fact can be generalized for more than two halfspaces.
In other words, p(n, i) is the index m such that i ∈ S n,m but i / ∈ S n,k for all k ∈ {m + 1, . . . ,w}. It follows from lines 9 and 13 of Algorithm 2.1 that (2.12) We now show one way to find z n+1,0 and H n+1,0 satisfying (2.8d).
For i ∈ {r 2 +1, . . . , r}, recall that by the construction of z n,p(n,i) i in (2.7) and (2.10), the condition (2.11) implies thatH n,i ⊃ C i , where the halfspaceH n,i is defined bỹ and x n,w is as defined in (2.10). We can check that Proof. The conclusion can be deduced from Fact 2.7.
One can check that the construction in Proposition 2.8 also leads to the conditions in (2.8). In particular, (2.8e) can be inferred from (2.13) via The other items in (2.8) are clear.
2.2. Convergence of Algorithm 2.1. We now prove the convergence of Algorithm 2.1. We first list assumptions that will ensure convergence to the primal minimizer.
Assumption 2.9. We make a few assumptions on Algorithm 2.1: We give a brief commentary on Assumption 2.9. Assumption 2.9(a) together with the strong convexity of the primal problem says that (2.1) is feasible and a unique primal minimizer exists. As we will see later, the structure of the functions f i (·) for i ∈ {1, . . . , r 1 } implies that z n,w i is uniformly bounded for all i ∈ {1, . . . , r 1 }. In Proposition 2.11, we shall introduce a condition on the choice of S n,w that will ensure that Assumption 2.9(c) is satisfied.
We follow the proof in [GM89] to show that lim n→∞ x n,w exists and is the minimizer of (P).
For any x ∈ X and z ∈ X r+1 , the analogue of [GM89,(8)  (iv) For the v * in (iii), x 0 − v * is the minimizer of the primal problem (P) and . The properties (i) to (iv) in turn imply that lim n→∞ x n,w exists, and x 0 − v * is the primal minimizer of (2.1).
Proof. We first show that (i) to (iv) implies the final assertion. For all n ∈ N we have, from weak duality, Hence lim n→∞ x n,w is the minimizer in (P). It remains to prove assertions (i) to (iv). Proof of (i): We note that if r + 1 ∈ S n,w , then The first inequality comes from the fact that sinceC n,w ⊂ H n,w−1 (from line 8 of Algorithm 2.1), then δ * C n,w (·) ≤ δ * H n,w−1 (·). The second inequality comes from the fact that {z n,w i } i∈Sn,w is a minimizer of the mapping with the 1 2 v n,w − v n,w−1 2 arising from the quadratic term. When r + 1 / ∈ S n,w , then we can make use of the fact that z n,w r+1 = z n,w−1 r+1 and C n,w = H n,w−1 = H n,w to see that the inequality (2.17) carries through as well.
Proof of (ii): Substituting x in (2.15) to be the primal minimizer x * and z to be z n,w , we have The conclusion is immediate. Proof of (iii): We first make use of the technique in [BC11, Lemma 29,1] (which is in turn largely attributed to [BD85]) to show that Seeking a contradiction, suppose instead that there is an ǫ > 0 andn > 0 such that if n >n, then Moreover, By (ii), there exists a further subsequence of {v n k ,w } ∞ k=1 which converges to some v * ∈ X. Combining (2.19) and (2.20) gives (iii).
Proof of (iv): From earlier results, we obtain Since lim k→∞ v n k ,w = v * , we have lim k→∞ converges to 0 by (iii). Next, recall from (2.10) that x 0 − v n k ,p(n k ,i) ∈ C i . Recall from the end of the proof of (iii) that Therefore (2.21) becomes an equation in the limit, which leads to lim k→∞ F H n k ,w (z n k ,w ) = We now show some reasonable conditions that guarantee Assumption 2.9(c).
Proposition 2.11. (Satisfying Assumption 2.9(c)) Assumption 2.9(c) is satisfied when all of the following conditions on S n,w hold: (1) There are only finitely many S n,w for which S n,w ∩{r 1 +1, . . . , r+1} contains more than one element. Proof. We only need to prove this result for when only condition (2) holds and S n ∩ {r 1 + 1, . . . , r + 1} always contains at most one element. We have (2.23) The sum of the left hand side of (2.23) can be written as Next, we estimate the second sum in (2.24). For each (m, w) ∈S n,2 , by condition (1), there is a unique i m,w ∈ S m,w ∩ {r 1 + 1, . . . , r + 1}. We have Together with the fact that v m,w is bounded from Theorem 2.10(ii) and the fact that Combining (2.26) and (2.28) into (2.24) gives the conclusion we need.

O(1/n) convergence when a dual minimizer exists
In this section, we show that for the problem (2.1), if Algorithm 2.1 is applied with some finite M and a minimizer for the dual problem exists, then the rate of convergence of the dual objective function is O(1/n), which leads to the O(1/ √ n) rate of convergence to the primal minimizer.
Instead of condition (A2) after (2.1), we assume a stronger condition on g(·): In other words, the functions g i (·) are such that if lim j→∞ x j lies in ∂domg i (·), then lim j→∞ g i (x j ) = ∞.
We have the following theorem.

Theorem 3.2. (O(1/n) convergence of dual function) Suppose conditions (1) and (2) in Proposition 2.11 and Assumption 2.9 are satisfied and Algorithm 2.1 is run with finite M . If a dual minimizer to (2.2) exists, then the convergence rate of the dual objective value is O(1/n). This in turn implies that the convergence rate of
Alg 2.1, line 11 In view of the above and the definitions of F H (·) in (2.6) and V n , we have (3.1) We then look at the subgradients generated in each iteration. Recall how z n,w were defined in (2.7). We have, for each i ∈ {1, . . . r + 1}, Let the vector s ∈ X r+1 be defined so that the ith component s i ∈ X is as in (3.2). Then Let z * ∈ X r+1 be a minimizer of −F H n,w (·) with z * r+1 = 0. (Such a minimizer can be constructed by appending z * r+1 = 0 to a minimizer of (2.2), which was assumed to exist.) Making use of the elementary fact that s ∈ ∂(−F H n,w )(z n,w ), we have Claim: There is a constant M 4 such that z n,w i ≤ M 4 for all n ≥ 0, w ∈ {1, . . . ,w} and i ∈ {1, . . . , r + 1}.
The limit lim n→∞ x n,w must lie in the interior of the domains of f i (·) and g i (·) for all i ∈ {1, . . . , r 2 } (by Assumption (A2 ′ )). It is well known that the subgradients of a convex function is bounded in the interior of its domain, so there is a constant M 1 such that z n,w i ≤ M 1 for all i ∈ {1, . . . , r 2 } and w ∈ {0, . . . ,w}.
Step 2: The claim is true for all n ≥ 0, i ∈ {1, . . . , r + 1} and w = 0. Since we assumed that Algorithm 2.1 was run with a finite M , by (2.8c), z n,0 i ≤ M for all i ∈ {r 2 + 1, . . . , r} and n ≥ 0. Next, we show that M 1 can be made larger if necessary so that z n,0 r+1 ≤ M 1 for all n ≥ 0. Seeking a contradiction, suppose that there is a subsequence {n k } such that lim k→∞ z n k ,0 r+1 = ∞. Then this would mean that lim k→∞ r+1 i=1 z n k ,0 i = ∞. Recalling (2.15) for the special case where x = x * (the primal minimizer), we have which is a contradiction.
Next, we recall from Theorem 2.10(i) that ∞ n=1 w w=1 v n,w −v n,w−1 2 is finite. This implies that there is a M 2 > 0 such that v n,w − v n,w−1 ≤ M 2 for all n ≥ 0 and w ∈ {1, . . . ,w}.
Next, for each n ≥ 0 and i ∈ {r 2 + 1, . . . , r}, we want to show that there is a constant M 3 such that z n,w i ≤ M 3 for all n ≥ 0 and w ∈ {1, . . . ,w}. Since the z n,w i were chosen by condition (1) in Proposition 2.11, then if n is large enough, if S n,w ∩ {r 2 + 1, . . . , r + 1} = ∅, then there is a i n,w ∈ S n,w such that S n,w \{i n,w } ⊂ {1, . . . , r 2 }. We have This would easily imply that z n,w i ≤ M 4 for some M 4 > 0 for all n ≥ 0, i ∈ {1, . . . , r + 1}, and w ∈ {1, . . . ,w} as needed, ending the proof of the claim. Now, (3.6) Then combining the above, we have by earlier claim Letting M 5 be (r + 1)M 4 + r+1 i=1 z * i and rearranging (3.7), we have Applying Lemma 3.1 gives the first statement of our conclusion. The second statement comes from substituting x = x * in (2.15) and noticing that Remark 3.3. (Nonexistence of dual minimizers) An example of a problem where dual minimizers do not exist is in [Han88,page 9]. Lemma 2 in [GM89] shows that a fast convergence rate to the primal minimizer implies the existence of dual minimizers.

Approximate proximal point algorithm
Consider the problem of minimizing (4.1) If one of the functions h i (·) can be split as h i (·) =h i (·) + ci 2 · −x 0 2 for some convexh i (·) and c i > 0, then (4.1) can be minimized using Dykstra's splitting algorithm of Section 2. In this section, we propose an approximate proximal point method for minimizing (4.1) without splitting h i (·). We first present Algorithm 4.1 and prove that all its cluster points are minimizers of the parent problem. Then, in Subsection 4.2, we show that the Dykstra splitting investigated in Section 2 can find an approximate primal minimizer required in Algorithm 4.1.

An approximate proximal point algorithm. Consider the problem of minimizing
and each h i : X → R is a closed convex function whose domain is an open set, and D is a compact convex set in X. This setting is less general than that of (2.1), since it does not allow for all lower semicontinuous convex functions, and we only allow for one compact set D instead of r − r 2 sets. Algorithm 4.1 shows an approximate proximal point algorithm, where one solves a regularized version of (4.2) and shifts the proximal center x k when an approximate KKT condition is satisfied.
end For.
If r 2 = 1, D = X and h 1 (·) were allowed to be any lower semicontinuous convex function, then Algorithm 4.1 would resemble the classical proximal point algorithm.
Define the operator T : X → X by This operator has some favorable properties in monotone operator theory. We prove our first result.

Lemma 4.2. (Approximate of T (·))
Consider the problem (4.2). Let T (·) be as defined in (4.4). Suppose D ⊂ X is compact and convex. For all ǫ > 0, there is a δ > 0 such that for all x, x + ∈ X and z, e ∈ X r+1 such that d(x, D) ≤ δ and whereD ⊃ D is a closed convex set, then Proof. Seeking a contradiction, suppose otherwise. Then there exists a ǫ > 0 such that for all positive integers k, there are x k , x + k ∈ X, z (k) , e (k) ∈ X r+1 and a closed convex set D (k) ⊃ D such that There are two cases we need to consider. Case 1:x + lies in the interior of domh i for all i ∈ {1, . . . , r 2 }. Making use of the fact that convex functions are locally Lipschitz in the interior of their domains, we obtain the boundedness of {z (k) }. We can assume (by taking subsequences if necessary) that lim k→∞ z (k) =z. Taking the limits of (4.5) as k → ∞ would give usz i ∈ ∂h i (x + ),z 0 ∈ N D (x + ) andx + −x + r2 i=0z i = 0, which would in turn imply thatx + = T (x). It is well known that T (·) is nonexpansive and hence continuous, so a contradiction. Case 2:x + lies on the boundary of domh i for some i ∈ {1, . . . , r 2 }. We cannot use the method in Case 1 as some components of {z (k) } might be unbounded. We now consider the perturbed functions h i,k (·) defined by (4.8) . Then the conditions (4.3) imply that where d k is marked in (4.5b). Supposeī is such thatx + lies on the boundary of domhī. Then we have that lim k→∞ hī(x + k ) = ∞. Since D is bounded, inf x∈D h i (x) is a finite number for all i, which implies that (4.10) Next, let x ′ k = prox h (x k ) and x ′ = prox h (x). By the continuity properties of T (·) = prox h (·) and lim k→∞ x k =x in (4.7), we must have lim k→∞ But on the other hand, since lim k→∞ d k = 0, we have (4.12) Formulas (4.11) and (4.12) are contradictory, sox + must lie in the interior of all domh i for all i, which reduces to case 1.
Thus we are done.
To simplify notation in the next two results, we define the set A to be We have another lemma.
Proof. Seeking a contradiction, suppose otherwise. In other words, there is aǭ > 0 such that for all k > 0, there is a w k such that d(w k , A) >ǭ but T (w k ) − w k ≤ 1 k . By taking subsequences if necessary, letw = lim k→∞ w k , which exists by the compactness of D. Taking limits as k ր ∞ gives usw = T (w), which will in turn imply that d(w, A) = 0, a contradiction. Proof. For any ǫ 1 > 0, we make use of Lemma 4.3 and obtain δ 1 > 0 such that (4.13) By Lemma 4.2, there exists some K large enough so that (4.14) Let ǫ > 0 be small enough so that (4.15) (4.16) Suppose k ≥ K. We split our analysis into two cases. Case 1: d(x k , A) > ǫ 1 . (4.14),(4.16) (4.14),(4.16) The analysis in these two cases implies d(x k+1 , A) ≤ ǫ 1 + ǫ for all k large enough.
Since ǫ 1 and ǫ can be made arbitrarily small, any cluster point 4.2. Satisfying (4.3) using Dykstra splitting. Consider the problem of mini- (4.18) and each h i : X → R is a closed convex function whose domain is an open set, and each C i is a closed convex set such that ∩ r i=r2+1 C i is compact. This formulation is slightly more general than that of (4.2). Theorem 4.5 below shows that Algorithm 2.1 can find approximate minimizers to (4.18) that will satisfy the conditions for moving to a new proximal center in Algorithm 4.1.
Theorem 4.5. Consider the problem (4.18). For any δ > 0, there is some n > 0 such that when Algorithm 2.1 is applied to solve we have a set D (n) , and points x (n) ∈ X andz ∈ X such that ∩ r i=r2+1 C i ⊂ D (n) , (4.20d) z ∈ N D (n) (x (n) ), (4.20e) x (n) − x n,w ≤ δ. Theorem 2.10 says that for any δ > 0, we can find n > 0 such that the first 3 conditions in (4.20) hold ifz were chosen to be z n,w 0 . We separate into two cases, and discuss how the set D (n) (which will actually be either the whole space X or a halfspace) and the point x (n) are constructed.
Case 1: lim inf n→∞ z n,w 0 = 0. By taking subsequences {n k } k , we can assume that lim k→∞ z n k ,w 0 = 0. Then the set D (n) can be chosen to be X, and x (n) can be chosen to be x * , the minimizer of (4.19). The vectorz can be chosen to be zero, and the inequalities in (4.20) can be easily seen to be satisfied.
Let D (n) be the halfspace with outward normal z n,w We now show how to satisfy (4.20e) and (4.20f) withz = z n,w 0 . Let x * be the optimal primal solution of (4.19). We now want to show that we can choose a further subsequence if necessary so that lim k→∞ d(∂D (n k ) , x * ) = 0. From the definition of the support function and the fact that x * ∈ Theorem 2.10(i)(iv) shows that the formula in the first line of (4.24) has a limit of zero, so by the squeeze theorem, the last term in (4.24) also has limit zero as n → ∞. This means that lim k→∞ d(∂D (n k ) , x * ) = 0. Thus x (n) can be chosen as the projection of x * onto ∂D (n) . We then have lim k→∞ x (n) − x * = 0, and so the inequalities in (4.20) can be easily seen to be satisfied.
Remark 4.6. (Achieving (4.3b)) A final detail is to find an implementable way for checking that d(x (n) , ∩ r i=r2+1 C i ) is indeed small. Note that x n,p(n,i) ∈ C i for all i ∈ {r 2 + 1, . . . , r}, so we have the estimate d(x n,w , C i ) ≤ x n,w − x n,p(n,i) . One can easily make use of the compactness of ∩ r i=r2+1 C i to prove that for all δ 1 > 0, there is a δ 2 > 0 such that Putting this fact together with Theorem 4.5 allows us to find a point satisfying (4.3) in Algorithm 4.1.
Remark 4.7. (Treating multiple sets in Theorem 4.4) We remark that if we had analyzed Theorem 4.4 for the case where there are more than one indicator functions, then analyzing (4.8) would mean having to introduce constraint qualifications (for example, a Lipschitzian error bound assumption) needed to deal with issues related to the stability of sets under perturbations.