طريقة شبه نيوتن

في التحليل العددي ، تُعدّ طريقة شبه نيوتن طريقةً عدديةً تكراريةً تُستخدم إما لإيجاد أصفار الدوال أو لإيجاد قيمها العظمى والصغرى المحلية، وذلك عبر صيغة تكرارية مشابهة لتلك المستخدمة في طريقة نيوتن ، باستثناء أنها تستخدم تقريبات لمشتقات الدوال بدلاً من المشتقات الدقيقة. تتطلب طريقة نيوتن مصفوفة جاكوبي لجميع المشتقات الجزئية لدالة متعددة المتغيرات عند استخدامها للبحث عن الأصفار، أو مصفوفة هيسيان عند استخدامها لإيجاد القيم القصوى . أما طرق شبه نيوتن، فيمكن استخدامها عندما تكون مصفوفات جاكوبي أو هيسيان غير متوفرة أو يصعب حسابها في كل تكرار.

بعض الطرق التكرارية التي تختزل إلى طريقة نيوتن، مثل البرمجة التربيعية المتسلسلة ، يمكن اعتبارها أيضًا طرقًا شبه نيوتنية.

طريقة نيوتن لإيجاد أصفار الدالة${\displaystyle g}$يُعطى عدد المتغيرات المتعددة بواسطة${\displaystyle x_{n+1}=x_{n}-[J_{g}(x_{n})]^{-1}g(x_{n})}$، أين${\displaystyle [J_{g}(x_{n})]^{-1}}$هي المعكوس الأيمن لمصفوفة جاكوبي${\displaystyle J_{g}(x_{n})}$ل${\displaystyle g}$تم تقييمه لـ${\displaystyle x_{n}}$.

