نزول متدرج . التحسين غير المشروط

يمكنك أيضًا البحث ليس عن أفضل نقطة في اتجاه التدرج، بل عن نقطة أفضل من النقطة الحالية.

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

وصف [ | ]

التحسينات[ | ]

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

بالنسبة للدوال القريبة من الدرجة التربيعية، تكون طريقة التدرج المترافق فعالة.

التطبيق في الشبكات العصبية الاصطناعية[ | ]

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

روابط [ | ]

• جي ماثيوز.وحدة لطريقة الهبوط الحاد أو التدرج. (الرابط غير متوفر)

الأدب [ | ]

• أكوليتش ​​آي إل.البرمجة الرياضية في الأمثلة والمسائل. - م: الثانوية العامة 1986. - ص298-310.
• جيل إف، موراي دبليو، رايت إم.التحسين العملي = التحسين العملي. - م: مير، 1985.
• كورشونوف يو. كورشونوف يو.الأسس الرياضية لعلم التحكم الآلي. - م: الطاقة الذرية، 1972.
• ماكسيموف يو. فيليبوفسكايا إي.خوارزميات لحل مشاكل البرمجة غير الخطية. - م: ميفي، 1982.
• ماكسيموف يو.خوارزميات للبرمجة الخطية والمنفصلة. - م: ميفي، 1980.
• كورن جي، كورن تي.دليل الرياضيات للعلماء والمهندسين. - م: ناوكا، 1970. - ص 575-576.
• S. Yu. Gorodetsky، V. A. Grishagin.البرمجة غير الخطية والتحسين متعدد الأطراف. - نيجني نوفغورود: دار النشر بجامعة نيجني نوفغورود، 2007. - الصفحات من 357 إلى 363.

طريقة الهبوط الأكثر انحدارًا هي طريقة التدرج ذات الخطوة المتغيرة. في كل تكرار، يتم تحديد حجم الخطوة k من شرط الحد الأدنى للدالة f(x) في اتجاه الهبوط، أي.

تعني هذه الحالة أن الحركة على طول مضاد التدرج تحدث طالما أن قيمة الدالة f (x) تنخفض. من وجهة نظر رياضية، في كل تكرار، من الضروري حل مشكلة التقليل أحادي البعد حسب الوظيفة

()=و (س (ك) -و (س (ك)))

دعونا نستخدم طريقة النسبة الذهبية لهذا الغرض.

خوارزمية طريقة الهبوط الأكثر انحدارًا هي كما يلي.

تم تحديد إحداثيات نقطة البداية x (0).

عند النقطة x (k) , k = 0, 1, 2, ...، يتم حساب قيمة التدرج f (x (k)).

يتم تحديد حجم الخطوة k عن طريق تصغير أحادي البعد باستخدام الوظيفة

()=و (س (ك) -و (س (ك))).

يتم تحديد إحداثيات النقطة x (k):

x i (k+1) = x i (k) - k f i (x (k))), i=1, …, n.

يتم التحقق من شرط إيقاف العملية التكرارية:

||f (x (ك +1))|| .

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

أرز. 2.1. رسم تخطيطي لطريقة الهبوط الأكثر انحدارًا.

تنفيذ الطريقة في البرنامج :

طريقة النزول الحاد.

أرز. 2.2. تنفيذ طريقة النزول الحاد.

الخلاصة: في حالتنا، تقاربت الطريقة في 7 تكرارات. النقطة A7 (0.6641; -1.3313) هي نقطة متطرفة. طريقة الاتجاهات المترافقة. بالنسبة للدوال التربيعية، يمكنك إنشاء طريقة تدرج يكون فيها زمن التقارب محدودًا ويساوي عدد المتغيرات n.

دعونا نسمي اتجاهًا معينًا ونقترن فيما يتعلق ببعض مصفوفة هيس الإيجابية المحددة H إذا:

إذن، أي بالنسبة للوحدة H، فإن الاتجاه المترافق يعني عموديهما. في الحالة العامة، H غير تافهة. في حالة عامةالاقتران هو تطبيق مصفوفة هيس على المتجه - ويعني تدوير هذا المتجه بزاوية معينة أو تمديده أو ضغطه.

