समकालिक प्रक्षोभ प्रसंभाव्यता सन्निकटन

समकालिक प्रक्षोभ प्रसंभाव्यता सन्निकटन (एसपीएसए) कई अज्ञात पैरामीटर वाली प्रणाली को अनुकूलित करने के लिए कलन विधि विधि है। यह प्रकार का स्टोकेस्टिक सन्निकटन कलन विधि है। अनुकूलन पद्धति के रूप में यह बड़े पैमाने पर जनसंख्या मॉडल, अनुकूली प्रतिरूप , अनुरूप अनुकूलन और वायुमंडलीय प्रतिरूप के लिए उपयुक्त है। एसपीएसए की वेबसाइट http://www.jhuapl.edu/एसपीएसए पर कई उदाहरण प्रस्तुत किए गए हैं। इस विषय पर विस्तृत पुस्तक भटनागर एवं अन्य हैं। (2013). इस विषय पर प्रारंभिक कागज मंत्र (1987) है और मुख्य सिद्धांत और औचित्य प्रदान करने वाला मूलभूत कागज मंत्र (1992) है।

एसपीएसए एक मूल विधि है जो वैश्विक मिनीमा खोजने में सक्षम है, इस संपत्ति को सिम्युलेटेड एनीलिंग के रूप में अन्य तरीकों से साझा कर रही है। इसकी मुख्य विशेषता प्रवणता सन्निकटन है जिसके लिए अनुकूलन समस्या के आयाम की ध्यान किए बिना उद्देश्य फलन के केवल दो मापों की आवश्यकता होती है। याद रखें कि हम अनुकूलतम नियंत्रण खोजना चाहते हैं $u^{*}$ क्षति के साथ कार्य $J(u)$:

$u^{*}=\arg \min _{u\in U}J(u).$

दोनों परिमित अंतर स्टोकेस्टिक सन्निकटन (एफडीएसए) और एसपीएसए समान पुनरावृत्ति प्रक्रिया का उपयोग करते हैं

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

जहाँ $u_{n}=((u_{n})_{1},(u_{n})_{2},\ldots ,(u_{n})_{p})^{T}$ का प्रतिनिधित्व करता है $n^{th}$ पुनरावृति, ${\hat {g}}_{n}(u_{n})$ उद्देश्य कार्य के प्रवणता का अनुमान है $g(u)={\frac {\partial }{\partial u}}J(u)$ पर मूल्यांकन किया गया ${u_{n}}$, और $\{a_{n}\}$ धनात्मक संख्या क्रम है जो 0 में परिवर्तित हो रहा है। यदि $u_{n}$ P-आयामी दिष्‍ट है $i^{th}$ सममित परिमित अंतर प्रवणता अनुमानक का घटक है।