بالمعنى الدقيق للكلمة، أي طريقة تحل محل مصفوفة جاكوبي الدقيقة${\displaystyle J_{g}(x_{n})}$مع التقريب، تُعتبر طريقة شبه نيوتن. ^{[ 1 ]} على سبيل المثال، طريقة الوتر (حيث${\displaystyle J_{g}(x_{n})}$يتم استبدالها بـ${\displaystyle J_{g}(x_{0})}$(لكل التكرارات) هو مثال بسيط. تشير الطرق المذكورة أدناه للتحسين إلى فئة فرعية مهمة من طرق شبه نيوتن، وهي طرق القاطع . ^{[ 2 ]}

لا يُعدّ استخدام الطرق المُصممة لإيجاد القيم القصوى لإيجاد الأصفار فكرةً صائبةً دائمًا، إذ تتطلب معظم طرق إيجاد القيم القصوى أن تكون المصفوفة المستخدمة متناظرة. ورغم صحة هذا الشرط عند البحث عن القيم القصوى، إلا أنه نادرًا ما ينطبق عند البحث عن الأصفار. تُعدّ طريقتا برودن "الجيدة" و"السيئة" من الطرق الشائعة لإيجاد القيم القصوى، ويمكن تطبيقهما أيضًا لإيجاد الأصفار. ومن الطرق الأخرى التي يُمكن استخدامها: طريقة تحديث الأعمدة ، وطريقة تحديث الأعمدة العكسية ، وطريقة المربعات الصغرى شبه نيوتن، وطريقة المربعات الصغرى العكسية شبه نيوتن.

في الآونة الأخيرة، طُبقت طرق شبه نيوتن لإيجاد حلول لأنظمة المعادلات المتعددة المترابطة (مثل مسائل تفاعل الموائع مع الهياكل أو مسائل التفاعل في الفيزياء). تسمح هذه الطرق بإيجاد الحل من خلال حل كل نظام مكون على حدة (وهو أبسط من حل النظام الكلي) بطريقة دورية تكرارية حتى يتم التوصل إلى حل النظام الكلي. ^{[ 2 ] [ 3 ]}

يرتبط البحث عن القيمة الصغرى أو العظمى لدالة عددية ارتباطًا وثيقًا بالبحث عن أصفار تدرج تلك الدالة. لذلك، يمكن تطبيق طرق شبه نيوتن بسهولة لإيجاد القيم القصوى للدالة. بعبارة أخرى، إذا${\displaystyle g}$هو تدرج${\displaystyle f}$ثم البحث عن أصفار الدالة ذات القيم المتجهة${\displaystyle g}$يتوافق ذلك مع البحث عن القيم القصوى للدالة ذات القيمة العددية${\displaystyle f}$اليعقوبي من${\displaystyle g}$أصبح الآن الهيسيين${\displaystyle f}$الفرق الرئيسي هو أن مصفوفة هيسيان مصفوفة متناظرة ، على عكس مصفوفة جاكوبي عند البحث عن الأصفار . تستغل معظم طرق شبه نيوتن المستخدمة في التحسين هذا التناظر.

في مجال التحسين ، تُعدّ طرق شبه نيوتن ( وهي حالة خاصة من طرق المقياس المتغير ) خوارزميات لإيجاد القيم العظمى والصغرى المحلية للدوال . تعتمد طرق شبه نيوتن في التحسين على طريقة نيوتن لإيجاد النقاط الثابتة للدالة، أي النقاط التي يكون فيها التدرج مساويًا للصفر. تفترض طريقة نيوتن إمكانية تقريب الدالة محليًا بدالة تربيعية في المنطقة المحيطة بالقيمة المثلى، وتستخدم المشتقة الأولى والثانية لإيجاد النقطة الثابتة. في الأبعاد الأعلى، تستخدم طريقة نيوتن التدرج ومصفوفة هيسيان للمشتقات الثانية للدالة المراد تصغيرها.

في طرق شبه نيوتن، لا يلزم حساب مصفوفة هيسيان. يتم تحديثها بتحليل متجهات التدرج المتتالية. تُعدّ طرق شبه نيوتن تعميمًا لطريقة القاطع لإيجاد جذر المشتقة الأولى للمسائل متعددة الأبعاد. في الأبعاد المتعددة، تكون معادلة القاطع غير محددة ، وتختلف طرق شبه نيوتن في كيفية تقييد الحل، عادةً بإضافة تحديث بسيط منخفض الرتبة للتقدير الحالي لمصفوفة هيسيان.

اقترح الفيزيائي ويليام سي. ديفيدون ، العامل في مختبر أرغون الوطني ، أول خوارزمية شبه نيوتن . وقد طوّرها عام 1959، وهي صيغة تحديث DFP ، التي شاع استخدامها لاحقًا على يد فليتشر وباول عام 1963، ولكنها نادرة الاستخدام اليوم. أما أكثر خوارزميات شبه نيوتن شيوعًا فهي حاليًا صيغة SR1 ( اختصارًا لـ " الرتبة المتناظرة من الدرجة الأولى")، وطريقة BHHH ، وطريقة BFGS واسعة الانتشار (التي اقترحها برودن وفليتشر وغولدفراب وشانو بشكل مستقل عام 1970)، وامتدادها منخفض الذاكرة L-BFGS . وتُعدّ فئة برودن مزيجًا خطيًا من طريقتي DFP وBFGS.

لا تضمن صيغة SR1 أن تظل مصفوفة التحديث موجبة التحديد، ويمكن استخدامها للمسائل غير المحددة. أما طريقة برودن، فلا تتطلب أن تكون مصفوفة التحديث متناظرة، وتُستخدم لإيجاد جذر نظام معادلات عام (بدلاً من التدرج) عن طريق تحديث مصفوفة جاكوبي (بدلاً من مصفوفة هيسيان).

إحدى المزايا الرئيسية لطرق شبه نيوتن مقارنة بطريقة نيوتن هي أن مصفوفة هيسيان (أو، في حالة طرق شبه نيوتن، تقريبها)${\displaystyle B}$لا حاجة لعكسها. تتطلب طريقة نيوتن، ومشتقاتها مثل طرق النقطة الداخلية ، عكس مصفوفة هيسيان، وهو ما يتم تنفيذه عادةً عن طريق حل نظام من المعادلات الخطية ، وغالبًا ما يكون مكلفًا للغاية. في المقابل، عادةً ما تُنتج طرق شبه نيوتن تقديرًا لـ${\displaystyle B^{-1}}$مباشرة.

كما هو الحال في طريقة نيوتن ، يتم استخدام تقريب من الدرجة الثانية لإيجاد الحد الأدنى للدالة${\displaystyle f(x)}$سلسلة تايلور لـ${\displaystyle f(x)}$حول التكرار هو

${\displaystyle f(x_{k}+\Delta x)\approx f(x_{k})+\nabla f(x_{k})^{\mathrm {T} }\,\Delta x+{\frac {1}{2}}\Delta x^{\mathrm {T} }B\,\Delta x,}$

أين (${\displaystyle \nabla f}$) هو التدرج ، و${\displaystyle B}$تقريب لمصفوفة هيسيان . ^{[ 4 ]} تدرج هذا التقريب (بالنسبة إلى${\displaystyle \Delta x}$) يكون

${\displaystyle \nabla f(x_{k}+\Delta x)\approx \nabla f(x_{k})+B\,\Delta x,}$

وتعيين هذا التدرج إلى الصفر (وهو هدف التحسين) يوفر خطوة نيوتن:

${\displaystyle \Delta x=-B^{-1}\nabla f(x_{k}).}$

تقريب هيسيان${\displaystyle B}$يتم اختياره لإرضاء

${\displaystyle \nabla f(x_{k}+\Delta x)=\nabla f(x_{k})+B\,\Delta x,}$

والتي تُسمى معادلة القاطع (متسلسلة تايلور للتدرج نفسه). في أكثر من بُعد واحد${\displaystyle B}$غير محدد . باستخدام${\displaystyle n}$يكفي استخدام قواطع مختلفة لتحديد ذلك.${\displaystyle B}$، لكنها تعادل حساب مصفوفة هيسيان باستخدام الفروق المحدودة. في بُعد واحد، حل المعادلة لـ${\displaystyle B}$وتطبيق خطوة نيوتن مع القيمة المُحدَّثة يُكافئ طريقة القاطع . تختلف طرق شبه نيوتن المختلفة في اختيارها لحل معادلة القاطع (في بُعد واحد، جميع المتغيرات متكافئة). تسعى معظم الطرق (باستثناءات، مثل طريقة برودن ) إلى إيجاد حل متناظر.${\displaystyle B^{T}=B}$); علاوة على ذلك، يمكن تبرير المتغيرات المدرجة أدناه من خلال إيجاد تحديث${\displaystyle B_{k+1}}$هذا أقرب ما يمكن إلى${\displaystyle B_{k}}$في بعض المعايير ؛ أي${\displaystyle B_{k+1}=\operatorname {argmin} _{B}\|B-B_{k}\|_{V}}$، أين${\displaystyle V}$هي مصفوفة موجبة محددة تحدد المعيار. قيمة ابتدائية تقريبية${\displaystyle B_{0}=\beta I}$غالباً ما يكون ذلك كافياً لتحقيق تقارب سريع، على الرغم من عدم وجود استراتيجية عامة للاختيار.${\displaystyle \beta }$[ ^{5 ] لاحظ} أن${\displaystyle B_{0}}$ينبغي أن يكون موجباً ومحدداً. المجهول${\displaystyle x_{k}}$يتم تحديثها بتطبيق خطوة نيوتن المحسوبة باستخدام مصفوفة هيسيان التقريبية الحالية${\displaystyle B_{k}}$:

