Dışbükey kümeler üzerine projeksiyonlar - Projections onto convex sets

Bu makale olabilir kafa karıştırıcı veya belirsiz okuyuculara. Lütfen bize yardım et makaleyi netleştir. Bununla ilgili bir tartışma olabilir konuşma sayfası. (Nisan 2018) (Bu şablon mesajını nasıl ve ne zaman kaldıracağınızı öğrenin)

Matematikte, dışbükey kümeler üzerine projeksiyonlar (POCS), bazen olarak bilinir alternatif projeksiyon yöntem, ikisinin kesişiminde bir nokta bulma yöntemidir. kapalı dışbükey setleri. Çok basit bir algoritmadır ve birçok kez yeniden keşfedilmiştir.^[1] En basit durum, setler olduğunda afin boşluklar, tarafından analiz edildi John von Neumann.^[2][3] Kümelerin yakın uzaylar olduğu durum özeldir, çünkü yinelemeler yalnızca kesişimdeki bir noktaya yakınsamakla kalmaz (kesişimin boş olmadığı varsayılarak), aynı zamanda noktanın kesişme üzerindeki ortogonal izdüşümüne de yakınsar. Genel kapalı dışbükey kümeler için sınır noktasının izdüşüm olması gerekmez. İki kapalı dışbükey kümenin durumuyla ilgili klasik çalışma, yakınsama oranı yinelemelerin% 'si doğrusaldır.^[4][5]Artık, birden fazla setin olduğu veya setlerin olmadığı durumları dikkate alan uzantılar var. dışbükey,^[6] veya daha hızlı yakınsama oranları sağlar. POCS analizi ve ilgili yöntemler, algoritmanın yakınsadığını göstermeye çalışır (ve eğer öyleyse, yakınsama oranı ) ve projeksiyon orijinal noktanın. Bu sorular büyük ölçüde basit vakalarla bilinir, ancak uzantılar için aktif bir araştırma konusudur. Algoritmanın varyantları da vardır, örneğin Dykstra'nın projeksiyon algoritması. Referanslara bakın daha fazla okuma POCS yönteminin varyantlarına, uzantılarına ve uygulamalarına genel bir bakış için bölüm; iyi bir tarihsel arka plan, bölüm III'te bulunabilir.^[7]

Algoritma

İki daire üzerine örnek

POCS algoritması aşağıdaki sorunu çözer:

${ displaystyle { text {bul}} ; x in mathbb {R} ^ {n} quad { text {böyle}} ; x C cap D içinde}$

nerede C ve D vardır kapalı dışbükey kümeler.

POCS algoritmasını kullanmak için, setlere nasıl yansıtma yapılacağını bilmek gerekir C ve D Algoritma, rastgele bir değerle başlar. ${ displaystyle x_ {0}}$ ve sonra diziyi oluşturur

${ displaystyle x_ {k + 1} = { mathcal {P}} _ {C} left ({ mathcal {P}} _ {D} (x_ {k}) sağ).}$

Algoritmanın basitliği, popülaritesinin bir kısmını açıklıyor. Eğer kavşak nın-nin C ve D boş değildir, sonra sıra algoritma tarafından üretilen yakınsamak bu kesişme noktasında bir noktaya.

Aksine Dykstra'nın projeksiyon algoritması çözümün kesişme noktasına bir izdüşüm olması gerekmez C ve D.

İlgili algoritmalar

Nın bir örneği ortalama tahminler varyant

Yöntemi ortalama tahminler oldukça benzer. İki kapalı dışbükey set durumunda C ve D, tarafından ilerler

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

Küresel olarak birleştiği uzun zamandır bilinmektedir.^[8] Dahası, yöntemin ikiden fazla kümeye genellenmesi kolaydır; bu durum için bazı yakınsama sonuçları var.^[9]

ortalama projeksiyon yöntemi şu şekilde yeniden formüle edilebilir: değişen standart bir numara kullanarak projeksiyon yöntemi. Seti düşünün

${ displaystyle E = {(x, y): x C, ; y D }}$

hangi ürün alanı ${ displaystyle mathbb {R} ^ {n} times mathbb {R} ^ {n}}$Ardından, ürün alanında da başka bir küme tanımlayın:

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

Böylece bulmak ${ displaystyle C cap D}$ bulmaya eşdeğerdir ${ displaystyle E cap F}$.

Bir nokta bulmak için ${ displaystyle E cap F}$alternatif projeksiyon yöntemini kullanın. Bir vektörün izdüşümü ${ displaystyle (x, y)}$ sete F tarafından verilir ${ displaystyle (x + y, x + y) / 2}$. Bu nedenle

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

Dan beri ${ displaystyle x_ {k + 1} = y_ {k + 1}}$ ve varsaymak ${ displaystyle x_ {0} = y_ {0}}$, sonra ${ displaystyle x_ {j} = y_ {j}}$ hepsi için ${ displaystyle j geq 0}$ve dolayısıyla yinelemeyi basitleştirebiliriz ${ displaystyle x_ {k + 1} = { frac {1} {2}} ({ mathcal {P}} _ {C} (x_ {k}) + { mathcal {P}} _ {D} (x_ {k}))}$.

Referanslar

daha fazla okuma

• 2011 yılı kitabı: Alternatif Projeksiyon Yöntemleri René Escalante ve Marcos Raydan (2011), SIAM tarafından yayınlanmıştır.