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

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

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

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

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

कारण विवरण

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

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

उतरने की दिशा p_k स्टेज पर k न्यूटन समीकरण के अनुरूप के समाधान द्वारा दिया गया है:

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

कहाँ $B_{k}$ हेसियन मैट्रिक्स का एक सन्निकटन है, जिसे प्रत्येक चरण में पुनरावृत्त रूप से अद्यतन किया जाता है, और $\nabla f(\mathbf {x} _{k})$ x पर मूल्यांकन किए गए फलन का ग्रेडिएंट है_k. दिशा पी में एक पंक्ति परीक्षण_k फिर अगले बिंदु x को परीक्षणने के लिए प्रयोग किया जाता है_k+1 कम करके $f(\mathbf {x} _{k}+\gamma \mathbf {p} _{k})$ अदिश के ऊपर $\gamma >0.$ अर्ध-न्यूटन स्थिति के अद्यतन पर लगाया गया $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}$ सममित रैंक-वन मैट्रिसेस हैं, लेकिन उनका योग रैंक-टू अपडेट मैट्रिक्स है। BFGS और डेविडॉन-फ्लेचर-पॉवेल फॉर्मूला अपडेटिंग मैट्रिक्स दोनों अपने पूर्ववर्ती से रैंक-दो मैट्रिक्स से भिन्न हैं। एक और सरल रैंक-वन विधि को सममित रैंक-वन विधि के रूप में जाना जाता है, जो सकारात्मक निश्चितता की गारंटी नहीं देती है। समरूपता और सकारात्मक निश्चितता बनाए रखने के लिए $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}}}$.

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

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

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

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

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

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

यह भी देखें

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

अग्रिम पठन

• 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

| group5 = Metaheuristics | abbr5 = heuristic | list5 =

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

| below =

• Software

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

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

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

}}