बेलमैन समीकरण

बेलमैन प्रवाह मानचित्र

रिचर्ड ई. बेलमैन के नाम पर एक बेलमैन समीकरण, गणितीय अनुकूलन (गणित) विधि से जुड़ी इष्टतमता के लिए एक आवश्यक परिस्थिति है जिसे गतिशील कार्यरचना के रूप में जाना जाता है। यह एक निश्चित समय पर एक निर्णय समस्या के मूल्य को कुछ प्रारंभिक विकल्पों से लाभ और उन प्रारंभिक विकल्पों से उत्पन्न शेष निर्णय समस्या के मूल्य के रूप में लिखता है। यह एक गतिशील अनुकूलन समस्या को सरल उप-समस्याओं के अनुक्रम में तोड़ता है, जैसा कि बेलमैन के "इष्टतमता का सिद्धांत निर्धारित करता है। समीकरण कुल क्रम के साथ बीजगणितीय संरचनाओं पर लागू होता है; आंशिक क्रम के साथ बीजगणितीय संरचनाओं के लिए, सामान्य बेलमैन के समीकरण का उपयोग किया जा सकता है।

बेलमैन समीकरण पहले इंजीनियरिंग नियंत्रण सिद्धांत और उपयोजित गणित में अन्य विषयों पर लागू किया गया था, और बाद में आर्थिक सिद्धांत में एक महत्वपूर्ण उपकरण बन गया; हालांकि गतिशील प्रोग्रामिंग की बुनियादी अवधारणाओं को जॉन वॉन न्यूमैन और ऑस्कर मॉर्गनस्टर्न के खेल और आर्थिक आचरण का सिद्धांत और अब्राहम के अनुक्रमिक विश्लेषण में पूर्वनिर्धारित किया गया है। 'बेलमैन समीकरण' शब्द सामान्यतः असतत-समय अनुकूलन समस्याओं से जुड़े गतिशील प्रोग्रामिंग समीकरण को संदर्भित करता है। निरंतर-समय की अनुकूलन समस्याओं में, अनुरूप समीकरण एक आंशिक अंतर समीकरण है जिसे हैमिल्टन-जैकोबी-बेलमैन समीकरण कहा जाता है।

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

गतिशील प्रोग्रामिंग में विश्लेषणात्मक अवधारणाएँ

बेलमैन समीकरण को समझने के लिए, कई अंतर्निहित अवधारणाओं को समझना आवश्यक है। सबसे पहले, किसी भी अनुकूलन समस्या का कुछ उद्देश्य होता है: यात्रा के समय को कम करना, लागत को कम करना, लाभ को अधिकतम करना, उपयोगिता को अधिकतम करना आदि। गणितीय कार्य जो इस उद्देश्य का वर्णन करता है, उसे हानि फलन कहा जाता है।

गतिशील प्रोग्रामिंग एक बहु-अवधि की योजना समस्या को अलग-अलग समय पर सरल चरणों में तोड़ देती है। इसलिए, समय के साथ निर्णय की स्थिति कैसे विकसित हो रही है, इस पर ध्यान केंद्रित करने की आवश्यकता है। सही निर्णय लेने के लिए आवश्यक वर्तमान स्थिति की जानकारी को स्थिति कहा जाता है। उदाहरण के लिए, यह निश्चित करने के लिए कि प्रत्येक बिंदु पर कितना उपभोग और व्यय करना है, लोगों को (अन्य बातों के अतिरिक्त) अपनी प्रारंभिक संपत्ति जानने की आवश्यकता होगी। इसलिए धन $(W)$ उनके स्थिति चरों में से एक होगा, परन्तु संभवतः अन्य भी होंगे।

किसी दिए गए समय पर चुने गए चर को प्रायः नियंत्रण चर (प्रोग्रामिंग) कहा जाता है। उदाहरण के लिए, उनकी वर्तमान संपत्ति को देखते हुए, लोग यह निश्चित कर सकते हैं कि अभी कितना व्यय करना है। नियंत्रण चर का चयन अब अगले स्थिति को चुनने के सामानांतर हो सकता है; सामान्यतः, अगली स्थिति वर्तमान नियंत्रण के अतिरिक्त अन्य कारकों से प्रभावित होती है। उदाहरण के लिए, सबसे सरल स्तिथि में, आज का धन (स्थिति) और खपत (नियंत्रण) कल के धन (नया स्थिति) को सटीक रूप से निर्धारित कर सकते हैं, हालांकि सामान्यतः अन्य कारक कल के धन को भी प्रभावित करेंगे।

गतिशील प्रोग्रामिंग दृष्टिकोण एक नियम खोजकर इष्टतम योजना का वर्णन करता है जो बताता है कि स्थिति के किसी भी संभावित मूल्य को देखते हुए नियंत्रण क्या होना चाहिए। उदाहरण के लिए, यदि उपभोग (c) केवल धन (W) पर निर्भर करता है, तो हम एक नियम $c(W)$ की खोज करेंगे जो उपभोग को धन के प्रकार्य के रूप में देता है। ऐसे नियम, जो स्थिति के कार्य के रूप में नियंत्रणों का निर्धारण करते हैं, नीति कार्य कहलाते हैं (बेलमैन, 1957, अध्याय III.2 देखें)।

