A Randomized Algorithm for Generalized Accelerated Projection Method

Tiancheng Qin, S. Rasoul Etesami

Research output: Contribution to journalArticle

Abstract

We consider the convex feasibility problem, which is to determine a point in the intersection of a finite number of closed convex sets. It was shown in the past literature a so-called generalized acceleration method converges to a feasible point in the intersection of all the sets, assuming the intersection set has a nonempty interior. In this letter, we establish the same convergence result without any assumption on the interior of the feasible set. In particular, we devise a randomized accelerated projection algorithm and prove its linear convergence rate when all the convex sets are half-spaces in a finite-dimensional Euclidean space. Numerical experiments comparing the generalized acceleration method with the classic cyclic projection methods are presented, which justify the fast convergence rate and the out-performance of the proposed algorithm.

Original languageEnglish (US)
Article number9113702
Pages (from-to)85-90
Number of pages6
JournalIEEE Control Systems Letters
Volume5
Issue number1
DOIs
StatePublished - Jan 2021

Keywords

  • Successive projection method
  • convex feasibility
  • convex optimization

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Control and Optimization

Fingerprint Dive into the research topics of 'A Randomized Algorithm for Generalized Accelerated Projection Method'. Together they form a unique fingerprint.

  • Cite this