शिथिलीकरण (सन्निकटन): Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
 
(6 intermediate revisions by 4 users not shown)
Line 1: Line 1:
[[गणितीय अनुकूलन]] और संबंधित क्षेत्रों में, '''सन्निकटन''' एक मॉडलिंग रणनीति है। सन्निकटन किसी कठिन समस्या का निकट की समस्या से अनुमान लगाना है जिसे हल करना आसान है। सन्निकट समस्या का समाधान मूल समस्या के बारे में जानकारी प्रदान करता है।
[[गणितीय अनुकूलन]] और संबंधित क्षेत्रों में, '''सन्निकटन''' एक मॉडलिंग युक्ति है। सन्निकटन किसी कठिन समस्या का निकट की समस्या से अनुमान लगाना है जिसे हल करना आसान है। सन्निकट समस्या का समाधान मूल समस्या के बारे में जानकारी प्रदान करता है।


उदाहरण के लिए, एक [[पूर्णांक प्रोग्रामिंग]] समस्या का एक [[रैखिक प्रोग्रामिंग]] सन्निकटन अभिन्नता समस्या को हटा देता है और इस प्रकार गैर-पूर्णांक तर्कसंगत समाधान की अनुमति देता है। कॉम्बिनेटरियल अनुकूलन में एक जटिल समस्या की लैग्रेंजियन छूट कुछ बाधाओं के उल्लंघन को दंडित करती है, जिससे एक आसान आराम वाली समस्या हल हो जाती है। सन्निकटन तकनीक संयोजनात्मक अनुकूलन की शाखा और बाध्य एल्गोरिदम को पूरक या पूरक करती है; पूर्णांक प्रोग्रामिंग के लिए शाखा-और-बाउंड एल्गोरिदम में सीमाएं प्राप्त करने के लिए रैखिक प्रोग्रामिंग और [[लैग्रेंजियन विश्राम|लैग्रेंजियन सन्निकटन]] का उपयोग किया जाता है।<ref name="Geoff">{{harvtxt|Geoffrion|1971}}</ref>
उदाहरण के लिए, एक [[पूर्णांक प्रोग्रामिंग]] समस्या का एक [[रैखिक प्रोग्रामिंग]] सन्निकटन अभिन्नता समस्या को हटा देता है और इस प्रकार गैर-पूर्णांक तर्कसंगत समाधान की अनुमति देता है। कॉम्बिनेटरियल अनुकूलन में एक जटिल समस्या की लैग्रेंजियन सन्निकटन कुछ बाधाओं के प्रतिबंधों को निरस्त करता है, जिससे एक आसान सन्निकट वाली समस्या हल हो जाती है। सन्निकटन तकनीक संयोजनात्मक अनुकूलन की शाखा और बाध्य एल्गोरिदम को पूरक या अनुपूरक करती है; पूर्णांक प्रोग्रामिंग के लिए शाखा-और-बाउंड एल्गोरिदम में सीमाएं प्राप्त करने के लिए रैखिक प्रोग्रामिंग और [[लैग्रेंजियन विश्राम|लैग्रेंजियन सन्निकटन]] का उपयोग किया जाता है।<ref name="Geoff">{{harvtxt|Geoffrion|1971}}</ref>


सन्निकटन की मॉडलिंग कार्यनीति को सन्निकटन के पुनरावृत्त विधियों के साथ भ्रमित नहीं किया जाना चाहिए, जैसे कि [[क्रमिक अति-विश्राम|क्रमिक अति-सन्निकटन]] (एसओआर); विभेदक समीकरणों, रैखिक न्यूनतम-वर्गों और रैखिक प्रोग्रामिंग में समस्याओं को हल करने में सन्निकटन की पुनरावृत्तीय विधियों का उपयोग किया जाता है।{{sfnp|Goffin|1980}}{{sfnp|Murty|1983|pp=453–464}}{{sfnp|Minoux|1986}} हालाँकि, लैग्रेन्जियन सन्निकटन को हल करने के लिए सन्निकटन के पुनरावृत्त तरीकों का उपयोग किया गया है।{{efn|Relaxation methods for finding feasible solutions to linear inequality systems arise in linear programming and in Lagrangian relaxation. {{sfnp|Goffin|1980}}{{sfnp|Minoux|1986|loc=Section 4.3.7, pp. 120–123}}<ref>[[Shmuel Agmon]] (1954)</ref><ref>[[Theodore Motzkin]] and [[Isaac Schoenberg]] (1954)</ref><ref>L. T. Gubin, Boris T. Polyak, and E. V. Raik (1969)</ref>}}
सन्निकटन की मॉडलिंग कार्यनीति को सन्निकटन के पुनरावृत्त विधियों के साथ भ्रमित नहीं किया जाना चाहिए, जैसे कि [[क्रमिक अति-विश्राम|क्रमिक अति-सन्निकटन]] (एसओआर); विभेदक समीकरणों, रैखिक न्यूनतम-वर्गों और रैखिक प्रोग्रामिंग में समस्याओं को हल करने में सन्निकटन की पुनरावृत्तीय विधियों का उपयोग किया जाता है।{{sfnp|Goffin|1980}}{{sfnp|Murty|1983|pp=453–464}}{{sfnp|Minoux|1986}} हालाँकि, लैग्रेन्जियन सन्निकटन को हल करने के लिए सन्निकटन के पुनरावृत्त तरीकों का उपयोग किया गया है।{{efn|Relaxation methods for finding feasible solutions to linear inequality systems arise in linear programming and in Lagrangian relaxation. {{sfnp|Goffin|1980}}{{sfnp|Minoux|1986|loc=Section 4.3.7, pp. 120–123}}<ref>[[Shmuel Agmon]] (1954)</ref><ref>[[Theodore Motzkin]] and [[Isaac Schoenberg]] (1954)</ref><ref>L. T. Gubin, Boris T. Polyak, and E. V. Raik (1969)</ref>}}


