Analysis of the convergence rate for the cyclic projection algorithm applied to basic semialgebraic convex sets

DOI10.1137/130919052zbMATH Open1296.41011arXiv1304.7965OpenAlexW2129130711WikidataQ59241477 ScholiaQ59241477MaRDI QIDQ4979877FDOQ4979877

Authors: Jonathan M. Borwein, G. Li, Liangjin Yao 

Publication date: 19 June 2014

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

Abstract: In this paper, we study the rate of convergence of the cyclic projection algorithm applied to finitely many basic semi-algebraic convex sets. We establish an explicit convergence rate estimate which relies on the maximum degree of the polynomials that generate the basic semi-algebraic convex sets and the dimension of the underlying space. We achieve our results by exploiting the algebraic structure of the basic semi-algebraic convex sets.

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

Recommendations

• The rate of convergence for the cyclic projections algorithm. I: Angles between convex sets
• Convergence rate analysis and error bounds for projection algorithms in convex feasibility problems
• The rate of convergence for the cyclic projections algorithm. III: Regularity of convex sets
• The rate of convergence for the cyclic projections algorithm. II: Norms of nonlinear operators
• scientific article; zbMATH DE number 2033473

zbMATH Keywords

distance functionprojector operatorconvex polynomialFejér monotone sequenceŁojasiewicz's inequalitybasic semialgebraic convex setcyclic projection algorithmHölderian regularityvon Neumann alternating projection method

Mathematics Subject Classification ID

Convex programming (90C25) Sensitivity, stability, parametric optimization (90C31) Best approximation, Chebyshev systems (41A50) Rate of convergence, degree of approximation (41A25)

Cited In (40)

• An algorithm for generalized constrained multi-source Weber problem with demand substations
• A new projection method for finding the closest point in the intersection of convex sets
• On the convergence of general projection methods for solving convex feasibility problems with applications to the inverse problem of image recovery
• Stochastic quasi-subgradient method for stochastic quasi-convex feasibility problems
• Primal necessary characterizations of transversality properties
• Quasi-convex feasibility problems: subgradient methods and convergence rates
• Iteration process for fixed point problems and zeros of maximal monotone operators
• Hölder-type global error bounds for non-degenerate polynomial systems
• Convergence Rate of Inexact Proximal Point Algorithms for Operator with Hölder Metric Subregularity
• On local convergence of the method of alternating projections
• Convergence Rate Analysis of a Sequential Convex Programming Method with Line Search for a Class of Constrained Difference-of-Convex Optimization Problems
• Convergence rate analysis for averaged fixed point iterations in common fixed point problems
• Perturbation of error bounds
• A new algorithm for the minimax location problem with the closest distance
• Linear regularity and linear convergence of projection-based methods for solving convex feasibility problems
• New fractional error bounds for polynomial systems with applications to Hölderian stability in optimization and spectral theory of tensors
• Linear convergence of subgradient algorithm for convex feasibility on Riemannian manifolds
• Douglas-Rachford splitting for nonconvex optimization with application to nonconvex feasibility problems
• Transversality properties: primal sufficient conditions
• Error bounds for parametric polynomial systems with applications to higher-order stability analysis and convergence rates
• Convergence analysis of the generalized Douglas-Rachford splitting method under Hölder subregularity assumptions
• Implicit error bounds for Picard iterations on Hilbert spaces
• Exact convergence rates of alternating projections for nontransversal intersections
• Multiple-sets split quasi-convex feasibility problems: adaptive subgradient methods with convergence guarantee
• Infeasibility and Error Bound Imply Finite Convergence of Alternating Projections
• Comparing averaged relaxed cutters and projection methods: theory and examples
• Peaceman-Rachford splitting for a class of nonconvex optimization problems
• Convergence rate of the relaxed CQ algorithm under Hölderian type error bound property
• Affine Invariant Convergence Rates of the Conditional Gradient Method
• A privacy-preserving method to optimize distributed resource allocation
• Moduli of regularity and rates of convergence for Fejér monotone sequences
• Convergence rate analysis for fixed-point iterations of generalized averaged nonexpansive operators
• The rate of convergence for the cyclic projections algorithm. I: Angles between convex sets
• A learning-enhanced projection method for solving convex feasibility problems
• Convergence rate analysis of an iterative algorithm for solving the multiple-sets split equality problem
• Improved effective Łojasiewicz inequality and applications
• Analytic formulas for alternating projection sequences for the positive semidefinite cone and an application to convergence analysis
• Curiosities and counterexamples in smooth convex optimization
• Error bounds and Hölder metric subregularity
• A note on alternating projections for ill-posed semidefinite feasibility problems

This page was built for publication: Analysis of the convergence rate for the cyclic projection algorithm applied to basic semialgebraic convex sets

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