الازدواجية (التحسين)

فجوة الازدواجية هي الفرق بين قيم أي حلول أولية وأي حلول ثنائية. إذا${\displaystyle d^{*}}$هي القيمة الثنائية المثلى و${\displaystyle p^{*}}$إذا كانت القيمة الأولية المثلى هي ، فإن فجوة الازدواجية تساوي${\displaystyle p^{*}-d^{*}}$تكون هذه القيمة دائمًا أكبر من أو تساوي صفرًا (في مسائل التصغير). وتكون فجوة الازدواجية صفرًا إذا وفقط إذا تحققت الازدواجية القوية . وإلا، فإن الفجوة تكون موجبة تمامًا وتتحقق الازدواجية الضعيفة . ^{[ 5 ]}

في مجال التحسين الحسابي، يُشار غالبًا إلى "فجوة الازدواجية"، وهي الفرق في القيمة بين أي حل ثنائي وقيمة تكرار ممكن ولكنه دون المستوى الأمثل للمسألة الأصلية. تُحدد هذه "الفجوة" البديلة التباين بين قيمة تكرار ممكن ولكنه دون المستوى الأمثل للمسألة الأصلية وقيمة المسألة الثنائية؛ حيث تساوي قيمة المسألة الثنائية، في ظل شروط الانتظام، قيمة الاسترخاء المحدب للمسألة الأصلية. الاسترخاء المحدب هو المسألة الناشئة عن استبدال مجموعة ممكنة غير محدبة بغلافها المحدب المغلق ، واستبدال دالة غير محدبة بإغلاقها المحدب ، أي الدالة التي يكون الرسم البياني الخاص بها هو الغلاف المحدب المغلق لدالة الهدف الأصلية. ^{[ 6 ] [ 7 ] [ 8 ] [ 9 ] [ 10 ] [ 11 ] [ 12 ] [ 13 ] [ 14 ] [ 15 ] [ 16 ]}

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

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

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

الدافع ^{[ 17 ]}

لنفترض أننا نريد حل مشكلة البرمجة غير الخطية التالية :

${\displaystyle {\begin{aligned}{\text{تقليل }}&f_{0}(x)\\{\text{بشرط }}&f_{i}(x)\leq 0,\ i\in \left\{1,\ldots ,m\right\}\\\end{aligned}}}$

تتضمن المسألة قيودًا؛ ونرغب في تحويلها إلى برنامج بدون قيود. نظريًا، من الممكن القيام بذلك عن طريق تقليل الدالة.${\displaystyle J(x)}$، كما هو مُعرَّف

${\displaystyle J(x)=f_{0}(x)+\sum _{i}I[f_{i}(x)]}$

أين${\displaystyle I}$هي دالة ذات خطوة لانهائية :${\displaystyle I[u]=0}$لو${\displaystyle u\leq 0}$، و${\displaystyle I[u]=\infty }$وإلا. ولكن${\displaystyle J(x)}$يصعب حلها لأنها غير متصلة. من الممكن "تقريبها".${\displaystyle I[u]}$بواسطة${\displaystyle \lambda u}$، أين${\displaystyle \lambda }$هو ثابت موجب. وهذا ينتج عنه دالة تُعرف باسم دالة لاغرانج:

${\displaystyle L(x,\lambda )=f_{0}(x)+\sum _{i}\lambda _{i}f_{i}(x)}$

لاحظ أنه لكل${\displaystyle x}$،

${\displaystyle \max _{\lambda \geq 0}L(x,\lambda )=J(x)}$.

دليل :

• لو${\displaystyle x}$يفي بجميع القيود${\displaystyle f_{i}(x)\leq 0}$، ثم${\displaystyle L(x,\lambda )}$يتم تحقيق أقصى قدر من الفائدة عند تناول${\displaystyle \lambda =0}$وقيمتها إذن${\displaystyle f(x)}$;
• لو${\displaystyle x}$ينتهك بعض القيود،${\displaystyle f_{i}(x)>0}$بالنسبة للبعض${\displaystyle i}$، ثم${\displaystyle L(x,\lambda )\to \infty }$متى${\displaystyle \lambda _{i}\to \infty }$.

وبالتالي، فإن المسألة الأصلية تعادل ما يلي:

${\displaystyle \min _{x}\max _{\lambda \geq 0}L(x,\lambda )}$.

بعكس ترتيب الحد الأدنى والحد الأقصى، نحصل على:

${\displaystyle \max _{\lambda \geq 0}\min _{x}L(x,\lambda )}$.

الدالة المزدوجة هي المشكلة الداخلية في الصيغة أعلاه:

${\displaystyle g(\lambda ):=\min _{x}L(x,\lambda )}$.

