Dykstras projektionsalgoritm

Ej att förväxla med Dijkstras algoritm .

Dykstras algoritm är en metod som beräknar en punkt i skärningspunkten av konvexa mängder , och är en variant av den alternerande projektionsmetoden (även kallad metoden projektioner på konvexa mängder ). I sin enklaste form hittar metoden en punkt i skärningspunkten mellan två konvexa uppsättningar genom att iterativt projicera på var och en av de konvexa uppsättningarna; den skiljer sig från den alternerande projektionsmetoden genom att det finns mellanliggande steg. En parallell version av algoritmen utvecklades av Gaffke och Mathar.

Metoden är uppkallad efter Richard L. Dykstra som föreslog den på 1980-talet.

En nyckelskillnad mellan Dykstras algoritm och standardmetoden för alternerande projektion uppstår när det finns mer än en punkt i skärningspunkten mellan de två uppsättningarna. I det här fallet ger den alternerande projektionsmetoden någon godtycklig punkt i denna skärningspunkt, medan Dykstras algoritm ger en specifik punkt: projektionen av r på skärningspunkten, där r är den initiala punkten som används i algoritmen,

Algoritm

Dykstras algoritm hittar för varje $r$ det enda ${\bar {x}}\in C\cap D$ så att:

$\|{\bar {x}}}-r\|^{2}\leq \|xr\| ^{2},{\text{för alla }}x\i C\cap D,$

där $C,D$ är konvexa mängder . Detta problem motsvarar att hitta projektionen av $r$ på mängden ${\displaystyle C\cap D} ,$ som vi betecknar med ${\mathcal {P}}_{ C\cap D}$ .

För att använda Dykstras algoritm måste man veta hur man projicerar på uppsättningarna $C$ och $D$ separat.

Tänk först på den grundläggande alternerande projektionsmetoden (aka POCS) (först studerad, i fallet när mängderna $C,D$ var linjära delrum, av John von Neumann ), som initierar $x_{0}=r$ och genererar sedan sekvensen

$x_{k+1}={\mathcal {P}}_{C}\left({\mathcal {P}}_{D} (x_{k})\höger)$ .

Dykstras algoritm är av liknande form, men använder ytterligare hjälpvariabler. Börja med $x_{0}=r,p_{0}=q_{0}=0$ och uppdatera med

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

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

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

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

Sedan konvergerar sekvensen $(x_{k})$ till lösningen av det ursprungliga problemet. För konvergensresultat och ett modernt perspektiv på litteraturen, se

•   Boyle, JP; Dykstra, RL (1986). En metod för att hitta projektioner på skärningspunkten mellan konvexa mängder i Hilbert-rum . Föreläsningsanteckningar i statistik . Vol. 37. s. 28–47. doi : 10.1007/978-1-4613-9940-7_3 . ISBN 978-0-387-96419-5 .
•   Gaffke, N.; Mathar, R. (1989). "En cyklisk projektionsalgoritm via dualitet". Metrika . 36 : 29–54. doi : 10.1007/bf02614077 . S2CID 120944669 .