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

"ब्रॉयडेन-फ्लेचर-गोल्डफार्ब-शन्नो" redirects here. For कैनेडियन हार्डकोर पंक बैंड, see बंचोफकिंगोफ्स.

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

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

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

कारण विवरण

$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}$, हम प्राप्त कर सकते हैं:

$\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}$ समाधान में परिवर्तित होता है:

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

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

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

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

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

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

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

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

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

यह भी देखें

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

अग्रिम पठन

• 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