अंत में, परिभाषा के अनुसार, इष्टतम निर्णय नियम वह है जो उद्देश्य के सर्वोत्तम संभव मूल्य को प्राप्त करता है। उदाहरण के लिए, यदि कोई आनन्द को अधिकतम करने के लिए, उपभोग को चुनता है, तो आनन्द को अधिकतम करने के लिए (यह मानते हुए कि आनन्द H को एक गणितीय कार्य द्वारा दर्शाया जा सकता है, जैसे उपयोगिता प्रकार्य और धन द्वारा परिभाषित है), तब धन का प्रत्येक स्तर आनन्द $H(W)$ के किसी उच्चतम संभव स्तर से जुड़ा होगा। स्थिति के एक फलन के रूप में लिखे गए उद्देश्य के सर्वोत्तम संभव मूल्य को मूल्य फलन कहा जाता है।

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

व्युत्पत्ति

एक गतिशील निर्णय समस्या

स्थिति को समय $t$ पर $x_{t}$ मान लीजिये। एक निर्णय के लिए जो समय 0 से प्रारम्भ होता है, हम प्रारंभिक अवस्था के रूप में $x_{0}$ लेते हैं। किसी भी समय, संभावित क्रियाओं का समूह वर्तमान स्थिति पर निर्भर करता है; हम इसे इस प्रकार $a_{t}\in \Gamma (x_{t})$लिख सकते हैं, जहां क्रिया $a_{t}$ एक या अधिक नियंत्रण चर का प्रतिनिधित्व करती है। हम यह भी मानते हैं कि $x$ स्थिति से बदलता है एक नए स्थिति $T(x,a)$ के लिए जब कार्यकलाप $a$ लिया जाता है, और यह कि कार्यकलाप $a$ करने से वर्तमान लाभ स्थिति $x$ में $F(x,a)$ है। अंत में, हम अधीरता को मान लेते हैं, जिसे छूट कारक $0<\beta <1$ द्वारा दर्शाया जाता है .

इन मान्यताओं के तहत, एक अनंत-क्षितिज निर्णय समस्या निम्न रूप लेती है:

$V(x_{0})\;=\;\max _{\left\{a_{t}\right\}_{t=0}^{\infty }}\sum _{t=0}^{\infty }\beta ^{t}F(x_{t},a_{t}),$

बाधाओं के अधीन

$a_{t}\in \Gamma (x_{t}),\;x_{t+1}=T(x_{t},a_{t}),\;\forall t=0,1,2,\dots$

ध्यान दें कि हमने संकेतन $V(x_{0})$ को परिभाषित किया है। उस इष्टतम मूल्य को निरूपित करने के लिए जिसे कल्पित बाधाओं के अधीन इस उद्देश्य फलन को अधिकतम करके प्राप्त किया जा सकता है। यह फलन मान फलन है। यह प्रारंभिक अवस्था चर $x_{0}$ का एक कार्य है, चूंकि प्राप्त करने योग्य सर्वोत्तम मूल्य प्रारंभिक स्थिति पर निर्भर करता है।

बेलमैन का इष्टतमता का सिद्धांत

गतिशील प्रोग्रामिंग पद्धति इस निर्णय समस्या को छोटे उप-समस्याओं में तोड़ देती है। बेलमैन का इष्टतमता का सिद्धांत बताता है कि यह किस प्रकार करना है:

इष्टतमता का सिद्धांत: एक इष्टतम नीति में यह गुण होता है कि प्रारंभिक स्थिति और प्रारंभिक निर्णय चाहे जो भी हों, शेष निर्णयों को पहले से उत्पन्न स्थिति के संबंध में एक इष्टतम नीति का गठन करना चाहिए। (बेलमैन, 1957, अध्याय III.3 देखें।)

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

जैसा कि इष्टतमता के सिद्धांत द्वारा सुझाया गया है, हम भविष्य के सभी निर्णयों को अलग करते हुए पहले निर्णय पर अलग से विचार करेंगे (हम नए स्थिति के साथ समय 1 से नए सिरे $x_{1}$ से प्रारंभ करेंगे)। भविष्य के निर्णयों को कोष्ठक में दाईं ओर एकत्रित करना, उपरोक्त अनंत-क्षितिज निर्णय समस्या के सामानांतर है:

$\underset{a_0}{max}\{F(x_0,a_0)+\mathrm{\beta <!--\; \beta \; -->}[\underset{{\left\{a_t\right\}}_{t=1}^{\mathrm{\infty <!--\; \infty \; -->}}}{max}\underset{t=1}{\overset{\mathrm{\infty <!--\; \infty \; -->}}{\sum <!--\; \sum \; -->}}{\mathrm{\beta <!--\; \beta \; -->}}^{t-<!--\; -\; -->1}F(x_t,a_t):a_t\in <!--\; \in \; -->\mathrm{\Gamma <!--\; \Gamma \; -->}({}_{}$