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

File:Ellipsoid 2.png

दीर्घवृत्ताभ विधि का पुनरावर्तन

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

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

इतिहास

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

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

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

विवरण

Main article: Convex optimization

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

• एक उत्तल कार्य $f_{0}(x):\mathbb {R} ^{n}\to \mathbb {R}$ वेक्टर पर न्यूनतम किया जाना है$x$(एन चर युक्त);
• रूप की उत्तल असमानता बाधाएँ $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$ ऐसा है कि $c\cdot x<c\cdot y$ सभी के लिए $y\in Q$.

दीर्घवृत्ताकार विधि का आउटपुट या तो है:

• पॉलीटोप में कोई भी बिंदु$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 .$

Sample sequence of iterates

File:Ellipsoid 1.png $k=0$	File:Ellipsoid 2.png $k=1$	File:Ellipsoid 3.png $k=2$
File:Ellipsoid 4.png $k=3$	File:Ellipsoid 5.png $k=4$	File:Ellipsoid 6.png $k=5$

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

प्रतिबंधित न्यूनतमकरण के लिए एल्गोरिथ्म के k-वें पुनरावृत्ति पर, हमारे पास एक बिंदु है $x^{(k)}$ एक दीर्घवृत्त के केंद्र में ${\mathcal {E}}^{(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)}$ अव्यवहार्य है और जे-वें बाधा का उल्लंघन करता है, व्यवहार्यता कटौती के साथ दीर्घवृत्त को अद्यतन करें। हमारी व्यवहार्यता कटौती एक उप-ग्रेडिएंट हो सकती है $g_{j}$ का $f_{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

| group5 = Metaheuristics | abbr5 = heuristic | list5 =

• Evolutionary algorithm
• Hill climbing
• Local search
• Simulated annealing
• Tabu search

| below =

• Software

}} | group5 =Metaheuuristic |abbr5 = heuristic | list5 =*विकासवादी एल्गोरिथ्म

• पहाड़ी की चढ़ाई
• स्थानीय खोज
• तैयार किए हुयी धातु पे पानी चढाने की कला
• तब्बू खोज

| below =* सॉफ्टवेयर

}}