قواعد لإدخال وظيفة
في طريقة الهبوط الأكثر حدةيتم تحديد المتجه الذي يكون اتجاهه معاكسًا لاتجاه متجه التدرج للدالة ▽f(x) باعتباره اتجاه البحث. من التحليل الرياضيمن المعروف أن المتجه grad f(x)=▽f(x) يميز اتجاه أسرع زيادة في الوظيفة (انظر تدرج الوظيفة). لذلك، يتم استدعاء المتجه - grad f (X) = -▽f(X). مكافحة التدرجوهو اتجاه أسرع انخفاض له. علاقة التكرار التي يتم من خلالها تنفيذ طريقة الهبوط الأكثر انحدارًا لها الشكل X k +1 =X k - lect k ▽f(x k), k = 0,1,...,
حيث k >0 هو حجم الخطوة. اعتمادا على اختيار حجم الخطوة، يمكنك الحصول عليها خيارات مختلفةطريقة التدرج. إذا كان حجم الخطوة ثابتًا أثناء عملية التحسين، فإن الطريقة تسمى طريقة التدرج بخطوة منفصلة. يمكن تسريع عملية التحسين في التكرارات الأولى بشكل كبير إذا تم تحديد lect k من الشرط lect k =min f(X k + lectS k) .
لتحديد k، يتم استخدام أي طريقة تحسين أحادية البعد. في هذه الحالة، تسمى الطريقة طريقة الهبوط الأكثر انحدارًا. كقاعدة عامة، في حالة عامةخطوة واحدة لا تكفي لتحقيق الحد الأدنى من الوظيفة؛ يتم تكرار العملية حتى تسمح الحسابات اللاحقة بتحسين النتيجة.
إذا كانت المساحة ممدودة للغاية في بعض المتغيرات، فسيتم تشكيل "الوادي". قد يتباطأ البحث ويتعرج عبر قاع "الوادي". في بعض الأحيان لا يمكن التوصل إلى حل خلال فترة زمنية مقبولة.
قد يكون عيب آخر لهذه الطريقة هو معيار التوقف ||▽f(X k)||<ε k , так как этому условию удовлетворяет и седловая точка, а не только оптимум.
مثال. بدءًا من النقطة x k =(-2, 3)، حدد النقطة x k +1 باستخدام طريقة الهبوط الأكثر انحدارًا لتقليل الوظيفة.
كاتجاه البحث، حدد متجه التدرج عند النقطة الحالية 
دعونا نتحقق من معيار التوقف. لدينا 
لنحسب قيمة الدالة عند نقطة البداية f(X 1) = 35. لنفعل ذلك
خطوة على طول الاتجاه المضاد للتدرج
لنحسب قيمة الدالة عند نقطة جديدة
و(X 2) = 3(-2 + 19 1) 2 + (3-8 1) 2 - (-2 + 19 1)(3-8 1) - 4(-2 + 19 1)
دعونا نجد خطوة بحيث تصل الدالة الهدف إلى الحد الأدنى على طول هذا الاتجاه. من الشرط الضروري لوجود أقصى للدالة
و'(X 2) = 6(-2 + 19lect 1) 19 + 2(3-8lect 1)(-8) – (73 - 304 lect 1) – 4*19
أو f’(X 2) = 2598 1 – 425 = 0.
نحصل على الخطوة 1 = 0.164
إكمال هذه الخطوة سيؤدي إلى هذه النقطة 
حيث قيمة التدرج 
، قيمة الدالة f(X 2) = 0.23. لم يتم تحقيق الدقة، من النقطة التي نخطو فيها خطوة على طول اتجاه التدرج المضاد.
f(X 2) = 3(1.116 – 1.008lect 1) 2 + (1.688-2.26lect 1) 2 - (1.116 – 1.008lect 1)(1.688-2.26lect 1) - 4(1.116 – 1.008lect 1)
و'(X 2) = 11.76 – 6.12 1 = 0
نحصل على 1 = 0.52 
بيان المشكلة
دع الوظيفة تعطى و (خ) آر إن
مطلوب و (خ) X = رن
استراتيجية البحث
س ك
} , ك = 0.1،...،
مثل هذا 
, ك = 0.1،...
. نقاط التسلسل ( س ك
) يتم حسابها وفقا للقاعدة
أين هي النقطة × 0 تعريف المستخدم؛ حجم الخطوة تك المحددة لكل قيمة ك من الشرط
يمكن حل المشكلة (3) باستخدام الحد الأدنى الضروري من الشرط متبوعًا بالتحقق من الحد الأدنى الكافي من الشرط. يمكن استخدام هذا المسار إما بوظيفة بسيطة بدرجة كافية لتقليلها، أو بتقريب أولي بدرجة كافية وظيفة معقدة 
متعدد الحدود ف(ر ك)
(عادة من الدرجة الثانية أو الثالثة)، ومن ثم يتم استبدال الشرط بشرط، والشرط بشرط 
التسلسل (xk)
ينتهي عند نقطة س ك
، من أجل أين ε
- رقم موجب صغير معين، أو ك ≥ م
، أين م
- عدد محدود من التكرارات، أو مع تنفيذ متباينتين في وقت واحد 
, 
أين ε 2
- رقم موجب صغير. والسؤال هو ما إذا كانت نقطة يمكن س ك
يمكن اعتباره التقريب الموجود لنقطة الحد الأدنى المحلية المطلوبة س*
، يتم حلها من خلال بحث إضافي.
التفسير الهندسي لطريقة ن = 2 في الشكل. 4.
طريقة الهبوط الإحداثي
بيان المشكلة
دع الوظيفة تعطى و (خ) ، يحدها أدناه على المجموعة آر إن ولها مشتقات جزئية متصلة في جميع نقاطها.
و (خ) على مجموعة الحلول الممكنة X = رن ، أي. العثور على نقطة من هذا القبيل
استراتيجية البحث
استراتيجية حل المشكلة هي بناء سلسلة من النقاط ( س ك
} , ك = 0.1،...،
مثل هذا , ك = 0.1،...
. نقاط التسلسل ( س ك
) يتم حسابها على دورات وفقا للقاعدة
(4)
أين ي - رقم دورة الحساب؛ ي = 0,1,2,...; ك - رقم التكرار داخل الحلقة، ك = 0,1,... ,ن - 1; ه ك +1، ك = 0،ل،...،ن - 1 - ناقل الوحدة، (ك+1) - الإسقاط الذي يساوي 1؛ نقطة × 00 تعريف المستخدم، حجم الخطوة تك يتم اختياره من الشرط
أو 
.
إذا كانت الحالة المحددة في التيار تك
لم يتم الوفاء، يتم خفض الخطوة إلى النصف والفترة 
يتم حسابها مرة أخرى. من السهل أن نرى أنه بالنسبة لـ j ثابت، في تكرار واحد مع الرقم ك
يتغير إسقاط واحد فقط للنقطة س جك
، وجود رقم ك+1
، وخلال الدورة بأكملها مع الرقم ي
، أي. ابتداء من ك = 0
والنهاية ك = ن -1
، كل إسقاطات n للنقطة تتغير س ي0
. بعد هذه النقطة س ي ن
تم تعيين الرقم س ي + 1.0
، ويتم أخذها كنقطة انطلاق لإجراء العمليات الحسابية فيها ي+1
دورة. وينتهي الحساب عند هذه النقطة س جك
عند استيفاء واحد على الأقل من معايير نهاية العد الثلاثة: 
أو أو التنفيذ المزدوج لعدم المساواة.
يمكن كتابة النقاط التي تم الحصول عليها نتيجة للحسابات كعناصر تسلسل (xl)، أين ل=ن*ي+ك - الرقم التسلسلي للنقطة،
يظهر الشكل 1 التفسير الهندسي لطريقة n = 2. 5.
4. طريقة فرانك وولف .
لنفترض أننا بحاجة إلى إيجاد القيمة القصوى للدالة المقعرة
تحت الظروف
السمة المميزة لهذه المشكلة هي أن نظام القيود الخاص بها يحتوي فقط على متباينات خطية. وتعتبر هذه الميزة هي الأساس لاستبدال الميزة غير الخطية في محيط النقطة قيد الدراسة وظيفة موضوعيةخطي، حيث يتم تقليل حل المشكلة الأصلية إلى الحل المتسلسل لمشاكل البرمجة الخطية.
تبدأ عملية إيجاد حل للمشكلة بتحديد نقطة تابعة لمنطقة الحلول الممكنة للمشكلة.
270
منازل ريفية دع هذه تكون النقطة X(ك)
ثم عند هذه النقطة يتم حساب تدرج الوظيفة (57).
وبناء دالة خطية
ثم ابحث عن القيمة القصوى لهذه الوظيفة ضمن القيود (58) و (59). دع حل هذه المشكلة يتحدد بالنقطة ض (ك)
. ثم يتم أخذ إحداثيات النقطة كحل جديد ممكن للمشكلة الأصلية X(ك+1)
:
أين κk - رقم معين يسمى خطوة الحساب ويقع بين الصفر والواحد (0<lect ك < 1). Это число κk اتخذت تعسفا أو تحديدا
بحيث تكون قيمة الدالة عند النقطة X (ك +1) و(X (ك +1)) ، اعتمادا علي κk ، كان الحد الأقصى. للقيام بذلك، عليك إيجاد حل للمعادلة واختيار الجذر الأصغر لها. وإذا كانت قيمتها أكبر من واحد، فيجب أن نضعها κk=1 . بعد تحديد العدد κk العثور على إحداثيات نقطة X(ك+1) احسب قيمة الدالة الموضوعية فيه وحدد الحاجة إلى الانتقال إلى نقطة جديدة X(ك+2) . إذا كانت هناك حاجة، فاحسب عند هذه النقطة X(ك+1) التدرج اللوني للدالة الهدف، انتقل إلى مشكلة البرمجة الخطية المقابلة وابحث عن حل لها. تحديد إحداثيات النقطة و X(ك+2) والتحقيق في الحاجة إلى مزيد من الحسابات. وبعد عدد محدود من الخطوات، يتم الحصول على حل للمشكلة الأصلية بالدقة المطلوبة.
لذا فإن عملية إيجاد حل المشكلة (57) - (59) باستخدام طريقة فرانك وولف تتضمن المراحل التالية:
1. تحديد الحل الأولي الممكن للمشكلة.
2. أوجد تدرج الدالة (57) عند نقطة الحل المقبول.
3. أنشئ الدالة (60) وأوجد قيمتها القصوى تحت الشرطين (58) و(59).
4. تحديد خطوة الحساب.
5. باستخدام الصيغ (61)، تم العثور على مكونات الحل الجديد الممكن.
6. تحقق من ضرورة الانتقال إلى الحل الممكن التالي. إذا لزم الأمر، انتقل إلى المرحلة 2، وإلا تم العثور على حل مقبول للمشكلة الأصلية.
طريقة وظائف العقوبة.
النظر في مشكلة تحديد القيمة القصوى للدالة المقعرة
و (× 1، × 2، .... × ن)تحت الظروف ز ط (س 1، س 2، .... س ن) ≤ ب ط (ط=ل، م) , س ي ≥ 0 (ي=1، ن) ، أين ز ط (س 1، س 2، .... س ن) - وظائف محدبة.
بدلًا من حل هذه المشكلة مباشرةً، أوجد القيمة القصوى للدالة F(x 1, x 2, ...., x n)= f(x 1, x 2, ...., x n) +ح(× 1، × 2، ....، × ن) وهو مجموع الوظيفة الموضوعية للمشكلة، وبعض الوظائف
ح(× 1، × 2، ....، × ن)، يحددها نظام القيود ويسمى وظيفة العقوبة. يمكن بناء وظيفة العقوبة بطرق مختلفة. ومع ذلك، في أغلب الأحيان يبدو الأمر كذلك
أ أنا> 0
- بعض الأرقام الثابتة التي تمثل معاملات الترجيح.
وباستخدام دالة الجزاء، ينتقلون بالتتابع من نقطة إلى أخرى حتى يحصلوا على حل مقبول. في هذه الحالة، يتم العثور على إحداثيات النقطة التالية باستخدام الصيغة
ويترتب على العلاقة الأخيرة أنه إذا كانت النقطة السابقة في منطقة الحلول الممكنة للمشكلة الأصلية، فإن الحد الثاني بين قوسين مربعين يساوي الصفر ويتم تحديد الانتقال إلى النقطة التالية فقط من خلال تدرج الهدف وظيفة. إذا كانت النقطة المحددة لا تنتمي إلى منطقة الحلول المقبولة، فبفضل هذا المصطلح في التكرارات اللاحقة يتم تحقيق العودة إلى منطقة الحلول المقبولة
القرارات. وفي نفس الوقت أقل أ
كلما تم العثور على حل مقبول بشكل أسرع، لكن دقة تحديده تقل. ولذلك، تبدأ العملية التكرارية عادةً بقيم صغيرة نسبيًا أ
ومواصلة ذلك تزداد هذه القيم تدريجياً.
لذا فإن عملية إيجاد حل لمشكلة البرمجة المحدبة باستخدام طريقة دالة الجزاء تتضمن الخطوات التالية:
1. تحديد الحل الأولي الممكن.
2. حدد خطوة الحساب.
3. أوجد، لجميع المتغيرات، المشتقات الجزئية للدالة الموضوعية والدوال التي تحدد نطاق الحلول الممكنة للمشكلة.
4. باستخدام الصيغة (72) يتم إيجاد إحداثيات النقطة التي تحدد الحل الجديد المحتمل للمشكلة.
5. التحقق مما إذا كانت إحداثيات النقطة التي تم العثور عليها تلبي نظام قيود المشكلة. إذا لم يكن الأمر كذلك، انتقل إلى المرحلة التالية. إذا حددت إحداثيات النقطة التي تم العثور عليها حلاً مقبولاً للمشكلة، فسيتم التحقيق في الحاجة إلى الانتقال إلى الحل المقبول التالي. إذا لزم الأمر، انتقل إلى المرحلة 2، وإلا فقد تم العثور على حل مقبول للمشكلة الأصلية.
6. اضبط قيم معاملات الترجيح وانتقل إلى الخطوة 4.
طريقة السهم هورويتز.
عند إيجاد حلول لمشاكل البرمجة غير الخطية باستخدام طريقة دالة الجزاء، قمنا باختيار القيم أ بشكل تعسفي مما أدى إلى تقلبات كبيرة في مسافة النقاط المحددة من منطقة الحلول الممكنة. يتم التخلص من هذا العيب عند حل المشكلة بطريقة Arrow-Hurwitz، والتي بموجبها يتم في الخطوة التالية الأرقام أ ط (ك) تحسب بواسطة الصيغة
كقيم أولية أنا (0) خذ أرقامًا تعسفية غير سالبة.
مثال على الحل
مثال 1.
أوجد الحد الأدنى المحلي للدالة
تحديد نقطة س ك
1. دعونا نستعد.
2. دعونا نضع ك = 0 .
3 0 . دعونا نحسب
4 0 . دعونا نحسب 
. دعنا ننتقل إلى الخطوة 5.
5 0 . دعونا نتحقق من الحالة 
. دعنا ننتقل إلى الخطوة 6.
6 0 . دعونا نضع ر0 = 0.5 .
7 0 . دعونا نحسب
8 0 . دعونا نقارن 
. لدينا 
. الخلاصة: شرط ل ك = 0
لم يتم تنفيذه. دعونا نضع ر0 = 0.25
، انتقل إلى تكرار الخطوات 7، 8.
7 01. دعونا نحسب.
8 01. دعونا نقارن و (× 1) و (× 0) . خاتمة: و (× 1)< f (x 0) . دعنا ننتقل إلى الخطوة 9.
9 0 . دعونا نحسب
الخلاصة: نحن نؤمن ك =1 وانتقل إلى الخطوة 3.
3 1. دعونا نحسب
4 1. دعونا نحسب 
. دعنا ننتقل إلى الخطوة 5.
5 1. دعونا نتحقق من الحالة ك ≥ م: ك = 1< 10 = M . دعنا ننتقل إلى الخطوة 6.
6 1. دعونا نضع ر 1 = 0.25.
7 1. دعونا نحسب
8 1. دعونا نقارن و (× 2) مع و (× 1) . خاتمة: و (× 2)< f (х 1). دعنا ننتقل إلى الخطوة 9.
9 1. دعونا نحسب
الخلاصة: نحن نؤمن ك = 2 وانتقل إلى الخطوة 3.
3 2. دعونا نحسب
4 2 . دعونا نحسب. دعنا ننتقل إلى الخطوة 5.
5 2. دعونا نتحقق من الحالة ك ≥ م : ك = 2< 10 = М ، انتقل إلى الخطوة 6.
6 2. دعونا نضع ر 2 =0,25 .
7 2. دعونا نحسب
8 2. دعونا نقارن و (× 3) و و (× 2) . خاتمة: و (× 3)< f (х 2) انتقل إلى الخطوة 9.
9 2. دعونا نحسب 
الخلاصة: نحن نؤمن ك = 3 وانتقل إلى الخطوة 3.
3 3 . دعونا نحسب
4 3 . دعونا نحسب. دعنا ننتقل إلى الخطوة 5.
5 3. دعونا نتحقق من الحالة ك ≥ م : ك = 3<10 = М ، انتقل إلى الخطوة 6.
6 3. دعونا نضع ر 3 = 0.25.
7 3. دعونا نحسب
8 3. دعونا نقارن و (× 4) و و (× 3) : و (× 4)< f (х 3) .
9 3. دعونا نحسب 
يتم استيفاء الشروط عندما ك = 2.3 . حساب
انتهى. تم العثور على نقطة
في الشكل. ترتبط النقاط الثلاث الناتجة بخط منقط.
ثانيا. تحليل النقطة × 4 .
وظيفة 
قابلة للاشتقاق مرتين، لذا سنتحقق من الشروط الكافية للحد الأدنى عند هذه النقطة × 4
. للقيام بذلك، دعونا نحلل مصفوفة هسه.
المصفوفة ثابتة وموجبة محددة (أي . ح > 0
) لأن كلا من القاصرين الزاويين موجبان. ولذلك النقطة 
هو التقريب الموجود لنقطة الحد الأدنى المحلية، والقيمة 
هو التقريب الموجود للقيمة و (س *) =0
. لاحظ أن الشرط ح > 0
، هناك في نفس الوقت شرط للتحدب الصارم للوظيفة 
. ونتيجة لذلك، تم العثور على تقديرات تقريبية لنقطة الحد الأدنى العالمية و (خ)
والحد الأدنى لقيمته عند ص 2
. ■
مثال 2
أوجد الحد الأدنى المحلي للدالة
I. تعريف النقطة س ك، حيث يتم استيفاء واحد على الأقل من معايير إكمال العمليات الحسابية.
1. دعونا نستعد.
دعونا نجد تدرج الوظيفة عند نقطة تعسفية
2. دعونا نضع ك = 0 .
3 0 . دعونا نحسب
4 0 . دعونا نحسب . دعنا ننتقل إلى الخطوة 5.
5 0 . دعونا نتحقق من الحالة 
. دعنا ننتقل إلى الخطوة 6.
6° تم العثور على النقطة التالية من خلال الصيغة
دعونا نستبدل التعبيرات التي تم الحصول عليها للإحداثيات بها
دعونا نجد الحد الأدنى من الوظيفة و (ر 0) بواسطة ر 0 باستخدام الشروط اللازمة للحد غير المشروط:
من هنا ر 0 =0.24
. لأن 
، توفر قيمة الخطوة التي تم العثور عليها الحد الأدنى من الوظيفة و (ر 0)
بواسطة ر 0
.
دعونا نحدد 
7 0 . سوف نجد
8°. دعونا نحسب
الخلاصة: نحن نؤمن ك = 1 وانتقل إلى الخطوة 3.
3 1. دعونا نحسب
4 1. دعونا نحسب 
5 1. دعونا نتحقق من الحالة ك ≥ 1: ك = 1< 10 = М.
6 1. دعونا نحدد
7 1. سوف نجد 
:
8 1. دعونا نحسب
نعتقد ك = 2 وانتقل إلى الخطوة 3.
3 2. دعونا نحسب
4 2 . دعونا نحسب
5 2. دعونا نتحقق من الحالة ك ≥ م: ك = 2< 10 = M .
6 2. دعونا نحدد
7 2. سوف نجد 
8 2. دعونا نحسب
نعتقد ك =3 وانتقل إلى الخطوة 3.
3 3 . دعونا نحسب
4 3 . دعونا نحسب.
اكتمل الحساب. تم العثور على نقطة
ثانيا. تحليل النقطة × 3 .
في المثال 1.1 (الفصل 2 §1) تبين أن الوظيفة و (خ) محدب تمامًا، وبالتالي، عند النقاط 3 هو التقريب الموجود لنقطة الحد الأدنى العالمية ×* .
مثال 3.
أوجد الحد الأدنى المحلي للدالة
I. تعريف النقطة xjk ، حيث يتم استيفاء واحد على الأقل من معايير إكمال العمليات الحسابية.
1. دعونا نستعد
دعونا نجد تدرج الوظيفة عند نقطة تعسفية 
2. دعونا نستعد ي = 0.
3 0 . دعونا نتحقق من استيفاء الشرط
4 0 . دعونا نضع ك = 0.
5 0 . دعونا نتحقق من استيفاء الشرط
6 0 . دعونا نحسب
7 0 . دعونا التحقق من الحالة 
8 0 . دعونا نضع
9 0 . دعونا نحسب 
، أين
10 0 . دعونا التحقق من الحالة
الخلاصة: نفترض وننتقل إلى الخطوة 9.
9 01. دعونا نحسب × 01 في خطوات
10 01. دعونا التحقق من الحالة 
11 0 . دعونا نتحقق من الشروط
نعتقد ك =1 وانتقل إلى الخطوة 5.
5 1. دعونا نتحقق من الحالة
6 1. دعونا نحسب
7 1. دعونا التحقق من الحالة
8 1. دعونا نضع
9 1. دعونا نحسب
10 1. دعونا التحقق من الحالة 
:
11 1. دعونا نتحقق من الشروط
نعتقد ك = 2 ، انتقل إلى الخطوة 5.
5 2. دعونا التحقق من الحالة. لنقم بالإعداد، انتقل إلى الخطوة 3.
3 1. دعونا التحقق من الحالة
4 1. دعونا نضع ك = 0.
5 2. دعونا نتحقق من الحالة
6 2. دعونا نحسب
7 2. دعونا التحقق من الحالة
8 2. دعونا نضع
9 2. دعونا نحسب
10 2. دعونا التحقق من الحالة 
11 2. دعونا نتحقق من الشروط
نعتقد ك =1 وانتقل إلى الخطوة 5.
5 3. دعونا نتحقق من الحالة
6 3. دعونا نحسب
7 3. دعونا نتحقق من الشروط
8 3. دعونا نضع
9 3. دعونا نحسب
10 3. دعونا التحقق من الحالة 
11 3. دعونا نتحقق من الشروط
دعونا نضع ك = 2 وانتقل إلى الخطوة 5.
5 4 . دعونا التحقق من الحالة 
نعتقد ي = 2، × 20 = × 12 وانتقل إلى الخطوة 3.
3 2. دعونا نتحقق من الحالة
4 2 . دعونا نضع ك =0 .
5 4 . دعونا التحقق من الحالة
6 4. دعونا نحسب
7 4. دعونا نتحقق من الحالة
8 4. دعونا نضع
9 4. دعونا نحسب
10 4. دعنا نتحقق من الحالة وننتقل إلى الخطوة 11.
11 4. دعونا نتحقق من الشروط
استيفاء الشروط في دورتين متتاليتين بالارقام ي = 2 و ي -1= 1 . اكتمل الحساب وتم العثور على النقطة
في الشكل. ترتبط النقاط الست الناتجة بخط منقط.
في طريقة الهبوط الإحداثي، ننزل على طول خط متقطع يتكون من قطع مستقيمة موازية لمحاور الإحداثيات.
ثانيا. تحليل النقطة x21.
في المثال 1.1 تبين أن الدالة و (خ)
محدب تمامًا، وله حد أدنى فريد، وبالتالي نقطة 
هو التقريب الموجود لنقطة الحد الأدنى العالمية.
في جميع طرق التدرج التي تمت مناقشتها أعلاه، يتم تحديد تسلسل النقاط (xk) يتقارب مع النقطة الثابتة للدالة و (خ) مع مقترحات عامة إلى حد ما فيما يتعلق بخصائص هذه الوظيفة. على وجه الخصوص، النظرية صحيحة:
نظرية. إذا كانت الدالة f(x) محصورة بالأسفل، فإن تدرجها يفي بشرط Lipschitz () واختيار القيمة تينيسي يتم إنتاجها بإحدى الطرق الموضحة أعلاه، ثم مهما كانت نقطة البداية × 0 :
في .
في التنفيذ العملي للمخطط
ك =1، 2، … ن.
التكرارات تتوقف إذا للجميع أنا، أنا = 1، 2، ...، ن ، مثل الظروف
,
حيث يوجد رقم معين يميز دقة العثور على الحد الأدنى.
في ظل ظروف النظرية، تضمن طريقة التدرج التقارب في الدالة أو إلى الحد الأدنى الدقيق (إذا كانت الدالة و (خ) ليس له حد أدنى؛ أرز. 7)، أو إلى قيمة الدالة عند نقطة ثابتة ما، وهي نهاية التسلسل (س ك). ليس من الصعب التوصل إلى أمثلة عندما يتحقق السرج في هذه المرحلة، وليس الحد الأدنى. من الناحية العملية، تتجاوز طرق النزول المتدرج بثقة نقاط السرج وتجد الحد الأدنى من الوظيفة الموضوعية (في الحالة العامة، تلك المحلية).
خاتمة
تمت مناقشة أمثلة على أساليب التحسين التدرج غير المقيدة أعلاه. ونتيجة للعمل المنجز، يمكن استخلاص الاستنتاجات التالية:
1. تتطلب المشكلات الأكثر أو الأقل تعقيدًا المتعلقة بإيجاد الحد الأقصى في ظل وجود قيود أساليب وأساليب خاصة.
2. تتضمن العديد من الخوارزميات لحل المشكلات المقيدة التقليل غير المقيد كخطوة ما.
3. طرق مختلفةتختلف السلالات عن بعضها البعض في طريقة اختيار اتجاه الهبوط وطول الخطوة على طول هذا الاتجاه.
4. لا توجد نظرية حتى الآن تأخذ في الاعتبار أي سمات للوظائف التي تصف صياغة المشكلة. يجب إعطاء الأفضلية للطرق التي يسهل إدارتها في عملية حل المشكلة.
مشاكل التحسين التطبيقية الحقيقية معقدة للغاية. الأساليب الحديثةلا تتعامل التحسينات دائمًا مع حل المشكلات الحقيقية دون مساعدة الإنسان.
مراجع
1. كوسوروكوف أ.أ. بحوث العمليات: كتاب مدرسي. 2003
2. بانتليف أ.ف. طرق التحسين في الأمثلة والمشكلات: كتاب مدرسي. فائدة. 2005
3. شيشكين إي.في. بحوث العمليات: كتاب مدرسي. 2006
4. أكوليتش آي.إل. البرمجة الرياضية في الأمثلة والمسائل. 1986
5. فنتزل إي.إس. بحوث العمليات. 1980
6. فينتزل إي.إس.، أوفتشاروف إل.إيه. نظرية الاحتمالية وتطبيقاتها الهندسية. 1988
©2015-2019 الموقع
جميع الحقوق تنتمي إلى مؤلفيها. هذا الموقع لا يدعي التأليف، ولكنه يوفر الاستخدام المجاني.
تاريخ إنشاء الصفحة: 2017-07-02
تعليق توضيحي: تغطي هذه المحاضرة على نطاق واسع طرق التحسين متعددة المعلمات مثل طريقة الهبوط الأكثر انحدارًا وطريقة دافيدون-فليتشر-باول. بالإضافة إلى ذلك، يتم إجراء تحليل مقارن للطرق المذكورة أعلاه من أجل تحديد الأكثر فعالية، وتحديد مزاياها وعيوبها؛ ويأخذ في الاعتبار أيضًا مشاكل التحسين متعددة الأبعاد، مثل طريقة الوادي وطريقة متعددة الأطراف.
1. طريقة النزول الحاد
الجوهر هذه الطريقةهو أن استخدام ما سبق ذكره طريقة الهبوط المنسقيتم البحث من نقطة معينةفي اتجاه موازٍ لأحد المحاور إلى أدنى نقطة في هذا الاتجاه. ثم يتم إجراء البحث في اتجاه موازي للمحور الآخر، وهكذا. الاتجاهات ثابتة بالطبع. يبدو من المعقول محاولة تعديل هذه الطريقة بحيث يتم في كل مرحلة البحث عن النقطة الدنيا على طول الاتجاه "الأفضل". ليس من الواضح أي اتجاه هو "الأفضل"، لكن من المعروف ذلك اتجاه التدرجهو اتجاه أسرع زيادة في الدالة. وبالتالي فإن الاتجاه المعاكس هو اتجاه أسرع تناقص للدالة. يمكن تبرير هذه الخاصية على النحو التالي.
لنفترض أننا ننتقل من النقطة x إلى النقطة التالية x + hd، حيث d هو اتجاه معين وh هي خطوة بطول معين. وبالتالي تتم الحركة من النقطة (x 1، x 2، ...، x n) إلى النقطة (x 1 + zx 1، x 2 + zx 2، ...، x n + zx n)، أين
يتم تحديد التغيير في قيم الوظائف من خلال العلاقات
| (1.3) |
حتى الدرجة الأولى zx i، مع حساب المشتقات الجزئية عند النقطة x. كيف يجب اختيار الاتجاهات d i التي تحقق المعادلة (1.2) للحصول على أكبر قيمة للتغير في الدالة df؟ هذا هو المكان الذي تنشأ فيه مشكلة التعظيم مع القيد. دعونا نطبق طريقة مضاعفات لاغرانج، والتي من خلالها نحدد الوظيفة
تصل القيمة df المُرضية للقيد (1.2) إلى الحد الأقصى عندما تكون الوظيفة
يصل إلى الحد الأقصى. مشتق منه
لذلك،
 |
