ダイクストラの射影アルゴリズム

ダイクストラのアルゴリズムは、凸集合の交差点の点を計算する方法であり、交互投影法（凸集合への投影法とも呼ばれる）の変形です。最も単純な形式では、この方法は、2 つの凸集合の交差点の点を、各凸集合に繰り返し投影することによって求めます。交互投影法と異なるのは、中間ステップがある点です。このアルゴリズムの並列バージョンは、ガフケとマサーによって開発されました。

この方法は、1980 年代に提案した Richard L. Dykstra にちなんで名付けられました。

ダイクストラのアルゴリズムと標準的な交互投影法の主な違いは、2つの集合の交差点に複数の点がある場合に発生します。この場合、交互投影法では交差点に任意の点が与えられますが、ダイクストラのアルゴリズムでは特定の点、つまり交差点へのrの投影が与えられます。ここでrはアルゴリズムで使用される初期点です。

Dykstra のアルゴリズムは、それぞれに対して次の 唯一のものを見つけます。${\displaystyle r}$${\displaystyle {\bar {x}}\in C\cap D}$

${\displaystyle \|{\bar {x}}-r\|^{2}\leq \|xr\|^{2},{\text{すべての }}x\in C\cap D に対して、}$

ここで は凸集合です。この問題は、の集合 への射影を求めることと同等であり、これを と表記します。 ${\displaystyle C,D}$${\displaystyle r}$${\displaystyle C\cap D}$${\displaystyle {\mathcal {P}}_{C\cap D}}$

Dykstra のアルゴリズムを使用するには、セットに個別に投影する方法を知っている必要があります。 ${\displaystyle C}$${\displaystyle D}$

まず、基本的な交代射影法（別名POCS）（集合が線形部分空間の場合にジョン・フォン・ノイマン^[1]によって最初に研究された）を考えてみましょう。これは、シーケンスを 初期化して生成します。${\displaystyle C,D}$${\displaystyle x_{0}=r}$

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

ダイクストラのアルゴリズムは同様の形式ですが、追加の補助変数を使用します。から始めて、次のように更新します。 ${\displaystyle x_{0}=r,p_{0}=q_{0}=0}$

${\displaystyle y_{k}={\mathcal {P}}_{D}(x_{k}+p_{k})}$

${\displaystyle p_{k+1}=x_{k}+p_{k}-y_{k}}$

${\displaystyle x_{k+1}={\mathcal {P}}_{C}(y_{k}+q_{k})}$

${\displaystyle q_{k+1}=y_{k}+q_{k}-x_{k+1}.}$

そして、このシーケンスは元の問題の解に収束します。収束結果と文献の現代的な観点については、^{[2]を参照してください。}${\displaystyle (x_{k})}$

• Boyle, JP; Dykstr, RL (1986)。「ヒルベルト空間の凸集合の交差への射影を求める方法」。順序制限統計推論の進歩。統計学講義ノート。第 37 巻。pp. 28–47。doi : 10.1007 /978-1-4613-9940-7_3。ISBN 978-0-387-96419-5。
• Gaffke, N.; Mathar, R. (1989). 「双対性による巡回射影アルゴリズム」Metrika . 36 : 29–54. doi :10.1007/bf02614077. S2CID  120944669.