طريقة لاغرانج المعززة

تُعدّ طرق لاغرانج المُعززة فئةً من الخوارزميات لحلّ مسائل التحسين المُقيدة . وهي تُشابه طرق الجزاء في استبدال مسألة التحسين المُقيدة بسلسلة من المسائل غير المُقيدة، وإضافة حدّ جزاء إلى دالة الهدف . إلا أن طريقة لاغرانج المُعززة تُضيف حدًّا آخر مُصمّمًا لمحاكاة مُضاعِف لاغرانج . وترتبط طريقة لاغرانج المُعززة بطريقة مُضاعِفات لاغرانج ، ولكنها ليست مُطابقة لها .

وبنظرة مختلفة، فإن الهدف غير المقيد هو لاغرانجيان المشكلة المقيدة، مع حد جزائي إضافي ( الزيادة ).

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

منذ سبعينيات القرن الماضي، حظيت البرمجة التربيعية المتسلسلة (SQP) وطرق النقطة الداخلية (IPM) باهتمام متزايد، ويعود ذلك جزئيًا إلى سهولة استخدامهما لبرامج فرعية للمصفوفات المتفرقة من مكتبات البرامج العددية ، وجزئيًا إلى امتلاك طرق النقطة الداخلية نتائج مُثبتة في مجال التعقيد استنادًا إلى نظرية الدوال ذاتية التوافق . وقد أُعيد إحياء طريقة لاغرانج المُعززة بفضل أنظمة التحسين LANCELOT وALGENCAN ^{[ 4 ] [ 5 ]} و AMPL ، التي سمحت باستخدام تقنيات المصفوفات المتفرقة على مسائل تبدو كثيفة ولكنها "قابلة للفصل جزئيًا". ولا تزال هذه الطريقة مفيدة لبعض المسائل. ^{[ 6 ]}

في حوالي عام 2007، شهدت طرق لاغرانج المعززة عودةً للانتشار في مجالات مثل إزالة التشويش باستخدام التباين الكلي والاستشعار المضغوط . وعلى وجه الخصوص، حظي نوعٌ من طريقة لاغرانج المعززة القياسية، يستخدم تحديثات جزئية (على غرار طريقة جاوس-سيدل لحل المعادلات الخطية)، والمعروف باسم طريقة الاتجاه المتناوب للمضاعفات أو ADMM، ببعض الاهتمام.

ضع في اعتبارك حل مسألة التحسين المقيد التالية:

${\displaystyle \min f(\mathbf {x} )}$

رهناً بـ

${\displaystyle c_{i}(\mathbf {x} )=0~\forall i\in {\mathcal {E}},}$

أين${\displaystyle {\mathcal {E}}}$تشير إلى مؤشرات قيود المساواة. يمكن حل هذه المسألة كسلسلة من مسائل التصغير غير المقيدة. وللتوضيح، نسرد أولًا الخطوة رقم k من أسلوب الجزاء :

${\displaystyle \min \Phi _{k}(\mathbf {x} )=f(\mathbf {x} )+\mu _{k}~\sum _{i\in {\mathcal {E}}}~c_{i}(\mathbf {x} )^{2}.}$

تقوم طريقة الجزاء بحل هذه المشكلة، ثم في التكرار التالي تعيد حل المشكلة باستخدام قيمة أكبر لـ${\displaystyle \mu _{k}}$واستخدام الحل القديم كتخمين أولي أو "بداية دافئة".

تستخدم طريقة لاغرانج المعززة الهدف غير المقيد التالي:

${\displaystyle \min \Phi _{k}(\mathbf {x} )=f(\mathbf {x} )+{\frac {\mu _{k}}{2}}~\sum _{i\in {\mathcal {E}}}~c_{i}(\mathbf {x} )^{2}+\sum _{i\in {\mathcal {E}}}~\lambda _{i}c_{i}(\mathbf {x} )}$

وبعد كل تكرار، بالإضافة إلى التحديث${\displaystyle \mu _{k}}$المتغير${\displaystyle \lambda }$كما يتم تحديثها وفقًا للقاعدة

