दीर्घवृत्ताकार विधि

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

दीर्घवृत्ताकार विधि दीर्घवृत्ताभ का एक अनुक्रम उत्पन्न करती है जिसका आयतन प्रत्येक चरण पर समान रूप से घटता है, इस प्रकार एक उत्तल फलन का न्यूनतमीकरण होता है।

इतिहास

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

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

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

विवरण

Main article: उत्तल अनुकूलन

उत्तल न्यूनीकरण समस्या में निम्नलिखित घटक सम्मिलित हैं।

• एक उत्तल फलनों $f_{0}(x):\mathbb {R} ^{n}\to \mathbb {R}$ सदिश $x$(n चर युक्त) पर न्यूनतम किया जाना है;
• रूप की उत्तल असमानता बाधाएँ $f_{i}(x)\leqslant 0$ उत्तल हैं, जहां $f_{i}$ फलनों करता है; ये बाधाएं उत्तल सम्मुच्चय $Q$ को परिभाषित करती हैं।
• प्रपत्र की रैखिक समानता बाधाएँ $h_{i}(x)=0$।

हमें एक प्रारंभिक दीर्घवृत्ताभ ${\mathcal {E}}^{(0)}\subset \mathbb {R} ^{n}$ भी दिया गया है, जिसे इस प्रकार परिभाषित किया गया है।

${\mathcal {E}}^{(0)}=\left\{z\in \mathbb {R} ^{n}\ :\ (z-x_{0})^{T}P_{(0)}^{-1}(z-x_{0})\leqslant 1\right\}$

एक मिनिमाइज़र $x^{*}$ युक्त, जहाँ $P_{(0)}\succ 0$ और $x_{0}$ का केंद्र ${\mathcal {E}}$ है।

अंत में, हमें उत्तल सम्मुच्चय के लिए एक पृथक्करण दैवज्ञ $Q$ के अस्तित्व की आवश्यकता होती है। एक बिंदु $x\in \mathbb {R} ^{n}$ दिया गया, दिव्यवक्ता को दो उत्तरों में से एक वापस करना चाहिए:

• बिंदु $x$ $Q$ में है, या -
• बिंदु $x$ $Q$ में नहीं है, और इसके अतिरिक्त, यहां एक अधिसमतल है जो $x$ से $Q$ अलग करता है, वह है, अर्थात्, एक सदिश $c$ ऐसा कि सभी $y\in Q$ के लिए $c\cdot x<c\cdot y$ है।

दीर्घवृत्ताकार विधि का प्रक्षेपण या तो निम्न है:

• पॉलीटोप $Q$ में कोई भी बिंदु (अर्थात, कोई भी व्यवहार्य बिंदु), या -
• एक प्रमाण कि $Q$ खाली है।

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

अप्रतिबंधित न्यूनतमकरण

कलन विधि के k-वें पुनरावृत्ति पर, हमारे पास एक दीर्घवृत्त के केंद्र में बिंदु $x^{(k)}$ है

${\mathcal {E}}^{(k)}=\left\{x\in \mathbb {R} ^{n}\ :\ \left(x-x^{(k)}\right)^{T}P_{(k)}^{-1}\left(x-x^{(k)}\right)\leqslant 1\right\}.$

हम एक सदिश $g^{(k+1)}\in \mathbb {R} ^{n}$ प्राप्त करने के लिए कर्तनतल ओरेकल से पूछताछ इस प्रकार करते हैं कि

$g^{(k+1)T}\left(x^{*}-x^{(k)}\right)\leqslant 0.$

इसलिए हम यह निष्कर्ष निकालते हैं

$x^{*}\in {\mathcal {E}}^{(k)}\cap \left\{z\ :\ g^{(k+1)T}\left(z-x^{(k)}\right)\leqslant 0\right\}.$

हम ${\mathcal {E}}^{(k+1)}$ ऊपर वर्णित अर्ध-दीर्घवृत्त वाले न्यूनतम आयतन वाले दीर्घवृत्ताभ को निर्धारित करते हैं और $x^{(k+1)}$ की गणना करते हैं। यह निम्न द्वारा अद्यतन दिया गया है

${\begin{aligned}x^{(k+1)}&=x^{(k)}-{\frac {1}{n+1}}P_{(k)}{\tilde {g}}^{(k+1)}\\P_{(k+1)}&={\frac {n^{2}}{n^{2}-1}}\left(P_{(k)}-{\frac {2}{n+1}}P_{(k)}{\tilde {g}}^{(k+1)}{\tilde {g}}^{(k+1)T}P_{(k)}\right)\end{aligned}}$

