Convergence rate analysis of a Dykstra-type projection algorithm

Given closed convex sets Ci, i=1,ldots,ℓ, and some nonzero linear maps Ai, i = 1,ldots,ℓ, of suitable dimensions, the multi-set split feasibility problem aims at finding a point in bigcapi=1ℓ Ai-1Ci based on computing projections onto Ci and multiplications by Ai and AiT. In this paper, we consider the associated best approximation problem, i.e., the problem of computing projections onto bigcapi=1ℓ Ai-1Ci; we refer to this problem as the best approximation problem in multi-set split feasibility settings (BA-MSF). We adapt the Dykstra's projection algorithm, which is classical for solving the BA-MSF in the special case when all Ai = I, to solve the general BA-MSF. Our Dykstra-type projection algorithm is derived by applying (proximal) coordinate gradient descent to the Lagrange dual problem, and it only requires computing projections onto Ci and multiplications by Ai and AiT in each iteration. Under a standard relative interior condition and a genericity assumption on the point we need to project, we show that the dual objective satisfies the Kurdyka-Lojasiewicz property with an explicitly computable exponent on a neighborhood of the (typically unbounded) dual solution set when each Ci is C1,α-cone reducible for some α∈ (0,1]: this class of sets covers the class of C2-cone reducible sets, which include all polyhedrons, second-order cone, and the cone of positive semidefinite matrices as special cases. Using this, explicit convergence rate (linear or sublinear) of the sequence generated by the Dykstra-type projection algorithm is derived. Concrete examples are constructed to illustrate the necessity of some of our assumptions.