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

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

शून्य के लिए खोजें: रूट फाइंडिंग

किसी फलन का शून्य ज्ञात करने की न्यूटन की विधि $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})$ सभी पुनरावृत्तियों के लिए) एक साधारण उदाहरण है। एक्स्ट्रेमा के लिए #Search के लिए नीचे दी गई विधियाँ अर्ध-न्यूटन विधियों, सिकेंट विधियों के एक महत्वपूर्ण उपवर्ग को संदर्भित करती हैं। शून्य को खोजने के लिए एक्स्ट्रेमा को खोजने के लिए विकसित विधियों का उपयोग करना हमेशा एक अच्छा विचार नहीं होता है, क्योंकि एक्स्ट्रेमा को खोजने के लिए उपयोग की जाने वाली अधिकांश विधियों के लिए आवश्यक है कि उपयोग किया जाने वाला मैट्रिक्स सममित हो। जबकि यह एक्स्ट्रेमा की खोज के संदर्भ में है, यह शून्य की खोज करते समय शायद ही कभी पकड़ में आता है। ब्रॉयडेन की विधि | ब्रोयडेन की अच्छी और बुरी विधियाँ दो विधियाँ हैं जिनका उपयोग आमतौर पर एक्स्ट्रेमा खोजने के लिए किया जाता है जिसे शून्य खोजने के लिए भी लागू किया जा सकता है। जिन अन्य विधियों का उपयोग किया जा सकता है, वे हैं कॉलम-अपडेटिंग विधि, व्युत्क्रम कॉलम-अपडेटिंग विधि, अर्ध-न्यूटन न्यूनतम वर्ग विधि और अर्ध-न्यूटन व्युत्क्रम न्यूनतम वर्ग विधि।

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

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

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

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

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

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

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}}}$
Broyden	$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}}}$
Broyden family	$(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 =* सॉफ्टवेयर

}}