जहाँ

${\tilde {g}}^{(k+1)}=\left({\frac {1}{\sqrt {g^{(k+1)T}P_{(k)}g^{(k+1)}}}}\right)g^{(k+1)}.$

विरामन निकष निम्न विशेषता द्वारा दिया गया है

${\sqrt {g^{(k)T}P_{(k)}g^{(k)}}}\leqslant \epsilon \quad \Rightarrow \quad f(x^{(k)})-f\left(x^{*}\right)\leqslant \epsilon .$

असमानता-विवश न्यूनीकरण

प्रतिबंधित न्यूनतमकरण के लिए कलन विधि के k-वें पुनरावृत्ति पर, हमारे पास पहले की तरह दीर्घवृत्त के केंद्र ${\mathcal {E}}^{(k)}$ पर एक बिंदु $x^{(k)}$ है। हमें अब तक संभव पुनरावृत्तियों के सबसे छोटे उद्देश्य मूल्य को रिकॉर्ड करते हुए मूल्यों की एक सूची $f_{\rm {best}}^{(k)}$ भी बनाए रखनी चाहिए। इस पर निर्भर करते हुए कि बिंदु $x^{(k)}$ संभव है या नहीं, हम दो में से एक फलनों करते हैं:

• यदि $x^{(k)}$ संभव है, तो एक सबग्रेडिएंट $g_{0}$ चुनकर, जो संतुष्ट करता है, अनिवार्य रूप से वही अद्यतन करें जो अप्रतिबंधित स्तिथि में था

$g_{0}^{T}(x^{*}-x^{(k)})+f_{0}(x^{(k)})-f_{\rm {best}}^{(k)}\leqslant 0$

• अगर $x^{(k)}$ अव्यवहार्य है और j-वें बाधा का उल्लंघन करता है, व्यवहार्यता कटौती के साथ दीर्घवृत्त को अद्यतन करें। हमारी व्यवहार्यता कटौती $f_{j}$ का उपग्रेडिएंट $g_{j}$ हो सकती है जिसे निम्न संतुष्ट करना होगा

$g_{j}^{T}(z-x^{(k)})+f_{j}(x^{(k)})\leqslant 0$

सभी व्यवहार्य z के लिए होता है।

प्रदर्शन

दीर्घवृत्ताकार विधि का उपयोग निम्न-आयामी समस्याओं पर किया जाता है, जैसे कि समतल स्थान की समस्याएँ, जहाँ यह संख्यात्मक रूप से स्थिर होती है। यहां तक ​​कि छोटी-छोटी समस्याओं पर भी, यह संख्यात्मक अस्थिरता और व्यवहार में खराब प्रदर्शन से ग्रस्त है।

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

अग्रिम पठन

• Dmitris Alevras and Manfred W. Padberg, Linear Optimization and Extensions: Problems and Extensions, Universitext, Springer-Verlag, 2001. (Problems from Padberg with solutions.)
• V. Chandru and M.R.Rao, Linear Programming, Chapter 31 in Algorithms and Theory of Computation Handbook, edited by M.J.Atallah, CRC Press 1999, 31-1 to 31-37.
• V. Chandru and M.R.Rao, Integer Programming, Chapter 32 in Algorithms and Theory of Computation Handbook, edited by M.J.Atallah, CRC Press 1999, 32-1 to 32-45.
• George B. Dantzig and Mukund N. Thapa. 1997. Linear programming 1: Introduction. Springer-Verlag.
• George B. Dantzig and Mukund N. Thapa. 2003. Linear Programming 2: Theory and Extensions. Springer-Verlag.
• L. Lovász: An Algorithmic Theory of Numbers, Graphs, and Convexity, CBMS-NSF Regional Conference Series in Applied Mathematics 50, SIAM, Philadelphia, Pennsylvania, 1986
• Kattta G. Murty, Linear Programming, Wiley, 1983.
• M. Padberg, Linear Optimization and Extensions, Second Edition, Springer-Verlag, 1999.
• Christos H. Papadimitriou and Kenneth Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Corrected republication with a new preface, Dover.
• Alexander Schrijver, Theory of Linear and Integer Programming. John Wiley & sons, 1998, ISBN 0-471-98232-6

बाहरी संबंध

• EE364b, a Stanford course homepage