FD $({\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, जहां $e_{i}$ 1 के साथ इकाई दिष्‍ट है $i^{th}$ स्थान , और $c_{n}$ छोटी धनात्मक संख्या है जो n से घटती है। इस पद्धति के साथ, प्रत्येक के लिए J का 2p मूल्यांकन $g_{n}$ आवश्यकता है। स्पष्ट रूप से, जब p बड़ा होता है, तो यह अनुमानक दक्षता खो देता है।

देख है $\Delta _{n}$ यादृच्छिक प्रक्षोभ दिष्‍ट बनें। $i^{th}$ h> स्टोकेस्टिक प्रक्षोभ प्रवणता अनुमानक का घटक है।

SP : $({\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 समय में केवल दिशा को परेशान करता है, जबकि SP अनुमानक ही समय में सभी दिशाओं को परेशान करता है। सभी P घटकों में अंश समान होता है। प्रत्येक के लिए एसपीएसए पद्धति में आवश्यक हानि फलन मापों की संख्या $g_{n}$ आयाम p से स्वतंत्र सदैव 2 होता है। इस प्रकार, एसपीएसए, एफडीएसए की तुलना में p गुना कम फलन मूल्यांकन का उपयोग करता है, जो इसे बहुत अधिक कुशल बनाता है।

P = 2 के साथ सरल प्रयोगों से पता चला है कि एसपीएसए उसी संख्या में पुनरावृत्तियों में एफडीएसए के रूप में अभिसरण करता है। उत्तरार्द्ध प्रवणता पद्धति की भांति व्यवहार करते हुए, सबसे तेज वंश दिशा का अनुसरण करता है। दूसरी ओर, एसपीएसए , यादृच्छिक खोज दिशा के साथ पूरी भांति से प्रवणता पथ का पालन नहीं करता है। चूँकि औसतन, यह इसे लगभग चिह्नित करता है क्योंकि प्रवणता सन्निकटन लगभग निष्पक्ष है प्रवणता का अनुमानक, जैसा कि निम्नलिखित लेम्मा में दिखाया गया है।

अभिसरण लेम्मा

द्वारा निरूपित करें

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

अनुमानक में पक्षपात ${\hat {g}}_{n}$. ये मान लीजिए $\{(\Delta _{n})_{i}\}$ शून्य-माध्य, बंधे हुए दूसरे के साथ सभी परस्पर स्वतंत्र हैं क्षण, और $E(|(\Delta _{n})_{i}|^{-1})$ समान रूप से बंधा हुआ। तब $b_{n}$→ 0 W.P. 1.

प्रमाण का रेखाचित्र

मुख्य विचार अनुकूलन का उपयोग करना है $\Delta _{n}$ संकेत करना $E[({\hat {g}}_{n})_{i}]$ और फिर दूसरे क्रम के टेलर विस्तार का उपयोग करने के लिए $J(u_{n}+c_{n}\Delta _{n})_{i}$ और $J(u_{n}-c_{n}\Delta _{n})_{i}$. शून्य माध्य और स्वतंत्रता का उपयोग करके बीजगणितीय जोड़ तोड़ के बाद $\{(\Delta _{n})_{i}\}$, हम पाते हैं

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

परिणाम परिकल्पना से आता है कि $c_{n}$→ 0।

इसके बाद हम कुछ परिकल्पनाओं को फिर से प्रारंभ करते हैं जिनके अनुसार $u_{t}$ के वैश्विक न्यूनतम चयनकी संभावना में अभिसरण करता है $J(u)$. की दक्षता विधि के आकार पर निर्भर करती है $J(u)$, मापदंडों के मान $a_{n}$ और $c_{n}$ और प्रक्षोभ की परिस्थिति का वितरण $\Delta _{ni}$. सबसे पहले, कलन विधि मापदंडों को संतुष्ट करना चाहिए निम्नलिखित अवस्था,

• $a_{n}$ >0, $a_{n}$→0 जब n→∝ और $\sum _{n=1}^{\infty }a_{n}=\infty$. अच्छा विकल्प होगा $a_{n}={\frac {a}{n}};$ ए> 0;
• $c_{n}={\frac {c}{n^{\gamma }}}$, जहां सी> 0, $\gamma \in \left[{\frac {1}{6}},{\frac {1}{2}}\right]$;
• $\sum _{n=1}^{\infty }({\frac {a_{n}}{c_{n}}})^{2}<\infty$
• $\Delta _{ni}$ पारस्परिक रूप से स्वतंत्र शून्य-अर्थात यादृच्छिक चर होना चाहिए। सममित रूप से शून्य के साथ वितरित किया जाना चाहिए $\Delta _{ni}<a_{1}<\infty$. का उलटा पहला और दूसरा क्षण $\Delta _{ni}$ परिमित होना चाहिए।

इसके लिए अच्छा विकल्प है $\Delta _{ni}$ यादृच्छिक चर है, अर्थात बर्नौली +-1 जिसकी प्रायिकता 0.5 है। अन्य विकल्प भी संभव हैं, किन्तु ध्यान दें कि समान और सामान्य वितरण का उपयोग नहीं किया जा सकता, क्योंकि वे परिमित व्युत्क्रम क्षण स्थितियों को संतुष्ट नहीं करते हैं।

हानि फलन जे (यू) तीन बार लगातार भिन्न होने वाला फलन होना चाहिए और तीसरे यौगिक के अलग-अलग तत्वों को बाध्य किया जाना चाहिए। $|J^{(3)}(u)|<a_{3}<\infty$. भी, $|J(u)|\rightarrow \infty$ जैसा $u\rightarrow \infty$.

इसके साथ ही, $\nabla J$ लिप्सचिट्ज़ निरंतर, परिबद्ध और स्तोत्र होना चाहिए ${\dot {u}}=g(u)$ प्रत्येक प्रारंभिक स्थिति के लिए अनूठा समाधान होना चाहिए। इन परिस्थिति के अनुसार और कुछ अन्य, $u_{k}$ J(u) के वैश्विक न्यूनतम के समुच्चय की प्रायिकता में अभिसरण (गणित) (देखें मैरीक और चिन, 2008)।

यह दिखाया गया है कि भिन्नता की आवश्यकता नहीं है, निरंतरता और उत्तलता अभिसरण के लिए पर्याप्त हैं।

दूसरे क्रम (न्यूटन) विधियों का विस्तार

यह ज्ञात है कि मानक नियतात्मक न्यूटन-रैफसन कलन विधि ("द्वितीय-क्रम" विधि) का स्टोकेस्टिक संस्करण स्टोकेस्टिक सन्निकटन का विषम रूप से अनुकूलतम या निकट-अनुकूलतम रूप प्रदान करता है। एसपीएसए का उपयोग ध्वनि हानि माप या ध्वनि प्रवणता माप स्टोकास्टिक प्रवणता के आधार पर हानि कार्य के हेसियन मैट्रिक्स का कुशलतापूर्वक अनुमान लगाने के लिए भी किया जा सकता है। मूल एसपीएसए विधि के साथ, समस्या आयाम P के अतिरिक्त, प्रत्येक पुनरावृत्ति पर हानि माप या प्रवणता माप की केवल छोटी निश्चित संख्या की आवश्यकता होती है। स्टोकेस्टिक प्रवणता डिसेंट में संक्षिप्त चर्चा देखें।

संदर्भ

• Bhatnagar, S., Prasad, H. L., and Prashanth, L. A. (2013), Stochastic Recursive Algorithms for Optimization: Simultaneous Perturbation Methods, Springer [1].
• Hirokami, T., Maeda, Y., Tsukada, H. (2006) "Parameter estimation using simultaneous perturbation stochastic approximation", Electrical Engineering in Japan, 154 (2), 30–3 [2]
• Maryak, J.L., and Chin, D.C. (2008), "Global Random Optimization by Simultaneous Perturbation Stochastic Approximation," IEEE Transactions on Automatic Control, vol. 53, pp. 780-783.
• Spall, J. C. (1987), “A Stochastic Approximation Technique for Generating Maximum Likelihood Parameter Estimates,” Proceedings of the American Control Conference, Minneapolis, MN, June 1987, pp. 1161–1167.
• Spall, J. C. (1992), “Multivariate Stochastic Approximation Using a Simultaneous Perturbation Gradient Approximation,” IEEE Transactions on Automatic Control, vol. 37(3), pp. 332–341.
• Spall, J.C. (1998). "Overview of the Simultaneous Perturbation Method for Efficient Optimization" 2. Johns Hopkins APL Technical Digest, 19(4), 482–492.
• Spall, J.C. (2003) Introduction to Stochastic Search and Optimization: Estimation, Simulation, and Control, Wiley. ISBN 0-471-33052-3 (Chapter 7)