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

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

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

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

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

औचित्य

अनुकूलन समस्या को कम करना है $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}$ सममित रैंक-वन मैट्रिसेस हैं, लेकिन उनका योग रैंक-टू अपडेट मैट्रिक्स है। बीएफजीएस और डेविडॉन-फ्लेचर-पॉवेल फॉर्मूला अपडेटिंग मैट्रिक्स दोनों अपने पूर्ववर्ती से रैंक-दो मैट्रिक्स से भिन्न हैं। एक और सरल रैंक-वन विधि को सममित रैंक-वन विधि के रूप में जाना जाता है, जो सकारात्मक निश्चितता की गारंटी नहीं देती है। समरूपता और सकारात्मक निश्चितता बनाए रखने के लिए $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}}}$.

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

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

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

• ALGLIB BFGS और इसके सीमित-स्मृति संस्करण को C++ और C# में लागू करता है
• जीएनयू ऑक्टेव अपने में बीएफजीएस के एक रूप का उपयोग करता है fsolve समारोह, विश्वास क्षेत्र एक्सटेंशन के साथ।
• जीएनयू वैज्ञानिक पुस्तकालय BFGS को gsl_multimin_fdfminimizer_vector_bfgs2 के रूप में लागू करती है।
• आर (प्रोग्रामिंग भाषा) में, बीएफजीएस एल्गोरिदम (और एल-बीएफजीएस-बी संस्करण जो बॉक्स बाधाओं की अनुमति देता है) को आधार फ़ंक्शन ऑप्टिम () के विकल्प के रूप में कार्यान्वित किया जाता है।
• SciPy में, scipy.optimize.fmin_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 =* सॉफ्टवेयर

}}