ब्रॉयडेन-फ्लेचर-गोल्डफर्ब-शन्नो एल्गोरिथम: Difference between revisions

Latest revision as of 09:47, 23 February 2023

संख्यात्मक विश्लेषण (गणित) में, ब्रॉयडेन-फ्लेचर-गोल्डफार्ब-शन्नो (बीएफजीएस) एल्गोरिथ्म अप्रतिबंधित गैर-रैखिक आकलन समस्याओं को हल करने के लिए पुनरावृत्त विधि है।^[1] संबंधित डेविडन-फ्लैचर-पोवेल पद्धति की तरह, ब्रॉयडेन-फ्लेचर-गोल्डफार्ब-शन्नो वक्रता सूचना के साथ प्रवणता को पूर्वानुकूलित करके अवरोही दिशा निर्धारित करता है। यह हानि फलन के हेसियन मैट्रिक्स के सन्निकटन में धीरे-धीरे सुधार करके ऐसा करता है, सामान्यीकृत पद्धति के माध्यम से केवल प्रवणता मूल्यांकन (या अनुमानित प्रवणता मूल्यांकन) से प्राप्त होता है।^[2]

चूंकि ब्रॉयडेन-फ्लेचर-गोल्डफार्ब-शन्नो वक्रता मैट्रिक्स के अद्यतन के लिए मैट्रिक्स व्युत्क्रम की आवश्यकता नहीं है, गणितीय कार्यों की इसकी कम्प्यूटेशनल जटिलता केवल ${\mathcal {O}}(n^{2})$ , की तुलना में ${\mathcal {O}}(n^{3})$ न्यूटन की विधि आकलन है। इसके अलावा सामान्य उपयोग में L-ब्रॉयडेन-फ्लेचर-गोल्डफार्ब-शन्नो है, जो कि ब्रॉयडेन-फ्लेचर-गोल्डफार्ब-शन्नो का सीमित-स्मृति संस्करण है जो विशेष रूप से बहुत बड़ी संख्या में चर (जैसे,> 1000) के साथ समस्याओं के अनुकूल है। ब्रॉयडेन-फ्लेचर-गोल्डफार्ब-शन्नो-B संस्करण सरल बॉक्स बाधाओं को नियंत्रण करता है।^[3]

एल्गोरिथ्म का नाम चार्ल्स जॉर्ज ब्रॉयडेन, रोजर फ्लेचर (गणितज्ञ), डोनाल्ड गोल्डफर्ब और डेविड शन्नो के नाम पर रखा गया है।^[4]^[5]^[6]^[7]

कारण विवरण

$f(\mathbf {x} )$ आकलन समस्या को कम करने के लिए है, जहां $\mathbf {x}$ में सदिश $\mathbb {R} ^{n}$ है और $f$ अवकलनीय अदिश फलन है। मूल्यों पर कोई प्रतिबंध नहीं है $\mathbf {x}$ ले जा सकते हैं।

एल्गोरिथ्म इष्टतम मूल्य के लिए $\mathbf {x} _{0}$ प्रारंभिक अनुमान से शुरू होता है और प्रत्येक चरण में बेहतर अनुमान प्राप्त करने के लिए क्रमिक रूप से आगे बढ़ता है।

चरण k पर परीक्षण दिशा p_k को न्यूटन समीकरण के अनुरूप हल द्वारा दिया जाता है:

B_{k}\mathbf {p} _{k}=-\nabla f(\mathbf {x} _{k}),

जहां $B_{k}$ हेसियन मैट्रिक्स का सन्निकटन है, जिसे प्रत्येक चरण में पुनरावृत्त रूप से अद्यतन किया जाता है और $\nabla f(\mathbf {x} _{k})$ x_k पर मूल्यांकन किए गए फलन का ग्रेडिएंट है। $f(\mathbf {x} _{k}+\gamma \mathbf {p} _{k})$ अदिश के ऊपर $\gamma >0$ , p_k की दिशा में रेखा परीक्षण का उपयोग तब अगले बिंदु x_k+1 को न्यूनतम करके खोजने के लिए किया जाता है।

अर्ध-न्यूटन स्थिति के अद्यतन पर लगाया गया $B_{k}$ है

B_{k+1}(\mathbf {x} _{k+1}-\mathbf {x} _{k})=\nabla f(\mathbf {x} _{k+1})-\nabla f(\mathbf {x} _{k}).

मान ले $\mathbf {y} _{k}=\nabla f(\mathbf {x} _{k+1})-\nabla f(\mathbf {x} _{k})$ और $\mathbf {s} _{k}=\mathbf {x} _{k+1}-\mathbf {x} _{k}$ , तब $B_{k+1}$ समाधान करता है

B_{k+1}\mathbf {s} _{k}=\mathbf {y} _{k}

,

जो कि कोटिज्या समीकरण है।

वक्रता की स्थिति $\mathbf {s} _{k}^{\top }\mathbf {y} _{k}>0$ के लिए समाधान होना चाहिए $B_{k+1}$ घनात्मक निश्चित होने के लिए, $\mathbf {s} _{k}^{T}$ जिसे कोटिज्या समीकरण को पूर्व-गुणा करके सत्यापित किया जा सकता है। यदि फलन अत्यधिक उत्तल फलन नहीं है, तो स्थिति को स्पष्ट रूप से लागू किया जाना चाहिए जैसे कि बिंदु x_k+1 ज्ञात करके रेखा परीक्षण का उपयोग करते हुए, वोल्फ की स्थिति का समाधान करना, जो वक्रता की स्थिति में प्रवेश करता है।

बिंदु पर पूर्ण हेस्सियन मैट्रिक्स की आवश्यकता के बजाय $\mathbf {x} _{k+1}$ के रूप में गणना की जानी है $B_{k+1}$ ,चरण k पर अनुमानित हेसियन को दो मैट्रिसेस जोड़कर अपडेट किया गया है:

B_{k+1}=B_{k}+U_{k}+V_{k}.

दोनों $U_{k}$ और $V_{k}$ सममित रैंक-वन मैट्रिसेस हैं, लेकिन उनका योग रैंक-टू अपडेट मैट्रिक्स है। ब्रॉयडेन-फ्लेचर-गोल्डफार्ब-शन्नो और डेविडॉन-फ्लेचर-पॉवेल सिद्धान्त अपडेटिंग मैट्रिक्स दोनों अपने पूर्ववर्ती से रैंक-दो मैट्रिक्स से भिन्न हैं। एक और सरल रैंक-वन विधि को सममित रैंक-वन विधि के रूप में जाना जाता है, जो घनात्मक निश्चितता की गारंटी नहीं देती है। समरूपता और घनात्मक निश्चितता बनाए रखने के लिए $B_{k+1}$ , अद्यतन प्रपत्र के रूप में चुना जा सकता है $B_{k+1}=B_{k}+\alpha \mathbf {u} \mathbf {u} ^{\top }+\beta \mathbf {v} \mathbf {v} ^{\top }$ . दूसरी स्थिति लागू करना, $B_{k+1}\mathbf {s} _{k}=\mathbf {y} _{k}$ . का चयन $\mathbf {u} =\mathbf {y} _{k}$ और $\mathbf {v} =B_{k}\mathbf {s} _{k}$ , हम प्राप्त कर सकते हैं:^[8]

\alpha ={\frac {1}{\mathbf {y} _{k}^{T}\mathbf {s} _{k}}},

\beta =-{\frac {1}{\mathbf {s} _{k}^{T}B_{k}\mathbf {s} _{k}}}.

अंत में, हमने प्रतिस्थापित किया $\alpha$ और $\beta$ में $B_{k+1}=B_{k}+\alpha \mathbf {u} \mathbf {u} ^{\top }+\beta \mathbf {v} \mathbf {v} ^{\top }$ और $B_{k+1}$ का अद्यतन समीकरण प्राप्त कर सकते हैं।

B_{k+1}=B_{k}+{\frac {\mathbf {y} _{k}\mathbf {y} _{k}^{\mathrm {T} }}{\mathbf {y} _{k}^{\mathrm {T} }\mathbf {s} _{k}}}-{\frac {B_{k}\mathbf {s} _{k}\mathbf {s} _{k}^{\mathrm {T} }B_{k}^{\mathrm {T} }}{\mathbf {s} _{k}^{\mathrm {T} }B_{k}\mathbf {s} _{k}}}.

एल्गोरिथम

प्रारंभिक अनुमान से $\mathbf {x} _{0}$ और अनुमानित हेस्सियन मैट्रिक्स $B_{0}$ निम्नलिखित चरणों को दोहराया $\mathbf {x} _{k}$ समाधान में परिवर्तित होता है:

$\mathbf {p} _{k}$ दिशा प्राप्त करें $B_{k}\mathbf {p} _{k}=-\nabla f(\mathbf {x} _{k})$ हल करते है।
अनुकूल चरण आकार परीक्षण के लिए $\alpha _{k}$ पहले चरण में मिली दिशा में आयामी आकलन (रेखा परीक्षण) करें। यदि सटीक रेखा परीक्षण की जाती, तो $\alpha _{k}=\arg \min f(\mathbf {x} _{k}+\alpha \mathbf {p} _{k})$ है। पद्धति में, अनुकूल रेखा के साथ अचूक रेखा परीक्षण सामान्यतः $\alpha _{k}$ संतोषजनक वोल्फ की स्थिति पर पर्याप्त होती है।
वर्ग $\mathbf {s} _{k}=\alpha _{k}\mathbf {p} _{k}$ और $\mathbf {x} _{k+1}=\mathbf {x} _{k}+\mathbf {s} _{k}$ अपडेट करते है।
$\mathbf {y} _{k}={\nabla f(\mathbf {x} _{k+1})-\nabla f(\mathbf {x} _{k})}$ .
$B_{k+1}=B_{k}+{\frac {\mathbf {y} _{k}\mathbf {y} _{k}^{\mathrm {T} }}{\mathbf {y} _{k}^{\mathrm {T} }\mathbf {s} _{k}}}-{\frac {B_{k}\mathbf {s} _{k}\mathbf {s} _{k}^{\mathrm {T} }B_{k}^{\mathrm {T} }}{\mathbf {s} _{k}^{\mathrm {T} }B_{k}\mathbf {s} _{k}}}$ .

$f(\mathbf {x} )$ कम से कम किए जाने वाले सामान्य फलन को दर्शाता है। अनुपात के मानक, $||\nabla f(\mathbf {x} _{k})||$ को देखकर अभिसरण की जांच की जा सकती है। अगर $B_{0}$ के साथ प्रारंभ किया $B_{0}=I$ , पहला चरण ग्रेडिएंट डिसेंट के बराबर होगा, लेकिन $B_{k}$ , हेस्सियन के सन्निकटन आगे के चरण अधिक से अधिक परिष्कृत होते जा रहे हैं।

एल्गोरिथ्म का पहला चरण $B_{k}$ मैट्रिक्स के व्युत्क्रम का उपयोग करके किया जाता है, जिसे एल्गोरिथम के चरण 5 में शर्मन-मॉरिसन सूत्र को लागू करके कुशलता से प्राप्त किया जा सकता है।

B_{k+1}^{-1}=\left(I-{\frac {\mathbf {s} _{k}\mathbf {y} _{k}^{T}}{\mathbf {y} _{k}^{T}\mathbf {s} _{k}}}\right)B_{k}^{-1}\left(I-{\frac {\mathbf {y} _{k}\mathbf {s} _{k}^{T}}{\mathbf {y} _{k}^{T}\mathbf {s} _{k}}}\right)+{\frac {\mathbf {s} _{k}\mathbf {s} _{k}^{T}}{\mathbf {y} _{k}^{T}\mathbf {s} _{k}}}.

अस्थायी मैट्रिसेस के बिना कुशलता से गणना की जा सकती है, यह मानते हुए कि $B_{k}^{-1}$ सममित है, और वह $\mathbf {y} _{k}^{\mathrm {T} }B_{k}^{-1}\mathbf {y} _{k}$ और $\mathbf {s} _{k}^{\mathrm {T} }\mathbf {y} _{k}$ विस्तार का उपयोग करते हुए स्केलर हैं,

B_{k+1}^{-1}=B_{k}^{-1}+{\frac {(\mathbf {s} _{k}^{\mathrm {T} }\mathbf {y} _{k}+\mathbf {y} _{k}^{\mathrm {T} }B_{k}^{-1}\mathbf {y} _{k})(\mathbf {s} _{k}\mathbf {s} _{k}^{\mathrm {T} })}{(\mathbf {s} _{k}^{\mathrm {T} }\mathbf {y} _{k})^{2}}}-{\frac {B_{k}^{-1}\mathbf {y} _{k}\mathbf {s} _{k}^{\mathrm {T} }+\mathbf {s} _{k}\mathbf {y} _{k}^{\mathrm {T} }B_{k}^{-1}}{\mathbf {s} _{k}^{\mathrm {T} }\mathbf {y} _{k}}}.

इसलिए, किसी भी मैट्रिक्स व्युत्क्रम से बचने के लिए, हेस्सियन के व्युत्क्रम को हेस्सियन के बजाय अनुमानित किया जा सकता है: $H_{k}{\overset {\operatorname {def} }{=}}B_{k}^{-1}.$ ^[9]

प्रारंभिक अनुमान से $\mathbf {x} _{0}$ और अनुमानित व्युत्क्रम हेस्सियन मैट्रिक्स $H_{0}$ निम्नलिखित चरणों को दोहराया जाता है $\mathbf {x} _{k}$ समाधान में अभिसरण करता है:

$\mathbf {p} _{k}$ हल करके $\mathbf {p} _{k}=-H_{k}\nabla f(\mathbf {x} _{k})$ दिशा प्राप्त करते है।
अनुकूल चरण आकार परीक्षण के लिए, $\alpha _{k}$ पहले चरण में मिली दिशा में आयामी आकलन (रेखा परीक्षण) करें। यदि सटीक रेखा परीक्षण की जाती, तो $\alpha _{k}=\arg \min f(\mathbf {x} _{k}+\alpha \mathbf {p} _{k})$ है। पद्धति में, एक अनुकूल रेखा के साथ अचूक रेखा परीक्षण सामान्यतः $\alpha _{k}$ संतोषजनक वोल्फ की स्थिति पर पर्याप्त होती है।
वर्ग $\mathbf {s} _{k}=\alpha _{k}\mathbf {p} _{k}$ और $\mathbf {x} _{k+1}=\mathbf {x} _{k}+\mathbf {s} _{k}$ अपडेट करते है।
$\mathbf {y} _{k}={\nabla f(\mathbf {x} _{k+1})-\nabla f(\mathbf {x} _{k})}$ .
$H_{k+1}=H_{k}+{\frac {(\mathbf {s} _{k}^{\mathrm {T} }\mathbf {y} _{k}+\mathbf {y} _{k}^{\mathrm {T} }H_{k}\mathbf {y} _{k})(\mathbf {s} _{k}\mathbf {s} _{k}^{\mathrm {T} })}{(\mathbf {s} _{k}^{\mathrm {T} }\mathbf {y} _{k})^{2}}}-{\frac {H_{k}\mathbf {y} _{k}\mathbf {s} _{k}^{\mathrm {T} }+\mathbf {s} _{k}\mathbf {y} _{k}^{\mathrm {T} }H_{k}}{\mathbf {s} _{k}^{\mathrm {T} }\mathbf {y} _{k}}}$ .

सांख्यिकीय आकलन समस्याओं में (जैसे कि अधिकतम संभावना अनुमान या बायेसियन अनुमान), समाधान के लिए विश्वसनीय अंतराल या विश्वास अंतराल का अनुमान अंतिम हेस्सियन मैट्रिक्स के मैट्रिक्स व्युत्क्रम से लगाया जा सकता है। यद्यपि, इन मात्राओं को तकनीकी रूप से सही हेस्सियन मैट्रिक्स द्वारा परिभाषित किया गया है और ब्रॉयडेन-फ्लेचर-गोल्डफार्ब-शन्नो सन्निकटन सही हेस्सियन मैट्रिक्स में परिवर्तित नहीं हो सकता है।^[10]

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

उल्लेखनीय ओपन सोर्स कार्यान्वयन हैं:

अल्गलिब ब्रॉयडेन-फ्लेचर-गोल्डफार्ब-शन्नो और इसके सीमित-स्मृति संस्करण को C++ और C# में लागू करता है।
जीएनयू ऑक्टेव ट्रस्ट क्षेत्र विस्तार के साथ अपने fsolveफलन, में ब्रॉयडेन-फ्लेचर-गोल्डफार्ब-शन्नो के रूप का उपयोग करता है।
जीएनयू वैज्ञानिक पुस्तकालय ब्रॉयडेन-फ्लेचर-गोल्डफार्ब-शन्नो को gsl_multimin_fdfminimizer_vector_ब्रॉयडेन-फ्लेचर-गोल्डफार्ब-शन्नो2 के रूप में लागू करती है।^[11]
R (प्रोग्रामिंग भाषा) में, ब्रॉयडेन-फ्लेचर-गोल्डफार्ब-शन्नो एल्गोरिदम (और L-ब्रॉयडेन-फ्लेचर-गोल्डफार्ब-शन्नो-B संस्करण जो बॉक्स बाधाओं की अनुमति देता है) को आधार फलन ऑप्टिम () के विकल्प के रूप में लागू किया गया है।^[12]
SciPy में, scipy.optimize.fmin_ब्रॉयडेन-फ्लेचर-गोल्डफार्ब-शन्नो फलन ब्रॉयडेन-फ्लेचर-गोल्डफार्ब-शन्नो लागू करता है।^[13] पैरामीटर L को बहुत बड़ी संख्या में सेट करके किसी भी L-ब्रॉयडेन-फ्लेचर-गोल्डफार्ब-शन्नो एल्गोरिदम का उपयोग करके ब्रॉयडेन-फ्लेचर-गोल्डफार्ब-शन्नो चलाना भी संभव है।
जूलिया (प्रोग्रामिंग लैंग्वेज) में, Optim.jl पैकेज ब्रॉयडेन-फ्लेचर-गोल्डफार्ब-शन्नो और L-ब्रॉयडेन-फ्लेचर-गोल्डफार्ब-शन्नो को ऑप्टिमाइज () फलन के सॉल्वर विकल्प के रूप में लागू करता है (अन्य के बीच) विकल्प)।^[14]

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