== परिभाषा ==
== परिभाषा ==
न्यूनतमकरण की समस्या में सन्निकटन
न्यूनतमकरण की समस्या में ''सन्निकटन''


: <math>z = \min \{c(x) : x \in X \subseteq \mathbf{R}^{n}\}</math>
: <math>z = \min \{c(x) : x \in X \subseteq \mathbf{R}^{n}\}</math>
Line 17: Line 17:
# <math>c_R(x) \leq c(x)</math> सभी के लिए <math>x \in X</math>.
# <math>c_R(x) \leq c(x)</math> सभी के लिए <math>x \in X</math>.


पहली संपत्ति बताती है कि मूल समस्या का व्यवहार्य डोमेन, शिथिल समस्या के व्यवहार्य डोमेन का एक उपसमूह है। दूसरी संपत्ति बताती है कि मूल समस्या का उद्देश्य-कार्य शिथिल समस्या के उद्देश्य-कार्य से अधिक या उसके बराबर है।<ref name="Geoff"/>
पहली गुण बताती है कि मूल समस्या का व्यवहार्य डोमेन, शिथिल समस्या के व्यवहार्य डोमेन का एक उपसमूह है। दूसरा गुण बताती है कि मूल समस्या का उद्देश्य-कार्य सन्निकट समस्या के उद्देश्य-कार्य से अधिक या उसके बराबर है।<ref name="Geoff"/>
 
 
 
===गुण===
===गुण===
अगर <math>x^*</math> तो, यह मूल समस्या का इष्टतम समाधान है <math>x^* \in X \subseteq X_R</math> और <math>z = c(x^*) \geq c_R(x^*)\geq z_R</math>. इसलिए, <math>x^* \in X_R</math> एक ऊपरी सीमा प्रदान करता है <math>z_R</math>.
<math>x^*</math> मूल समस्या का इष्टतम समाधान है, तो <math>x^* \in X \subseteq X_R</math> और <math>z = c(x^*) \geq c_R(x^*)\geq z_R</math>इसलिए, <math>x^* \in X_R</math>, <math>z_R</math> पर ऊपरी सीमा प्रदान करता है।
 
यदि पिछली धारणाओं के अतिरिक्त, <math>c_R(x)=c(x)</math>, <math>\forall x\in X</math>, निम्नलिखित मानता है: यदि मूल समस्या के लिए आरामदेह समस्या का इष्टतम समाधान संभव है, तो यह मूल समस्या के लिए इष्टतम है।<ref name="Geoff"/>
 


यदि पिछली धारणाओं के अलावा, <math>c_R(x)=c(x)</math>,<math>\forall x\in X</math>, तो निम्नलिखित मान्य है: यदि मूल समस्या के लिए सन्निकटन समस्या का इष्टतम समाधान संभव है , तो यह मूल समस्या के लिए इष्टतम है।<ref name="Geoff"/>
==कुछ सन्निकटन तकनीक==
==कुछ सन्निकटन तकनीक==
*[[रैखिक प्रोग्रामिंग विश्राम|रैखिक प्रोग्रामिंग सन्निकटन]]
*[[रैखिक प्रोग्रामिंग विश्राम|रैखिक प्रोग्रामिंग सन्निकटन]]
Line 32: Line 27:
<!-- NO this is an ITERATIVE METHOD, not a relaxation strategy,  *[[Successive over-relaxation]] -->
<!-- NO this is an ITERATIVE METHOD, not a relaxation strategy,  *[[Successive over-relaxation]] -->
*[[अर्धनिश्चित विश्राम|अर्धनिश्चित सन्निकटन]]
*[[अर्धनिश्चित विश्राम|अर्धनिश्चित सन्निकटन]]
* [[सरोगेट विश्राम|सरोगेट सन्निकटन]] और सरोगेट द्वंद्व
* [[सरोगेट विश्राम|सरोगेट सन्निकटन]] और द्विभाजन


