गणितीय अनुकूलन

a का ग्राफ z = f(x, y) = −(x² + y²) + 4 द्वारा दिया गया है। (x, y, z) = (0, 0, 4) पर वैश्विक अधिकतम एक नीले बिंदु द्वारा इंगित किया गया है।

Error creating thumbnail:

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

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

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

अनुकूलन समस्याएं

अनुकूलन समस्याओं को दो श्रेणियों में विभाजित किया जा सकता है, यह इस बात पर निर्भर करता है कि चर निरंतर हैं या असतत:

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

अनुकूलन समस्या को निम्नलिखित तरीके से दर्शाया जा सकता है:

दिया गया: फलन f : A → ℝ समुच्चय A से वास्तविक संख्या तक

मांग: तत्व x₀ ∈ A ऐसा है कि f(x₀) ≤ f(x) सभी x ∈ A (कम से कम) के लिए या f(x₀) ≥ f(x) सभी x ∈ A (अधिकतमकरण) के लिए।

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

चूंकि निम्नलिखित मान्य है

$f\left(\mathbf {x} _{0}\right)\geq f\left(\mathbf {x} \right)\Leftrightarrow {\tilde {f}}\left(\mathbf {x} _{0}\right)\leq {\tilde {f}}\left(\mathbf {x} \right)$

यह केवल न्यूनीकरण की समस्याओं को हल करने के लिए पर्याप्त है। हालाँकि, केवल अधिकतमकरण की समस्याओं पर विचार करने का विपरीत परिप्रेक्ष्य भी मान्य होगा।

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

आमतौर पर, A यूक्लिडियन स्पेस ℝⁿ का सबसमुच्चय है, जो अक्सर बाधाओं, समानता या असमानताओं के समुच्चय द्वारा निर्दिष्ट होता है जिसे A के सदस्यों को संतुष्ट करना होता है। फलन f के डोमेन A को खोज स्थान या विकल्प समुच्चय कहा जाता है, जबकि A के तत्व उम्मीदवार समाधान या व्यवहार्य समाधान कहा जाता है।

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

गणित में, पारंपरिक अनुकूलन समस्याएं आमतौर पर न्यूनतमकरण के संदर्भ में बताई जाती हैं।

स्थानीय न्यूनतम x* तत्व के रूप में परिभाषित किया गया है जिसके लिए कुछ δ > 0 मौजूद ऐसा है कि$\forall \mathbf {x} \in A\;{\text{where}}\;\left\Vert \mathbf {x} -\mathbf {x} ^{\ast }\right\Vert \leq \delta ,\,$

व्यंजक f(x*) ≤ f(x) धारण करता है;

यानी, x* के आस-पास के किसी क्षेत्र पर सभी फलन मान उस तत्व के मान से अधिक या उसके बराबर हैं। स्थानीय मैक्सिमा को समान रूप से परिभाषित किया गया है।

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

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

संकेतन

अनुकूलन समस्याओं को अक्सर विशेष संकेतन के साथ व्यक्त किया जाता है। यहां कुछ उदाहरण दिए गए हैं:

फलन का न्यूनतम और अधिकतम मूल्य

निम्नलिखित संकेतन पर विचार करें:

$\min _{x\in \mathbb {R} }\;\left(x^{2}+1\right)$

यह उद्देश्य फलन x² + 1 के न्यूनतम मान को दर्शाता है, जब वास्तविक संख्याओं ℝ के समुच्चय में से x का चयन करते है। इस मामले में न्यूनतम मूल्य 1 है, जो x = 0 पर घटित होता है।

इसी तरह, संकेतन

$\max _{x\in \mathbb {R} }\;2x$

उद्देश्य फलन 2x का अधिकतम मान माँगता है, जहाँ पे x कोई भी वास्तविक संख्या हो सकती है। इस मामले में, ऐसा कोई अधिकतम नहीं है क्योंकि उद्देश्य फलन असीमित है, इसलिए इसका उत्तर "अनंत" या "अपरिभाषित" है।

इष्टतम निवेश तर्क

निम्नलिखित संकेतन पर विचार करें:

${\underset {x\in (-\infty ,-1]}{\operatorname {arg\,min} }}\;x^{2}+1,$

या समकक्ष रूप से

${\underset {x}{\operatorname {arg\,min} }}\;x^{2}+1,\;{\text{subject to:}}\;x\in (-\infty ,-1].$

यह अंतराल (−∞,−1] में तर्क x के मान (या मूल्यों) का प्रतिनिधित्व करता है, उद्देश्य फलन x² + 1 को कम (या कम से कम) करता है (उस फलन का वास्तविक न्यूनतम मूल्य वह नहीं है जो समस्या में पूछा जाता है)। इस मामले में, जवाब x = −1 है, क्योंकि x = 0 अव्यवहार्य है, अर्थात, यह व्यवहार्य समुच्चय से संबंधित नहीं है।

इसी तरह,

${\underset {x\in [-5,5],\;y\in \mathbb {R} }{\operatorname {arg\,max} }}\;x\cos y,$

या समकक्ष रूप से

${\underset {x,\;y}{\operatorname {arg\,max} }}\;x\cos y,\;{\text{subject to:}}\;x\in [-5,5],\;y\in \mathbb {R} ,$

{x, y} जोड़ी (या जोड़े) का प्रतिनिधित्व करता है जो उद्देश्य फलन x cos y के मान को उस अतिरिक्त बाधा के साथ अधिकतम करता है, जो x अंतराल [−5,5] में स्थित है (फिर से, अभिव्यक्ति का वास्तविक अधिकतम मूल्य मायने नहीं रखता)। इस मामले में, समाधान {5, 2kπ} और {5, 2kπ} के रूप के जोड़े हैं, जहां k सभी पूर्णांक पर है।

ऑपरेटर्स arg min और arg max को कभी -कभी argmin और argmax भी लिखा जाता है, और यह न्यूनतम और अधिकतम के तर्क के लिए माने जाते हैं।

इतिहास

फर्मेट और लैग्रेंज ने ऑप्टिमा की पहचान के लिए कलन-आधारित सूत्र पाए, जबकि न्यूट और गॉस ने इष्टतम की ओर बढ़ने के लिए पुनरावृत्त तरीकों का प्रस्ताव दिया।

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