Convergence Rate Analysis of a Dykstra-Type Projection Algorithm

DOI10.1137/23M1545781MaRDI QIDQ6202756zbMATH OpenOpenAlexWikidataFDO

Authors Xiaozhou Wang, Ting Kei Pong

Publication date 27 February 2024

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

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

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)

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.

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

Cites work

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

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)