• ${\displaystyle \Delta x_{k}=-\alpha _{k}B_{k}^{-1}\nabla f(x_{k})}$، مع${\displaystyle \alpha }$تم اختيارها لتلبية شروط وولف ؛
• ${\displaystyle x_{k+1}=x_{k}+\Delta x_{k}}$؛
• التدرج المحسوب عند النقطة الجديدة${\displaystyle \nabla f(x_{k+1})}$، و

${\displaystyle y_{k}=\nabla f(x_{k+1})-\nabla f(x_{k})}$

تُستخدم لتحديث مصفوفة هيسيان التقريبية${\displaystyle B_{k+1}}$أو عكسها مباشرة${\displaystyle H_{k+1}=B_{k+1}^{-1}}$باستخدام صيغة شيرمان-موريسون .

• تتمثل إحدى الخصائص الرئيسية لتحديثات BFGS وDFP في أنه إذا${\displaystyle B_{k}}$موجبة التحديد، و${\displaystyle \alpha _{k}}$يتم اختيارها لتحقيق شروط وولف، ثم${\displaystyle B_{k+1}}$وهي أيضًا موجبة تمامًا.

أكثر صيغ التحديث شيوعاً هي:

طريقة	${\displaystyle \displaystyle B_{k+1}=}$	${\displaystyle H_{k+1}=B_{k+1}^{-1}=}$
BFGS	${\displaystyle B_{k}+{\frac {y_{k}y_{k}^{\mathrm {T} }}{y_{k}^{\mathrm {T} }\Delta x_{k}}}-{\frac {B_{k}\Delta x_{k}(B_{k}\Delta x_{k})^{\mathrm {T} }}{\Delta x_{k}^{\mathrm {T} }B_{k}\,\Delta x_{k}}}}$	${\displaystyle \left(I-{\frac {\Delta x_{k}y_{k}^{\mathrm {T} }}{y_{k}^{\mathrm {T} }\Delta x_{k}}}\right)H_{k}\left(I-{\frac {y_{k}\Delta x_{k}^{\mathrm {T} }}{y_{k}^{\mathrm {T} }\Delta x_{k}}}\right)+{\frac {\Delta x_{k}\Delta x_{k}^{\mathrm {T} }}{y_{k}^{\mathrm {T} }\,\Delta x_{k}}}}$
برودين	${\displaystyle B_{k}+{\frac {y_{k}-B_{k}\Delta x_{k}}{\Delta x_{k}^{\mathrm {T} }\,\Delta x_{k}}}\,\Delta x_{k}^{\mathrm {T} }}$	${\displaystyle H_{k}+{\frac {(\Delta x_{k}-H_{k}y_{k})\Delta x_{k}^{\mathrm {T} }H_{k}}{\Delta x_{k}^{\mathrm {T} }H_{k}\,y_{k}}}}$
عائلة برودين	${\displaystyle (1-\varphi _{k})B_{k+1}^{\text{BFGS}}+\varphi _{k}B_{k+1}^{\text{DFP}},\quad \varphi \in [0,1]}$
DFP	${\displaystyle \left(I-{\frac {y_{k}\,\Delta x_{k}^{\mathrm {T} }}{y_{k}^{\mathrm {T} }\,\Delta x_{k}}}\right)B_{k}\left(I-{\frac {\Delta x_{k}y_{k}^{\mathrm {T} }}{y_{k}^{\mathrm {T} }\,\Delta x_{k}}}\right)+{\frac {y_{k}y_{k}^{\mathrm {T} }}{y_{k}^{\mathrm {T} }\,\Delta x_{k}}}}$	${\displaystyle H_{k}+{\frac {\Delta x_{k}\Delta x_{k}^{\mathrm {T} }}{\Delta x_{k}^{\mathrm {T} }\,y_{k}}}-{\frac {H_{k}y_{k}y_{k}^{\mathrm {T} }H_{k}}{y_{k}^{\mathrm {T} }H_{k}y_{k}}}}$
SR1	${\displaystyle B_{k}+{\frac {(y_{k}-B_{k}\,\Delta x_{k})(y_{k}-B_{k}\,\Delta x_{k})^{\mathrm {T} }}{(y_{k}-B_{k}\,\Delta x_{k})^{\mathrm {T} }\,\Delta x_{k}}}}$	${\displaystyle H_{k}+{\frac {(\Delta x_{k}-H_{k}y_{k})(\Delta x_{k}-H_{k}y_{k})^{\mathrm {T} }}{(\Delta x_{k}-H_{k}y_{k})^{\mathrm {T} }y_{k}}}}$

