خوارزمية برودن-فليتشر-جولدفراب-شانو

في مجال التحسين العددي ، تُعد خوارزمية برودن-فليتشر-غولدفراب-شانو ( BFGS ) طريقة تكرارية لحل مسائل التحسين غير الخطي غير المقيد. ^{[ 1 ]} وكما هو الحال في طريقة ديفيدون-فليتشر-باول ، تحدد خوارزمية BFGS اتجاه الانحدار من خلال تهيئة التدرج بمعلومات الانحناء. ويتم ذلك عن طريق التحسين التدريجي لتقريب مصفوفة هيسيان لدالة الخسارة ، والتي يتم الحصول عليها فقط من تقييمات التدرج (أو تقييمات التدرج التقريبية) باستخدام طريقة القاطع المعممة . ^{[ 2 ]}

بما أن تحديثات مصفوفة انحناء BFGS لا تتطلب عكس المصفوفة ، فإن تعقيدها الحسابي هو فقط${\displaystyle {\mathcal {O}}(n^{2})}$، مقارنة ب${\displaystyle {\mathcal {O}}(n^{3})}$في طريقة نيوتن . كما يشيع استخدام L-BFGS ، وهو نسخة محدودة الذاكرة من BFGS، مناسبة بشكل خاص للمسائل ذات الأعداد الكبيرة جدًا من المتغيرات (مثلًا، أكثر من 1000). ويتعامل متغير BFGS-B مع قيود الصندوق البسيطة. ^{[ 3 ]} كما تسمح مصفوفة BFGS بتمثيل مضغوط ، مما يجعلها أكثر ملاءمة للمسائل المقيدة الكبيرة.

سُميت الخوارزمية نسبةً إلى تشارلز جورج برودن ، وروجر فليتشر ، ودونالد غولدفراب ، وديفيد شانو . ^{[ 4 ] [ 5 ] [ 6 ] [ 7 ]} وهي مثال على خوارزمية أكثر عمومية وضعها جون غرينستادت. ^{[ 8 ]}

تتمثل مشكلة التحسين في تقليل${\displaystyle f(\mathbf {x} )}$، أين${\displaystyle \mathbf {x} }$هو متجه في${\displaystyle \mathbb {R} ^{n}}$، و${\displaystyle f}$هي دالة قياسية قابلة للتفاضل. لا توجد قيود على القيم التي${\displaystyle \mathbf {x} }$يمكن أن يأخذ.

تبدأ الخوارزمية بتقدير أولي${\displaystyle \mathbf {x} _{0}}$للحصول على القيمة المثلى، ثم يتابع بشكل تكراري للحصول على تقدير أفضل في كل مرحلة.

يُعطى اتجاه البحث p k _في المرحلة k بواسطة حل معادلة نيوتن المماثلة:

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

أين${\displaystyle B_{k}}$هي تقريب لمصفوفة هيسيان عند${\displaystyle \mathbf {x} _{k}}$والتي يتم تحديثها بشكل متكرر في كل مرحلة، و${\displaystyle \nabla f(\mathbf {x} _{k})}$يمثل تدرج الدالة عند النقطة x _k . ثم يُستخدم بحث خطي في اتجاه p _k لإيجاد النقطة التالية x _{k + 1} عن طريق تقليل${\displaystyle f(\mathbf {x} _{k}+\gamma \mathbf {p} _{k})}$على الكمية القياسية${\displaystyle \gamma >0.}$

الشرط شبه النيوتني المفروض على تحديث${\displaystyle B_{k}}$يكون

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

يترك${\displaystyle \mathbf {y} _{k}=\nabla f(\mathbf {x} _{k+1})-\nabla f(\mathbf {x} _{k})}$و${\displaystyle \mathbf {s} _{k}=\mathbf {x} _{k+1}-\mathbf {x} _{k}}$، ثم${\displaystyle B_{k+1}}$يرضي

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

وهي معادلة القاطع.

حالة الانحناء${\displaystyle \mathbf {s} _{k}^{\mathsf {T}}\mathbf {y} _{k}>0}$ينبغي أن يكون راضياً عن${\displaystyle B_{k+1}}$لكي تكون موجبة تمامًا، وهو ما يمكن التحقق منه عن طريق ضرب معادلة القاطع من اليسار بـ${\displaystyle \mathbf {s} _{k}^{\mathsf {T}}}$إذا لم تكن الدالة محدبة بقوة ، فيجب فرض الشرط بشكل صريح، على سبيل المثال عن طريق إيجاد نقطة x _{k +1} تحقق شروط وولف ، والتي تستلزم شرط الانحناء، باستخدام البحث الخطي.