${\displaystyle \lambda _{i}\leftarrow \lambda _{i}+\mu _{k}c_{i}(\mathbf {x} _{k})}$

أين${\displaystyle \mathbf {x} _{k}}$يمثل حل المشكلة غير المقيدة في الخطوة k (أي${\displaystyle \mathbf {x} _{k}={\text{argmin}}\Phi _{k}(\mathbf {x} )}$).

المتغير${\displaystyle \lambda }$يمثل هذا تقديرًا لمُضاعِف لاغرانج ، وتتحسن دقة هذا التقدير في كل خطوة. وتتمثل الميزة الرئيسية لهذه الطريقة في أنها، على عكس طريقة الجزاء ، لا تتطلب أخذ${\displaystyle \mu \rightarrow \infty }$لحل المسألة الأصلية المقيدة. بسبب وجود حد مُضاعِف لاغرانج،${\displaystyle \mu }$يمكن أن تبقى أصغر بكثير، وبالتالي تجنب سوء التكييف. ^{[ 6 ]} ومع ذلك، من الشائع في التطبيقات العملية إسقاط تقديرات المضاعفات في مجموعة محدودة كبيرة (ضمانات) مما يتجنب عدم الاستقرار العددي ويؤدي إلى تقارب نظري قوي. ^{[ 5 ]}

يمكن توسيع نطاق هذه الطريقة لتشمل التعامل مع قيود المتباينات. لمناقشة التحسينات العملية، انظر المراجع ^{[ 6 ] و[ 5 ] .}

طريقة الاتجاه المتناوب للمضاعفات (ADMM) هي شكل من أشكال مخطط لاغرانج المعزز الذي يستخدم تحديثات جزئية للمتغيرات الثنائية. غالبًا ما تُطبق هذه الطريقة لحل مسائل مثل:

${\displaystyle \min _{x}f(x)+g(Mx).}$

هذا يعادل المسألة المقيدة،

${\displaystyle \min _{x,y}f(x)+g(y),\quad {\text{subject to}}\quad Mx=y.}$

على الرغم من أن هذا التغيير قد يبدو بسيطًا، إلا أنه يُمكن الآن معالجة المشكلة باستخدام أساليب التحسين المقيد (وخاصةً طريقة لاغرانج المُعززة)، كما أن دالة الهدف قابلة للفصل بدلالة x و y . يتطلب التحديث الثنائي حل دالة تقارب بدلالة x و y في آنٍ واحد؛ تسمح تقنية ADMM بحل هذه المشكلة تقريبًا عن طريق حل المعادلة أولًا لإيجاد قيمة x مع تثبيت y ، ثم حل المعادلة لإيجاد قيمة y مع تثبيت x . بدلًا من تكرار هذه العملية حتى الوصول إلى التقارب (كما في طريقة جاكوبي )، تنتقل خوارزمية ADMM مباشرةً إلى تحديث المتغير الثنائي ثم تُكرر العملية. هذا لا يُعادل التصغير الدقيق، لكن الطريقة لا تزال تتقارب إلى الحل الصحيح في ظل بعض الافتراضات. ولأنها لا تُصغّر دالة لاغرانج المُعززة أو تُصغّرها تقريبًا، فإن هذه الخوارزمية تختلف عن طريقة لاغرانج المُعززة العادية.

يمكن اعتبار خوارزمية ADMM تطبيقًا لخوارزمية تقسيم دوغلاس-راشفورد ، وخوارزمية دوغلاس-راشفورد بدورها هي مثال على خوارزمية النقطة التقريبية ؛ يمكن الاطلاع على التفاصيل في المرجع ^{[ 7 ]} . توجد العديد من حزم البرامج الحديثة، بما في ذلك YALL1 ^{[ 8 ]} (2009) وSpaRSA ^{[ 9 ]} (2009) وSALSA ^{[ 10 ]} (2009)، التي تحل مسائل البحث عن الأساس ومتغيراتها باستخدام خوارزمية ADMM. كما توجد حزم أخرى تستخدم خوارزمية ADMM لحل مسائل أكثر عمومية، بعضها يستفيد من معالجات متعددة النوى (مثل SNAPVX ^{[ 11 ]} (2015) وparADMM ^{[ 12 ]} (2016)).