والآن أصبح المتجه متعامدًا، أي أن الاقتران ليس هو تعامد المتجه، بل هو تعامد المتجه الذي تم تدويره.

أرز. 2.3. رسم تخطيطي لطريقة الاتجاهات المترافقة.

تنفيذ الطريقة في البرنامج: طريقة توجيهات مترافقة.

أرز. 2.4. تنفيذ طريقة الاتجاهات المترافقة.

أرز. 2.5. رسم بياني لطريقة الاتجاهات المترافقة.

الاستنتاج: تم العثور على النقطة A3 (0.6666; -1.3333) في 3 تكرارات وهي نقطة متطرفة.

3. تحليل طرق تحديد الحد الأدنى والحد الأقصى لقيمة الوظيفة في ظل وجود قيود

دعونا نذكركم بذلك مهمة مشتركةالتحسين الشرطي يبدو مثل هذا

f(x) ® دقيقة، x О W،

حيث W هي مجموعة فرعية مناسبة من R m. تتميز فئة فرعية من المشاكل ذات قيود من نوع المساواة بحقيقة أن المجموعة  يتم تعريفها بواسطة قيود النموذج

f i (x) = 0، حيث f i: R m ®R (i = 1, …, k).

وهكذا، W = (x О R m: f i (x) = 0، i = 1، …، k).

سيكون من المناسب لنا أن نكتب الفهرس "0" للدالة f. وهكذا، تتم كتابة مشكلة التحسين مع قيود نوع المساواة كما

f 0 (x) ® دقيقة، (3.1)

و أنا (س) = 0، أنا = 1، …، ك. (3.2)

إذا قمنا الآن بالإشارة إلى دالة على R m بقيم في R k، فإن تدوين الإحداثيات لها الشكل f(x) = (f 1 (x), ..., f k (x))، ثم ( 3.1)-(3.2) يمكننا أيضًا كتابتها في النموذج

f 0 (x) ® دقيقة، f(x) = Q.

هندسيًا، مشكلة قيود نوع المساواة هي مشكلة إيجاد أدنى نقطة في الرسم البياني للدالة f 0 على المشعب  (انظر الشكل 3.1).

النقاط التي تستوفي جميع القيود (أي النقاط في المجموعة ) عادة ما تسمى مقبولة. النقطة المقبولة x* تسمى الحد الأدنى المشروط للدالة f 0 تحت القيود f i (x) = 0، i = 1، ...، k (أو حل للمشكلة (3.1)–(3.2)) ، إذا لجميع النقاط المسموح بها x f 0 (x *)  f 0 (x). (3.3)

إذا تم استيفاء (3.3) فقط لـ x المقبول في بعض الأحياء V x * للنقطة x*، فإننا نتحدث عن حد أدنى مشروط محلي. يتم تعريف مفاهيم الحدود الدنيا المحلية والعالمية الصارمة المشروطة بطريقة طبيعية.

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

دقيقة (ي ك (أ) | أ>0)، (2.27)

حيث j k (a)=f(X k - a· (X k)). وهكذا، عند كل تكرار في اتجاه التدرج العكسي يتم إجراء نزول شامل. لحل المشكلة (2.27)، يمكنك استخدام إحدى طرق البحث أحادية البعد الموضحة في القسم 1، على سبيل المثال، طريقة البحث بالبت أو طريقة القسم الذهبي.

دعونا نصف خوارزمية طريقة الهبوط الأكثر انحدارًا.

الخطوة 0.اضبط معلمة الدقة e>0، وحدد X 0 ОE n، واضبط k=0.

الخطوة 1.ابحث عن (X k) وتحقق من الشرط لتحقيق الدقة المحددة || (x ك) || £ ه. إذا كان راضيًا، فانتقل إلى الخطوة 3، وإلا - إلى الخطوة 2.

الخطوة 2.حل المشكلة (2.27) أي. العثور على ك. ابحث عن النقطة التالية، ضع k=k+1 وانتقل إلى الخطوة 1.

الخطوة 3أكمل الحسابات بوضع X * = X k، f * = f(X k).

مثال نموذجي

تصغير الوظيفة

