अर्ध-न्यूटन विधि

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

शून्य के लिए खोजें: मूल अनुसंधान

किसी फलन का शून्य ज्ञात करने की न्यूटन विधि $g$ एकाधिक चर के द्वारा दिया जाता है $x_{n+1}=x_{n}-[J_{g}(x_{n})]^{-1}g(x_{n})$, जहाँ $[J_{g}(x_{n})]^{-1}$ जैकबियन मैट्रिक्स का व्युत्क्रम तत्व आव्यूह है, $J_{g}(x_{n})$ का $g$ के लिए मूल्यांकन किया गया $x_{n}$.

वास्तव में कोई भी विधि जो सटीक जैकोबियन को बदल देती है $J_{g}(x_{n})$ सन्निकटन के साथ अर्ध-न्यूटन विधि है। उदाहरण के लिए, राग विधि जहाँ $J_{g}(x_{n})$ द्वारा प्रतिस्थापित किया जाता है $J_{g}(x_{0})$ सभी पुनरावृत्तियों के लिए) साधारण उदाहरण है। एक्स्ट्रेमा के लिए खोजें नीचे दी गई विधियाँ अर्ध-न्यूटन विधियों के छेदक विधियों के महत्वपूर्ण उपवर्ग को संदर्भित करती हैं।शून्य को खोजने के लिए और एक्स्ट्रेमा को खोजने के लिए विकसित विधियों का उपयोग करना सदैव अच्छा विचार नहीं होता है, क्योंकि एक्स्ट्रेमा को खोजने के लिए उपयोग की जाने वाली अधिकांश विधियों के लिए आवश्यक है कि उपयोग किया जाने वाला मैट्रिक्स सममित हो। जबकि यह एक्स्ट्रेमा की खोज के संदर्भ में है, यह शून्य की खोज करते समय संभवतः ही कभी पकड़ में आता है। ब्रॉयडेन की विधि | ब्रोयडेन की अच्छी और खराब दो विधियाँ हैं जिनका उपयोग सामान्यतः एक्स्ट्रेमा खोजने के लिए किया जाता है जिसे शून्य खोजने के लिए भी लागू किया जा सकता है। जिन अन्य विधियों का उपयोग किया जा सकता है, वे हैं स्तंभ-अद्यतन विधि, व्युत्क्रम स्तंभ-अद्यतन विधि, अर्ध-न्यूटन न्यूनतम वर्ग विधि और अर्ध-न्यूटन व्युत्क्रम न्यूनतम वर्ग विधि।

जल्दी ही में अर्ध-न्यूटन विधियों को समीकरणों के कई युग्मित प्रणालियों के समाधान खोजने के लिए लागू किया गया है, उदाहरण के लिए द्रव-संरचना अन्योन्यक्रिया समस्याएं या भौतिकी में अंतःक्रियात्मक समस्याएं है। वे प्रत्येक घटक प्रणाली को अलग-अलग जो वैश्विक प्रणाली की तुलना में सरल है चक्रीय, पुनरावृत्त प्रकार में हल करके समाधान खोजने की अनुमति देते हैं जब तक कि वैश्विक प्रणाली का समाधान नहीं मिल जाता।

एक्सट्रीमा के लिए खोजें: अनुकूलन

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

अनुकूलन (गणित) में, अर्ध-न्यूटन विधियाँ चर-दशांश विधियों का विशेष स्थिति फ़ंक्शन गणित के स्थानीय मैक्सिमा और मिनिमा को खोजने के लिए कलन विधि हैं। अर्ध-न्यूटन विधियाँ अनुकूलन में न्यूटन विधि पर आधारित हैं। किसी फ़ंक्शन के स्थिर बिंदु को खोजने के लिए न्यूटन विधि , जहाँ प्रवणता 0 है। न्यूटन विधि मानती है कि फ़ंक्शन को अनुकूलतम के आसपास के क्षेत्र में द्विघात फ़ंक्शन के रूप में स्थानीय रूप से अनुमानित किया जा सकता है और स्थिर बिंदु खोजने के लिए पहले और दूसरे यौगिक का उपयोग करता है। उच्च आयामों में न्यूटन विधि फ़ंक्शन के दूसरे यौगिक के ढाल और हेस्सियन मैट्रिक्स का उपयोग कम करने के लिए करती है।

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