بدلاً من اشتراط مصفوفة هيسيان الكاملة عند النقطة${\displaystyle \mathbf {x} _{k+1}}$يتم حسابها على النحو التالي${\displaystyle B_{k+1}}$يتم تحديث مصفوفة هيسيان التقريبية في المرحلة k عن طريق إضافة مصفوفتين:

${\displaystyle B_{k+1}=B_{k}+U_{k}+V_{k}.}$

كلاهما${\displaystyle U_{k}}$و${\displaystyle V_{k}}$هي مصفوفات متناظرة من الرتبة الأولى، لكن مجموعها عبارة عن مصفوفة تحديث من الرتبة الثانية. تختلف مصفوفة تحديث BFGS و DFP عن سابقتها بمصفوفة من الرتبة الثانية. هناك طريقة أخرى أبسط من الرتبة الأولى تُعرف باسم طريقة الرتبة الأولى المتناظرة ، والتي لا تضمن الإيجابية المحددة . وللحفاظ على التناظر والإيجابية المحددة لـ${\displaystyle B_{k+1}}$يمكن اختيار نموذج التحديث كـ${\displaystyle B_{k+1}=B_{k}+\alpha \mathbf {u} \mathbf {u} ^{\mathsf {T}}+\beta \mathbf {v} \mathbf {v} ^{\mathsf {T}}}$بفرض شرط القاطع،${\displaystyle B_{k+1}\mathbf {s} _{k}=\mathbf {y} _{k}}$اختيار${\displaystyle \mathbf {u} =\mathbf {y} _{k}}$و${\displaystyle \mathbf {v} =B_{k}\mathbf {s} _{k}}$، يمكننا الحصول على: ^{[ 9 ]}

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

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

وأخيرًا، نستبدل${\displaystyle \alpha }$و${\displaystyle \beta }$داخل${\displaystyle B_{k+1}=B_{k}+\alpha \mathbf {u} \mathbf {u} ^{\mathsf {T}}+\beta \mathbf {v} \mathbf {v} ^{\mathsf {T}}}$واحصل على معادلة التحديث لـ${\displaystyle B_{k+1}}$:

$// _ {ك}\mathbf {s} _{k}^{\mathsf {T}}B_{k}^{\mathsf {T}}}{\mathbf {s} _{k}^{\mathsf {T}}B_{k}\mathbf {s} _{k}}}.}$

لنفترض مسألة التحسين غير المقيدة التالية $${\displaystyle {\begin{aligned}{\underset {\mathbf {x} \in \mathbb {R} ^{n}}{\text{minimize}}}\quad &f(\mathbf {x} ),\end{aligned}}}$$ أين${\displaystyle f:\mathbb {R} ^{n}\to \mathbb {R} }$هي دالة هدف غير خطية وقابلة للتفاضل مرتين .

من تخمين أولي${\displaystyle \mathbf {x} _{0}\in \mathbb {R} ^{n}}$وتخمين أولي لمصفوفة هيسيان${\displaystyle B_{0}\in \mathbb {R} ^{n\times n}}$تُكرر الخطوات التالية كما يلي${\displaystyle \mathbf {x} _{k}}$يتقارب مع الحل:

1. احصل على توجيهات${\displaystyle \mathbf {p} _{k}}$عن طريق حل${\displaystyle B_{k}\mathbf {p} _{k}=-\nabla f(\mathbf {x} _{k})}$.
2. قم بإجراء عملية تحسين أحادية البعد ( بحث خطي ) لإيجاد حجم خطوة مقبول${\displaystyle \alpha _{k}}$في الاتجاه الذي تم تحديده في الخطوة الأولى. إذا تم إجراء بحث خطي دقيق، فـ${\displaystyle \alpha _{k}=\arg \min _{\alpha }f(\mathbf {x} _{k}+\alpha \mathbf {p} _{k})}$في الواقع العملي، عادةً ما يكفي البحث غير الدقيق عن السطر، مع نتيجة مقبولة.${\displaystyle \alpha _{k}}$استيفاء شروط وولف .
3. تعيين${\displaystyle \mathbf {s} _{k}=\alpha _{k}\mathbf {p} _{k}}$وتحديث${\displaystyle \mathbf {x} _{k+1}=\mathbf {x} _{k}+\mathbf {s} _{k}}$.
4. ${\displaystyle \mathbf {y} _{k}={\nabla f(\mathbf {x} _{k+1})-\nabla f(\mathbf {x} _{k})}}$.
5. $// _ {ك}\mathbf {s} _{k}^{\mathsf {T}}B_{k}^{\mathsf {T}}}{\mathbf {s} _{k}^{\mathsf {T}}B_{k}\mathbf {s} _{k}}}}$.

