आंतरिक-बिंदु विधि

उदाहरण समाधान के लिए खोजें। नीली रेखाएँ बाधाएँ दिखाती हैं, लाल बिंदु पुनरावृत्त समाधान दिखाते हैं।

इंटीरियर-पॉइंट मेथड्स (जिसे बैरियर मेथड्स या आईपीएम भी कहा जाता है) एल्गोरिदम का एक निश्चित वर्ग है जो रैखिक और नॉनलाइनियर उत्तल अनुकूलन समस्याओं को हल करता है।

1967 में सोवियत गणितज्ञ आई. आई. डिकिन द्वारा एक आंतरिक बिंदु विधि की खोज की गई और 1980 के दशक के मध्य में अमेरिका में इसका पुन: आविष्कार किया गया। 1984 में, नरेंद्र करमरकर ने लीनियर प्रोग्रामिंग के लिए एक विधि विकसित की जिसे कर्मकार का कलन विधि कहा जाता है, जो सिद्ध बहुपद समय में चलता है और व्यवहार में भी बहुत कुशल है। यह रैखिक प्रोग्रामिंग समस्याओं के समाधान को सक्षम करता है जो सरल विधि की क्षमताओं से परे थे। सिम्प्लेक्स विधि के विपरीत, यह संभव क्षेत्र के आंतरिक भाग को पार करके एक सर्वोत्तम समाधान तक पहुँचता है। उत्तल सेट को सांकेतिक शब्दों में बदलने के लिए उपयोग किए जाने वाले स्व-समन्वय बाधा समारोह के आधार पर उत्तल प्रोग्रामिंग के लिए विधि को सामान्यीकृत किया जा सकता है।

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

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

प्रारंभिक-दोहरी पथ-निम्नलिखित आंतरिक-बिंदु विधियों का वर्ग सबसे सफल माना जाता है। मेहरोत्रा ​​प्रेडिक्टर-करेक्टर विधि|

अतिरिक्त, यह सरल विधि के साथ प्रतिस्पर्धी था। पहले से ही लियोनिद खचियान की दीर्घवृत्त विधि एक बहुपद-समय एल्गोरिथम थी; चूँकि, यह व्यावहारिक रुचि के लिए बहुत धीमा था।

गैर-रैखिक अनुकूलन के लिए प्रारंभिक-दोहरी आंतरिक-बिंदु विधि

प्रारंभिक-दोहरी विधि का विचार विवश अरैखिक अनुकूलन के लिए प्रदर्शित करना आसान है। सादगी के लिए, एक गैर-रैखिक अनुकूलन समस्या के सभी-असमानता संस्करण पर विचार करें:

छोटा करना $f(x)$ का विषय है $c_{i}(x)\geq 0~{\text{for}}~i=1,\ldots ,m,~x\in \mathbb {R} ^{n},$ कहाँ $f:\mathbb {R} ^{n}\to \mathbb {R} ,c_{i}:\mathbb {R} ^{n}\rightarrow \mathbb {R} \quad (1).$

इस असमानता-बाधित अनुकूलन समस्या को तब इसे एक अप्रतिबंधित उद्देश्य समारोह में परिवर्तित करके हल किया जाता है जिसका न्यूनतम हम कुशलता से खोजने की उम्मीद करते हैं। विशेष रूप से, (1) से जुड़ा लॉगरिदमिक बैरियर फ़ंक्शन है

$B(x,\mu )=f(x)-\mu \sum _{i=1}^{m}\log(c_{i}(x)).\quad (2)$

यहाँ $\mu$ एक छोटा धनात्मक अदिश है, जिसे कभी-कभी बाधा पैरामीटर कहा जाता है। जैसा $\mu$ न्यूनतम शून्य में परिवर्तित हो जाता है $B(x,\mu )$ (1) के समाधान में अभिसरण होना चाहिए।

बैरियर फंक्शन ग्रेडियेंट है

$g_{b}(x,\mu ):=\nabla B(x,\mu )=g(x)-\mu \sum _{i=1}^{m}{\frac {1}{c_{i}(x)}}\nabla c_{i}(x),\quad (3)$

कहाँ $g(x):=\nabla f(x)$ मूल कार्य का ढाल है $f(x)$, और $\nabla c_{i}$ की प्रवणता है $c_{i}$.

मूल (मूल) चर के अतिरिक्त $x$ हम एक Lagrange गुणक-प्रेरित Lagrange गुणक का परिचय देते हैं#शक्तिशाली Lagrangian सिद्धांत: Lagrange द्वैत चर $\lambda \in \mathbb {R} ^{m}$