تشمل الطرق الأخرى طريقة بيرسون، وطريقة ماكورميك، وطريقة باول المتناظرة برودن (PSB)، وطريقة غرينستادت. ^{[ 2 ]} يمكن أيضًا تمثيل تحديثات المصفوفات المتكررة منخفضة الرتبة هذه كمصفوفة أولية بالإضافة إلى تصحيح منخفض الرتبة. يُعرف هذا بالتمثيل شبه نيوتن المضغوط ، وهو فعال بشكل خاص للمسائل المقيدة و/أو الكبيرة.

متى${\displaystyle f}$هي دالة تربيعية محدبة ذات مصفوفة هيسية موجبة التحديد${\displaystyle B}$، يتوقع المرء أن تكون المصفوفات${\displaystyle H_{k}}$يتم توليدها بواسطة طريقة شبه نيوتن للتقارب إلى معكوس مصفوفة هيسيان${\displaystyle H=B^{-1}}$وهذا ينطبق بالفعل على فئة طرق شبه نيوتن القائمة على تحديثات أقل تغيير. ^{[ 6 ]}

في عام ١٩٨٥، نُشرت مقالة بعنوان "طرق شبه نيوتن المنتظمة" ^{[ ٧ ]} ، حاولت تقديم نظرة عامة على مختلف مناهج طرق شبه نيوتن. في هذه المقالة، طُوِّرت فئة شاملة من هذه الطرق، تمثل جميع صيغ الرتبة الأولى لما يُسمى بفئة هوانغ المتناظرة والمُجدَّدة، والتي تشمل طرقًا معروفة مثل دافيدون-فليتشر-باول (DFP)، وبرودن-فليتشر-غولدفراب-شانو (BFGS)، وطرق المقياس المتغير ذاتي القياس (SSVM). كما قُدِّمت اقتراحات لتحسين سلوك حلول طرق شبه نيوتن. وقد تم بناء الفئة التالية من صيغ تحديث شبه نيوتن "المنتظمة" (أي المفضلة للاستخدام نظرًا لخصائصها الخاصة):

