凸集合への射影

数学において、凸集合への射影（POCS ）は交互射影法とも呼ばれ、2つの閉じた 凸集合の交点を見つける手法である。これは非常に単純なアルゴリズムで、何度も再発見されている。^[1]最も単純なケースである、集合がアフィン空間である場合は、ジョン・フォン・ノイマンによって解析された。^{[2] [3]}集合がアフィン空間である場合は特殊であり、反復は交点（交点が空でないと仮定）に収束するだけでなく、その点の交点への直交射影にも収束する。一般的な閉凸集合の場合、極限点は射影である必要はない。2つの閉凸集合の場合の古典的な研究では、反復の収束率が線形であることが示されている。 ^{[4] [5]現在では、集合が3つ以上ある場合や集合が}凸でない場合を考慮した拡張や、^[6]より高速な収束率を与える 拡張が存在する。 POCS および関連手法の分析では、アルゴリズムが収束するかどうか (収束する場合は収束率)、および元の点の投影に収束するかどうかを示そうとします。これらの質問は、単純なケースでは主に知られていますが、拡張については活発に研究されています。アルゴリズムには、 Dykstra の投影アルゴリズムなどのバリエーションもあります。POCS 法のバリエーション、拡張、およびアプリケーションの概要については、参考文献のセクションを参照してください。優れた歴史的背景は、セクション III に記載されています。^[7]

POCS アルゴリズムは次の問題を解決します。

${\displaystyle {\text{x\in \mathbb {R} ^{n}\quad {\text{x\in C\cap D} を求める}$

ここで、CとD は閉凸 集合です。

POCS アルゴリズムを使用するには、投影を介してセットCとDに個別に投影する方法を知っておく必要があります。 ${\displaystyle {\mathcal {P}}_{i}}$

アルゴリズムは任意の値から始まり、シーケンスを生成する。 ${\displaystyle x_{0}}$

${\displaystyle x_{k+1}={\mathcal {P}}_{C}\left({\mathcal {P}}_{D}(x_{k})\right).}$

アルゴリズムの単純さが、その人気の理由の 1 つです。Cと Dの交差点が空でない場合、アルゴリズムによって生成されたシーケンスは、この交差点のどこかの点に 収束します。

Dykstra の射影アルゴリズムとは異なり、解は交差点CとDへの射影である必要はありません。

平均射影法も非常によく似ている。2つの閉凸集合CとDの場合、次のように進む。

${\displaystyle x_{k+1}={\frac {1}{2}}({\mathcal {P}}_{C}(x_{k})+{\mathcal {P}}_{D}(x_{k}))}$

この方法は大域的に収束することが古くから知られています。^[8] さらに、この方法は2つ以上の集合に一般化することも容易であり、この場合の収束結果もいくつか得られています。^[9]

平均投影法は、標準的なトリックを使用して交互投影法として再定式化することができます。次の集合を考えてみましょう。

${\displaystyle E=\{(x,y):x\in C,\;y\in D\}}$

これは積空間 で定義されます。次に、積空間で別のセットを定義します。 ${\displaystyle \mathbb {R} ^{n}\times \mathbb {R} ^{n}}$

${\displaystyle F=\{(x,y):x\in \mathbb {R} ^{n},\,y\in \mathbb {R} ^{n},\;x=y\}.}$

したがって、 を見つけることはを見つけることと同等です。 ${\displaystyle C\cap D}$${\displaystyle E\cap F}$

内の点を見つけるには、交代射影法を使用します。ベクトルの集合Fへの射影は で与えられます。したがって、 ${\displaystyle E\cap F}$${\displaystyle (x,y)}$${\displaystyle (x+y,x+y)/2}$

${\displaystyle (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}))。 }$

および を仮定すると、すべての に対してとなり、したがって反復を に簡略化できます。 ${\displaystyle x_{k+1}=y_{k+1}}$${\displaystyle x_{0}=y_{0}}$${\displaystyle x_{j}=y_{j}}$${\displaystyle j\geq 0}$${\displaystyle x_{k+1}={\frac {1}{2}}({\mathcal {P}}_{C}(x_{k})+{\mathcal {P}}_{D}(x_{k}))}$

• 2011 年の書籍: René Escalante と Marcos Raydan 著『Alternating Projection Methods』(2011 年)、SIAM 発行。