4
$\begingroup$

Assume for simplicity $C_1,C_2,...,C_n\subset \mathbb{R}^m$ to be closed and convex subsets with $\underset{i=1}{\overset{n}{\bigcap{}}}C_i\neq\emptyset$.

Let $x^0\in\mathbb{R}^n$ and define the following iterative method: $$x^{k+1}=P_{C_{i_k}}(x^k)$$ Where $P_{C_{i_k}}$ is the projection onto the set $C_{i_k}$ and $i_k:\mathbb{N}\cup\{0\}\rightarrow\{1,...,n\}$ is the control sequence.

I would like to ask the following two questions:

Q1: The special case of $n=2$ is fairly well understood and an exact rate of convergence is known, see for example this paper. Is a similar result known for more than two subsets, perhaps with additional assumptions?

Q2: Some control sequences can be demonstrated numerically to be faster than others in terms of iterations, for example, the cyclic control: $$i_k=(k\mod n)+1$$ can be shown to be slower than the remotest set control: $$i_k=\underset{i\in\{1..n\}}{argmax}\:d(x^k,C_i)$$ Are there papers that capture this behavior theoretically?

$\endgroup$
2
  • 4
    $\begingroup$ Added the oc tag as per @StefanKohl's request. $\endgroup$
    – Dirk
    Oct 13, 2015 at 10:26
  • 2
    $\begingroup$ Change "$C_1, \ldots, C_n \subset \mathbb{R}^n$" to "$C_1, \ldots, C_m \subset \mathbb{R}^n$" $\endgroup$
    – dohmatob
    Oct 13, 2015 at 13:21

2 Answers 2

4
$\begingroup$

A lot of things are known for the convergence of alternating projections for these convex feasibility problems. I suggest to start with

H.H. Bauschke and J.M. Borwein: On projection algorithms for solving convex feasibility problems, SIAM Review 38(3), 1996

which can be obtained via the website of Heinz Bauschke. It's almost 20 years old, but even then a lot was known.

You may also check the book

Parallel Optimization: Theory, Algorithms, and Applications,Oxford University Press, 1997, Yair Censor, ‎Stavros Andrea Zenios.

For some newer results: There is something known for non-convex sets, also with a convergence rate, see e.g.

``Local Linear Convergence of Approximate Projections onto Regularized Sets '', D. R. Luke, Nonlinear Analysis, 75(2012):1531--1546. DOI: 10.1016/j.na.2011.08.027.

There are truly randomized versions, see e.g.

T. Strohmer, R. Vershynin: A randomized Kaczmarz algorithm with exponential convergence, J. Fourier Anal. Appl. 15(1), 262–278, 2009

for the Kaczmarz-method (i.e. the sets $C_i$ are hyperplanes).

Regarding the "remotest set control" I don't know results about convergence speed. From a practical point of view, it seems to me that this rule is not that use useful since in many cases computing the distance $d(x_k,C_i)$ is as expensive as computing the projection $P_{C_i}(x_k)$. In these cases one step with remotest set control is as costly as a whole sweep over all sets and there is no advantage in speed anymore…

$\endgroup$
1
2
$\begingroup$

If by chance the $C_k$'s are manifolds, then the following refs are relevant:

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.