طريقة نيوتن في التحسين

في حساب التفاضل والتكامل ، طريقة نيوتن (وتسمى أيضًا نيوتن-رافسون ) هي طريقة تكرارية لإيجاد جذور دالة قابلة للاشتقاق ، والتي هي حلول للمعادلة . ومع ذلك، لتحسين دالة قابلة للاشتقاق مرتين ، فإن هدفنا هو إيجاد جذور . وبالتالي، يمكننا استخدام طريقة نيوتن على مشتقتها لإيجاد حلول لـ ، والمعروفة أيضًا باسم النقاط الحرجة لـ . قد تكون هذه الحلول عبارة عن نقاط دنيا أو نقاط قصوى أو نقاط سرج؛ راجع القسم "عدة متغيرات" في النقطة الحرجة (الرياضيات) وأيضًا القسم "التفسير الهندسي" في هذه المقالة. هذا مهم في التحسين ، الذي يهدف إلى إيجاد نقاط دنيا (عالمية) للدالة . ${\displaystyle f}$ ${\displaystyle f(x)=0}$${\displaystyle f}$${\displaystyle f'}$ ${\displaystyle f'}$${\displaystyle f'(x)=0}$${\displaystyle f}$${\displaystyle f}$

المشكلة الأساسية في التحسين هي تقليل الوظائف إلى الحد الأدنى. دعونا أولاً نفكر في حالة الوظائف أحادية المتغير، أي وظائف متغير حقيقي واحد. سننظر لاحقًا في حالة الوظائف المتعددة المتغيرات الأكثر عمومية والأكثر فائدة عمليًا.

بالنظر إلى دالة قابلة للاشتقاق مرتين ، فإننا نسعى إلى حل مشكلة التحسين ${\displaystyle f:\mathbb {R} \to \mathbb {R} }$

${\displaystyle \min _{x\in \mathbb {R} }f(x).}$

تحاول طريقة نيوتن حل هذه المشكلة من خلال إنشاء تسلسل من تخمين أولي (نقطة بداية) يتقارب نحو الحد الأدنى من خلال استخدام تسلسل من تقريبات تايلور من الدرجة الثانية حول التكرارات. توسع تايلور من الدرجة الثانية لـ f حول هو ${\displaystyle \{x_{k}\}}$${\displaystyle x_{0}\in \mathbb {R} }$${\displaystyle x_{*}}$${\displaystyle f}$${\displaystyle f}$${\displaystyle x_{k}}$

${\displaystyle f(x_{k}+t)\approx f(x_{k})+f'(x_{k})t+{\frac {1}{2}}f''(x_{k})t^{2}.}$

يتم تعريف التكرار التالي بحيث يتم تقليل هذا التقريب التربيعي في ، وضبط . إذا كانت المشتقة الثانية موجبة، فإن التقريب التربيعي عبارة عن دالة محدبة لـ ، ويمكن إيجاد الحد الأدنى لها عن طريق ضبط المشتقة على الصفر. نظرًا لأن ${\displaystyle x_{k+1}}$${\displaystyle t}$${\displaystyle x_{k+1}=x_{k}+t}$${\displaystyle t}$

${\displaystyle \displaystyle 0={\frac {\rm {d}}{{\rm {d}}t}\left(f(x_{k})+f'(x_{k})t+{\frac {1}{2}}f''(x_{k})t^{2}\right)=f'(x_{k})+f''(x_{k})t,}$

تم تحقيق الحد الأدنى لـ

${\displaystyle t=-{\f'(x_{k})}{f''(x_{k})}}}}}$

بجمع كل شيء معًا، تقوم طريقة نيوتن بإجراء التكرار

${\displaystyle x_{k+1}=x_{k}+t=x_{k}-{\f'(x_{k})}{f''(x_{k})}}.}$

التفسير الهندسي لطريقة نيوتن هو أنه في كل تكرار، يعادل ذلك تركيب قطع مكافئ للرسم البياني لـ عند القيمة التجريبية ، التي لها نفس ميل وانحناء الرسم البياني عند تلك النقطة، ثم الانتقال إلى الحد الأقصى أو الأدنى لذلك القطع المكافئ (في الأبعاد الأعلى، قد تكون هذه أيضًا نقطة سرج )، انظر أدناه. لاحظ أنه إذا كانت دالة تربيعية، فسيتم العثور على الحد الأقصى الدقيق في خطوة واحدة. ${\displaystyle f(x)}$${\displaystyle x_{k}}$${\displaystyle f}$

يمكن تعميم المخطط التكراري أعلاه على الأبعاد عن طريق استبدال المشتقة بالتدرج ( يستخدم مؤلفون مختلفون تدوينًا مختلفًا للتدرج، بما في ذلك )، ومعكوس المشتقة الثانية مع معكوس مصفوفة هيسيان (يستخدم مؤلفون مختلفون تدوينًا مختلفًا لمصفوفة هيسيان، بما في ذلك ). وبالتالي نحصل على المخطط التكراري ${\displaystyle d>1}$${\displaystyle f'(x)=\nabla f(x)=g_{f}(x)\in \mathbb {R} ^{d}}$${\displaystyle f''(x)=\nabla ^{2}f(x)=H_{f}(x)\in \mathbb {R} ^{d\times d}}$

${\displaystyle x_{k+1}=x_{k}-[f''(x_{k})]^{-1}f'(x_{k}),\qquad k\geq 0.}$

في كثير من الأحيان يتم تعديل طريقة نيوتن لتشمل حجم خطوة صغير بدلاً من : ${\displaystyle 0<\gamma \leq 1}$${\displaystyle \gamma =1}$

${\displaystyle x_{k+1}=x_{k}-\gamma [f''(x_{k})]^{-1}f'(x_{k}).}$

غالبًا ما يتم ذلك للتأكد من استيفاء شروط وولف ، أو شرط أرميجو الأكثر بساطة وكفاءة ، في كل خطوة من خطوات الطريقة. بالنسبة لأحجام الخطوات بخلاف 1، غالبًا ما يشار إلى الطريقة باسم طريقة نيوتن المريحة أو المخففة.

إذا كانت f دالة محدبة بقوة مع Lipschitz Hessian، فبشرط أن تكون قريبة بدرجة كافية من ، فإن التسلسل الناتج عن طريقة نيوتن سوف يتقارب مع المُقلل (الفريد بالضرورة) لـ سريع تربيعيًا. ^[1] أي، ${\displaystyle x_{0}}$${\displaystyle x_{*}=\arg \min f(x)}$${\displaystyle x_{0},x_{1},x_{2},\dots }$${\displaystyle x_{*}}$${\displaystyle f}$

${\displaystyle \|x_{k+1}-x_{*}\|\leq {\frac {1}{2}}\|x_{k}-x_{*}\|^{2},\qquad \forall k\geq 0.}$

إن إيجاد معكوس الهسيان في الأبعاد العالية لحساب اتجاه نيوتن قد يكون عملية مكلفة. في مثل هذه الحالات، بدلاً من عكس الهسيان مباشرة، من الأفضل حساب المتجه كحل لنظام المعادلات الخطية${\displaystyle h=-(f''(x_{k}))^{-1}f'(x_{k})}$${\displaystyle h}$

${\displaystyle [f''(x_{k})]h=-f'(x_{k})}$

والتي يمكن حلها من خلال التحليلات المختلفة للعوامل أو تقريبًا (ولكن بدقة كبيرة) باستخدام الطرق التكرارية . العديد من هذه الطرق لا تنطبق إلا على أنواع معينة من المعادلات، على سبيل المثال، لن يعمل تحليل تشوليسكي والتدرج المترافق إلا إذا كانت مصفوفة محددة موجبة. في حين أن هذا قد يبدو وكأنه قيد، إلا أنه غالبًا ما يكون مؤشرًا مفيدًا لشيء خاطئ؛ على سبيل المثال، إذا تم التعامل مع مشكلة التقليل ولم تكن محددة موجبة، فإن التكرارات تتقارب إلى نقطة سرج وليس إلى الحد الأدنى. ${\displaystyle f''(x_{k})}$${\displaystyle f''(x_{k})}$

من ناحية أخرى، إذا تم إجراء تحسين مقيد (على سبيل المثال، باستخدام مضاعفات لاغرانج )، فقد تصبح المشكلة هي إيجاد نقطة السرج، وفي هذه الحالة سيكون هيسيان متماثلًا غير محدد وسيتعين حله باستخدام طريقة تعمل على ذلك، مثل متغير تحليل العوامل تشوليسكي أو طريقة المتبقي المترافق . ${\displaystyle x_{k+1}}$${\displaystyle LDL^{\top }}$

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

إذا كان الهسيان قريبًا من مصفوفة غير قابلة للعكس ، فقد يكون الهسيان المقلوب غير مستقر عدديًا وقد يتباعد الحل. في هذه الحالة، تم تجربة بعض الحلول البديلة في الماضي، والتي حققت نجاحًا متفاوتًا مع بعض المشكلات. يمكن للمرء، على سبيل المثال، تعديل الهسيان عن طريق إضافة مصفوفة تصحيح لجعل الموجب محددًا. أحد الأساليب هو تحويل الهسيان إلى قطري واختياره بحيث يكون له نفس المتجهات الذاتية مثل الهسيان، ولكن مع استبدال كل قيمة ذاتية سالبة بـ . ${\displaystyle B_{k}}$${\displaystyle f''(x_{k})+B_{k}}$${\displaystyle B_{k}}$${\displaystyle f''(x_{k})+B_{k}}$${\displaystyle \epsilon >0}$

إن أحد الأساليب المستخدمة في خوارزمية ليفينبيرج-ماركوارت (التي تستخدم هيسيان تقريبي) هو إضافة مصفوفة هوية مقياسية إلى هيسيان، ، مع تعديل المقياس في كل تكرار حسب الحاجة. بالنسبة إلى هيسيان الكبيرة والصغيرة، ستتصرف التكرارات مثل الانحدار التدريجي بحجم خطوة . ويؤدي هذا إلى تقارب أبطأ ولكن أكثر موثوقية حيث لا يوفر هيسيان معلومات مفيدة. ${\displaystyle \mu I}$${\displaystyle \mu }$${\displaystyle 1/\mu }$

تحتوي طريقة نيوتن، في نسختها الأصلية، على عدة تحذيرات:

1. لا ينجح هذا إذا لم يكن الهسياني قابلاً للعكس. وهذا واضح من التعريف ذاته لطريقة نيوتن، التي تتطلب أخذ معكوس الهسياني.
2. قد لا تتقارب على الإطلاق، لكن يمكن أن تدخل في دورة بها أكثر من نقطة واحدة. انظر طريقة نيوتن § تحليل الفشل .
3. يمكن أن تتقارب إلى نقطة السرج بدلاً من الحد الأدنى المحلي، راجع قسم "التفسير الهندسي" في هذه المقالة.

تتضمن التعديلات الشائعة لطريقة نيوتن، مثل طرق شبه نيوتن أو خوارزمية ليفينبيرج-ماركوارت المذكورة أعلاه، تحذيرات أيضًا:

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

• طريقة شبه نيوتن
• نزول التدرج
• خوارزمية جاوس-نيوتن
• خوارزمية ليفينبيرج-ماركوارت
• منطقة الثقة
• تحسين
• طريقة نيلدر-ميد
• دالة متطابقة ذاتيًا - دالة تتمتع طريقة نيوتن فيها بمعدل تقارب عالمي جيد جدًا. ^{[2] : القسم 6.2}

• أفريل، مردخاي (2003). البرمجة غير الخطية: التحليل والأساليب . دار دوفر للنشر. رقم ISBN 0-486-43227-0.
• Bonnans, J. Frédéric; Gilbert, J. Charles; Lemaréchal, Claude ; Sagastizábal, Claudia A. (2006). التحسين العددي: الجوانب النظرية والعملية . Universitext (الطبعة الثانية المنقحة من ترجمة الطبعة الفرنسية لعام 1997). برلين: Springer-Verlag. doi :10.1007/978-3-540-35447-5. ISBN 3-540-35445-X. السيد  2265882.
• فليتشر، روجر (1987). الطرق العملية للتحسين (الطبعة الثانية). نيويورك: جون وايلي وأولاده . رقم ISBN 978-0-471-91547-8.
• جيفنز، جوف هـ.؛ هوتينج، جينيفر أ. (2013). إحصاءات حسابية . هوبوكين، نيوجيرسي: جون وايلي وأولاده. ص 24-58. رقم ISBN 978-0-470-53331-4.
• نوسيدال، خورخي؛ رايت، ستيفن جيه. (1999). التحسين العددي . دار نشر سبرينغر. رقم ISBN 0-387-98793-2.
• كوفاليف، دميتري؛ ميشينكو، كونستانتين؛ ريتشاريك، بيتر (2019). "طرق نيوتن العشوائية ونيوتن المكعبة مع معدلات خطية تربيعية محلية بسيطة". arXiv : 1912.01597 [cs.LG].

• كورنبلوم ، دانيال (29 أغسطس 2015). “تصور نيوتن-رافسون (1D)”. Bl.ocks . ffe9653768cb80dfc0da.