Please use this identifier to cite or link to this item:
http://hdl.handle.net/10397/106824
Title: | Convergence rate analysis of a Dykstra-type projection algorithm | Authors: | Wang, X Pong, TK |
Issue Date: | 2024 | Source: | SIAM journal on optimization, 2024, v. 34, no. 1, p. 563-589 | Abstract: | Given closed convex sets Ci, i = 1, . . . , \ell , and some nonzero linear maps Ai, i = 1, . . . , \ell ,of suitable dimensions, the multiset split feasibility problem aims at finding a point in \bigcap \ell i=1 A 1i Cibased on computing projections onto Ci and multiplications by Ai and ATi . In this paper, weconsider the associated best approximation problem, i.e., the problem of computing projections onto\bigcap \ell i=1 A 1i Ci; we refer to this problem as the best approximation problem in multiset split feasibilitysettings (BA-MSF). We adapt the Dykstra's projection algorithm, which is classical for solving theBA-MSF in the special case when all Ai = I, to solve the general BA-MSF. Our Dykstra-typeprojection algorithm is derived by applying (proximal) coordinate gradient descent to the Lagrangedual problem, and it only requires computing projections onto Ci and multiplications by Ai andATi in each iteration. Under a standard relative interior condition and a genericity assumption onthe point we need to project, we show that the dual objective satisfies the Kurdyka-\Lojasiewiczproperty with an explicitly computable exponent on a neighborhood of the (typically unbounded)dual solution set when each Ci is C1,\alpha -cone reducible for some \alpha \in (0, 1]: this class of sets coversthe class of C2-cone reducible sets, which include all polyhedrons, second-order cone, and the coneof positive semidefinite matrices as special cases. Using this, explicit convergence rate (linear orsublinear) of the sequence generated by the Dykstra-type projection algorithm is derived. Concreteexamples are constructed to illustrate the necessity of some of our assumptions. | Keywords: | Dykstra's projection algorithm Kurdyka-Lojasiewicz property Linear convergence C1,α-cone reducibility |
Publisher: | Society for Industrial and Applied Mathematics Publications | Journal: | SIAM journal on optimization | ISSN: | 1052-6234 | EISSN: | 1095-7189 | DOI: | 10.1137/23M1545781 | Rights: | Copyright © by SIAM. Unauthorized reproduction of this article is prohibited. The following publication Wang, X., & Pong, T. K. (2024). Convergence Rate Analysis of a Dykstra-Type Projection Algorithm. SIAM Journal on Optimization, 34(1), 563-589 is available at https://doi.org/10.1137/23M1545781. |
Appears in Collections: | Journal/Magazine Article |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
23m1545781.pdf | 525.52 kB | Adobe PDF | View/Open |
Page views
7
Citations as of Jun 30, 2024
Downloads
2
Citations as of Jun 30, 2024
![](/image/google_scholar.jpg)
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.