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

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

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

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

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

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

${\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: Lagrange multipliers

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

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

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

रैखिक प्रोग्रामिंग

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

अरेखीय प्रोग्रामिंग

यदि उद्देश्य फ़ंक्शन या कुछ बाधाएँ अरेखीय हैं, और कुछ बाधाएँ असमानताएँ हैं, तो समस्या एक अरेखीय प्रोग्रामिंग समस्या है।

द्विघात प्रोग्रामिंग

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

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

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

शाखा और सीमा

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

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

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

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

पहली पसंद बाउंडिंग फ़ंक्शन

आंशिक समाधान के लिए इस ऊपरी सीमा का मूल्यांकन करने का एक तरीका प्रत्येक नरम बाधा पर अलग से विचार करना है। प्रत्येक सॉफ्ट बाधा के लिए, अनअसाइन्ड वेरिएबल्स के किसी भी असाइनमेंट के लिए अधिकतम संभव मान माना जाता है। इन मूल्यों का योग एक ऊपरी सीमा है क्योंकि नरम बाधाएं उच्च मूल्य नहीं मान सकती हैं। यह सटीक है क्योंकि नरम बाधाओं के अधिकतम मूल्य विभिन्न मूल्यांकनों से प्राप्त हो सकते हैं: एक नरम बाधा अधिकतम हो सकती है $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 =* सॉफ्टवेयर

}}