و(س)=س 1 2 +4x 2 2 -6x 1 -8x 2 +13; (2.28)

دعونا نحل المشكلة أولا كلاسيكيطريقة. دعونا نكتب نظام المعادلات التي تمثل الشروط الضروريةأقصى غير مشروط

وبعد حلها، حصلنا على نقطة ثابتة X*=(3;1). بعد ذلك، دعونا نتحقق من التنفيذ حالة كافية، حيث نجد مصفوفة المشتقات الثانية

نظرًا لأن هذه المصفوفة، وفقًا لمعيار سيلفستر، موجبة ومحددة لـ "، فإن النقطة التي تم العثور عليها X* هي النقطة الدنيا للدالة f(X). الحد الأدنى للقيمة f *=f(X*)=0. هذا هو الحل الدقيق للمشكلة (11).

لنقم بإجراء تكرار واحد للطريقة نزول متدرجل (2.28). دعونا نختار نقطة البداية X 0 =(1;0)، ونحدد الخطوة الأولية a=1 والمعلمة l=0.5. لنحسب f(X 0)=8.

لنجد ميل الدالة f(X) عند النقطة X 0

(× 0) = = (2.29)

دعونا نحدد نقطة جديدة X=X 0 -a· (X 0) عن طريق حساب إحداثياتها

× 1 =

× 2 = (2.30)

دعونا نحسب f(X)= f(X 0 -a· (X 0))=200. بما أن f(X)>f(X 0)، قمنا بتقسيم الخطوة، على افتراض أن a=a·l=1·0.5=0.5. نحسب مرة أخرى باستخدام الصيغ (2.30) x 1 =1+4a=3؛ x 2 =8a=4 وأوجد القيمة f(X)=39. بما أن f(X)>f(X 0) مرة أخرى، فإننا نقوم بتقليل حجم الخطوة بشكل أكبر، حيث نضبط a=a·l=0.5·0.5=0.25. نحسب نقطة جديدة بإحداثيات x 1 =1+4·0.25=2؛ x 2 =8·0.25=2 وقيمة الدالة عند هذه النقطة f(X)=5. منذ شرط التناقص f(X)

لنقم بإجراء تكرار واحد باستخدام الطريقة أشد النسبلـ (2.28) بنفس النقطة الأولية X 0 =(1;0). باستخدام التدرج الموجود بالفعل (2.29)، نجد

X= X 0 -أ· (X 0)

وأنشئ الدالة j 0 (a)=f(X 0 -a· (X 0))=(4a-2) 2 +4(8a-1) 2. وذلك بتصغيره باستخدام الشرط الضروري

ي 0 ¢(أ)=8·(4أ - 2)+64·(8أ - 1)=0

نجد القيمة المثلى لحجم الخطوة 0 = 5/34.

تحديد نقطة تسلسل التصغير

× 1 = × 0 -أ 0 · (× 0) .

تدرج الدالة القابلة للتفاضل f(x) عند النقطة Xمُسَمًّى ن-ناقل الأبعاد و(س) ، والتي تكون مكوناتها مشتقات جزئية للدالة و (خ)،تحسب عند هذه النقطة X، أي.

و"(x ) = (دف(x)/د 1 ، ...، مدافع (خ)/دكس ن) ت .

هذا المتجه عمودي على المستوى من خلال هذه النقطة X، والمماس لسطح مستوى الوظيفة و (خ)،المرور عبر نقطة X.في كل نقطة من هذا السطح وظيفة و (خ)يأخذ نفس القيمة. بمساواة الدالة بقيم ثابتة مختلفة C 0 , C 1 , ...، نحصل على سلسلة من الأسطح التي تميز طوبولوجيتها (الشكل 2.8).

أرز. 2.8. التدرج

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

من الواضح أنه إذا لم تكن هناك معلومات إضافية، فمن نقطة البداية Xفمن الحكمة أن نذهب إلى هذه النقطة X، الكذب في اتجاه التدرج - أسرع انخفاض في الوظيفة. اختيار اتجاه النسب[صك ] ضد التدرج -و '(خ ) [ك] X[صعند هذه النقطة

]، نحصل على عملية تكرارية للنموذج س[ 1] = ك+[ص]-ك ف"(xو '(خ ) , و ك > 0; ص=0, 1, 2, ...