बड़े पैमाने पर नॉनलाइनियर ऑप्टिमाइज़ेशन सॉफ़्टवेयर Artelys Knitro, दूसरों के बीच, ब्रॉयडेन-फ्लेचर-गोल्डफार्ब-शन्नो और L-ब्रॉयडेन-फ्लेचर-गोल्डफार्ब-शन्नो एल्गोरिदम दोनों को लागू करता है।
मैट्रिक्स प्रयोगशाला आकलन टूलबॉक्स में, fminunc फलन घन रेखा के साथ ब्रॉयडेन-फ्लेचर-गोल्डफार्ब-शन्नो का उपयोग करता है जब समस्या का आकार "मध्यम स्केल" पर सेट होता है।

यह भी देखें

बीएचएचएच एल्गोरिदम
डेविडॉन-फ्लेचर-पॉवेल सूत्र
ढतला हुआ वंश
एल-बीएफजीएस
लेवेनबर्ग-मार्क्वार्ट एल्गोरिथम
नेल्डर-मीड विधि
पैटर्न खोज (अनुकूलन)
अर्ध-न्यूटन विधियाँ
सममित रैंक-एक

संदर्भ

↑ Fletcher, Roger (1987), Practical Methods of Optimization (2nd ed.), New York: John Wiley & Sons, ISBN 978-0-471-91547-8
↑ Dennis, J. E. Jr.; Schnabel, Robert B. (1983), "Secant Methods for Unconstrained Minimization", Numerical Methods for Unconstrained Optimization and Nonlinear Equations, Englewood Cliffs, NJ: Prentice-Hall, pp. 194–215, ISBN 0-13-627216-9
↑ Byrd, Richard H.; Lu, Peihuang; Nocedal, Jorge; Zhu, Ciyou (1995), "A Limited Memory Algorithm for Bound Constrained Optimization", SIAM Journal on Scientific Computing, 16 (5): 1190–1208, CiteSeerX 10.1.1.645.5814, doi:10.1137/0916069
↑ Broyden, C. G. (1970), "The convergence of a class of double-rank minimization algorithms", Journal of the Institute of Mathematics and Its Applications, 6: 76–90, doi:10.1093/imamat/6.1.76
↑ Fletcher, R. (1970), "A New Approach to Variable Metric Algorithms", Computer Journal, 13 (3): 317–322, doi:10.1093/comjnl/13.3.317
↑ Goldfarb, D. (1970), "A Family of Variable Metric Updates Derived by Variational Means", Mathematics of Computation, 24 (109): 23–26, doi:10.1090/S0025-5718-1970-0258249-6
↑ Shanno, David F. (July 1970), "Conditioning of quasi-Newton methods for function minimization", Mathematics of Computation, 24 (111): 647–656, doi:10.1090/S0025-5718-1970-0274029-X, MR 0274029
↑ 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. (2006), Numerical Optimization (2nd ed.), Berlin, New York: Springer-Verlag, ISBN 978-0-387-30303-1
↑ Ge, Ren-pu; Powell, M. J. D. (1983). "The Convergence of Variable Metric Matrices in Unconstrained Optimization". Mathematical Programming. 27 (2). 123. doi:10.1007/BF02591941. S2CID 8113073.
↑ "GNU Scientific Library — GSL 2.6 documentation". www.gnu.org. Retrieved 2020-11-22.
↑ "R: General-purpose Optimization". stat.ethz.ch. Retrieved 2020-11-22.
↑ "scipy.optimize.fmin_bfgs — SciPy v1.5.4 Reference Guide". docs.scipy.org. Retrieved 2020-11-22.
↑ "Optim.jl Configurable options". julianlsolvers.

अग्रिम पठन

Avriel, Mordecai (2003), Nonlinear Programming: Analysis and Methods, Dover Publishing, ISBN 978-0-486-43227-4
Bonnans, J. Frédéric; Gilbert, J. Charles; Lemaréchal, Claude; Sagastizábal, Claudia A. (2006), "Newtonian Methods", Numerical Optimization: Theoretical and Practical Aspects (Second ed.), Berlin: Springer, pp. 51–66, 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
Luenberger, David G.; Ye, Yinyu (2008), Linear and nonlinear programming, International Series in Operations Research & Management Science, vol. 116 (Third ed.), New York: Springer, pp. xiv+546, ISBN 978-0-387-74502-2, MR 2423726
Kelley, C. T. (1999), Iterative Methods for Optimization, Philadelphia: Society for Industrial and Applied Mathematics, pp. 71–86, ISBN 0-89871-433-8

[1] Fletcher, Roger (1987), Practical Methods of Optimization (2nd ed.), New York: John Wiley & Sons, ISBN 978-0-471-91547-8

[2] Dennis, J. E. Jr.; Schnabel, Robert B. (1983), "Secant Methods for Unconstrained Minimization", Numerical Methods for Unconstrained Optimization and Nonlinear Equations, Englewood Cliffs, NJ: Prentice-Hall, pp. 194–215, ISBN 0-13-627216-9

[3] Byrd, Richard H.; Lu, Peihuang; Nocedal, Jorge; Zhu, Ciyou (1995), "A Limited Memory Algorithm for Bound Constrained Optimization", SIAM Journal on Scientific Computing, 16 (5): 1190–1208, CiteSeerX 10.1.1.645.5814, doi:10.1137/0916069

[4] Broyden, C. G. (1970), "The convergence of a class of double-rank minimization algorithms", Journal of the Institute of Mathematics and Its Applications, 6: 76–90, doi:10.1093/imamat/6.1.76

[5] Fletcher, R. (1970), "A New Approach to Variable Metric Algorithms", Computer Journal, 13 (3): 317–322, doi:10.1093/comjnl/13.3.317

[6] Goldfarb, D. (1970), "A Family of Variable Metric Updates Derived by Variational Means", Mathematics of Computation, 24 (109): 23–26, doi:10.1090/S0025-5718-1970-0258249-6

[7] Shanno, David F. (July 1970), "Conditioning of quasi-Newton methods for function minimization", Mathematics of Computation, 24 (111): 647–656, doi:10.1090/S0025-5718-1970-0274029-X, MR 0274029

[8] Fletcher, Roger (1987), Practical methods of optimization (2nd ed.), New York: John Wiley & Sons, ISBN 978-0-471-91547-8

[Nocedal-9] Nocedal, Jorge; Wright, Stephen J. (2006), Numerical Optimization (2nd ed.), Berlin, New York: Springer-Verlag, ISBN 978-0-387-30303-1

[10] Ge, Ren-pu; Powell, M. J. D. (1983). "The Convergence of Variable Metric Matrices in Unconstrained Optimization". Mathematical Programming. 27 (2). 123. doi:10.1007/BF02591941. S2CID 8113073.

[11] "GNU Scientific Library — GSL 2.6 documentation". www.gnu.org. Retrieved 2020-11-22.

[12] "R: General-purpose Optimization". stat.ethz.ch. Retrieved 2020-11-22.

[13] "scipy.optimize.fmin_bfgs — SciPy v1.5.4 Reference Guide". docs.scipy.org. Retrieved 2020-11-22.

[14] "Optim.jl Configurable options". julianlsolvers.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

@@ Line 1: / Line 1: @@
 {{short description|Optimization method}}