البرنامج الثنائي لاغرانجي هو برنامج تعظيم g:

${\displaystyle \max _{\lambda \geq 0}g(\lambda )}$.

الحل الأمثل للبرنامج الثنائي هو حد أدنى للحل الأمثل للبرنامج الأصلي (الأولي)؛ وهذا ما يُعرف بمبدأ الازدواجية الضعيفة . إذا كانت المسألة الأولية محدبة ومحدودة من الأسفل، ووجدت نقطة تتحقق عندها جميع القيود غير الخطية بشكل صارم ( شرط سلاتر )، فإن الحل الأمثل للبرنامج الثنائي يساوي الحل الأمثل للبرنامج الأولي؛ وهذا ما يُعرف بمبدأ الازدواجية القوية . في هذه الحالة، يمكننا حل البرنامج الأولي بإيجاد الحل الأمثل.${\displaystyle \lambda ^{*}}$إلى البرنامج المزدوج، ثم الحل:

${\displaystyle \min _{x}L(x,\lambda ^{*})}$.

لاحظ أنه لاستخدام مبدأ الازدواجية الضعيف أو القوي، نحتاج إلى طريقة للحساب${\displaystyle g(\lambda )}$بشكل عام، قد يكون هذا صعبًا، حيث نحتاج إلى حل مشكلة تصغير مختلفة لكل${\displaystyle \lambda }$لكن بالنسبة لبعض فئات الدوال، من الممكن الحصول على صيغة صريحة لـ${\displaystyle g(\lambda )}$غالبًا ما يكون حلّ البرنامجين الأصلي والثنائي معًا أسهل من حلّ أحدهما فقط. ومن الأمثلة على ذلك البرمجة الخطية والبرمجة التربيعية . ويُقدّم مبرهنة فينكل للثنائية منهجًا أفضل وأكثر عموميةً للثنائية . ^{[ 18 ] : Sub.3.3.1}

هناك حالة أخرى تتساوى فيها القيم الدنيا والقصوى، والقيم القصوى والدنيا، وهي عندما يكون للدالة اللاغرانجية نقطة سرجية :${\displaystyle (x^{*},\lambda ^{*})}$هي نقطة سرجية لدالة لاغرانج${\displaystyle L}$إذا وفقط إذا${\displaystyle x^{*}}$هو الحل الأمثل للمسألة الأولية،${\displaystyle \lambda ^{*}}$يمثل حلاً أمثل للمسألة الثنائية، والقيم المثلى في المسائل المذكورة متساوية. ^{[ 18 ] : الخاصية 3.2.2}

بالنظر إلى مسألة برمجة غير خطية في شكلها القياسي

${\displaystyle {\begin{aligned}{\text{minimize }}&f_{0}(x)\\{\text{subject to }}&f_{i}(x)\leq 0,\ i\in \left\{1,\ldots ,m\right\}\\&h_{i}(x)=0,\ i\in \left\{1,\ldots ,p\right\}\end{aligned}}}$

مع النطاق${\displaystyle {\mathcal {D}}\subset \mathbb {R} ^{n}}$بوجود باطن غير فارغ، دالة لاغرانج${\displaystyle {\mathcal {L}}:\mathbb {R} ^{n}\times \mathbb {R} ^{m}\times \mathbb {R} ^{p}\to \mathbb {R} }$يُعرَّف بأنه

${\displaystyle {\mathcal {L}}(x,\lambda ,\nu )=f_{0}(x)+\sum _{i=1}^{m}\lambda _{i}f_{i}(x)+\sum _{i=1}^{p}\nu _{i}h_{i}(x).}$

المتجهات${\displaystyle \lambda }$و${\displaystyle \nu }$تُسمى هذه المتغيرات بالمتغيرات الثنائية أو متجهات مُضاعِف لاغرانج المرتبطة بالمسألة. دالة لاغرانج الثنائية${\displaystyle g:\mathbb {R} ^{m}\times \mathbb {R} ^{p}\to \mathbb {R} }$يُعرَّف بأنه

${\displaystyle g(\lambda ,\nu )=\inf _{x\in {\mathcal {D}}}{\mathcal {L}}(x,\lambda ,\nu )=\inf _{x\in {\mathcal {D}}}\left\{f_{0}(x)+\sum _{i=1}^{m}\lambda _{i}f_{i}(x)+\sum _{i=1}^{p}\nu _{i}h_{i}(x)\right\}.}$

