Eşzamanlı pertürbasyon stokastik yaklaşım - Simultaneous perturbation stochastic approximation

Eşzamanlı pertürbasyon stokastik yaklaşım (SPSA) bir algoritmik birden fazla bilinmeyenli sistemleri optimize etme yöntemi parametreleri. Bu bir tür stokastik yaklaşım algoritması. Bir optimizasyon yöntemi olarak, büyük ölçekli popülasyon modellerine, uyarlamalı modellemeye, simülasyona uygun şekilde uygundur. optimizasyon, ve atmosferik modelleme. SPSA web sitesinde birçok örnek sunulmaktadır. http://www.jhuapl.edu/SPSA. Konuyla ilgili yeni kapsamlı bir kitap Bhatnagar ve ark. (2013). Konuyla ilgili erken bir makale Spall (1987) ve temel teori ve gerekçelendirmeyi sağlayan temel makale Spall (1992) 'dir.

SPSA, küresel minimumları bulabilen, bu özelliği diğer yöntemlerle paylaşan bir iniş yöntemidir. benzetimli tavlama. Temel özelliği, optimizasyon probleminin boyutuna bakılmaksızın, amaç fonksiyonunun sadece iki ölçümünü gerektiren gradyan yaklaşımıdır. Optimum kontrolü bulmak istediğimizi hatırlayın ${ displaystyle u ^ {*}}$ kayıp fonksiyonlu ${ displaystyle J (u)}$:

${ displaystyle u ^ {*} = arg min _ {u , U} J (u).}$

Hem Sonlu Farklılıklar Stokastik Yaklaşım (FDSA) hem de SPSA aynı yinelemeli süreci kullanır:

${ displaystyle u_ {n + 1} = u_ {n} -a_ {n} { hat {g}} _ {n} (u_ {n}),}$

nerede ${ displaystyle u_ {n} = ((u_ {n}) _ {1}, (u_ {n}) _ {2}, ldots, (u_ {n}) _ {p}) ^ {T}}$temsil etmek ${ displaystyle n ^ {th}}$ yinelemek, ${ displaystyle { hat {g}} _ {n} (u_ {n})}$ amaç fonksiyonunun gradyanının tahminidir ${ displaystyle g (u) = { frac { kısmi} { kısmi u}} J (u)}$ değerlendirildi ${ displaystyle {u_ {n}}}$, ve ${ displaystyle {a_ {n} }}$ 0'a yakınsayan pozitif bir sayı dizisidir. ${ displaystyle u_ {n}}$ bir pboyutlu vektör, ${ displaystyle i ^ {th}}$ bileşeni simetrik sonlu fark gradyan tahmincisi:

FD: ${ displaystyle ({ hat {g_ {n}}} (u_ {n})) _ {i} = { frac {J (u_ {n} + c_ {n} e_ {i}) - J (u_ {n} -c_ {n} e_ {i})} {2c_ {n}}},}$

1 ≤i ≤p, nerede ${ displaystyle e_ {i}}$ içinde 1 olan birim vektördür ${ displaystyle i ^ {th}}$yer ve ${ displaystyle c_ {n}}$ile azalan küçük bir pozitif sayıdır n. Bu yöntemle, 2p değerlendirmeleri J her biri için ${ displaystyle g_ {n}}$ ihtiyaç vardır. Açıkça, ne zaman p büyük, bu tahmin edici verimliliği kaybeder.

Şimdi ${ displaystyle Delta _ {n}}$ rastgele bir tedirginlik vektörü olabilir. ${ displaystyle i ^ {th}}$ Stokastik pertürbasyon gradyan tahmin edicisinin bileşeni:

SP: ${ displaystyle ({ hat {g_ {n}}} (u_ {n})) _ {i} = { frac {J (u_ {n} + c_ {n} Delta _ {n}) - J (u_ {n} -c_ {n} Delta _ {n})} {2c_ {n} ( Delta _ {n}) _ {i}}}.}$

