प्रतिबंधित अनुकूलन

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

बाधा-संतुष्टि का समस्याओं से संबंध

विवश-अनुकूलन समस्या (सीओपी) मौलिक रूप से बाधा-संतुष्टि समस्या (सीएसपी) के प्रारूप के लिए महत्वपूर्ण सामान्यीकरण है। सीओपी सीएसपी है, जिसमें अनुकूलित किया जाने वाला आब्जेक्टिव फंक्शन सम्मिलित होते है। इस प्रकार अनुकूलन भाग को संभालने के लिए कई एल्गोरिदम का उपयोग किया जाता है।

सामान्य प्रपत्र

एक सामान्य विवश न्यूनतमकरण समस्या इस प्रकार लिखी जा सकती है:

${\begin{array}{rcll}\min &~&f(\mathbf {x} )&\\\mathrm {subject~to} &~&g_{i}(\mathbf {x} )=c_{i}&{\text{for }}i=1,\ldots ,n\quad {\text{Equality constraints}}\\&~&h_{j}(\mathbf {x} )\geq d_{j}&{\text{for }}j=1,\ldots ,m\quad {\text{Inequality constraints}}\end{array}}$

जहाँ $g_{i}(\mathbf {x} )=c_{i}~\mathrm {for~} i=1,\ldots ,n$ और $h_{j}(\mathbf {x} )\geq d_{j}~\mathrm {for~} j=1,\ldots ,m$ ऐसी बाधाएं हैं, जिन्हें संतुष्ट करना आवश्यक होता है, इन्हें बाधा (गणित) के लिए कठोर और सरल बाधाएं कहा जाता है, और $f(\mathbf {x} )$ वस्तुनिष्ठ फंक्शन है, जिससे बाधाओं के अधीन अनुकूलित करने की आवश्यकता होती है।

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

हल करने की विधि

कई प्रतिबंधित अनुकूलन एल्गोरिदम को अधिकांशतः पेनैल्टी पद्धति के उपयोग के माध्यम से, अप्रतिबंधित स्थिति में अनुकूलित किया जा सकता है। चूंकि, अप्रतिबंधित विधि द्वारा उठाए गए खोज के लिए बढ़ाये गए इस चरण के लिए बाधित समस्या के लिए अस्वीकार्य हो सकते हैं, जिससे अभिसरण की कमी हो सकती है। इसे मराटोस प्रभाव कहा जाता है।

समानता की बाधाएं

प्रतिस्थापन विधि

बहुत ही सरल समस्याओं के लिए, मान लें कि एकल समानता बाधा के अधीन दो वैरियेबल के बीच के इस फंक्शन को प्रतिस्थापन विधि के द्वारा लागू करने पर सबसे व्यावहारिक माना जाता है। इस प्रकार को किसी विचार फंक्शन संरचना बनाने के लिए आब्जेक्टिव फंक्शन में बाधा को प्रतिस्थापित करने का है, जो इस बाधा के प्रभाव को सम्मिलित करता है। उदाहरण के लिए यदि मान लें कि उद्देश्य अधिकतम करना है, जिसके लिए $f(x,y)=x\cdot y$ मुख्य रूप से $x+y=10$ का विषय है, यहाँ पर बाधा का तात्पर्य $y=10-x$ से है, जिसे बनाने के आब्जेक्टिव फंक्शन $p(x)=x(10-x)=10x-x^{2}$में प्रतिस्थापित किया जा सकता है, इसका प्रथम-क्रम ${\frac {\partial p}{\partial x}}=10-2x=0$ के लिए आवश्यक शर्त देता है, जिसका हल $x=5$ और इसके परिणामस्वरूप, $y=10-5=5$ द्वारा किया जा सकता है।

लैग्रेंज गुणक

Main article: लैग्रेंज गुणक

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

असमानता बाधाएं

असमान बाधाओं के साथ, समस्या को ज्यामितीय इष्टतमता स्थितियों, फ्रिट्ज़ जॉन स्थितियों और करुश-कुह्न-टकर स्थितियों के संदर्भ में वर्णित किया जा सकता है, जिसके अनुसार सरल समस्याएं हल हो सकती हैं।

लीनियर प्रोग्रामिंग

