Projekce na konvexní množiny - Projections onto convex sets
tento článek možná matoucí nebo nejasné čtenářům.Dubna 2018) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) ( |
V matematice projekce na konvexní sady (POCS), někdy známý jako střídavá projekce metoda, je metoda k nalezení bodu v průsečíku dvou Zavřeno konvexní sady. Je to velmi jednoduchý algoritmus a byl znovuobjeven mnohokrát.[1] Nejjednodušší případ, když jsou sady afinní prostory, byl analyzován uživatelem John von Neumann.[2][3] Případ, kdy jsou množiny afinní prostory, je zvláštní, protože iterace nejen konvergují k bodu v průsečíku (za předpokladu, že průnik není prázdný), ale také k ortogonální projekci bodu na průsečík. U obecně uzavřených konvexních množin nemusí být mezním bodem projekce. Klasická práce na případě dvou uzavřených konvexních množin ukazuje, že rychlost konvergence iterátů je lineární.[4][5]Nyní existují rozšíření, která berou v úvahu případy, kdy existuje více než jedna sada, nebo když sady nejsou konvexní,[6] nebo které poskytují rychlejší konvergenční sazby. Analýza POCS a souvisejících metod se pokouší ukázat, že algoritmus konverguje (a pokud ano, najděte rychlost konvergence ) a zda konverguje k projekce původního bodu. Tyto otázky jsou většinou známé pro jednoduché případy, ale téma aktivního výzkumu rozšíření. Existují také varianty algoritmu, například Dykstrův projekční algoritmus. Viz odkazy v Další čtení sekce pro přehled variant, rozšíření a aplikací metody POCS; dobré historické pozadí najdete v části III.[7]
Algoritmus
Algoritmus POCS řeší následující problém:
kde C a D jsou Zavřeno konvexní sady.
Chcete-li použít algoritmus POCS, musíte vědět, jak promítat do množin C a D samostatně. Algoritmus začíná libovolnou hodnotou pro a poté vygeneruje sekvenci
Jednoduchost algoritmu vysvětluje některé jeho popularity. Pokud průsečík z C a D není prázdné, pak sekvence generované algoritmem bude konvergovat do určitého bodu v této křižovatce.
Na rozdíl od Dykstrův projekční algoritmus, řešením nemusí být projekce na křižovatku C a D.
Související algoritmy
Metoda průměrné projekce je docela podobný. Pro případ dvou uzavřených konvexních sad C a D, postupuje tím
Je již dlouho známo, že se globálně sbližuje.[8] Dále lze metodu snadno zobecnit na více než dvě sady; některé výsledky konvergence pro tento případ jsou v.[9]
The průměrně metodu projekce lze přeformulovat jako střídavý metoda projekcí pomocí standardního triku. Zvažte sadu
který je definován v produktový prostor Poté definujte další sadu, také v produktovém prostoru:
Tak zjištění je ekvivalentní nálezu .
Chcete-li najít bod v , použijte metodu střídavé projekce. Projekce vektoru na scénu F je dána . Proto
Od té doby a za předpokladu , pak pro všechny , a proto můžeme iteraci zjednodušit na .
Reference
- ^ Bauschke, H.H .; Borwein, J. M. (1996). "O projekčních algoritmech pro řešení konvexních problémů proveditelnosti". Recenze SIAM. 38 (3): 367–426. CiteSeerX 10.1.1.49.4940. doi:10.1137 / S0036144593251710.
- ^ J. von Neumann,Neumann, John Von (1949). „Na kruzích operátorů. Teorie redukce“. Ann. matematiky. 50 (2): 401–485. doi:10.2307/1969463. JSTOR 1969463. (dotisk poznámek, které byly poprvé distribuovány v roce 1933)
- ^ J. von Neumann. Funkční operátoři, svazek II. Princeton University Press, Princeton, NJ, 1950. Dotisk mimeografických přednášek nejprve distribuovaných v roce 1933.
- ^ Gubin, L.G .; Polyak, B.T .; Raik, E.V. (1967). "Metoda projekcí pro nalezení společného bodu konvexních množin". U.S.S.R. Výpočetní matematika a matematická fyzika. 7 (6): 1–24. doi:10.1016/0041-5553(67)90113-9.
- ^ Bauschke, H.H .; Borwein, J. M. (1993). "O konvergenci von Neumannova alternačního projekčního algoritmu pro dvě sady". Set-Valued Analysis. 1 (2): 185–212. doi:10.1007 / bf01027691.
- ^ Lewis, A. S .; Malick, J. (2008). "Střídavé projekce na rozdělovače". Matematika operačního výzkumu. 33: 216–234. CiteSeerX 10.1.1.416.6182. doi:10,1287 / měsíc 1070,0291.
- ^ Combettes, P. L. (1993). „Základy teoretického odhadu množiny“ (PDF). Sborník IEEE. 81 (2): 182–208. doi:10.1109/5.214546. Archivovány od originál (PDF) dne 2015-06-14. Citováno 2012-10-09.
- ^ A. Auslender. Metody Numeriques pour la Resolution des Problems d’Optimisation avec Constraintes. Disertační práce, Faculte des Sciences, Grenoble, 1969
- ^ Místní konvergence pro střídavé a průměrné nekonvexní projekce. A Lewis, R Luke, J Malick, 2007. arXiv
Další čtení
- Kniha z roku 2011: Střídavé projekční metody autorů René Escalante a Marcos Raydan (2011), publikovaných SIAM.