पहला अर्ध-न्यूटन कलन विधि विलियम सी. डेविडॉन द्वारा प्रस्तावित किया गया था, जो अग्रोने राष्ट्रीय प्रयोगशाला में कार्यरत भौतिक विज्ञानी थे। उन्होंने 1959 में पहला अर्ध-न्यूटन कलन विधि विकसित किया। DFP अद्यतन सूत्र, जिसे बाद में 1963 में फ्लेचर और पॉवेल द्वारा लोकप्रिय बनाया गया था, किन्तु आज संभवतः ही कभी इसका उपयोग किया जाता है। सबसे साधारण अर्ध-न्यूटन कलन विधि वर्तमान में SR1 सूत्र सममित रैंक-वन के लिए, BHHH विधि, व्यापक BFGS विधि 1970 में ब्रॉयडेन, फ्लेचर, गोल्डफार्ब और शन्नो द्वारा स्वतंत्र रूप से सुझाया गया, और इसकी कम-मेमोरी हैं विस्तार एल-बीएफजीएस। ब्रॉयडेन की कक्षा DFP और बीएफजीएस विधियों का रैखिक संयोजन है।

SR1 सूत्र सकारात्मक-निश्चित मैट्रिक्स को बनाए रखने के लिए अद्यतन मैट्रिक्स की गारंटी नहीं देता है। सकारात्मक-निश्चितता और अनिश्चित समस्याओं के लिए उपयोग किया जा सकता है। ब्रॉयडेन की विधि को अद्यतन मैट्रिक्स को सममित होने की आवश्यकता नहीं होती है। जैकबियन मैट्रिक्स और निर्धारक हेस्सियन के अतिरिक्त को अद्यतन करके समीकरणों की सामान्य प्रणाली ढाल के अतिरिक्त की मूल को खोजने के लिए उपयोग किया जाता है।

अनुकूलन में न्यूटन विधि पर अर्ध-न्यूटन विधियों के मुख्य लाभों में से न्यूटन की विधि यह है कि हेस्सियन मैट्रिक्स ,अर्ध-न्यूटन विधियों के स्थितियों में इसका सन्निकटन $B$ उलटने की जरूरत नहीं है। न्यूटन विधि और इसके यौगिक जैसे आंतरिक बिंदु विधियों के लिए हेस्सियन को उल्टा करने की आवश्यकता होती है, जिसे सामान्यतः रैखिक समीकरणों की प्रणाली को हल करके कार्यान्वित किया जाता है और अधिकांशतः बहुत बहुमूल्य होता है। इसके विपरीत अर्ध-न्यूटन विधियाँ सामान्यतः अनुमान $B^{-1}$ उत्पन्न करती हैं।

अनुकूलन में न्यूटन विधि के रूप में न्यूटन विधि , फ़ंक्शन का न्यूनतम पता लगाने के लिए दूसरे क्रम के सन्निकटन का उपयोग करता है $f(x)$. टेलर श्रृंखला $f(x)$ चारों ओर पुनरावृति है

$f(x_{k}+\Delta x)\approx f(x_{k})+\nabla f(x_{k})^{\mathrm {T} }\,\Delta x+{\frac {1}{2}}\Delta x^{\mathrm {T} }B\,\Delta x,$

जहाँ ($\nabla f$) ढाल है, और $B$ हेस्सियन मैट्रिक्स के लिए सन्निकटन। इस सन्निकटन का ढाल के संबंध में $\Delta x$ है,

