طريقة التدرج القريب

الموسوعة الحرة

تُعد طرق التدرج التقريبي شكلاً معمماً للإسقاط يستخدم لحل مشاكل التحسين المحدب غير القابلة للتفاضل.

مقارنة بين تكرارات طريقة التدرج المسقط (باللون الأحمر) وطريقة فرانك وولف (باللون الأخضر).

يمكن صياغة العديد من المشكلات المثيرة للاهتمام على شكل مسائل تحسين محدبة من الشكل التالي:

مينx∈Rد∑أنا=1نوأنا(x){\displaystyle \min _{\mathbf {x} \in \mathbb {R} ^{d}}\sum _{i=1}^{n}f_{i}(\mathbf {x} )}

أينوأنا:Rد→R، أنا=1،...،ن{\displaystyle f_{i}:\mathbb {R} ^{d}\rightarrow \mathbb {R} ,\ i=1,\dots ,n}قد تكون هذه الدوال محدبة وغير قابلة للتفاضل . ويستبعد عدم قابليتها للتفاضل استخدام تقنيات التحسين السلس التقليدية مثل طريقة الانحدار الأسرع وطريقة التدرج المترافق ، ولكن يمكن استخدام طرق التدرج التقريبي بدلاً من ذلك.

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

للاطلاع على نظرية طرق التدرج التقريبي من منظور نظرية التعلم الإحصائي وتطبيقاتها ، انظر طرق التدرج التقريبي للتعلم .

الإسقاط على المجموعات المحدبة (POCS)

تُعدّ خوارزمية الإسقاط على المجموعات المحدبة (POCS) إحدى خوارزميات التحسين المحدبة شائعة الاستخدام . تُستخدم هذه الخوارزمية لاستعادة/توليف إشارة تُحقق في آنٍ واحد عدة قيود محدبة.وأنا{\displaystyle f_{i}}لتكن دالة المؤشر لمجموعة محدبة مغلقة غير فارغةجأنا{\displaystyle C_{i}}نمذجة قيد. هذا يختزل إلى مسألة جدوى محدبة، والتي تتطلب منا إيجاد حل يقع في تقاطع جميع المجموعات المحدبة.جأنا{\displaystyle C_{i}}في طريقة POCS، كل مجموعةجأنا{\displaystyle C_{i}}يتم دمجها بواسطة مشغل الإسقاط الخاص بهاPجأنا{\displaystyle P_{C_{i}}}لذا في كل تكرارx{\displaystyle x}يتم تحديثها عند

xك+1=Pج1Pج2⋯Pجنxك{\displaystyle x_{k+1}=P_{C_{1}}P_{C_{2}}\cdots P_{C_{n}}x_{k}}

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

أمثلة

تُعدّ الحالات الخاصة من طرق التدرج التقريبي

انظر أيضاً

ملحوظات

  1. ↑ دوبيشيز، آي؛ ديفريز، إم؛ دي مول، سي (2004). "خوارزمية عتبة تكرارية للمسائل العكسية الخطية مع قيد التباعد". مجلة الاتصالات في الرياضيات البحتة والتطبيقية . 57 (11): 1413-1457 . arXiv : math/0307152 . Bibcode : 2003math......7152D . doi : 10.1002/cpa.20042 .
  2. ↑ تُناقش تفاصيل الطرق التقريبية في: Combettes, Patrick L.; Pesquet, Jean-Christophe (2009). "طرق التقسيم التقريبي في معالجة الإشارات". arXiv : 0912.3522 [ math.OC ].

مراجع

  • روكافيلر، آر تي (1970). التحليل المحدب . برينستون: مطبعة جامعة برينستون.
  • كومبيتس، باتريك ل.؛ بيسكيه، جان كريستوف (2011). خوارزميات النقطة الثابتة للمسائل العكسية في العلوم والهندسة . المجلد  49. الصفحات 185-212 .