द्वैत (अनुकूलन)

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

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

दोहरी समस्या

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

सामान्यतः पर अलग-अलग जगहों के दो दोहरे जोड़े स्थानीय रूप से उत्तल स्थान होते हैं $\left(X,X^{*}\right)$ और $\left(Y,Y^{*}\right)$ और समारोह $f:X\to \mathbb {R} \cup \{+\infty \}$, हम प्राथमिक समस्या को खोजने के रूप में परिभाषित कर सकते हैं ${\hat {x}}$ ऐसा है कि $f({\hat {x}})=\inf _{x\in X}f(x).\,$

दूसरे शब्दों में, अगर ${\hat {x}}$ उपस्थित, $f({\hat {x}})$ समारोह का न्यूनतम है $f$ और फ़ंक्शन की न्यूनतम (सबसे बड़ी निचली सीमा) प्राप्त की जाती है।

यदि बाधा की स्थिति है, तो इन्हें फ़ंक्शन में बनाया जा सकता है $f$ जैसे भी हो ${\tilde {f}}=f+I_{\mathrm {constraints} }$ कहाँ $I_{\mathrm {constraints} }$ पर उपयुक्त कार्य है $X$ इसकी बाधाओं पर न्यूनतम 0 है, और जिसके लिए कोई यह सिद्ध कर सकता है $\inf _{x\in X}{\tilde {f}}(x)=\inf _{x\ \mathrm {constrained} }f(x)$. बाद की स्थिति तुच्छ है, लेकिन हमेशा सुविधाजनक नहीं है, विशेषता कार्य (उत्तल विश्लेषण) के लिए संतुष्ट (यानी। $I_{\mathrm {constraints} }(x)=0$ के लिए $x$ बाधाओं को पूरा करना और $I_{\mathrm {constraints} }(x)=\infty$ अन्यथा)। फिर विस्तार करें ${\tilde {f}}$ एक बाधा समारोह के लिए $F:X\times Y\to \mathbb {R} \cup \{+\infty \}$ ऐसा है कि $F(x,0)={\tilde {f}}(x)$.

द्वैत अंतर असमानता के दाएं और बाएं हाथ के पक्षों का अंतर है

$\sup _{y^{*}\in Y^{*}}-F^{*}(0,y^{*})\leq \inf _{x\in X}F(x,0),\,$

कहाँ $F^{*}$ दोनों चर में उत्तल संयुग्म है और $\sup$ अंतिम (कम से कम ऊपरी सीमा) को दर्शाता है।

द्वैत अंतराल

Main article: द्वैत अंतराल

द्वैत अंतर किसी भी मूल समाधान और किसी भी दोहरे समाधान के मूल्यों के बीच का अंतर है। अगर $d^{*}$ इष्टतम दोहरा मूल्य है और $p^{*}$ इष्टतम प्रारंभिक मान है, तो द्वैत अंतर बराबर है $p^{*}-d^{*}$. यह मान हमेशा 0 से अधिक या उसके बराबर होता है (न्यूनतम समस्याओं के लिए)। द्वैत अंतर शून्य है अगर और केवल अगर मजबूत द्वैत धारण करता है। अन्यथा अंतराल सख्ती से सकारात्मक है और कमजोर द्वैत धारण करता है।

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

रैखिक मामला

Main article: दोहरी रैखिक कार्यक्रम

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

दोहरी समस्या में, उद्देश्य फलन m मानों का एक रैखिक संयोजन है जो प्राथमिक समस्या से m बाधाओं में सीमाएँ हैं। n दोहरी बाधाएँ हैं, जिनमें से प्रत्येक m दोहरे चर के एक रैखिक संयोजन पर एक निचली सीमा रखती है।

प्राथमिक समस्या और दोहरी समस्या के बीच संबंध

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

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

इस अंतर्ज्ञान को रैखिक प्रोग्रामिंग # द्वैत में समीकरणों द्वारा औपचारिक बनाया गया है। रैखिक प्रोग्रामिंग: द्वैत।

नॉनलाइनियर केस

गैर-रैखिक प्रोग्रामिंग में, बाधाएँ आवश्यक रूप से रैखिक नहीं होती हैं। बहरहाल, कई समान सिद्धांत लागू होते हैं।

यह सुनिश्चित करने के लिए कि एक गैर-रैखिक समस्या की वैश्विक अधिकतम पहचान आसानी से की जा सकती है, समस्या निर्माण के लिए अधिकांशतः यह आवश्यक होता है कि कार्य उत्तल हों और कॉम्पैक्ट निचले स्तर के सेट हों।

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

मजबूत Lagrangian सिद्धांत: Lagrange द्वैत

मानक रूप में एक अरेखीय प्रोग्रामिंग समस्या को देखते हुए

${\begin{aligned}{\text{minimize }}&f_{0}(x)\\{\text{subject to }}&f_{i}(x)\leq 0,\ i\in \left\{1,\ldots ,m\right\}\\&h_{i}(x)=0,\ i\in \left\{1,\ldots ,p\right\}\end{aligned}}$

