शिथिलीकरण (सन्निकटन)

गणितीय अनुकूलन और संबंधित क्षेत्रों में, विश्राम एक गणितीय मॉडल है। विश्राम एक कठिन समस्या का निकटवर्ती समस्या से एक अनुमान है जिसे हल करना आसान है। शांत समस्या का समाधान मूल समस्या के बारे में जानकारी प्रदान करता है।

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

परिभाषा

न्यूनतमकरण की समस्या में छूट

$z=\min\{c(x):x\in X\subseteq \mathbf {R} ^{n}\}$

फॉर्म की एक और न्यूनतमकरण समस्या है

$z_{R}=\min\{c_{R}(x):x\in X_{R}\subseteq \mathbf {R} ^{n}\}$

इन दो गुणों के साथ

1. $X_{R}\supseteq X$
2. $c_{R}(x)\leq c(x)$ सभी के लिए $x\in X$.

पहली संपत्ति बताती है कि मूल समस्या का व्यवहार्य डोमेन, शिथिल समस्या के व्यवहार्य डोमेन का एक उपसमूह है। दूसरी संपत्ति बताती है कि मूल समस्या का उद्देश्य-कार्य शिथिल समस्या के उद्देश्य-कार्य से अधिक या उसके बराबर है।

गुण

अगर $x^{*}$ तो, यह मूल समस्या का इष्टतम समाधान है $x^{*}\in X\subseteq X_{R}$ और $z=c(x^{*})\geq c_{R}(x^{*})\geq z_{R}$. इसलिए, $x^{*}\in X_{R}$ एक ऊपरी सीमा प्रदान करता है $z_{R}$.

यदि पिछली धारणाओं के अतिरिक्त, $c_{R}(x)=c(x)$, $\forall x\in X$, निम्नलिखित मानता है: यदि मूल समस्या के लिए आरामदेह समस्या का इष्टतम समाधान संभव है, तो यह मूल समस्या के लिए इष्टतम है।

कुछ विश्राम तकनीक

• रैखिक प्रोग्रामिंग विश्राम
• लैग्रेंजियन विश्राम
• अर्धनिश्चित विश्राम
• सरोगेट विश्राम और सरोगेट द्वंद्व

संदर्भ

• Buttazzo, G. (1989). Semicontinuity, Relaxation and Integral Representation in the Calculus of Variations. Pitman Res. Notes in Math. 207. Harlow: Longmann.
• Geoffrion, A. M. (1971). "Duality in Nonlinear Programming: A Simplified Applications-Oriented Development". SIAM Review. 13 (1): 1–37. JSTOR 2028848.
• Goffin, J.-L. (1980). "The relaxation method for solving systems of linear inequalities". Math. Oper. Res. 5 (3): 388–414. doi:10.1287/moor.5.3.388. JSTOR 3689446. MR 0594854.
• Minoux, M. (1986). Mathematical programming: Theory and algorithms. Chichester: A Wiley-Interscience Publication. John Wiley & Sons. ISBN 978-0-471-90170-9. MR 0868279. Translated by Steven Vajda from Programmation mathématique: Théorie et algorithmes. Paris: Dunod. 1983. MR 2571910.
• Murty, Katta G. (1983). "16 Iterative methods for linear inequalities and linear programs (especially 16.2 Relaxation methods, and 16.4 Sparsity-preserving iterative SOR algorithms for linear programming)". Linear programming. New York: John Wiley & Sons. ISBN 978-0-471-09725-9. MR 0720547.
• Nemhauser, G. L.; Rinnooy Kan, A. H. G.; Todd, M. J., eds. (1989). Optimization. Handbooks in Operations Research and Management Science. Vol. 1. Amsterdam: North-Holland Publishing Co. ISBN 978-0-444-87284-5. MR 1105099.
  • W. R. Pulleyblank, Polyhedral combinatorics (pp. 371–446);
  • George L. Nemhauser and Laurence A. Wolsey, Integer programming (pp. 447–527);
  • Claude Lemaréchal, Nondifferentiable optimization (pp. 529–572);
• Rardin, Ronald L. (1998). Optimization in operations research. Prentice Hall. ISBN 978-0-02-398415-0.
• Roubíček, T. (1997). Relaxation in Optimization Theory and Variational Calculus. Berlin: Walter de Gruyter. ISBN 978-3-11-014542-7.