다이크스트라의 투영 알고리즘

다이크스트라의 알고리즘은 볼록 집합의 교차점에 있는 점을 계산하는 방법으로, 교대 투영법(볼록 집합에 대한 투영법이라고도 함)의 변형이다.가장 간단한 형태에서, 이 방법은 각각의 볼록 세트에 반복적으로 투영함으로써 두 볼록 세트의 교차점에서 점을 찾는다; 중간 단계가 있다는 점에서 교대 투영 방법과 다르다.알고리즘의 병렬 버전은 Gaffke와 Mathar에 의해 개발되었다.

그 방법은 리처드 L의 이름을 따서 명명되었다.1980년대에 그것을 제안한 Dykstra.

다이크스트라의 알고리즘과 표준 교대 투영법 사이의 키 차이는 두 세트의 교차점에 점수가 둘 이상 있을 때 발생한다.이 경우, 교대 투영법은 이 교차로에서 어느 정도 임의의 지점을 주는 반면, Dykstra의 알고리즘은 특정 지점: r의 교차로 투영, 여기서 r은 알고리즘에서 사용되는 초기 지점이다.

알고리즘.

Dykstra의 알고리즘은 각 $r{\displaystyle }$ ${\displaystyle r}$에 대해 유일한$$ x${\displaystyle }x{\displaystyle \stackrel{}{}}$ ${\displaystyle C}$ ${\displaystyle \cap }$ ${\displaystyle D}$ ${\displaystyle {\x}\in$ C\$cap$ D$}$에서 다음과 같은 것을$$ 찾아낸다.

${\displaystyle \{\bar}-r\ ^{2}\leq \x-r\ ^{2},{\text{모든 }x\in C\cap D,}$

$여기$서 C${\displaystyle }$, ${\displaystyle D}$ ${\displaystyle C,D}$은(는) 볼록 세트다.이 문제는 우리가 P ${\displaystyle C_{}}$ ${\displaystyle {\cap }_{}}$ ${\displaystyle D_{}}$ ${\$C\$c\cap$ D$}$로 나타내는 $세트{\displaystyle }$ C ${\displaystyle \cap }$ D ${\displaystyle C\cap D}$에 $대한{\displaystyle }$ r ${\displaystystyle$ C\cap $d}$의 투영을 찾는 것과 동등하다$.$

다이크스트라의 알고리즘을 $사용$하려면 C {\$displaystyle$ C$}$과 D ${\displaystyle$ D$} 세트$에 개별적으로$$ 투영하는 방법을 알아야 한다.

${\displaystyle {먼저\mathrm{}}_{}}$ x 0 = r {\$displaystyle x_{0}=r}$을(를) 초기화한$$ 후 시퀀스를 생성하는 $C{\displaystyle }$, D ${\displaystyle C,D}$ 세트가 선형$$ 서브스페이스인 경우 John von Neumann에^[1] 의해 처음 연구됨) 기본 교대 투영법(a POCS)을 고려한다${\displaystyle {}_{}}$

${\displaystyle x_{}}$ ${\displaystyle k_{}}$+ ${\displaystyle 1_{}}$= ${\displaystyle P_{}}$ ${\displaystyle {}_{}}$( ${\displaystyle P_{}}$ ${\displaystyle D{\mathcal{}}_{}}$( x $){\$

다이크스트라의 알고리즘은 형태는 비슷하지만 추가 보조 변수를 사용한다.$x{\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$= ${\displaystyle r,}$ ${\displaystyle {p\mathrm{}}_{}}$ 0${\displaystyle {}_{}}$= ${\displaystyle \mathrm{q}}$ ${\displaystyle {0\mathrm{}}_{}}$= 0 ${\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}.$

그런 다음 순서$({\displaystyle {xk}_{}}$) ${\displaystyle(x_{k})$가 원래 문제의 해결책으로 수렴된다$$.통합 결과와 문헌에 대한 현대적 관점은 다음을 참조하십시오.

참조

• Boyle, J. P.; Dykstra, R. L. (1986). A method for finding projections onto the intersection of convex sets in Hilbert spaces. Lecture Notes in Statistics. Vol. 37. pp. 28–47. doi:10.1007/978-1-4613-9940-7_3. ISBN 978-0-387-96419-5.
• Gaffke, N.; Mathar, R. (1989). "A cyclic projection algorithm via duality". Metrika. 36: 29–54. doi:10.1007/bf02614077. S2CID 120944669.

인용구