FD'nin her seferinde yalnızca bir yönü bozduğuna, SP tahmincisinin aynı anda tüm yönleri bozduğuna dikkat edin (pay hepsinde aynıdır p bileşenleri). Her biri için SPSA yönteminde ihtiyaç duyulan kayıp fonksiyonu ölçümlerinin sayısı ${ displaystyle g_ {n}}$ her zaman 2'dir, bağımsız olarak boyut p. Böylece SPSA, p FDSA'dan kat daha az işlev değerlendirmesi, bu da onu çok daha verimli hale getirir.

İle basit deneyler p = 2 SPSA'nın FDSA ile aynı sayıda yinelemede yakınsadığını gösterdi. İkincisi takip eder yaklaşık olarak en dik iniş yönü, gradyan yöntemi gibi davranır. Öte yandan, rastgele arama yönüne sahip SPSA, gradyan yolunu tam olarak izlemez. Ortalama olarak, neredeyse izler çünkü gradyan yaklaşımı neredeyse tarafsız aşağıdaki lemmada gösterildiği gibi gradyan tahmin edicisi.

Yakınsama lemma

Gösteren

${ displaystyle b_ {n} = E [{ hat {g}} _ {n} | u_ {n}] - nabla J (u_ {n})}$

tahmin edicideki önyargı ${ displaystyle { hat {g}} _ {n}}$. Varsayalım ki ${ displaystyle {( Delta _ {n}) _ {i} }}$ sıfır ortalamalı, sınırlı ikinci anlarla karşılıklı olarak bağımsızdır ve ${ displaystyle E (| ( Delta _ {n}) _ {i} | ^ {- 1})}$ düzgün sınırlı. Sonra ${ displaystyle b_ {n}}$→ 0 ağ. 1.

İspatın taslağı

Ana fikir şartlandırmayı kullanmak ${ displaystyle Delta _ {n}}$ ifade etmek ${ displaystyle E [({ hat {g}} _ {n}) _ {i}]}$ ve sonra ikinci dereceden Taylor açılımını kullanmak için ${ displaystyle J (u_ {n} + c_ {n} Delta _ {n}) _ {i}}$ ve ${ displaystyle J (u_ {n} -c_ {n} Delta _ {n}) _ {i}}$. Sıfır ortalamasını ve bağımsızlığını kullanan cebirsel işlemlerden sonra ${ displaystyle {( Delta _ {n}) _ {i} }}$, anlıyoruz

${ displaystyle E [({ hat {g}} _ {n}) _ {i}] = (g_ {n}) _ {i} + O (c_ {n} ^ {2})}$

Sonuç, hipotez o ${ displaystyle c_ {n}}$→0.

Daha sonra, altında yatan bazı hipotezlere devam ediyoruz ${ displaystyle u_ {t}}$ birleşir olasılık küresel minimumlar kümesine ${ displaystyle J (u)}$. Yöntemin etkinliği uygulama şekline bağlıdır. ${ displaystyle J (u)}$, parametrelerin değerleri ${ displaystyle a_ {n}}$ ve ${ displaystyle c_ {n}}$ ve tedirginlik terimlerinin dağılımı ${ displaystyle Delta _ {ni}}$. İlk olarak, algoritma parametreleri aşağıdaki koşulları sağlamalıdır:

• ${ displaystyle a_ {n}}$ >0, ${ displaystyle a_ {n}}$→ 0, n → ∝ ve ${ displaystyle toplam _ {n = 1} ^ { infty} a_ {n} = infty}$. İyi bir seçim olurdu ${ displaystyle a_ {n} = { frac {a} {n}};}$ a> 0;
• ${ displaystyle c_ {n} = { frac {c} {n ^ { gamma}}}}$, burada c> 0, ${ displaystyle gamma in sol [{ frac {1} {6}}, { frac {1} {2}} sağ]}$;
• ${ displaystyle toplamı _ {n = 1} ^ { infty} ({ frac {a_ {n}} {c_ {n}}}) ^ {2} < infty}$
• ${ displaystyle Delta _ {ni}}$ karşılıklı bağımsız sıfır ortalamalı rastgele değişkenler olmalı, simetrik olarak yaklaşık sıfıra dağılmış olmalı, ${ displaystyle Delta _ {ni}$. Ters birinci ve ikinci anları ${ displaystyle Delta _ {ni}}$ sonlu olmalıdır.

İçin iyi bir seçim ${ displaystyle Delta _ {ni}}$ ... Rademacher dağılımı, yani 0.5 olasılıkla Bernoulli + -1. Diğer seçimler de mümkündür, ancak üniform ve normal dağılımların, sonlu ters moment koşullarını karşılamadıkları için kullanılamayacağını unutmayın.

Kayıp işlevi J (u) sürekli üç kez olmalı ayırt edilebilir ve üçüncü türevin münferit unsurları sınırlandırılmalıdır: ${ displaystyle | J ^ {(3)} (u) |$. Ayrıca, ${ displaystyle | J (u) | rightarrow infty}$ gibi ${ displaystyle u sağ infty}$.

Ek olarak, ${ displaystyle nabla J}$ sürekli Lipschitz, sınırlı ve ODE olmalıdır ${ displaystyle { dot {u}} = g (u)}$ her başlangıç ​​koşulu için benzersiz bir çözüme sahip olmalıdır.Bu koşullar ve diğer birkaç koşulda, ${ displaystyle u_ {k}}$ yakınsak J (u) 'nun küresel minimumlar kümesine olasılıkla (bakınız Maryak ve Chin, 2008).

İkinci Dereceden (Newton) Yöntemlere Genişletme

Standart (deterministik) Newton-Raphson algoritmasının (bir "ikinci dereceden" yöntem) stokastik bir versiyonunun, asimptotik olarak optimal veya neredeyse optimal bir stokastik yaklaşım formu sağladığı bilinmektedir. SPSA ayrıca gürültülü kayıp ölçümlerine veya gürültülü gradyan ölçümlerine (stokastik gradyanlar) dayalı olarak kayıp fonksiyonunun Hessian matrisini verimli bir şekilde tahmin etmek için de kullanılabilir. Temel SPSA yönteminde olduğu gibi, problem boyutuna bakılmaksızın her yinelemede yalnızca küçük bir sabit sayıda kayıp ölçümü veya gradyan ölçümü gerekir. p. Kısa tartışmaya bakın Stokastik gradyan inişi.

Referanslar

• Bhatnagar, S., Prasad, H. L. ve Prashanth, L.A. (2013), Optimizasyon için Stokastik Özyineli Algoritmalar: Eşzamanlı Pertürbasyon Yöntemleri, Springer [1].
• Hirokami, T., Maeda, Y., Tsukada, H. (2006) "Eşzamanlı pertürbasyon stokastik yaklaşım kullanarak parametre tahmini", Japonya'da Elektrik Mühendisliği, 154 (2), 30–3 [2]
• Maryak, J.L. ve Chin, D.C. (2008), "Eşzamanlı Pertürbasyon Stokastik Yaklaşımla Küresel Rastgele Optimizasyon" Otomatik Kontrolde IEEE İşlemleri, cilt. 53, sayfa 780-783.
• Spall, J. C. (1987), "Maksimum Olabilirlik Parametresi Tahminleri Oluşturmak İçin Stokastik Bir Yaklaşım Tekniği" Amerikan Kontrol Konferansı Tutanakları, Minneapolis, MN, Haziran 1987, s. 1161–1167.
• Spall, J. C. (1992), "Eşzamanlı Pertürbasyon Gradyan Yaklaşımı Kullanılarak Çok Değişkenli Stokastik Yaklaşım" Otomatik Kontrolde IEEE İşlemleri, cilt. 37 (3), s. 332–341.
• Spall, J.C. (1998). "Etkili Optimizasyon için Eşzamanlı Pertürbasyon Yöntemine Genel Bakış" 2. Johns Hopkins APL Teknik Özet, 19(4), 482–492.
• Spall, J.C. (2003) Stokastik Arama ve Optimizasyona Giriş: Tahmin, Simülasyon ve Kontrol, Wiley. ISBN  0-471-33052-3 (Bölüm 7)