बेलमैन समीकरण: Difference between revisions
From Vigyanwiki
(text) |
(text) |
||
| Line 1: | Line 1: | ||
{{short description|Necessary condition for optimality associated with dynamic programming}} | {{short description|Necessary condition for optimality associated with dynamic programming}} | ||
[[File:Bellman flow chart.png|thumb|बेलमैन प्रवाह मानचित्र]]रिचर्ड ई. बेलमैन के नाम पर एक बेलमैन समीकरण, गणितीय [[अनुकूलन (गणित)]] विधि से जुड़ी इष्टतमता के लिए एक [[आवश्यक शर्त]] है जिसे [[गतिशील प्रोग्रामिंग|गतिशील कार्यरचना]] के रूप में जाना जाता है।<ref>{{cite book |first=Avinash K. |last=Dixit |title=Optimization in Economic Theory |publisher=Oxford University Press |edition=2nd |year=1990 |isbn=0-19-877211-4 |page=164 |url=https://books.google.com/books?id=dHrsHz0VocUC&pg=PA164 }}</ref> यह एक निश्चित समय पर एक निर्णय समस्या के मूल्य को कुछ प्रारंभिक विकल्पों से लाभ और उन प्रारंभिक विकल्पों से उत्पन्न शेष निर्णय समस्या के मूल्य के रूप में लिखता है।{{Citation needed|date=September 2017}} यह एक गतिशील अनुकूलन समस्या को सरल उप-समस्याओं के [[अनुक्रम]] में तोड़ता है, जैसा कि बेलमैन के "इष्टतमता का सिद्धांत निर्धारित करता है।<ref>{{cite book |first=Donald E. |last=Kirk |title=Optimal Control Theory: An Introduction |publisher=Prentice-Hall |year=1970 |isbn=0-13-638098-0 |page=55 |url=https://books.google.com/books?id=fCh2SAtWIdwC&pg=PA55 }}</ref> समीकरण कुल क्रम के साथ बीजगणितीय संरचनाओं पर लागू होता है; आंशिक क्रम के साथ बीजगणितीय संरचनाओं के लिए, सामान्य बेलमैन के समीकरण का उपयोग किया जा सकता है।<ref name = "Generic Dijkstra correctness">{{citation | title = Generic Dijkstra: correctness and tractability | last1 = Szcześniak | first1 = Ireneusz | last2 = Woźna-Szcześniak | first2 = Bożena | year = 2022 | arxiv = 2204.13547}}</ref> | [[File:Bellman flow chart.png|thumb|बेलमैन प्रवाह मानचित्र]]रिचर्ड ई. बेलमैन के नाम पर एक बेलमैन समीकरण, गणितीय [[अनुकूलन (गणित)]] विधि से जुड़ी इष्टतमता के लिए एक [[आवश्यक शर्त]] है जिसे [[गतिशील प्रोग्रामिंग|गतिशील कार्यरचना]] के रूप में जाना जाता है।<ref>{{cite book |first=Avinash K. |last=Dixit |title=Optimization in Economic Theory |publisher=Oxford University Press |edition=2nd |year=1990 |isbn=0-19-877211-4 |page=164 |url=https://books.google.com/books?id=dHrsHz0VocUC&pg=PA164 }}</ref> यह एक निश्चित समय पर एक निर्णय समस्या के मूल्य को कुछ प्रारंभिक विकल्पों से लाभ और उन प्रारंभिक विकल्पों से उत्पन्न शेष निर्णय समस्या के मूल्य के रूप में लिखता है।{{Citation needed|date=September 2017}} यह एक गतिशील अनुकूलन समस्या को सरल उप-समस्याओं के [[अनुक्रम]] में तोड़ता है, जैसा कि बेलमैन के "इष्टतमता का सिद्धांत निर्धारित करता है।<ref>{{cite book |first=Donald E. |last=Kirk |title=Optimal Control Theory: An Introduction |publisher=Prentice-Hall |year=1970 |isbn=0-13-638098-0 |page=55 |url=https://books.google.com/books?id=fCh2SAtWIdwC&pg=PA55 }}</ref> समीकरण कुल क्रम के साथ बीजगणितीय संरचनाओं पर लागू होता है; आंशिक क्रम के साथ बीजगणितीय संरचनाओं के लिए, सामान्य बेलमैन के समीकरण का उपयोग किया जा सकता है।<ref name = "Generic Dijkstra correctness">{{citation | title = Generic Dijkstra: correctness and tractability | last1 = Szcześniak | first1 = Ireneusz | last2 = Woźna-Szcześniak | first2 = Bożena | year = 2022 | arxiv = 2204.13547}}</ref> | ||
बेलमैन समीकरण पहले इंजीनियरिंग [[नियंत्रण सिद्धांत]] और उपयोजित गणित में अन्य विषयों पर लागू किया गया था, और बाद में [[आर्थिक सिद्धांत]] में एक महत्वपूर्ण उपकरण बन गया; हालांकि गतिशील | बेलमैन समीकरण पहले इंजीनियरिंग [[नियंत्रण सिद्धांत]] और उपयोजित गणित में अन्य विषयों पर लागू किया गया था, और बाद में [[आर्थिक सिद्धांत]] में एक महत्वपूर्ण उपकरण बन गया; हालांकि गतिशील क्रमादेशन की बुनियादी अवधारणाओं को [[जॉन वॉन न्यूमैन]] और [[ऑस्कर मॉर्गनस्टर्न]] के [[गेम और आर्थिक आचरण का सिद्धांत|खेल और आर्थिक आचरण का सिद्धांत]] और [[अब्राहम का जन्म हुआ|अब्राहम]] के [[अनुक्रमिक विश्लेषण]] में पूर्वनिर्धारित किया गया है।{{Citation needed|date=September 2017}} 'बेलमैन समीकरण' शब्द सामान्यतः असतत-समय अनुकूलन समस्याओं से जुड़े गतिशील क्रमादेशन समीकरण को संदर्भित करता है।<ref>{{harvnb|Kirk|1970|p=[https://books.google.com/books?id=fCh2SAtWIdwC&pg=PA70 70]}}</ref> निरंतर-समय की अनुकूलन समस्याओं में, अनुरूप समीकरण एक आंशिक अंतर समीकरण है जिसे हैमिल्टन-जैकोबी-बेलमैन समीकरण कहा जाता है।<ref>{{cite book |first1=Morton I. |last1=Kamien |author-link=Morton Kamien |first2=Nancy L. |last2=Schwartz |title=Dynamic Optimization: The Calculus of Variations and Optimal Control in Economics and Management |location=Amsterdam |publisher=Elsevier |edition=Second |year=1991 |isbn=0-444-01609-0 |page=261 |url=https://books.google.com/books?id=liLCAgAAQBAJ&pg=PA261 }}</ref><ref>{{harvnb|Kirk|1970|p=[https://books.google.com/books?id=fCh2SAtWIdwC&pg=PA88 88]}}</ref> | ||
असतत समय में उपयुक्त बेलमैन समीकरण का विश्लेषण करके किसी भी बहु-स्तरीय अनुकूलन समस्या को हल किया जा सकता है। नई स्थिति चर को प्रस्तुत करके उपयुक्त बेलमैन समीकरण पाया जा सकता है।<ref>{{cite journal |last1=Jones |first1=Morgan |last2=Peet |first2=Matthew M. |title=Extensions of the Dynamic Programming Framework: Battery Scheduling, Demand Charges, and Renewable Integration |journal=IEEE Transactions on Automatic Control |date=2020 |volume=66 |issue=4 |pages=1602–1617 |doi=10.1109/TAC.2020.3002235|arxiv=1812.00792 |s2cid=119622206 }}</ref> हालाँकि, परिणामी संवर्धित-स्थिति बहु-स्तरीय अनुकूलन समस्या में मूल बहु-स्तरीय अनुकूलन समस्या की तुलना में एक उच्च आयामी स्थिति स्थान है - एक ऐसा विषय जो संभावित रूप से संवर्धित समस्या को "आयामीता के अभिशाप" के कारण असाध्य बना सकता है। वैकल्पिक रूप से, यह दिखाया गया है कि यदि बहु-चरणी इष्टमीकरण समस्या का लागत प्रकार्य एक पिछड़े वियोज्य संरचना को संतुष्ट करता है, तो उपयुक्त बेलमैन समीकरण स्थिति वृद्धि के बिना पाया जा सकता है।<ref>{{cite journal |last1=Jones |first1=Morgan |last2=Peet |first2=Matthew M. |title=A Generalization of Bellman's Equation with Application to Path Planning, Obstacle Avoidance and Invariant Set Estimation |journal=Automatica |date=2021 |volume=127 |pages=109510 |doi=10.1016/j.automatica.2021.109510 |url=https://www.sciencedirect.com/science/article/pii/S0005109821000303 |arxiv=2006.08175 |s2cid=222350370 }}</ref> | असतत समय में उपयुक्त बेलमैन समीकरण का विश्लेषण करके किसी भी बहु-स्तरीय अनुकूलन समस्या को हल किया जा सकता है। नई स्थिति चर को प्रस्तुत करके उपयुक्त बेलमैन समीकरण पाया जा सकता है।<ref>{{cite journal |last1=Jones |first1=Morgan |last2=Peet |first2=Matthew M. |title=Extensions of the Dynamic Programming Framework: Battery Scheduling, Demand Charges, and Renewable Integration |journal=IEEE Transactions on Automatic Control |date=2020 |volume=66 |issue=4 |pages=1602–1617 |doi=10.1109/TAC.2020.3002235|arxiv=1812.00792 |s2cid=119622206 }}</ref> हालाँकि, परिणामी संवर्धित-स्थिति बहु-स्तरीय अनुकूलन समस्या में मूल बहु-स्तरीय अनुकूलन समस्या की तुलना में एक उच्च आयामी स्थिति स्थान है - एक ऐसा विषय जो संभावित रूप से संवर्धित समस्या को "आयामीता के अभिशाप" के कारण असाध्य बना सकता है। वैकल्पिक रूप से, यह दिखाया गया है कि यदि बहु-चरणी इष्टमीकरण समस्या का लागत प्रकार्य एक पिछड़े वियोज्य संरचना को संतुष्ट करता है, तो उपयुक्त बेलमैन समीकरण स्थिति वृद्धि के बिना पाया जा सकता है।<ref>{{cite journal |last1=Jones |first1=Morgan |last2=Peet |first2=Matthew M. |title=A Generalization of Bellman's Equation with Application to Path Planning, Obstacle Avoidance and Invariant Set Estimation |journal=Automatica |date=2021 |volume=127 |pages=109510 |doi=10.1016/j.automatica.2021.109510 |url=https://www.sciencedirect.com/science/article/pii/S0005109821000303 |arxiv=2006.08175 |s2cid=222350370 }}</ref> | ||
| Line 8: | Line 7: | ||
== गतिशील | == गतिशील क्रमादेशन में विश्लेषणात्मक अवधारणाएँ == | ||
बेलमैन समीकरण को समझने के लिए, कई अंतर्निहित अवधारणाओं को समझना आवश्यक है। सबसे पहले, किसी भी अनुकूलन समस्या का कुछ उद्देश्य होता है: यात्रा के समय को कम करना, लागत को कम करना, लाभ को अधिकतम करना, उपयोगिता को अधिकतम करना आदि। गणितीय कार्य जो इस उद्देश्य का वर्णन करता है, उसे हानि फलन कहा जाता है। | बेलमैन समीकरण को समझने के लिए, कई अंतर्निहित अवधारणाओं को समझना आवश्यक है। सबसे पहले, किसी भी अनुकूलन समस्या का कुछ उद्देश्य होता है: यात्रा के समय को कम करना, लागत को कम करना, लाभ को अधिकतम करना, उपयोगिता को अधिकतम करना आदि। गणितीय कार्य जो इस उद्देश्य का वर्णन करता है, उसे हानि फलन कहा जाता है। | ||
गतिशील | गतिशील क्रमादेशन एक बहु-अवधि की योजना समस्या को अलग-अलग समय पर सरल चरणों में तोड़ देती है। इसलिए, समय के साथ निर्णय की स्थिति कैसे विकसित हो रही है, इस पर ध्यान देने की आवश्यकता है। सही निर्णय लेने के लिए आवश्यक वर्तमान स्थिति की जानकारी को स्थिति कहा जाता है।<ref name=BellmanDP>{{cite book |last=Bellman |first=R.E. |orig-year=1957 |title=Dynamic Programming |year=2003 |publisher=Dover |isbn=0-486-42809-5}}</ref><ref name=dreyfus>{{cite journal |first=S. |last=Dreyfus |year=2002 |title=Richard Bellman on the birth of dynamic programming |journal=Operations Research |volume=50 |issue=1 |pages=48–51 |doi=10.1287/opre.50.1.48.17791|doi-access=free }}</ref> उदाहरण के लिए, यह निश्चित करने के लिए कि प्रत्येक बिंदु पर कितना उपभोग और व्यय करना है, लोगों को (अन्य बातों के अतिरिक्त) अपनी प्रारंभिक संपत्ति जानने की आवश्यकता होगी। इसलिए धन <math>(W)</math> उनके स्थिति चरों में से एक होगा, परन्तु संभवतः अन्य भी होंगे। | ||
किसी दिए गए समय पर चुने गए चर को प्रायः [[नियंत्रण चर (प्रोग्रामिंग)]] कहा जाता है। उदाहरण के लिए, उनकी वर्तमान संपत्ति को देखते हुए, लोग यह तय कर सकते हैं कि अभी कितना व्यय करना है। नियंत्रण चर का चयन अब अगले स्थिति को चुनने के बराबर हो सकता है; सामान्यतः, अगली स्थिति वर्तमान नियंत्रण के अतिरिक्त अन्य कारकों से प्रभावित होती है। उदाहरण के लिए, सबसे सरल स्तिथि में, आज का धन (स्थिति) और खपत (नियंत्रण) कल के धन (नया स्थिति) को सटीक रूप से निर्धारित कर सकते हैं, हालांकि सामान्यतः अन्य कारक कल के धन को भी प्रभावित करेंगे। | किसी दिए गए समय पर चुने गए चर को प्रायः [[नियंत्रण चर (प्रोग्रामिंग)|नियंत्रण चर (क्रमादेशन)]] कहा जाता है। उदाहरण के लिए, उनकी वर्तमान संपत्ति को देखते हुए, लोग यह तय कर सकते हैं कि अभी कितना व्यय करना है। नियंत्रण चर का चयन अब अगले स्थिति को चुनने के बराबर हो सकता है; सामान्यतः, अगली स्थिति वर्तमान नियंत्रण के अतिरिक्त अन्य कारकों से प्रभावित होती है। उदाहरण के लिए, सबसे सरल स्तिथि में, आज का धन (स्थिति) और खपत (नियंत्रण) कल के धन (नया स्थिति) को सटीक रूप से निर्धारित कर सकते हैं, हालांकि सामान्यतः अन्य कारक कल के धन को भी प्रभावित करेंगे। | ||
गतिशील क्रमादेशन दृष्टिकोण एक नियम खोजकर इष्टतम योजना का वर्णन करता है जो बताता है कि स्थिति के किसी भी संभावित मूल्य को देखते हुए नियंत्रण क्या होना चाहिए। उदाहरण के लिए, यदि उपभोग (c) केवल धन (W) पर निर्भर करता है, तो हम एक नियम <math>c(W)</math> की खोज करेंगे जो उपभोग को धन के प्रकार्य के रूप में देता है। ऐसे नियम, जो स्थिति के कार्य के रूप में नियंत्रणों का निर्धारण करते हैं, नीति कार्य कहलाते हैं (बेलमैन, 1957, अध्याय III.2 देखें)।<ref name=BellmanDP /> | |||
अंत में, परिभाषा के अनुसार, इष्टतम निर्णय नियम वह है जो उद्देश्य के सर्वोत्तम संभव मूल्य को प्राप्त करता है। उदाहरण के लिए, यदि कोई खुशी को अधिकतम करने के लिए, उपभोग को चुनता है, तो खुशी को अधिकतम करने के लिए (यह मानते हुए कि खुशी | अंत में, परिभाषा के अनुसार, इष्टतम निर्णय नियम वह है जो उद्देश्य के सर्वोत्तम संभव मूल्य को प्राप्त करता है। उदाहरण के लिए, यदि कोई खुशी को अधिकतम करने के लिए, उपभोग को चुनता है, तो खुशी को अधिकतम करने के लिए (यह मानते हुए कि खुशी H को एक गणितीय कार्य द्वारा दर्शाया जा सकता है, जैसे [[उपयोगिता]] प्रकार्य और धन द्वारा परिभाषित है), तब धन का प्रत्येक स्तर खुशी <math>H(W)</math> के किसी उच्चतम संभव स्तर से जुड़ा होगा। स्थिति के एक फलन के रूप में लिखे गए उद्देश्य के सर्वोत्तम संभव मूल्य को मूल्य फलन कहा जाता है। | ||
बेलमैन ने दिखाया कि असतत समय में एक गतिशील अनुकूलन (गणित) समस्या को एक पुनरावृत्ति में कहा जा सकता है, चरण-दर-चरण रूप जिसे [[पीछे की ओर प्रेरण]] के रूप में जाना जाता है, | बेलमैन ने दिखाया कि असतत समय में एक गतिशील अनुकूलन (गणित) समस्या को एक पुनरावृत्ति में कहा जा सकता है, चरण-दर-चरण रूप जिसे एक अवधि में मूल्य फलन और अगली अवधि में मूल्य फलन के बीच संबंध लिखकर [[पीछे की ओर प्रेरण|पश्च प्रेरण]] के रूप में जाना जाता है, इन दो मूल्य कार्यों के बीच संबंध को बेलमैन समीकरण कहा जाता है। इस दृष्टिकोण में, अंतिम समय अवधि में इष्टतम नीति उस समय स्थिति चर के मूल्य के एक फलन के रूप में अग्रिम रूप से निर्दिष्ट की जाती है, और इस प्रकार उद्देश्य फलन के परिणामी इष्टतम मूल्य को स्थिति चर के उस मूल्य के संदर्भ में व्यक्त किया जाता है। इसके बाद, अगली-से-अंतिम अवधि के अनुकूलन में उस अवधि की अवधि-विशिष्ट उद्देश्य फलन और भविष्य के उद्देश्य फलन के इष्टतम मूल्य को अधिकतम करना सम्मिलित है, जो उस अवधि की इष्टतम नीति को स्थिति चर के मूल्य पर निर्भर करता है, जैसा कि अगले- से अंतिम अवधि का निर्णय निर्भर करता है।{{clarify |date=January 2020 |reason=comment from reader: the last two sentences are too long and ambiguous/confusing}} यह तर्क समय-समय पर पुनरावर्ती रूप से जारी रहता है, जब तक कि पहली अवधि के निर्णय नियम को प्रारंभिक स्थिति चर मूल्य के एक फलन के रूप में, पहली-अवधि-विशिष्ट उद्देश्य फलन के योग और दूसरी अवधि के मूल्य फलन के मूल्य को अनुकूलित करके, प्राप्त नहीं किया जाता है। जो भविष्य की सभी अवधियों के लिए मूल्य देता है। इस प्रकार, प्रत्येक अवधि का निर्णय स्पष्ट रूप से यह स्वीकार करते हुए किया जाता है कि भविष्य के सभी निर्णय इष्टतम रूप से किए जाएंगे। | ||
== व्युत्पत्ति == | == व्युत्पत्ति == | ||
=== एक गतिशील निर्णय समस्या === | === एक गतिशील निर्णय समस्या === | ||
स्थिति को समय | स्थिति को समय <math>t</math> पर <math>x_t</math> मान लीजिये। एक निर्णय के लिए जो समय 0 से प्रारम्भ होता है, हम प्रारंभिक अवस्था के रूप में <math>x_0</math> लेते हैं। किसी भी समय, संभावित क्रियाओं का समूह वर्तमान स्थिति पर निर्भर करता है; हम इसे इस प्रकार <math> a_{t} \in \Gamma (x_t)</math>लिख सकते हैं, जहां क्रिया <math>a_t</math> एक या अधिक नियंत्रण चर का प्रतिनिधित्व करती है। हम यह भी मानते हैं कि <math>x</math> स्थिति से बदलता है एक नए स्थिति <math>T(x,a)</math> के लिए जब कार्रवाई <math>a</math> लिया जाता है, और यह कि कार्रवाई <math>a</math> करने से वर्तमान लाभ स्थिति <math>x</math> में <math>F(x,a)</math> है। अंत में, हम अधीरता को मान लेते हैं, जिसे [[छूट कारक]] <math>0<\beta<1</math> द्वारा दर्शाया जाता है . | ||
इन मान्यताओं के तहत, एक अनंत-क्षितिज निर्णय समस्या निम्न रूप लेती है: | इन मान्यताओं के तहत, एक अनंत-क्षितिज निर्णय समस्या निम्न रूप लेती है: | ||
| Line 32: | Line 31: | ||
:<math> a_{t} \in \Gamma (x_t), \; x_{t+1}=T(x_t,a_t), \; \forall t = 0, 1, 2, \dots </math> | :<math> a_{t} \in \Gamma (x_t), \; x_{t+1}=T(x_t,a_t), \; \forall t = 0, 1, 2, \dots </math> | ||
ध्यान दें कि हमने संकेतन | ध्यान दें कि हमने संकेतन <math>V(x_0)</math> को परिभाषित किया है। उस इष्टतम मूल्य को निरूपित करने के लिए जिसे कल्पित बाधाओं के अधीन इस उद्देश्य फलन को अधिकतम करके प्राप्त किया जा सकता है। यह फलन मान फलन है। यह प्रारंभिक अवस्था चर <math>x_0</math> का एक कार्य है, चूंकि प्राप्त करने योग्य सर्वोत्तम मूल्य प्रारंभिक स्थिति पर निर्भर करता है। | ||
=== बेलमैन का इष्टतमता का सिद्धांत === | === बेलमैन का इष्टतमता का सिद्धांत === | ||
गतिशील | गतिशील क्रमादेशन पद्धति इस निर्णय समस्या को छोटे उप-समस्याओं में तोड़ देती है। बेलमैन का इष्टतमता का सिद्धांत बताता है कि यह कैसे करना है:<blockquote>इष्टतमता का सिद्धांत: एक इष्टतम नीति में यह गुण होता है कि प्रारंभिक स्थिति और प्रारंभिक निर्णय चाहे जो भी हों, शेष निर्णयों को पहले से उत्पन्न स्थिति के संबंध में एक इष्टतम नीति का गठन करना चाहिए। (बेलमैन, 1957, अध्याय III.3 देखें।)<ref name="BellmanDP" /><ref name="dreyfus" /><ref name="BellmanTheory">{{cite journal |first=R |last=Bellman |pmc=1063639 |title=On the Theory of Dynamic Programming |journal=Proc Natl Acad Sci U S A |date=August 1952 |volume=38 |issue=8 |pages=716–9 |pmid=16589166 |doi=10.1073/pnas.38.8.716|bibcode=1952PNAS...38..716B |doi-access=free }}</ref></blockquote>कंप्यूटर विज्ञान में, एक समस्या जिसे इस तरह से तोड़ा जा सकता है, उसे [[इष्टतम उपसंरचना]] कहा जाता है। गतिशील [[खेल सिद्धांत]] के संदर्भ में, यह सिद्धांत उपखेल पूर्ण संतुलन की अवधारणा के अनुरूप है, हालांकि इस स्तिथि में एक इष्टतम नीति क्या है जो निर्णयकर्ता के विरोधियों द्वारा उनके दृष्टिकोण से समान इष्टतम नीतियों को चुनने पर निर्भर है। | ||
कंप्यूटर विज्ञान में, एक समस्या जिसे इस तरह से तोड़ा जा सकता है, उसे [[इष्टतम उपसंरचना]] कहा जाता है। गतिशील [[खेल सिद्धांत]] के संदर्भ में, यह सिद्धांत | |||
जैसा कि इष्टतमता के सिद्धांत द्वारा सुझाया गया है, हम भविष्य के सभी निर्णयों को अलग करते हुए पहले निर्णय पर अलग से विचार करेंगे (हम नए स्थिति के साथ समय 1 से नए सिरे | जैसा कि इष्टतमता के सिद्धांत द्वारा सुझाया गया है, हम भविष्य के सभी निर्णयों को अलग करते हुए पहले निर्णय पर अलग से विचार करेंगे (हम नए स्थिति के साथ समय 1 से नए सिरे <math>x_1 </math> से प्रारंभ करेंगे)। भविष्य के निर्णयों को कोष्ठक में दाईं ओर एकत्रित करना, उपरोक्त अनंत-क्षितिज निर्णय समस्या के बराबर है:{{Clarify|date=September 2017}} | ||
:<math> \max_{ a_0 } \left \{ F(x_0,a_0) | :<math> \max_{ a_0 } \left \{ F(x_0,a_0) | ||
+ \beta \left[ \max_{ \left \{ a_{t} \right \}_{t=1}^{\infty} } | + \beta \left[ \max_{ \left \{ a_{t} \right \}_{t=1}^{\infty} } | ||
| Line 46: | Line 44: | ||
:<math> a_0 \in \Gamma (x_0), \; x_1=T(x_0,a_0). </math> | :<math> a_0 \in \Gamma (x_0), \; x_1=T(x_0,a_0). </math> | ||
यहां हम | यहां हम <math>a_0</math> चुन रहे हैं, यह जानते हुए कि हमारी पसंद समय 1 स्थिति का कारण <math>x_1=T(x_0,a_0)</math> बनेगी। वह नया स्थिति समय 1 से निर्णय समस्या को प्रभावित करेगा। संपूर्ण भविष्य की निर्णय समस्या दाईं ओर वर्ग कोष्ठक के अंदर दिखाई देती है। | ||
=== बेलमैन समीकरण === | === बेलमैन समीकरण === | ||
अभी तक ऐसा लगता है कि हमने आज के निर्णय को भविष्य के निर्णयों से अलग करके समस्या को और अधिक कुरूप बना दिया है। लेकिन हम यह देखकर सरल कर सकते हैं कि दाईं ओर वर्ग कोष्ठक के अंदर जो है वह समय 1 निर्णय समस्या का मान है, जो | अभी तक ऐसा लगता है कि हमने आज के निर्णय को भविष्य के निर्णयों से अलग करके समस्या को और अधिक कुरूप बना दिया है। लेकिन हम यह देखकर सरल कर सकते हैं कि दाईं ओर वर्ग कोष्ठक के अंदर जो है वह समय 1 निर्णय समस्या का मान है, जो <math>x_1=T(x_0,a_0)</math> स्थिति से प्रारम्भ होता है। | ||
इसलिए, हम समस्या को मान | इसलिए, हम समस्या को मान फलन की पुनरावर्तन परिभाषा के रूप में फिर से लिख सकते हैं: | ||
:<math>V(x_0) = \max_{ a_0 } \{ F(x_0,a_0) + \beta V(x_1) \} </math>, बाधाओं के अधीन: <math> a_0 \in \Gamma (x_0), \; x_1=T(x_0,a_0). </math> | :<math>V(x_0) = \max_{ a_0 } \{ F(x_0,a_0) + \beta V(x_1) \} </math>, बाधाओं के अधीन: <math> a_0 \in \Gamma (x_0), \; x_1=T(x_0,a_0). </math> | ||
यह बेलमैन समीकरण है। इसे और भी सरल बनाया जा सकता है यदि हम | यह बेलमैन समीकरण है। इसे और भी सरल बनाया जा सकता है यदि हम काल पादाक्षर छोड़ दें और अगले स्थिति के मान में प्रचार करें: | ||
:<math>V(x) = \max_{a \in \Gamma (x) } \{ F(x,a) + \beta V(T(x,a)) \}.</math> | :<math>V(x) = \max_{a \in \Gamma (x) } \{ F(x,a) + \beta V(T(x,a)) \}.</math> | ||
बेलमैन समीकरण को एक [[कार्यात्मक समीकरण]] के रूप में वर्गीकृत किया गया है, क्योंकि इसे हल करने का अर्थ अज्ञात | बेलमैन समीकरण को एक [[कार्यात्मक समीकरण]] के रूप में वर्गीकृत किया गया है, क्योंकि इसे हल करने का अर्थ अज्ञात फलन <math>V</math> को खोजना है, जो कि परिमाण फलन है। याद रखें कि मूल्य फलन स्थिति के एक फलन के रूप में, उद्देश्य के सर्वोत्तम संभव मूल्य का वर्णन <math>x</math> करता है। मान फलन की गणना करके, हम <math>a(x)</math> फलन भी ज्ञात करेंगे, जो स्थिति के कार्य के रूप में इष्टतम क्रिया का वर्णन करता है; इसे नीति कार्य कहा जाता है। | ||
=== एक प्रसंभाव्य समस्या में === | |||
{{See also|मार्कोव निर्णय प्रक्रिया}} | |||
नियतात्मक समायोजन में, उपरोक्त [[इष्टतम नियंत्रण]] समस्या से निपटने के लिए गतिशील क्रमादेशन के अतिरिक्त अन्य तकनीकों का उपयोग किया जा सकता है। हालांकि, बेलमैन समीकरण प्रायः प्रसंभाव्य इष्टतम नियंत्रण समस्याओं को हल करने का सबसे सुविधाजनक तरीका होता है। | |||
नियतात्मक | |||
अर्थशास्त्र से एक विशिष्ट उदाहरण के लिए, प्रारंभिक धन | अर्थशास्त्र से एक विशिष्ट उदाहरण के लिए, प्रारंभिक धन अक्षयनिधि <math>{\color{Red}a_0}</math> के साथ <math>0</math> अवधि में असीम रूप से रहने वाले उपभोक्ता पर विचार करें। उनके पास तात्कालिक उपयोगिता कार्य <math>u(c)</math> है जहाँ <math>c</math> की दर से खपत और अगली अवधि की उपयोगिता को <math>0< \beta<1 </math> दर्शाता है। मान लीजिए कि अवधिकाल <math>t</math> में जो उपभुक्त नहीं किया जाता है वह ब्याज दर <math>r</math> के साथ अगली अवधि के लिए आगे बढ़ता है। तब उपभोक्ता की उपयोगिता अधिकतम करने की समस्या उपभोग योजना <math>\{{\color{OliveGreen}c_t}\}</math> का चयन करना है। वह निम्न हल करता है | ||
:<math>\max \sum_{t=0} ^{\infty} \beta^t u ({\color{OliveGreen}c_t})</math> | :<math>\max \sum_{t=0} ^{\infty} \beta^t u ({\color{OliveGreen}c_t})</math> | ||
के अधीन | |||
:<math>{\color{Red}a_{t+1}} = (1 + r) ({\color{Red}a_t} - {\color{OliveGreen}c_t}), \; {\color{OliveGreen}c_t} \geq 0,</math> | :<math>{\color{Red}a_{t+1}} = (1 + r) ({\color{Red}a_t} - {\color{OliveGreen}c_t}), \; {\color{OliveGreen}c_t} \geq 0,</math> | ||
| Line 73: | Line 73: | ||
:<math>\lim_{t \rightarrow \infty} {\color{Red}a_t} \geq 0.</math> | :<math>\lim_{t \rightarrow \infty} {\color{Red}a_t} \geq 0.</math> | ||
पहली बाधा पूंजी संचय/समस्या द्वारा निर्दिष्ट गति का नियम है, जबकि दूसरी बाधा एक [[ट्रांसवर्सलिटी (गणित)]] है कि उपभोक्ता अपने जीवन के अंत में ऋण नहीं लेता है। बेलमैन समीकरण है | पहली बाधा पूंजी संचय/समस्या द्वारा निर्दिष्ट गति का नियम है, जबकि दूसरी बाधा एक [[ट्रांसवर्सलिटी (गणित)|अनुप्रस्थता प्रतिबंध]] है कि उपभोक्ता अपने जीवन के अंत में ऋण नहीं लेता है। बेलमैन समीकरण निम्न है | ||
:<math>V(a) = \max_{ 0 \leq c \leq a } \{ u(c) + \beta V((1+r) (a - c)) \},</math> | :<math>V(a) = \max_{ 0 \leq c \leq a } \{ u(c) + \beta V((1+r) (a - c)) \},</math> | ||
वैकल्पिक रूप से, कोई अनुक्रम समस्या का सीधे उपयोग कर सकता है, उदाहरण के लिए, [[हैमिल्टनियन (नियंत्रण सिद्धांत)]]। | वैकल्पिक रूप से, कोई अनुक्रम समस्या का सीधे उपयोग कर सकता है, उदाहरण के लिए, [[हैमिल्टनियन (नियंत्रण सिद्धांत)|हैमिल्टनियन समीकरण]]। | ||
अब, यदि ब्याज दर समय-समय पर बदलती रहती है, तो उपभोक्ता को | अब, यदि ब्याज दर समय-समय पर बदलती रहती है, तो उपभोक्ता को प्रसंभाव्य अनुकूलन समस्या का सामना करना पड़ता है। बता दें कि ब्याज r प्रायिकता संक्रमण फलन के साथ एक [[मार्कोव प्रक्रिया]] <math>Q(r, d\mu_r)</math> का पालन करता है जहाँ <math>d\mu_r</math> यदि वर्तमान ब्याज दर है तो अगली अवधि में ब्याज दर के वितरण को नियंत्रित करने वाले [[संभाव्यता माप]] <math>r</math> को दर्शाता है। इस प्रतिरूप में उपभोक्ता वर्तमान अवधि की ब्याज दर की घोषणा के बाद अपनी वर्तमान अवधि की खपत निश्चित करता है। | ||
केवल एक अनुक्रम | केवल एक अनुक्रम <math>\{{\color{OliveGreen}c_t}\}</math> चुनने के स्थान पर, उपभोक्ता को अब एक क्रम <math>\{{\color{OliveGreen}c_t}\}</math> चुनना होगा, a के हर संभव प्रत्यक्षीकरण <math>\{r_t\}</math> के लिए, इस तरह से कि उनकी आजीवन अपेक्षित उपयोगिता अधिकतम हो: | ||
:<math>\max_{ \left \{ c_{t} \right \}_{t=0}^{\infty} } \mathbb{E}\bigg( \sum_{t=0} ^{\infty} \beta^t u ({\color{OliveGreen}c_t}) \bigg).</math> | :<math>\max_{ \left \{ c_{t} \right \}_{t=0}^{\infty} } \mathbb{E}\bigg( \sum_{t=0} ^{\infty} \beta^t u ({\color{OliveGreen}c_t}) \bigg).</math> | ||
अपेक्षा <math>\mathbb{E}</math> | अपेक्षा <math>\mathbb{E}</math> r's के अनुक्रमों पर Q द्वारा दिए गए उचित संभाव्यता माप के संबंध में लिया जाता है। क्योंकि r एक मार्कोव प्रक्रिया द्वारा नियंत्रित होता है, गतिशील क्रमादेशन समस्या को महत्वपूर्ण रूप से सरल करती है। तब बेलमैन समीकरण सरल है: | ||
:<math>V(a, r) = \max_{ 0 \leq c \leq a } \{ u(c) + \beta \int V((1+r) (a - c), r') Q(r, d\mu_r) \} .</math> | :<math>V(a, r) = \max_{ 0 \leq c \leq a } \{ u(c) + \beta \int V((1+r) (a - c), r') Q(r, d\mu_r) \} .</math> | ||
कुछ उचित धारणा के तहत, परिणामी इष्टतम नीति कार्य g(a,r) मापने योग्य है। | कुछ उचित धारणा के तहत, परिणामी इष्टतम नीति कार्य g(a,r) मापने योग्य है। | ||
मार्कोवियन झटकों के साथ एक सामान्य | मार्कोवियन झटकों के साथ एक सामान्य प्रसंभाव्य अनुक्रमिक अनुकूलन समस्या के लिए और जहां अभिकर्ता को अपने निर्णय पूर्व-पट्रवाहक का प्रतिमुखन करना पड़ता है, बेलमैन समीकरण एक समान रूप लेता है | ||
:<math>V(x, z) = \max_{c \in \Gamma(x,z)} \{F(x, c, z) + \beta \int V( T(x,c), z') d\mu_z(z')\}. </math> | :<math>V(x, z) = \max_{c \in \Gamma(x,z)} \{F(x, c, z) + \beta \int V( T(x,c), z') d\mu_z(z')\}. </math> | ||
| Line 95: | |||