Convergence Rate Analysis of a Dykstra-Type Projection Algorithm

Xiaozhou Wang, Ting Kei Pong

Research output: Journal article publication β€Ί Journal article β€Ί Academic research β€Ί peer-review


Given closed convex sets 𝐢𝑖, 𝑖=1,…,β„“, and some nonzero linear maps 𝐴𝑖, 𝑖=1,…,β„“, of suitable dimensions, the multiset split feasibility problem aims at finding a point in ⋂ℓ𝑖=1π΄βˆ’1𝑖⁒𝐢𝑖 based on computing projections onto 𝐢𝑖 and multiplications by 𝐴𝑖 and 𝐴𝑇𝑖. In this paper, we consider the associated best approximation problem, i.e., the problem of computing projections onto β‹‚β„“
𝑖=1π΄βˆ’1𝑖⁒𝐢𝑖; we refer to this problem as the best approximation problem in multiset 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 𝐴𝑖=𝐼, 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 𝐢𝑖 and multiplications by 𝐴𝑖 and 𝐴𝑇𝑖 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-Łojasiewicz property with an explicitly computable exponent on a neighborhood of the (typically unbounded) dual solution set when each 𝐢𝑖 is 𝐢1,𝛼-cone reducible for some π›Όβˆˆ(0,1]
: this class of sets covers the class of 𝐢2-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.
Original languageEnglish
Pages (from-to)563-589
Number of pages27
JournalSIAM Journal on Optimization
Issue number1
Publication statusPublished - 2024


Dive into the research topics of 'Convergence Rate Analysis of a Dykstra-Type Projection Algorithm'. Together they form a unique fingerprint.

Cite this