क्लासिक गणित की समस्या वास्तविक दुनिया में ही प्रकट होती है

एक सौ साल पहले, महान गणितज्ञ डेविड हिल्बर्ट ने शुद्ध गणित के क्षेत्र से एक शोध प्रश्न पूछा था। ऑप्टिमाइज़ेशन थ्योरी में हालिया घटनाक्रम हिल्बर्ट के काम को रोबेम्बाइल्स की दुनिया में लाते हैं

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

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

"एक पूर्ण, 100% प्रदर्शनकारी गारंटी है कि आपका सिस्टम" टकराव से बच सकता है, प्रिंसटन से स्नातक छात्र जोर्जिना हॉल ने कहा, जिन्होंने इस काम में अहमदी के साथ सहयोग किया।

अमीर अली अहमदी, प्रिंसटन से प्रो

वारंटी को एक अप्रत्याशित स्थान पर लिया जाता है - एक गणितीय समस्या में जिसे " वर्गों का योग " के रूप में जाना जाता है। इसे 1900 में महान गणितज्ञ डेविड हिल्बर्ट ने डाला था। उन्होंने पूछा कि क्या कुछ समीकरणों को हमेशा दो अलग-अलग शब्दों के योग के रूप में व्यक्त किया जा सकता है, जिनमें से प्रत्येक को चुकता किया गया है।

गणितज्ञों ने कुछ दशकों बाद हिल्बर्ट के प्रश्न का उत्तर दिया। फिर, लगभग 90 साल बाद, कंप्यूटर वैज्ञानिकों और इंजीनियरों ने पाया कि यह गणितीय संपत्ति - वर्गों के योग के संदर्भ में एक समीकरण की अभिव्यक्ति - कई वास्तविक समस्याओं को हल करने में मदद करती है जिन्हें वे हल करना चाहते हैं।

अहमदी ने कहा, "19 वीं शताब्दी के बहुत से शास्त्रीय गणित का उपयोग मैं जो भी करता हूं, उसमें बहुत ही आधुनिक कम्प्यूटेशनल गणित के साथ किया जाता है।"

हालांकि, जैसे ही शोधकर्ताओं ने महसूस किया कि वर्गों का योग कई प्रकार के सवालों के जवाब देने में मदद कर सकता है, वे इस दृष्टिकोण को लागू करने में समस्याओं में भाग गए। नया काम इस तरह की सबसे बड़ी समस्याओं में से एक को समाप्त करता है, जो पुराने गणितीय प्रश्न को हमारे समय के कुछ सबसे महत्वपूर्ण तकनीकी मुद्दों को हल करने के लिए मजबूर करता है।

सकारात्मक गारंटी

इसका क्या मतलब है कि एक निश्चित मात्रा वर्गों का योग है? संख्या १३ लें। यह दो वर्गों का योग है - २ ^२ और ३ ^२ । ३४ की संख्या ३ ^२ और ५ ^२ का योग है।

संख्याओं के बजाय, हिल्बर्ट के सवाल - 23 वीं समस्याओं में से 17 वीं समस्याएं जो उन्होंने 20 वीं शताब्दी की सुबह में प्रस्तावित कीं - 5x ² + 16x + 13. जैसे बहुपदों के साथ सौदे किए गए। इस तरह के बहुपदों को कभी-कभी वर्गों के योग के रूप में भी दर्शाया जा सकता है। उदाहरण के लिए, 5x ² + 16x + 13 को (x + 2) ² + (2x + 3) ^{2 के} रूप में फिर से लिखा जा सकता है।

जब एक अभिव्यक्ति वर्गों का योग होता है, तो आप जानते हैं कि यह हमेशा सकारात्मक होता है (सभी [वास्तविक] संख्या वाले वर्ग एक सकारात्मक संख्या या शून्य देते हैं, और सकारात्मक संख्याओं का योग सकारात्मक होता है)। हिल्बर्ट जानना चाहते थे कि क्या यह दूसरे तरीके से काम करता है: क्या सभी गैर-नकारात्मक बहुपदों को तर्कसंगत कार्यों के वर्गों के योग के रूप में व्यक्त किया जा सकता है। 1927 में, गणितज्ञ एमिल आर्टिन ने साबित किया कि हिल्बर्ट की परिकल्पना सच थी।

यह संबंध काफी उपयोगी है। यदि आपको एक जटिल बहुपद दिया जाता है, तो दर्जनों चर उच्चतम डिग्री तक उठाए जाते हैं, यह तुरंत निर्धारित करना काफी मुश्किल है कि क्या यह हमेशा गैर-नकारात्मक है। “कुछ बहुपद स्पष्ट रूप से गैर-नकारात्मक हैं, अन्य नहीं हैं। अहमदी ने कहा कि गैर-नकारात्मकता के लिए उनका परीक्षण करना कठिन है।

लेकिन जैसे ही आप दिखाते हैं कि इस बहुपद को वर्गों के योग के रूप में व्यक्त किया जा सकता है, तो गैर-नकारात्मकता बस इसका एक परिणाम होगी। मैसाचुसेट्स इंस्टीट्यूट ऑफ टेक्नोलॉजी के एक कंप्यूटर वैज्ञानिक और इंजीनियर पाब्लो पैरिलो ने कहा, "वर्गों का योग आपको सकारात्मकता का एक सुंदर प्रमाण पत्र देता है, जो अनुप्रयोग जगत में वर्गों के योग के मुद्दे को खींचने में शामिल था।"