${\displaystyle H_{i+1}:=B(H_{i},p_{i},q_{i},\theta _{i},r_{i},\rho _{i})}$

مع

${\displaystyle B(H,p,q,\theta ,r,\rho )=rH+{{\rho \sigma +r\tau \theta } \over \sigma ^{2}}pp^{T}+r{{(\theta -1)} \over \tau }Hqq^{T}H-{{r\theta } \over \sigma }(pq^{T}H+Hqp^{T});}$

${\displaystyle H\in \mathbb {R} ^{nxn}}$إيجابي محدد؛${\displaystyle p,q\in \mathbb {R} ^{n};\epsilon =p^{T}H^{-1}p;}$

${\displaystyle \sigma =p^{T}q;\tau =q^{T}Hq;\theta ,r,\rho \in \mathbb {R} ;r>0;\rho \sigma >0;}$

${\displaystyle \theta [\epsilon \tau -\sigma ^{2}]>-\sigma ^{2};r\tau [\rho \sigma +\theta (r\tau -\rho \sigma )]\geq 0}$.

لتحقيق تقليل تقريبي ودقيق بما فيه الكفاية لحزمة الأشعة، تكون القيم موجبة ومحددة.${\displaystyle H_{0}\in \mathbb {R} ^{nxn}}$وعشوائي${\displaystyle x_{0}\in \mathbb {R} ^{n}}$ينطبق ما يلي على هذه الطرق العادية، والتي تم اشتقاقها من الصيغة المذكورة أعلاه:

1) الطرق هي طرق شبه نيوتن.

2) المصفوفات${\displaystyle H_{i}}$تكون موجبة تمامًا لجميع التكرارات. وبالتالي،

${\displaystyle f(x_{i+1})<f(x_{i})}$ينطبق هذا على جميع التكرارات.

3) لجميع التكرارات${\displaystyle i\geq 0}$، نحصل على حلول لمسألة التصغير.

بالنسبة لتقليل طول الشعاع بدقة ودوال الهدف التربيعية، تنتهي كل من هذه الطرق عند نقطة الحد الأدنى بعد عدد لا يتجاوز n من خطوات التكرار. وعلى وجه الخصوص، تتمتع طرق شبه نيوتن المنتظمة بخصائص جيدة لكل من فئة غرينستادت الموسعة وفئة هوانغ الموسعة المتناظرة فيما يتعلق بالتقارب والاستقرار.

يمكن افتراض أن جميع طرق شبه نيوتن القوية بشكل خاص منتظمة.

تتوفر تطبيقات طرق شبه نيوتن في العديد من لغات البرمجة.

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

• يستخدم برنامج GNU Octave شكلاً من أشكال BFGS في fsolveوظيفته، مع امتدادات منطقة الثقة .
• تقوم مكتبة GNU العلمية بتنفيذ خوارزمية Broyden-Fletcher-Goldfarb-Shanno ( BFGS ).
• تُنفذ مكتبة ALGLIB خوارزمية (L)BFGS في لغتي C++ و C#
• optimيستخدم روتين التحسين للأغراض العامة في R طريقة BFGS باستخدام method="BFGS". ^{[ 8 ]}
• تحتوي دالة .optimize في مكتبة SciPy على fmin_bfgs. في امتداد SciPy للغة بايثون ، scipy.optimize.minimizeتتضمن الدالة، من بين طرق أخرى، تطبيقًا لخوارزمية BFGS . ^{[ 9 ]}

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

• يتضمن برنامج Mathematica حلول شبه نيوتن. ^{[ 10 ]}
• تحتوي مكتبة NAG على العديد من الإجراءات ^{[ 11 ]} لتقليل أو زيادة دالة ^{[ 12 ]} والتي تستخدم خوارزميات شبه نيوتن.
• في حزمة أدوات التحسين في MATLAB ، fminuncتستخدم الدالة (من بين طرق أخرى) طريقة BFGS شبه نيوتن. ^{[ 13 ]} تستخدم العديد من الطرق المقيدة في حزمة أدوات التحسين طريقة BFGS ومتغيرها L-BFGS . ^{[ 14 ]}

• بونانز، جيه إف؛ جيلبرت، جيه. تش.؛ ليمارشال، سي .؛ ساغاستيزابال، سي إيه (2006). التحسين العددي  : الجوانب النظرية والعددية (  الطبعة الثانية). سبرينغر. ISBN 3-540-35445-X.
• فليتشر، روجر (1987)، الأساليب العملية للتحسين (  الطبعة الثانية)، نيويورك: جون وايلي وأولاده ، ISBN 978-0-471-91547-8.
• نوسيدال، خورخي؛ رايت، ستيفن ج. (1999). "طرق شبه نيوتن" . التحسين العددي . نيويورك: سبرينغر. ص 192-221 . ISBN  0-387-98793-2.
• بريس، دبليو إتش؛ تيوكولسكي، إس إيه؛ فيترلينغ، دبليو تي؛ فلانيري، بي بي (2007). "القسم 10.9. طرق شبه نيوتن أو الطرق ذات المقياس المتغير في الأبعاد المتعددة" . وصفات عددية: فن الحوسبة العلمية (  الطبعة الثالثة). نيويورك: مطبعة جامعة كامبريدج. ISBN 978-0-521-88068-8.
• سكيلز، إل إي (1985). مقدمة في التحسين غير الخطي . نيويورك: ماكميلان. الصفحات 84-106 . ISBN  0-333-32552-4.