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

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

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

किसी फलन का शून्य ज्ञात करने की न्यूटन विधि $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 में पहला अर्ध-न्यूटन कलन विधि विकसित किया। डीएफपी अद्यतन सूत्र, जिसे बाद में 1963 में फ्लेचर और पॉवेल द्वारा लोकप्रिय बनाया गया था, किन्तु आज संभवतः ही कभी इसका उपयोग किया जाता है। सबसे साधारण अर्ध-न्यूटन कलन विधि वर्तमान में एसआर 1 सूत्र सममित पंक्ति-1 के लिए, BHHH विधि, व्यापक बीएफजीएस विधि 1970 में ब्रॉयडेन, फ्लेचर, गोल्डफार्ब और शन्नो द्वारा स्वतंत्र रूप से सुझाया गया, और इसकी कम-धारणा हैं विस्तार एल-बीएफजीएस। ब्रॉयडेन की कक्षा डीएफपी और बीएफजीएस विधियों का रैखिक संयोजन है।

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

अनुकूलन में न्यूटन विधि पर अर्ध-न्यूटन विधियों के मुख्य लाभों में से न्यूटन की विधि यह है कि हेस्सियन मैट्रिक्स ,अर्ध-न्यूटन विधियों के स्थितियों में इसका सन्निकटन $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}$ शर्मन-मॉरिसन सूत्र का उपयोग करना।

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

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

विधि	$\displaystyle B_{k+1}=$	$H_{k+1}=B_{k+1}^{-1}=$
बीएफजीएस	$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]$
डीएफपी	$\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}}}$
एसआर 1	$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}$. यह वास्तव में कम से कम परिवर्तन अद्यतनों के आधार पर अर्ध-न्यूटन विधियों के वर्ग का स्थिति है।

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

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

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

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

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

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

यह भी देखें

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

अग्रिम पठन

• 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.