$c_{i}(x)\lambda _{i}=\mu ,\forall i=1,\ldots ,m.\quad (4)$

(4) कभी-कभी केकेटी स्थितियों में पूरक सुस्ती के समानता के लिए परेशान पूरकता की स्थिति कहा जाता है।

हम उन्हें खोजने की कोशिश करते हैं $(x_{\mu },\lambda _{\mu })$ जिसके लिए बैरियर फंक्शन की ग्रेडिएंट शून्य है।

(4) से (3) तक प्रयुक्त करने पर, हमें ग्रेडिएंट के लिए एक समीकरण मिलता है:

$g-A^{T}\lambda =0,\quad (5)$

जहां मैट्रिक्स $A$ जैकबियन मैट्रिक्स और बाधाओं का निर्धारक है $c(x)$.

(5) के पीछे बोध यह है कि की प्रवणता $f(x)$ बाधाओं के ग्रेडियेंट द्वारा फैले उप-स्थान में झूठ बोलना चाहिए। छोटे के साथ परेशान पूरकता $\mu$ (4) इस शर्त के रूप में समझा जा सकता है कि समाधान या तो सीमा के पास होना चाहिए $c_{i}(x)=0$, या ढाल का प्रक्षेपण $g$ बाधा घटक पर $c_{i}(x)$ सामान्य लगभग शून्य होना चाहिए।

न्यूटन विधि |न्यूटन की विधि (4) और (5) को प्रयुक्त करने पर, हमें एक समीकरण प्राप्त होता है $(x,\lambda )$ अद्यतन $(p_{x},p_{\lambda })$:

${\begin{pmatrix}W&-A^{T}\\\Lambda A&C\end{pmatrix}}{\begin{pmatrix}p_{x}\\p_{\lambda }\end{pmatrix}}={\begin{pmatrix}-g+A^{T}\lambda \\\mu 1-C\lambda \end{pmatrix}},$

कहाँ $W$ का हेसियन मैट्रिक्स है $B(x,\mu )$, $\Lambda$ का विकर्ण मैट्रिक्स है $\lambda$, और $C$ के साथ एक विकर्ण मैट्रिक्स है $C_{ii}=c_{i}(x)$.

(1), (4) स्थिति के कारण

$\lambda \geq 0$

प्रत्येक चरण पर प्रयुक्त किया जाना चाहिए। यह उपयुक्त चुनकर किया जा सकता है $\alpha$:

$(x,\lambda )\to (x+\alpha p_{x},\lambda +\alpha p_{\lambda }).$

आतंरिक बिंदु विधि का उपयोग करके x के पुनरावृत्तियों का प्रक्षेपवक्र।

यह भी देखें

• एफ़िन स्केलिंग
• संवर्धित Lagrangian विधि
• दंड विधि
• करुश-कुह्न-टकर स्थितियां

ग्रन्थसूची

• Dikin, I.I. (1967). "Iterative solution of problems of linear and quadratic programming". Dokl. Akad. Nauk SSSR. 174 (1): 747–748.
• Bonnans, J. Frédéric; Gilbert, J. Charles; Lemaréchal, Claude; Sagastizábal, Claudia A. (2006). Numerical optimization: Theoretical and practical aspects. Universitext (Second revised ed. of translation of 1997 French ed.). Berlin: Springer-Verlag. pp. xiv+490. doi:10.1007/978-3-540-35447-5. ISBN 978-3-540-35445-1. MR 2265882.
• Karmarkar, N. (1984). "A new polynomial-time algorithm for linear programming" (PDF). Proceedings of the sixteenth annual ACM symposium on Theory of computing – STOC '84. p. 302. doi:10.1145/800057.808695. ISBN 0-89791-133-4. Archived from the original (PDF) on 28 December 2013.
• Mehrotra, Sanjay (1992). "On the Implementation of a Primal-Dual Interior Point Method". SIAM Journal on Optimization. 2 (4): 575–601. doi:10.1137/0802028.
• Nocedal, Jorge; Stephen Wright (1999). Numerical Optimization. New York, NY: Springer. ISBN 978-0-387-98793-4.
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Section 10.11. Linear Programming: Interior-Point Methods". Numerical Recipes: The Art of Scientific Computing (3rd ed.). New York: Cambridge University Press. ISBN 978-0-521-88068-8.
• Wright, Stephen (1997). Primal-Dual Interior-Point Methods. Philadelphia, PA: SIAM. ISBN 978-0-89871-382-4.
• Boyd, Stephen; Vandenberghe, Lieven (2004). Convex Optimization (PDF). Cambridge University Press.

| group5 = Metaheuristics | abbr5 = heuristic | list5 =

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

| below =

• Software

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

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

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

}}