يمكن تحديد التقارب من خلال ملاحظة معيار التدرج؛ بالنظر إلى بعض${\displaystyle \epsilon >0}$يمكن إيقاف الخوارزمية عندما${\displaystyle ||\nabla f(\mathbf {x} _{k})||\leq \epsilon .}$لو${\displaystyle B_{0}}$يتم تهيئتها بـ${\displaystyle B_{0}=I}$ستكون الخطوة الأولى مكافئة لانحدار التدرج ، لكن الخطوات اللاحقة ستكون أكثر دقةً وتطوراً.${\displaystyle B_{k}}$، التقريب لمصفوفة هيسيان.

تُنفذ الخطوة الأولى من الخوارزمية باستخدام معكوس المصفوفة${\displaystyle B_{k}}$والتي يمكن الحصول عليها بكفاءة عن طريق تطبيق صيغة شيرمان-موريسون على الخطوة 5 من الخوارزمية، مما يعطي

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

يمكن حساب ذلك بكفاءة دون استخدام مصفوفات مؤقتة، مع الأخذ في الاعتبار أن${\displaystyle B_{k}^{-1}}$متناظر، وأن${\displaystyle \mathbf {y} _{k}^{\mathsf {T}}B_{k}^{-1}\mathbf {y} _{k}}$و${\displaystyle \mathbf {s} _{k}^{\mathsf {T}}\mathbf {y} _{k}}$هي كميات قياسية، باستخدام توسيع مثل

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

لذلك، ولتجنب أي عملية عكس للمصفوفة، يمكن تقريب معكوس مصفوفة هيسيان بدلاً من مصفوفة هيسيان نفسها:${\displaystyle H_{k}{\overset {\operatorname {def} }{=}}B_{k}^{-1}.}$^{[ 10 ]}

من تخمين أولي${\displaystyle \mathbf {x} _{0}}$ومصفوفة هيسيان معكوسة تقريبية${\displaystyle H_{0}}$تُكرر الخطوات التالية كما يلي${\displaystyle \mathbf {x} _{k}}$يتقارب مع الحل:

1. احصل على توجيهات${\displaystyle \mathbf {p} _{k}}$عن طريق حل${\displaystyle \mathbf {p} _{k}=-H_{k}\nabla f(\mathbf {x} _{k})}$.
2. قم بإجراء عملية تحسين أحادية البعد ( بحث خطي ) لإيجاد حجم خطوة مقبول${\displaystyle \alpha _{k}}$في الاتجاه الذي تم تحديده في الخطوة الأولى. إذا تم إجراء بحث خطي دقيق، فـ${\displaystyle \alpha _{k}=\arg \min _{\alpha }f(\mathbf {x} _{k}+\alpha \mathbf {p} _{k})}$في الواقع العملي، عادةً ما يكفي البحث غير الدقيق عن السطر، مع نتيجة مقبولة.${\displaystyle \alpha _{k}}$استيفاء شروط وولف .
3. تعيين${\displaystyle \mathbf {s} _{k}=\alpha _{k}\mathbf {p} _{k}}$وتحديث${\displaystyle \mathbf {x} _{k+1}=\mathbf {x} _{k}+\mathbf {s} _{k}}$.
4. ${\displaystyle \mathbf {y} _{k}={\nabla f(\mathbf {x} _{k+1})-\nabla f(\mathbf {x} _{k})}}$.
5. ${\displaystyle H_{k+1}=H_{k}+{\frac {(\mathbf {s} _{k}^{\mathsf {T}}\mathbf {y} _{k}+\mathbf {y} _{k}^{\mathsf {T}}H_{k}\mathbf {y} _{k})(\mathbf {s} _{k}\mathbf {s} _{k}^{\mathsf {T}})}{(\mathbf {s} _{k}^{\mathsf {T}}\mathbf {y} _{k})^{2}}}-{\frac {H_{k}\mathbf {y} _{k}\mathbf {s} _{k}^{\mathsf {T}}+\mathbf {s} _{k}\mathbf {y} _{k}^{\mathsf {T}}H_{k}}{\mathbf {s} _{k}^{\mathsf {T}}\mathbf {y} _{k}}}}$.

في مسائل التقدير الإحصائي (مثل طريقة الاحتمال الأقصى أو الاستدلال البايزي)، يمكن تقدير فترات المصداقية أو فترات الثقة للحل من معكوس مصفوفة هيسيان النهائية . ومع ذلك، فإن هذه الكميات تُعرَّف تقنيًا بواسطة مصفوفة هيسيان الحقيقية، وقد لا يتقارب تقريب BFGS مع مصفوفة هيسيان الحقيقية. ^{[ 11 ]}

