Interior-point method
आंतरिक-बिंदु विधियाँ (जिन्हें बाधा विधियाँ या आई. पी. एम. भी कहा जाता है) एल्गोरिदम का एक निश्चित वर्ग है जो रैखिक और अरैखिक उत्तल अनुकूलन समस्याओं को हल करता है। एक आंतरिक बिंदु विधि की खोज 1967 में सोवियत गणितशास्त्री आई. आई. डिकिन द्वारा की गई थी और 1980 के दशक के मध्य में अमेरिका में इसका पुनः आविष्कार किया गया था। 1984 में, नरेंद्र करमरकर ने रैखिक प्रोग्रामिंग के लिए एक विधि विकसित की जिसे करमरकर का एल्गोरिदम कहा जाता है, जो बहुपद समय में चलता है और व्यवहार में भी बहुत कुशल है। इसने रैखिक प्रोग्रामिंग समस्याओं के समाधान को सक्षम किया जो सिम्प्लेक्स विधि की क्षमताओं से परे थे। सिम्प्लेक्स विधि के विपरीत, यह व्यवहार्य क्षेत्र के आंतरिक भाग को पार करके एक सर्वोत्तम समाधान तक पहुँचता है। उत्तल समूह को कूटबद्ध करने के लिए उपयोग किए जाने वाले स्व-समन्वय बाधा कार्य के आधार पर उत्तल प्रोग्रामिंग के लिए विधि को सामान्यीकृत किया जा सकता है। किसी भी उत्तल अनुकूलन समस्या को शिलालेख रूप में परिवर्तित करके एक उत्तल समूह पर एक रैखिक कार्य को न्यूनतम (या अधिकतम) करने में बदला जा सकता है। 1960 के दशक की शुरुआत में एंथनी वी. फियाकको, गार्थ पी. मैककॉर्मिक और अन्य लोगों द्वारा एक बाधा का उपयोग करके व्यवहार्य सेट को कूटबद्ध करने और बाधा विधियों को डिजाइन करने के विचार का अध्ययन किया गया था। इन विचारों को मुख्य रूप से सामान्य अरैखिक प्रोग्रामिंग के लिए विकसित किया गया था, लेकिन बाद में समस्याओं के इस वर्ग के लिए अधिक प्रतिस्पर्धी तरीकों की उपस्थिति के कारण उन्हें छोड़ दिया गया था। क्रमिक द्विघात प्रोग्रामिंग)। यूरी नेस्टरोव और अर्काडी नेमिरोव्स्की ने इस तरह की बाधाओं का एक विशेष वर्ग तैयार किया जिसका उपयोग किसी भी उत्तल समूह को कूटबद्ध करने के लिए किया जा सकता है। वे गारंटी देते हैं कि एल्गोरिथ्म के पुनरावृत्तियों की संख्या समाधान के आयाम और सटीकता में एक बहुपद से घिरी हुई है। करमरकर की सफलता ने आंतरिक-बिंदु विधियों और बाधा समस्याओं के अध्ययन को पुनर्जीवित किया, जिससे पता चलता है कि बहुपद जटिलता की विशेषता वाली रैखिक प्रोग्रामिंग के लिए एक एल्गोरिथ्म बनाना संभव था और इसके अलावा, जो सिम्प्लेक्स विधि के साथ प्रतिस्पर्धी था। पहले से ही खाचियान की दीर्घवृत्त विधि एक बहुपद-समय एल्गोरिथ्म थी; हालाँकि, यह व्यावहारिक रुचि का होना बहुत धीमा था। प्रारंभिक-द्वैत पथ-अनुसरण आंतरिक-बिंदु विधियों के वर्ग को सबसे सफल माना जाता है। मेहरोत्रा का भविष्यवक्ता-सुधारक एल्गोरिदम इस वर्ग की विधियों के अधिकांश कार्यान्वयन के लिए आधार प्रदान करता है। गैर-रैखिक अनुकूलन के लिए प्राथमिक-दोहरी आंतरिक-बिंदु विधि सीमित गैर-रैखिक अनुकूलन के लिए प्राथमिक-दोहरी विधि के विचार को प्रदर्शित करना आसान है। सरलता के लिए, असमानता बाधाओं के साथ निम्नलिखित अरैखिक अनुकूलन समस्या पर विचार करेंः इस असमानता-बाधित अनुकूलन समस्या को एक अप्रतिबंधित उद्देश्य कार्य में परिवर्तित करके हल किया जाता है जिसका न्यूनतम हम कुशलता से खोजने की उम्मीद करते हैं। विशेष रूप से, (1) से जुड़ा लॉगरिदमिक बैरियर फ़ंक्शन है यहाँ एक छोटा सकारात्मक स्केलर है, जिसे कभी-कभी "बैरियर पैरामीटर" कहा जाता है। जैसे ही शून्य में अभिसरण होता है, न्यूनतम को (1) के समाधान में अभिसरण होना चाहिए। एक अवकलनीय फलन के प्रवणता को दर्शाया जाता है। मूल ("प्राइमल") चर के अलावा हम एक लैग्रेंज गुणक-प्रेरित दोहरे चर समीकरण (4) को पेश करते हैं, जिसे कभी-कभी "विचलित पूरकता" स्थिति कहा जाता है, क्योंकि यह केकेटी स्थितियों में "पूरक शिथिलता" से मिलता-जुलता है। हम उन लोगों को खोजने की कोशिश करते हैं जिनके लिए बैरियर फंक्शन का ग्रेडिएंट शून्य है। (4) से (3) में प्रतिस्थापित करने पर, हम ढाल के लिए एक समीकरण प्राप्त करते हैंः जहां मैट्रिक्स बाधाओं का जैकोबियन है। (5) के पीछे का अंतर्ज्ञान यह है कि का ढाल बाधाओं के ढाल द्वारा फैले उपक्षेत्र में होना चाहिए। छोटे (4) के साथ "विचलित पूरकता" को इस शर्त के रूप में समझा जा सकता है कि समाधान या तो सीमा के पास होना चाहिए, या बाधा घटक सामान्य पर ढाल का प्रक्षेपण लगभग शून्य होना चाहिए। पुनरावृत्त रूप से अद्यतन करने के लिए खोज दिशा होने दें। (4) और (5) पर न्यूटन की विधि को लागू करते हुए, हमें एक समीकरण मिलता हैः जहाँ का हेसियन मैट्रिक्स है, एक विकर्ण मैट्रिक्स है, और इसका विकर्ण मैट्रिक्स है। (1), (4) के कारण प्रत्येक चरण में शर्त लागू की जानी चाहिए। यह उपयुक्त चयन करके किया जा सकता हैः एफाइन स्केलिंग ऑगमेंटेड लैग्रैन्जियन विधि चैम्बोले-पॉक एल्गोरिदम करुश-कुह्न-टकर शर्त दंड विधि संदर्भ ग्रंथ सूची अनुकूलन एल्गोरिदम और विधियाँ भी देखें।