20210620 Successive projection algorithm（连续投影法）

https://en.wikipedia.org/wiki/Projections_onto_convex_sets

Algorithm
The POCS algorithm solves the following problem:
find $x\in {\mathbb{R}}^n$ such that $x\in C\cap D$
where $C$ and $D$ are closed convex sets.
To use the POCS algorithm, one must know how to project onto the sets $C$ and $D$ separately. The algorithm starts with an arbitrary value for $x_0$ and then generates the sequence
$$x_{k+1}={\mathcal{P}}_C\left({\mathcal{P}}_D\left(x_k\right)\right)$$
The simplicity of the algorithm explains some of its popularity. If the intersection of $C$ and $D$ is non-empty, then the sequence generated by the algorithm will converge to some point in this intersection.
Unlike Dykstra’s projection algorithm, the solution need not be a projection onto the intersection $C$ and $D$.

Related algorithms
The method of averaged projections is quite similar. For the case of two closed convex sets $C$ and $D$, it proceeds by
$$x_{k+1}=\frac{1}{2}\left({\mathcal{P}}_C\left(x_k\right)+{\mathcal{P}}_D\left(x_k\right)\right)$$
It has long been known to converge globally. ${}^{[8]}$ Furthermore, the method is easy to generalize to more than two sets; some convergence results for this case are in. ${}^{[9]}$

The averaged projections method can be reformulated as alternating projections method using a standard trick. Consider the set
$$E=\{(x,y):x\in C,y\in D\}$$
which is defined in the product space ${\mathbb{R}}^n\times {\mathbb{R}}^n$. Then define another set, also in the product
space:
$$F=\left\{(x,y):x\in {\mathbb{R}}^n,y\in {\mathbb{R}}^n,x=y\right\}.$$
Thus finding $C\cap D$ is equivalent to finding $E\cap F$.

To find a point in $E\cap F$, use the alternating projection method. The projection of a vector $(x,y)$ onto the set $F$ is given by $(x+y,x+y)/2$. Hence
$$\left(x_{k+1},y_{k+1}\right)={\mathcal{P}}_F\left({\mathcal{P}}_E\left(\left(x_k,y_k\right)\right)\right)={\mathcal{P}}_F\left(\left({\mathcal{P}}_C{x}_k,{\mathcal{P}}_D{y}_k\right)\right)=\frac{1}{2}({\mathcal{P}}_C\left(x_k\right)+{\mathcal{P}}_D\left(y_k\right),\left({\mathcal{P}}_C\left(x_k\right)+{\mathcal{P}}_D\left(y_k\right)\right)$$

Since $x_{k+1}=y_{k+1}$ and assuming $x_0=y_0$, then $x_j=y_j$ for all $j\ge 0$, and hence we can simplify the iteration to $x_{k+1}=\frac{1}{2}\left({\mathcal{P}}_C\left(x_k\right)+{\mathcal{P}}_D\left(x_k\right)\right)$.

总结

以上是生活随笔为你收集整理的20210620 Successive projection algorithm（连续投影法）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。