خوارزمية فرانك-وولف

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

يفترض${\displaystyle {\mathcal {D}}}$هي مجموعة محدبة متراصة في فضاء متجهي و${\displaystyle f\colon {\mathcal {D}}\to \mathbb {R} }$هي دالة محدبة وقابلة للتفاضل ذات قيم حقيقية . تحل خوارزمية فرانك-وولف مسألة التحسين.

التقليل${\displaystyle f(\mathbf {x} )}$

رهناً بـ${\displaystyle \mathbf {x} \in {\mathcal {D}}}$.

التهيئة: دع${\displaystyle k\leftarrow 0}$ودع${\displaystyle \mathbf {x} _{0}\!}$في أي نقطة${\displaystyle {\mathcal {D}}}$.

الخطوة 1. مسألة فرعية لإيجاد الاتجاه: إيجاد${\displaystyle \mathbf {s} _{k}}$حل

التقليل${\displaystyle \mathbf {s} ^{T}\nabla f(\mathbf {x} _{k})}$

رهناً بـ${\displaystyle \mathbf {s} \in {\mathcal {D}}}$

(التفسير: تقليل التقريب الخطي للمسألة المعطاة بتقريب تايلور من الدرجة الأولى لـ${\displaystyle f}$حول${\displaystyle \mathbf {x} _{k}\!}$مُلزم بالبقاء في${\displaystyle {\mathcal {D}}}$.)

الخطوة 2. تحديد حجم الخطوة: اضبط${\displaystyle \alpha \leftarrow {\frac {2}{k+2}}}$أو بدلاً من ذلك ابحث${\displaystyle \alpha }$ذلك يقلل${\displaystyle f(\mathbf {x} _{k}+\alpha (\mathbf {s} _{k}-\mathbf {x} _{k}))}$رهناً بـ${\displaystyle 0\leq \alpha \leq 1}$.

الخطوة 3. التحديث: دع${\displaystyle \mathbf {x} _{k+1}\leftarrow \mathbf {x} _{k}+\alpha (\mathbf {s} _{k}-\mathbf {x} _{k})}$، يترك${\displaystyle k\leftarrow k+1}$ثم انتقل إلى الخطوة 1.

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

يكون تقارب خوارزمية فرانك-وولف دون الخطي بشكل عام: الخطأ في دالة الهدف بالنسبة للقيمة المثلى هو${\displaystyle O(1/k)}$بعد k تكرار، طالما أن التدرج متصل وفقًا لشرط ليبشيتز بالنسبة لمعيار معين. ويمكن إثبات معدل التقارب نفسه إذا تم حل المسائل الفرعية بشكل تقريبي فقط. ^{[ 3 ]}

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

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

بينما معدل التقارب في أسوأ الحالات مع${\displaystyle O(1/k)}$لا يمكن تحسينها بشكل عام، ولكن يمكن الحصول على تقارب أسرع لفئات معينة من المسائل، مثل بعض المسائل المحدبة بشدة. ^{[ 6 ]}

منذ${\displaystyle f}$يكون محدبًا ، لأي نقطتين${\displaystyle \mathbf {x} ,\mathbf {y} \in {\mathcal {D}}}$لدينا:

${\displaystyle f(\mathbf {y} )\geq f(\mathbf {x} )+(\mathbf {y} -\mathbf {x} )^{T}\nabla f(\mathbf {x} )}$

وينطبق هذا أيضاً على الحل الأمثل (غير المعروف).${\displaystyle \mathbf {x} ^{*}}$. إنه،${\displaystyle f(\mathbf {x} ^{*})\geq f(\mathbf {x} )+(\mathbf {x} ^{*}-\mathbf {x} )^{T}\nabla f(\mathbf {x} )}$أفضل حد أدنى بالنسبة لنقطة معينة${\displaystyle \mathbf {x} }$يُعطى بواسطة

${\displaystyle {\begin{aligned}f(\mathbf {x} ^{*})&\geq f(\mathbf {x} )+(\mathbf {x} ^{*}-\mathbf {x} )^{T}\nabla f(\mathbf {x} )\\&\geq \min _{\mathbf {y} \in D}\left\{f(\mathbf {x} )+(\mathbf {y} -\mathbf {x} )^{T}\nabla f(\mathbf {x} )\right\}\\&=f(\mathbf {x} )-\mathbf {x} ^{T}\nabla f(\mathbf {x} )+\min _{\mathbf {y} \in D}\mathbf {y} ^{T}\nabla f(\mathbf {x} )\end{aligned}}}$

يتم حل مشكلة التحسين الأخيرة في كل تكرار لخوارزمية فرانك-وولف، وبالتالي فإن الحل${\displaystyle \mathbf {s} _{k}}$من المسألة الفرعية لإيجاد الاتجاه في${\displaystyle k}$يمكن استخدام التكرار رقم - لتحديد الحدود الدنيا المتزايدة${\displaystyle l_{k}}$خلال كل تكرار عن طريق التعيين${\displaystyle l_{0}=-\infty }$و

${\displaystyle l_{k}:=\max(l_{k-1},f(\mathbf {x} _{k})+(\mathbf {s} _{k}-\mathbf {x} _{k})^{T}\nabla f(\mathbf {x} _{k}))}$

تُعدّ هذه الحدود الدنيا للقيمة المثلى المجهولة مهمة عمليًا لأنها تُستخدم كمعيار للتوقف، وتُقدّم شهادة فعّالة لجودة التقريب في كل تكرار، حيث إنها دائمًا${\displaystyle l_{k}\leq f(\mathbf {x} ^{*})\leq f(\mathbf {x} _{k})}$.

لقد ثبت أن فجوة الازدواجية المقابلة هذه ، أي الفرق بين${\displaystyle f(\mathbf {x} _{k})}$والحد الأدنى${\displaystyle l_{k}}$، يتناقص بنفس معدل التقارب، أي ${\displaystyle f(\mathbf {x} _{k})-l_{k}=O(1/k).}$

يمكن استخدام خوارزمية فرانك-وولف لحساب توازن واردوب .

• جاغي، مارتن (2013). "إعادة النظر في فرانك-وولف: التحسين المحدب المتفرق بدون إسقاط" . مجلة أبحاث تعلم الآلة: وقائع ورش العمل والمؤتمرات . 28 (1): 427-435 .(ورقة استعراضية)
• وصف خوارزمية فرانك-وولف
• نوسيدال، خورخي؛ رايت، ستيفن جيه. (2006). التحسين العددي (  الطبعة الثانية). برلين، نيويورك: سبرينغر-فيرلاغ . ISBN 978-0-387-30303-1..
• غابور براون، أليخاندرو كارديريرا، سيريل دبليو كومبيتس، حامد حسني، أمين كرباسي، أريان مختاري، وسيباستيان بوكوتا (2025). طرق التدرج الشرطي: من المبادئ الأساسية إلى تطبيقات الذكاء الاصطناعي ، SIAM (سلسلة MOS-SIAM في التحسين)، ISBN 978-1-61197-855-1.

• https://conditional-gradients.org/ : مسح لخوارزميات فرانك وولف.
• مارغريت فرانك تقدم سردًا شخصيًا لتاريخ الخوارزمية

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