डोमेन के साथ ${\mathcal {D}}\subset \mathbb {R} ^{n}$ गैर-खाली इंटीरियर, Lagrangian समारोह ${\mathcal {L}}:\mathbb {R} ^{n}\times \mathbb {R} ^{m}\times \mathbb {R} ^{p}\to \mathbb {R}$ परिभाषित किया जाता है

${\mathcal {L}}(x,\lambda ,\nu )=f_{0}(x)+\sum _{i=1}^{m}\lambda _{i}f_{i}(x)+\sum _{i=1}^{p}\nu _{i}h_{i}(x).$

वैक्टर $\lambda$ और $\nu$ समस्या से जुड़े दोहरे चर या लैग्रेंज गुणक वैक्टर कहलाते हैं। लैग्रेंज डुअल फंक्शन $g:\mathbb {R} ^{m}\times \mathbb {R} ^{p}\to \mathbb {R}$ परिभाषित किया जाता है

$g(\lambda ,\nu )=\inf _{x\in {\mathcal {D}}}{\mathcal {L}}(x,\lambda ,\nu )=\inf _{x\in {\mathcal {D}}}\left\{f_{0}(x)+\sum _{i=1}^{m}\lambda _{i}f_{i}(x)+\sum _{i=1}^{p}\nu _{i}h_{i}(x)\right\}.$

दोहरी कार्य g अवतल है, तब भी जब प्रारंभिक समस्या उत्तल नहीं है, क्योंकि यह affine कार्यों का एक बिंदु-वार infimum है। दोहरे कार्य से इष्टतम मान पर निचली सीमाएं प्राप्त होती हैं $p^{*}$ प्रारंभिक समस्या का; किसी के लिए $\lambda \geq 0$ और कोई भी $\nu$ अपने पास $g(\lambda ,\nu )\leq p^{*}$.

यदि स्लेटर की स्थिति जैसी बाधा योग्यता रखती है और मूल समस्या उत्तल है, तो हमारे पास मजबूत द्वंद्व है, यानी। $d^{*}=\max _{\lambda \geq 0,\nu }g(\lambda ,\nu )=\inf f_{0}=p^{*}$.

उत्तल समस्याएं

असमानता बाधाओं के साथ उत्तल न्यूनीकरण समस्या के लिए,

${\begin{aligned}&{\underset {x}{\operatorname {minimize} }}&&f(x)\\&\operatorname {subject\;to} &&g_{i}(x)\leq 0,\quad i=1,\ldots ,m\end{aligned}}$

Lagrangian दोहरी समस्या है

${\begin{aligned}&{\underset {u}{\operatorname {maximize} }}&&\inf _{x}\left(f(x)+\sum _{j=1}^{m}u_{j}g_{j}(x)\right)\\&\operatorname {subject\;to} &&u_{i}\geq 0,\quad i=1,\ldots ,m\end{aligned}}$

जहाँ वस्तुनिष्ठ फलन लैग्रेंज दोहरा फलन है। बशर्ते कि कार्य करता है $f$ और $g_{1},\ldots ,g_{m}$ लगातार अलग-अलग होते हैं, कम होता है जहां ग्रेडिएंट शून्य के बराबर होता है। समस्या

${\begin{aligned}&{\underset {x,u}{\operatorname {maximize} }}&&f(x)+\sum _{j=1}^{m}u_{j}g_{j}(x)\\&\operatorname {subject\;to} &&\nabla f(x)+\sum _{j=1}^{m}u_{j}\,\nabla g_{j}(x)=0\\&&&u_{i}\geq 0,\quad i=1,\ldots ,m\end{aligned}}$

वोल्फ दोहरी समस्या कहा जाता है। कम्प्यूटेशनल रूप से इस समस्या से निपटना मुश्किल हो सकता है, क्योंकि संयुक्त चर में उद्देश्य फ़ंक्शन अवतल नहीं है $(u,x)$. साथ ही, समानता की बाधा $\nabla f(x)+\sum _{j=1}^{m}u_{j}\,\nabla g_{j}(x)$ सामान्य रूप से अरेखीय है, इसलिए वोल्फ दोहरी समस्या सामान्यतःपर एक गैर-उत्तल अनुकूलन समस्या है। किसी भी मामले में, कमजोर द्वंद्व धारण करता है।

इतिहास

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

यह भी देखें

• उत्तल द्वैत
• द्वैत (गणित)
• विश्राम (सन्निकटन)

संदर्भ

पुस्तकें