यदि आब्जेक्टिव फंक्शन और सभी कठिन बाधाएं लीनियर हैं और कुछ कठिन बाधाएं असमानताएं हैं, तो समस्या लीनियर प्रोग्रामिंग समस्या है। इस प्रकार इसे सिंप्लेक्स विधि द्वारा हल किया जा सकता है, जो सामान्यतः इसकी समस्या के आकार में बहुपद समय में कार्य करता है, अपितु इसकी गारंटी नहीं है, या आंतरिक बिंदु विधियों द्वारा जो बहुपद समय में कार्य करने की गारंटी देता है।

नाॅन लीनियर प्रोग्रामिंग

यदि आब्जेक्टिव फंक्शन या कुछ बाधाएँ नाॅन लीनियर हैं, और कुछ बाधाएँ असमानताएँ हैं, तो समस्या नाॅन लीनियर प्रोग्रामिंग समस्या है।

क्वाडरैटिक प्रोग्रामिंग

यदि सभी कठिन बाधाएं लीनियर हैं और कुछ असमानताएं हैं, अपितु यह आब्जेक्टिव फंक्शन क्वाडरैटिक है, जो समस्या क्वाडरैटिक प्रोग्रामिंग समस्या के रूप से जाना जाता है। यह इस प्रकार की नॉनलाइनियर प्रोग्रामिंग है। यदि आब्जेक्टिव फंक्शन उत्तल फंक्शन है तो इसे अभी भी दीर्घवृत्त विधि द्वारा बहुपद समय में हल किया जा सकता है, अन्यथा इस समस्या एनपी कठिन हो सकती है।

केकेटी की शर्तें

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

शाखा और सीमा

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

यह मानते हुए कि लागत को कम किया जाना है, इन एल्गोरिदम की दक्षता इस बात पर निर्भर करती है कि आंशिक हल के विस्तार से प्राप्त होने वाली लागत का मूल्यांकन कैसे किया जाता है। इसके अतिरिक्त यदि एल्गोरिदम आंशिक हल से पीछे हट सकता है, तो खोज का हिस्सा छोड़ दिया जाता है। अनुमानित लागत जितनी कम होगी, इस प्रकार एल्गोरिदम उतना ही उत्तम होगा, क्योंकि कम अनुमानित लागत अब तक पाए गए हल की सर्वोत्तम लागत से कम होने की अधिक संभावना है।

दूसरी ओर, यह अनुमानित लागत उस प्रभावी लागत से कम नहीं हो सकती है जो हल का विस्तार करके प्राप्त की जा सकती है, अन्यथा एल्गोरिदम पीछे हट सकता है जबकि अब तक पाए गए सर्वोत्तम हल से उत्तम हल उपस्थित है। इसके परिणामस्वरूप एल्गोरिदम की लागत पर ऊपरी सीमा की आवश्यकता होती है, जो इस प्रकार आंशिक हल का विस्तार करके प्राप्त की जा सकती है, और यह ऊपरी सीमा यथासंभव छोटी होनी चाहिए।

इस दृष्टिकोण का रूपांतर जिसे हेन्सन विधि कहा जाता है, इसके अतिरिक्त यहाँ पर अंतराल अंकगणित इतिहास का उपयोग करता है। यह स्वाभाविक रूप से आयताकार बाधाओं को लागू करता है।

बाउंडिंग फंक्शन

आंशिक हल के लिए इस ऊपरी सीमा का मूल्यांकन करने का तरीका प्रत्येक सरल बाधा पर अलग से विचार करना है। प्रत्येक सरल बाधा के लिए, अनअसाइन्ड वेरिएबल्स के किसी भी असाइनमेंट के लिए अधिकतम संभव मान माना जाता है। इन मूल्यों का योग ऊपरी सीमा है क्योंकि सरल बाधाएं उच्च मूल्य नहीं मान सकती हैं। यह सटीक है क्योंकि सरल बाधाओं के अधिकतम मूल्य विभिन्न मूल्यांकनों से प्राप्त हो सकते हैं: सरल बाधा अधिकतम $x=a$ तक हो सकती है, जबकि अन्य बाधा अधिकतम $x=b$ तक हो सकती है।

रूसी डाॅल की खोज