الوظيفة المزدوجة${\displaystyle g}$تكون الدالة مقعرة، حتى عندما لا تكون المسألة الأولية محدبة، لأنها تمثل قيمة دنيا نقطية للدوال الأفينية. وتعطي الدالة الثنائية حدودًا دنيا للقيمة المثلى.${\displaystyle p^{*}}$من المشكلة الأولية؛ لأي${\displaystyle \lambda \geq 0}$وأي${\displaystyle \nu }$لدينا${\displaystyle g(\lambda ,\nu )\leq p^{*}}$.

إذا تحقق شرط تقييدي مثل شرط سلاتر وكانت المسألة الأصلية محدبة، فإننا نحصل على ازدواجية قوية ، أي${\displaystyle d^{*}=\max _{\lambda \geq 0,\nu }g(\lambda ,\nu )=\inf f_{0}=p^{*}}$.

بالنسبة لمسألة تصغير محدبة ذات قيود متباينة،

${\displaystyle {\begin{aligned}&{\underset {x}{\operatorname {minimize} }}&&f(x)\\&\operatorname {subject\;to} &&g_{i}(x)\leq 0,\quad i=1,\ldots ,m\end{aligned}}}$

مشكلة لاغرانج الثنائية هي

${\displaystyle {\begin{aligned}&{\underset {u}{\operatorname {maximize} }}&&\inf _{x}\left(f(x)+\sum _{j=1}^{m}u_{j}g_{j}(x)\right)\\&\operatorname {subject\;to} &&u_{i}\geq 0,\quad i=1,\ldots ,m\end{aligned}}}$

حيث تكون دالة الهدف هي دالة لاغرانج الثنائية. بشرط أن تكون الدوال${\displaystyle f}$و${\displaystyle g_{1},\ldots ,g_{m}}$إذا كانت الدوال قابلة للتفاضل باستمرار، فإن القيمة الدنيا تحدث عندما يكون التدرج مساوياً للصفر. المشكلة

${\displaystyle {\begin{aligned}&{\underset {x,u}{\operatorname {maximize} }}&&f(x)+\sum _{j=1}^{m}u_{j}g_{j}(x)\\&\operatorname {subject\;to} &&\nabla f(x)+\sum _{j=1}^{m}u_{j}\,\nabla g_{j}(x)=0\\&&&u_{i}\geq 0,\quad i=1,\ldots ,m\end{aligned}}}$

تُسمى هذه المسألة بمسألة وولف الثنائية . قد يكون من الصعب التعامل مع هذه المسألة حسابيًا، لأن دالة الهدف ليست مقعرة في المتغيرات المشتركة.${\displaystyle (u,x)}$. كذلك، قيد المساواة${\displaystyle \nabla f(x)+\sum _{j=1}^{m}u_{j}\,\nabla g_{j}(x)}$هي غير خطية بشكل عام، لذا فإن مسألة وولف الثنائية هي عادةً مسألة تحسين غير محدبة. على أي حال، فإن الثنائية الضعيفة صحيحة. ^{[ 19 ]}