تعتمد صيغة تحديث BFGS بشكل كبير على الانحناء${\displaystyle \mathbf {s} _{k}^{\mathsf {T}}\mathbf {y} _{k}}$أن تكون الدالة موجبة تمامًا ومحدودة بعيدًا عن الصفر. يتحقق هذا الشرط عند إجراء بحث خطي باستخدام شروط وولف على هدف محدب. مع ذلك، تُنتج بعض التطبيقات العملية (مثل طرق البرمجة التربيعية المتسلسلة) انحناءات سالبة أو قريبة من الصفر بشكل روتيني. قد يحدث هذا عند تحسين هدف غير محدب أو عند استخدام أسلوب منطقة الثقة بدلًا من البحث الخطي. من الممكن أيضًا إنتاج قيم زائفة بسبب التشويش في الهدف.

في مثل هذه الحالات، يمكن استخدام أحد تحديثات BFGS المخمدة (انظر ^{[ 12 ]} ) والتي تُعدّل${\displaystyle \mathbf {s} _{k}}$و/أو${\displaystyle \mathbf {y} _{k}}$من أجل الحصول على تحديث أكثر قوة.

من أبرز تطبيقات المصادر المفتوحة ما يلي:

• تُنفذ مكتبة ALGLIB خوارزمية BFGS وإصدارها ذي الذاكرة المحدودة في لغتي C++ و C#
• يستخدم برنامج GNU Octave شكلاً من أشكال BFGS في fsolveوظيفته، مع امتدادات منطقة الثقة .
• تُنفذ مكتبة GSL خوارزمية BFGS كـ gsl_multimin_fdfminimizer_vector_bfgs2. ^{[ 13 ]}
• في لغة R ، يتم تنفيذ خوارزمية BFGS (والإصدار L-BFGS-B الذي يسمح بقيود الصندوق) كخيار للدالة الأساسية optim(). ^{[ 14 ]}
• في مكتبة SciPy ، تُنفّذ الدالة scipy.optimize.fmin_bfgs خوارزمية BFGS. ^{[ 15 ]} كما يُمكن تشغيل BFGS باستخدام أيٍّ من خوارزميات L-BFGS عن طريق ضبط قيمة المعامل L على رقم كبير جدًا. وهي أيضًا إحدى الطرق الافتراضية المُستخدمة عند تشغيل scipy.optimize.minimize بدون قيود. ^{[ 16 ]}
• في لغة جوليا ، تُنفذ حزمة Optim.jl خوارزميتي BFGS و L-BFGS كخيار لحل المعادلات في دالة optimize() (من بين خيارات أخرى). ^{[ 17 ]}
• يقوم ستان بتطبيق BFGS مع التفاضل التلقائي كخيار لحل مشاكل تقدير الاحتمال الأقصى وتقدير الاحتمال اللاحق الأقصى .

تشمل التطبيقات الخاصة البارزة ما يلي:

• يقوم برنامج التحسين غير الخطي واسع النطاق Artelys Knitro بتنفيذ خوارزميات BFGS و L-BFGS من بين أمور أخرى.
• في مجموعة أدوات التحسين MATLAB ، تستخدم الدالة fminunc خوارزمية BFGS مع البحث الخطي التكعيبي عندما يتم ضبط حجم المشكلة على "مقياس متوسط".
• يتضمن برنامج Mathematica برنامج BFGS.
• يستخدم برنامج LS-DYNA أيضًا خوارزمية BFGS لحل المشكلات الضمنية.

• أفرييل، موردخاي (2003)، البرمجة غير الخطية: التحليل والأساليب ، دار نشر دوفر، رقم ISBN 978-0-486-43227-4
• بونان، ج.  فريدريك؛ جيلبرت، ج.  تشارلز؛ ليمارشال، كلود ؛ ساغاستيزابال، كلوديا  أ. (2006)، "الأساليب النيوتونية"، التحسين العددي: الجوانب النظرية والعملية (  الطبعة الثانية)، برلين: سبرينغر، ص 51-66 ، ISBN  3-540-35445-X
• فليتشر، روجر (1987)، الأساليب العملية للتحسين (الطبعة الثانية  )، نيويورك: جون وايلي وأولاده ، رقم ISBN 978-0-471-91547-8
• لونبرغر، ديفيد ج .؛ يي، يينيو (2008)، البرمجة الخطية وغير الخطية ، السلسلة الدولية في بحوث العمليات وعلوم الإدارة، المجلد  116 (  الطبعة الثالثة)، نيويورك: سبرينغر، الصفحات  546+14، ISBN 978-0-387-74502-2MR 2423726​ 
• كيلي، سي تي (1999)، الطرق التكرارية للتحسين ، فيلادلفيا: جمعية الرياضيات الصناعية والتطبيقية، الصفحات 71-86 ، رقم ISBN  0-89871-433-8