Projektion til konvekse sæt

Projektion i konvekse mængder ( engelsk projektions onto convex sets , POCS ), som nogle gange omtales som metoden til alternativ projektion , er en metode til at finde et punkt i skæringspunktet mellem to lukkede konvekse sæt . Dette er en meget simpel algoritme og er blevet genopdaget mange gange [1] . Det simple tilfælde, hvor mængderne er affine rum , blev analyseret af John von Neumann [2] [3] . Tilfældet med affine rum er et særligt tilfælde, da iterationerne ikke kun konvergerer til et punkt i skæringspunktet (forudsat at skæringspunktet ikke er tomt), men til den ortogonale projektion af det (oprindelige) punkt på skæringspunktet mellem mængder. I tilfælde af generelle lukkede konvekse sæt er grænsepunktet ikke nødvendigvis en projektion. Et klassisk papir for tilfældet med to lukkede konvekse sæt viser, at hastigheden for konvergens af iterationer er lineær [4] [5] . Der er udvidelser, der omhandler tilfælde, hvor der er mere end et sæt, eller når sættene ikke er konvekse [6] , eller varianter, der giver hurtigere konvergens. Når man analyserer POCS og relaterede metoder, forsøger man at vise, at algoritmen konvergerer (og hvis det er tilfældet, forsøger man at finde konvergenshastigheden ) og at finde ud af, om metoden konvergerer til projektionen af udgangspunktet. Svarene er mest kendt for simple tilfælde, men dette område udforskes aktivt i retning af generaliseringer. Der er to varianter af algoritmen, såsom Dykstras [7] algoritme . Se linkene i afsnittet Litteratur til yderligere læsning for en oversigt over varianter, generaliseringer og anvendelser af POCS-metoden. En god opsummering af metodens historie kan findes i afsnit III i Combets bog [8] .

Algoritme

POCS-algoritmen løser følgende problem:

finde sådan

\;x\in \mathbb {R} ^{n}\quad

\;x\in C\cap D

hvor C og D er to lukkede konvekse sæt .

For at bruge POCS-algoritmen skal du vide, hvordan du projicerer i sæt C og D separat. Algoritmen starter med en vilkårlig værdi og genererer en sekvens $x_{0}$

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

Algoritmens enkelhed forklarer dens popularitet. Hvis skæringspunktet mellem sættene C og D ikke er tomt, vil sekvensen genereret af algoritmen konvergere til et eller andet punkt ved deres skæringspunkt.

I modsætning til Dykstras designalgoritme , viser løsningen sig ikke nødvendigvis at være en projektion ind i skæringspunktet mellem sæt C og D.

Relaterede algoritmer

Den gennemsnitlige fremskrivningsmetode er den samme. I tilfælde af to lukkede konvekse sæt C og D fungerer det i henhold til formlen

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

Det har længe været kendt, at det konvergerer globalt [9] . Desuden er metoden let at generalisere til mere end to sæt. Nogle konvergensresultater for dette tilfælde kan findes i Lewis, Luke og Malik [10] .

Den gennemsnitlige projektionsmetode kan omformuleres som en alternativ projektionsmetode ved hjælp af et standardtrick. Overvej sættet

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

som er defineret i produktet af mellemrum . Lad os nu definere et andet sæt, også i produktet af mellemrum: ${\displaystyle \mathbb {R} ^{n}\times \mathbb {R} ^{n))$

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

Så svarer det at finde til at finde . $C\cap D$ $E\cap F$

For at finde et punkt i bruger vi metoden med alternativ projektion. Projektionen af en vektor til mængden F er givet ved udtrykket , derfor, $E\cap F$ $(x,y)$ $(x+y,x+y)/2$

(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})).

Da , under den antagelse at , vil vi have for alle , og derfor kan vi forenkle iterationen til . $x_{k+1}=y_{k+1}$ $x_{0}=y_{0}$ ${\displaystyle x_{j}=y_{j))$ $j\geqslant 0$ $x_{k+1}={\frac {1}{2}}({\mathcal {P}}_{C}(x_{k})+{\mathcal {P}}_{D} (x_{k}))$

Noter

↑ Bauschke og Borwein 1996 , s. 367-426.
↑ von Neumann, 1949 , s. 401-485.
↑ von Neumann, 1950 .
↑ Gurin, Polyak, Raik, 1967 , s. 1-24.
↑ Bauschke og Borwein 1993 , s. 185-212.
↑ Lewis og Malick, 2008 , s. 216-234.
↑ Bemærk venligst, Dykstra, ikke Dijkstra, det er forskellige mennesker.
↑ Combettes, 1993 , s. 182-208.
↑ Auslender, 1969 .
↑ Lokal konvergens for alternerende og gennemsnitlige ikke-konvekse fremskrivninger. A Lewis, R Luke, J Malick, 2007. arXiv

Litteratur

A. Auslender. Numeriske metoder for Resolution des Problems d'Optimization med begrænsninger. - Grenoble: Faculte des Sciences, 1969. - (PhD-afhandling).
Bauschke HH, Borwein JM Om projektionsalgoritmer til løsning af konvekse gennemførlighedsproblemer // SIAM Review. - 1996. - T. 38 , no. 3 . - doi : 10.1137/S0036144593251710 .
J. von Neumann. På ringe af operatører. Reduktionsteori // Ann. af math.. - 1949. - V. 50 , no. 2 . - doi : 10.2307/1969463 . — . (Genoptryk af forelæsningsnotater udgivet i 1933)
J. von Neumann. Funktionelle operatører. - Princeton, NJ: Princeton University Press, 1950. - Vol. II. Genoptryk af mimeograferede forelæsningsnoter distribueret første gang i 1933
L.G. Gurin, B.T. Polyak, E.V. Raik. Projektionsmetoder til at finde et fælles punkt for konvekse sæt // Zh. Vychisl. matematik. og mat. fysik - 1967. - V. 7 , no. 6 .
Bauschke HH, Borwein JM Om konvergensen af von Neumanns alternerende projektionsalgoritme for to sæt // Set-Valued Analysis. - 1993. - Vol. 1 , udgave. 2 . - doi : 10.1007/bf01027691 .
Lewis AS, Malick J. Alternating Projections on Manifolds // Mathematics of Operations Research. - 2008. - T. 33 . - doi : 10.1287/moor.1070.0291 .
Combettes PL Grundlaget for sætteoretisk estimering // Proceedings of the IEEE. - 1993. - T. 81 , no. 2 . - doi : 10.1109/5.214546 .

Læsning for yderligere læsning

René Escalante, Marcos Raydan. Skiftende projektionsmetoder . — SIAM, 2011.