यह विधि ब्रांच-एंड-बाउंड एल्गोरिदम $n$ समस्याएं चलाता है, जहाँ $n$ वैरियेबल्स की संख्या है, ऐसी प्रत्येक समस्या वैरियेबल्स के अनुक्रम को छोड़ने से प्राप्त उपसमस्या $x_{1},\ldots ,x_{i}$ है, यहाँ पर इस प्रकार की मूल समस्या से, साथ ही उनमें उपस्थित बाधाओं से किया जाता हैं। इस प्रकार वैरियेबल पर समस्या के पश्चात $x_{i+1},\ldots ,x_{n}$ के हल हो जाने पर, इसकी इष्टतम लागत को अन्य समस्याओं को हल करते समय ऊपरी सीमा के रूप में उपयोग किया जा सकता है,

विशेष रूप से, किसी हल की लागत का अनुमान $x_{i+1},\ldots ,x_{n}$ हैं, चूंकि असाइन किए गए वैरियेबल को उस लागत में जोड़ा जाता है जो मूल्यांकन किए गए वैरियेबल से प्राप्त होती है। वस्तुतः यह मूल्यांकन किए गए वैरियेबल्स को अनदेखा करने और असाइन न किए गए वैरियेबल्स पर समस्या को हल करने के अनुरूप है, इसके अतिरिक्त बाद वाली समस्याएं पहले ही हल हो चुकी है। इसका अधिक सटीक रूप से, असाइन किए गए और अनअसाइन किए गए दोनों वैरियेबल वाले सरल बाधाओं की लागत का अनुमान या मनमाने ढंग से अन्य विधि का उपयोग करके ऊपर दिया गया है, इसके अतिरिक्त केवल अनिर्धारित वैरियेबल वाले सरल बाधाओं की लागत का अनुमान संबंधित समस्या के इष्टतम हल का उपयोग करके लगाया जाता है, जो इस बिंदु पर पहले से ही ज्ञात है।

रूसी डाॅल की खोज पद्धति और डायनेमिक प्रोग्रामिंग के बीच समानता है। डायनेमिक प्रोग्रामिंग के समान रूसी डाॅल की खोज पूरी समस्या को हल करने के लिए उप-समस्याओं को हल करती है। अपितु, जबकि डायनामिक प्रोग्रामिंग मुख्यतः इस प्रकार की संपूर्ण समस्याओं का परिणाम प्राप्त करने के लिए उप-समस्याओं पर प्राप्त परिणामों को सीधे संयोजित करता है, इस प्रकार रूसी डाॅल की खोज केवल अपनी खोज के समय उन्हें सीमा के रूप में उपयोग करती है।

बकेट उन्मूलन

बकेट एलिमिनेशन एल्गोरिदम को बाधा अनुकूलन के लिए अनुकूलित किया जा सकता है। किसी दिए गए वेरिएबल को वास्तव में सभी सरल बाधाओं को नए सरल बाधा के साथ प्रतिस्थापित करके समस्या से हटाया जा सकता है। इस नई बाधा की लागत की गणना हटाए गए वैरियेबल के प्रत्येक मान के लिए अधिकतम मान मानकर की जाती है। इस प्रकार औपचारिक रूप से, यदि $x$ क्या वेरिएबल को हटाया जाना है, यहाँ पर $C_{1},\ldots ,C_{n}$ में सम्मिलित सरल बाधाएं हैं, और $y_{1},\ldots ,y_{m}$ के अतिरिक्त उनके वैरियेबल $x$ हैं, इस प्रकार की नई सरल बाधाओं द्वारा इन्हें परिभाषित किया गया है:

$C(y_{1}=a_{1},\ldots ,y_{n}=a_{n})=\max _{a}\sum _{i}C_{i}(x=a,y_{1}=a_{1},\ldots ,y_{n}=a_{n}).$

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

यह भी देखें

• सीमित न्यूनतम वर्ग
• वितरित बाधा अनुकूलन
• बाधा संतुष्टि समस्या (सीएसपी)
• बाधा प्रोग्रामिंग
• पूर्णांक प्रोग्रामिंग
• पेनैल्टी विधि
• श्रेष्ठीकरण

अग्रिम पठन

• Bertsekas, Dimitri P. (1982). Constrained Optimization and Lagrange Multiplier Methods. New York: Academic Press. ISBN 0-12-093480-9.
• Dechter, Rina (2003). Constraint Processing. Morgan Kaufmann. ISBN 1-55860-890-7.

| group5 = Metaheuristics | abbr5 = heuristic | list5 =

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

| below =

• Software

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

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

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

}}