• أهوجا، رافيندرا ك .؛ ماجنانتي، توماس ل .؛ أورلين، جيمس ب. (1993). تدفقات الشبكة: النظرية والخوارزميات والتطبيقات . برنتيس هول. ISBN 0-13-617549-X.
• بيرتسيكاس، ديمتري؛ نيديتش، أنجيليا؛ أوزداغلار، أسومان (2003). التحليل المحدب والتحسين . أثينا ساينتيفيك. ISBN 1-886529-45-0.
• بيرتسيكاس، ديمتري ب. (1999). البرمجة غير الخطية (  الطبعة الثانية). أثينا ساينتيفيك. ISBN 1-886529-00-0.
• بيرتسيكاس، ديمتري ب. (2009). نظرية التحسين المحدب . أثينا ساينتيفيك. ISBN 978-1-886529-31-1.
• بونان، ج.  فريدريك؛ جيلبرت، ج.  تشارلز؛ ليمارشال، كلود ؛ ساغاستيزابال، كلوديا  أ. (2006). التحسين العددي: الجوانب النظرية والعملية . Universitext (الطبعة الثانية المنقحة من ترجمة  الطبعة الفرنسية لعام 1997). برلين: Springer-Verlag. الصفحات:  xiv+490. doi : 10.1007/978-3-540-35447-5 . ISBN 3-540-35445-XMR 2265882 .​ 
• كوك، ويليام ج .؛ كانينغهام، ويليام هـ.؛ بوليبلانك، ويليام ر.؛ شريجفر ، ألكسندر (12 نوفمبر 1997). التحسين التوافقي (  الطبعة الأولى). جون وايلي وأولاده. ISBN 0-471-55894-X.
• دانتزيج، جورج ب. (1963). البرمجة الخطية والامتدادات . برينستون، نيوجيرسي: مطبعة جامعة برينستون.
• هيريارت أوروتي، جان بابتيست؛ ليمارشال، كلود (1993). التحليل المحدب وخوارزميات التقليل، المجلد  الأول: الأساسيات . Grundlehren der Mathematischen Wissenschaften [المبادئ الأساسية للعلوم الرياضية]. المجلد.  305. برلين: سبرينغر-فيرلاغ. ص  الثامن عشر+417. رقم ISBN 3-540-56850-6MR 1261420 .​ 
• هيريارت أوروتي، جان بابتيست؛ ليمارشال، كلود (1993). “14 الازدواجية للممارسين”. التحليل المحدب وخوارزميات التقليل، المجلد  الثاني: النظرية المتقدمة وطرق الحزمة . Grundlehren der Mathematischen Wissenschaften [المبادئ الأساسية للعلوم الرياضية]. المجلد.  306. برلين: سبرينغر-فيرلاغ. ص  الثامن عشر+346. رقم ISBN 3-540-56852-2MR 1295240 .​ 
• لاسدون، ليون  س. (2002) [طبعة مُعاد طباعتها من طبعة ماكميلان لعام 1970]. نظرية التحسين للأنظمة الكبيرة . مينولا، نيويورك: منشورات دوفر. الصفحات:  523 + 13. ISBN 978-0-486-41999-2MR 1888251 .​ 
• لولر، يوجين (2001). "4.5. الآثار التوافقية لنظرية التدفق الأقصى والقطع الأدنى، 4.6. تفسير البرمجة الخطية لنظرية التدفق الأقصى والقطع الأدنى". التحسين التوافقي: الشبكات والمصفوفات . دوفر. ص 117-120 . ISBN  0-486-41453-1.
• ليمارشال، كلود (2001). "استرخاء لاغرانج". في جونجر، مايكل؛ نادف، دينيس (محرران). التحسين التوافقي الحسابي: أوراق من مدرسة الربيع التي عقدت في شلوس داغستوهل،  15-19 مايو  2000 . ملاحظات المحاضرة في علوم الكمبيوتر (LNCS). المجلد.  2241. برلين: سبرينغر-فيرلاغ. ص 112 – 156. دوى : 10.1007 / 3-540-45586-8_4 . رقم ISBN  3-540-42877-1MR 1900016 . S2CID 9048698 .​  
• مينو، ميشيل (1986). البرمجة الرياضية: النظرية والخوارزميات . إيغون بالاس (مقدمة)؛ ستيفن فاجدا (مترجم) من الفرنسية. (1983 باريس: دونود). تشيتشستر: منشورات وايلي-إنترساينس. جون وايلي وأولاده المحدودة. الصفحات:  489 + 28. ISBN 0-471-90170-9. السيد 0868279 . (2008 الطبعة الثانية، بالفرنسية: Programmation mathématique : Théorie et Algorithms ، Éditions Tec & Doc، Paris، 2008. xxx+711 pp. )).  
• نيرينج، إيفار د.؛ تاكر، ألبرت و. (1993). البرمجة الخطية والمسائل ذات الصلة . بوسطن، ماساتشوستس: أكاديميك برس. ISBN 978-0-12-515440-6.
• باباديميتريو، كريستوس هـ.؛ ستيغليتز، كينيث (يوليو 1998). التحسين التوافقي: الخوارزميات والتعقيد (  طبعة كاملة). دوفر. ISBN 0-486-40258-4.
• روسزتشينسكي، أندريه (2006). التحسين غير الخطي . برينستون، نيوجيرسي: مطبعة جامعة برينستون . الصفحات:  454 + 12 صفحة. ISBN 978-0-691-11915-1MR 2199043 .​ 

• إيفريت، هيو الثالث (1963). " طريقة مُضاعِف لاغرانج المُعمَّمة لحل مسائل التخصيص الأمثل للموارد" . بحوث العمليات . 11 (3): 399-417 . doi : 10.1287/opre.11.3.399 . JSTOR 168028. MR 0152360. مؤرشف من الأصل بتاريخ 24-07-2011.  
• كيوييل، كريستوف  سي؛ لارسون، توربيورن؛ ليندبرغ، ب.  أو. (أغسطس 2007). "الاسترخاء اللاغرانجي باستخدام طرق التدرج الفرعي للخطوة الكروية" . رياضيات بحوث العمليات . 32 (3): 669-686 . doi : 10.1287/moor.1070.0261 . MR 2348241. مؤرشف من الأصل في 26 يوليو 2011. تم الاسترجاع في 12 مايو 2011 . 
• الازدواجية في البرمجة الخطية، غاري دي. نوت