यह जानते हुए कि एक विशेष बहुपद हमेशा गैर-नकारात्मक होता है, गणितीय तुच्छता की तरह लग सकता है। लेकिन हिल्बर्ट ने अपना सवाल पूछने के सौ साल बाद, बहुपत्नी की गैर-नकारात्मकता उन सभी समस्याओं का जवाब देने के लिए बदल दी जो हम सभी को प्रभावित करती हैं।

सबसे अच्छा तरीका है

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

कई चरों के साथ बहुपद का न्यूनतम खोजना एक मुश्किल काम है। जटिल बहुपद के न्यूनतम मूल्य की गणना के लिए पाठ्यपुस्तक से कोई सरल एल्गोरिथ्म नहीं है, इसके अलावा, वे एक ग्राफ पर निर्माण करना मुश्किल है।

जॉर्जिना हॉल

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

न्यूनतम मूल्य खोजने का एक तरीका यह है कि प्रश्न पूछें: एक गैर-नकारात्मक बहुपद से अधिकतम मूल्य क्या घटाया जा सकता है ताकि यह किसी बिंदु पर नकारात्मक न हो जाए? प्रश्न का उत्तर देने के लिए, विभिन्न मूल्यों की जांच करना आवश्यक है - क्या 3 को घटाना संभव है ताकि यह नकारात्मक न हो जाए? और 4? और 5? प्रक्रिया को दोहराते हुए, प्रत्येक चरण पर आपको यह जानना होगा कि क्या बहुपद गैर-नकारात्मक है। यह वर्गों की राशि के रूप में इसकी अभिव्यक्ति की संभावना के माध्यम से सत्यापित है।

अहमदी ने कहा, "जिस सवाल पर सवाल पूछा जाना चाहिए वह है" बहुपद गैर-नकारात्मक? "समस्या यह है कि बड़ी संख्या में चर के साथ, इस सवाल का जवाब देना मुश्किल है। "इसलिए, हम गैर नकारात्मकता के प्रतिस्थापन के रूप में वर्गों के योग का उपयोग करते हैं।"

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

समस्या को तोड़ना

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

अनिरुद्ध मजूमदार

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

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

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

"हमने रोबोटिक्स और नियंत्रण सिद्धांत की कई समस्याओं का अध्ययन किया, और दिखाया कि परिणामी समाधानों की गुणवत्ता व्यावहारिक उपयोग के लिए उपयोगी है, और यह कि वे गणना करने में बहुत तेज़ हैं," मजूमदार ने कहा।

सुरक्षा प्रमाण

निर्णय की गति सब कुछ है यदि आप एक रोबोट में हैं। ऐसी स्थिति में, बहुपद एक गणितीय बाधा के रूप में कार्य कर सकता है जो उन बाधाओं के आसपास स्थापित होता है जिन्हें आप दुर्घटना में डालना नहीं चाहते हैं - यदि इसकी गणना जल्दी से की जा सकती है।

एक सरल उदाहरण की कल्पना करें: एक विशाल पार्किंग में एक रोबोट कार। पार्किंग में कुछ भी नहीं है सिवाय एक छोर पर सुरक्षा बूथ के। आपका कार्य मशीन को प्रोग्राम करना है ताकि यह इस बूथ में कभी क्रैश न हो।

इस मामले में, आप ग्रिड को पार्किंग में खींच सकते हैं। फिर एक बहुपद बनाते हैं जो इनपुट के रूप में ग्रिड पर अंक लेता है। सुनिश्चित करें कि मशीन के स्थान पर बहुपद के मान ऋणात्मक हैं, और गार्ड के बूथ के स्थान पर मान धनात्मक है।

आपकी कार और बूथ के बीच कुछ बिंदुओं पर, बहुपद माइनस से प्लस तक जाएगा। चूंकि आपकी कार केवल उसी स्थान पर स्थित हो सकती है जहां बहुपद नकारात्मक है, ये बिंदु एक दीवार की भूमिका निभाएंगे।

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

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

व्यवहार में, मूल्य को कम करना आवश्यक है - दीवार और बॉक्स के बीच की दूरी - इसलिए आपको बहुपद के ग्राफ को स्थानांतरित करने और यह देखने की आवश्यकता है कि इसे शून्य से प्लस तक जाने तक कितनी दूर ले जाया जा सकता है। यह जाँच कर प्राप्त किया जाता है कि क्या बहुपद वर्गों का योग है।

लगभग खाली पार्किंग एक बात है। लेकिन एक मशीन को नियंत्रित करने के यथार्थवादी परिदृश्यों में, इसके सेंसर लगातार नई चलती बाधाओं का पता लगाते हैं - कार, साइकिल, बच्चे। हर बार एक नई बाधा दिखाई देती है या एक ज्ञात चाल चलती है, मशीन को नए जटिल बहुपद बनाने की आवश्यकता होती है जो इन बाधाओं को घेरते हैं। यह मक्खी पर प्रदर्शन किया जाना चाहिए कि वर्गों की मात्रा पर बहुत सारे चेक है।

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

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