طريقة التدرج الفرعي

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

• حجم خطوة ثابت،${\displaystyle \alpha _{k}=\alpha .}$
• طول خطوة ثابت،${\displaystyle \alpha _{k}=\gamma /\lVert g^{(k)}\rVert _{2},}$مما يعطي${\displaystyle \lVert x^{(k+1)}-x^{(k)}\rVert _{2}=\gamma .}$
• حجم الخطوة قابل للجمع التربيعي ولكنه غير قابل للجمع، أي أي أحجام خطوات تحقق$${\displaystyle \alpha _{k}\geq 0,\qquad \sum _{k=1}^{\infty }\alpha _{k}^{2}<\infty ,\qquad \sum _{k=1}^{\infty }\alpha _{k}=\infty .}$$
• تناقص غير قابل للجمع، أي أي أحجام خطوات مُرضية$${\displaystyle \alpha _{k}\geq 0,\qquad \lim _{k\to \infty }\alpha _{k}=0,\qquad \sum _{k=1}^{\infty }\alpha _{k}=\infty .}$$
• أطوال الخطوات المتناقصة غير القابلة للجمع، أي${\displaystyle \alpha _{k}=\gamma _{k}/\lVert g^{(k)}\rVert _{2},}$أين$${\displaystyle \gamma _{k}\geq 0,\qquad \lim _{k\to \infty }\gamma _{k}=0,\qquad \sum _{k=1}^{\infty }\gamma _{k}=\infty .}$$

بالنسبة لجميع القواعد الخمس، تُحدد أحجام الخطوات "خارجياً"، قبل تكرار الطريقة؛ ولا تعتمد أحجام الخطوات على التكرارات السابقة. تختلف خاصية "الخارجية" هذه لطرق التدرج الفرعي عن قواعد حجم الخطوة "المباشرة" المستخدمة في طرق الانحدار للدوال القابلة للتفاضل: إذ أن العديد من طرق تقليل الدوال القابلة للتفاضل تُحقق شروط وولف الكافية للتقارب، حيث تعتمد أحجام الخطوات عادةً على النقطة الحالية واتجاه البحث الحالي. يُقدم نقاش مُفصل حول قواعد حجم الخطوة لطرق التدرج الفرعي، بما في ذلك الإصدارات التزايدية، في كتابي بيرتسيكاس ^{[ 1 ]} وبيرتسيكاس، نيديتش، وأوزداغلار ^{[ 2 ] .}

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

${\displaystyle \lim _{k\to \infty }f_{\rm {best}}^{(k)}-f^{*}<\epsilon }$نتيجة لشور . ^{[ 3 ]}

تتميز طرق التدرج الفرعي الكلاسيكية هذه بأداء ضعيف، ولم تعد موصى بها للاستخدام العام. ^{[ 4 ] [ 5 ]} ومع ذلك، لا تزال تُستخدم على نطاق واسع في التطبيقات المتخصصة نظرًا لبساطتها وسهولة تكييفها للاستفادة من البنية الخاصة للمسألة المطروحة.

إحدى امتدادات طريقة التدرج الفرعي هي طريقة التدرج الفرعي المسقط ، والتي تحل مشكلة التحسين المقيد.

تقليل${\displaystyle f(x)\ }$رهناً بـ$${\displaystyle x\in {\mathcal {C}}}$$

أين${\displaystyle {\mathcal {C}}}$هي مجموعة محدبة . تستخدم طريقة التدرج الفرعي المسقط التكرار $${\displaystyle x^{(k+1)}=P\left(x^{(k)}-\alpha _{k}g^{(k)}\right)}$$ أين${\displaystyle P}$هو إسقاط على${\displaystyle {\mathcal {C}}}$و${\displaystyle g^{(k)}}$أي تدرج فرعي من${\displaystyle f\ }$في${\displaystyle x^{(k)}.}$

يمكن توسيع طريقة التدرج الفرعي لحل مشكلة القيود غير المتكافئة

تقليل${\displaystyle f_{0}(x)\ }$رهناً بـ$${\displaystyle f_{i}(x)\leq 0,\quad i=1,\ldots ,m}$$

أين${\displaystyle f_{i}}$محدبة. تأخذ الخوارزمية نفس شكل الحالة غير المقيدة $${\displaystyle x^{(k+1)}=x^{(k)}-\alpha _{k}g^{(k)}\ }$$ أين${\displaystyle \alpha _{k}>0}$وهي حجم الخطوة، و${\displaystyle g^{(k)}}$هو تدرج فرعي للدالة الهدف أو لإحدى دوال القيد عند${\displaystyle x.\ }$ يأخذ $${\displaystyle g^{(k)}={\begin{cases}\partial f_{0}(x)&{\text{ if }}f_{i}(x)\leq 0\;\forall i=1\dots m\\\partial f_{j}(x)&{\text{ for some }}j{\text{ such that }}f_{j}(x)>0\end{cases}}}$$ أين${\displaystyle \partial f}$يشير إلى التفاضل الجزئي لـ${\displaystyle f.\ }$ إذا كانت النقطة الحالية قابلة للتطبيق، فإن الخوارزمية تستخدم تدرجًا فرعيًا موضوعيًا؛ وإذا كانت النقطة الحالية غير قابلة للتطبيق، فإن الخوارزمية تختار تدرجًا فرعيًا لأي قيد منتهك.