• Ahuja, Ravindra K.; Magnanti, Thomas L.; Orlin, James B. (1993). नेटवर्क प्रवाह: सिद्धांत, एल्गोरिदम और अनुप्रयोग. Prentice Hall. ISBN 0-13-617549-X.
• Bertsekas, Dimitri; Nedic, Angelia; Ozdaglar, Asuman (2003). उत्तल विश्लेषण और अनुकूलन. Athena Scientific. ISBN 1-886529-45-0.
• Bertsekas, Dimitri P. (1999). नॉनलाइनियर प्रोग्रामिंग (2nd ed.). Athena Scientific. ISBN 1-886529-00-0.
• Bertsekas, Dimitri P. (2009). उत्तल अनुकूलन सिद्धांत. Athena Scientific. ISBN 978-1-886529-31-1.
• Bonnans, J. Frédéric; Gilbert, J. Charles; Lemaréchal, Claude; Sagastizábal, Claudia A. (2006). संख्यात्मक अनुकूलन: सैद्धांतिक और व्यावहारिक पहलू. 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 3-540-35445-X. MR 2265882.
• Cook, William J.; Cunningham, William H.; Pulleyblank, William R.; Schrijver, Alexander (November 12, 1997). संयुक्त अनुकूलन (1st ed.). John Wiley & Sons. ISBN 0-471-55894-X.
• Dantzig, George B. (1963). रैखिक प्रोग्रामिंग और एक्सटेंशन. Princeton, NJ: Princeton University Press.
• Hiriart-Urruty, Jean-Baptiste; Lemaréchal, Claude (1993). उत्तल विश्लेषण और न्यूनीकरण एल्गोरिदम, खंड I: बुनियादी सिद्धांत. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. Vol. 305. Berlin: Springer-Verlag. pp. xviii+417. ISBN 3-540-56850-6. MR 1261420.
• Hiriart-Urruty, Jean-Baptiste; Lemaréchal, Claude (1993). "14 Duality for Practitioners". उत्तल विश्लेषण और न्यूनीकरण एल्गोरिदम, खंड II: उन्नत सिद्धांत और बंडल विधियां. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. Vol. 306. Berlin: Springer-Verlag. pp. xviii+346. ISBN 3-540-56852-2. MR 1295240.
• Lasdon, Leon S. (2002) [Reprint of the 1970 Macmillan]. बड़ी प्रणालियों के लिए अनुकूलन सिद्धांत. Mineola, New York: Dover Publications, Inc. pp. xiii+523. ISBN 978-0-486-41999-2. MR 1888251.
• Lawler, Eugene (2001). "4.5. Combinatorial Implications of Max-Flow Min-Cut Theorem, 4.6. Linear Programming Interpretation of Max-Flow Min-Cut Theorem". कॉम्बिनेटरियल ऑप्टिमाइज़ेशन: नेटवर्क और मैट्रोइड्स. Dover. pp. 117–120. ISBN 0-486-41453-1.
• Lemaréchal, Claude (2001). "Lagrangian relaxation". In Jünger, Michael; Naddef, Denis (eds.). कम्प्यूटेशनल कॉम्बिनेटरियल ऑप्टिमाइज़ेशन: 15-19 मई, 2000 को श्लॉ डगस्टुहल में आयोजित स्प्रिंग स्कूल के पेपर. Lecture Notes in Computer Science (LNCS). Vol. 2241. Berlin: Springer-Verlag. pp. 112–156. doi:10.1007/3-540-45586-8_4. ISBN 3-540-42877-1. MR 1900016. S2CID 9048698.
• Minoux, Michel (1986). गणितीय प्रोग्रामिंग: सिद्धांत और एल्गोरिदम. Egon Balas (forward); Steven Vajda (trans) from the (1983 Paris: Dunod) French. Chichester: A Wiley-Interscience Publication. John Wiley & Sons, Ltd. pp. xxviii+489. ISBN 0-471-90170-9. MR 0868279. (2008 Second ed., in French: Programmation mathématique : Théorie et algorithmes, Éditions Tec & Doc, Paris, 2008. xxx+711 pp. )).
• Nering, Evar D.; Tucker, Albert W. (1993). रैखिक प्रोग्रामिंग और संबंधित समस्याएं. Boston, MA: Academic Press. ISBN 978-0-12-515440-6.
• Papadimitriou, Christos H.; Steiglitz, Kenneth (July 1998). कॉम्बिनेटरियल ऑप्टिमाइज़ेशन: एल्गोरिदम और जटिलता (Unabridged ed.). Dover. ISBN 0-486-40258-4.
• Ruszczyński, Andrzej (2006). गैर रेखीय अनुकूलन. Princeton, NJ: Princeton University Press. pp. xii+454. ISBN 978-0691119151. MR 2199043.

लेख

• Everett, Hugh, III (1963). "संसाधनों के इष्टतम आवंटन की समस्याओं को हल करने के लिए सामान्यीकृत लैग्रेंज गुणक विधि". Operations Research. 11 (3): 399–417. doi:10.1287/opre.11.3.399. JSTOR 168028. MR 0152360. Archived from the original on 2011-07-24.{{cite journal}}: CS1 maint: multiple names: authors list (link)
• Kiwiel, Krzysztof C.; Larsson, Torbjörn; Lindberg, P. O. (August 2007). "बॉलस्टेप सबग्रेडिएंट विधियों के माध्यम से लैग्रैन्जियन विश्राम". Mathematics of Operations Research. 32 (3): 669–686. doi:10.1287/moor.1070.0261. MR 2348241.
• रैखिक प्रोग्रामिंग में द्वंद्व गैरी डी. नॉट

श्रेणी:उत्तल अनुकूलन श्रेणी:रैखिक प्रोग्रामिंग