## Abstract

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.

π=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 language | English |
---|---|

Pages (from-to) | 563-589 |

Number of pages | 27 |

Journal | SIAM Journal on Optimization |

Volume | 34 |

Issue number | 1 |

Publication status | Published - 2024 |