-{{Redirect|BFGS|कैनेडियन हार्डकोर पंक बैंड|बंचोफकिंगोफ्स}}
+{{Redirect|ब्रॉयडेन-फ्लेचर-गोल्डफार्ब-शन्नो|कैनेडियन हार्डकोर पंक बैंड|बंचोफकिंगोफ्स}}
-{{More citations needed|date=March 2016}}
+[[संख्यात्मक विश्लेषण]] [[अनुकूलन (गणित)|(गणित)]] में, ब्रॉयडेन-फ्लेचर-गोल्डफार्ब-शन्नो (बीएफजीएस) एल्गोरिथ्म अप्रतिबंधित गैर-रैखिक आकलन समस्याओं को हल करने के लिए पुनरावृत्त विधि है।<ref>{{Citation | last1=Fletcher | first1=Roger | title=Practical Methods of Optimization | publisher=[[John Wiley & Sons]] | location=New York | edition=2nd | isbn=978-0-471-91547-8 | year=1987 | url-access=registration | url=https://archive.org/details/practicalmethods0000flet }}</ref> संबंधित डेविडन-फ्लैचर-पोवेल पद्धति की तरह, ब्रॉयडेन-फ्लेचर-गोल्डफार्ब-शन्नो वक्रता सूचना के साथ प्रवणता को पूर्वानुकूलित करके अवरोही दिशा निर्धारित करता है। यह हानि फलन के [[हेसियन मैट्रिक्स]] के सन्निकटन में धीरे-धीरे सुधार करके ऐसा करता है, सामान्यीकृत पद्धति के माध्यम से केवल प्रवणता मूल्यांकन (या अनुमानित प्रवणता मूल्यांकन) से प्राप्त होता है।<ref>{{citation |first1=J. E. Jr. |last1=Dennis |author-link=John E. Dennis |first2=Robert B. |last2=Schnabel |author-link2=Robert B. Schnabel |title=Numerical Methods for Unconstrained Optimization and Nonlinear Equations |chapter=Secant Methods for Unconstrained Minimization |location=Englewood Cliffs, NJ |publisher=Prentice-Hall |year=1983 |isbn=0-13-627216-9 |pages=194–215 |chapter-url=https://www.google.com/books/edition/Numerical_Methods_for_Unconstrained_Opti/ksvJTtJCx9cC?hl=en&gbpv=1&pg=PA194 }}</ref>
-[[संख्यात्मक विश्लेषण]] [[अनुकूलन (गणित)|(गणित)]] में, ब्रॉयडेन-फ्लेचर-गोल्डफार्ब-शन्नो (BFGS) एल्गोरिथ्म अप्रतिबंधित गैर-रैखिक अनुकूलन समस्याओं को हल करने के लिए पुनरावृत्त विधि है।<ref>{{Citation | last1=Fletcher | first1=Roger | title=Practical Methods of Optimization | publisher=[[John Wiley & Sons]] | location=New York | edition=2nd | isbn=978-0-471-91547-8 | year=1987 | url-access=registration | url=https://archive.org/details/practicalmethods0000flet }}</ref> संबंधित डेविडन-फ्लैचर-पोवेल पद्धति की तरह, BFGS वक्रता सूचना के साथ प्रवणता को पूर्वानुकूलित करके अवरोही दिशा निर्धारित करता है। यह हानि फलन के [[हेसियन मैट्रिक्स]] के सन्निकटन में धीरे-धीरे सुधार करके ऐसा करता है, सामान्यीकृत पद्धति के माध्यम से केवल प्रवणता मूल्यांकन (या अनुमानित प्रवणता मूल्यांकन) से प्राप्त होता है। [[ग्रेडियेंट]]   <ref>{{citation |first1=J. E. Jr. |last1=Dennis |author-link=John E. Dennis |first2=Robert B. |last2=Schnabel |author-link2=Robert B. Schnabel |title=Numerical Methods for Unconstrained Optimization and Nonlinear Equations |chapter=Secant Methods for Unconstrained Minimization |location=Englewood Cliffs, NJ |publisher=Prentice-Hall |year=1983 |isbn=0-13-627216-9 |pages=194–215 |chapter-url=https://www.google.com/books/edition/Numerical_Methods_for_Unconstrained_Opti/ksvJTtJCx9cC?hl=en&gbpv=1&pg=PA194 }}</ref>
-चूंकि बीएफजीएस वक्रता मैट्रिक्स के अद्यतन के लिए मैट्रिक्स व्युत्क्रम की आवश्यकता नहीं है, गणितीय कार्यों की इसकी कम्प्यूटेशनल जटिलता केवल <math>\mathcal{O}(n^{2})</math>, की तुलना में <math>\mathcal{O}(n^{3})</math> अनुकूलन में न्यूटन की विधि | न्यूटन की विधि। इसके अलावा सामान्य उपयोग में [[एल-बीएफजीएस]] है, जो कि बीएफजीएस का एक सीमित-स्मृति संस्करण है जो विशेष रूप से बहुत बड़ी संख्या में चर (जैसे,> 1000) के साथ समस्याओं के अनुकूल है। बीएफजीएस-बी संस्करण सरल बॉक्स बाधाओं को संभालता है।<ref>{{Citation|url=http://www.ece.northwestern.edu/~nocedal/PSfiles/limited.ps.gz |pages= 1190–1208|doi=10.1137/0916069|title= A Limited Memory Algorithm for Bound Constrained Optimization|journal= SIAM Journal on Scientific Computing|volume= 16|issue= 5|year= 1995|last1= Byrd|first1= Richard H.|last2= Lu|first2= Peihuang|last3= Nocedal|first3= Jorge|last4= Zhu|first4= Ciyou |citeseerx= 10.1.1.645.5814}}</ref>
+चूंकि ब्रॉयडेन-फ्लेचर-गोल्डफार्ब-शन्नो वक्रता मैट्रिक्स के अद्यतन के लिए मैट्रिक्स व्युत्क्रम की आवश्यकता नहीं है, गणितीय कार्यों की इसकी कम्प्यूटेशनल जटिलता केवल <math>\mathcal{O}(n^{2})</math>, की तुलना में <math>\mathcal{O}(n^{3})</math> न्यूटन की विधि आकलन है। इसके अलावा सामान्य उपयोग में  [[एल-बीएफजीएस|L-ब्रॉयडेन-फ्लेचर-गोल्डफार्ब-शन्नो]] है, जो कि ब्रॉयडेन-फ्लेचर-गोल्डफार्ब-शन्नो का सीमित-स्मृति संस्करण है जो विशेष रूप से बहुत बड़ी संख्या में चर (जैसे,> 1000) के साथ समस्याओं के अनुकूल है। ब्रॉयडेन-फ्लेचर-गोल्डफार्ब-शन्नो-B संस्करण सरल बॉक्स बाधाओं को नियंत्रण करता है।<ref>{{Citation|url=http://www.ece.northwestern.edu/~nocedal/PSfiles/limited.ps.gz |pages= 1190–1208|doi=10.1137/0916069|title= A Limited Memory Algorithm for Bound Constrained Optimization|journal= SIAM Journal on Scientific Computing|volume= 16|issue= 5|year= 1995|last1= Byrd|first1= Richard H.|last2= Lu|first2= Peihuang|last3= Nocedal|first3= Jorge|last4= Zhu|first4= Ciyou |citeseerx= 10.1.1.645.5814}}</ref>
 एल्गोरिथ्म का नाम [[चार्ल्स जॉर्ज ब्रॉयडेन]], [[रोजर फ्लेचर (गणितज्ञ)]], [[डोनाल्ड गोल्डफर्ब]] और [[डेविड शन्नो]] के नाम पर रखा गया है।<ref>{{Citation| last=Broyden | first=C. G. | author-link=Charles George Broyden | year=1970 | title=The convergence of a class of double-rank minimization algorithms | journal=Journal of the Institute of Mathematics and Its Applications | volume=6 | pages=76–90 | doi=10.1093/imamat/6.1.76}}</ref><ref>{{Citation | last1=Fletcher|first1= R.|title= A New Approach to Variable Metric Algorithms|journal=Computer Journal |year=1970|volume=13|pages=317–322 | doi=10.1093/comjnl/13.3.317 | issue=3|doi-access=free}}</ref><ref>{{Citation|author-link=Donald Goldfarb|last=Goldfarb|first= D.|title=A Family of Variable Metric Updates Derived by Variational Means|journal=Mathematics of Computation|year=1970|volume=24|pages=23–26|doi=10.1090/S0025-5718-1970-0258249-6|issue=109|doi-access=free}}</ref><ref>{{Citation | last1=Shanno|first1= David F.|title=Conditioning of quasi-Newton methods for function minimization|date=July 1970|journal=Mathematics of Computation|volume=24|pages= 647–656|mr=274029|doi=10.1090/S0025-5718-1970-0274029-X | issue=111 |doi-access=free}}</ref>
+== कारण विवरण ==
+<math>f(\mathbf{x})</math> आकलन समस्या को कम करने के लिए है, जहां <math>\mathbf{x}</math> में सदिश <math>\mathbb{R}^n</math> है और <math>f</math> अवकलनीय अदिश फलन है। मूल्यों पर कोई प्रतिबंध नहीं है <math>\mathbf{x}</math> ले जा सकते हैं।
+एल्गोरिथ्म इष्टतम मूल्य के लिए  <math>\mathbf{x}_0</math> प्रारंभिक अनुमान से शुरू होता है और प्रत्येक चरण में बेहतर अनुमान प्राप्त करने के लिए क्रमिक रूप से आगे बढ़ता है।
+चरण ''k'' पर परीक्षण दिशा '''p'''<sub>''k''</sub> को न्यूटन समीकरण के अनुरूप हल द्वारा दिया जाता है:
-== औचित्य ==
+:<math>B_k \mathbf{p}_k = -\nabla f(\mathbf{x}_k),</math>
-अनुकूलन समस्या को कम करना है <math>f(\mathbf{x})</math>, कहाँ <math>\mathbf{x}</math> में सदिश है <math>\mathbb{R}^n</math>, और <math>f</math> एक अवकलनीय अदिश फलन है। मूल्यों पर कोई प्रतिबंध नहीं है <math>\mathbf{x}</math> ले जा सकते हैं।
+जहां <math>B_k</math> हेसियन मैट्रिक्स का सन्निकटन है, जिसे प्रत्येक चरण में पुनरावृत्त रूप से अद्यतन किया जाता है और <math>\nabla f(\mathbf{x}_k)</math> '''x'''<sub>''k''</sub> पर मूल्यांकन किए गए फलन का ग्रेडिएंट है। <math>f(\mathbf{x}_k + \gamma\mathbf{p}_k)</math> अदिश के ऊपर <math>\gamma > 0</math>,  '''p'''<sub>''k''</sub> की दिशा में रेखा परीक्षण का उपयोग तब अगले बिंदु '''x'''<sub>''k''+1</sub> को न्यूनतम करके खोजने के लिए किया जाता है।
-एल्गोरिथ्म इष्टतम मूल्य के लिए प्रारंभिक अनुमान से शुरू होता है <math>\mathbf{x}_0</math> और प्रत्येक चरण में एक बेहतर अनुमान प्राप्त करने के लिए क्रमिक रूप से आगे बढ़ता है।
-उतरने की दिशा p<sub>''k''</sub> स्टेज पर k न्यूटन समीकरण के अनुरूप के समाधान द्वारा दिया गया है:
-:<math>B_k \mathbf{p}_k = -\nabla f(\mathbf{x}_k),</math>
-कहाँ <math>B_k</math> हेसियन मैट्रिक्स का एक सन्निकटन है, जिसे प्रत्येक चरण में पुनरावृत्त रूप से अद्यतन किया जाता है, और <math>\nabla f(\mathbf{x}_k)</math> x पर मूल्यांकन किए गए फ़ंक्शन का ग्रेडिएंट है<sub>''k''</sub>. दिशा पी में एक पंक्ति खोज<sub>''k''</sub> फिर अगले बिंदु x को खोजने के लिए प्रयोग किया जाता है<sub>''k''+1</sub> कम करके <math>f(\mathbf{x}_k + \gamma\mathbf{p}_k)</math> अदिश के ऊपर <math>\gamma > 0.</math>
 अर्ध-न्यूटन स्थिति के अद्यतन पर लगाया गया <math>B_k</math> है
 :<math>B_{k+1} (\mathbf{x}_{k+1} - \mathbf{x}_k) = \nabla f(\mathbf{x}_{k+1}) - \nabla f(\mathbf{x}_k).</math>
-होने देना <math>\mathbf{y}_k = \nabla f(\mathbf{x}_{k+1}) - \nabla f(\mathbf{x}_k)</math> और <math>\mathbf{s}_k = \mathbf{x}_{k+1} - \mathbf{x}_k</math>, तब <math>B_{k+1}</math> संतुष्ट
+मान ले <math>\mathbf{y}_k = \nabla f(\mathbf{x}_{k+1}) - \nabla f(\mathbf{x}_k)</math> और <math>\mathbf{s}_k = \mathbf{x}_{k+1} - \mathbf{x}_k</math>, तब <math>B_{k+1}</math> समाधान करता है
 :<math>B_{k+1} \mathbf{s}_k = \mathbf{y}_k</math>,
-जो कि छेदक समीकरण है।
+जो कि कोटिज्या समीकरण है।
-वक्रता की स्थिति <math>\mathbf{s}_k^\top \mathbf{y}_k > 0</math> के लिए संतुष्ट होना चाहिए <math>B_{k+1}</math> सकारात्मक निश्चित होने के लिए, जिसे सेकेंट समीकरण को पूर्व-गुणा करके सत्यापित किया जा सकता है <math>\mathbf{s}_k^T</math>. यदि फ़ंक्शन अत्यधिक उत्तल फ़ंक्शन नहीं है, तो स्थिति को स्पष्ट रूप से लागू किया जाना चाहिए उदा। एक बिंदु x ज्ञात करके<sub>''k''+1</sub> लाइन खोज का उपयोग करते हुए, [[वोल्फ की स्थिति]] को संतुष्ट करना, जो वक्रता की स्थिति में प्रवेश करता है।
+वक्रता की स्थिति <math>\mathbf{s}_k^\top \mathbf{y}_k > 0</math> के लिए समाधान होना चाहिए <math>B_{k+1}</math> घनात्मक निश्चित होने के लिए,  <math>\mathbf{s}_k^T</math>  जिसे कोटिज्या समीकरण को पूर्व-गुणा करके सत्यापित किया जा सकता है। यदि फलन अत्यधिक उत्तल फलन नहीं है, तो स्थिति को स्पष्ट रूप से लागू किया जाना चाहिए जैसे कि बिंदु  '''x'''<sub>''k''+1</sub> ज्ञात करके रेखा परीक्षण का उपयोग करते हुए, [[वोल्फ की स्थिति]] का समाधान करना, जो वक्रता की स्थिति में प्रवेश करता है।
-बिंदु पर पूर्ण हेस्सियन मैट्रिक्स की आवश्यकता के बजाय <math>\mathbf{x}_{k+1}</math> के रूप में गणना की जानी है <math>B_{k+1}</math>, स्टेज k पर अनुमानित हेसियन को दो मैट्रिसेस जोड़कर अपडेट किया गया है:
+बिंदु पर पूर्ण हेस्सियन मैट्रिक्स की आवश्यकता के बजाय <math>\mathbf{x}_{k+1}</math> के रूप में गणना की जानी है <math>B_{k+1}</math>,चरण k पर अनुमानित हेसियन को दो मैट्रिसेस जोड़कर अपडेट किया गया है:
 :<math>B_{k+1} = B_k + U_k + V_k.</math>
-दोनों <math>U_k</math> और <math>V_k</math> सममित रैंक-वन मैट्रिसेस हैं, लेकिन उनका योग रैंक-टू अपडेट मैट्रिक्स है। बीएफजीएस और डेविडॉन-फ्लेचर-पॉवेल फॉर्मूला अपडेटिंग मैट्रिक्स दोनों अपने पूर्ववर्ती से रैंक-दो मैट्रिक्स से भिन्न हैं। एक और सरल रैंक-वन विधि को सममित रैंक-वन विधि के रूप में जाना जाता है, जो [[सकारात्मक निश्चितता]] की गारंटी नहीं देती है। समरूपता और सकारात्मक निश्चितता बनाए रखने के लिए <math>B_{k+1}</math>, अद्यतन प्रपत्र के रूप में चुना जा सकता है <math>B_{k+1} = B_k + \alpha\mathbf{u}\mathbf{u}^\top + \beta\mathbf{v}\mathbf{v}^\top</math>. दूसरी स्थिति लागू करना, <math>B_{k+1} \mathbf{s}_k = \mathbf{y}_k </math>. का चयन <math>\mathbf{u} = \mathbf{y}_k</math> और <math>\mathbf{v} = B_k \mathbf{s}_k</math>, हम प्राप्त कर सकते हैं:<ref>{{Citation | last1=Fletcher | first1=Roger | title=Practical methods of optimization | publisher=[[John Wiley & Sons]] | location=New York | edition=2nd | isbn=978-0-471-91547-8 | year=1987 | url-access=registration | url=https://archive.org/details/practicalmethods0000flet }}</ref>
+दोनों <math>U_k</math> और <math>V_k</math> सममित रैंक-वन मैट्रिसेस हैं, लेकिन उनका योग रैंक-टू अपडेट मैट्रिक्स है। ब्रॉयडेन-फ्लेचर-गोल्डफार्ब-शन्नो और डेविडॉन-फ्लेचर-पॉवेल सिद्धान्त अपडेटिंग मैट्रिक्स दोनों अपने पूर्ववर्ती से रैंक-दो मैट्रिक्स से भिन्न हैं। एक और सरल रैंक-वन विधि को सममित रैंक-वन विधि के रूप में जाना जाता है, जो [[सकारात्मक निश्चितता|घनात्मक निश्चितता]] की गारंटी नहीं देती है। समरूपता और घनात्मक निश्चितता बनाए रखने के लिए <math>B_{k+1}</math>, अद्यतन प्रपत्र के रूप में चुना जा सकता है <math>B_{k+1} = B_k + \alpha\mathbf{u}\mathbf{u}^\top + \beta\mathbf{v}\mathbf{v}^\top</math>. दूसरी स्थिति लागू करना, <math>B_{k+1} \mathbf{s}_k = \mathbf{y}_k </math>. का चयन <math>\mathbf{u} = \mathbf{y}_k</math> और <math>\mathbf{v} = B_k \mathbf{s}_k</math>, हम प्राप्त कर सकते हैं:<ref>{{Citation | last1=Fletcher | first1=Roger | title=Practical methods of optimization | publisher=[[John Wiley & Sons]] | location=New York | edition=2nd | isbn=978-0-471-91547-8 | year=1987 | url-access=registration | url=https://archive.org/details/practicalmethods0000flet }}</ref>
 :<math>\alpha = \frac{1}{\mathbf{y}_k^T \mathbf{s}_k},</math>
 :<math>\beta = -\frac{1}{\mathbf{s}_k^T  B_k \mathbf{s}_k}.</math>
-अंत में, हम स्थानापन्न करते हैं <math>\alpha</math> और <math>\beta</math> में <math>B_{k+1} = B_k + \alpha\mathbf{u}\mathbf{u}^\top + \beta\mathbf{v}\mathbf{v}^\top</math> और का अद्यतन समीकरण प्राप्त करें <math>B_{k+1}</math>:
+अंत में, हमने प्रतिस्थापित किया <math>\alpha</math> और <math>\beta</math> में <math>B_{k+1} = B_k + \alpha\mathbf{u}\mathbf{u}^\top + \beta\mathbf{v}\mathbf{v}^\top</math> और  <math>B_{k+1}</math> का अद्यतन समीकरण प्राप्त कर सकते हैं।
 :<math>B_{k+1} = B_k + \frac{\mathbf{y}_k \mathbf{y}_k^{\mathrm{T}}}{\mathbf{y}_k^{\mathrm{T}} \mathbf{s}_k} - \frac{B_k \mathbf{s}_k \mathbf{s}_k^{\mathrm{T}} B_k^{\mathrm{T}} }{\mathbf{s}_k^{\mathrm{T}} B_k \mathbf{s}_k}.</math>
 == एल्गोरिथम ==
-प्रारंभिक अनुमान से <math>\mathbf{x}_0</math> और अनुमानित हेस्सियन मैट्रिक्स <math>B_0</math> निम्नलिखित चरणों को दोहराया जाता है <math>\mathbf{x}_k</math> समाधान के लिए अभिसरण:
+प्रारंभिक अनुमान से <math>\mathbf{x}_0</math> और अनुमानित हेस्सियन मैट्रिक्स <math>B_0</math> निम्नलिखित चरणों को दोहराया <math>\mathbf{x}_k</math> समाधान में परिवर्तित होता है:
-# दिशा प्राप्त करें <math>\mathbf{p}_k</math> हल करके <math>B_k \mathbf{p}_k = -\nabla f(\mathbf{x}_k)</math>.
+# <math>\mathbf{p}_k</math> दिशा प्राप्त करें <math>B_k \mathbf{p}_k = -\nabla f(\mathbf{x}_k)</math> हल करते है।
-# एक स्वीकार्य चरण आकार खोजने के लिए एक आयामी अनुकूलन (लाइन खोज) करें <math>\alpha_k</math> पहले चरण में मिली दिशा में। यदि एक सटीक रेखा खोज की जाती है, तो <math>\alpha_k=\arg \min f(\mathbf{x}_k+\alpha\mathbf{p}_k)</math> . व्यवहार में, एक स्वीकार्य रेखा के साथ एक अचूक रेखा खोज आमतौर पर पर्याप्त होती है <math>\alpha_k</math> संतोषजनक वोल्फ की स्थिति।
+#अनुकूल चरण आकार परीक्षण के लिए  <math>\alpha_k</math> पहले चरण में मिली दिशा में आयामी आकलन (रेखा परीक्षण) करें। यदि सटीक रेखा परीक्षण की जाती, तो <math>\alpha_k=\arg \min f(\mathbf{x}_k+\alpha\mathbf{p}_k)</math> है। पद्धति में, अनुकूल रेखा के साथ अचूक रेखा परीक्षण सामान्यतः <math>\alpha_k</math> संतोषजनक वोल्फ की स्थिति पर पर्याप्त होती है।
-# तय करना <math> \mathbf{s}_k = \alpha_k \mathbf{p}_k</math> और अपडेट करें <math>\mathbf{x}_{k+1} = \mathbf{x}_k + \mathbf{s}_k</math>.
+# वर्ग <math> \mathbf{s}_k = \alpha_k \mathbf{p}_k</math> और <math>\mathbf{x}_{k+1} = \mathbf{x}_k + \mathbf{s}_k</math> अपडेट करते है।
 # <math>\mathbf{y}_k = {\nabla f(\mathbf{x}_{k+1}) - \nabla f(\mathbf{x}_k)}</math>.
 # <math>B_{k+1} = B_k + \frac{\mathbf{y}_k \mathbf{y}_k^{\mathrm{T}}}{\mathbf{y}_k^{\mathrm{T}} \mathbf{s}_k} - \frac{B_k \mathbf{s}_k \mathbf{s}_k^{\mathrm{T}} B_k^{\mathrm{T}} }{\mathbf{s}_k^{\mathrm{T}} B_k \mathbf{s}_k}</math>.
-<math>f(\mathbf{x})</math> कम से कम किए जाने वाले उद्देश्य समारोह को दर्शाता है। ढाल के मानदंड को देखकर अभिसरण की जाँच की जा सकती है, <math>||\nabla f(\mathbf{x}_k)||</math>. अगर <math>B_0</math> के साथ प्रारंभ किया गया है <math>B_0 = I</math>, पहला चरण [[ढतला हुआ वंश]] के बराबर होगा, लेकिन आगे के चरण अधिक से अधिक परिष्कृत होते जा रहे हैं <math>B_{k}</math>, हेस्सियन के सन्निकटन।
+<math>f(\mathbf{x})</math> कम से कम किए जाने वाले सामान्य फलन को दर्शाता है। अनुपात के मानक, <math>||\nabla f(\mathbf{x}_k)||</math> को देखकर अभिसरण की जांच की जा सकती है। अगर <math>B_0</math> के साथ प्रारंभ किया  <math>B_0 = I</math>, पहला चरण ग्रेडिएंट डिसेंट के बराबर होगा, लेकिन <math>B_{k}</math>, हेस्सियन के सन्निकटन आगे के चरण अधिक से अधिक परिष्कृत होते जा रहे हैं।
-एल्गोरिथ्म का पहला चरण मैट्रिक्स के व्युत्क्रम का उपयोग करके किया जाता है <math>B_k</math>, जिसे एल्गोरिथम के चरण 5 में शर्मन-मॉरिसन सूत्र को लागू करके कुशलता से प्राप्त किया जा सकता है
+एल्गोरिथ्म का पहला चरण  <math>B_k</math> मैट्रिक्स के व्युत्क्रम का उपयोग करके किया जाता है, जिसे एल्गोरिथम के चरण 5 में शर्मन-मॉरिसन सूत्र को लागू करके कुशलता से प्राप्त किया जा सकता है।
 : <math>B_{k+1}^{-1} = \left(I - \frac{\mathbf{s}_k \mathbf{y}_k^T}{\mathbf{y}_k^T \mathbf{s}_k} \right) B_{k}^{-1} \left(I - \frac{\mathbf{y}_k \mathbf{s}_k^T}{\mathbf{y}_k^T \mathbf{s}_k} \right) + \frac{\mathbf{s}_k \mathbf{s}_k^T}{\mathbf{y}_k^T \mathbf{s}_k}.</math>
-यह पहचानते हुए, अस्थायी मैट्रिसेस के बिना कुशलता से गणना की जा सकती है <math>B_k^{-1}</math> सममित है,
+अस्थायी मैट्रिसेस के बिना कुशलता से गणना की जा सकती है, यह मानते हुए कि <math>B_k^{-1}</math> सममित है, और वह <math>\mathbf{y}_k^{\mathrm{T}} B_k^{-1} \mathbf{y}_k</math> और <math>\mathbf{s}_k^{\mathrm{T}} \mathbf{y}_k</math> विस्तार का उपयोग करते हुए स्केलर हैं,
-ओर वो <math>\mathbf{y}_k^{\mathrm{T}} B_k^{-1} \mathbf{y}_k</math> और <math>\mathbf{s}_k^{\mathrm{T}} \mathbf{y}_k</math> स्केलर हैं, जैसे विस्तार का उपयोग कर रहे हैं
 : <math>B_{k+1}^{-1} = B_k^{-1} + \frac{(\mathbf{s}_k^{\mathrm{T}}\mathbf{y}_k+\mathbf{y}_k^{\mathrm{T}} B_k^{-1} \mathbf{y}_k)(\mathbf{s}_k \mathbf{s}_k^{\mathrm{T}})}{(\mathbf{s}_k^{\mathrm{T}} \mathbf{y}_k)^2} - \frac{B_k^{-1} \mathbf{y}_k \mathbf{s}_k^{\mathrm{T}} + \mathbf{s}_k \mathbf{y}_k^{\mathrm{T}}B_k^{-1}}{\mathbf{s}_k^{\mathrm{T}} \mathbf{y}_k}.</math>
 इसलिए, किसी भी मैट्रिक्स व्युत्क्रम से बचने के लिए, हेस्सियन के व्युत्क्रम को हेस्सियन के बजाय अनुमानित किया जा सकता है: <math>H_k \overset{\operatorname{def}}{=} B_k^{-1}.</math><ref name="Nocedal">{{Citation | last1=Nocedal | first1=Jorge | last2=Wright | first2=Stephen J. | title=Numerical Optimization | publisher=[[Springer-Verlag]] | location=Berlin, New York | edition=2nd | isbn=978-0-387-30303-1 | year=2006}}</ref>
-प्रारंभिक अनुमान से <math>\mathbf{x}_0</math> और अनुमानित उलटा हेस्सियन मैट्रिक्स <math>H_0</math> निम्नलिखित चरणों को दोहराया जाता है <math>\mathbf{x}_k</math> समाधान के लिए अभिसरण:
-# दिशा प्राप्त करें <math>\mathbf{p}_k</math> हल करके <math>\mathbf{p}_k = -H_k \nabla f(\mathbf{x}_k)</math>.
+प्रारंभिक अनुमान से <math>\mathbf{x}_0</math> और अनुमानित व्युत्क्रम हेस्सियन मैट्रिक्स <math>H_0</math> निम्नलिखित चरणों को दोहराया जाता है <math>\mathbf{x}_k</math> समाधान में अभिसरण करता है:
-# एक स्वीकार्य चरण आकार खोजने के लिए एक आयामी अनुकूलन (लाइन खोज) करें <math>\alpha_k</math> पहले चरण में मिली दिशा में। यदि एक सटीक रेखा खोज की जाती है, तो <math>\alpha_k=\arg \min f(\mathbf{x}_k+\alpha\mathbf{p}_k)</math> . व्यवहार में, एक स्वीकार्य रेखा के साथ एक अचूक रेखा खोज आमतौर पर पर्याप्त होती है <math>\alpha_k</math> संतोषजनक वोल्फ की स्थिति।
+# <math>\mathbf{p}_k</math> हल करके <math>\mathbf{p}_k = -H_k \nabla f(\mathbf{x}_k)</math> दिशा प्राप्त करते है।
-# तय करना <math> \mathbf{s}_k = \alpha_k \mathbf{p}_k</math> और अपडेट करें <math>\mathbf{x}_{k+1} = \mathbf{x}_k + \mathbf{s}_k</math>.
+# अनुकूल चरण आकार परीक्षण के लिए, <math>\alpha_k</math> पहले चरण में मिली दिशा में आयामी आकलन (रेखा परीक्षण) करें। यदि सटीक रेखा परीक्षण की जाती, तो <math>\alpha_k=\arg \min f(\mathbf{x}_k+\alpha\mathbf{p}_k)</math> है। पद्धति में,  एक अनुकूल रेखा के साथ अचूक रेखा परीक्षण सामान्यतः <math>\alpha_k</math> संतोषजनक वोल्फ की स्थिति पर पर्याप्त होती है।
+# वर्ग <math> \mathbf{s}_k = \alpha_k \mathbf{p}_k</math> और <math>\mathbf{x}_{k+1} = \mathbf{x}_k + \mathbf{s}_k</math> अपडेट करते है।
 # <math>\mathbf{y}_k = {\nabla f(\mathbf{x}_{k+1}) - \nabla f(\mathbf{x}_k)}</math>.
 # <math>H_{k+1} = H_k + \frac{(\mathbf{s}_k^{\mathrm{T}}\mathbf{y}_k+\mathbf{y}_k^{\mathrm{T}} H_k \mathbf{y}_k)(\mathbf{s}_k \mathbf{s}_k^{\mathrm{T}})}{(\mathbf{s}_k^{\mathrm{T}} \mathbf{y}_k)^2} - \frac{H_k \mathbf{y}_k \mathbf{s}_k^{\mathrm{T}} + \mathbf{s}_k \mathbf{y}_k^{\mathrm{T}}H_k}{\mathbf{s}_k^{\mathrm{T}} \mathbf{y}_k}</math>.
-सांख्यिकीय आकलन समस्याओं में (जैसे कि [[अधिकतम संभावना अनुमान]] या बायेसियन अनुमान), समाधान के लिए [[विश्वसनीय अंतराल]] या [[विश्वास अंतराल]] का अनुमान अंतिम हेस्सियन मैट्रिक्स के मैट्रिक्स व्युत्क्रम से लगाया जा सकता है। {{Citation needed|reason=there is a need to see in which works this was applied, esp. given the next sentence|date=May 2021}}. हालांकि, इन मात्राओं को तकनीकी रूप से सही हेस्सियन मैट्रिक्स द्वारा परिभाषित किया गया है, और बीएफजीएस सन्निकटन सही हेस्सियन मैट्रिक्स में परिवर्तित नहीं हो सकता है।<ref>{{Cite journal | last1=Ge | last2=Powell| first1=Ren-pu | first2=M. J. D. | title=The Convergence of Variable Metric Matrices in Unconstrained Optimization | journal=[[Mathematical Programming]] |volume=27| year=1983 | issue=2|at=123 |doi=10.1007/BF02591941 | s2cid=8113073}}</ref>
+सांख्यिकीय आकलन समस्याओं में (जैसे कि [[अधिकतम संभावना अनुमान]] या बायेसियन अनुमान), समाधान के लिए [[विश्वसनीय अंतराल]] या [[विश्वास अंतराल]] का अनुमान अंतिम हेस्सियन मैट्रिक्स के मैट्रिक्स व्युत्क्रम से लगाया जा सकता है। यद्यपि, इन मात्राओं को तकनीकी रूप से सही हेस्सियन मैट्रिक्स द्वारा परिभाषित किया गया है और ब्रॉयडेन-फ्लेचर-गोल्डफार्ब-शन्नो सन्निकटन सही हेस्सियन मैट्रिक्स में परिवर्तित नहीं हो सकता है।<ref>{{Cite journal | last1=Ge | last2=Powell| first1=Ren-pu | first2=M. J. D. | title=The Convergence of Variable Metric Matrices in Unconstrained Optimization | journal=[[Mathematical Programming]] |volume=27| year=1983 | issue=2|at=123 |doi=10.1007/BF02591941 | s2cid=8113073}}</ref>
 == उल्लेखनीय कार्यान्वयन ==
 उल्लेखनीय ओपन सोर्स कार्यान्वयन हैं:
-* [[ALGLIB]] BFGS और इसके सीमित-स्मृति संस्करण को C++ और C# में लागू करता है
+* [[ALGLIB|अल्गलिब]] ब्रॉयडेन-फ्लेचर-गोल्डफार्ब-शन्नो और इसके सीमित-स्मृति संस्करण को C++ और C# में लागू करता है।
-* [[जीएनयू ऑक्टेव]] अपने में बीएफजीएस के एक रूप का उपयोग करता है <code>fsolve</code> समारोह, [[विश्वास क्षेत्र]] एक्सटेंशन के साथ।
+* [[जीएनयू ऑक्टेव]] ट्रस्ट क्षेत्र विस्तार के साथ अपने <code>fsolve</code>फलन, में ब्रॉयडेन-फ्लेचर-गोल्डफार्ब-शन्नो के रूप का उपयोग करता है।
-* [[जीएनयू वैज्ञानिक पुस्तकालय]] BFGS को gsl_multimin_fdfminimizer_vector_bfgs2 के रूप में लागू करती है।<ref>{{Cite web|title=GNU Scientific Library — GSL 2.6 documentation|url=https://www.gnu.org/software/gsl/doc/html/index.html|access-date=2020-11-22|website=www.gnu.org}}</ref>
+* [[जीएनयू  वैज्ञानिक पुस्तकालय]] ब्रॉयडेन-फ्लेचर-गोल्डफार्ब-शन्नो को gsl_multimin_fdfminimizer_vector_ब्रॉयडेन-फ्लेचर-गोल्डफार्ब-शन्नो2 के रूप में लागू करती है।<ref>{{Cite web|title=GNU Scientific Library — GSL 2.6 documentation|url=https://www.gnu.org/software/gsl/doc/html/index.html|access-date=2020-11-22|website=www.gnu.org}}</ref>
-* [[आर (प्रोग्रामिंग भाषा)]] में, बीएफजीएस एल्गोरिदम (और एल-बीएफजीएस-बी संस्करण जो बॉक्स बाधाओं की अनुमति देता है) को आधार फ़ंक्शन ऑप्टिम () के विकल्प के रूप में कार्यान्वित किया जाता है।<ref>{{Cite web|title=R: General-purpose Optimization|url=https://stat.ethz.ch/R-manual/R-devel/library/stats/html/optim.html|access-date=2020-11-22|website=stat.ethz.ch}}</ref>
+* [[आर (प्रोग्रामिंग भाषा)|R (प्रोग्रामिंग भाषा)]] में, ब्रॉयडेन-फ्लेचर-गोल्डफार्ब-शन्नो एल्गोरिदम (और L-ब्रॉयडेन-फ्लेचर-गोल्डफार्ब-शन्नो-B संस्करण जो बॉक्स बाधाओं की अनुमति देता है) को आधार फलन ऑप्टिम () के विकल्प के रूप में लागू किया गया है।<ref>{{Cite web|title=R: General-purpose Optimization|url=https://stat.ethz.ch/R-manual/R-devel/library/stats/html/optim.html|access-date=2020-11-22|website=stat.ethz.ch}}</ref>
-* [[SciPy]] में, scipy.optimize.fmin_bfgs फ़ंक्शन BFGS लागू करता है।<ref>{{Cite web|title=scipy.optimize.fmin_bfgs — SciPy v1.5.4 Reference Guide|url=https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.fmin_bfgs.html|access-date=2020-11-22|website=docs.scipy.org}}</ref> पैरामीटर एल को बहुत बड़ी संख्या में सेट करके किसी भी एल-बीएफजीएस एल्गोरिदम का उपयोग करके बीएफजीएस चलाना भी संभव है।
+* [[SciPy]] में, scipy.optimize.fmin_ब्रॉयडेन-फ्लेचर-गोल्डफार्ब-शन्नो फलन ब्रॉयडेन-फ्लेचर-गोल्डफार्ब-शन्नो लागू करता है।<ref>{{Cite web|title=scipy.optimize.fmin_bfgs — SciPy v1.5.4 Reference Guide|url=https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.fmin_bfgs.html|access-date=2020-11-22|website=docs.scipy.org}}</ref> पैरामीटर L को बहुत बड़ी संख्या में सेट करके किसी भी L-ब्रॉयडेन-फ्लेचर-गोल्डफार्ब-शन्नो एल्गोरिदम का उपयोग करके ब्रॉयडेन-फ्लेचर-गोल्डफार्ब-शन्नो चलाना भी संभव है।
-* जूलिया (प्रोग्रामिंग लैंग्वेज) में, [https://julianlsolvers.github.io/Optim.jl/stable/ Optim.jl] पैकेज BFGS और L-BFGS को ऑप्टिमाइज () फंक्शन के सॉल्वर विकल्प के रूप में लागू करता है (अन्य के बीच) विकल्प)।<ref>{{cite web |title=Optim.jl Configurable options |url=https://julianlsolvers.github.io/Optim.jl/stable/#user/config/#solver-options |website=julianlsolvers}}</ref>
+* जूलिया (प्रोग्रामिंग लैंग्वेज) में, [https://julianlsolvers.github.io/Optim.jl/stable/ Optim.jl] पैकेज ब्रॉयडेन-फ्लेचर-गोल्डफार्ब-शन्नो और L-ब्रॉयडेन-फ्लेचर-गोल्डफार्ब-शन्नो को ऑप्टिमाइज () फलन के सॉल्वर विकल्प के रूप में लागू करता है (अन्य के बीच) विकल्प)।<ref>{{cite web |title=Optim.jl Configurable options |url=https://julianlsolvers.github.io/Optim.jl/stable/#user/config/#solver-options |website=julianlsolvers}}</ref>
-उल्लेखनीय मालिकाना कार्यान्वयन में शामिल हैं:
+उल्लेखनीय एकायत्‍त कार्यान्वयन में सम्मलित हैं:
-* बड़े पैमाने पर नॉनलाइनियर ऑप्टिमाइज़ेशन सॉफ़्टवेयर [[Artelys Knitro]], दूसरों के बीच, BFGS और L-BFGS एल्गोरिदम दोनों को लागू करता है।
+* बड़े पैमाने पर नॉनलाइनियर ऑप्टिमाइज़ेशन सॉफ़्टवेयर [[Artelys Knitro]], दूसरों के बीच, ब्रॉयडेन-फ्लेचर-गोल्डफार्ब-शन्नो और L-ब्रॉयडेन-फ्लेचर-गोल्डफार्ब-शन्नो एल्गोरिदम दोनों को लागू करता है।
-* MATLAB [[अनुकूलन टूलबॉक्स]] में, समस्या का आकार मध्यम पैमाने पर सेट होने पर fminunc फ़ंक्शन क्यूबिक लाइन खोज के साथ BFGS का उपयोग करता है।
+* मैट्रिक्स प्रयोगशाला [[अनुकूलन टूलबॉक्स|आकलन टूलबॉक्स]] में, fminunc फलन घन रेखा के साथ ब्रॉयडेन-फ्लेचर-गोल्डफार्ब-शन्नो का उपयोग करता है जब समस्या का आकार "मध्यम स्केल" पर सेट होता है।
-* गणित में बीएफजीएस शामिल है।
 == यह भी देखें ==
@@ Line 98: / Line 90: @@
 * सममित रैंक-एक
 {{Div col end}}
 == संदर्भ ==
 {{reflist}}
 == अग्रिम पठन ==
 * {{Citation | last1=Avriel |first1=Mordecai |year=2003|title=Nonlinear Programming: Analysis and Methods|publisher= Dover Publishing|isbn= 978-0-486-43227-4}}
@@ Line 110: / Line 98: @@
 * {{Citation|last1=Luenberger|first1=David G.|author-link1=David G. Luenberger|last2=Ye|first2=Yinyu|author-link2=Yinyu Ye|title=Linear and nonlinear programming|edition=Third|series=International Series in Operations Research & Management Science|volume=116|publisher=Springer|location=New York|year=2008|pages=xiv+546|isbn=978-0-387-74502-2| mr = 2423726}}
 * {{citation |last=Kelley |first=C. T. |title=Iterative Methods for Optimization |location=Philadelphia |publisher=Society for Industrial and Applied Mathematics |year=1999 |isbn=0-89871-433-8 |pages=71–86 }}
-{{Optimization algorithms|unconstrained}}
+{{DEFAULTSORT:Broyden-Fletcher-Goldfarb-Shanno algorithm}}
-{{DEFAULTSORT:Broyden-Fletcher-Goldfarb-Shanno algorithm}}[[Category: अनुकूलन एल्गोरिदम और तरीके]]
-[[Category: Machine Translated Page]]
+[[Category:Articles with hatnote templates targeting a nonexistent page|Broyden-Fletcher-Goldfarb-Shanno algorithm]]
-[[Category:Created On 13/02/2023]]
+[[Category:Created On 13/02/2023|Broyden-Fletcher-Goldfarb-Shanno algorithm]]
+[[Category:Lua-based templates|Broyden-Fletcher-Goldfarb-Shanno algorithm]]
+[[Category:Machine Translated Page|Broyden-Fletcher-Goldfarb-Shanno algorithm]]
+[[Category:Missing redirects|Broyden-Fletcher-Goldfarb-Shanno algorithm]]
+[[Category:Multi-column templates|Broyden-Fletcher-Goldfarb-Shanno algorithm]]
+[[Category:Pages using div col with small parameter|Broyden-Fletcher-Goldfarb-Shanno algorithm]]
+[[Category:Pages with script errors|Broyden-Fletcher-Goldfarb-Shanno algorithm]]
+[[Category:Short description with empty Wikidata description|Broyden-Fletcher-Goldfarb-Shanno algorithm]]
+[[Category:Templates Vigyan Ready|Broyden-Fletcher-Goldfarb-Shanno algorithm]]
+[[Category:Templates that add a tracking category|Broyden-Fletcher-Goldfarb-Shanno algorithm]]
+[[Category:Templates that generate short descriptions|Broyden-Fletcher-Goldfarb-Shanno algorithm]]
+[[Category:Templates using TemplateData|Broyden-Fletcher-Goldfarb-Shanno algorithm]]
+[[Category:Templates using under-protected Lua modules|Broyden-Fletcher-Goldfarb-Shanno algorithm]]
+[[Category:Wikipedia fully protected templates|Div col]]
+[[Category:अनुकूलन एल्गोरिदम और तरीके|Broyden-Fletcher-Goldfarb-Shanno algorithm]]

Anonymous

Search

ब्रॉयडेन-फ्लेचर-गोल्डफर्ब-शन्नो एल्गोरिथम: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 09:47, 23 February 2023

Contents

कारण विवरण

एल्गोरिथम

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

यह भी देखें

संदर्भ

अग्रिम पठन

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

ब्रॉयडेन-फ्लेचर-गोल्डफर्ब-शन्नो एल्गोरिथम: Difference between revisions

Latest revision as of 09:47, 23 February 2023

कारण विवरण

एल्गोरिथम

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

यह भी देखें

संदर्भ

अग्रिम पठन

Navigation

Wiki tools

Page tools

Other projects

Categories