$\nabla f(x_{k}+\Delta x)\approx \nabla f(x_{k})+B\,\Delta x,$

और इस ढाल को शून्य पर चयन करना जो अनुकूलन का लक्ष्य है न्यूटन चरण प्रदान करता है,

$\Delta x=-B^{-1}\nabla f(x_{k}).$

हेसियन सन्निकटन $B$ संतुष्ट करने के लिए चुना गया है,

$\nabla f(x_{k}+\Delta x)=\nabla f(x_{k})+B\,\Delta x,$

जिसे छेदक समीकरण प्रवणता की टेलर श्रृंखला कहा जाता है। एक से अधिक आयामों में $B$ अनिर्धारित प्रणाली है। आयाम के लिए हल करना $B$ और अद्यतन मूल्य के साथ न्यूटन के कदम को लागू करना छेदक विधि के बराबर है। विभिन्न अर्ध-न्यूटन विधियाँ छेदक समीकरण आयाम में सभी प्रकार समतुल्य हैं आयाम के समाधान की अपनी पसंद में भिन्न हैं। अधिकांश विधियाँ किन्तु अपवादों के साथ, जैसे कि ब्रॉयडेन की विधि सममित समाधान की खोज करती हैं ($B^{T}=B$); इसके अतिरिक्त, नीचे सूचीबद्ध प्रकार को अद्यतन पाकर प्रेरित किया जा सकता है $B_{k+1}$ यह जितना संभव हो उतना समीप है $B_{k}$ कुछ सामान्य (गणित) में; वह है, $B_{k+1}=\operatorname {argmin} _{B}\|B-B_{k}\|_{V}$, जहाँ $V$ कुछ सकारात्मक-निश्चित आव्यूह है जो आदर्श को परिभाषित करता है। अनुमानित प्रारंभिक मूल्य $B_{0}=\beta I$ तेजी से अभिसरण प्राप्त करने के लिए अधिकांशतः पर्याप्त होता है, चूंकि चुनने के लिए कोई सामान्य रणनीति नहीं होती है $\beta$. ध्यान दें कि $B_{0}$ सकारात्मक-निश्चित होना चाहिए। अनभिज्ञ $x_{k}$ वर्तमान सन्निकट हेस्सियन मैट्रिक्स का उपयोग करके गणना किए गए न्यूटन के कदम को लागू करते हुए अद्यतन किया गया है $B_{k}$:

• $\Delta x_{k}=-\alpha _{k}B_{k}^{-1}\nabla f(x_{k})$, साथ $\alpha$ वोल्फ की अवस्था को पूरा करने के लिए चुना गया,
• $x_{k+1}=x_{k}+\Delta x_{k}$;
• प्रवणता की गणना नए बिंदु पर की जाती है $\nabla f(x_{k+1})$, और

$y_{k}=\nabla f(x_{k+1})-\nabla f(x_{k})$

अनुमानित हेसियन को अद्यतन करने के लिए प्रयोग किया जाता है $B_{k+1}$, या सीधे इसका उलटा $H_{k+1}=B_{k+1}^{-1}$ शर्मन-मॉरिसन सूत्र का उपयोग करना।

• BFGS और DFP अद्यतनों की प्रमुख विशेषता यह है कि यदि $B_{k}$ सकारात्मक-निश्चित है, और $\alpha _{k}$ फिर वोल्फ की अवस्था को पूरा करने के लिए चुना जाता है $B_{k+1}$ सकारात्मक-निश्चित भी है।

सबसे लोकप्रिय अद्यतन सूत्र हैं:

Method	$\displaystyle B_{k+1}=$	$H_{k+1}=B_{k+1}^{-1}=$
BFGS	$B_{k}+{\frac {y_{k}y_{k}^{\mathrm {T} }}{y_{k}^{\mathrm {T} }\Delta x_{k}}}-{\frac {B_{k}\Delta x_{k}(B_{k}\Delta x_{k})^{\mathrm {T} }}{\Delta x_{k}^{\mathrm {T} }B_{k}\,\Delta x_{k}}}$	$\left(I-{\frac {\Delta x_{k}y_{k}^{\mathrm {T} }}{y_{k}^{\mathrm {T} }\Delta x_{k}}}\right)H_{k}\left(I-{\frac {y_{k}\Delta x_{k}^{\mathrm {T} }}{y_{k}^{\mathrm {T} }\Delta x_{k}}}\right)+{\frac {\Delta x_{k}\Delta x_{k}^{\mathrm {T} }}{y_{k}^{\mathrm {T} }\,\Delta x_{k}}}$
ब्रॉयडेन	$B_{k}+{\frac {y_{k}-B_{k}\Delta x_{k}}{\Delta x_{k}^{\mathrm {T} }\,\Delta x_{k}}}\,\Delta x_{k}^{\mathrm {T} }$	$H_{k}+{\frac {(\Delta x_{k}-H_{k}y_{k})\Delta x_{k}^{\mathrm {T} }H_{k}}{\Delta x_{k}^{\mathrm {T} }H_{k}\,y_{k}}}$
ब्रॉयडेन परिवार	$(1-\varphi _{k})B_{k+1}^{\text{BFGS}}+\varphi _{k}B_{k+1}^{\text{DFP}},\quad \varphi \in [0,1]$
DFP	$\left(I-{\frac {y_{k}\,\Delta x_{k}^{\mathrm {T} }}{y_{k}^{\mathrm {T} }\,\Delta x_{k}}}\right)B_{k}\left(I-{\frac {\Delta x_{k}y_{k}^{\mathrm {T} }}{y_{k}^{\mathrm {T} }\,\Delta x_{k}}}\right)+{\frac {y_{k}y_{k}^{\mathrm {T} }}{y_{k}^{\mathrm {T} }\,\Delta x_{k}}}$	$H_{k}+{\frac {\Delta x_{k}\Delta x_{k}^{\mathrm {T} }}{\Delta x_{k}^{\mathrm {T} }\,y_{k}}}-{\frac {H_{k}y_{k}y_{k}^{\mathrm {T} }H_{k}}{y_{k}^{\mathrm {T} }H_{k}y_{k}}}$
SR1	$B_{k}+{\frac {(y_{k}-B_{k}\,\Delta x_{k})(y_{k}-B_{k}\,\Delta x_{k})^{\mathrm {T} }}{(y_{k}-B_{k}\,\Delta x_{k})^{\mathrm {T} }\,\Delta x_{k}}}$	$H_{k}+{\frac {(\Delta x_{k}-H_{k}y_{k})(\Delta x_{k}-H_{k}y_{k})^{\mathrm {T} }}{(\Delta x_{k}-H_{k}y_{k})^{\mathrm {T} }y_{k}}}$

अन्य विधियाँ पियर्सन की विधि, मैककॉर्मिक की विधि, पॉवेल सममित ब्रॉयडेन (PSB) विधि और ग्रीनस्टेड की विधि हैं।

मैट्रिक्स व्युत्क्रम से संबंध

कब $f$ सकारात्मक-निश्चित हेस्सियन के साथ उत्तल द्विघात फलन है $B$, कोई मेट्रिसेस की अपेक्षा करेगा $H_{k}$ व्युत्क्रम हेसियन में अभिसरण करने के लिए अर्ध-न्यूटन विधि द्वारा उत्पन्न $H=B^{-1}$. यह वास्तव में कम से कम परिवर्तन अद्यतनों के आधार पर अर्ध-न्यूटन विधियों के वर्ग का स्थिति है।

उल्लेखनीय कार्यान्वयन

अर्ध-न्यूटन विधियों का कार्यान्वयन कई प्रोग्रामिंग भाषाओं में उपलब्ध है।

उल्लेखनीय खुला स्त्रोत कार्यान्वयन में शामिल हैं:

• जीएनयू ऑक्टेव अपने में बीएफजीएस के रूप का उपयोग करता है fsolve समारोह, विश्वास क्षेत्र विस्तार के साथ।
• जीएनयू वैज्ञानिक पुस्तकालय ब्रॉयडेन-फ्लेचर-गोल्डफार्ब-शन्नो (बीएफजीएस) कलन विधि को लागू करती है।
• ALGLIB C++ और C# में (L)BFGS लागू करता है
• आर (प्रोग्रामिंग भाषा) की optim सामान्य-उद्देश्य ऑप्टिमाइज़र रूटीन BFGS विधि का उपयोग करके उपयोग करता है method="BFGS".
• Scipy.optimize में fmin_bfgs है। पायथन (प्रोग्रामिंग भाषा) के लिए SciPy विस्तार में, scipy.optimize.minimize फ़ंक्शन में अन्य विधियों के साथ-साथ BFGS कार्यान्वयन भी शामिल है।

उल्लेखनीय मालिकाना कार्यान्वयन में शामिल हैं:

• गणित में अर्ध-न्यूटन सॉल्वर शामिल हैं।
• एनएजी न्यूमेरिकल लाइब्रेरी में कई रूटीन होते हैं किसी फ़ंक्शन को न्यूनतम या अधिकतम करने के लिए जो अर्ध-न्यूटन कलन विधि का उपयोग करते हैं।
• MATLAB के अनुकूलन टूलबॉक्स में, fminunc फ़ंक्शन उपयोग करता है (अन्य विधियों के बीच) बीएफजीएस अर्ध-न्यूटन विधि। अनुकूलन टूलबॉक्स के कई विवश तरीके BFGS और प्रकार L-BFGS का उपयोग करते हैं।<

यह भी देखें

• बीएफजीएस विधि
  • सीमित-मेमोरी BFGS|L-BFGS
  • ऑर्थेंट-वार सीमित-स्मृति अर्ध-न्यूटन|OWL-QN
• ब्रॉयडेन की विधि
• DFP अद्यतन करने का फ़ॉर्मूला
• न्यूटन विधि
• अनुकूलन में न्यूटन विधि
• SR1 फ़ॉर्मूला

अग्रिम पठन

• Bonnans, J. F.; Gilbert, J. Ch.; Lemaréchal, C.; Sagastizábal, C. A. (2006). Numerical Optimization : Theoretical and Numerical Aspects (Second ed.). Springer. ISBN 3-540-35445-X.
• Fletcher, Roger (1987), Practical methods of optimization (2nd ed.), New York: John Wiley & Sons, ISBN 978-0-471-91547-8.
• Nocedal, Jorge; Wright, Stephen J. (1999). "Quasi-Newton Methods". Numerical Optimization. New York: Springer. pp. 192–221. ISBN 0-387-98793-2.
• Press, W. H.; Teukolsky, S. A.; Vetterling, W. T.; Flannery, B. P. (2007). "Section 10.9. Quasi-Newton or Variable Metric Methods in Multidimensions". Numerical Recipes: The Art of Scientific Computing (3rd ed.). New York: Cambridge University Press. ISBN 978-0-521-88068-8.
• Scales, L. E. (1985). Introduction to Non-Linear Optimization. New York: MacMillan. pp. 84–106. ISBN 0-333-32552-4.

| group5 = Metaheuristics | abbr5 = heuristic | list5 =

• Evolutionary algorithm
• Hill climbing
• Local search
• Simulated annealing
• Tabu search

| below =

• Software

}} | group5 =Metaheuuristic |abbr5 = heuristic | list5 =*विकासवादी एल्गोरिथ्म

• पहाड़ी की चढ़ाई
• स्थानीय खोज
• तैयार किए हुयी धातु पे पानी चढाने की कला
• तब्बू खोज

| below =* सॉफ्टवेयर

}}