Ellipsoid method
गणितीय अनुकूलन में, दीर्घवृत्त विधि उत्तल कार्यों को कम करने के लिए एक पुनरावृत्ति विधि है। जब तर्कसंगत डेटा के साथ व्यवहार्य रैखिक अनुकूलन समस्याओं को हल करने के लिए विशेषज्ञता प्राप्त होती है, तो दीर्घवृत्त विधि एक एल्गोरिथ्म है जो कई चरणों में एक इष्टतम समाधान ढूंढती है जो इनपुट आकार में बहुपद है। दीर्घवृत्त विधि दीर्घवृत्त का एक अनुक्रम उत्पन्न करती है जिसका आयतन हर चरण में समान रूप से कम हो जाता है, इस प्रकार एक उत्तल फलन के लघुकरण को घेरता है। दीर्घवृत्त विधि का एक लंबा इतिहास रहा है। एक पुनरावृत्ति विधि के रूप में, एक प्रारंभिक संस्करण नॉम जेड शोर द्वारा पेश किया गया था। 1972 में, वास्तविक उत्तल लघुकरण के लिए एक सन्निकटन एल्गोरिथ्म का अध्ययन अर्काडी नेमिरोव्स्की और डेविड बी. युडिन (जुडिन) द्वारा किया गया था। तर्कसंगत डेटा के साथ रैखिक प्रोग्रामिंग समस्याओं को हल करने के लिए एक एल्गोरिथ्म के रूप में, एलिप्सॉइड एल्गोरिथ्म का अध्ययन लियोनिद खाचियान द्वारा किया गया था; खाचियान की उपलब्धि रैखिक कार्यक्रमों की बहुपद-समय समाधानशीलता को साबित करना था। यह एक सैद्धांतिक दृष्टिकोण से एक उल्लेखनीय कदम थाः उस समय रैखिक समस्याओं को हल करने के लिए मानक एल्गोरिथ्म सिम्प्लेक्स एल्गोरिथ्म था, जिसका एक रन टाइम होता है जो आमतौर पर समस्या के आकार में रैखिक होता है, लेकिन जिनके लिए उदाहरण मौजूद हैं जिनके लिए यह समस्या के आकार में घातीय है। इस प्रकार, एक एल्गोरिथ्म होना जो सभी मामलों के लिए बहुपद होने की गारंटी है, एक सैद्धांतिक सफलता की तरह लग रहा था। खाचियान के काम ने पहली बार दिखाया कि रैखिक कार्यक्रमों को हल करने के लिए एल्गोरिदम हो सकते हैं जिनके रनटाइम को बहुपद साबित किया जा सकता है। व्यवहार में, हालांकि, एल्गोरिथ्म काफी धीमा है और बहुत कम व्यावहारिक रुचि का है, हालांकि इसने बाद के काम के लिए प्रेरणा प्रदान की जो बहुत अधिक व्यावहारिक उपयोग का साबित हुआ। विशेष रूप से, कर्मकार का एल्गोरिथ्म, एक आंतरिक-बिंदु विधि, व्यवहार में दीर्घवृत्त विधि की तुलना में बहुत तेज है। सबसे खराब स्थिति में भी करमरकर का एल्गोरिदम तेज होता है। एलिप्सॉइडल एल्गोरिथ्म जटिलता सिद्धांतकारों को (सबसे खराब स्थिति) सीमाओं को प्राप्त करने की अनुमति देता है जो समस्या के आयाम और डेटा के आकार पर निर्भर करते हैं, लेकिन पंक्तियों की संख्या पर नहीं, इसलिए यह कई वर्षों तक संयोजन अनुकूलन सिद्धांत में महत्वपूर्ण रहा। केवल 21वीं सदी में समान जटिलता गुणों के साथ आंतरिक-बिंदु एल्गोरिदम दिखाई दिए हैं। विवरण एक उत्तल लघुकरण समस्या में निम्नलिखित तत्व होते हैं। वेक्टर पर न्यूनतम किया जाने वाला उत्तल फलन (जिसमें n चर होते हैं); रूप की उत्तल असमानता बाधाएं, जहां कार्य उत्तल होते हैं; ये बाधाएं एक उत्तल समूह को परिभाषित करती हैं। रूप की रैखिक समानता की सीमाएँ। हमें एक प्रारंभिक दीर्घवृत्त भी दिया जाता है जिसे एक मिनीमाइज़र के रूप में परिभाषित किया जाता है, जहाँ और इसका केंद्र है। अंत में, हमें उत्तल समुच्चय के लिए एक पृथक्करण दैवज्ञ के अस्तित्व की आवश्यकता होती है। एक बिंदु को देखते हुए, दैवज्ञ को दो उत्तरों में से एक जवाब देना चाहिएः "बिंदु अंदर है", या-"बिंदु अंदर नहीं है, और इसके अलावा, यहाँ एक हाइपरप्लेन है जो अलग होता है", यानी, एक वेक्टर जो सभी के लिए है। एलिप्सॉइड विधि का परिणाम या तो हैः पॉलीटोप में कोई भी बिंदु (यानी, कोई भी व्यवहार्य बिंदु), या-एक प्रमाण जो खाली है। किसी भी कार्य का असमानता-सीमित न्यूनतमकरण जो हर जगह शून्य है, किसी भी व्यवहार्य बिंदु की पहचान करने की समस्या से मेल खाता है। यह पता चला है कि किसी भी रैखिक प्रोग्रामिंग समस्या को एक रैखिक व्यवहार्यता समस्या में कम किया जा सकता है (जैसे। कुछ रैखिक असमानता और समानता बाधाओं के अधीन शून्य फलन को कम करें)। ऐसा करने का एक तरीका यह है कि प्राथमिक और दोहरे रैखिक कार्यक्रमों को एक साथ एक कार्यक्रम में जोड़ा जाए, और अतिरिक्त (रैखिक) बाधा को जोड़ा जाए कि प्राथमिक समाधान का मूल्य दोहरे समाधान के मूल्य से बदतर नहीं है। एक अन्य तरीका रैखिक कार्यक्रम के उद्देश्य को एक अतिरिक्त बाधा के रूप में मानना है, और इष्टतम मूल्य खोजने के लिए द्विआधारी खोज का उपयोग करना है। अनियंत्रित लघुकरण एल्गोरिथम के k-th पुनरावृत्ति में, हमारे पास एक दीर्घवृत्त के केंद्र में एक बिंदु होता है हम एक वेक्टर प्राप्त करने के लिए कटिंग-प्लेन ओरेकल से पूछताछ करते हैं ताकि हम इसलिए निष्कर्ष निकाल सकें कि हम ऊपर वर्णित अर्ध-दीर्घवृत्त युक्त न्यूनतम आयतन का दीर्घवृत्त निर्धारित करते हैं और गणना करते हैं। अद्यतन इस प्रकार दिया जाता है कि कहाँ रुकने का मानदंड उस गुण द्वारा दिया जाता है कि असमानता-सीमित न्यूनतमकरण सीमित न्यूनतमकरण के लिए एल्गोरिथ्म के k-th पुनरावृत्ति पर, हमारे पास पहले की तरह एक दीर्घवृत्त के केंद्र में एक बिंदु है। हमें अब तक संभव पुनरावृत्तियों के सबसे छोटे वस्तुनिष्ठ मूल्य को दर्ज करने वाले मूल्यों की एक सूची भी बनाए रखनी चाहिए। इस बात पर निर्भर करते हुए कि बिंदु संभव है या नहीं, हम दो कार्यों में से एक का प्रदर्शन करते हैंः यदि संभव है, तो अनिवार्य रूप से उसी अद्यतन का प्रदर्शन करें जैसा कि अनियंत्रित मामले में, एक उप-प्रवणता का चयन करके जो संतुष्ट करता है यदि व्यवहार्य नहीं है और जे-th बाधा का उल्लंघन करता है, तो व्यवहार्यता कटौती के साथ दीर्घवृत्त को अद्यतन करें। हमारी व्यवहार्यता में कटौती एक उप-प्रवणता हो सकती है जिसे सभी व्यवहार्य z के लिए संतुष्ट करना चाहिए। प्रदर्शन दीर्घवृत्त विधि का उपयोग निम्न-आयामी समस्याओं पर किया जाता है, जैसे कि समतलीय स्थान की समस्याएं, जहां यह संख्यात्मक रूप से स्थिर है। "छोटे" आकार की समस्याओं पर भी, यह संख्यात्मक अस्थिरता और व्यवहार में खराब प्रदर्शन से ग्रस्त है। हालांकि, दीर्घवृत्त विधि संयोजन अनुकूलन में एक महत्वपूर्ण सैद्धांतिक तकनीक है। कम्प्यूटेशनल जटिलता सिद्धांत में, दीर्घवृत्तीय एल्गोरिथ्म आकर्षक है क्योंकि इसकी जटिलता स्तंभों की संख्या और गुणांकों के डिजिटल आकार पर निर्भर करती है, लेकिन पंक्तियों की संख्या पर नहीं। 21वीं सदी में, समान गुणों वाले आंतरिक-बिंदु एल्गोरिदम सामने आए हैं। दिमित्रीस अलेवरास और मैनफ्रेड डब्ल्यू. पैडबर्ग, रैखिक अनुकूलन और विस्तारः समस्याएं और विस्तार, यूनिवर्सिटेक्स्ट, स्प्रिंगर-वेरलैग, 2001। (समाधान के साथ पैडबर्ग की समस्याएं।) वी. चंद्रू और M.R.Rao, रैखिक प्रोग्रामिंग, एल्गोरिदम में अध्याय 31 और गणना पुस्तिका का सिद्धांत, M.J.Atallah द्वारा संपादित, CRC प्रेस 1999,31-1 से 31-37। वी. चंद्रू और M.R.Rao, पूर्णांक प्रोग्रामिंग, एल्गोरिदम में अध्याय 32 और गणना पुस्तिका का सिद्धांत, M.J.Atallah द्वारा संपादित, CRC प्रेस 1999,32-1 से 32-45। जॉर्ज बी. डांट्जिग और मुकुंद एन. थापा। 1997 में। रैखिक प्रोग्रामिंग 1: परिचय। स्प्रिंगर-वेरलैग। जॉर्ज बी. डांट्जिग और मुकुंद एन. थापा। 2003 में। रैखिक प्रोग्रामिंग 2: सिद्धांत और विस्तार। स्प्रिंगर-वेरलैग। एल. लोवाज़ः एन एल्गोरिदमिक थ्योरी ऑफ़ नंबर्स, ग्राफ़्स एंड कन्वेक्सिटी, सीबीएमएस-एन. एस. एफ. रीजनल कॉन्फ्रेंस सीरीज़ इन एप्लाइड मैथमेटिक्स 50, एस. आई. ए. एम., फिलाडेल्फिया, पेंसिल्वेनिया, 1986 कट्टा जी. मूर्ति, लीनियर प्रोग्रामिंग, विली, 1983। एम. पैडबर्ग, रैखिक अनुकूलन और विस्तार, दूसरा संस्करण, स्प्रिंगर-वेरलैग, 1999। क्रिस्टोस एच. पापाडिमिट्रियो और केनेथ स्टीग्लिट्ज़, कॉम्बिनेटरियल ऑप्टिमाइजेशनः एल्गोरिदम और जटिलता, एक नई प्रस्तावना के साथ संशोधित गणराज्य, डोवर। अलेक्जेंडर श्राइज्वर, रैखिक और पूर्णांक प्रोग्रामिंग का सिद्धांत। जॉन विली एंड संस, 1998, एक्सटर्नल लिंक्स EE364b, एक स्टैनफोर्ड कोर्स होमपेज कॉम्बिनेटोरियल ऑप्टिमाइजेशन कन्वेक्स ऑप्टिमाइजेशन लीनियर प्रोग्रामिंग