Content deleted Content added
No edit summary |
→Related algorithms: clarifying relation between averaged and alternating projection method |
||
Line 29:
d’Optimisation avec Constraintes. PhD thesis, Faculte des Sciences, Grenoble, 1969</ref> Furthermore, the method is easy to generalize to more than two sets; some convergence results for this case are in <ref>Local convergence for alternating and averaged nonconvex projections. A Lewis, R Luke, J Malick, 2007. [http://arxiv.org/abs/0709.0109 arXiv]</ref>.
The ''averaged'' projections method can be reformulated as ''alternating'' projections method using a standard trick. Consider the set
<math> E = \{ (x,y) : x \in C, \; y \in D \}</math>
which is defined in the [[Tensor product|product space]] <math> \mathcal{R}^n \times \mathcal{R}^n </math>.
Then define another set, also in the product space:
<math> F = \{ (x,y) : x \in \mathcal{R}^b,\, y \in \mathcal{R}^n,\; x=y \}.</math>
Thus finding <math> C \cap D </math> is equivalent to finding <math> E \cap F</math>.
To find a point in <math> E \cap F</math>, use the alternating projection method. The projection of a vector <math>(x,y)</math> onto the set ''F'' is given by <math>(x+y,x+y)/2</math>. Hence
<math>(x_{k+1},y_{k+1}) = \mathcal{P}_{F}( \mathcal{P}_{E}( (x_{k},y_{k}) ) ) = \mathcal{P}_{F}( (\mathcal{P}_{C}x_{k},\mathcal{P}_{D}y_{k}) ) = \frac{1}{2}( \mathcal{P}_C(x_k) + \mathcal{P}_D(y_k) , (\mathcal{P}_C(x_k) + \mathcal{P}_D(y_k) ). </math>
Since <math> x_{k+1} = y_{k+1} </math> and assuming <math> x_0 = y_0 </math>, then <math>x_j=y_j</math> for all <math> j \ge 0</math>, and hence we can simplify the iteration to <math> x_{k+1} = \frac{1}{2}( \mathcal{P}_C(x_k) + \mathcal{P}_D(x_k) ) </math>.
== Further reading ==
| |||