==टिप्पणियाँ==
==टिप्पणियाँ==
{{notelist}}
{{notelist}}
{{reflist}}
{{reflist}}
==संदर्भ==
==संदर्भ==
* {{cite book|author=Buttazzo |first=G. |title = Semicontinuity, Relaxation and Integral Representation in the Calculus of Variations |series=Pitman Res. Notes in Math. 207|publisher=Longmann|location=Harlow |year=1989}}
* {{cite book|author=Buttazzo |first=G. |title = Semicontinuity, Relaxation and Integral Representation in the Calculus of Variations |series=Pitman Res. Notes in Math. 207|publisher=Longmann|location=Harlow |year=1989}}
Line 59: Line 52:
* {{cite book|title=Relaxation in Optimization Theory and Variational Calculus|last=Roubíček|first=T.|publisher=Walter de Gruyter|location=Berlin|year=1997|isbn=978-3-11-014542-7}}
* {{cite book|title=Relaxation in Optimization Theory and Variational Calculus|last=Roubíček|first=T.|publisher=Walter de Gruyter|location=Berlin|year=1997|isbn=978-3-11-014542-7}}


{{DEFAULTSORT:Relaxation (Approximation)}}[[Category: विश्राम (अनुमान)| विश्राम]] [[Category: गणितीय अनुकूलन]] [[Category: अनुमान]]
{{DEFAULTSORT:Relaxation (Approximation)}}
 
 


[[Category: Machine Translated Page]]
[[Category:Created On 09/08/2023|Relaxation (Approximation)]]
[[Category:Created On 09/08/2023]]
[[Category:Machine Translated Page|Relaxation (Approximation)]]
[[Category:Pages with script errors|Relaxation (Approximation)]]
[[Category:Templates Vigyan Ready|Relaxation (Approximation)]]
[[Category:अनुमान|Relaxation (Approximation)]]
[[Category:गणितीय अनुकूलन|Relaxation (Approximation)]]
[[Category:विश्राम (अनुमान)| विश्राम]]

Latest revision as of 16:55, 21 August 2023

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

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

सन्निकटन की मॉडलिंग कार्यनीति को सन्निकटन के पुनरावृत्त विधियों के साथ भ्रमित नहीं किया जाना चाहिए, जैसे कि क्रमिक अति-सन्निकटन (एसओआर); विभेदक समीकरणों, रैखिक न्यूनतम-वर्गों और रैखिक प्रोग्रामिंग में समस्याओं को हल करने में सन्निकटन की पुनरावृत्तीय विधियों का उपयोग किया जाता है।[2][3][4] हालाँकि, लैग्रेन्जियन सन्निकटन को हल करने के लिए सन्निकटन के पुनरावृत्त तरीकों का उपयोग किया गया है।[lower-alpha 1]

परिभाषा

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

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

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

  2. सभी के लिए .

पहली गुण बताती है कि मूल समस्या का व्यवहार्य डोमेन, शिथिल समस्या के व्यवहार्य डोमेन का एक उपसमूह है। दूसरा गुण बताती है कि मूल समस्या का उद्देश्य-कार्य सन्निकट समस्या के उद्देश्य-कार्य से अधिक या उसके बराबर है।[1]

गुण

मूल समस्या का इष्टतम समाधान है, तो और इसलिए, , पर ऊपरी सीमा प्रदान करता है।

यदि पिछली धारणाओं के अलावा, ,, तो निम्नलिखित मान्य है: यदि मूल समस्या के लिए सन्निकटन समस्या का इष्टतम समाधान संभव है , तो यह मूल समस्या के लिए इष्टतम है।[1]

कुछ सन्निकटन तकनीक

टिप्पणियाँ

  1. ↑ Relaxation methods for finding feasible solutions to linear inequality systems arise in linear programming and in Lagrangian relaxation. [2][5][6][7][8]
  1. ↑ 1.0 1.1 1.2 Geoffrion (1971)
  2. ↑ 2.0 2.1 Goffin (1980).
  3. ↑ Murty (1983), pp. 453–464.
  4. ↑ Minoux (1986).
  5. ↑ Minoux (1986), Section 4.3.7, pp. 120–123.
  6. ↑ Shmuel Agmon (1954)
  7. ↑ Theodore Motzkin and Isaac Schoenberg (1954)
  8. ↑ L. T. Gubin, Boris T. Polyak, and E. V. Raik (1969)

संदर्भ

  • 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.
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=शिथिलीकरण_(सन्निकटन)&oldid=251120’