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

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

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

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$ हम लैग्रेंज गुणक-प्रेरित लैग्रेंज गुणक का परिचय देते हैं या शक्तिशाली लैग्रेंजियन सिद्धांत: लैग्रेंज द्वैत चर $\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 के पुनरावृत्तियों का प्रक्षेपवक्र।

यह भी देखें

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

ग्रन्थसूची

• 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.