Convergence Rate Analysis of a Dykstra-Type Projection Algorithm

DOI10.1137/23M1545781arXiv2301.03026OpenAlexW4391574861WikidataQ128542404 ScholiaQ128542404MaRDI QIDQ6202756FDOQ6202756

Authors: Xiaozhou Wang, Ting Kei Pong 

Publication date: 27 February 2024

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

Abstract: Given closed convex sets $C_i$, $i=1,ldots,ell$, and some nonzero linear maps $A_i$, $i=1,ldots,ell$, of suitable dimensions, the multi-set split feasibility problem aims at finding a point in $$ based on computing projections onto $C_i$ and multiplications by $A_i$ and $A_i^T$. In this paper, we consider the associated best approximation problem, i.e., the problem of computing projections onto $$; 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 $A_i=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 $C_i$ and multiplications by $A_i$ and $A_i^T$ 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 $C_i$ is $C^{1,alpha}$-cone reducible for some $alphain(0,1]$: this class of sets covers the class of $C^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.

Full work available at URL: https://arxiv.org/abs/2301.03026

Recommendations

• A Convergence Analysis of Dykstra's Algorithm for Polyhedral Sets
• On Dykstra's algorithm: finite convergence, stalling, and the method of alternating projections
• An acceleration scheme for Dykstra's algorithm
• The rate of convergence of dykstra's cyclic projections algorithm: The polyhedral case
• The supporting halfspace-quadratic programming strategy for the dual of the best approximation problem

zbMATH Keywords

linear convergenceDykstra's projection algorithmKurdyka-Łojasiewicz property\(C^{1,\alpha}\)-cone reducibility

Mathematics Subject Classification ID

Convex programming (90C25) Optimality conditions and duality in mathematical programming (90C46) Applications of mathematical programming (90C90) Nonlinear programming (90C30)

Cites Work

• On Projection Algorithms for Solving Convex Feasibility Problems
• Convex Analysis
• A coordinate gradient descent method for nonsmooth separable minimization
• A multiprojection algorithm using Bregman projections in a product space
• Proximal Alternating Minimization and Projection Methods for Nonconvex Problems: An Approach Based on the Kurdyka-Łojasiewicz Inequality
• The multiple-sets split feasibility problem and its applications for inverse problems
• Proximal alternating linearized minimization for nonconvex and nonsmooth problems
• Iterative oblique projection onto convex sets and the split feasibility problem
• Implicit Functions and Solution Mappings
• Title not available (Why is that?)
• Title not available (Why is that?)
• Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods
• Title not available (Why is that?)
• On the convergence of the proximal algorithm for nonsmooth functions involving analytic features
• A cyclic projection algorithm via duality
• A successive projection method
• Error bounds and convergence analysis of feasible descent methods: A general approach
• Dykstra's alternating projection algorithm for two sets
• Convex analysis and monotone operator theory in Hilbert spaces
• Sensitivity analysis of generalized equations
• Strong conical hull intersection property, bounded linear regularity, Jameson's property \((G)\), and error bounds in convex optimization
• On the ergodic convergence rates of a first-order primal-dual algorithm
• The rate of convergence of dykstra's cyclic projections algorithm: The polyhedral case
• Convex Functions with Unbounded Level Sets and Applications to Duality Theory
• Modified alternating direction methods for the modified multiple-sets split feasibility problems
• Two generalizations of Dykstra's cyclic projections algorithm
• From error bounds to the complexity of first-order descent methods for convex functions
• Error bounds, quadratic growth, and linear convergence of proximal methods
• Dykstras algorithm with bregman projections: A convergence proof
• Set intersection problems: supporting hyperplanes and quadratic programming
• On Dykstra's algorithm: finite convergence, stalling, and the method of alternating projections
• Calculus of the exponent of Kurdyka-Łojasiewicz inequality and its applications to linear convergence of first-order methods
• A family of inexact SQA methods for non-smooth convex minimization with provable convergence guarantees based on the Luo-Tseng error bound property
• Iterative reweighted linear least squares for exact penalty subproblems on product sets
• A generalized block-iterative projection method for the common fixed point problem induced by cutters
• Dynamic string‐averaging CQ‐methods for the split feasibility problem with percentage violation constraints arising in radiation therapy treatment planning
• Kurdyka-Łojasiewicz exponent via inf-projection
• Distributed deterministic asynchronous algorithms in time-varying graphs through Dykstra splitting
• The Exact Modulus of the Generalized Concave Kurdyka-Łojasiewicz Property

This page was built for publication: Convergence Rate Analysis of a Dykstra-Type Projection Algorithm

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6202756)