(1.6) |
ثم di ~ df/dx i والاتجاه d موازي للاتجاه V/(x) عند النقطة x.
هكذا، أكبر زيادة محليةدالة لخطوة صغيرة معينة h تحدث عندما يكون d هو اتجاه Vf(x) أو g(x) . ولذلك فإن اتجاه الهبوط الأكثر انحدارًا هو الاتجاه
في المزيد في شكل بسيطويمكن كتابة المعادلة (1.3) على النحو التالي:
أين هي الزاوية بين المتجهين Vf(x) و dx. ل قيمة معينة dx نقوم بتقليل df عن طريق اختيار أن اتجاه dx يتزامن مع اتجاه -Vf(x) .
تعليق. اتجاه التدرجعمودي على أي نقطة على خط المستوى الثابت، حيث أن الدالة ثابتة على طول هذا الخط. وبالتالي، إذا كانت (د 1، د 2، ...، د ن) هي خطوة صغيرة على طول خط المستوى، إذن
وبالتالي
 |
(1.8) |
يمكنك أيضًا البحث ليس عن أفضل نقطة في اتجاه التدرج، بل عن نقطة أفضل من النقطة الحالية.
الأسهل في تنفيذ جميع أساليب التحسين المحلية. لقد تماما ظروف ضعيفةالتقارب، ولكن معدل التقارب منخفض جدا (الخطي). غالبًا ما يتم استخدام خطوة أسلوب التدرج كجزء من طرق التحسين الأخرى، مثل طريقة فليتشر-ريفز.
وصف [ | ]
التحسينات[ | ]
تبين أن طريقة النزول المتدرج تكون بطيئة جدًا عند التحرك على طول الوادي، ومع زيادة عدد المتغيرات في الوظيفة الموضوعية، يصبح سلوك الطريقة نموذجيًا. لمكافحة هذه الظاهرة يتم استخدامه، وجوهرها بسيط للغاية. بعد إجراء خطوتين من النزول المتدرج والحصول على ثلاث نقاط، ينبغي اتخاذ الخطوة الثالثة في اتجاه المتجه الذي يربط النقطتين الأولى والثالثة، على طول الجزء السفلي من الوادي.
بالنسبة للدوال القريبة من الدرجة التربيعية، تكون طريقة التدرج المترافق فعالة.
التطبيق في الشبكات العصبية الاصطناعية[ | ]
تُستخدم طريقة النسب المتدرج، مع بعض التعديلات، على نطاق واسع في تدريب الإدراك الحسي، وتُعرف في نظرية الشبكات العصبية الاصطناعية باسم طريقة الانتشار العكسي. عند تدريب شبكة عصبية من نوع الإدراك الحسي، من الضروري تغيير معاملات الترجيح للشبكة لتقليل متوسط الخطأعند مخرج الشبكة العصبية عندما يتم توفير سلسلة من بيانات إدخال التدريب إلى الإدخال. رسميًا، من أجل اتخاذ خطوة واحدة فقط باستخدام طريقة النزول المتدرج (إجراء تغيير واحد فقط في معلمات الشبكة)، من الضروري إرسال مجموعة بيانات التدريب بأكملها بشكل تسلسلي إلى مدخلات الشبكة، وحساب الخطأ لكل كائن من بيانات التدريب وحساب التصحيح اللازم لمعاملات الشبكة (ولكن لا تقم بهذا التصحيح)، وبعد تقديم جميع البيانات، احسب مقدار تصحيح كل معامل شبكة (مجموع التدرجات) وتصحيح المعاملات "خطوة واحدة" . من الواضح أنه مع وجود مجموعة كبيرة من بيانات التدريب، ستعمل الخوارزمية ببطء شديد، لذلك من الناحية العملية، غالبًا ما يتم تعديل معاملات الشبكة بعد كل عنصر تدريب، حيث يتم تقريب قيمة التدرج من خلال تدرج دالة التكلفة، ويتم حسابها على تدريب واحد فقط عنصر. هذه الطريقة تسمى نزول التدرج العشوائي أو نزول التدرج التشغيلي . العشوائية نزول متدرجهو أحد أشكال التقريب العشوائي. توفر نظرية التقريبات العشوائية شروطًا لتقارب طريقة النسب التدرج العشوائي.
روابط [ | ]
- جي ماثيوز.وحدة لطريقة الهبوط الحاد أو التدرج. (الرابط غير متوفر)
الأدب [ | ]
- أكوليتش آي إل.البرمجة الرياضية في الأمثلة والمسائل. - م: الثانوية العامة 1986. - ص298-310.
- جيل إف، موراي دبليو، رايت إم.التحسين العملي = التحسين العملي. - م: مير، 1985.
- كورشونوف يو. كورشونوف يو.الأسس الرياضية لعلم التحكم الآلي. - م: الطاقة الذرية، 1972.
- ماكسيموف يو. فيليبوفسكايا إي.خوارزميات لحل مشاكل البرمجة غير الخطية. - م: ميفي، 1982.
- ماكسيموف يو.خوارزميات للبرمجة الخطية والمنفصلة. - م: ميفي، 1980.
- كورن جي، كورن تي.دليل الرياضيات للعلماء والمهندسين. - م: ناوكا، 1970. - ص 575-576.
- S. Yu. Gorodetsky، V. A. Grishagin.البرمجة غير الخطية والتحسين متعدد الأطراف. - نيجني نوفغورود: دار النشر بجامعة نيجني نوفغورود، 2007. - الصفحات من 357 إلى 363.
عند استخدام طريقة الهبوط الأكثر انحدارًا في كل تكرار، يتم تحديد حجم الخطوة أ ك يتم تحديده من الحد الأدنى لحالة الوظيفة و (خ)في اتجاه الهبوط، أي.
و(س[ك] -أ ك و"(x[ك])) = و(س[ك] -بالعربية"(x[ك])) .
هذا الشرط يعني أن الحركة على طول مضاد التدرج تحدث طالما كانت قيمة الوظيفة و (خ)يتناقص. من وجهة نظر رياضية، في كل تكرار، من الضروري حل مشكلة التقليل أحادي البعد وفقًا لـ أوظائف
ي (أ) = و(س[ك]-أف"(x[ك])) .
خوارزمية طريقة الهبوط الأكثر انحدارًا هي كما يلي.
- 1. قم بتعيين إحداثيات نقطة البداية X.
- 2. عند هذه النقطة X[ك], ك = 0، 1، 2، ... يحسب قيمة التدرج و"(x[ك]) .
- 3. يتم تحديد حجم الخطوة أ k ، عن طريق التقليل أحادي البعد أوظائف ي (أ) = و(س[ك]-أف"(x[ك])).
- 4. يتم تحديد إحداثيات النقطة X[ك+ 1]:
X أنا [ك+ 1]= س أنا [ك] -أ ك و" أنا (x[ك]) ، ط = 1،...، ص.
5. التحقق من شروط إيقاف عملية التعقيم. إذا تم الوفاء بها، فإن الحسابات تتوقف. بخلاف ذلك، انتقل إلى الخطوة 1.
في الطريقة قيد النظر، اتجاه الحركة من النقطة X[ك] يمس خط المستوى عند هذه النقطة س[ك+ 1] (الشكل 2.9). مسار الهبوط متعرج، مع روابط متعرجة مجاورة متعامدة مع بعضها البعض. بالفعل خطوة أيتم اختيار k عن طريق التقليل بواسطة أوظائف؟ (أ) = و(س[ك] -أف"(x[ك])) . شرط أساسيوظيفة الحد الأدنى دي (أ)/دا = 0.بعد حساب مشتق دالة معقدة، نحصل على شرط التعامد لمتجهات اتجاهات الهبوط عند النقاط المجاورة:
دي (أ)/دا = -f"(x[ك+ 1]و"(x[ك]) = 0.
أرز. 2.9.
تتلاقى أساليب التدرج إلى الحد الأدنى مع سرعة عالية(بسرعة التقدم الهندسي) لوظائف محدبة ناعمة. هذه الوظائف لديها أعظم موأقلها مالقيم الذاتية لمصفوفة المشتقات الثانية (مصفوفة هسه)
تختلف قليلا عن بعضها البعض، أي المصفوفة ن (خ)مكيفة بشكل جيد. دعونا نذكركم بذلك القيم الذاتيةل أنا, أنا =1, …, ن، المصفوفات هي جذور المعادلة المميزة
ومع ذلك، في الممارسة العملية، كقاعدة عامة، تحتوي الوظائف التي يتم تصغيرها على مصفوفات غير مشروطة للمشتقات الثانية (ر / م<< 1). تتغير قيم هذه الوظائف في بعض الاتجاهات بشكل أسرع بكثير (أحيانًا بعدة أوامر من حيث الحجم) مقارنة بالاتجاهات الأخرى. تكون أسطحها المستوية في أبسط الحالات ممدودة بقوة (الشكل 2.10)، وفي الحالات الأكثر تعقيدًا تنحني وتبدو مثل الوديان. يتم استدعاء الوظائف مع هذه الخصائص أخدود.ينحرف اتجاه التدرج العكسي لهذه الوظائف (انظر الشكل 2.10) بشكل كبير عن الاتجاه إلى النقطة الدنيا، مما يؤدي إلى تباطؤ في سرعة التقارب.
أرز. 2.10.
ويعتمد معدل تقارب طرق التدرج أيضًا بشكل كبير على دقة حسابات التدرج. يمكن أن يؤدي فقدان الدقة، الذي يحدث عادةً بالقرب من النقاط الدنيا أو في حالة الأخدود، إلى تعطيل تقارب عملية نزول التدرج. للأسباب المذكورة أعلاه، غالبًا ما يتم استخدام أساليب التدرج مع طرق أخرى أكثر فعالية في المرحلة الأولى من حل المشكلة. في هذه الحالة النقطة Xبعيدًا عن النقطة الدنيا، والخطوات في اتجاه التدرج العكسي تجعل من الممكن تحقيق انخفاض كبير في الوظيفة.