في شكل إحداثي، يتم كتابة هذه العملية على النحو التالي:

س ط [ ص+1]=× ط[ص] - كو(سو '(خ ) /x ط

ط = 1، ...، ن; ص= 0, 1, 2,...

كمعيار لإيقاف العملية التكرارية إما تحقيق شرط الزيادة البسيطة في الوسيطة || ك+[ص+ ل] - س[ص] || <= e , либо выполнение условия малости градиента

|| و '(خ[ص+ل] ) || <= g ,

هنا يتم إعطاء e و g كميات صغيرة.

من الممكن أيضًا وجود معيار مشترك يتكون من الاستيفاء المتزامن للشروط المحددة. تختلف طرق التدرج عن بعضها البعض في طريقة اختيار حجم الخطوة و ك.

في الطريقة ذات الخطوة الثابتة، يتم تحديد قيمة خطوة ثابتة معينة لجميع التكرارات. خطوة صغيرة جدًا و كسيضمن انخفاض الدالة، أي عدم المساواة

و (س [ ص+1]) = و(س[ك] – ك و '(xو '(خ )) < و(سو '(خ ) .

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

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

عند استخدام طريقة الهبوط الأكثر انحدارًا في كل تكرار، يتم تحديد حجم الخطوة و كيتم تحديده من الحد الأدنى لحالة الوظيفة و (خ)في اتجاه الهبوط، أي.
و(س[ص]-أ ك و '(x[ص])) = و(سو '(خ - بالعربية"(خ[ص])) .

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

خوارزمية طريقة الهبوط الأكثر انحدارًا هي كما يلي.

1. قم بتعيين إحداثيات نقطة البداية X.

2. عند هذه النقطة X[ص], ك = 0، 1، 2، ... يحسب قيمة التدرج و '(خ[ص]) .

3. يتم تحديد حجم الخطوة أك، عن طريق التقليل أحادي البعد أوظائف ي (أ) = و(س[ص]-أف"(خ[ص])).

4. يتم تحديد إحداثيات النقطة X[س[ 1]:

س ط [ س[ 1]= الحادي عشر[ص]- ك و 'أنا (خ[ص]) ، ط = 1،...، ص.

5. التحقق من شروط إيقاف عملية التعقيم. إذا تم الوفاء بها، فإن الحسابات تتوقف. بخلاف ذلك، انتقل إلى الخطوة 1.

في الطريقة قيد النظر، اتجاه الحركة من النقطة X[ص] يمس خط المستوى عند هذه النقطة ك+[س[ 1] (الشكل 2.9). مسار الهبوط متعرج، مع روابط متعرجة مجاورة متعامدة مع بعضها البعض. بالفعل خطوة أيتم اختيار k عن طريق التقليل بواسطة أوظائف؟ (أ) = و(سو '(خ -أف"(خ[ص])) . شرط ضروري للحد الأدنى من الوظيفةي (أ)/دا = 0.بعد حساب مشتق دالة معقدة، نحصل على شرط التعامد لمتجهات اتجاهات الهبوط عند النقاط المجاورة:

دي جي (أ)/دا = -و'(x[س[ 1]و '(خ[ص]) = 0.

أرز. 2.9.

التفسير الهندسي لطريقة الهبوط الأكثر انحدارا تتقارب طرق التدرج إلى الحد الأدنى عند السرعة العالية (سرعة التقدم الهندسي) للحصول على وظائف محدبة سلسة. هذه الوظائف لديها أعظمم وأقلهام

القيم الذاتية لمصفوفة المشتقات الثانية (مصفوفة هسه) تختلف قليلا عن بعضها البعض، أي المصفوفةن (خ) مكيفة بشكل جيد. تذكر أن القيم الذاتية l i، =1, …, نأنا

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

ينحرف اتجاه التدرج العكسي لهذه الوظائف (انظر الشكل 2.10) بشكل كبير عن الاتجاه إلى النقطة الدنيا، مما يؤدي إلى تباطؤ في سرعة التقارب.

أرز. 2.10. وظيفة اخدود Xويعتمد معدل تقارب طرق التدرج أيضًا بشكل كبير على دقة حسابات التدرج. يمكن أن يؤدي فقدان الدقة، والذي يحدث عادةً بالقرب من النقاط الدنيا أو في حالة الأخدود، إلى تعطيل تقارب عملية نزول التدرج.

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

بعيدًا عن النقطة الدنيا، والخطوات في اتجاه التدرج العكسي تجعل من الممكن تحقيق انخفاض كبير في الوظيفة.

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

يمكن تقريب أي دالة سلسة بالقرب من النقطة الدنيا بشكل جيد بواسطة دالة تربيعية، لذلك يتم استخدام طرق التدرج المترافق بنجاح لتقليل الدوال غير التربيعية. في هذه الحالة، فإنها تتوقف عن أن تكون محدودة وتصبح متكررة. نبحكم التعريف، اثنان X-ناقل الأبعاد وفي مُسَمًّىمترافق نسبة إلى المصفوفةح نسبة إلى المصفوفة(أو -مترافق)، إذا كان المنتج العددي, (xحسنا) = 0. هنان - مصفوفة إيجابية متماثلة محددة الحجمن X

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

دعونا نفكر أولاً في هذه الطريقة فيما يتعلق بمشكلة التقليل اختيار اتجاه النسب[صدالة تربيعية

الاتجاهات ص] = -و '(خ[ص]) ] يتم حسابه باستخدام الصيغ: في الاتجاه[صص[ ص>= 1;

+ب ك-1 -ل]،’-مترافق)، إذا كان المنتج العددي) .

ع = - صو في الاتجاه[ص], اختيار اتجاه النسب[صب القيم نسبة إلى المصفوفة-1 يتم اختيارها بحيث تكون الاتجاهات :

(في الاتجاه[ص], -1] كانوا[-مترافق 1])= 0.

HP

,

ك-

ونتيجة لذلك، للدالة التربيعية ص+ل] عملية التقليل التكرارية لها الشكل[ص]س[[ص],

=س اختيار اتجاه النسب[ص] - +أ ك ص -مترافقأين اتجاه النزول الىخطوة م؛ و ك -حجم الخطوة. أويتم اختيار الأخير من الحد الأدنى لحالة الوظيفة

و (س [ ص] + و (خ)[ص]) = و(س[ص] + بواسطة [ص]) .

في اتجاه الحركة أي نتيجة لحل مشكلة التصغير أحادية البعد:

ك ر

ع Xلدالة تربيعية في الاتجاه = -و '(خ) .

خوارزمية طريقة التدرج المترافق فليتشر-ريفز هي كما يلي. -مترافق 1. عند هذه النقطة أمحسوب . 2. تشغيل X[س[ 1].

خطوة م، باستخدام الصيغ المذكورة أعلاه، يتم تحديد الخطوة و(س[ص+1]) ك و '(خ[ص+1]) .

والفترة و '(خ) 3. يتم حساب القيم X[صو 4. إذا= 0 ثم أشر في الاتجاه[ص+1] هي النقطة الدنيا للوظيفة

و (خ). مصفوفة إيجابية متماثلة محددة الحجموإلا سيتم تحديد اتجاه جديد +l] من العلاقةويتم الانتقال إلى التكرار التالي. سيجد هذا الإجراء الحد الأدنى للدالة التربيعية في ما لا يزيد عن Xخطوات. عند تقليل الدوال غير التربيعية، تصبح طريقة فليتشر-ريفز تكرارية من النهاية. في هذه الحالة بعد X[مصفوفة إيجابية متماثلة محددة الحجم(ع+

ونتيجة لذلك، للدالة التربيعية ص+ل] 1) يتم تكرار الإجراء 1-4 بشكل دوري مع الاستبدال[ص]س[[ص],

الاتجاهات ص] على[ص])+ +1]، وتنتهي الحسابات عند، حيث يوجد رقم معين. في هذه الحالة، يتم استخدام التعديل التالي للطريقة: -مترافق 1 في الاتجاه[صص[ ص>= 1;

= س ك+);

و (س [ ص] + = -و'(س[ص]) = و(س[ص] ب[ص];

.

ص = -و'( ك ص+ ا ف ب ك صهنا أنا- العديد من الفهارس: مصفوفة إيجابية متماثلة محددة الحجم= (0، ن، 2

ع ، الراتب ، ...)، أي يتم تحديث الطريقة كل Xخطوات. اختيار اتجاه النسب = معنى هندسيطريقة التدرج المترافق هي كما يلي (الشكل 2.11). من نقطة انطلاق معينة Xيتم الهبوط في الاتجاه -ف"(x). Xهي النقطة الدنيا للدالة في الاتجاه اختيار اتجاه النسب, الذي - التي ] ضد التدرج -) متعامد مع ناقلات اختيار اتجاه النسب. ثم تم العثور على المتجه اختيار اتجاه النسب , نسبة إلى المصفوفة-مقترن ب اختيار اتجاه النسب. بعد ذلك، نجد الحد الأدنى للدالة على طول الاتجاه اختيار اتجاه النسبإلخ.

أرز. 2.11 . مسار النسب في طريقة التدرج المترافق

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

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

هي قيم وسيطة الوظيفة (المعلمات الخاضعة للتحكم) في المجال الحقيقي.

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

حيث i، j،…، n هي متجهات وحدة موازية لمحاور الإحداثيات.

التدرج عند نقطة الأساس متعامد تمامًا مع السطح، ويوضح اتجاهه اتجاه أسرع زيادة في الوظيفة، والاتجاه المعاكس (مضاد التدرج)، على التوالي، يوضح اتجاه أسرع انخفاض في الوظيفة.

الطريقة الأكثر انحدارًا هي مزيد من التطويرطريقة النزول المتدرج. بشكل عام، عملية إيجاد الحد الأقصى للدالة هي إجراء تكراري، وهو مكتوب على النحو التالي:

حيث يتم استخدام علامة "+" للعثور على الحد الأقصى للدالة، ويتم استخدام علامة "-" للعثور على الحد الأدنى من الوظيفة؛

متجه اتجاه الوحدة، والذي يتم تحديده بواسطة الصيغة:

- وحدة التدرج تحدد معدل زيادة أو نقصان الدالة في اتجاه التدرج أو عكس التدرج:

ثابت يحدد حجم الخطوة وهو نفسه بالنسبة لجميع الاتجاهات i.

يتم اختيار حجم الخطوة من شرط الحد الأدنى للدالة الموضوعية f(x) في اتجاه الحركة، أي نتيجة لحل مشكلة التحسين أحادية البعد في اتجاه التدرج أو مضاد التدرج:

بمعنى آخر يتم تحديد حجم الخطوة من خلال حل هذه المعادلة:

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

في حالة وجود دالة بمتغيرين هذه الطريقةله التفسير الهندسي التالي: اتجاه الحركة من نقطة يمس خط المستوى عند النقطة . مسار الهبوط متعرج، مع روابط متعرجة مجاورة متعامدة مع بعضها البعض. تتم كتابة شرط تعامد متجهات اتجاهات النسب عند النقاط المجاورة بالتعبير التالي:

مسار الحركة إلى النقطة القصوى باستخدام طريقة الهبوط الأكثر انحدارًا، كما هو موضح في الرسم البياني لخط المستوى المتساوي للدالة f(x)

ينتهي البحث عن الحل الأمثل عند الوصول إلى خطوة الحساب التكرارية (عدة معايير):

يبقى مسار البحث في حي صغير من نقطة البحث الحالية:

لا تتغير زيادة الوظيفة الهدف:

يصبح تدرج الدالة الهدف عند النقطة الدنيا المحلية صفرًا:

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

وظيفة اخدود

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

طريقة الحساب

الخطوة 1:تعريف التعبيرات التحليلية (في شكل رمزي) لحساب تدرج الوظيفة

الخطوة 2: اضبط التقريب الأولي

الخطوة 3:يتم تحديد الحاجة إلى إعادة تشغيل الإجراء الخوارزمي لإعادة تعيين اتجاه البحث الأخير. نتيجة لإعادة التشغيل، يتم إجراء البحث مرة أخرى في اتجاه النزول الأسرع.