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

DOI10.1137/130919052MaRDI QIDQ4979877zbMATH OpenOpenAlexWikidataFDO

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

Publication date 19 June 2014

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

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

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)

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.

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

Cited in

(39)

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

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)