تُعنى التحسين العشوائي بمشكلة تقليل دالة الخسارة مع إمكانية الوصول إلى عينات مشوشة من تدرج الدالة. والهدف هو الحصول على تقدير للمعامل الأمثل (المُصغِّر) لكل عينة جديدة. مع بعض التعديلات، يمكن استخدام خوارزمية ADMM للتحسين العشوائي. في بيئة عشوائية، لا تتوفر سوى عينات مشوشة من التدرج، لذا يُستخدم تقريب غير دقيق لدالة لاغرانج.

$// ^ {2}+{\frac {\Vert x-x_{k}\Vert ^{2}}{2\eta _{k+1}}},}$

أين${\displaystyle \eta _{k+1}}$^{[ 13 ]} حجم خطوة متغير مع الزمن.

تم تطبيق خوارزمية ADMM لحل المسائل المنتظمة، حيث يمكن إجراء تحسين الدالة والتنظيم محليًا ثم تنسيقهما عالميًا عبر القيود. ^{[ 14 ] [ 15 ] [ 16 ] [ 17 ]}

تُعدّ مسائل التحسين المُنتظم ذات أهمية خاصة في الأنظمة عالية الأبعاد، إذ يُشكّل التنظيم آلية طبيعية للتغلب على عدم استقرار الحلول وتشجيع الاقتصاد في الحل الأمثل (مثل التباعد وانخفاض الرتبة). وقد تعني فعالية خوارزمية ADMM في حلّ المسائل المُنتظمة أنها قد تكون مفيدة في حلّ مسائل التحسين العشوائي عالية الأبعاد.

• البرمجة التربيعية المتسلسلة
• البرمجة الخطية المتسلسلة
• البرمجة الخطية التربيعية المتسلسلة

تطبيقات مفتوحة المصدر وغير مجانية/تجارية لطريقة لاغرانج المعززة:

• Accord.NET (تطبيق بلغة C# لمُحسِّن لاغرانج المُعزَّز)
• ALGLIB (تطبيقات C# و C++ لحل لاغرانج المعزز المشروط مسبقًا)
• بنون (رخصة جنو العمومية 3، رخصة تجارية متاحة)
• لانسلوت (رخصة "للاستخدام الداخلي" مجانية، وخيارات تجارية مدفوعة)
• يستخدم برنامج MINOS أيضًا طريقة لاغرانج المعززة لبعض أنواع المشاكل.
• يتوفر رمز برنامج REASON المرخص بموجب رخصة Apache 2.0 على الإنترنت. ^{[ 18 ]}
• ALGENCAN (تنفيذ Fortran لطريقة لاغرانج المعززة مع الضمانات). متاح عبر الإنترنت. ^{[ 19 ]}
• NLOPT (تنفيذ C++ لمحسن لاغرانج المعزز، يمكن الوصول إليه من لغات برمجة مختلفة ^{[ 20 ] [ 21 ]} ) ^{[ 22 ]}
• PyProximal (تطبيق بايثون لطريقة لاغرانج المعززة). ^{[ 23 ]}

• وظيفة الحاجز
• طريقة النقطة الداخلية
• مضاعف لاغرانج
• طريقة الجزاء

• بيرتسيكاس، ديمتري ب. (1999)، البرمجة غير الخطية (  الطبعة الثانية)، بلمونت، ماساتشوستس: أثينا ساينتيفيك ، ISBN 978-1-886529-00-7
• بيرجين، إي جي؛ مارتينيز، جي إم (2014)، طرق لاغرانجية معززة عملية للتحسين المقيد ، فيلادلفيا: جمعية الرياضيات الصناعية والتطبيقية ، doi : 10.1137/1.9781611973365 ، ISBN 978-1-611973-35-8
• نوسيدال، خورخي؛ رايت، ستيفن جيه. (2006)، التحسين العددي (  الطبعة الثانية)، برلين، نيويورك: سبرينغر-فيرلاغ ، ISBN 978-0-387-30303-1